秒懂Merkle-Tree-与SPV

  • 2017-09-04
  • 174
  • 0
  • 0

本文作者:苏江,微信公众号:苏江。

首发于“申龙斌的程序人生”公众号。

这篇文章对于刚刚接触区块链的读者有点难,适合有一定程序背景知识的朋友阅读,普通用户需要了解SPV(简易支付验证)的概念,知道默克尔树的基本原理也有助于理解轻钱包的概念。

Merkle tree(默克尔树)是一种数据结构,通常是一个二叉树(也有可能是多叉树),它以特定的方式逐层向上计算,直到顶部。Merkle tree最为常见和最简单的形成是二叉默克尔树。

在比特币的设计里,也使用了Merkle tree的数据结构,只不过里面存放的数据内容都是哈希值(HASH)。

哈希算法是一种摘要算法,你给它输入一个任意长的数据A,经过HASH运算后,它返回给你固定长度的数据B,也称B为“数据指纹”。这种哈希算法理论上是不可逆的,所以构成了加密数字货币设计的基础。

比特币的每一笔交易,都有一个交易ID,是一串很长的数字,如T1、T2、T3…..。

每个transaction ID进行哈希运算,生成一个哈希值H1, H2, H3等。然后相邻的两个哈希值相加之后,再进行哈希计算,形成它的父节点,以次类推,一直到根节点,形成默克尔树。

根节点的哈希值就是比特币单独一个区块的哈希值。比特币的每一个区块都可以通过其区块头的“前一个区块的哈希值”字段引用前一区块,形成一个区块链条。Merkle tree的根哈希值则可以确保区块中所有交易的真实性。

如果恰巧交易ID的总共数量为奇数个呢?那么排在最后的这个交易ID就copy自己一份,凑成偶数。

在比特币的设计里,有一点非常重要,一定要把所有的交易(transaction)按顺序排列下来,通过时间戳的功能就可以做到,如果顺序有误,那根哈希的结果就会大相径庭。

比特币的Merkle tree只存哈希值,没有任何实质的内容,实质的内容存在尾部的每笔交易里。

比特币为什么要用Merkle tree呢?

因为比特币有一个SPV功能,即:Simple Payment Verification(简单支付验证)。比特币的Merkle tree就是用来支持SPV功能。

SPV client 是个轻量级的客户端,SPV Client 只会下载所有的区块的头部信息,而不会下载交易部分,所以整个client下载比较快。

这里的头部信息仅包含5项内容,数据块大小为80字节:

  • 上一区块头的哈希值

  • 时间戳

  • 挖矿难度值

  • 工作量证明随机数(nonce)

  • 包含该区块交易的梅克尔树的根哈希

SPV的目标是为了验证某个支付是否真实存在,并得到多少个确认。比如我向你转了一笔比特币,我告诉你我已经转了,那你如何验证这笔支付的真实性呢?

支付验证的过程很简单,只是判断这笔支付交易是否得到了区块链节点共识验证,并得到了多少的确认数即可。

1)首先计算待验证支付的交易哈希值。

2)节点从区块链网络上获取并存储最长链的所有区块头到本地。

3)节点从区块链获取待验证支付对应的Merkle tree 哈希认证路径。

4)根据认证路径,计算Merkle tree的根哈希值,将计算结果与本地区块头中的Merkle tree的根哈希值相比较。

5)如果一致则说明支付真实有效。

6)根据区块头所处的位置,确定该支付已经得到的确认数量。

第3步中,假设你的交易是HK, 则计算根哈希值的办法是找到HL、HIJ、HMNOP 和 HABCDEFGH,这里有一种专门的遍历算法可以得到。

总的来说,Merkle tree 在区块链的应用实现了简单快速验证的功能。

我是苏江,长期分享区块链思考,欢迎加我微信与我交流:su466120534

评论

还没有任何评论,你来说两句吧

发表评论