miden_protocol/block/account_tree/
mod.rs

1use alloc::string::ToString;
2use alloc::vec::Vec;
3
4use crate::Word;
5use crate::account::{AccountId, AccountIdPrefix};
6use crate::crypto::merkle::MerkleError;
7use crate::crypto::merkle::smt::{MutationSet, SMT_DEPTH, Smt, SmtLeaf};
8use crate::errors::AccountTreeError;
9use crate::utils::serde::{
10    ByteReader,
11    ByteWriter,
12    Deserializable,
13    DeserializationError,
14    Serializable,
15};
16
17mod partial;
18pub use partial::PartialAccountTree;
19
20mod witness;
21pub use witness::AccountWitness;
22
23mod backend;
24pub use backend::AccountTreeBackend;
25
26mod account_id_key;
27pub use account_id_key::AccountIdKey;
28
29// ACCOUNT TREE
30// ================================================================================================
31
32/// The sparse merkle tree of all accounts in the blockchain.
33///
34/// The key is the [`AccountId`] while the value is the current state commitment of the account,
35/// i.e. [`Account::to_commitment`](crate::account::Account::to_commitment). If the account is new,
36/// then the commitment is the [`EMPTY_WORD`](crate::EMPTY_WORD).
37///
38/// Each account ID occupies exactly one leaf in the tree, which is identified by its
39/// [`AccountId::prefix`]. In other words, account ID prefixes are unique in the blockchain.
40#[derive(Debug, Clone, PartialEq, Eq)]
41pub struct AccountTree<S = Smt> {
42    smt: S,
43}
44
45impl<S> Default for AccountTree<S>
46where
47    S: Default,
48{
49    fn default() -> Self {
50        Self { smt: Default::default() }
51    }
52}
53
54impl<S> AccountTree<S>
55where
56    S: AccountTreeBackend<Error = MerkleError>,
57{
58    // CONSTANTS
59    // --------------------------------------------------------------------------------------------
60
61    /// The depth of the account tree.
62    pub const DEPTH: u8 = SMT_DEPTH;
63
64    /// The index of the account ID suffix in the SMT key.
65    pub(super) const KEY_SUFFIX_IDX: usize = 2;
66    /// The index of the account ID prefix in the SMT key.
67    pub(super) const KEY_PREFIX_IDX: usize = 3;
68
69    // CONSTRUCTORS
70    // --------------------------------------------------------------------------------------------
71
72    /// Creates a new `AccountTree` from its inner representation with validation.
73    ///
74    /// This constructor validates that the provided SMT upholds the guarantees of the
75    /// [`AccountTree`]. The constructor ensures only the uniqueness of the account ID prefix.
76    ///
77    /// # Errors
78    ///
79    /// Returns an error if:
80    /// - The SMT contains invalid account IDs.
81    /// - The SMT contains duplicate account ID prefixes.
82    pub fn new(smt: S) -> Result<Self, AccountTreeError> {
83        for (_leaf_idx, leaf) in smt.leaves() {
84            match leaf {
85                SmtLeaf::Empty(_) => {
86                    // Empty leaves are fine (shouldn't be returned by leaves() but handle anyway)
87                    continue;
88                },
89                SmtLeaf::Single((key, _)) => {
90                    // Single entry is good - verify it's a valid account ID
91                    AccountIdKey::try_from_word(key).map_err(|err| {
92                        AccountTreeError::InvalidAccountIdKey { key, source: err }
93                    })?;
94                },
95                SmtLeaf::Multiple(entries) => {
96                    // Multiple entries means duplicate prefixes
97                    // Extract one of the keys to identify the duplicate prefix
98                    if let Some((key, _)) = entries.first() {
99                        let key = *key;
100                        let account_id = AccountIdKey::try_from_word(key).map_err(|err| {
101                            AccountTreeError::InvalidAccountIdKey { key, source: err }
102                        })?;
103
104                        return Err(AccountTreeError::DuplicateIdPrefix {
105                            duplicate_prefix: account_id.prefix(),
106                        });
107                    }
108                },
109            }
110        }
111
112        Ok(Self::new_unchecked(smt))
113    }
114
115    /// Creates a new `AccountTree` from its inner representation without validation.
116    ///
117    /// # Warning
118    ///
119    /// Assumes the provided SMT upholds the guarantees of the [`AccountTree`]. Specifically:
120    /// - Each account ID prefix must be unique (no duplicate prefixes allowed)
121    /// - The SMT should only contain valid account IDs and their state commitments
122    ///
123    /// See type-level documentation for more details on these invariants. Using this constructor
124    /// with an SMT that violates these guarantees may lead to undefined behavior.
125    pub fn new_unchecked(smt: S) -> Self {
126        AccountTree { smt }
127    }
128
129    // PUBLIC ACCESSORS
130    // --------------------------------------------------------------------------------------------
131
132    /// Returns an opening of the leaf associated with the `account_id`. This is a proof of the
133    /// current state commitment of the given account ID.
134    ///
135    /// Conceptually, an opening is a Merkle path to the leaf, as well as the leaf itself.
136    ///
137    /// # Panics
138    ///
139    /// Panics if the SMT backend fails to open the leaf (only possible with `LargeSmt` backend).
140    pub fn open(&self, account_id: AccountId) -> AccountWitness {
141        let key = AccountIdKey::from(account_id).as_word();
142        let proof = self.smt.open(&key);
143
144        AccountWitness::from_smt_proof(account_id, proof)
145    }
146
147    /// Returns the current state commitment of the given account ID.
148    pub fn get(&self, account_id: AccountId) -> Word {
149        let key = AccountIdKey::from(account_id).as_word();
150        self.smt.get_value(&key)
151    }
152
153    /// Returns the root of the tree.
154    pub fn root(&self) -> Word {
155        self.smt.root()
156    }
157
158    /// Returns true if the tree contains a leaf for the given account ID prefix.
159    pub fn contains_account_id_prefix(&self, account_id_prefix: AccountIdPrefix) -> bool {
160        let key = Self::id_prefix_to_smt_key(account_id_prefix);
161        let is_empty = matches!(self.smt.get_leaf(&key), SmtLeaf::Empty(_));
162        !is_empty
163    }
164
165    /// Returns the number of account IDs in this tree.
166    pub fn num_accounts(&self) -> usize {
167        // Because each ID's prefix is unique in the tree and occupies a single leaf, the number of
168        // IDs in the tree is equivalent to the number of leaves in the tree.
169        self.smt.num_leaves()
170    }
171
172    /// Returns an iterator over the account ID state commitment pairs in the tree.
173    pub fn account_commitments(&self) -> impl Iterator<Item = (AccountId, Word)> {
174        self.smt.leaves().map(|(_leaf_idx, leaf)| {
175            // SAFETY: By construction no Multiple variant is ever present in the tree.
176            // The Empty variant is not returned by Smt::leaves, because it only returns leaves that
177            // are actually present.
178            let SmtLeaf::Single((key, commitment)) = leaf else {
179                unreachable!("empty and multiple variant should never be encountered")
180            };
181
182            (
183                // SAFETY: By construction, the tree only contains valid IDs.
184                AccountId::try_from_elements(key[Self::KEY_SUFFIX_IDX], key[Self::KEY_PREFIX_IDX])
185                    .expect("account tree should only contain valid IDs"),
186                commitment,
187            )
188        })
189    }
190
191    /// Computes the necessary changes to insert the specified (account ID, state commitment) pairs
192    /// into this tree, allowing for validation before applying those changes.
193    ///
194    /// [`Self::apply_mutations`] can be used in order to commit these changes to the tree.
195    ///
196    /// If the `concurrent` feature of `miden-crypto` is enabled, this function uses a parallel
197    /// implementation to compute the mutations, otherwise it defaults to the sequential
198    /// implementation.
199    ///
200    /// This is a thin wrapper around [`Smt::compute_mutations`]. See its documentation for more
201    /// details.
202    ///
203    /// # Errors
204    ///
205    /// Returns an error if:
206    /// - an insertion of an account ID would violate the uniqueness of account ID prefixes in the
207    ///   tree.
208    /// - the list of provided account updates contains duplicates.
209    pub fn compute_mutations(
210        &self,
211        account_commitments: impl IntoIterator<Item = (AccountId, Word)>,
212    ) -> Result<AccountMutationSet, AccountTreeError> {
213        let mutation_set = self
214            .smt
215            .compute_mutations(Vec::from_iter(
216                account_commitments
217                    .into_iter()
218                    .map(|(id, commitment)| (AccountIdKey::from(id).as_word(), commitment)),
219            ))
220            .map_err(AccountTreeError::ComputeMutations)?;
221
222        for id_key in mutation_set.new_pairs().keys() {
223            // Check if the insertion would be valid.
224            match self.smt.get_leaf(id_key) {
225                // Inserting into an empty leaf is valid.
226                SmtLeaf::Empty(_) => (),
227                SmtLeaf::Single((existing_key, _)) => {
228                    // If the key matches the existing one, then we're updating the leaf, which is
229                    // valid. If it does not match, then we would insert a duplicate.
230                    if existing_key != *id_key {
231                        return Err(AccountTreeError::DuplicateIdPrefix {
232                            duplicate_prefix: AccountIdKey::try_from_word(*id_key)
233                                .expect("account tree should only contain valid IDs")
234                                .prefix(),
235                        });
236                    }
237                },
238                SmtLeaf::Multiple(_) => {
239                    unreachable!(
240                        "account tree should never contain duplicate ID prefixes and therefore never a multiple leaf"
241                    )
242                },
243            }
244        }
245
246        Ok(AccountMutationSet::new(mutation_set))
247    }
248
249    // PUBLIC MUTATORS
250    // --------------------------------------------------------------------------------------------
251
252    /// Inserts the state commitment for the given account ID, returning the previous state
253    /// commitment associated with that ID.
254    ///
255    /// This also recomputes all hashes between the leaf (associated with the key) and the root,
256    /// updating the root itself.
257    ///
258    /// # Errors
259    ///
260    /// Returns an error if:
261    /// - the prefix of the account ID already exists in the tree.
262    pub fn insert(
263        &mut self,
264        account_id: AccountId,
265        state_commitment: Word,
266    ) -> Result<Word, AccountTreeError> {
267        let key = AccountIdKey::from(account_id).as_word();
268        // SAFETY: account tree should not contain multi-entry leaves and so the maximum number
269        // of entries per leaf should never be exceeded.
270        let prev_value = self.smt.insert(key, state_commitment)
271            .expect("account tree should always have a single value per key, and hence cannot exceed the maximum leaf number");
272
273        // If the leaf of the account ID now has two or more entries, we've inserted a duplicate
274        // prefix.
275        if self.smt.get_leaf(&key).num_entries() >= 2 {
276            return Err(AccountTreeError::DuplicateIdPrefix {
277                duplicate_prefix: account_id.prefix(),
278            });
279        }
280
281        Ok(prev_value)
282    }
283
284    /// Applies the prospective mutations computed with [`Self::compute_mutations`] to this tree.
285    ///
286    /// # Errors
287    ///
288    /// Returns an error if:
289    /// - `mutations` was computed on a tree with a different root than this one.
290    pub fn apply_mutations(
291        &mut self,
292        mutations: AccountMutationSet,
293    ) -> Result<(), AccountTreeError> {
294        self.smt
295            .apply_mutations(mutations.into_mutation_set())
296            .map_err(AccountTreeError::ApplyMutations)
297    }
298
299    /// Applies the prospective mutations computed with [`Self::compute_mutations`] to this tree
300    /// and returns the reverse mutation set.
301    ///
302    /// Applying the reverse mutation sets to the updated tree will revert the changes.
303    ///
304    /// # Errors
305    ///
306    /// Returns an error if:
307    /// - `mutations` was computed on a tree with a different root than this one.
308    pub fn apply_mutations_with_reversion(
309        &mut self,
310        mutations: AccountMutationSet,
311    ) -> Result<AccountMutationSet, AccountTreeError> {
312        let reversion = self
313            .smt
314            .apply_mutations_with_reversion(mutations.into_mutation_set())
315            .map_err(AccountTreeError::ApplyMutations)?;
316        Ok(AccountMutationSet::new(reversion))
317    }
318
319    // HELPERS
320    // --------------------------------------------------------------------------------------------
321
322    /// Returns the SMT key of the given account ID prefix.
323    fn id_prefix_to_smt_key(account_id: AccountIdPrefix) -> Word {
324        // We construct this in such a way that we're forced to use the constants, so that when
325        // they're updated, the other usages of the constants are also updated.
326        let mut key = Word::empty();
327        key[Self::KEY_PREFIX_IDX] = account_id.as_felt();
328
329        key
330    }
331}
332
333// SERIALIZATION
334// ================================================================================================
335
336impl Serializable for AccountTree {
337    fn write_into<W: ByteWriter>(&self, target: &mut W) {
338        self.account_commitments().collect::<Vec<_>>().write_into(target);
339    }
340}
341
342impl Deserializable for AccountTree {
343    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
344        let entries = Vec::<(AccountId, Word)>::read_from(source)?;
345
346        // Validate uniqueness of account ID prefixes before creating the tree
347        let mut seen_prefixes = alloc::collections::BTreeSet::new();
348        for (id, _) in &entries {
349            if !seen_prefixes.insert(id.prefix()) {
350                return Err(DeserializationError::InvalidValue(format!(
351                    "Duplicate account ID prefix: {}",
352                    id.prefix()
353                )));
354            }
355        }
356
357        // Create the SMT with validated entries
358        let smt = Smt::with_entries(
359            entries.into_iter().map(|(k, v)| (AccountIdKey::from(k).as_word(), v)),
360        )
361        .map_err(|err| DeserializationError::InvalidValue(err.to_string()))?;
362        Ok(Self::new_unchecked(smt))
363    }
364}
365
366// ACCOUNT MUTATION SET
367// ================================================================================================
368
369/// A newtype wrapper around a [`MutationSet`] for use in the [`AccountTree`].
370///
371/// It guarantees that applying the contained mutations will result in an account tree with unique
372/// account ID prefixes.
373///
374/// It is returned by and used in methods on the [`AccountTree`].
375#[derive(Debug, Clone, PartialEq, Eq)]
376pub struct AccountMutationSet {
377    mutation_set: MutationSet<SMT_DEPTH, Word, Word>,
378}
379
380impl AccountMutationSet {
381    // CONSTRUCTORS
382    // --------------------------------------------------------------------------------------------
383
384    /// Creates a new [`AccountMutationSet`] from the provided raw mutation set.
385    fn new(mutation_set: MutationSet<SMT_DEPTH, Word, Word>) -> Self {
386        Self { mutation_set }
387    }
388
389    // PUBLIC ACCESSORS
390    // --------------------------------------------------------------------------------------------
391
392    /// Returns a reference to the underlying [`MutationSet`].
393    pub fn as_mutation_set(&self) -> &MutationSet<SMT_DEPTH, Word, Word> {
394        &self.mutation_set
395    }
396
397    // PUBLIC MUTATORS
398    // --------------------------------------------------------------------------------------------
399
400    /// Consumes self and returns the underlying [`MutationSet`].
401    pub fn into_mutation_set(self) -> MutationSet<SMT_DEPTH, Word, Word> {
402        self.mutation_set
403    }
404}
405
406// TESTS
407// ================================================================================================
408
409#[cfg(test)]
410pub(super) mod tests {
411    use std::vec::Vec;
412
413    use assert_matches::assert_matches;
414
415    use super::*;
416    use crate::account::AccountType;
417    use crate::testing::account_id::{AccountIdBuilder, account_id};
418
419    pub(crate) fn setup_duplicate_prefix_ids() -> [(AccountId, Word); 2] {
420        let id0 = AccountId::try_from(account_id(AccountType::Public, 0xaabb_ccdd)).unwrap();
421        let id1 = AccountId::try_from(account_id(AccountType::Public, 0xaabb_ccff)).unwrap();
422        assert_eq!(id0.prefix(), id1.prefix(), "test requires that these ids have the same prefix");
423
424        let commitment0 = Word::from([0, 0, 0, 42u32]);
425        let commitment1 = Word::from([0, 0, 0, 24u32]);
426
427        assert_eq!(id0.prefix(), id1.prefix(), "test requires that these ids have the same prefix");
428        [(id0, commitment0), (id1, commitment1)]
429    }
430
431    #[test]
432    fn insert_fails_on_duplicate_prefix() {
433        let mut tree = AccountTree::<Smt>::default();
434        let [(id0, commitment0), (id1, commitment1)] = setup_duplicate_prefix_ids();
435
436        tree.insert(id0, commitment0).unwrap();
437        assert_eq!(tree.get(id0), commitment0);
438
439        let err = tree.insert(id1, commitment1).unwrap_err();
440
441        assert_matches!(err, AccountTreeError::DuplicateIdPrefix {
442          duplicate_prefix
443        } if duplicate_prefix == id0.prefix());
444    }
445
446    #[test]
447    fn insert_succeeds_on_multiple_updates() {
448        let mut tree = AccountTree::<Smt>::default();
449        let [(id0, commitment0), (_, commitment1)] = setup_duplicate_prefix_ids();
450
451        tree.insert(id0, commitment0).unwrap();
452        tree.insert(id0, commitment1).unwrap();
453        assert_eq!(tree.get(id0), commitment1);
454    }
455
456    #[test]
457    fn apply_mutations() {
458        let id0 = AccountIdBuilder::new().build_with_seed([5; 32]);
459        let id1 = AccountIdBuilder::new().build_with_seed([6; 32]);
460        let id2 = AccountIdBuilder::new().build_with_seed([7; 32]);
461
462        let digest0 = Word::from([0, 0, 0, 1u32]);
463        let digest1 = Word::from([0, 0, 0, 2u32]);
464        let digest2 = Word::from([0, 0, 0, 3u32]);
465        let digest3 = Word::from([0, 0, 0, 4u32]);
466
467        let mut tree = AccountTree::with_entries([(id0, digest0), (id1, digest1)]).unwrap();
468
469        let mutations = tree
470            .compute_mutations([(id0, digest1), (id1, digest2), (id2, digest3)])
471            .unwrap();
472
473        tree.apply_mutations(mutations).unwrap();
474
475        assert_eq!(tree.num_accounts(), 3);
476        assert_eq!(tree.get(id0), digest1);
477        assert_eq!(tree.get(id1), digest2);
478        assert_eq!(tree.get(id2), digest3);
479    }
480
481    #[test]
482    fn duplicates_in_compute_mutations() {
483        let [pair0, pair1] = setup_duplicate_prefix_ids();
484        let id2 = AccountIdBuilder::new().build_with_seed([5; 32]);
485        let commitment2 = Word::from([0, 0, 0, 99u32]);
486
487        let tree = AccountTree::with_entries([pair0, (id2, commitment2)]).unwrap();
488        let err = tree.compute_mutations([pair1]).unwrap_err();
489
490        assert_matches!(err, AccountTreeError::DuplicateIdPrefix {
491          duplicate_prefix
492        } if duplicate_prefix == pair1.0.prefix());
493    }
494
495    #[test]
496    fn account_commitments() {
497        let id0 = AccountIdBuilder::new().build_with_seed([5; 32]);
498        let id1 = AccountIdBuilder::new().build_with_seed([6; 32]);
499        let id2 = AccountIdBuilder::new().build_with_seed([7; 32]);
500
501        let digest0 = Word::from([0, 0, 0, 1u32]);
502        let digest1 = Word::from([0, 0, 0, 2u32]);
503        let digest2 = Word::from([0, 0, 0, 3u32]);
504        let empty_digest = Word::empty();
505
506        let mut tree =
507            AccountTree::with_entries([(id0, digest0), (id1, digest1), (id2, digest2)]).unwrap();
508
509        // remove id2
510        tree.insert(id2, empty_digest).unwrap();
511
512        assert_eq!(tree.num_accounts(), 2);
513
514        let accounts: Vec<_> = tree.account_commitments().collect();
515        assert_eq!(accounts.len(), 2);
516        assert!(accounts.contains(&(id0, digest0)));
517        assert!(accounts.contains(&(id1, digest1)));
518    }
519
520    #[test]
521    fn account_witness() {
522        let id0 = AccountIdBuilder::new().build_with_seed([5; 32]);
523        let id1 = AccountIdBuilder::new().build_with_seed([6; 32]);
524
525        let digest0 = Word::from([0, 0, 0, 1u32]);
526        let digest1 = Word::from([0, 0, 0, 2u32]);
527
528        let tree = AccountTree::with_entries([(id0, digest0), (id1, digest1)]).unwrap();
529
530        assert_eq!(tree.num_accounts(), 2);
531
532        for id in [id0, id1] {
533            let proof = tree.smt.open(&AccountIdKey::from(id).as_word());
534            let (control_path, control_leaf) = proof.into_parts();
535            let witness = tree.open(id);
536
537            assert_eq!(witness.leaf(), control_leaf);
538            assert_eq!(witness.path(), &control_path);
539        }
540    }
541
542    #[test]
543    fn contains_account_prefix() {
544        // Create a tree with a single account.
545        let [pair0, pair1] = setup_duplicate_prefix_ids();
546        let tree = AccountTree::with_entries([pair0]).unwrap();
547        assert_eq!(tree.num_accounts(), 1);
548
549        // Validate the leaf for the inserted account exists.
550        assert!(tree.contains_account_id_prefix(pair0.0.prefix()));
551
552        // Validate the leaf for the uninserted account with same prefix exists.
553        assert!(tree.contains_account_id_prefix(pair1.0.prefix()));
554
555        // Validate the unrelated, uninserted account leaf does not exist.
556        let id1 = AccountIdBuilder::new().build_with_seed([7; 32]);
557        assert!(!tree.contains_account_id_prefix(id1.prefix()));
558    }
559
560    #[cfg(feature = "std")]
561    #[test]
562    fn large_smt_backend_basic_operations() {
563        use miden_crypto::merkle::smt::{LargeSmt, MemoryStorage};
564
565        // Create test data
566        let id0 = AccountIdBuilder::new().build_with_seed([5; 32]);
567        let id1 = AccountIdBuilder::new().build_with_seed([6; 32]);
568        let id2 = AccountIdBuilder::new().build_with_seed([7; 32]);
569
570        let digest0 = Word::from([0, 0, 0, 1u32]);
571        let digest1 = Word::from([0, 0, 0, 2u32]);
572        let digest2 = Word::from([0, 0, 0, 3u32]);
573
574        // Create AccountTree with LargeSmt backend
575        let tree = LargeSmt::<MemoryStorage>::with_entries(
576            MemoryStorage::default(),
577            [
578                (AccountIdKey::from(id0).as_word(), digest0),
579                (AccountIdKey::from(id1).as_word(), digest1),
580            ],
581        )
582        .map(AccountTree::new_unchecked)
583        .unwrap();
584
585        // Test basic operations
586        assert_eq!(tree.num_accounts(), 2);
587        assert_eq!(tree.get(id0), digest0);
588        assert_eq!(tree.get(id1), digest1);
589
590        // Test opening
591        let witness0 = tree.open(id0);
592        assert_eq!(witness0.id(), id0);
593
594        // Test mutations
595        let mut tree_mut = LargeSmt::<MemoryStorage>::with_entries(
596            MemoryStorage::default(),
597            [
598                (AccountIdKey::from(id0).as_word(), digest0),
599                (AccountIdKey::from(id1).as_word(), digest1),
600            ],
601        )
602        .map(AccountTree::new_unchecked)
603        .unwrap();
604        tree_mut.insert(id2, digest2).unwrap();
605        assert_eq!(tree_mut.num_accounts(), 3);
606        assert_eq!(tree_mut.get(id2), digest2);
607
608        // Verify original tree unchanged
609        assert_eq!(tree.num_accounts(), 2);
610    }
611
612    #[cfg(feature = "std")]
613    #[test]
614    fn large_smt_backend_duplicate_prefix_check() {
615        use miden_crypto::merkle::smt::{LargeSmt, MemoryStorage};
616
617        let [(id0, commitment0), (id1, commitment1)] = setup_duplicate_prefix_ids();
618
619        let mut tree = AccountTree::new_unchecked(LargeSmt::new(MemoryStorage::default()).unwrap());
620
621        tree.insert(id0, commitment0).unwrap();
622        assert_eq!(tree.get(id0), commitment0);
623
624        let err = tree.insert(id1, commitment1).unwrap_err();
625
626        assert_matches!(
627            err,
628            AccountTreeError::DuplicateIdPrefix { duplicate_prefix }
629            if duplicate_prefix == id0.prefix()
630        );
631    }
632
633    #[cfg(feature = "std")]
634    #[test]
635    fn large_smt_backend_apply_mutations() {
636        use miden_crypto::merkle::smt::{LargeSmt, MemoryStorage};
637
638        let id0 = AccountIdBuilder::new().build_with_seed([5; 32]);
639        let id1 = AccountIdBuilder::new().build_with_seed([6; 32]);
640        let id2 = AccountIdBuilder::new().build_with_seed([7; 32]);
641
642        let digest0 = Word::from([0, 0, 0, 1u32]);
643        let digest1 = Word::from([0, 0, 0, 2u32]);
644        let digest2 = Word::from([0, 0, 0, 3u32]);
645        let digest3 = Word::from([0, 0, 0, 4u32]);
646
647        let mut tree = LargeSmt::with_entries(
648            MemoryStorage::default(),
649            [
650                (AccountIdKey::from(id0).as_word(), digest0),
651                (AccountIdKey::from(id1).as_word(), digest1),
652            ],
653        )
654        .map(AccountTree::new_unchecked)
655        .unwrap();
656
657        let mutations = tree
658            .compute_mutations([(id0, digest1), (id1, digest2), (id2, digest3)])
659            .unwrap();
660
661        tree.apply_mutations(mutations).unwrap();
662
663        assert_eq!(tree.num_accounts(), 3);
664        assert_eq!(tree.get(id0), digest1);
665        assert_eq!(tree.get(id1), digest2);
666        assert_eq!(tree.get(id2), digest3);
667    }
668
669    #[cfg(feature = "std")]
670    #[test]
671    fn large_smt_backend_same_root_as_regular_smt() {
672        use miden_crypto::merkle::smt::{LargeSmt, MemoryStorage};
673
674        let id0 = AccountIdBuilder::new().build_with_seed([5; 32]);
675        let id1 = AccountIdBuilder::new().build_with_seed([6; 32]);
676
677        let digest0 = Word::from([0, 0, 0, 1u32]);
678        let digest1 = Word::from([0, 0, 0, 2u32]);
679
680        // Create tree with LargeSmt backend
681        let large_tree = LargeSmt::with_entries(
682            MemoryStorage::default(),
683            [
684                (AccountIdKey::from(id0).as_word(), digest0),
685                (AccountIdKey::from(id1).as_word(), digest1),
686            ],
687        )
688        .map(AccountTree::new_unchecked)
689        .unwrap();
690
691        // Create tree with regular Smt backend
692        let regular_tree = AccountTree::with_entries([(id0, digest0), (id1, digest1)]).unwrap();
693
694        // Both should have the same root
695        assert_eq!(large_tree.root(), regular_tree.root());
696
697        // Both should have the same account commitments
698        let large_commitments: std::collections::BTreeMap<_, _> =
699            large_tree.account_commitments().collect();
700        let regular_commitments: std::collections::BTreeMap<_, _> =
701            regular_tree.account_commitments().collect();
702
703        assert_eq!(large_commitments, regular_commitments);
704    }
705}
miden_protocol/block/account_tree/mod.rs

miden_protocol/block/account_tree/
mod.rs
