比特币如何交易 大部分中merkletree的验证路径在讲述轻钱包验证过程

资讯 8个月前 manoon
0

大多数材料都会提到默克尔根存储在区块中,并用它来验证交易的真实性。但是,一般没有关于如何进行真实性验证的文章。本文假设您已经了解了区块链中默克尔树的原理比特币如何交易,现在想弄清楚如何实现交易真实性验证。

默克尔树

这部分简单介绍了merkle的原理,我会写一篇文章详细解释。你可以关注我的文章。简单的说,merkle树就是hash二叉树,父节点是两个子节点的双sha256结果,叶子节点是交易内容的双sha256结果。

区块链默克尔树

上图中最底层是交易数据。对于每一笔交易,都可以计算一个hash,从而可以逐层获取merkle root。但是,由于区块链中的merkle操作要求叶子节点为偶数,当一个区块包含奇数个交易时,会复制最后一个交易为偶数。

最后将merkle root保存在块头中,交易数据保存在块体中。实际上,中间没有保存hash时,它们只是操作过程的数据。

SPV

比特币如何交易 大部分中merkletree的验证路径在讲述轻钱包验证过程

为什么这么复杂?现在所有的交易数据都是直接保存的,是不是很容易验证交易的存在?之所以会这样,是因为在比特币被发明的时候,中本聪想到了一个轻钱包的设计,就是SPV(Simplified Payment Verification)。

轻钱包不存储完整的区块链,而只存储每个区块的区块头。区块体保存了完整的交易信息,交易信息所需的存储量大部分是交易头的千倍以上。因此,如果只保存交易头,可以大大减少本地客户端存储的区块链信息。

然而,区块链因此无法工作。如果此时轻钱包需要验证某笔交易,而本地没有该交易的信息,如何验证?这时候区块头中的merkle root就会生效。

验证路径

在讲述轻钱包的验证过程之前,我们需要知道如何在merkle树中进行验证。我们知道默克尔树中父节点和子节点的操作关系。因此,当我们要证明这棵树中存在叶节点时,只需要得到从叶节点到根节点计算过程中需要的hash即可。不需要所有叶子节点都参与计算。

比特币如何交易 大部分中merkletree的验证路径在讲述轻钱包验证过程

默克尔验证路径

你可能会觉得有点奇怪,为什么不直接告诉它所有的叶子节点,你可以用所有的叶子节点来计算根hash,验证通过。但这是事实,因为每一个父节点的hash都必须通过两个子节点的hash运算得到,所以我们只需要选择所有参与运算的节点就可以证明叶子节点存在于树中。这可以减少散列操作的次数。这些被选中的节点以及它们之间的层次关系就是验证路径,即上图中merkle根框下的所有框。

如何证明交易的真实性?

只有在比特币网络中已经记录在区块链上并收到 6 个确认的交易才被认为是真实的,并且只有基于这些真实交易(输入输出的概念)发起的新交易才是合法的。

我们询问交易是否真实,通常基于以下前提:

那么对于 SPV 轻钱包,如何知道一笔交易是否真实呢? SPV 获得交易信息后(如收到一笔款项),无法确认交易是否合法,因此必须对这笔交易的输入进行验证。但是,它只获取单笔交易的信息,并没有本地完整的区块链数据。因此,SPV 需要利用交易信息向网络发起查询请求。这个请求被称为默克尔区块消息。当其他拥有完整区块链数据的客户端收到此请求时,它们会使用传输的交易信息在自己的区块链数据库中进行查询,并将验证路径返回给请求源。 SPV得到验证路径后,再次做merkle检查比特币如何交易,确认交易可信。

比特币如何交易 大部分中merkletree的验证路径在讲述轻钱包验证过程

现在的问题是:

检查来自区块链的交易

区块链的数据结构是离散的。比特币中的一个块存储在一个文件中。要获取交易的验证路径,必须获取交易所在的区块链。这是一个复制的查询过程,您可能需要遍历所有块才能找到它。于是,一个像blockchain.info这样的网站诞生了,通过一条信息,帮你查看区块链上所有这些信息的相关记录。但对于客户来说,就没有那么容易了。它不能信任网站blockchain.info,而只能信任自己本地存储的区块链。因此,只有合理的算法才能优化交易查询。

一种设计是将每个块的数据结构修改成关系型数据库,通过它可以使用SQL语句进行快速查询。然而,遍历和查询所有区块链是一种浪费。另一种思路是利用交易的时间戳来快速定位区块位置,并在相邻的几个区块中快速找到。

如何获取merkle验证路径?

其实merkle的验证路径生成的前提是已经存在完整的merkle树。市面上的merkle树实现包很多,有的包直接给出了getProof方法来获取某个叶子节点的验证路径。

客户端收到默克尔区块消息后,必须执行以下步骤:

使用上述方法找到包含交易的区块,检查该区块是否是全网最长的链,取出所有交易生成默克尔树,使用getProof方法获取该区块的验证路径交易并将验证路径发送回请求源

SPV得到回复后,需要做如下验证:

同步区块链,确保它是全网最长的。首先获取merkle root在区块链中找到,确保merkle root hash是链上得到的验证路径,然后进行merkle校准。确保验证路径全部合法

为什么SPV需要再做一次merkle验证?主要是为了保证响应者发送的验证路径的有效性。

确保验证路径的真实性

比特币如何交易 大部分中merkletree的验证路径在讲述轻钱包验证过程

如上所述,SPV需要做merkle验证,这也是“不信任”的表现之一。我们不保证响应我们的节点不会作弊或欺骗,所以我们必须自己检查。但是,有没有可能验证过程虽然顺利,验证路径却是伪造的?

让我们做一个假设:1)merkle root 是真的; 2) 交易是假的;路径中的3) 哈希值可以为真,也可以为假。这个假设成立吗?

我们知道不同字符串碰撞同一个sha256的概率极小,那么双sha256的概率就是它的平方,逐层计算merkle根。如果一个区块只有一个(或2个)交易,那就是double^(2+1)sha256,如果有4个交易,就有double^(4 + 2 + 1)sha256,更不用说一个区块中有这么多交易需要经过,merkle操作获得相同的hash几乎是不可能的,因此在merkle验证中使用伪造的交易hash获得已知的merkle根是不可能的。

如果想进一步查看,可以在区块头中存储打包在区块中的交易数量,这样你就可以知道从交易哈希到默克尔根需要经过多少层计算。这也是一个检查站。

总结

merkle 树在区块链中被广泛使用,但不仅仅是区块链将其用于验证。比如一些p2p下载,比如迅雷,需要把文件分成小文件。每个块都有一个哈希值。每个块都是从不同的网络节点下载的。最后形成一个完整的文件,但也需要hash验证。可以使用merkle来验证。默克尔树不一定是二叉树,它可以是任何树结构。在以太坊中,merkle 验证是不够的。增加了Patricia Tree验证,统称为“Merkle Patricia Tree”。

2018-03-07 39180

暂无评论

暂无评论...