openvm_sdk/prover/deferral/
merkle.rs

1use openvm_circuit::{
2    arch::instructions::DEFERRAL_AS,
3    system::memory::{dimensions::MemoryDimensions, merkle::MerkleTree},
4};
5use openvm_stark_backend::p3_field::PrimeCharacteristicRing;
6use openvm_stark_sdk::config::baby_bear_poseidon2::{DIGEST_SIZE, F};
7use openvm_verify_stark_host::deferral::DeferralMerkleProofs;
8
9/// Compute deferral merkle proofs from the initial and final memory merkle trees.
10///
11/// Proofs have length `overall_height()`. When `depth > 0`, the first `depth` entries
12/// are zeros (skipped levels covered by the deferral subtree). The final deferral
13/// subtree is required by the verifier to be rooted at node_idx 0.
14pub fn compute_deferral_merkle_proofs(
15    memory_dimensions: MemoryDimensions,
16    initial_merkle_tree: &MerkleTree<F, DIGEST_SIZE>,
17    final_merkle_tree: &MerkleTree<F, DIGEST_SIZE>,
18    depth: usize,
19) -> DeferralMerkleProofs<F> {
20    let initial_merkle_proof =
21        deferral_merkle_proof_from_tree(memory_dimensions, initial_merkle_tree, depth);
22    let final_merkle_proof =
23        deferral_merkle_proof_from_tree(memory_dimensions, final_merkle_tree, depth);
24    DeferralMerkleProofs {
25        initial_merkle_proof,
26        final_merkle_proof,
27    }
28}
29
30/// Extract one side of the deferral merkle proof from a memory merkle tree.
31///
32/// Returns a full-length proof (`overall_height()` entries). The first `depth` entries
33/// are zeros; the remaining entries are siblings from the tree.
34fn deferral_merkle_proof_from_tree(
35    memory_dimensions: MemoryDimensions,
36    merkle_tree: &MerkleTree<F, DIGEST_SIZE>,
37    depth: usize,
38) -> Vec<[F; DIGEST_SIZE]> {
39    let overall_height = memory_dimensions.overall_height();
40
41    // Leaf index for DEFERRAL_AS, block_id=0 in the full tree (1-indexed).
42    let leaf_idx = (1u64 << overall_height) + memory_dimensions.label_to_index((DEFERRAL_AS, 0));
43    debug_assert_eq!(leaf_idx % 2, 0);
44
45    // Start at level `depth` above the leaf. When `depth == 0`, the first node in the
46    // path is the right sibling of the node at `leaf_idx`.
47    let mut node_idx = if depth == 0 {
48        leaf_idx + 1
49    } else {
50        leaf_idx >> depth
51    };
52
53    // Pad the first `depth` entries with zeros (skipped levels).
54    let mut proof = vec![[F::ZERO; DIGEST_SIZE]; depth];
55
56    // Collect siblings from depth up to the root.
57    while node_idx > 1 {
58        let sibling_idx = node_idx ^ 1;
59        proof.push(merkle_tree.get_node(sibling_idx));
60        node_idx >>= 1;
61    }
62
63    assert_eq!(proof.len(), overall_height);
64    proof
65}
openvm_sdk/prover/deferral/merkle.rs

openvm_sdk/prover/deferral/
merkle.rs
