openvm_verify_stark_host/
deferral.rs

1use openvm_circuit::{
2    arch::instructions::DEFERRAL_AS, system::memory::dimensions::MemoryDimensions,
3};
4use openvm_stark_backend::codec::{DecodableConfig, EncodableConfig};
5use openvm_stark_sdk::config::baby_bear_poseidon2::{
6    poseidon2_compress_with_capacity, BabyBearPoseidon2Config as SC, DIGEST_SIZE, F,
7};
8use p3_field::PrimeCharacteristicRing;
9
10use crate::error::VerifyStarkError;
11
12/// Deferral Merkle proofs connecting `initial_acc_hash` and `final_acc_hash` to the
13/// initial and final memory roots. Both proofs have length `overall_height()`.
14/// When `depth > 0`, the first `depth` entries are zeros (skipped levels covered by
15/// the deferral subtree). The final aggregated deferral public values must have
16/// `node_idx == 0`; this proof starts from that canonical subtree location.
17#[derive(Clone, Debug)]
18pub struct DeferralMerkleProofs<F> {
19    pub initial_merkle_proof: Vec<[F; DIGEST_SIZE]>,
20    pub final_merkle_proof: Vec<[F; DIGEST_SIZE]>,
21}
22
23impl DeferralMerkleProofs<F> {
24    pub fn encode<W: std::io::Write>(&self, writer: &mut W) -> std::io::Result<()> {
25        SC::encode_digest_slice(&self.initial_merkle_proof, writer)?;
26        SC::encode_digest_slice(&self.final_merkle_proof, writer)?;
27        Ok(())
28    }
29
30    pub fn decode<R: std::io::Read>(reader: &mut R) -> std::io::Result<Self> {
31        let initial_merkle_proof = SC::decode_digest_vec(reader)?;
32        let final_merkle_proof = SC::decode_digest_vec(reader)?;
33        Ok(Self {
34            initial_merkle_proof,
35            final_merkle_proof,
36        })
37    }
38
39    /// Verify that `initial_acc_hash` and `final_acc_hash` are committed into `initial_root`
40    /// and `final_root` respectively via the deferral address space Merkle path.
41    ///
42    /// `depth` is the deferral subtree depth: when `depth == 0` the acc hashes are "unset"
43    /// (the leaf is `compress(acc_hash, [0; DIGEST_SIZE])`), otherwise the leaf is `acc_hash`
44    /// directly and the first `depth` proof siblings are skipped.
45    pub fn verify(
46        &self,
47        memory_dimensions: MemoryDimensions,
48        initial_root: [F; DIGEST_SIZE],
49        final_root: [F; DIGEST_SIZE],
50        initial_acc_hash: [F; DIGEST_SIZE],
51        final_acc_hash: [F; DIGEST_SIZE],
52        depth: usize,
53    ) -> Result<(), VerifyStarkError> {
54        let overall_height = memory_dimensions.overall_height();
55        if self.initial_merkle_proof.len() != overall_height {
56            return Err(VerifyStarkError::DeferralMerkleProofLengthMismatch {
57                expected: overall_height,
58                actual: self.initial_merkle_proof.len(),
59            });
60        }
61        if self.final_merkle_proof.len() != overall_height {
62            return Err(VerifyStarkError::DeferralMerkleProofLengthMismatch {
63                expected: overall_height,
64                actual: self.final_merkle_proof.len(),
65            });
66        }
67
68        if depth > memory_dimensions.address_height {
69            return Err(VerifyStarkError::DeferralDepthTooLarge {
70                depth,
71                address_height: memory_dimensions.address_height,
72            });
73        }
74
75        for i in 0..memory_dimensions.address_height {
76            if self.initial_merkle_proof[i] != self.final_merkle_proof[i] {
77                return Err(VerifyStarkError::DeferralMerkleProofSiblingMismatch {
78                    depth: i,
79                    initial: self.initial_merkle_proof[i],
80                    final_: self.final_merkle_proof[i],
81                });
82            }
83        }
84
85        let is_unset = depth == 0;
86        let idx_prefix =
87            usize::try_from(memory_dimensions.label_to_index((DEFERRAL_AS, 0))).unwrap();
88
89        // When unset, the leaf is compress(acc_hash, zeros); otherwise it's acc_hash directly.
90        let initial_leaf = if is_unset {
91            poseidon2_compress_with_capacity(initial_acc_hash, [F::ZERO; DIGEST_SIZE]).0
92        } else {
93            initial_acc_hash
94        };
95        let final_leaf = if is_unset {
96            poseidon2_compress_with_capacity(final_acc_hash, [F::ZERO; DIGEST_SIZE]).0
97        } else {
98            final_acc_hash
99        };
100
101        let computed_initial_root =
102            merkle_path_root(initial_leaf, &self.initial_merkle_proof, idx_prefix, depth);
103        if computed_initial_root != initial_root {
104            return Err(VerifyStarkError::DeferralInitialRootMismatch {
105                expected: initial_root,
106                actual: computed_initial_root,
107            });
108        }
109
110        let computed_final_root =
111            merkle_path_root(final_leaf, &self.final_merkle_proof, idx_prefix, depth);
112        if computed_final_root != final_root {
113            return Err(VerifyStarkError::DeferralFinalRootMismatch {
114                expected: final_root,
115                actual: computed_final_root,
116            });
117        }
118
119        Ok(())
120    }
121}
122
123/// Walk a Merkle path from `leaf` to root, skipping the first `depth` levels. `idx_prefix`
124/// determines which side the node is on at each level (bit i => right child). The first
125/// node is a right node if depth == 0.
126fn merkle_path_root(
127    leaf: [F; DIGEST_SIZE],
128    proof: &[[F; DIGEST_SIZE]],
129    idx_prefix: usize,
130    depth: usize,
131) -> [F; DIGEST_SIZE] {
132    let mut node = leaf;
133    for (i, sibling) in proof.iter().enumerate() {
134        if i < depth {
135            continue;
136        }
137        let is_right = (depth == 0 && i == 0) || (idx_prefix >> i) & 1 == 1;
138        node = if is_right {
139            poseidon2_compress_with_capacity(*sibling, node).0
140        } else {
141            poseidon2_compress_with_capacity(node, *sibling).0
142        };
143    }
144    node
145}
openvm_verify_stark_host/deferral.rs

openvm_verify_stark_host/
deferral.rs
