mina_tree/sparse_ledger/
sparse_ledger.rs

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

mina_tree/sparse_ledger/
sparse_ledger.rs
