论文标题
具有有效证明的动态Merkle B-Tree
Dynamic Merkle B-tree with Efficient Proofs
论文作者
论文摘要
我们提出并定义了具有Q-Mercurial承诺的递归Merkle结构，以创建简洁的B-Merkle树。这种默克尔B树建立在先前的Q-ary merkle树的工作基础上，这些树木使用简洁的，恒定的大小，Q-Mercurial承诺来证明Intranode证明。尽管这些Q-Ary树降低了分支因子和高度，但它们仍然根据关键长度具有高度，并且被迫固定高度。 B Merkle树不是基于Q-Ary前缀树的节点，而是将简洁的内模构成在自平衡树中。该树是基于元素的排序，该元素需要额外的信息来确定元素放置，但可以显着较小的证明大小。这允许较低的树高度（由元素的顺序，而不是钥匙的大小指示），因此可以创建较小，更有效的证明和操作。此外，B Merkle树是由子集查询定义的，该查询具有与非会员证明相似的通信成本。我们的方案有可能使外包数据库模型（例如区块链）受益，该模型使用经过身份验证的数据结构和数据库索引来确保数据的不可分割性和完整性。我们在钥匙值商店，关系数据库以及部分默克尔森林中提出了潜在的应用。
We propose and define a recursive Merkle structure with q-mercurial commitments, in order to create a concise B-Merkle tree. This Merkle B-Tree builds on previous work of q-ary Merkle trees which use concise, constant size, q-mercurial commitments for intranode proofs. Although these q-ary trees reduce the branching factor and height, they still have their heights based on the key length, and are forced to fixed heights. Instead of basing nodes on q-ary prefix trees, the B Merkle Tree incorporates concise intranode commitments within a self-balancing tree. The tree is based on the ordering of elements, which requires extra information to determine element placement, but it enables significantly smaller proof sizes. This allows for much lower tree heights (directed by the order of elements, not the size of the key), and therefore creates smaller and more efficient proofs and operations. Additionally, the B Merkle Tree is defined with subset queries that feature similar communication costs to non-membership proofs. Our scheme has the potential to benefit outsourced database models, like blockchain, which use authenticated data structures and database indices to ensure immutability and integrity of data. We present potential applications in key-value stores, relational databases, and, in part, Merkle forests.
