🧭
🧭
🧭
🧭
区块链技术指南
搜索文档…
🧭
🧭
🧭
🧭
区块链技术指南
前言
修订记录
如何贡献
区块链的诞生
核心技术概览
典型应用场景
分布式系统核心技术
密码学与安全技术
密码学简史
Hash 算法与数字摘要
加解密算法
消息认证码与数字签名
数字证书
PKI 体系
Merkle 树结构
Bloom Filter 结构
同态加密
其它技术
本章小结
比特币 —— 初露锋芒的区块链
以太坊 —— 挣脱加密货币的枷锁
超级账本 —— 面向企业的分布式账本
Fabric 安装与部署
智能合约开发
Fabric 架构与设计
区块链服务平台设计
性能与评测
附录
由
GitBook
提供支持
Merkle 树结构
默克尔树
(又叫哈希树)是一种典型的二叉树结构,由一个根节点、一组中间节点和一组叶节点组成。默克尔树最早由 Merkle Ralf 在 1980 年提出,曾广泛用于文件系统和 P2P 系统中。
其主要特点为:
最下面的叶节点包含存储数据或其哈希值;
非叶子节点(包括中间节点和根节点)都是它的两个孩子节点内容的哈希值。
进一步地,默克尔树可以推广到多叉树的情形,此时非叶子节点的内容为它所有的孩子节点的内容的哈希值。
默克尔树逐层记录哈希值的特点,让它具有了一些独特的性质。例如,底层数据的任何变动,都会传递到其父节点,一层层沿着路径一直到树根。这意味树根的值实际上代表了对底层所有数据的“数字摘要”。
目前,默克尔树的典型应用场景包括如下几种。
证明某个集合中存在或不存在某个元素
通过构建集合的默克尔树,并提供该元素各级兄弟节点中的 Hash 值,可以不暴露集合完整内容而证明某元素存在。
另外,对于可以进行排序的集合,可以将不存在元素的位置用空值代替,以此构建稀疏默克尔树(Sparse Merkle Tree)。该结构可以证明某个集合中不包括指定元素。
快速比较大量数据
对每组数据排序后构建默克尔树结构。当两个默克尔树根相同时,则意味着所代表的两组数据必然相同。否则,必然不同。
由于 Hash 计算的过程可以十分快速,预处理可以在短时间内完成。利用默克尔树结构能带来巨大的比较性能优势。
快速定位修改
以下图为例,基于数据 D0……D3 构造默克尔树,如果 D1 中数据被修改,会影响到 N1,N4 和 Root。
Merkle 树示例
因此,一旦发现某个节点如 Root 的数值发生变化,沿着 Root --> N4 --> N1,最多通过 O(lgN) 时间即可快速定位到实际发生改变的数据块 D1。
零知识证明
仍以上图为例,如何向他人证明拥有某个数据 D0 而不暴露其它信息。挑战者提供随机数据 D1,D2 和 D3,或由证明人生成(需要加入特定信息避免被人复用证明过程)。
证明人构造如图所示的默克尔树,公布 N1,N5,Root。验证者自行计算 Root 值,验证是否跟提供值一致,即可很容易检测 D0 存在。整个过程中验证者无法获知与 D0 相关的额外信息。
以前
PKI 体系
下一个
Bloom Filter 结构
最近更新
5mo ago
复制链接
在 GitHub 上编辑
大纲
证明某个集合中存在或不存在某个元素
快速比较大量数据
快速定位修改
零知识证明