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

相关文章

来自专栏CSDN技术头条

用不到50行的Python代码构建最小的区块链

本文用不到50行的 Python 代码构建最小的数据区块链,简单介绍了区块链去中心化的结构与其实现原理。

6827
来自专栏码洞

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

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

651

我编写了一个应用程序来告诉你区块链是如何运作的

为了演示一个区块链, 我们将使用一个名为Blockchain CLI的开源命令行界面.

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

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

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

2604
来自专栏从流域到海域

如何进行一次真正的原子交换

原文地址:https://hackernoon.com/so-how-do-i-really-do-an-atomic-swap-f797852c7639

3656
来自专栏区块链深度

原来区块链上的区块长得像大白!好奇里面都有些什么?

盖一间房子,它的基本单元结构是每一块砖;而组成区块链的基本单元结构,就叫做区块。每个区块由区块头和区块主体组成。如果把区块链比做有头有身子的人,那它更像大白:区...

3538
来自专栏纯洁的微笑

用Java实现简单的比特币系统

1355
来自专栏一块探索区块链

基于Java语言构建区块链(二)—— 工作量证明

在 上一篇 文章中,我们实现了区块链最基本的数据结构模型,添加区块以及和前一个区块连接在一起。但是,我们的实现方式非常简单,而真实的比特币区块链中,每一个区块的...

4434
来自专栏何俊林

用Java实现简单的比特币系统

最近区块链技术突然爆火,身边做技术的朋友茶余饭后不谈点区块链什么的都被认为是跟不上时代了,为啥会这样了? 这其实跟比特币价格去年的突飞猛进是分不开的,比特币价格...

3093
来自专栏友弟技术工作室

通过一个App Demo的演示深入理解区块链运行原理

从字面上看:区块链是由一个个记录着各种信息的小区块链接起来组成的一个链条,类似于我们将一块块砖头叠起来,而且叠起来后是没办法拆掉的,每个砖头上面还写着各种信息,...

2835

扫描关注云+社区