[朱丽叶]比特币的默克尔树是二叉搜索树吗？

欧易(OKX)

用戶喜愛的交易所

立即注冊立即下载

币安(Binance)

已有账号登陆后会弹出下载

立即注冊立即下载

本文最初发表于高泽明网站，经作者许可转载。

在这里阅读全文。比特币的 Merkle 树是二叉搜索树吗？

Craig Wright 表示，比特币的 Merkle 树是一棵二叉搜索树。

BTC 开发人员不同意并质疑他的资格。

BTC 的提问和 Wright 博士的回答是 Wright 博士谈论它的典型例子，其谈论的水平和深度是其他人没有想到的。讽刺的是，有些人甚至质疑 Wright 博士在本科阶段对技术的理解，而不是尽管如此，但正因为如此。（正是这种在过去八年中持续不断的质疑主导了赖特中本聪的主题。坦率地说，这是可耻和不公正的。这也是经常迫使我向其他人解释的原因.）任何可能有赖特博士甚至不知道基本知识的印象的人都应该重新审视自己的基本心态。没有人应该盲目相信别人所说的话，但人们对赖特博士犯的一个更常见的错误是推定地拒绝他。

是时候从一次又一次发生的事情中吸取教训了。

从过去的重复经验来看，基本的谨慎意识需要更仔细、更深入地思考赖特博士所说的话，以免尴尬。如果你真的想探究比特币的真相，请抵制住关注孤立的技术细节的诱惑。太多了。

它是一个系统。

更具体地说，是一个存在于计算、经济和法律环境中的系统。您对这些问题的理解很大程度上取决于您是否想要一个主要用于抵制审查的技术政治系统，或者一个主要用于生产力的经济系统。

每种观点都有其值得尊重的理由，但在得出别人一无所知的结论之前，必须先了解其中的差异。我非常理解这两种观点。

我只是碰巧更喜欢可扩展且富有成效的经济体系，而不是技术政治的法律抵抗体系。

现实世界可能有空间允许这两个系统同时存在。

我的偏好与我所信仰的价值观有关，并且我理解其他人也有自己的价值观和信仰。因此，请听我讲述比特币二叉搜索树的这个特定问题。

我讨论它不仅因为它具有独特的技术意义，还因为它是一个很好的例子，说明为什么人们应该关注 Wright 博士的言论。 Merkle 树和二叉树

赖特表示，默克尔树结构最初是由中本聪设计的，现在已经在 BSV 中与二叉搜索树 SPV（简化支付验证）一起实现。他的反对者认为这是荒谬的错误，因为每个对默克尔树有基本了解的人都可以理解。计算机科学知道 Merkle 树不是二叉搜索树。他的对手是对的，因为 Merkle 树在学校教授的基本应用中不是二叉搜索树。

但他们不知道的是，中本聪对比特币默克尔树的设计是这样的，虽然它是默克尔树，但它也是一棵搜索树，甚至是一棵二叉搜索树。

赖特再次说得令人难以置信。让我解释一下下面的技术细节。首先，“二叉树”的关键概念是指将树（数据语料库）切成两半的功能（因此'二进制'）在每一步中。

它根据匹配或不匹配确定下一步的方向，并丢弃另一个方向的一半。

重复此操作，直到找到目标项目。

这种二进制方式使得该过程非常快速且可扩展。

因为每一步都是二进制的，所以它呈指数级增长，从而产生对数可扩展性。事实是，一半的数据可以立即被忽略，而不会有丢失目标的风险，这就是创造这种显着效果的原因。

但这必然要求树中的节点和叶子以特定方式排序和平衡。因此，将树称为“二元”意味着树以可以执行操作（例如搜索）的方式构建以二进制方式。

如果该结构不具有这种二进制特征，那么称其为二进制是不正确的。

但是，如果该结构确实具有这种二叉特征，但没有人知道这种结构并且从未将其称为二叉，那么第一个调用它的人不仅是正确的，而且是创新的。二叉树可以被结构化以执行各种功能并实现各种目标。

当树被构造为执行二分搜索时，它就是二分搜索树。

但二叉树还可以用于其他目的，比如用于确保数据完整性。那么问题是，为什么 Wright 博士将比特币的 Merkle 树称为二叉搜索树？首先，如果比特币的 Merkle 树的结构是为了查找确定某条数据的位置并确认其存在，它就是一棵搜索树。

这很简单，不管别人怎么说。但是它是“二叉”的，因此是二叉搜索树吗？

这是一个更详细的考虑。答案是肯定的。

比特币的 Merkle 树是二叉搜索树，因为比特币数据被特意构建为键值数据库，这意味着每个项目（一笔交易或哈希）都与一个键相关联（由其标记）。

键是连续的。

有多种不同的方式来构建密钥。

这取决于树结构和算法的设计（参见下面的示例）。

注意，这里的“密钥”这个词是一种标准的数据库技术，就像一个物品的标签，与加密密钥无关。因为比特币交易是根据每笔交易收到的时间顺序加上时间戳的，这种顺序是自然的。

现在，通过内置的顺序键（每个键对应一个带时间戳的顺序事务），您就拥有了一个有序且平衡的叶子哈希树。图 1。

基于 Merkle 树的二叉搜索树 图 1 显示了这种 Merkle 树的示例，它也是二叉搜索树。交易用 Di 表示。

交易Di对应hash(i, i)，它是key(i, j)的特例，其中i=j。每个节点用一个由一对数字(i, j)组成的key来表示，如( 1、4）。

数字的含义很简单：一个具有键（i，j）的节点意味着该节点及其下的子节点的数据涵盖了i到j范围内的交易。

例如，(1, 4) 表示该节点及其下的子节点涵盖了事务 1、2、3、4。隐含地，这也意味着它们与事务 5、6、7、8 无关，即被(5,8)下的另一个分支覆盖。根据这个顺序编号，(i,k)和(k+1,j)是两个相邻节点，如k和k+1所示。

当两个相邻的哈希值 H(i, k) 和 H(k+1, j) 连接并进行哈希处理时，会生成一个新的哈希值 H(i, j)。

生成的键 (i, j) 是逻辑的，因为连接两个邻居哈希会连接两个范围，即 i 到 k 和 k+1 到 j，以创建一个新范围 i 到 j，因此其生成的哈希表示为 H (i ，j）。

请注意，中间的数字 k 和 k+1 不会出现在新密钥 (i, j) 中。

这是因为范围 i 到 j 表示扩展范围，必须覆盖中间的数字 k 和 k+1。图 1 说明了一个简单的情况，其中 i=1, 2,…8。

实际上，i=1, 2,…n，其中n是区块中交易的总数，可以是一个很大的数字。Merkle树的形成如下：对每个交易Di进行哈希得到H(i, i)。

这是默克尔树的第一层，其中交易数据项与其哈希值具有一一对应关系。哈希每对相邻的 H(i, i) 和 H(i+1, i+) 的串联1) 得到H(i, i+1)。

这就达到了第二个层次。

第二层将有 n/2 个节点。重复上面步骤 2 中的相同过程，直到到达最后一层，只剩下一个节点。

这就是 Merkle 根。因为每下一层的节点数减半，所以这个过程很快到达根（顶部）。

总级别数m=log2(n)。

区块的交易越多，其优势就越大。例如，当n=8时，m=3。

当n=100万时，m=20；

当n=10亿时，m=30；

当n=1万亿时，m=40，依此类推。

可以看到，从n=8到n=10亿，一个区块的总交易数增加了1亿多倍，而树的总层数只增加了10倍。以上是基本的Merkle 树的特征。

但很明显，使用顺序键标记节点会将 Merkle 树转换为二叉搜索树。 在图 1 所示的示例中，假设我们需要搜索交易 D5。

对应于键 (5, 5)。

我们从顶部（根）H(1, 8)开始，这表明该块从1到8总共有8笔交易。首先，我们比较我们的目标（5,

5) 与当前节点(1,8)。

因为 5 > 8/2，我们知道我们的目标在右侧。

我们走到右侧到达节点 H(5, 8) 并忽略整个左分支，即树的一半。

如果这在这个小例子中并不明显，想象一下，如果该块有 10 亿笔交易，这一步骤会跳过 5 亿笔交易。接下来，我们将目标 (5, 5) 与当前节点 (5, 8) 进行比较。

因为5=5，我们知道我们已经正确地得到了这部分密钥，这是交易范围的下边界。

但因为 5<8，我们向左走，到达 H(5,5)，它对应的是交易 D5，也就是我们要找的交易。因此，上面构造的 Merkle 树可以实现二分搜索，因此是二分搜索树。

这是毫无争议的，因为二叉搜索树正是这样定义的。这样的二叉搜索树与 SPV 的精心设计相结合，使得在 BSV 中实现的比特币极其强大。二叉搜索树和 SPVSPV 本身是另一个例子主题。

虽然在比特币白皮书中有所披露，但SPV只是在比特币SV（BSV）上才被正确理解和进一步发展。

我将跳过对 SPV 本身的解释，但想强调它与比特币的二叉搜索树相关。SPV 是关于可扩展性的。

如果你只看 SPV 如何与用户提交其交易的 Merkle 路径一起工作的个别事件，那么它似乎与搜索无关，因为用户很容易生成 Merkle 路径，该路径不仅专门定位了交易 ID 及其位置，无需在区块链上搜索任何其他内容。

唯一剩下的就是接收者需要计算 Merkle 证明，以使用 Merkle 路径验证交易的存在。但请记住，SPV 涉及可扩展性。

这意味着它将在单个区块中包含数十亿甚至数万亿交易的区块链上运行。

在如此大规模的区块链上，可扩展且高效的搜索变得绝对必要，否则，包括发送者、接收者和服务提供者在内的所有人都将不知所措。因此，我们需要可扩展的搜索和 SPV。

但是还有什么比二叉搜索树能更好地做到这一点呢？二叉搜索树和 SPV 就这样紧密地配合在一起。

这就是 BSV 所做的。

即将测试的 Teranode 将展示这些功能。

如果您不关心可扩展的系统，您可能不会对此感到兴奋。

但这并不意味着你应该趾高气扬地声称赖特博士无知，因为他声称比特币默克尔树是一棵二叉搜索树。

相反，你应该发现自己的无知，无法理解他所说的内容。观看：

比特币——电子现金系统 width="562" height="315" frameborder="0" allowedfullscreen="allowfullscreen">区块链新手？

查看 CoinGeek 的区块链初学者部分，这是了解更多有关区块链技术的终极资源指南。

热点：比特币 比特币的 特币 朱丽叶