poseidon_merkle/
lib.rs

1// This Source Code Form is subject to the terms of the Mozilla Public
2// License, v. 2.0. If a copy of the MPL was not distributed with this
3// file, You can obtain one at http://mozilla.org/MPL/2.0/.
4//
5// Copyright (c) DUSK NETWORK. All rights reserved.
6
7#![doc = include_str!("../README.md")]
8#![no_std]
9#![deny(clippy::pedantic)]
10
11#[cfg(feature = "zk")]
12pub mod zk;
13
14use dusk_bls12_381::BlsScalar;
15use dusk_bytes::Serializable;
16use dusk_merkle::Aggregate;
17use dusk_poseidon::{Domain, Hash};
18
19pub const ARITY: usize = 4;
20
21/// An alias for a tree containing `Item<T>`.
22pub type Tree<T, const H: usize> = dusk_merkle::Tree<Item<T>, H, ARITY>;
23
24/// An alias for an opening of a tree containing `Item<T>`.
25pub type Opening<T, const H: usize> = dusk_merkle::Opening<Item<T>, H, ARITY>;
26
27/// A type that wraps a piece of data `T` together with a poseidon hash - i.e. a
28/// [`BlsScalar`].
29///
30/// It implements [`Aggregate`] for any `T` that also implements the trait,
31/// allowing for the construction of a poseidon tree without the need to define
32/// where the aggregation of hashes is predefined.
33///
34/// # Example
35/// ```rust
36/// use std::cmp::{max, min};
37///
38/// use dusk_bls12_381::BlsScalar;
39/// use dusk_merkle::Aggregate;
40/// use dusk_poseidon::{Domain, Hash};
41/// use poseidon_merkle::{ARITY, Item, Tree as PoseidonTree};
42///
43/// const H: usize = 17;
44///
45/// // Leaf struct that carries some data and the current block-height.
46/// struct Leaf {
47///     leaf_data: BlsScalar,
48///     bh: usize,
49/// }
50///
51/// // A node of the merkle tree that keeps track of the min and max
52/// // block-height of all of it's children nodes.
53/// struct BHRange {
54///     min: Option<usize>,
55///     max: Option<usize>,
56/// }
57///
58/// // Implement `Aggragate` only for the `BHRange`
59/// impl Aggregate<ARITY> for BHRange {
60///     const EMPTY_SUBTREE: BHRange = BHRange {
61///         min: None,
62///         max: None,
63///     };
64///
65///     fn aggregate(items: [&Self; ARITY]) -> Self {
66///         let mut parent = Self::EMPTY_SUBTREE;
67///
68///         for child in items {
69///             parent.min = match (parent.min, child.min) {
70///                 (Some(parent_min), Some(child_min)) => {
71///                     Some(min(parent_min, child_min))
72///                 }
73///                 (Some(parent_min), None) => Some(parent_min),
74///                 (None, Some(child_min)) => Some(child_min),
75///                 (None, None) => None,
76///             };
77///             parent.max = match (parent.max, child.max) {
78///                 (Some(parent_max), Some(child_max)) => {
79///                     Some(max(parent_max, child_max))
80///                 }
81///                 (Some(parent_max), None) => Some(parent_max),
82///                 (None, Some(child_max)) => Some(child_max),
83///                 (None, None) => None,
84///             }
85///         }
86///
87///         parent
88///     }
89/// }
90///
91/// // Create a merkle tree using the poseidon-hash for each level
92/// type Tree = PoseidonTree<BHRange, H>;
93/// let mut tree = Tree::new();
94///
95/// let leaf = Leaf {
96///     leaf_data: BlsScalar::from(42),
97///     bh: 42,
98/// };
99///
100/// let item = Item {
101///     hash: Hash::digest(Domain::Other, &[leaf.leaf_data])[0],
102///     data: BHRange {
103///         min: Some(leaf.bh),
104///         max: Some(leaf.bh),
105///     },
106/// };
107/// tree.insert(42, item);
108/// ```
109#[derive(Debug, Clone, Copy, Hash, Eq, PartialEq)]
110#[cfg_attr(
111    feature = "rkyv-impl",
112    derive(rkyv::Archive, rkyv::Serialize, rkyv::Deserialize),
113    archive_attr(derive(bytecheck::CheckBytes))
114)]
115pub struct Item<T> {
116    pub hash: BlsScalar,
117    pub data: T,
118}
119
120impl<T> Item<T> {
121    /// Create a new Item for the merkle tree
122    pub fn new(hash: BlsScalar, data: T) -> Self {
123        Self { hash, data }
124    }
125}
126
127impl<T> Aggregate<ARITY> for Item<T>
128where
129    T: Aggregate<ARITY>,
130{
131    const EMPTY_SUBTREE: Self = Item {
132        hash: BlsScalar::zero(),
133        data: T::EMPTY_SUBTREE,
134    };
135
136    fn aggregate(items: [&Self; ARITY]) -> Self {
137        let empty = &T::EMPTY_SUBTREE;
138
139        let mut level_hashes = [BlsScalar::zero(); ARITY];
140        let mut level_data = [empty; ARITY];
141
142        // grab hashes and data
143        items.into_iter().enumerate().for_each(|(i, item)| {
144            level_hashes[i] = item.hash;
145            level_data[i] = &item.data;
146        });
147
148        // create new aggregated item with the hash being the poseidon hash of
149        // the previous level
150        Item {
151            hash: Hash::digest(Domain::Merkle4, &level_hashes)[0],
152            data: T::aggregate(level_data),
153        }
154    }
155}
156
157impl Serializable<32> for Item<()> {
158    type Error = <BlsScalar as Serializable<32>>::Error;
159
160    fn from_bytes(buf: &[u8; 32]) -> Result<Self, Self::Error>
161    where
162        Self: Sized,
163    {
164        Ok(Item {
165            hash: <BlsScalar as Serializable<32>>::from_bytes(buf)?,
166            data: (),
167        })
168    }
169
170    fn to_bytes(&self) -> [u8; 32] {
171        self.hash.to_bytes()
172    }
173}
poseidon_merkle/lib.rs

poseidon_merkle/
lib.rs
