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

相关文章

来自专栏比原链

Derek解读Bytom源码-创世区块

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

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

一些基本比特币概念

3579
来自专栏极客编程

用Solidity语言通过以太坊钱包开发hello world示例

使用以太坊钱包开发实现经典的HelloWord智能合约类。本文中,我们将看到如何编写简单的合约并将其部署到区块链上。我们还将通过发送和读取数据来了解如何与我们的...

701
来自专栏深入浅出区块链技术

比特币脚本及交易分析 - 智能合约雏形

1184
来自专栏学习圈

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

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

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

基于Java语言构建区块链(四)—— 交易(UTXO)

上一篇 文章,我们实现了区块数据的持久化,本篇开始交易环节的实现。交易这一环节是整个比特币系统当中最为关键的一环,并且区块链唯一的目的就是通过安全的、可信的方式...

4785
来自专栏liuchengxu

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

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

742
来自专栏liuchengxu

用 Go 构建一个区块链 ---- Part 1: 基本原型

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

682
来自专栏极客编程

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

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

933
来自专栏Seebug漏洞平台

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

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

1063

扫码关注云+社区