darkfi_sdk/wasm/
merkle.rs

1/* This file is part of DarkFi (https://dark.fi)
2 *
3 * Copyright (C) 2020-2026 Dyne.org foundation
4 *
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU Affero General Public License as
7 * published by the Free Software Foundation, either version 3 of the
8 * License, or (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13 * GNU Affero General Public License for more details.
14 *
15 * You should have received a copy of the GNU Affero General Public License
16 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
17 */
18
19use darkfi_serial::Encodable;
20
21use crate::{
22    crypto::MerkleNode,
23    error::{ContractError, GenericResult},
24    pasta::pallas,
25    wasm::db::DbHandle,
26};
27
28/// Add given elements into an on-chain Merkle tree. Used for inclusion proofs.
29///
30/// * `db_info` is a handle for a database where the Merkle tree is stored.
31/// * `db_roots` is a handle for a database where all the new Merkle roots are stored.
32/// * `root_key` is the serialized key pointing to the latest Merkle root in `db_info`
33/// * `tree_key` is the serialized key pointing to the Merkle tree in `db_info`.
34/// * `elements` are the items we want to add to the Merkle tree.
35///
36/// There are 2 databases:
37///
38/// * `db_info` stores general metadata or info.
39/// * `db_roots` stores a log of all the merkle roots.
40///
41/// Inside `db_info` we store:
42///
43/// * The \[latest root hash:32\] under `root_key`.
44/// * The incremental merkle tree under `tree_key`.
45///
46/// Inside `db_roots` we store:
47///
48/// * All \[merkle root:32\]s as keys. The value is the current \[tx_hash:32\]\[call_idx:1\].
49///   If no new values are added, then the root key is updated to the current (tx_hash, call_idx).
50pub fn merkle_add(
51    db_info: DbHandle,
52    db_roots: DbHandle,
53    root_key: &[u8],
54    tree_key: &[u8],
55    elements: &[MerkleNode],
56) -> GenericResult<()> {
57    merkle_add_internal(db_info, db_roots, root_key, tree_key, elements, false)
58}
59
60/// Add given elements into a tx-local Merkle tree. Used for inclusion proofs.
61///
62/// * `db_info` is a handle for a database where the Merkle tree is stored.
63/// * `db_roots` is a handle for a database where all the new Merkle roots are stored.
64/// * `root_key` is the serialized key pointing to the latest Merkle root in `db_info`
65/// * `tree_key` is the serialized key pointing to the Merkle tree in `db_info`.
66/// * `elements` are the items we want to add to the Merkle tree.
67///
68/// There are 2 databases:
69///
70/// * `db_info` stores general metadata or info.
71/// * `db_roots` stores a log of all the merkle roots.
72///
73/// Inside `db_info` we store:
74///
75/// * The \[latest root hash:32\] under `root_key`.
76/// * The incremental merkle tree under `tree_key`.
77///
78/// Inside `db_roots` we store:
79///
80/// * All \[merkle root:32\]s as keys. The value is the current \[tx_hash:32\]\[call_idx:1\].
81///   If no new values are added, then the root key is updated to the current (tx_hash, call_idx).
82pub fn merkle_add_local(
83    db_info: DbHandle,
84    db_roots: DbHandle,
85    root_key: &[u8],
86    tree_key: &[u8],
87    elements: &[MerkleNode],
88) -> GenericResult<()> {
89    merkle_add_internal(db_info, db_roots, root_key, tree_key, elements, true)
90}
91
92/// Internal function for `merkle_add` which branches to either on-chain or
93/// transaction-local.
94pub fn merkle_add_internal(
95    db_info: DbHandle,
96    db_roots: DbHandle,
97    root_key: &[u8],
98    tree_key: &[u8],
99    elements: &[MerkleNode],
100    local: bool,
101) -> GenericResult<()> {
102    let mut buf = vec![];
103    let mut len = 0;
104    len += db_info.encode(&mut buf)?;
105    len += db_roots.encode(&mut buf)?;
106    len += root_key.encode(&mut buf)?;
107    len += tree_key.encode(&mut buf)?;
108    len += elements.encode(&mut buf)?;
109
110    let ret = unsafe {
111        if local {
112            merkle_add_local_(buf.as_ptr(), len as u32)
113        } else {
114            merkle_add_(buf.as_ptr(), len as u32)
115        }
116    };
117
118    if ret < 0 {
119        return Err(ContractError::from(ret))
120    }
121
122    match ret {
123        0 => Ok(()),
124        _ => unreachable!(),
125    }
126}
127
128/// Add given elements into a sparse Merkle tree. Used for exclusion proofs.
129///
130/// * `db_info` is a handle for a database where the latest root is stored.
131/// * `db_smt` is a handle for a database where all the actual tree is stored.
132/// * `db_roots` is a handle for a database where all the new roots are stored.
133/// * `root_key` is the serialized key pointing to the latest Merkle root in `db_info`
134/// * `elements` are the items we want to add to the tree.
135///
136/// There are 2 databases:
137///
138/// * `db_info` stores general metadata or info.
139/// * `db_roots` stores a log of all the merkle roots.
140///
141/// Inside `db_info` we store:
142///
143/// * The \[latest root hash:32\] under `root_key`.
144///
145/// Inside `db_roots` we store:
146///
147/// * All \[merkle root:32\]s as keys. The value is the current \[tx_hash:32\]\[call_idx:1\].
148///   If no new values are added, then the root key is updated to the current (tx_hash, call_idx).
149pub fn sparse_merkle_insert_batch(
150    db_info: DbHandle,
151    db_smt: DbHandle,
152    db_roots: DbHandle,
153    root_key: &[u8],
154    elements: &[pallas::Base],
155) -> GenericResult<()> {
156    let mut buf = vec![];
157    let mut len = 0;
158    len += db_info.encode(&mut buf)?;
159    len += db_smt.encode(&mut buf)?;
160    len += db_roots.encode(&mut buf)?;
161    len += root_key.encode(&mut buf)?;
162    len += elements.encode(&mut buf)?;
163
164    match unsafe { sparse_merkle_insert_batch_(buf.as_ptr(), len as u32) } {
165        0 => Ok(()),
166        -1 => Err(ContractError::CallerAccessDenied),
167        -2 => Err(ContractError::DbSetFailed),
168        _ => unreachable!(),
169    }
170}
171
172extern "C" {
173    fn merkle_add_(ptr: *const u8, len: u32) -> i64;
174    fn merkle_add_local_(ptr: *const u8, len: u32) -> i64;
175    fn sparse_merkle_insert_batch_(ptr: *const u8, len: u32) -> i64;
176}
darkfi_sdk/wasm/merkle.rs

darkfi_sdk/wasm/
merkle.rs
