merkle_heapless/
traits.rs

1use crate::prefixed::Prefixed;
2use crate::Error;
3use core::fmt::Debug;
4use core::hash::Hash;
5
6impl<const ARITY: usize, H: HashT> PartialEq for Prefixed<ARITY, H> {
7    fn eq(&self, other: &Self) -> bool {
8        self.hashes == other.hashes
9    }
10}
11
12/// trait for a hash pluggable to Merkle tree at compile time
13pub trait HashT {
14    /// output returned by hash implementor
15    type Output: Hash + Default + Copy + PartialEq + Debug  + From<u8>;
16    /// hash implementation
17    fn hash(input: &[u8]) -> Self::Output;
18    /// default implementation for concatenating and hashing hash values contained in the nodes
19    /// used by proof items for hashing with prefix
20    fn concat_then_hash(hashes: &[Self::Output]) -> Self::Output {
21        unsafe {
22            Self::hash(core::slice::from_raw_parts(
23                hashes.as_ref().as_ptr() as *const u8,
24                core::mem::size_of_val(hashes),
25            ))
26        }
27    }
28}
29/// trait that an item contained in a proof implements.
30/// [ProofBuilder] implementor relies on it
31pub trait ProofItemT<const ARITY: usize, H: HashT>: Clone + Default + Debug {
32    /// consructor
33    fn create(offset: usize, prefixed: Prefixed<ARITY, H>) -> Self;
34    /// hash the hashed input with its siblings
35    fn hash_with_siblings(self, word_hash: H::Output) -> Option<H::Output>;
36}
37/// trait for building a proof
38/// a proof is normally supposed to implement both [ProofBuilder] and [ProofValidator]
39/// [StaticTreeTrait.generate_proof]
40pub trait ProofBuilder<const ARITY: usize, H: HashT>: Default {
41    /// type of the item this proof contains
42    type Item: ProofItemT<ARITY, H>;
43    /// create a proof instance and assign its root
44    fn from_root(root: H::Output) -> Self;
45    /// add a new item to proof
46    fn push(&mut self, offset: usize, prefixed: Prefixed<ARITY, H>);
47}
48
49/// trait for verifying a proof generated by a [ProofBuilder] implementor
50pub trait ProofValidator {
51    /// verify the proof at given index
52    fn validate(self, input: &[u8]) -> bool;
53}
54/// trait for a basic Merkle Tree functionality
55pub trait StaticTreeTrait<const ARITY: usize, H: HashT, PB: ProofBuilder<ARITY, H>> {
56    /// generate a proof for a leaf at index
57    fn generate_proof(&self, index: usize) -> PB;
58    /// replace a leaf at index with a new value
59    fn replace(&mut self, index: usize, input: &[u8]);
60    /// replace a hashed leaf at index with a new hashed value
61    fn replace_leaf(&mut self, index: usize, leaf: H::Output);
62    /// return a root
63    fn root(&self) -> H::Output;
64    /// return a slice of leaves
65    fn leaves(&self) -> &[Prefixed<ARITY, H>];
66    /// a size (not necessarily a number of currently present leaves) of the leaf layer
67    fn base_layer_size(&self) -> usize;
68    /// returns tree's arity (determined at compile time)
69    fn arity(&self) -> usize {
70        ARITY
71    }
72    /// returns tree's height (determined at compile time)
73    fn height(&self) -> usize;
74}
75/// trait for append-only Merkle tree semantics
76pub trait AppendOnly {
77    /// appends a new leaf into the tree unless it's full
78    fn try_append(&mut self, input: &[u8]) -> Result<(), Error>;
79    /// number of leaves currently stored in the tree
80    fn num_of_leaves(&self) -> usize;
81}
82
83/// trait for Merkle tree supporting leaf removal
84pub trait CanRemove {
85    /// removes a leaf at index
86    fn remove(&mut self, index: usize);
87    /// number of leaves currently stored in the trsee
88    fn num_of_leaves(&self) -> usize;
89}
merkle_heapless/traits.rs

merkle_heapless/
traits.rs
