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

mina_tree/sparse_ledger/
sparse_ledger.rs
