静态 Merkle 树和山脉

这个 Merkle 树实现为一个连续的内存数组，不进行动态分配。因此，它允许进行某些优化和在编译时对阶数和大小边界的约束。

特性

• 无 std 依赖（实际上没有依赖）
• 2、4、8、... 的 2 的幂次方通用分支阶数
• 任何接受 &[u8] 并返回实现 AsRef<[u8]> 的东西的哈希函数
• 99% 安全的 Rust
• 可选项增强或减少
• 可选的山脉范围 proc 宏（当编译带有功能时）

基本功能

最基本的树是 StaticTree。这种类型的树实例化为其最终大小。

基本操作

use merkle_heapless::{StaticBinaryTree};
use merkle_heapless::traits::{StaticTreeTrait, ProofValidator};
// tree height 3, 8 leaves
const MAX_HEIGHT: usize = 3;
const MAX_WORD_LEN: usize = 10;
// supposing the YourHash struct exists
let mut tree = StaticBinaryTree::<MAX_HEIGHT, YourHash, MAX_WORD_LEN>::try_from::<&[u8]>(
    &[b"apple", b"banana"]
).unwrap();

let proof = tree.generate_proof(0);
assert!(proof.validate(b"apple"));

替换和删除叶子

您可以用另一个值替换叶子

// snip
// replace
tree.replace(5, b"cherry");
let proof = tree.generate_proof(5);
assert!(proof.validate(b"cherry"));
// remove
tree.replace(1, &[]);
let proof = tree.generate_proof(1);
assert!(!proof.validate(b"banana"));
let proof = tree.generate_proof(1);
assert!(proof.validate(&[]));

除 2 以外的阶数

这是上述树的泛化形式。

use merkle_heapless::{StaticTree};

const ARITY: usize = 4;
let mut tree = StaticTree::<ARITY, MAX_HEIGHT, YourHash, MAX_WORD_LEN>::try_from::<&[u8]>(
    &[b"apple", b"banana"]
).unwrap();
// same operations can be applied

自定义哈希实现

示例：blake256 和用于 HashMap 的标准 Rust 哈希

use merkle_heapless::traits::HashT;

#[derive(Debug)]
struct Blake2_256Hash;
#[derive(Hash, Clone, Copy, Default, PartialEq, Debug)]
pub struct Wrapped32([u8; 32]);
impl From<u8> for Wrapped32 {
    fn from(n: u8) -> Self {
        let mut arr = [0u8; 32];
        arr[0] = n;
        Self(arr)
    }
}
impl HashT for Blake2_256Hash {
    type Output = Wrapped32;

    fn hash(input: &[u8]) -> Self::Output {
        Wrapped32(sp_core::blake2_256(input))
    }
}

use std::{
    collections::hash_map::DefaultHasher,
    hash::{Hash, Hasher},
};
use merkle_heapless::traits::HashT;
#[derive(Debug)]
pub struct StdHash;
#[derive(Hash, Clone, Copy, Default, PartialEq, Debug)]
pub struct Wrapped8([u8; 8]);
impl From<u8> for Wrapped8 {
    fn from(n: u8) -> Self {
        let mut arr = [0u8; 8];
        arr[0] = n;
        Self(arr)
    }
}
impl HashT for StdHash {
    type Output = Wrapped8;

    fn hash(input: &[u8]) -> Self::Output {
        let mut s = DefaultHasher::new();
        input.hash(&mut s);
        Wrapped8(s.finish().to_ne_bytes())
    }
}

增强和减少

这些扩展提供有限的动态行为，用于树大小处理。

增强

通过创建一个高度增加一级的新树来增强树，新树包含两倍于前一个树的节点。然后复制前一个树的内容并重新计算哈希。

增强

use merkle_heapless::augmentable::{DefaultAugmentable};

const ARITY: usize = 4;
const HEIGHT: usize = 3;
const MAX_WORD_LEN: usize = 10;

let mt1 = DefaultAugmentable::<ARITY, HEIGHT, StdHash, MAX_WORD_LEN>::try_from::<&[u8]>(&[
    "apple", "apricot", "banana", "cherry",
]).unwrap();

let mut mt = mt1.augment();
assert_eq!(mt.height(), HEIGHT + 1);

合并

您可以将较小的（或大小相等的）树合并到原始树中。此操作不涉及增强，如果合并不可行，则失败。

// snip
let mt2 = DefaultAugmentable::<ARITY, HEIGHT_2, StdHash, MAX_WORD_LEN>::try_from::<&[u8]>(&[
    "kiwi", "lemon",
]).unwrap();

mt1.try_merge(mt2).unwrap();

### Reduction
Similarly, if remove, compact and reduce semantics is needed it is achievable through a Compactable tree variation:
```rust
use merkle_heapless::compactable::{DefaultCompactable};

const ARITY: usize = 4;
const HEIGHT: usize = 3;
const MAX_WORD_LEN: usize = 10;

let mut cmt = DefaultCompactable::<ARITY, HEIGHT, StdHash, MAX_WORD_LEN>::try_from::<&[u8]>(&[
    "apple", "apricot", "banana", "cherry",
]).unwrap();

cmt.try_remove(0).unwrap();
cmt.compact();
// will try to create a smaller tree from the compacted tree
let mut reduced = cmt.try_reduce().unwrap();

山脉

Merkle 山脉提供只增不删的 Merkle 树语义，优化了空间使用。这种山脉实现的规则是

• 空间限制在编译时定义（无动态分配）仅通过山峰数量
• 一个元素通过向具有附加新项目能力的最右侧山峰追加来插入
• 左侧的山峰在任何时刻都是最高的山峰
• 当两个相邻的山峰具有相同的高度时，它们会递归地与左侧的兄弟合并
• 山峰的根形成“山顶默克尔树”的叶子
• 山脉证明是通过将对应山峰的证明与山顶树中相关路径生成的证明链式连接来生成的
• 对于声明为N个山峰的MMR，它将处理高度为[0..N]的山峰，从而在二进制MMR的情况下模拟一个叶子数为[0..N*2^N]的树

在Cargo.toml中的merkle-heapless依赖中包含features = ["mmr_macro"]。

// compulsory at the beginning of the .rs file in order the macro to compile
#![allow(incomplete_features)]
#![feature(generic_const_exprs)]
// snip
use merkle_heapless::{mmr_macro};
// declaration with expicit type name for your MMR
mmr_macro::mmr!(Type = FooMMR, BranchFactor = 2, Peaks = 3, Hash = StdHash, MaxInputWordLength = 10);
let mmr = FooMMR::default();
// implicitly creates MerkleMountainRange type
mmr_macro::mmr!(BranchFactor = 2, Peaks = 5, Hash = StdHash, MaxInputWordLength = 10);
// create with default current peak of height 0
let mmr = MerkleMountainRange::default();
// or create with current peak of height 2
let mut mmr = MerkleMountainRange::from_peak(MerkleMountainRangePeak::Peak3(Default::default()));
assert_eq!(mmr.peaks()[0].height(), 5 - 3);

mmr.try_append(b"apple").unwrap();
// peak leaf numbers: [1, 0, 0, 0, 0]
assert_eq!(mmr.peaks()[0].height(), 0);
assert_eq!(mmr.peaks()[0].num_of_leaves(), 1);
assert_eq!(mmr.peaks()[1].num_of_leaves(), 0);
let proof = mmr.generate_proof(0);
assert!(proof.validate(b"apple"));