什么是Merkle Tree 可信树 ?

Merkle可信树是为了解决多重一次签名中的认证问题而产生的,Merkle可信树结构具有一次签名大量认证的优点,在认证方面具有显著的优势。如今,Merkle可信树的树形结构已经被广泛应用到了信息安全的各个领域,比如证书撤销、源组播认证、群密钥协商等等。并且基于Merkle可信树的数字签名方案在安全性上仅仅依赖于哈希函数的安全性,且不需要太多的理论假设,这使得基于Merkle可信树的数字签名更加安全、实用。


随着越来越多的人使用比特币,这条规则变得越来越难以遵守:因为不太可能每个人都去运行一个全节点。并且,由于节点是网络中的完全参与者,它们负有相关责任:节点必须验证交易和区块。


另外,要想与其他节点交互和下载新块,也有一定的网络流量需求。在中本聪的比特币原始论文 中,对这个问题也有一个解决方案:简易支付验证(Simplified Payment Verification,SPV)。SPV是一个比特币轻节点,它不需要下载整个区块链,也不需要验证区块和交易。相反,它会在区块链查找交易(为了验证支付),并且需要连接到一个全节点来检索必要的数据。这个机制允许在仅运行一个全节点的情况下有多个轻钱包。


为了实现SPV,需要有一个方式来检查是否一个区块包含了某笔交易,而无须下载整个区块。


这就是Merkle树所要完成的事情。比特币用Merkle树来获取交易哈希,哈希被保存在区块头中,并会用于工作量证明系统。到目前为止,我们只是将一个块里面的每笔交易哈希连接了起来,将在上面应用了SHA-256算法。虽然这是一个用于获取区块交易唯一表示的一个不错的途径,但是它没有利用到Merkle树。




每个块都会有一个Merkle树,它从叶子节点(树的底部)开始,一个叶子节点就是一个交易哈希(比特币使用双SHA256哈希)。叶子节点的数量必须是双数,但是并非每个块都包含了双数的交易。因为,如果一个块里面的交易数为单数,那么就将最后一个叶子节点(也就是Merkle树的最后一个交易,不是区块的最后一笔交易)复制一份凑成双数。


从下往上,两两成对,连接两个节点哈希,将组合哈希作为新的哈希。新的哈希就成为新的树节点。重复该过程,直到仅有一个节点,也就是树根。根哈希然后就会当做是整个块交易的唯一标示,将它保存到区块头,然后用于工作量证明。


Merkle树的好处就是一个节点可以在不下载整个块的情况下,验证是否包含某笔交易。并且这些只需要一个交易哈希,一个Merkle树根哈希和一个Merkle路径。