multiproof.rs

是 Alexey Akhunov 的 multiproof 算法 的 Rust 实现。

在创建时，multiproof 仍处于开发中，此代码做出了一系列假设，这些假设需要讨论和更新以实现完全兼容。以下是非详尽的假设列表

• 初始的 LEAF、BRANCH、ADD、HASHER 和 EXTENSION 模型仍在使用中，
• HASHER 总是有一个参数为 0。这显然是此代码的一个问题，因为几个不同的树最终会有相同的哈希值。

安装

此代码使用 Rust nightly 的功能。 安装它，请输入

rustup install nightly

然后您可以使用以下命令运行测试

cargo +nightly test

用法

创建树

从一个空树开始

let mut tree_root = Node::default();

这创建了一个可变树根，它是一个具有 16 个（目前为空）子节点的节点。

您可以使用 insert_leaf 将一个 (key,value) 对添加到该树中。此示例将 (0x11111..111, 0x22222..222) 添加到上面创建的树中

new_root.insert(&NibbleKey::from(vec![1u8; 32]), vec![2u8; 32]).unwrap();

注意键格式为 &NibbleKey，而不是 Vec<u8>。

计算哈希值

hash 函数将遍历树并计算哈希表示。

let hash = new_root.hash();

创建证明

调用 make_multiproof 函数，传入树的根和需要更改的键列表。它返回一个 Multiproof 对象，该对象可以通过网络发送给验证者；以下示例将为叶节点 0x11...11 创建证明。

let proof = make_multiproof(&new_root, vec![NibbleKey::from(vec![1u8; 32])]).unwrap();

验证证明

在 make_multiproof 的输出上调用 rebuild 函数。

let root = proof.rebuild().unwrap();

示例

参见单元测试。

更新日志

0.1.9

• 添加了 Hashable 特性和使用方法 M2 和 M3（见https://ethresear.ch/t/binary-trie-format/7621/6）
• 实现了 From<Vec<bool>> 和 Into<Vec<bool>>
• 二进制键使用 bool 作为键类型
• 使用二叉搜索树扩展
• 修复：在插入时检查键的长度是否相同。
• 模糊测试：引入 nibblekey 和 Node::inset 的测试。

0.1.8

• 在 Node 上使用 keys 方法以获取树中存在的键列表。
• 修复 #61 - 如果多个键有相同的前缀指向 Leaf 对象，不要返回错误；相反，将此键添加到证明中，作为所有额外键缺失的证明。

0.1.7

• 接受空键的插入

0.1.6

• 修复偶长度十六进制前缀计算的错误

0.1.5

• 导出 ByteKey 到 Vec
• 为 NibbleKey 实现 fmt::Display

0.1.4

• 支持二叉树
• 证明的 CBOR 编码

0.1.3

• 允许 insert 覆盖现有叶子节点
• 使 has_key 成为树特质的组成部分
• 修复 NibbleKey 索引计算中的错误
• README 更新

0.1.2

• 导出所有子模块

0.1.1

• 从 crate 中导出 node::*