Struct MerkleTree

pub struct MerkleTree<F, W, M, const DIGEST_ELEMS: usize> { /* private fields */ }

A binary Merkle tree whose leaves are vectors of matrix rows.

• F – scalar element type inside each matrix row.
• W – scalar element type of every digest word.
• M – matrix type. Must implement Matrix<F>.
• DIGEST_ELEMS – number of W words in one digest.

The tree is balanced only at the digest layer. Leaf matrices may have arbitrary heights as long as any two heights that round up to the same power-of-two are equal.

Use [root] to fetch the final digest once the tree is built.

This generally shouldn’t be used directly. If you’re using a Merkle tree as an MMCS, see MerkleTreeMmcs.

Implementations

impl<F: Clone + Send + Sync, W: Clone, M: Matrix<F>, const DIGEST_ELEMS: usize> MerkleTree<F, W, M, DIGEST_ELEMS>

pub fn new<P, PW, H, C>(h: &H, c: &C, leaves: Vec<M>) -> Self

where P: PackedValue<Value = F>, PW: PackedValue<Value = W>, H: CryptographicHasher<F, [W; DIGEST_ELEMS]> + CryptographicHasher<P, [PW; DIGEST_ELEMS]> + Sync, C: PseudoCompressionFunction<[W; DIGEST_ELEMS], 2> + PseudoCompressionFunction<[PW; DIGEST_ELEMS], 2> + Sync,

Build a tree from one or more matrices.

• h – hashing function used on raw rows.
• c – 2-to-1 compression function used on digests.
• leaves – matrices to commit to. Must be non-empty.

Matrices do not need to have power-of-two heights. However, any two matrices whose heights round up to the same power-of-two must have equal actual height. This ensures proper balancing when folding digests layer-by-layer.

All matrices are hashed row-by-row with h. The resulting digests are then folded upwards with c until a single root remains.

Panics

• If leaves is empty.
• If the packing widths of P and PW differ.
• If two leaf heights round up to the same power-of-two but are not equal (violates balancing rule).

pub fn root(&self) -> Hash<F, W, DIGEST_ELEMS>

where W: Copy,

Return the root digest of the tree.

Trait Implementations

impl<F: Debug, W: Debug, M: Debug, const DIGEST_ELEMS: usize> Debug for MerkleTree<F, W, M, DIGEST_ELEMS>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'de, F, W, M, const DIGEST_ELEMS: usize> Deserialize<'de> for MerkleTree<F, W, M, DIGEST_ELEMS>

where [W; DIGEST_ELEMS]: Deserialize<'de>, M: Deserialize<'de>,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<F, W, M, const DIGEST_ELEMS: usize> Serialize for MerkleTree<F, W, M, DIGEST_ELEMS>

where [W; DIGEST_ELEMS]: Serialize, M: Serialize,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.