秒懂Merkle Tree 与SPV

这篇文章对于刚刚接触区块链的读者有点难,适合有一定程序背景知识的朋友阅读,普通用户需要了解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 在区块链的应用实现了简单快速验证的功能。

--- END ---

原文发布于微信公众号 - 申龙斌的程序人生(slbGTD)

原文发表时间:2017-09-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏乐享123

比特币总量为什么是2100万

2753
来自专栏比原链

Derek解读Bytom源码-创世区块

Gitee地址:https://gitee.com/BytomBlockchain/bytom

852
来自专栏java达人

通过比特币了解以太坊(1)

作者:Mike Goldin 图标:Eva Shon 译者:java达人 来源:https://media.consensys.net/time-sure-do...

2204
来自专栏区块链源码分析

比特币源码分析之五:区块

uint256 hashMerkleRoot; 表示交易集合算出来的merkle 树的树根hash

2754
来自专栏CDA数据分析师

五分钟带你看懂什么是区块链丨附中字视频

翻译/校对: Mika 本文为 CDA 数据分析师原创作品,转载需授权 如今区块链技术非常流行。那么让我们看到这几个问题: · 区块链究竟是什么· 工作原理是...

1869
来自专栏架构师之路

1分钟了解“挖矿”的本质

上一篇《1分钟了解区块链的本质》,介绍了什么是区块链,区块链是一个没有管理员,每个节点都拥有全部数据,高可用的分布式存储系统。 文章的留言里,不少朋友会用比特币...

36910
来自专栏码洞

面向程序猿的比特币教程之数据结构基础

最近才开始了解区块链,花了一些时间使劲钻研了一下,大致理解了比特币区块链的基本结构和运行机制。比特币说复杂也不复杂,但是如果深究下去,绝不是非常简单。

761
来自专栏信安之路

浅谈以太坊智能合约的安全漏洞

智能合约的安全是区块链安全中的热议话题,但其实 89% 的智能合约都存在漏洞,本文将浅谈以太坊智能合约出现过的一些安全漏洞。

710
来自专栏申龙斌的程序人生

PoW工作量证明

PoW是Proof of Work的缩写,即工作量证明的意思。在《拜占庭将军问题》中介绍过,比特币系统中引入了“工作量”的概念,有意降低了信息传递的效率,让矿工...

36313
来自专栏Python私房菜

最爱你的人,会让你不费脑细胞的理解区块链

区块链是一个近期非常火的概念,随便走进一个写字楼的电梯,都会听到有人谈论区块链,或者炒币: ) 希望通过这篇文章,能让你对区块链的概念有一个整体的认识,在理解概...

772

扫码关注云+社区