云社区 博客 博客详情
云社区 博客 博客详情

深入比特币原理(九)——Merkle树

Aaron 发表于 2018-03-01 14:24:02 03-01 14:24
Aaron 发表于 2018-03-01 14:24:02 2018/03/01
0
1

【摘要】 Merkle树是一种哈希二叉树,它是一种用作快速归纳和校验大规模数据完整性的数据结构,比特币的交易信息存储为Merkle树结构。

Merkle树是一种哈希二叉树,它是一种用作快速归纳和校验大规模数据完整性的数据结构,比特币的交易信息存储为Merkle树结构。

比特币Merkle树结构示例:

每一个叶子节点代表一个交易的Hash值,如HA = SHA256(SHA256(Transaction A))
两个叶子节点合并后进行Hash计算,形成父节点,如HAB = SHA256(SHA256(HA + HB))

1q.png

Merkle树是一种平衡二叉树,如果交易数量为奇数,最后的叶子节点会被复制,组成偶数的叶子节点,如下:

2q.png

从Merkle树的结构可以看出,任意一个叶子节点的交易被修改,叶子节点Hash值就会变更,最终Merkle Root的Hash值就会改变。所以确定的Merkle Root可以准确的作为一组交易的唯一摘要。

下面我们来看一下如何通过Merkle树验证一笔交易
假设我们要验证区块中存在Hash值为HK的交易,我们仅需要知道HL、HIJ、HMNOP、HABCDEFGH(蓝色框)即可计算出HKL、HIJKL、HIJKLMNOP与Root节点哈希(虚线框),如果最终计算得到的Root节点哈希与区块头中记录的哈希一致,即代表该交易在区块中存在。

3q.png

使用Merkle路径验证交易,可以大大降低验证交易时需要传输的数据量,这种验证方式在SPV节点上被应用,SPV节点在需要验证交易时会向全节点请求Merkle路径信息,这是为什么SPV节点只需要存储区块头即可验证交易的原因

随着区块中的交易增多,区块大小将线性增长,而Merkle路径的大小增长却极其缓慢,如下表所示:

4q.png

从上表可以看到,区块内交易数从16笔增加到65535笔时,区块大小从4KB增加到16MB,但是梅克尔路径大小仅从128bytes增加到512bytes


登录后可下载附件,请登录或者注册

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区),文章链接,文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:huaweicloud.bbs@huawei.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
评论文章 //点赞 收藏 1
点赞
分享文章到微博
分享文章到朋友圈

评论 (0)


0/1000
评论

登录后可评论,请 登录注册

评论

您没有权限执行当前操作

温馨提示

您确认删除评论吗?

确定
取消
温馨提示

您确认删除评论吗?

删除操作无法恢复,请谨慎操作。

确定
取消
温馨提示

您确认删除博客吗?

确定
取消

确认删除

您确认删除博客吗?

确认删除

您确认删除评论吗?

温馨提示

登录超时或用户已下线,请重新登录!!!

确定
取消