# Merkle Structures

*阅读其它语言版本: [English](../merkle.md), [Korean](merkle_KR.md).*

Mimblewimble 是设计给用户在仅给出修剪后的数据的情况下也能验证系统状态。
为了实现此目标，所有交易数据都通过 Merkle trees 提交给了区块链，该 Merkle trees 即使在被修剪后也需要在更新和序列化操作上有良好的效率。

同样，几乎所有交易数据（输入（inputs），输出（outputs），超额（excesses） 和 超额证明（excess proofs））都可以某种方式进行求和，因此将 Merkle sum trees 作为默认选项并在这里处理总和是完全合理的。

Grin 的设计目标是使所有结构都易于实现尽可能的简单。Mimblewimble 引入了许多新的加密技术，应该会使其更易于理解。
它的验证规则很容易指定（没有脚本），并且 Grin 是用一种具有非常明确的语义的语言编写的，因此简单性也有助于达成易于理解的共识规则。

## Merkle Trees

每个块有四棵 Merkle trees：

### 总输出集（Total Output Set）

每个对象都是以下两项之一：用一个承诺来表示未花费的输出（unspent output）或用一个 NULL 标记表示一个已经被花费（spent）的。
它是所有未花费输出的总和树（已花费输出对总和没有任何贡献）。输出集应反映出在当前块*生效后*链的状态。

自创世起，根总和应等于所有超额的总和。

设计要求：

1. 高效地添加和更新从未花费的到已花费的。
1. 高效地证明一个特定的输出被花费了。
1. 高效的 UTXO roots 之间的差异存储。
1. 高效的树存储即使丢失数据、有数百万个条目。
1. 如果节点提交为 NULL，表示它没有未花费的子节点，并且最终其数据应该是可以被清除的。
1. 支持序列化并且能够高效的合并来自部分存档的节点中的被修剪过的树。

### 输出见证（Output witnesses）

该树反映了总输出集，但具有范围证明来代替承诺。它从不更新，仅做附加，并且不对任何内容求和。
当一个输出被花费时，从树上修剪它的范围证明就足够了而不用删除它。

设计要求：

1. 支持序列化并且能够高效的合并来自部分存档的节点中的被修剪过的树。

### 输入和输出（Inputs and Outputs）

每个对象都是这两件事之一：输入（对旧交易（transaction）输出的明确引用）或输出（一对（承诺，范围证明））。
它是一颗输出承诺的总和树，也就是输入承诺的对立面。

输入引用是旧承诺的哈希值。这是一个共识规则，所有未花费的输出必须是唯一的。

根总和应等于此块的超额总和。请参阅下一节。

通常，验证者要么会看到此 Merkle trees 的 100％ 要么 0％，因此它与任何设计都兼容。

设计要求：

1. 有效的包含证明，用于发布证明。（Efficient inclusion proofs, for proof-of-publication.）

### 超额（Excesses）

每个对象的形式为（超额，签名）。它是一颗关于超额的总和树。

通常，验证者总是会看到该树的 100％，因此甚至完全没有必要使用 Merkle 结构。
但是，为了将来支持部分存档的节点，我们希望支持高效地修剪。

设计要求：

1. 支持序列化并且能够高效的合并来自部分存档的节点中的被修剪过的树。

## 提议的 Merkle 结构

**针对所有树提出了以下设计：对于一个 sum-MMR，其中每个节点应该将其子节点的数量以及数据求和然后相加。**
**结果是，每个节点都会提交其所有子节点的计数。**

[MMRs，或 Merkle Mountain Ranges](https://github.com/opentimestamps/opentimestamps-server/blob/master/doc/merkle-mountain-range.md)

输出集的六个设计标准是：

### 高效地插入/更新

立即（包含证明）。对于任何平衡 Merkle tree 的设计都是如此。

### 高效的花费证明

Grin 本身不需要花费证明，但支持是一件好事以便将来应用于 SPV 客户端。

子计数（children-counts）表示树中每个对象的索引，该索引不会变动，因为插入仅发生在树的最右侧。

这同时也允许永久的花费证明，即使稍后将相同的输出添加到树中，对于相同的输出也可以防止错误的证明。
对于非插入顺序的树，这些属性很难实现。

### 高效的差异存储

对于这个来说，存储完整的块应该足够了。
显然，更新和撤消操作一样容易，并且由于总是按顺序处理块，因此在重组期间回滚它们就像从树的右侧删除一组连续的输出一样简单。
（这比通过重复删除来支持删除操作的树中要快得多。）

### 高效的树存储即使丢失数据

要在随机输出被花费时候更新根哈希，我们不需要存储或计算整个树。取而代之的是，我们只能存储深度为 20 的哈希，其中最多不超过一百万。
然后，每个更新仅需要重新计算高于该深度的哈希（根据比特币的历史记录可知它现在的输出数量少于 2^29 个，这意味着只需要为每个更新计算大小为 2^9 = 512 的树），在完成所有更新后，根哈希可以被重新计算出来。

这个深度是可配置的，并且可以随着输出集的增长或可用磁盘空间而改变。

这对任何 Merkle tree 都是可行的，但可能会因 PATRICIA tree 或其他前缀树而变得复杂，具体取决于如何计算深度。

### 丢弃已花费的代币（Dropping spent coins）

由于代币永远不会从已花费变为未花费，因此对于已花费的代币上的数据不再需要进行任何更新或查找。

### 高效地序列化已被修剪的树

由于每个节点都有其子节点数，因此验证人无需所有哈希就可以确定树的结构，并且可以确定哪些节点是兄弟节点，依此类推。

在输出集中，每个节点还提交其未花费子项的总和，因此验证人通过检查已被修剪节点上的总和是否为零来知道它是否缺少未花费代币的数据。

## 算法

(To appear alongside an implementation.)

## 存储

求和树数据结构允许高效地存储输出集和输出见证，同时允许立即检索根哈希或根和（适用时）。
但是，该树必须包含系统中的每个输出承诺和见证哈希。
这些数据太大，无法永久存储在内存中，即使我们考虑修剪，因为开销太大也无法在每次重新启动时从头开始进行重建（目前，比特币有超过 5000 万个 UTXO，它们需要至少 3.2 GB，假设每个 UTXO 都有几个哈希）。
因此，我们需要一种高效的方法来将这些数据结构存储在磁盘上。

哈希树的另一个限制是，给定一个键（即输出承诺），不可能在与该键关联的树中找到叶子。我们不能以任何有意义的方式从树根上走下来。
因此，需要在整个键空间上附加索引。由于 MMR 是 append-only 的二叉树，因此我们可以通过其插入位置在树中找到该键。
因此，还需要插入到树中的键的完整索引（即输出承诺）。