持久默克勒树
二进制墨克勒树 持续的数据结构。 。 。 .
示例
// LeafNode and BranchNode are used to build nodes in a tree
// Nodes may not be changed once initialized
import {LeafNode, BranchNode} from "@chainsafe/persistent-merkle-tree";
const leaf = LeafNode.fromRoot(Buffer.alloc(32, 0xaa));
const otherLeaf = LeafNode.fromRoot(Buffer.alloc(32, 0xbb));
const branch = new BranchNode(leaf, otherLeaf);
// The `root` property returns the merkle root of a Node
// this is equal to `hash(leaf.root, otherLeaf.root));`
const r: Uint8Array = branch.root;
// The `isLeaf` method returns true if the Node is a LeafNode
branch.isLeaf() === false;
leaf.isLeaf() === true;
// Well-known zero nodes are provided
import {zeroNode} from "@chainsafe/persistent-merkle-tree";
// 0x0
const zero0 = zeroNode(0);
// hash(0, 0)
const zero1 = zeroNode(1);
// hash(hash(0, 0), hash(0, 0))
const zero1 = zeroNode(2);
// Tree provides a mutable wrapper around a "root" Node
import {Tree} from "@chainsafe/persistent-merkle-tree";
const tree = new Tree(zeroNode(10));
// `rootNode` property returns the root Node of a Tree
const rootNode: Node = tree.rootNode;
// `root` property returns the merkle root of a Tree
const rr: Uint8Array = tree.root;
// A Tree is navigated by Gindex
const gindex = BigInt(...);
const n: Node = tree.getNode(gindex); // the Node at gindex
const rrr: Uint8Array = tree.getRoot(gindex); // the Uint8Array root at gindex
const subtree: Tree = tree.getSubtree(gindex); // the Tree wrapping the Node at gindex. Updates to `subtree` will be propagated to `tree`
// A merkle proof for a gindex can be generated
const proof: Uint8Array[] = tree.getSingleProof(gindex);
// Multiple types of proofs are supported through the `getProof` interface
// For example, a multiproof for multiple gindices can be generated like so
import {ProofType} from "@chainsafe/persistent-merkle-tree";
const gindices: BigInt[] = [...];
const proof: Proof = tree.getProof({
type: ProofType.treeOffset,
gindices,
});
// `Proof` objects can be used to recreate `Tree` objects
// These `Tree` objects can be navigated as usual for all nodes contained in the proof
// Navigating to unknown/unproven nodes results in an error
const partialTree: Tree = Tree.createFromProof(proof);
const unknownGindex: BigInt = ...;
gindices.includes(unknownGindex) // false
partialTree.getRoot(unknownGindex) // throws
动机
在处理大型数据集时,将数据集整体化是非常昂贵的. 在大数据集在更新和添加之间经常被重现的情况下,使用等离子结构来进行中间散列,导致大量重复工作,因为许多中间散列会被重编并丢弃在每次分解上. 在这些情况下,维持整个树的结构,包括中间节点,可以减轻这些问题并允许额外的用例(例如:证明生成). 这一执行还利用了已知的节点的不可变能性,在不同版本数据的共同子树之间共享数据.
特征
中间节点有缓存和懒散计算散列
该树作为连接的树被代表 Nodes,目前为 BranchNodes 或 (简体中文) LeafNode编号.
A 类 BranchNode 有一个 left 财务报告和审定财务报表 right 儿童 Node,则a root, 32 字节 Uint8Array。 。 。 .
A 类 LeafNode 有一个 root。 。 。 .
这个 root 页:1 Node 在请求之前不计算,然后缓存.
共享数据 betwen 常见子树
对一棵树的任何更新(无论是叶子还是中间节点)都是作为再绑定的,产生出一棵新的更新树,在版本之间最大限度地共享数据. 垃圾收集使得来自未使用节点的内存最终被回收.
持久性核心的可变包装器
A 类 Tree 对象包 Node ,并提供了用于树导航的API并透明地重新约束更新.
通过gindex或(深度,索引)进行导航
许多树法允许用gindex来导航. 一个gindex(或泛指指数)描述了从根起从下而上从树上取出的一个路径.
1
/ \
2 3
/ \ / \
4 5 6 7
也可以被解释为位字符串,从"1"开始,再将"0"附加到每个导航左侧,或者将"1"附加到每个导航右侧.
1
/ \
10 11
/ \ / \
100 101 110 111
或者,几种树法,名称以 AtDepth,允许通过(深度,索引)进行导航。 深度和索引导航通过首先从上方向下导航到树上,从0(深度)开始,从左侧索引出节点,从0(index)开始.
0 <- depth 0
/ \
0 1 <- depth 1
/ \ / \
0 1 2 3 <- depth 2
内存效率
作为执行细节,节点保持其价值 HashObject (javascript 对象为 h0,, , , , , , , , . h7 金特32号 number 而不是作为32字节 Uint8Array。内存基准显示,这导致内存减少~3x Uint8Array。这种优化可以使这个库在实际上扩展到有上百万个节点的树上.
导航效率
在表现关键应用程序中,许多对树进行读取和写作,聪明地使用树导航至关重要。 这个库正确提供了树导航方法,可以处理几个重要的优化案例:多节点获取和设置,以及得到-当时设置的操作.
另见:
https://github.com/protolambda/remerkleble (中文(简体) )
审计
这一回购额由最不发达国家管理局审计,作为 本次安全审计,于2020-03-23发布. 提交 8b5ad7 报告已核实.
许可证
阿帕奇 - 2.0