Crate p3_miden_lmcs 

Lifted Matrix Commitment Scheme (LMCS) for matrices with power-of-two heights.

This crate provides a Merkle tree commitment scheme optimized for matrices that store polynomial evaluations in bit-reversed order over multiplicative cosets.

Main Types

• LmcsConfig: Configuration holding cryptographic primitives (sponge + compression) with packed types for SIMD parallelization.
• Lmcs: Trait for LMCS configurations, providing type-erased access to commitment operations.
• LmcsTree: Trait for built LMCS trees, providing opening operations.
• LiftedMerkleTree: The underlying Merkle tree data structure.
• Proof: Single-opening proof with rows, optional salt, and authentication path.
• BatchProof: Parsed batch opening from transcript hints.

API Overview

Direct Usage (Simple)

use p3_miden_lmcs::{HidingLmcsConfig, Lmcs, LmcsConfig, LmcsTree};
use p3_miden_transcript::{ProverTranscript, VerifierTranscript};

// Config captures PF, PD (packed types), H, C, WIDTH, DIGEST
// F = PF::Value and D = PD::Value are derived
let config = LmcsConfig::<PF, PD, _, _, WIDTH, DIGEST>::new(sponge, compress);
let challenger = /* ... */;

// Build tree - no turbofish needed, packed types are known from config
let tree = config.build_aligned_tree(matrices);
let root = tree.root();
let mut prover_channel = ProverTranscript::new(challenger);
tree.prove_batch(&indices, &mut prover_channel);
let (_, transcript) = prover_channel.finalize();

let mut verifier_channel = VerifierTranscript::from_data(challenger, &transcript);
let rows = config.open_batch(&root, &widths, log_max_height, &indices, &mut verifier_channel)?;

// For hiding commitment with salt, use HidingLmcsConfig with RNG
let hiding_config =
    HidingLmcsConfig::<PF, PD, _, _, _, WIDTH, DIGEST, 4>::new(sponge, compress, rng);
let tree = hiding_config.build_aligned_tree(matrices);

Trait-Based Usage (for generic code like FRI)

use p3_miden_lmcs::{Lmcs, LmcsTree};
use p3_miden_transcript::ProverTranscript;

fn commit_and_open<L: Lmcs>(lmcs: &L, matrices: Vec<impl Matrix<L::F>>) {
    let tree = lmcs.build_aligned_tree(matrices);
    let commitment = tree.root();
    let challenger = /* ... */;
    let mut channel = ProverTranscript::new(challenger);
    tree.prove_batch(&[0, 1, 2], &mut channel);
    // ...
}

Transcript Hints

For the LmcsConfig/LiftedMerkleTree implementation in this crate, batch openings are streamed as transcript hints: for each unique query index in sorted tree index order (ascending, deduplicated), prove_batch writes one row per matrix (in tree leaf order) followed by optional salt. After all indices, missing sibling hashes are emitted level-by-level in canonical left-to-right, bottom-to-top order. Hints are not observed into the Fiat-Shamir challenger.

LmcsConfig::open_batch consumes only the hints it needs to reconstruct the root; extra hint data is left unread. It expects widths and log_max_height to match the committed tree and treats empty indices as invalid. Use BatchProof::read_from_channel if you need to parse hints without hashing; then call BatchProof::single_proofs with an LMCS config to reconstruct per-index proofs (keyed by index) without verifying against a commitment.

Mathematical Foundation

Consider a polynomial f(X) of degree less than d, and let g be the coset generator and K a subgroup of order n ≥ d with primitive root ω. The coset evaluations {f(g·ω^j) : j ∈ [0, n)} can be stored in two orderings:

• Canonical order: [f(g·ω^0), f(g·ω^1), ..., f(g·ω^{n-1})]
• Bit-reversed order: [f(g·ω^{bitrev(0)}), f(g·ω^{bitrev(1)}), ..., f(g·ω^{bitrev(n-1)})]

where bitrev(i) is the bit-reversal of index i within log2(n) bits.

Lifting by Upsampling

When we have matrices with different heights n₀ ≤ n₁ ≤ … ≤ nₜ₋₁ (each a power of two), we “lift” smaller matrices to the maximum height N = nₜ₋₁ using nearest-neighbor upsampling: each row is repeated contiguously r = N/n times.

For a matrix of height n lifted to N, the index map is: i ↦ floor(i / r) = i >> log2(r)

Example (n=4, N=8):

• Original rows: [row0, row1, row2, row3]
• Upsampled: [row0, row0, row1, row1, row2, row2, row3, row3] (blocks of 2)

Why Upsampling for Bit-Reversed Data

Given bit-reversed evaluations of f(X) over a coset gK where |K| = n, upsampling to height N = n · r (where r = 2^k) produces the bit-reversed evaluations of f'(X) = f(Xʳ) over the coset gK' where |K'| = N.

Mathematically, if the input contains f(g·(ω_n)^{bitrev_n(j)}) at index j, then after upsampling, each index i in [0, N) maps to the original index j = i >> k, giving:

upsampled[i] = f(g·(ω_n)^{bitrev_n(i >> k)}) = f'(g·(ω_N)^{bitrev_N(i)})

where f'(X) = f(Xʳ). This is exactly the bit-reversed evaluation of f' over gK'.

Opening Semantics

When opening at index i, we retrieve the value at position i in the bit-reversed list. For the lifted polynomial f'(X) = f(Xʳ), this gives f'(g·(ω_N)^{bitrev_N(i)}).

Equivalently, this is f'(g·ξ^i) where ξ = (ω_N)^{bitrev_N(i)} is the i-th element when iterating over K' in the order induced by bit-reversed indices.

Equivalence to Cyclic Lifting

Upsampling bit-reversed data is equivalent to cyclically repeating canonically-ordered data:

Upsample(BitReverse(data)) = BitReverse(Cyclic(data))

where cyclic repetition tiles the original n rows periodically: [row0, row1, ..., row_{n-1}, row0, ...].

This equivalence follows from the bit-reversal identity: for r = N/n = 2^k, bitrev_N(i) mod n = bitrev_n(i >> k).

Re-exports

pub use proof::BatchProof;

pub use proof::LeafOpening;

pub use proof::Proof;

pub use utils::RowList;

pub use utils::log2_strict_u8;

Modules

mmcs

MMCS trait implementation for LMCS configurations.

proof

Single-opening proof structures and transcript parsing helpers.

utils

Utility functions for LMCS operations.

Structs

HidingLmcsConfig

Configuration for hiding LMCS with random salt.

LiftedMerkleTree

A uniform binary Merkle tree whose leaves are constructed from matrices with power-of-two heights.

LmcsConfig

LMCS configuration holding cryptographic primitives (sponge + compression).

Enums

LmcsError

Errors that can occur during LMCS operations.

Traits

Lmcs

Trait for LMCS configurations.

LmcsTree

Trait for built LMCS trees.

Type Aliases

OpenedRows

Opened rows keyed by leaf index, returned by Lmcs::open_batch.