Hyperledger的Bucket Tree简介通俗介绍关键点与Ethereum的MPT进行对比

74 阅读 0 评论 49 点赞

我是靠谱客的博主活力皮皮虾，最近开发中收集的这篇文章主要介绍Hyperledger的Bucket Tree简介通俗介绍关键点与Ethereum的MPT进行对比，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

简介

Bucket Tree是worldstate的组织方式的实现。

为了下面描述的目的，worldstate的键被表示成两个组件(chaincodeID and ckey) 的通过nil字节的级联，如：key = chaincodeID+nil+cKey。

这个方法的模型是一个merkle-tree在hash table桶的顶部来计算worldstate的加密-哈希

这个方法的核心是worldstate的key-values被假定存储在由预先决定的桶的数量(numBuckets)所组成的哈希表中。一个哈希函数(hashFunction) 被用来确定包含给定键的桶数量。注意hashFunction不代表SHA3这样的加密-哈希方法，而是决定给定的键的桶的数量的正规的编程语言散列函数。

为了对 merkle-tree建模，有序桶扮演了树上的叶子节点-编号最低的桶是树中的最左边的叶子节点。为了构造树的最后第二层，叶子节点的预定义数量即一个父节点有多少个子节点 (maxGroupingAtEachLevel)，从左边开始把每个这样的分组组合在一起，一个节点被当作组中所有叶子节点的共同父节点来插入到最后第二层中。注意最后的父节点的数量可能会少maxGroupingAtEachLevel这个构造方式继续使用在更高的层级上直到树的根节点被构造。

下面这个表展示的在{numBuckets=10009 and maxGroupingAtEachLevel=10}的配置下会得到的树在不同层级上的节点数。

为了计算世界状态的加密-哈希，需要计算每个桶的加密-哈希，并假设它们是merkle-tree的叶子节点的加密-哈希。为了计算桶的加密-哈希，存储在桶中的键值对首先被序列化为字节码并在其上应用加密-哈希函数。为了序列化桶的键值对，所有具有公共chaincodeID前缀的键值对分别序列化并以chaincodeID的升序的方式追加在一起。为了序列化一个chaincodeID的键值对，会涉及到下面的信息：

chaincodeID的长度(chaincodeID的字节数)
chaincodeID的utf8字节码
chaincodeID的键值对数量
对于每个键值对(以ckey排序)
ckey的长度
ckey的字节码
值的长度
值的字节码

对于上面列表的所有数值类型项（如：chaincodeID的长度），使用protobuf的变体编码方式。上面这种编码方式的目的是为了桶中的键值对的字节表示方式不会被任意其他键值对的组合所产生，并减少了序列化字节码的总体大小。

例如：考虑具有chaincodeID1_key1:value1, chaincodeID1_key2:value2, 和 chaincodeID2_key1:value1这样名字的键值对的桶。序列化后的桶看上去会像：12 + chaincodeID1 + 2 + 4 + key1 + 6 + value1 + 4 + key2 + 6 + value2 + 12 + chaincodeID2 + 1 + 4 + key1 + 6 + value1

如果桶中没有键值对，那么加密-哈希为nil。

中间节点和根节点的加密-哈希与标准merkle-tree的计算方法一样，即：应用加密-哈希函数到所有子节点的加密-哈希从左到右级联后得到的字节码。进一步说，如果一个子节点的加密-哈希为nil，那么这个子节点的加密-哈希在级联子节点的加密-哈希是就被省略。如果它只有一个子节点，那么它的加密-哈希就是子节点的加密-哈希。最后，根节点的加密-哈希就是世界状态的加密-哈希。

上面这种方法在状态中少数键值对改变时计算加密-哈希是有性能优势的。主要的优势包括：

那些没有变化的桶的计算会被跳过
merkle-tree的宽度和深度可以通过配置numBuckets和maxGroupingAtEachLevel参数来控制。树的不同深度和宽度对性能和不同的资源都会产生不同的影响。

在一个具体的部署中，所有的 peer 都期望使用相同的numBuckets, maxGroupingAtEachLevel, 和 hashFunction的配置。进一步说，如果任何一个配置在之后的阶段被改变，那么这些改变需要应用到所有的 peer 中，来保证 peer 节点之间的加密-哈希的比较是有意义的。即使，这可能会导致基于实现的已有数据的迁移。例如：一种实现希望存储树中所有节点最后计算的加密-哈希，那么它就需要被重新计算。

通俗介绍

关键点

numBuckets = 6
利用哈希表进行底层数据的维护，使得数据项均匀分布；(哈希桶计算存在一个合并的操作，即在Pos2，需要将新插入的数据，与历史的数据进行一个合并，且按照固定的排序算法进行重排序，最终得到一个新的哈希桶，包含了所有的新旧数据，且按序排列。这个就是每个桶要均匀，元素不能过多的原因)
思考一下numBuckes以及maxGroupingAtEachLevel过大或过少会有什么问题？提示：桶大小/节点更新/树高度）