7.1 LMSR Implementation Details

Implementing LMSR on-chain requires careful optimization due to compute constraints and the mathematical complexity of exponential and logarithmic functions.

Fixed-Point Arithmetic

Solana programs cannot use floating-point operations. Path Protocol implements LMSR using fixed-point arithmetic:

// Fixed-point representation: multiply by 10^6 for precision
const FIXED_POINT_SCALE: u128 = 1_000_000;

// Example: 1.5 represented as 1_500_000
// Example: 0.001 represented as 1_000

Exponential Approximation

The LMSR cost function requires computing e^(q_i/b). Path uses a Taylor series approximation:

/// Approximates e^x using Taylor series: e^x ≈ 1 + x + x²/2! + x³/3! + ...
/// Limited to 10 terms for compute efficiency
pub fn fixed_point_exp(x: u64, b: u64) -> Result<u128> {
    // Calculate x/b ratio in fixed point
    let ratio = (x as u128 * FIXED_POINT_SCALE) / b as u128;

    // Taylor series terms
    let mut result = FIXED_POINT_SCALE; // 1.0
    let mut term = FIXED_POINT_SCALE;

    for n in 1..=10 {
        term = (term  ratio) / (FIXED_POINT_SCALE  n as u128);
        result += term;

        if term < 100 { break; } // Early termination for small terms
    }

    Ok(result)
}

Accuracy:

For x/b ratios in range [-5, 5], Taylor series with 10 terms achieves <0.01% error.

Logarithm Approximation

For ln(x), Path uses a piecewise linear approximation with lookup tables:

/// Approximates ln(x) using lookup table + linear interpolation
pub fn fixed_point_ln(x: u128) -> Result<u64> {
    // Lookup table for ln(x) at key points
    const LN_TABLE: &[(u128, u64)] = &[
        (1_000_000, 0),           // ln(1) = 0
        (2_718_282, 1_000_000),   // ln(e) = 1
        (7_389_056, 2_000_000),   // ln(e²) = 2
        // ... more entries
    ];

    // Binary search + linear interpolation
    // ...
}

Alternative: For higher accuracy requirements, Path may use Solana's log2 syscall combined with change-of-base formula:

ln(x) = log2(x) / log2(e)
      = log2(x) × ln(2)

Cost Function Implementation

/// Calculate LMSR cost: C(q) = b × ln(Σ e^(q_i/b))
pub fn cost_function(
    b: u64,
    shares: &[u64],
) -> Result<u64> {
    let b_u128 = b as u128;
    let mut sum_exp: u128 = 0;

    // Calculate Σ e^(q_i/b)
    for &q_i in shares.iter() {
        let exp_term = fixed_point_exp(q_i, b)?;
        sum_exp = sum_exp
            .checked_add(exp_term)
            .ok_or(ErrorCode::MathOverflow)?;
    }

    // Calculate b × ln(sum)
    let ln_sum = fixed_point_ln(sum_exp)?;
    let cost = (b_u128 * ln_sum as u128) / FIXED_POINT_SCALE;

    Ok(cost as u64)
}

Compute Units:

• Binary market (N=2): ~30,000 CU

• 5-outcome market: ~60,000 CU

• 10-outcome market: ~100,000 CU

Well within Solana's 200,000 CU instruction limit.

Price Calculation

/// Calculate marginal price: P_i = e^(q_i/b) / Σ e^(q_j/b)
pub fn marginal_price(
    b: u64,
    shares: &[u64],
    outcome_index: u8,
) -> Result<u64> {
    let mut sum_exp: u128 = 0;
    let mut outcome_exp: u128 = 0;

    for (idx, &q_i) in shares.iter().enumerate() {
        let exp_term = fixed_point_exp(q_i, b)?;
        sum_exp += exp_term;

        if idx == outcome_index as usize {
            outcome_exp = exp_term;
        }
    }

    // Price = outcome_exp / sum_exp (in fixed point)
    let price = (outcome_exp * FIXED_POINT_SCALE) / sum_exp;

    Ok(price as u64)
}

Output Format:

Prices returned as basis points (10000 = 100%):

• 5000 = 50%

• 7500 = 75%

• 2500 = 25%

Buy Shares Calculation

Finding the number of shares for a given cost requires solving:

C_after - C_before = cost

Where: C = b × ln(Σ e^(q_i/b))

This is solved iteratively using binary search:

pub fn calculate_shares_from_cost(
    b: u64,
    current_shares: &[u64],
    outcome_index: u8,
    cost: u64,
) -> Result<u64> {
    let c_before = cost_function(b, current_shares)?;
    let target_cost = c_before + cost;

    // Binary search for share quantity
    let mut low: u64 = 0;
    let mut high: u64 = cost * 10; // Upper bound estimate
    let mut iterations = 0;

    while iterations < 20 && high - low > 100 {
        let mid = (low + high) / 2;

        let mut test_shares = current_shares.to_vec();
        test_shares[outcome_index as usize] += mid;

        let c_after = cost_function(b, &test_shares)?;

        if c_after < target_cost {
            low = mid;
        } else {
            high = mid;
        }

        iterations += 1;
    }

    Ok(low)
}

Convergence:

Typically converges in 10-15 iterations with <0.1% precision.