[toc]
默克尔树（又叫哈希树）是一种典型的二叉树结构，由一个根节点、一组中间节点和一组叶节点组成。默克尔树最早由 Merkle Ralf 在 1980 年提出，曾广泛用于文件系统和 P2P 系统中。（比如Git用到了默克尔树）🖱️
其主要特点为：
- 最下面的叶节点包含存储数据或其哈希值；
- 非叶子节点（包括中间节点和根节点）都是它的两个孩子节点内容的哈希值。
进一步地，默克尔树可以推广到多叉树的情形，此时非叶子节点的内容为它所有的孩子节点的内容的哈希值。
默克尔树逐层记录哈希值的特点，让它具有了一些独特的性质。例如，底层数据的任何变动，都会传递到其父节点，一层层沿着路径一直到树根。这意味树根的值实际上代表了对底层所有数据的“数字摘要”。
目前，默克尔树的典型应用场景包括如下几种。
通过构建集合的默克尔树，并提供该元素各级兄弟节点中的 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 相关的额外信息。
密码学中，零知识证明（英语：zero-knowledge proof）或零知识协议（zero-knowledge protocol）是一方（证明者）向另一方（检验者）证明某命题的方法，特点是过程中除“该命题为真”之事外，不泄露任何资讯。因此，可理解成“零泄密证明”。[1]例如，欲向人证明自己拥有某情报，则直接公开该情报即可，但如此则会将该细节亦一并泄露；零知识证明的精粹在于，如何证明自己拥有该情报而不必透露情报内容。这也是零知识证明的难点。[2]
若该命题的证明，需要知悉某秘密方能作出，则检验者单凭目睹证明，而未获悉该秘密，仍无法向第三方证明该命题（即单单转述不足以证明）。待证的命题中，必定包含证明者宣称自己知道该秘密，但过程中不能传达该秘密本身。否则，协议完结时，已给予检验者有关命题的额外的资讯。此类“知识的零知识证明”是零知识证明的特例，其中待证命题仅有“证明者知道某事”。
交互式零知识证明中，需要各方互动，靠通讯过程证明某方具备某知识，而另一方检验该证明是否成立。[2]
也有某种非交互式零知识证明（英语：non-interactive zero-knowledge proof）[3][4]，但证明之所以成立，依赖计算假设（典型假设是理想的密码杂凑函数）。
零知识证明要具备下列三种性质：
-
完备（complete）
若所要证之事为真，则诚实（意即依协议行事）的证明者能说服诚实验证者。
-
健全（sound）
若命题为假，则作弊证明者仅得极小机会能说服诚实验证者该事为真。
-
零知识（zero-knowledge）
若命题为真，则验证者除此之外，过程中没有得悉任何其他资讯。换言之，仅知命题为真（而不知秘密本身）已足以“想像”出一个交互的情境，其中证明者的确知道该秘密。此性质能严格定义为：每个验证者皆有相应的模拟器，输入欲证事实时，无需求助于证明者，已可输出一套通讯誊本，看似诚实验证者与证明者的通讯记录。
前两种性质，更广义的交互式证明系统亦应具备。第三种性质使该交互证明称为零知识。
零知识证明不算数学证明，因为尚允许有很少（但非零）概率，令作弊证明者能向验证者“证明”假命题。该概率称为可靠度误差（soundness error）。换言之，零知识证明是概率“证明”，而非决定性。不过，也有技巧将可靠度误差压到忽略不计。