秒懂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 条评论
登录 后参与评论

相关文章

来自专栏liuchengxu

50 行 Python 代码构建一个区块链

尽管有人认为区块链 (blockchain) 是一个答案先于问题的技术,但毫无疑问, 这项新的技术已然是一个计算的奇迹。不过,到底区块链是什么呢

722
来自专栏Seebug漏洞平台

从以太坊"MorphToken事件"看智能合约构造函数大小写编码错误漏洞

以太坊智能合约的含义就是一组代码(函数)和数据(合约的状态),它们位于以太坊区块链的一个特定地址上。智能合约一般使用solidity语言编写。

973
来自专栏华仔的技术笔记

一些基本比特币概念

3489
来自专栏服务端技术杂谈

比特币脚本

在比特币区块链中,交易不是这么简单,交易实际是通过脚本来完成,以承载更多的功能个,这也是为什么比特币被称为是一种“可编程的货币”。 比特币交易是首先要通过私钥解...

36510
来自专栏Seebug漏洞平台

LCTF2018 ggbank 薅羊毛实战

作者:LoRexxar'@知道创宇404区块链安全研究团队 时间:2018年11月20日

634
来自专栏学习圈

以太坊开发入门 - 基本概念

本质上是一个去中心的数据库,区块链包含一串数据块,每个数据块中包含若干交易数据、时间戳等信息,可用于验证交易的有效性。

2227
来自专栏极客编程

solidity语言开发以太坊智能合约中的继承

我们已经探索了很多主题,在编写智能合约时我们发现经常使用相同的模式:例如,智能合约具有在构造函数中设置的所有者,然后生成修改器以便仅让所有者使用一些功能。如果我...

833
来自专栏liuchengxu

用 Go 构建一个区块链 -- Part 4: 交易(1)

翻译的系列文章我已经放到了 GitHub 上:blockchain-tutorial,后续如有更新都会在 GitHub 上,可能就不在这里同步了。如果想直接运行...

892
来自专栏汇智网教程

web3.eth.getTransaction

2735
来自专栏区块链入门

【深度知识】10分钟教会你深挖以太坊数据层

在当下数据爆炸的信息时代,凭借区块链去中心化、点对点和防篡改的特性,“区块链+大数据”已成为研究的热门,可以说,区块链与大数据的结合为今后区块链应用的大规模落地...

1132

扫码关注云+社区