mina_tree/sparse_ledger/
sparse_ledger.rs

1use std::{
2    collections::{BTreeMap, HashMap, VecDeque},
3    sync::{Arc, Mutex},
4};
5
6use ark_ff::Zero;
7use mina_core::constants::constraint_constants;
8use mina_curves::pasta::Fp;
9use mina_p2p_messages::bigint::InvalidBigInt;
10
11use crate::{
12    scan_state::{
13        conv::to_ledger_hash,
14        currency::{Amount, Signed, Slot},
15        transaction_logic::{
16            apply_zkapp_command_first_pass_aux, apply_zkapp_command_second_pass_aux,
17            local_state::LocalStateEnv,
18            protocol_state::{GlobalState, ProtocolStateView},
19            transaction_applied::ZkappCommandApplied,
20            transaction_partially_applied::ZkappCommandPartiallyApplied,
21            zkapp_command::ZkAppCommand,
22            AccountState,
23        },
24    },
25    Account, AccountId, AccountIndex, Address, HashesMatrix, Mask, MerklePath,
26};
27
28use super::{sparse_ledger_impl::SparseLedgerImpl, LedgerIntf};
29
30#[derive(Clone, Debug)]
31pub struct SparseLedger {
32    // Using a mutex for now but this can be replaced with a RefCell
33    inner: Arc<Mutex<SparseLedgerImpl<AccountId, Account>>>,
34}
35
36impl PartialEq for SparseLedger {
37    fn eq(&self, other: &Self) -> bool {
38        if Arc::as_ptr(&self.inner) == Arc::as_ptr(&other.inner) {
39            return true;
40        }
41
42        let this = self.inner.try_lock().unwrap();
43        let other = other.inner.try_lock().unwrap();
44
45        this.eq(&other)
46    }
47}
48
49impl SparseLedger {
50    fn with<F, R>(&self, fun: F) -> R
51    where
52        F: FnOnce(&mut SparseLedgerImpl<AccountId, Account>) -> R,
53    {
54        let mut inner = self.inner.try_lock().expect("lock failed");
55        fun(&mut inner)
56    }
57}
58
59impl SparseLedger {
60    pub fn create(depth: usize, root_hash: Fp) -> Self {
61        let inner = SparseLedgerImpl::create(depth, root_hash);
62        Self {
63            inner: Arc::new(Mutex::new(inner)),
64        }
65    }
66
67    pub fn of_ledger_subset_exn(oledger: Mask, keys: &[AccountId]) -> Self {
68        let inner = SparseLedgerImpl::of_ledger_subset_exn(oledger, keys);
69        Self {
70            inner: Arc::new(Mutex::new(inner)),
71        }
72    }
73
74    pub fn copy_content(&self) -> Self {
75        let inner = self.with(|this| this.clone());
76        Self {
77            inner: Arc::new(Mutex::new(inner)),
78        }
79    }
80
81    pub fn has_locked_tokens_exn(&self, global_slot: Slot, account_id: AccountId) -> bool {
82        self.with(|this| this.has_locked_tokens_exn(global_slot, account_id))
83    }
84
85    pub fn iteri<F>(&self, fun: F)
86    where
87        F: Fn(Address, &Account),
88    {
89        self.with(|this| this.iteri(fun))
90    }
91
92    pub fn add_path(
93        &mut self,
94        merkle_path: &[MerklePath],
95        account_id: AccountId,
96        account: Account,
97    ) {
98        self.with(|this| this.add_path(merkle_path, account_id, account))
99    }
100
101    #[inline(never)]
102    pub fn get_exn(&self, addr: &Address) -> Box<Account> {
103        self.with(|this| Box::new(this.get_exn(addr).clone()))
104    }
105
106    pub fn set_exn(&mut self, addr: Address, value: Box<Account>) {
107        self.with(|this| this.set_exn(addr, value))
108    }
109
110    pub fn find_index_exn(&self, key: AccountId) -> Address {
111        self.with(|this| this.find_index_exn(key))
112    }
113
114    pub fn path_exn(&mut self, addr: Address) -> Vec<MerklePath> {
115        self.with(|this| this.path_exn(addr))
116    }
117
118    pub fn merkle_root(&mut self) -> Fp {
119        self.with(|this| this.merkle_root())
120    }
121
122    pub fn get_account(&self, key: &AccountId) -> Box<Account> {
123        let account = self.with(|this| {
124            let addr = this.get_index(key)?;
125            this.get(addr)
126        });
127        account.unwrap_or_else(|| Box::new(Account::empty()))
128    }
129
130    pub fn apply_zkapp_first_pass_unchecked_with_states(
131        &mut self,
132        states: &mut Vec<(GlobalState<SparseLedger>, LocalStateEnv<SparseLedger>)>,
133        global_slot: Slot,
134        state_view: &ProtocolStateView,
135        fee_excess: Signed<Amount>,
136        supply_increase: Signed<Amount>,
137        second_pass_ledger: &Self,
138        zkapp_command: &ZkAppCommand,
139    ) -> Result<ZkappCommandPartiallyApplied<SparseLedger>, String> {
140        apply_zkapp_command_first_pass_aux(
141            constraint_constants(),
142            global_slot,
143            state_view,
144            states,
145            |acc, global_state, local_state| {
146                let GlobalState {
147                    first_pass_ledger,
148                    second_pass_ledger: _,
149                    fee_excess,
150                    supply_increase,
151                    protocol_state,
152                    block_global_slot,
153                } = global_state.clone();
154
155                let mut local_state = local_state.clone();
156                local_state.ledger = local_state.ledger.copy_content();
157
158                acc.insert(
159                    0,
160                    (
161                        GlobalState {
162                            first_pass_ledger: first_pass_ledger.copy_content(),
163                            second_pass_ledger: second_pass_ledger.copy_content(),
164                            fee_excess,
165                            supply_increase,
166                            protocol_state,
167                            block_global_slot,
168                        },
169                        local_state,
170                    ),
171                );
172            },
173            Some(fee_excess),
174            Some(supply_increase),
175            self,
176            zkapp_command,
177        )
178    }
179
180    pub fn apply_zkapp_second_pass_unchecked_with_states(
181        &mut self,
182        init: &mut Vec<(GlobalState<SparseLedger>, LocalStateEnv<SparseLedger>)>,
183        c: ZkappCommandPartiallyApplied<Self>,
184    ) -> Result<ZkappCommandApplied, String> {
185        let account_update_applied = apply_zkapp_command_second_pass_aux(
186            constraint_constants(),
187            init,
188            |acc, global_state, local_state| {
189                let GlobalState {
190                    first_pass_ledger,
191                    second_pass_ledger,
192                    fee_excess,
193                    supply_increase,
194                    protocol_state,
195                    block_global_slot,
196                } = global_state.clone();
197
198                let mut local_state = local_state.clone();
199                local_state.ledger = local_state.ledger.copy_content();
200
201                acc.insert(
202                    0,
203                    (
204                        GlobalState {
205                            first_pass_ledger: first_pass_ledger.copy_content(),
206                            second_pass_ledger: second_pass_ledger.copy_content(),
207                            fee_excess,
208                            supply_increase,
209                            protocol_state,
210                            block_global_slot,
211                        },
212                        local_state,
213                    ),
214                );
215                // acc
216            },
217            self,
218            c,
219        )?;
220
221        let rev_states = init;
222        let will_succeed = account_update_applied.command.status.is_applied();
223
224        rev_states.reverse();
225        // All but first and last
226        let nintermediate = rev_states.len().saturating_sub(2);
227
228        for (_global_state, local_state) in rev_states.iter_mut().skip(1).take(nintermediate) {
229            local_state.will_succeed = will_succeed;
230        }
231
232        // let states = rev_states;
233        Ok(account_update_applied)
234    }
235}
236
237impl LedgerIntf for SparseLedger {
238    type Location = Address;
239
240    /// <https://github.com/MinaProtocol/mina/blob/05c2f73d0f6e4f1341286843814ce02dcb3919e0/src/lib/mina_base/sparse_ledger_base.ml#L58>
241    fn get(&self, addr: &Self::Location) -> Option<Box<Account>> {
242        self.with(|this| this.get(addr))
243    }
244
245    /// <https://github.com/MinaProtocol/mina/blob/05c2f73d0f6e4f1341286843814ce02dcb3919e0/src/lib/mina_base/sparse_ledger_base.ml#L66>
246    fn location_of_account(&self, account_id: &AccountId) -> Option<Self::Location> {
247        self.with(|this| this.location_of_account(account_id))
248    }
249
250    /// <https://github.com/MinaProtocol/mina/blob/05c2f73d0f6e4f1341286843814ce02dcb3919e0/src/lib/mina_base/sparse_ledger_base.ml#L75>
251    fn set(&mut self, addr: &Self::Location, account: Box<Account>) {
252        self.with(|this| this.set(addr, account))
253    }
254
255    /// <https://github.com/MinaProtocol/mina/blob/05c2f73d0f6e4f1341286843814ce02dcb3919e0/src/lib/mina_base/sparse_ledger_base.ml#L96>
256    fn get_or_create(
257        &mut self,
258        account_id: &AccountId,
259    ) -> Result<(AccountState, Box<Account>, Self::Location), String> {
260        self.with(|this| this.get_or_create(account_id))
261    }
262
263    /// <https://github.com/MinaProtocol/mina/blob/05c2f73d0f6e4f1341286843814ce02dcb3919e0/src/lib/mina_base/sparse_ledger_base.ml#L109>
264    fn create_new_account(&mut self, account_id: AccountId, to_set: Account) -> Result<(), ()> {
265        self.with(|this| this.create_new_account(account_id, to_set))
266    }
267
268    /// <https://github.com/MinaProtocol/mina/blob/05c2f73d0f6e4f1341286843814ce02dcb3919e0/src/lib/mina_base/sparse_ledger_base.ml#L112>
269    fn remove_accounts_exn(&mut self, _account_ids: &[AccountId]) {
270        unimplemented!("remove_accounts_exn: not implemented")
271    }
272
273    /// <https://github.com/MinaProtocol/mina/blob/05c2f73d0f6e4f1341286843814ce02dcb3919e0/src/lib/mina_base/sparse_ledger_base.ml#L115>
274    fn merkle_root(&mut self) -> Fp {
275        self.merkle_root()
276    }
277
278    /// <https://github.com/MinaProtocol/mina/blob/05c2f73d0f6e4f1341286843814ce02dcb3919e0/src/lib/mina_base/sparse_ledger_base.ml#L142>
279    fn empty(depth: usize) -> Self {
280        Self::create(depth, Fp::zero())
281    }
282
283    fn create_masked(&self) -> Self {
284        self.copy_content()
285    }
286
287    fn apply_mask(&mut self, mask: Self) {
288        let mask_inner = mask.with(|this| this.clone());
289        self.with(|this| *this = mask_inner);
290    }
291
292    fn account_locations(&self) -> Vec<Self::Location> {
293        self.with(|this| this.account_locations())
294    }
295}
296
297impl From<&SparseLedger> for mina_p2p_messages::v2::MinaBaseSparseLedgerBaseStableV2 {
298    fn from(value: &SparseLedger) -> Self {
299        use mina_p2p_messages::v2::{
300            MinaBaseAccountBinableArgStableV2, MinaBaseAccountIdStableV2,
301            MinaBaseSparseLedgerBaseStableV2Tree,
302        };
303
304        let value = value.inner.try_lock().unwrap();
305
306        assert!(value.hashes_matrix.get(&Address::root()).is_some());
307
308        let indexes: Vec<_> = value
309            .indexes_list
310            .iter()
311            .map(|id| {
312                let addr = value.indexes.get(id).unwrap();
313
314                let index = addr.to_index();
315                let index: mina_p2p_messages::number::UInt64 = index.as_u64().into();
316
317                let id: MinaBaseAccountIdStableV2 = id.clone().into();
318
319                (id, index)
320            })
321            .collect();
322
323        fn build_tree(
324            addr: Address,
325            matrix: &HashesMatrix,
326            ledger_depth: usize,
327            values: &BTreeMap<AccountIndex, Account>,
328        ) -> MinaBaseSparseLedgerBaseStableV2Tree {
329            if addr.length() == ledger_depth {
330                let account_index = addr.to_index();
331
332                return match values.get(&account_index).cloned() {
333                    Some(account) => {
334                        let account: MinaBaseAccountBinableArgStableV2 = (&account).into();
335                        MinaBaseSparseLedgerBaseStableV2Tree::Account(Box::new(account))
336                    }
337                    None => {
338                        let hash = matrix.get(&addr).unwrap();
339                        MinaBaseSparseLedgerBaseStableV2Tree::Hash(to_ledger_hash(hash))
340                    }
341                };
342            }
343
344            let child_left = addr.child_left();
345            let child_right = addr.child_right();
346
347            let is_level_above_accounts = addr.length() == ledger_depth - 1;
348
349            let is_left = matrix.get(&child_left).is_some()
350                || (is_level_above_accounts && values.get(&child_left.to_index()).is_some());
351            let is_right = matrix.get(&child_right).is_some()
352                || (is_level_above_accounts && values.get(&child_right.to_index()).is_some());
353
354            if is_left && is_right {
355                let hash = matrix.get(&addr).unwrap();
356                let left_node = build_tree(child_left, matrix, ledger_depth, values);
357                let right_node = build_tree(child_right, matrix, ledger_depth, values);
358
359                MinaBaseSparseLedgerBaseStableV2Tree::Node(
360                    to_ledger_hash(hash),
361                    Box::new(left_node),
362                    Box::new(right_node),
363                )
364            } else {
365                assert!(!is_left && !is_right);
366                let hash = matrix.get(&addr).unwrap();
367                MinaBaseSparseLedgerBaseStableV2Tree::Hash(to_ledger_hash(hash))
368            }
369        }
370
371        let tree = build_tree(
372            Address::root(),
373            &value.hashes_matrix,
374            value.depth,
375            &value.values,
376        );
377
378        let depth: u64 = value.depth.try_into().unwrap();
379
380        Self {
381            indexes: indexes.into_iter().collect(),
382            depth: depth.into(),
383            tree,
384        }
385    }
386}
387
388impl TryFrom<&mina_p2p_messages::v2::MinaBaseSparseLedgerBaseStableV2> for SparseLedger {
389    type Error = InvalidBigInt;
390
391    fn try_from(
392        value: &mina_p2p_messages::v2::MinaBaseSparseLedgerBaseStableV2,
393    ) -> Result<Self, Self::Error> {
394        use mina_p2p_messages::v2::{
395            MinaBaseSparseLedgerBaseStableV2Tree,
396            MinaBaseSparseLedgerBaseStableV2Tree::{Account, Hash, Node},
397        };
398
399        fn build_matrix(
400            matrix: &mut HashesMatrix,
401            addr: Address,
402            node: &MinaBaseSparseLedgerBaseStableV2Tree,
403            values: &mut BTreeMap<AccountIndex, crate::Account>,
404        ) -> Result<(), InvalidBigInt> {
405            match node {
406                Account(account) => {
407                    let account: crate::Account = (&**account).try_into()?;
408                    // matrix.set(&addr, account.hash()); Do not hash here, it's slow
409                    values.insert(addr.to_index(), account);
410                }
411                Hash(hash) => {
412                    matrix.set(&addr, hash.to_field()?);
413                }
414                Node(hash, left, right) => {
415                    matrix.set(&addr, hash.to_field()?);
416                    build_matrix(matrix, addr.child_left(), left, values)?;
417                    build_matrix(matrix, addr.child_right(), right, values)?;
418                }
419            }
420            Ok(())
421        }
422
423        let depth = value.depth.as_u64() as usize;
424        let mut indexes = HashMap::with_capacity(value.indexes.len());
425        let mut indexes_list = VecDeque::with_capacity(value.indexes.len());
426        let mut hashes_matrix = HashesMatrix::new(depth);
427        let mut values = BTreeMap::new();
428
429        for (account_id, account_index) in value.indexes.iter() {
430            let account_id: AccountId = account_id.try_into()?;
431            let account_index = AccountIndex::from(account_index.as_u64() as usize);
432
433            let addr = Address::from_index(account_index, depth);
434
435            indexes.insert(account_id.clone(), addr);
436            indexes_list.push_back(account_id);
437        }
438
439        build_matrix(
440            &mut hashes_matrix,
441            Address::root(),
442            &value.tree,
443            &mut values,
444        )?;
445
446        Ok(Self {
447            inner: Arc::new(Mutex::new(SparseLedgerImpl {
448                values,
449                indexes,
450                hashes_matrix,
451                depth,
452                indexes_list,
453            })),
454        })
455    }
456}
mina_tree/sparse_ledger/sparse_ledger.rs

mina_tree/sparse_ledger/
sparse_ledger.rs
