miden_protocol/block/account_tree/
witness.rs

1use alloc::string::ToString;
2
3use miden_crypto::merkle::smt::{LeafIndex, SMT_DEPTH, SmtLeaf, SmtProof, SmtProofError};
4use miden_crypto::merkle::{InnerNodeInfo, SparseMerklePath};
5
6use crate::Word;
7use crate::account::AccountId;
8use crate::block::account_tree::{account_id_to_smt_key, smt_key_to_account_id};
9use crate::errors::AccountTreeError;
10use crate::utils::{ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable};
11
12// ACCOUNT WITNESS
13// ================================================================================================
14
15/// A specialized version of an [`SmtProof`] for use in [`AccountTree`](super::AccountTree) and
16/// [`PartialAccountTree`](super::PartialAccountTree). It proves the inclusion of an account
17/// ID at a certain state (i.e. [`Account::commitment`](crate::account::Account::commitment)) in the
18/// [`AccountTree`](super::AccountTree).
19///
20/// By construction the witness can only represent the equivalent of an [`SmtLeaf`] with zero or one
21/// entries, which guarantees that the account ID prefix it represents is unique in the tree.
22///
23/// # Guarantees
24///
25/// This type guarantees that:
26/// - its MerklePath is of depth [`SMT_DEPTH`].
27/// - converting this type into an [`SmtProof`] results in a leaf with zero or one entries, i.e. the
28///   account ID prefix is unique.
29#[derive(Debug, Clone, PartialEq, Eq)]
30pub struct AccountWitness {
31    /// The account ID that this witness proves inclusion for.
32    id: AccountId,
33    /// The state commitment of the account ID.
34    commitment: Word,
35    /// The merkle path of the account witness.
36    path: SparseMerklePath,
37}
38
39impl AccountWitness {
40    /// Constructs a new [`AccountWitness`] from the provided parts.
41    ///
42    /// # Errors
43    ///
44    /// Returns an error if:
45    /// - the merkle path's depth is not [`SMT_DEPTH`].
46    pub fn new(
47        account_id: AccountId,
48        commitment: Word,
49        path: SparseMerklePath,
50    ) -> Result<Self, AccountTreeError> {
51        if path.depth() != SMT_DEPTH {
52            return Err(AccountTreeError::WitnessMerklePathDepthDoesNotMatchAccountTreeDepth(
53                path.depth() as usize,
54            ));
55        }
56
57        Ok(Self::new_unchecked(account_id, commitment, path))
58    }
59
60    /// Creates an [`AccountWitness`] from the provided proof and the account ID for which the proof
61    /// was requested.
62    ///
63    /// # Warning
64    ///
65    /// This should only be called on SMT proofs retrieved from (partial) account tree, because it
66    /// relies on the guarantees of those types.
67    ///
68    /// # Panics
69    ///
70    /// Panics if:
71    /// - the merkle path in the proof does not have depth equal to [`SMT_DEPTH`].
72    /// - the proof contains an SmtLeaf::Multiple.
73    pub(super) fn from_smt_proof(requested_account_id: AccountId, proof: SmtProof) -> Self {
74        // Check which account ID this proof actually contains. We rely on the fact that the
75        // trees only contain zero or one entry per account ID prefix.
76        //
77        // If the requested account ID matches an existing ID's prefix but their suffixes do
78        // not match, then this witness is for the _existing ID_.
79        //
80        // Otherwise, if the ID matches the one in the leaf or if it's empty, the witness is
81        // for the requested ID.
82        let witness_id = match proof.leaf() {
83            SmtLeaf::Empty(_) => requested_account_id,
84            SmtLeaf::Single((key_in_leaf, _)) => {
85                // SAFETY: By construction, the tree only contains valid IDs.
86                smt_key_to_account_id(*key_in_leaf)
87            },
88            SmtLeaf::Multiple(_) => {
89                unreachable!("account tree should only contain zero or one entry per ID prefix")
90            },
91        };
92
93        let commitment = proof
94            .get(&account_id_to_smt_key(witness_id))
95            .expect("we should have received a proof for the witness key");
96
97        // SAFETY: The proof is guaranteed to have depth SMT_DEPTH if it comes from one of
98        // the account trees.
99        debug_assert_eq!(proof.path().depth(), SMT_DEPTH);
100
101        AccountWitness::new_unchecked(witness_id, commitment, proof.into_parts().0)
102    }
103
104    /// Constructs a new [`AccountWitness`] from the provided parts.
105    ///
106    /// # Warning
107    ///
108    /// This does not validate any of the guarantees of this type.
109    pub(super) fn new_unchecked(
110        account_id: AccountId,
111        commitment: Word,
112        path: SparseMerklePath,
113    ) -> Self {
114        Self { id: account_id, commitment, path }
115    }
116
117    /// Returns the underlying [`AccountId`] that this witness proves inclusion for.
118    pub fn id(&self) -> AccountId {
119        self.id
120    }
121
122    /// Returns the state commitment of the account witness.
123    pub fn state_commitment(&self) -> Word {
124        self.commitment
125    }
126
127    /// Returns the [`SparseMerklePath`] of the account witness.
128    pub fn path(&self) -> &SparseMerklePath {
129        &self.path
130    }
131
132    /// Returns the [`SmtLeaf`] of the account witness.
133    pub fn leaf(&self) -> SmtLeaf {
134        if self.commitment == Word::empty() {
135            let leaf_idx = LeafIndex::from(account_id_to_smt_key(self.id));
136            SmtLeaf::new_empty(leaf_idx)
137        } else {
138            let key = account_id_to_smt_key(self.id);
139            SmtLeaf::new_single(key, self.commitment)
140        }
141    }
142
143    /// Consumes self and returns the inner proof.
144    pub fn into_proof(self) -> SmtProof {
145        let leaf = self.leaf();
146        debug_assert_eq!(self.path.depth(), SMT_DEPTH);
147        SmtProof::new(self.path, leaf)
148            .expect("merkle path depth should be the SMT depth by construction")
149    }
150
151    /// Returns an iterator over every inner node of this witness' merkle path.
152    pub fn authenticated_nodes(&self) -> impl Iterator<Item = InnerNodeInfo> + '_ {
153        let leaf = self.leaf();
154        self.path()
155            .authenticated_nodes(leaf.index().value(), leaf.hash())
156            .expect("leaf index is u64 and should be less than 2^SMT_DEPTH")
157    }
158}
159
160impl From<AccountWitness> for SmtProof {
161    fn from(witness: AccountWitness) -> Self {
162        witness.into_proof()
163    }
164}
165
166// SERIALIZATION
167// ================================================================================================
168
169impl Serializable for AccountWitness {
170    fn write_into<W: ByteWriter>(&self, target: &mut W) {
171        self.id.write_into(target);
172        self.commitment.write_into(target);
173        self.path.write_into(target);
174    }
175}
176
177impl Deserializable for AccountWitness {
178    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
179        let id = AccountId::read_from(source)?;
180        let commitment = Word::read_from(source)?;
181        let path = SparseMerklePath::read_from(source)?;
182
183        if path.depth() != SMT_DEPTH {
184            return Err(DeserializationError::InvalidValue(
185                SmtProofError::InvalidMerklePathLength(path.depth() as usize).to_string(),
186            ));
187        }
188
189        Ok(Self { id, commitment, path })
190    }
191}
miden_protocol/block/account_tree/witness.rs

miden_protocol/block/account_tree/
witness.rs
