[−][src]Struct merkletree::merkle::MerkleTree
Merkle Tree.
All leafs and nodes are stored in a linear array (vec).
A merkle tree is a tree in which every non-leaf node is the hash of its children nodes. A diagram depicting how it works:
root = h1234 = h(h12 + h34)
/ \
h12 = h(h1 + h2) h34 = h(h3 + h4)
/ \ / \
h1 = h(tx1) h2 = h(tx2) h3 = h(tx3) h4 = h(tx4)
In memory layout:
[h1 h2 h3 h4 h12 h34 root]
Merkle root is always the last element in the array.
The number of inputs is not always a power of two which results in a balanced tree structure as above. In that case, parent nodes with no children are also zero and parent nodes with only a single left node are calculated by concatenating the left node with itself before hashing. Since this function uses nodes that are pointers to the hashes, empty nodes will be nil.
TODO: Ord
Methods
impl<T: Element, A: Algorithm<T>, K: Store<T>> MerkleTree<T, A, K>
[src]
pub fn new<I: IntoIterator<Item = T>>(data: I) -> MerkleTree<T, A, K>
[src]
Creates new merkle from a sequence of hashes.
pub fn new_with_config<I: IntoIterator<Item = T>>(
data: I,
config: StoreConfig
) -> MerkleTree<T, A, K>
[src]
data: I,
config: StoreConfig
) -> MerkleTree<T, A, K>
Creates new merkle from a sequence of hashes.
pub fn from_data<O: Hashable<A>, I: IntoIterator<Item = O>>(
data: I
) -> MerkleTree<T, A, K>
[src]
data: I
) -> MerkleTree<T, A, K>
Creates new merkle tree from a list of hashable objects.
pub fn from_data_with_config<O: Hashable<A>, I: IntoIterator<Item = O>>(
data: I,
config: StoreConfig
) -> MerkleTree<T, A, K>
[src]
data: I,
config: StoreConfig
) -> MerkleTree<T, A, K>
Creates new merkle tree from a list of hashable objects.
pub fn from_data_store(data: K, size: usize) -> MerkleTree<T, A, K>
[src]
Creates new merkle tree from an already allocated 'Store' (used with 'Store::new_from_disk'). The specified 'size' is the number of base data leafs in the MT.
pub fn gen_proof(&self, i: usize) -> Proof<T>
[src]
Generate merkle tree inclusion proof for leaf i
pub fn gen_proof_and_partial_tree(
&self,
i: usize,
levels: usize
) -> Result<ProofAndTree<T, A, VecStore<T>>>
[src]
&self,
i: usize,
levels: usize
) -> Result<ProofAndTree<T, A, VecStore<T>>>
Generate merkle tree inclusion proof for leaf i
by first
building a partial tree (returned) along with the proof.
pub fn gen_proof_with_partial_tree(
&self,
i: usize,
levels: usize,
partial_tree: &MerkleTree<T, A, VecStore<T>>
) -> Proof<T>
[src]
&self,
i: usize,
levels: usize,
partial_tree: &MerkleTree<T, A, VecStore<T>>
) -> Proof<T>
Generate merkle tree inclusion proof for leaf i
given a
partial tree for lookups where data is otherwise unavailable.
pub fn root(&self) -> T
[src]
Returns merkle root
pub fn len(&self) -> usize
[src]
Returns number of elements in the tree.
pub fn compact(&mut self, config: StoreConfig) -> Result<bool>
[src]
Truncates the data for later access via LevelCacheStore interface.
pub fn delete(&self, config: StoreConfig) -> Result<()>
[src]
Removes the backing store for this merkle tree.
pub fn is_empty(&self) -> bool
[src]
Returns true
if the vector contains no elements.
pub fn height(&self) -> usize
[src]
Returns height of the tree
pub fn leafs(&self) -> usize
[src]
Returns original number of elements the tree was built upon.
pub fn data(&self) -> &K
[src]
Returns data reference
pub fn read_at(&self, i: usize) -> T
[src]
Returns merkle root
pub fn read_range(&self, start: usize, end: usize) -> Vec<T>
[src]
pub fn read_range_into(&self, start: usize, end: usize, buf: &mut [u8])
[src]
pub fn read_into(&self, pos: usize, buf: &mut [u8])
[src]
Reads into a pre-allocated slice (for optimization purposes).
pub fn from_byte_slice_with_config(leafs: &[u8], config: StoreConfig) -> Self
[src]
Build the tree given a slice of all leafs, in bytes form.
pub fn from_byte_slice(leafs: &[u8]) -> Self
[src]
Build the tree given a slice of all leafs, in bytes form.
Trait Implementations
impl<T: Element, A: Algorithm<T>, K: Store<T>> FromIndexedParallelIterator<T> for MerkleTree<T, A, K>
[src]
fn from_par_iter<I>(into: I) -> Self where
I: IntoParallelIterator<Item = T>,
I::Iter: IndexedParallelIterator,
[src]
I: IntoParallelIterator<Item = T>,
I::Iter: IndexedParallelIterator,
Creates new merkle tree from an iterator over hashable objects.
fn from_par_iter_with_config<I>(into: I, config: StoreConfig) -> Self where
I: IntoParallelIterator<Item = T>,
I::Iter: IndexedParallelIterator,
[src]
I: IntoParallelIterator<Item = T>,
I::Iter: IndexedParallelIterator,
Creates new merkle tree from an iterator over hashable objects.
impl<T: Element, A: Algorithm<T>, K: Store<T>> FromIteratorWithConfig<T> for MerkleTree<T, A, K>
[src]
fn from_iter_with_config<I: IntoIterator<Item = T>>(
into: I,
config: StoreConfig
) -> Self
[src]
into: I,
config: StoreConfig
) -> Self
Creates new merkle tree from an iterator over hashable objects.
impl<T: Clone, A: Clone, K: Clone> Clone for MerkleTree<T, A, K> where
T: Element,
A: Algorithm<T>,
K: Store<T>,
[src]
T: Element,
A: Algorithm<T>,
K: Store<T>,
fn clone(&self) -> MerkleTree<T, A, K>
[src]
fn clone_from(&mut self, source: &Self)
1.0.0[src]
impl<T: Default, A: Default, K: Default> Default for MerkleTree<T, A, K> where
T: Element,
A: Algorithm<T>,
K: Store<T>,
[src]
T: Element,
A: Algorithm<T>,
K: Store<T>,
fn default() -> MerkleTree<T, A, K>
[src]
impl<T: Eq, A: Eq, K: Eq> Eq for MerkleTree<T, A, K> where
T: Element,
A: Algorithm<T>,
K: Store<T>,
[src]
T: Element,
A: Algorithm<T>,
K: Store<T>,
impl<T: PartialEq, A: PartialEq, K: PartialEq> PartialEq<MerkleTree<T, A, K>> for MerkleTree<T, A, K> where
T: Element,
A: Algorithm<T>,
K: Store<T>,
[src]
T: Element,
A: Algorithm<T>,
K: Store<T>,
fn eq(&self, other: &MerkleTree<T, A, K>) -> bool
[src]
fn ne(&self, other: &MerkleTree<T, A, K>) -> bool
[src]
impl<T: Debug, A: Debug, K: Debug> Debug for MerkleTree<T, A, K> where
T: Element,
A: Algorithm<T>,
K: Store<T>,
[src]
T: Element,
A: Algorithm<T>,
K: Store<T>,
impl<T, A, K> StructuralPartialEq for MerkleTree<T, A, K> where
T: Element,
A: Algorithm<T>,
K: Store<T>,
[src]
T: Element,
A: Algorithm<T>,
K: Store<T>,
impl<T, A, K> StructuralEq for MerkleTree<T, A, K> where
T: Element,
A: Algorithm<T>,
K: Store<T>,
[src]
T: Element,
A: Algorithm<T>,
K: Store<T>,
impl<T: Element, A: Algorithm<T>, K: Store<T>> FromIterator<T> for MerkleTree<T, A, K>
[src]
fn from_iter<I: IntoIterator<Item = T>>(into: I) -> Self
[src]
Creates new merkle tree from an iterator over hashable objects.
Auto Trait Implementations
impl<T, A, K> Send for MerkleTree<T, A, K> where
A: Send,
A: Send,
impl<T, A, K> Sync for MerkleTree<T, A, K> where
A: Sync,
A: Sync,
impl<T, A, K> Unpin for MerkleTree<T, A, K> where
A: Unpin,
K: Unpin,
T: Unpin,
A: Unpin,
K: Unpin,
T: Unpin,
impl<T, A, K> UnwindSafe for MerkleTree<T, A, K> where
A: UnwindSafe,
K: UnwindSafe,
T: UnwindSafe,
A: UnwindSafe,
K: UnwindSafe,
T: UnwindSafe,
impl<T, A, K> RefUnwindSafe for MerkleTree<T, A, K> where
A: RefUnwindSafe,
K: RefUnwindSafe,
T: RefUnwindSafe,
A: RefUnwindSafe,
K: RefUnwindSafe,
T: RefUnwindSafe,
Blanket Implementations
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T> From<T> for T
[src]
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
fn to_owned(&self) -> T
[src]
fn clone_into(&self, target: &mut T)
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,
type Error = <U as TryFrom<T>>::Error
The type returned in the event of a conversion error.
fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>
[src]
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<V, T> VZip<V> for T where
V: MultiLane<T>,
V: MultiLane<T>,