理解默克尔树 - 为什么使用它们，谁在使用它们，以及如何使用它们
5.00/5 (41投票s)
演示审计和一致性证明如何工作的交互式演示
在GitHub上获取最新源代码： https://github.com/cliftonm/MerkleTree
目录
引言
1979年，Ralph Merkle1 获得了哈希树（或更知名的默克尔树）的概念专利3（专利已于2002年到期）。简而言之：“本发明包含一种用于消息身份验证的数字签名方法，该方法利用单向函数的身份验证树函数和一个秘密数字。”
或者，如果您更喜欢维基百科的定义：“在密码学和计算机科学中，哈希树或默克尔树是一种树，其中每个非叶节点都标记有其子节点的标签或值（如果是叶子）的哈希。哈希树允许对大型数据结构的内容进行高效且安全的验证。哈希树是哈希列表和哈希链的泛化。”2
本文术语
我将尝试在本文中始终使用一致的术语，除非直接引用某些参考材料。
记录 - 一个无聊的词，描述一个数据包，其哈希对应于默克尔树中的“叶子”。在阅读有关默克尔树的内容时，您会根据上下文看到其他词，如“事务”或“证书”。
块 - 借用比特币的术语，我将使用“块”一词来表示代表默克尔树叶子的*所有永久记录*。引用比特币的话：“交易数据永久记录在称为块的文件中。它们可以被视为城市记录员的记录簿（记录不动产所有权变更的地方）或股票交易分类账的个别页面。”8换句话说：“记录永久记录在称为块的文件中。”
日志 - 与默克尔树同义，日志是由哈希记录构建的哈希树。除了日志表示为哈希树之外，日志还有一个特定的属性：新条目始终作为新的叶子（或叶子）附加到树的最后一个叶子。此外，对于交易系统（如货币），一旦记录被“记录”，就不能更改 - 相反，交易的更改表示为日志中的新记录条目，从而提供完整的交易审计跟踪。相反，在允许更改记录的分布式数据存储（如NoSQL数据库）中，它将更新记录的哈希，从而更新整个树。在这种情况下，默克尔树用于快速有效地识别已更改的记录，以便分布式系统中的节点可以同步。
谁在使用默克尔树？
数字货币
默克尔树（及其变体）被比特币4、以太坊6、Apache Cassandra5等系统使用，以提供
- 一致性验证
- 数据验证
- 数据同步（您将不得不等待第二部分，因为数据同步是一个独立的文章。）
这些术语是什么意思？我很快就会解释！
区块链的概念，它利用了默克尔树，正在超越比特币而日益普及。需要跟踪数据并验证数据完整性的企业开始看到区块链如何在此过程中提供帮助。
全球供应链
例如，IBM和马士基正在合作使用区块链来管理全球供应链
“科技巨头IBM（纽约证券交易所代码：IBM）和马士基（Maersk），领先的运输和物流公司马士基航运的拥有者，宣布了一项可能具有开创性的合作，利用“区块链”技术来数字化全球庞大而相互关联的托运人、货运代理、海运承运人、港口和参与供应链的当局之间的交易。
“如果得到广泛采用，这项技术可能改变全球跨境供应链，并为行业节省数十亿美元，根据IBM和马士基的说法。”10
医疗保健行业
“谷歌的人工智能健康科技子公司DeepMind Health正计划使用一种宽松地基于比特币的新技术，让医院、NHS以及最终的患者能够实时跟踪个人数据的去向。
“该计划被称为‘可验证数据审计’，旨在创建一个特殊的数字分类账，以加密可验证的方式自动记录与患者数据的每一次交互。这意味着数据的任何更改或访问都将可见。”11
资本市场
不要花2,500英镑阅读这项研究。如果您问，我也没有。
“尽管区块链最初是作为一种免费访问的、类似于公用事业的替代方案而被开发的，用于在分布式共享网络中记录和存储交易方之间的资产转移，但许多金融科技初创公司在2015年专注于开发只能由预先批准的参与者访问的私有区块链。GreySpark认为，这一趋势表明金融科技初创公司创建能够获得广泛采纳的区块链解决方案的业务需求，与银行和买方公司希望支持旨在服务于交易前后生命周期所有方面的DLT[分布式账本技术]解决方案的愿望之间存在脱节。”12
Git和Mercurial
据称（尽管我找不到我认为是权威来源的资料），Git和Mercurial都使用专门的默克尔树来管理版本。
为什么选择默克尔树？
使用像默克尔树这样的哈希树
- 显著减少了可信权威机构必须维护以证明数据完整性的数据量。
- 显著减小了执行一致性和数据验证以及数据同步的网络 I/O 数据包大小。
- 将数据验证与数据本身分离 - 默克尔树可以本地存在，或者存在于可信权威机构上，或者本身存在于分布式系统中（也许您只维护自己的树）。将“我可以证明数据有效”与数据本身解耦意味着您可以为默克尔树和数据存储实现适当且独立的（包括冗余的）持久化。
所以“为什么”的答案是三方面的
- 默克尔树提供了一种证明数据完整性/有效性的方法。
- 默克尔树需要很少的内存/磁盘空间，并且证明在计算上是简单快速的。
- 默克尔树证明和管理只需要在网络上传输非常少量、简洁的信息。
一致性验证
这被称为“一致性证明”，因为它允许您验证日志的任何两个版本是否一致
- 较早的版本包含了较早版本中的所有内容
- ......顺序相同
- ...并且所有新记录都出现在旧版本记录之后7
“如果您能证明日志是一致的，这意味着
- 没有证书[记录]被追溯并插入日志，
- 日志中的证书未被修改，
- 并且日志从未被分支或分叉。”7
因此，一致性证明对于验证您的日志是否未损坏至关重要。“监视器和审计员定期使用一致性证明来验证日志是否运行正常。”7
数据验证
这被称为“审计证明”，因为它允许您验证特定记录是否已包含在日志中。与一致性验证一样，维护日志的服务器向客户端提供证明该记录存在于日志中的证明。“任何人都可以从日志请求默克尔审计证明，并验证证书[记录]是否在日志中。审计员通常会向日志发送此类请求，以便他们可以验证TLS客户端的证书。如果默克尔审计证明未能生成与默克尔树哈希匹配的根哈希，则表示证书不在日志中。”7（稍后将详细介绍根哈希是什么以及审计证明如何工作。）
但是发送证明给客户端还有另一个原因：它证明服务器本身没有编造积极的答案，而是向您（客户端）证明它知道自己在说什么。伪造证明在计算上是不可能的。
数据同步
默克尔树在跨分布式数据存储同步数据方面很有用，因为它允许分布式系统中的每个节点在不发送所有数据进行比较的情况下，快速有效地识别已更改的记录。相反，一旦确定了树中的特定叶子已更改，就只会将与该特定叶子关联的记录通过网络发送。请注意，默克尔树不直接提供解决冲突和同步同一记录的多个写入者的机制。我们稍后将演示如何做到这一点。
如上所述，您将不得不等待第二部分，因为数据同步是一篇独立的文章。基本同步（叶子是否已更改）很简单，但在叶子可以被添加或删除的动态环境中（我不确定`insert`操作是否有意义）进行更复杂的同步是一个棘手的问题。技术上，您可能不想为此使用默克尔树，特别是由于它使审计或一致性证明的意义失效，但我认为在同步分布式数据的上下文中讨论这一点仍然有价值，当很可能一个叶子，如果不是被直接删除，至少会被标记为删除。所以，默克尔树垃圾回收是我认为与数据同步相关的一个问题。
证明至关重要
对于一致性证明和审计证明的概念至关重要的是，实际上有一个客户端可以自己验证的证明。这意味着当客户端查询服务器（理想情况下是可信的权威机构）以验证一致性或事务的存在时，服务器不会仅仅回答“是”或“否”，而是在“是”的情况下，会返回一个客户端可以验证的*证明*。该证明基于服务器对默克尔树的了解，试图让客户端相信其数据有效的人无法复制。
在分布式系统中，每个节点都维护其数据的默克尔树，在同步过程中，任何表示记录已更改的节点都会隐式地向其他节点证明自己是一个有效节点。换句话说，节点不能跳到网络上说“我有一个新记录”或“我有一个记录要替换这个其他记录”，因为它缺少证明自己给其他节点所需的信息。
默克尔树的实际应用
默克尔树通常是一个二叉树，其中每个叶子代表与该叶子关联的记录的哈希值。分支是子节点哈希串联的哈希。通过重复此过程，将子节点串联的哈希值重新哈希以创建父节点，直到到达树的顶部，称为“根哈希”。
上图*模拟*了子哈希的串联。我们将在整个文章中使用此模拟。
数据验证（审计证明）如何工作？
假设您是上图中记录“2”的所有者。您还从可信的权威机构获得了根哈希，在本模拟中是“01234567”。您要求服务器证明您的记录“2”在树中。服务器返回给您的是“3”、“01”、“4567”的哈希，如下图所示
使用此信息（包括与哈希一起返回的左右标志），证明是
- 2 + 3，从中计算出 23
- 01 + 23，从中计算出 0123
- 0123 + 4567，从中计算出 01234567
由于您知道可信权威机构提供的根哈希，因此该证明验证了“2”存在于树中。此外，您从中获取证明的系统向您证明它是一个“权威”，因为它能够提供有效的哈希，以便您可以从“2”得到您已知的根哈希“01234567”。任何试图验证您请求的假冒系统都无法为您提供中间哈希，因为您没有提供根哈希给系统，您只是告诉它给您证明 - 它无法编造证明，因为它不知道您的根哈希 - 只有您知道。
为了验证证明，只向您揭示了关于树的少量信息。此外，此证明所需的数据包非常小，使其易于通过网络发送并进行证明计算。
一致性验证（一致性证明）如何工作？
一致性证明适用于“仅追加”的树，如日志。它们通常不用于更新叶子的系统，因为这需要同步旧的根哈希值。这是可行的，只是我没想到会看到。RFC 69629的第2.1.3节提供了一些关于一致性证明如何工作的有用图示，但我发现它很难理解，所以我将在这里尝试更好地解释。使用他们的例子（但用我的模拟哈希编号），我们将从3个记录开始
创建了前三个记录“012”
在某个时候添加了第四个记录“3”，产生了这棵树
又添加了两个记录“45”
最后，又添加了一个记录“6”
对于每个子树（记录集），我们添加了
012
3
45
6
我们有
- 附加所有子树后的树的新根哈希……
- 在附加更多记录*之前*的每棵树的原始哈希。
现在，我们想验证在添加这些子树时，即使整棵树的根哈希已更改，仍然可以重建这些子树的根哈希。这验证了记录的顺序以及记录相关数据是否已更改，无论是在权威服务器上还是在客户端机器上。
一致性证明演练
一致性证明在给定新树（上图的最后一个图）的情况下，重新创建每个子树的哈希。
- 第一棵树的根哈希为“
012”。 - 添加第二棵树时，根哈希变为“
0123”。 - 添加第三棵树时，根哈希更改为“
012345”。 - 添加最后一棵树时，根哈希更改为“
0123456”。
第一棵树的一致性证明
我们需要做什么来验证第一棵树（有3个叶子）是否仍然存在于新树中？
如上图所示，我们需要2个节点“01”和“2”的哈希才能重建第一棵树的旧根哈希“012”。
第二棵树的一致性证明
添加第二棵树时，根哈希是“0123”这个节点的哈希，它附加了一个叶子“3”，总共有4个叶子。
一致性证明只是代表“0123”的节点。
第三棵树的一致性证明
第三棵树添加了两个节点“45”，当时的根哈希是“012345”。一致性证明为此提供了支持。
一致性证明的另一种场景
假设我们单独添加了叶子“4”、“5”和“6”。当我们添加“4”的叶子时，我们获得了当时树中5个叶子的节点“01234”的哈希。现在树中有7个叶子，以下是重建旧根哈希“01234”所需的组件。
一致性证明的最后一种场景
此场景与其他所有场景不同，因为需要三个节点来构建原始根哈希。给定一个有8个叶子的树，其中添加了第7个叶子（节点“6”），当时的根哈希是“0123456”的哈希。重建此哈希需要以下节点
重建旧的根哈希
上面的最后一个例子说明了如何从一致性证明中的节点列表中重建旧根哈希“0123456”。这里，节点按以下顺序提供给我们
0123
45
6
要重建旧哈希，我们必须从右到左组合哈希
45 + 6 = 456
0123 + 456 = 0123456
一致性证明的注意事项
这不是一个简单的算法，它使用以下规则和信息
- 一致性证明总是基于验证树中前*m*个叶子的计算。当我们向“日志”（现有记录集）添加树时，*m*是组合树后的叶子数量。这是必需的，因为您要确保所有数据的哈希都验证了顺序并且没有发生变异。
- 但是，通过知道代表中间根哈希的叶子数量，算法可以快速识别由以下任一项组成的特定节点：
- 匹配的哈希（如果叶子数量是2的幂）。
- 重建中间根哈希所需的子节点对。
- 这意味着当一棵树被添加到“日志”（现有记录集）中时，树中存在的叶子数量会与根哈希一起被保留。
- 在许多情况下，当一个特定的系统专门负责添加树时，这很简单，因为系统当然知道它正在添加的每棵树中有多少叶子。
- 在分布式系统中，可能还有其他参与者在添加树（以及防止并发添加操作的复杂性），添加树的参与者需要被告知树中有多少叶子，以便之后可以执行一致性检查。
- 为避免这种额外的知识，完整默克尔树的维护者可以使用字典将附加的树根映射到叶子计数。这可能是管理所需信息的一种更安全的方式。
另一方面，该算法非常高效，因为它从树的第2n（n=log2(m)）层最左边的节点开始。这避免了从第一个叶子开始计算可能数千个叶子的哈希，但仍然保证如果生成的证明与添加树时的哈希匹配，则记录的顺序和记录本身都是有效的。
一致性证明通用算法
您可以阅读RFC 69629的第2.1.2节中的一致性证明，或者您可以参考这个，如以下DRAKON图所示
规则1
找到我们可以开始进行一致性证明的树的最左边节点。通常，这将是一个节点，它代表获取旧根哈希所需的哈希的一部分（左边部分）。
给定*m*（在添加子树后主树中的叶子数量），取*n*=log2(*m*)来找到代表最多*m*个叶子的节点的索引。该索引是从最左边的叶子开始，向上遍历树的左分支。
例如
3个叶子：log2(3) = 1.58（我们从节点“01”开始）
4个叶子：log2(4) = 2（我们从节点“0123”开始）
6个叶子：log2(6) = 2.58（我们从节点“0123”开始）
这给出了您开始使用的哈希的节点的索引（向下取整）。通过从正确的级别开始，我们知道子树从该位置开始，或者是由当前节点的哈希和其兄弟节点的哈希组成的 - 如果有余数 log2(m)。此图应该有所帮助（请注意，级别3实际上并不代表8个叶子，因为所有8个叶子尚未添加）。
同时，设置*k*，该节点的叶子数量（*节点必须计算其叶子数量，因为最后一个叶子可能缺失*）。
如果存在，还将初始兄弟节点（SN）设置为规则1所获取节点的兄弟节点。
如果m-k == 0，则继续执行规则3。
使用上述图示的三个场景
- m为2：索引=1（“01”节点），它有2个叶子，所以我们继续规则3
- m为4：索引=2（“01234”节点），它有4个叶子，所以我们继续规则3
- m为3：索引=1（“01”节点），它有2个叶子，但m-k=1，所以我们继续规则2
规则2
- 如果m-k == SN的叶子数量，则连接SN的哈希并退出规则2，因为它代表旧根的哈希。
- 如果m-k < SN的叶子数量，则将SN设置为SN的左子节点并重复规则2。
- 如果m-k > SN的叶子数量，则连接SN的哈希，将k增加SN的叶子数量，并将SN设置为其父节点的右节点。
这样，我们最终总能得到可以重建旧根哈希的哈希。
几个场景
m = 3。k=2（“01”下的叶子数量），SN = “23”
SN的叶子数量是2。m-k < 2，所以SN = SN的左子节点，即“2”。
SN的叶子数量是1（是的，它*是*一个叶子）。
m-k = SN的叶子数量，所以我们知道使用“01”的哈希加上“2”的哈希来构建旧根“012”。
m = 4 由规则1处理
m = 5。k=4（“0123”下的叶子数量）。SN = “456”
SN的叶子数量是3。
m-k < SN的叶子数量，所以SN = SN的左子节点，即“45”。
SN的叶子数量现在是2。
m-k < SN的叶子数量，所以SN = SN的左子节点，即“4”。
SN的叶子数量现在是1（它是一个叶子）。
m-k = SN的叶子数量，所以我们知道使用“0123”的哈希加上“4”的哈希来构建旧根“01234”。
这是构建任意数量叶子的一致性树的一个好例子，从第一个叶子开始，无论旧根是主树中添加的树的一部分还是不是。然而，这不是典型场景。继续前进
m = 6。k=4（“0123”下的叶子数量）。SN = “456”
SN的叶子数量是3。
m-k < SN的叶子数量，所以SN = SN的左子节点，即“45”。
SN的叶子数量现在是2。
m-k - SN的叶子数量，所以我们知道使用“0123”的哈希加上“45”的哈希来构建旧根“012345”。
m = 7。k=4（“0123”下的叶子数量）。SN = “456”
m-k = SN的叶子数量，所以我们知道使用“0123”的哈希加上“456”的哈希来构建现有根“0123456”。
规则3：使用一致性证明中最后一个节点（不一定是叶子）的（适当的左或右）兄弟节点继续进行审计证明。
例如，给定这个一致性证明，到代表“01234”的树的旧哈希（这是一个更有趣的例子）
为了获得根哈希，证明的其余部分涉及的节点是节点“5”和“67”的哈希。
我们需要“5”来获得“45”，我们需要“67”来获得“4567”。很酷！
演示
该演示允许您探索创建默克尔树以及执行审计和一致性证明。图形界面实现为一个嵌入式 FlowSharp 服务。
该演示使用端口1100上的websocket与FlowSharp服务通信，用于在画布上创建形状和连接器。首次运行演示时，您可能会看到Windows防火墙警报。
请点击“允许访问”。
更改叶子数量
您可以选择最多16个叶子。为了方便渲染，叶子模拟哈希表示为0-F。
测试审计证明
您可以选择要审计的叶子来测试审计证明（叶子编号选择为0-15，其中10-15在图上表示为A-F）。当您点击“给我看”时，将显示证明并运行验证例程。图表还向您显示了执行审计证明所涉及的节点（参见上面的众多截图）。
测试一致性证明
您可以选择要测试一致性的叶子数量来测试一致性证明。用于计算旧根的节点以黄色显示，用于完成审计证明的节点以紫色显示。
复选框“仅到根节点”基本上是为了方便创建我讨论一致性证明第一部分的截图 - 紫色节点不参与第二步，审计证明。
默克尔树实现
以下是默克尔树的实现。有三个类：
MerkleHashMerkleNodeMerkleTree
让我们一一来看。
MerkleHash类
此类提供了一些静态创建运算符、相等性测试，当然还有从字节数组、字符串或其他两个`MerkleHash`实例计算哈希。
namespace Clifton.Blockchain
{
public class MerkleHash
{
public byte[] Value { get; protected set; }
protected MerkleHash()
{
}
public static MerkleHash Create(byte[] buffer)
{
MerkleHash hash = new MerkleHash();
hash.ComputeHash(buffer);
return hash;
}
public static MerkleHash Create(string buffer)
{
return Create(Encoding.UTF8.GetBytes(buffer));
}
public static MerkleHash Create(MerkleHash left, MerkleHash right)
{
return Create(left.Value.Concat(right.Value).ToArray());
}
public static bool operator ==(MerkleHash h1, MerkleHash h2)
{
return h1.Equals(h2);
}
public static bool operator !=(MerkleHash h1, MerkleHash h2)
{
return !h1.Equals(h2);
}
public override int GetHashCode()
{
return base.GetHashCode();
}
public override bool Equals(object obj)
{
MerkleTree.Contract(() => obj is MerkleHash, "rvalue is not a MerkleHash");
return Equals((MerkleHash)obj);
}
public override string ToString()
{
return BitConverter.ToString(Value).Replace("-", "");
}
public void ComputeHash(byte[] buffer)
{
SHA256 sha256 = SHA256.Create();
SetHash(sha256.ComputeHash(buffer));
}
public void SetHash(byte[] hash)
{
MerkleTree.Contract(() => hash.Length == Constants.HASH_LENGTH,
"Unexpected hash length.");
Value = hash;
}
public bool Equals(byte[] hash)
{
return Value.SequenceEqual(hash);
}
public bool Equals(MerkleHash hash)
{
bool ret = false;
if (((object)hash) != null)
{
ret = Value.SequenceEqual(hash.Value);
}
return ret;
}
}
}
MerkleNode类
此类管理节点的所有内容 - 它的父节点、子节点以及当然它的哈希。 `MerkleNode`类真正有趣的功能是它实现了自底向上/左右迭代器。
namespace Clifton.Blockchain
{
public class MerkleHash
{
public byte[] Value { get; protected set; }
protected MerkleHash()
{
}
public static MerkleHash Create(byte[] buffer)
{
MerkleHash hash = new MerkleHash();
hash.ComputeHash(buffer);
return hash;
}
public static MerkleHash Create(string buffer)
{
return Create(Encoding.UTF8.GetBytes(buffer));
}
public static MerkleHash Create(MerkleHash left, MerkleHash right)
{
return Create(left.Value.Concat(right.Value).ToArray());
}
public static bool operator ==(MerkleHash h1, MerkleHash h2)
{
return h1.Equals(h2);
}
public static bool operator !=(MerkleHash h1, MerkleHash h2)
{
return !h1.Equals(h2);
}
public override int GetHashCode()
{
return base.GetHashCode();
}
public override bool Equals(object obj)
{
MerkleTree.Contract(() => obj is MerkleHash, "rvalue is not a MerkleHash");
return Equals((MerkleHash)obj);
}
public override string ToString()
{
return BitConverter.ToString(Value).Replace("-", "");
}
public void ComputeHash(byte[] buffer)
{
SHA256 sha256 = SHA256.Create();
SetHash(sha256.ComputeHash(buffer));
}
public void SetHash(byte[] hash)
{
MerkleTree.Contract(() =>
hash.Length == Constants.HASH_LENGTH, "Unexpected hash length.");
Value = hash;
}
public bool Equals(byte[] hash)
{
return Value.SequenceEqual(hash);
}
public bool Equals(MerkleHash hash)
{
bool ret = false;
if (((object)hash) != null)
{
ret = Value.SequenceEqual(hash.Value);
}
return ret;
}
}
}
MerkleTree类
此类负责构建树并执行审计和一致性证明。使用了一些静态方法来验证审计和一致性证明，因此您无需编写验证算法。我已将该类分解为其组成部分。
属性和字段
namespace Clifton.Blockchain
{
public class MerkleTree
{
public MerkleNode RootNode { get; protected set; }
protected List<MerkleNode> nodes;
protected List<MerkleNode> leaves;
就是这样 - 非常简单。
Contract方法
public static void Contract(Func<bool> action, string msg)
{
if (!action())
{
throw new MerkleException(msg);
}
}
我使用此方法进行参数和状态验证。
构造函数
public MerkleTree()
{
nodes = new List<MerkleNode>();
leaves = new List<MerkleNode>();
}
添加叶子
public MerkleNode AppendLeaf(MerkleNode node)
{
nodes.Add(node);
leaves.Add(node);
return node;
}
public void AppendLeaves(MerkleNode[] nodes)
{
nodes.ForEach(n => AppendLeaf(n));
}
public MerkleNode AppendLeaf(MerkleHash hash)
{
var node = CreateNode(hash);
nodes.Add(node);
leaves.Add(node);
return node;
}
public List<MerkleNode> AppendLeaves(MerkleHash[] hashes)
{
List<MerkleNode> nodes = new List<MerkleNode>();
hashes.ForEach(h => nodes.Add(AppendLeaf(h)));
return nodes;
}
将一棵树添加到现有树中
public MerkleHash AddTree(MerkleTree tree)
{
Contract(() => leaves.Count > 0, "Cannot add to a tree with no leaves.");
tree.leaves.ForEach(l => AppendLeaf(l));
return BuildTree();
}
从叶子构建树
/// <summary>
/// Builds the tree for leaves and returns the root node.
/// </summary>
public MerkleHash BuildTree()
{
// We do not call FixOddNumberLeaves because we want the ability to append
// leaves and add additional trees without creating unecessary wasted space in the tree.
Contract(() => leaves.Count > 0, "Cannot build a tree with no leaves.");
BuildTree(leaves);
return RootNode.Hash;
}
/// <summary>
/// Recursively reduce the current list of n nodes to n/2 parents.
/// </summary>
/// <param name="nodes"></param>
protected void BuildTree(List<MerkleNode> nodes)
{
Contract(() => nodes.Count > 0, "node list not expected to be empty.");
if (nodes.Count == 1)
{
RootNode = nodes[0];
}
else
{
List<MerkleNode> parents = new List<MerkleNode>();
for (int i = 0; i < nodes.Count; i += 2)
{
MerkleNode right = (i + 1 < nodes.Count) ? nodes[i + 1] : null;
MerkleNode parent = CreateNode(nodes[i], right);
parents.Add(parent);
}
BuildTree(parents);
}
}
审计证明
/// <summary>
/// Returns the audit proof hashes to reconstruct the root hash.
/// </summary>
/// <param name="leafHash">The leaf hash we want to verify exists in the tree.</param>
/// <returns>The audit trail of hashes needed to create the root,
/// or an empty list if the leaf hash doesn't exist.</returns>
public List<MerkleProofHash> AuditProof(MerkleHash leafHash)
{
List<MerkleProofHash> auditTrail = new List<MerkleProofHash>();
var leafNode = FindLeaf(leafHash);
if (leafNode != null)
{
Contract(() => leafNode.Parent != null, "Expected leaf to have a parent.");
var parent = leafNode.Parent;
BuildAuditTrail(auditTrail, parent, leafNode);
}
return auditTrail;
}
protected void BuildAuditTrail(List<MerkleProofHash> auditTrail,
MerkleNode parent, MerkleNode child)
{
if (parent != null)
{
Contract(() => child.Parent == parent, "Parent of child is not expected parent.");
var nextChild = parent.LeftNode == child ? parent.RightNode : parent.LeftNode;
var direction = parent.LeftNode == child ? MerkleProofHash.Branch.Left :
MerkleProofHash.Branch.Right;
// For the last leaf, the right node may not exist.
// In that case, we ignore it because it's
// the hash we are given to verify.
if (nextChild != null)
{
auditTrail.Add(new MerkleProofHash(nextChild.Hash, direction));
}
BuildAuditTrail(auditTrail, child.Parent.Parent, child.Parent);
}
}
一致性证明
/// <summary>
/// Verifies ordering and consistency of the first n leaves,
/// such that we reach the expected subroot.
/// This verifies that the prior data has not been changed and
/// that leaf order has been preserved.
/// m is the number of leaves for which to do a consistency check.
/// </summary>
public List<MerkleProofHash> ConsistencyProof(int m)
{
// Rule 1:
// Find the leftmost node of the tree from which we can start our consistency proof.
// Set k, the number of leaves for this node.
List<MerkleProofHash> hashNodes = new List<MerkleProofHash>();
int idx = (int)Math.Log(m, 2);
// Get the leftmost node.
MerkleNode node = leaves[0];
// Traverse up the tree until we get to the node specified by idx.
while (idx > 0)
{
node = node.Parent;
--idx;
}
int k = node.Leaves().Count();
hashNodes.Add(new MerkleProofHash(node.Hash, MerkleProofHash.Branch.OldRoot));
if (m == k)
{
// Continue with Rule 3 -- the remainder is the audit proof
}
else
{
// Rule 2:
// Set the initial sibling node (SN) to the sibling of the node acquired by Rule 1.
// if m-k == # of SN's leaves, concatenate the hash of the sibling SN and exit Rule 2,
// as this represents the hash of the old root.
// if m - k < # of SN's leaves, set SN to SN's left child node and repeat Rule 2.
// sibling node:
MerkleNode sn = node.Parent.RightNode;
bool traverseTree = true;
while (traverseTree)
{
Contract(() => sn != null, "Sibling node must exist because m != k");
int sncount = sn.Leaves().Count();
if (m - k == sncount)
{
hashNodes.Add(new MerkleProofHash(sn.Hash, MerkleProofHash.Branch.OldRoot));
break;
}
if (m - k > sncount)
{
hashNodes.Add(new MerkleProofHash(sn.Hash, MerkleProofHash.Branch.OldRoot));
sn = sn.Parent.RightNode;
k += sncount;
}
else // (m - k < sncount)
{
sn = sn.LeftNode;
}
}
}
// Rule 3: Apply ConsistencyAuditProof below.
return hashNodes;
}
/// <summary>
/// Completes the consistency proof with an audit proof
/// using the last node in the consistency proof.
/// </summary>
public List<MerkleProofHash> ConsistencyAuditProof(MerkleHash nodeHash)
{
List<MerkleProofHash> auditTrail = new List<MerkleProofHash>();
var node = RootNode.Single(n => n.Hash == nodeHash);
var parent = node.Parent;
BuildAuditTrail(auditTrail, parent, node);
return auditTrail;
}
验证审计证明
/// <summary>
/// Verify that if we walk up the tree from a particular leaf,
/// we encounter the expected root hash.
/// </summary>
public static bool VerifyAudit(MerkleHash rootHash, MerkleHash leafHash,
List<MerkleProofHash> auditTrail)
{
Contract(() => auditTrail.Count > 0, "Audit trail cannot be empty.");
MerkleHash testHash = leafHash;
// TODO: Inefficient - compute hashes directly.
foreach (MerkleProofHash auditHash in auditTrail)
{
testHash = auditHash.Direction == MerkleProofHash.Branch.Left ?
MerkleHash.Create(testHash.Value.Concat(auditHash.Hash.Value).ToArray()) :
MerkleHash.Create(auditHash.Hash.Value.Concat(testHash.Value).ToArray());
}
return rootHash == testHash;
}
获取用于验证的哈希对形式的审计证明
/// <summary>
/// For demo / debugging purposes,
/// we return the pairs of hashes used to verify the audit proof.
/// </summary>
public static List<Tuple<MerkleHash, MerkleHash>> AuditHashPairs
(MerkleHash leafHash, List<MerkleProofHash> auditTrail)
{
Contract(() => auditTrail.Count > 0, "Audit trail cannot be empty.");
var auditPairs = new List<Tuple<MerkleHash, MerkleHash>>();
MerkleHash testHash = leafHash;
// TODO: Inefficient - compute hashes directly.
foreach (MerkleProofHash auditHash in auditTrail)
{
switch (auditHash.Direction)
{
case MerkleProofHash.Branch.Left:
auditPairs.Add(new Tuple<MerkleHash, MerkleHash>(testHash, auditHash.Hash));
testHash = MerkleHash.Create
(testHash.Value.Concat(auditHash.Hash.Value).ToArray());
break;
case MerkleProofHash.Branch.Right:
auditPairs.Add(new Tuple<MerkleHash, MerkleHash>(auditHash.Hash, testHash));
testHash = MerkleHash.Create
(auditHash.Hash.Value.Concat(testHash.Value).ToArray());
break;
}
}
return auditPairs;
}
验证一致性证明
public static bool VerifyConsistency(MerkleHash oldRootHash, List<MerkleProofHash> proof)
{
MerkleHash hash, lhash, rhash;
if (proof.Count > 1)
{
lhash = proof[proof.Count - 2].Hash;
int hidx = proof.Count - 1;
hash = rhash = MerkleTree.ComputeHash(lhash, proof[hidx].Hash);
hidx -= 2;
while (hidx >= 0)
{
lhash = proof[hidx].Hash;
hash = rhash = MerkleTree.ComputeHash(lhash, rhash);
--hidx;
}
}
else
{
hash = proof[0].Hash;
}
return hash == oldRootHash;
}
在叶子列表中查找叶子
protected MerkleNode FindLeaf(MerkleHash leafHash)
{
// TODO: We can improve the search for the leaf hash
// by maintaining a sorted list of leaf hashes.
// We use First because a tree with an odd number of leaves will duplicate the last leaf
// and will therefore have the same hash.
return leaves.FirstOrDefault(l => l.Hash == leafHash);
}
创建MerkleNode重写以满足自定义节点要求
// Override in derived class to extend the behavior.
// Alternatively, we could implement a factory pattern.
protected virtual MerkleNode CreateNode(MerkleHash hash)
{
return new MerkleNode(hash);
}
protected virtual MerkleNode CreateNode(MerkleNode left, MerkleNode right)
{
return new MerkleNode(left, right);
}
其他 - FixOddNumberLeaves
在比特币中，一棵树总是偶数个叶子。如果树中的最后一个叶子是左分支，那么最后一个叶子将被复制到右叶子位置，父节点的哈希因此由相同（左分支）哈希的串联计算而来。您可以使用`FixOddNumberLeaves`来创建此行为。
/// <summary>
/// If we have an odd number of leaves, add a leaf that
/// is a duplicate of the last leaf hash so that when we add the leaves of the new tree,
/// we don't change the root hash of the current tree.
/// This method should only be used if you have a specific reason that you need to balance
/// the last node with it's right branch, for example as a pre-step to computing an audit trail
/// on the last leaf of an odd number of leaves in the tree.
/// </summary>
public void FixOddNumberLeaves()
{
if ((leaves.Count & 1) == 1)
{
var lastLeaf = leaves.Last();
var l = AppendLeaf(lastLeaf.Hash);
}
}
其他 - 给定两个哈希计算哈希
public static MerkleHash ComputeHash(MerkleHash left, MerkleHash right)
{
return MerkleHash.Create(left.Value.Concat(right.Value).ToArray());
}
MerkleProofHash类
此类由审计证明使用，它将左/右分支与证明哈希关联起来，这对于按正确顺序串联两个子哈希以获得父哈希是必需的。
namespace Clifton.Blockchain
{
public class MerkleProofHash
{
public enum Branch
{
Left,
Right,
OldRoot, // used for linear list of hashes
// to compute the old root in a consistency proof.
}
public MerkleHash Hash { get; protected set; }
public Branch Direction { get; protected set; }
public MerkleProofHash(MerkleHash hash, Branch direction)
{
Hash = hash;
Direction = direction;
}
public override string ToString()
{
return Hash.ToString();
}
}
}
单元测试
共有14个单元测试，其中一些很傻，大部分都很简单。最有趣的单元测试是一致性证明的测试，所以我将在这里只描述它。
一致性证明单元测试
此单元测试创建具有3到100个叶子的树，对于每棵树，测试是否可以为叶子[1, n-1]（其中n是测试树中的叶子数量）获得旧根。
[TestMethod]
public void ConsistencyTest()
{
// Start with a tree with 2 leaves:
MerkleTree tree = new MerkleTree();
var startingNodes = tree.AppendLeaves(new MerkleHash[]
{
MerkleHash.Create("1"),
MerkleHash.Create("2"),
});
MerkleHash firstRoot = tree.BuildTree();
List<MerkleHash> oldRoots = new List<MerkleHash>() { firstRoot };
// Add a new leaf and verify that each time we add a leaf, we can get a consistency check
// for all the previous leaves.
for (int i = 2; i < 100; i++)
{
tree.AppendLeaf(MerkleHash.Create(i.ToString())); //.Text=i.ToString();
tree.BuildTree();
// After adding a leaf, verify that all the old root hashes exist.
oldRoots.ForEachWithIndex((oldRootHash, n) =>
{
List<MerkleProofHash> proof = tree.ConsistencyProof(n+2);
MerkleHash hash, lhash, rhash;
if (proof.Count > 1)
{
lhash = proof[proof.Count - 2].Hash;
int hidx = proof.Count - 1;
hash = rhash = MerkleTree.ComputeHash(lhash, proof[hidx].Hash);
hidx -= 2;
while (hidx >= 0)
{
lhash = proof[hidx].Hash;
hash = rhash = MerkleTree.ComputeHash(lhash, rhash);
--hidx;
}
}
else
{
hash = proof[0].Hash;
}
Assert.IsTrue(hash == oldRootHash, "Old root hash not found for index "
+ i + " m = " + (n+2).ToString());
});
// Then we add this root hash as the next old root hash to check.
oldRoots.Add(tree.RootNode.Hash);
}
}
单调哈希和区块链
哈希树是创建数据完整性高效证明的一种方式。单调（顺序有序）也可以是处理哈希链的适当方式。其中一个例子是 Holochain "...一个由权威哈希链支持的验证性单调DHT..."14 Holochain是“...一个共享的DHT，其中每个数据都根植于一个或多个方的签名哈希链。它是一个验证性DHT，因此数据在未首先被每个节点持有的共享验证规则验证之前无法传播”13 因此，可以将这两种技术（单调哈希链和哈希树）结合起来。正如 Arthur 在Slack上告诉我
默克尔树可以用于holochain条目内部，以拥有真正*私有*的数据（不仅仅是加密的），在一个共享的链空间中。我的意思是……假设您有一个包含以下6个字段的数据结构
- 发送者ID
- 发送者上一个哈希
- 接收者ID
- 接收者上一个哈希
- 发送的信用数量
- 交易负载
如果您将这些结构化为具有这6个叶子的默克尔树，那么交易双方都可以将其完整交易提交到他们的私人链，然后两人将一个部分默克尔树放入共享DHT并签名，其中*不包含*字段#6的叶子节点。这足以对需要发布的用于管理货币的前5个字段进行默克尔证明，使他们能够拥有数字资产，或隐藏字段中的任何其他类型的数据，这些数据可以*始终*保留在您的本地链上，只有您可以看到，而不会损害管理相互信贷加密货币所需数据的完整性。
在区块链上，交易中的所有数据都会进入链，您需要加密您想保密的ส่วน，并希望您的密钥或使用的加密方案永远不会在此永久公开记录上受到损害。在holochain上，由于共享DHT“由本地链的数据验证支持”的机制，您可以使用默克尔证明来混合公共/私人数据，以便您可以真正地将私人数据保持私密。
比特币、以太坊和其他区块链也是单调哈希链（块链）的示例，其中包含交易的默克尔树。
结论
写这篇文章绝对是“只有当你能教会它时，你才理解它”的经历的体现。它需要大量的研究和挖掘才能理解，特别是对于一致性证明的算法。更重要的是，“为什么”的理解并不直观。我最终与自己进行了一次心理问答环节，我决定在这里添加它，以便您可以看到我基本的问题以及我如何决定回答它们，至少对我自己而言。其中一些答案可能不那么好，有些可能会深入不必要的兔子洞等等，所以请记住，这代表了我开始写这篇文章之前自己调查的一个快照。
在您阅读我可能很奇怪的思考过程之前，再补充一点结论 - 区块链及其变体，在我看来，注定会成为分布式数据管理的核心组成部分。默克尔树和类似的哈希树实现是这项技术工作方式的基石。
数据同步问答
- 作为“客户端”，您正在从对等方下载一个大文件，假设为10GB，分布在4096字节的块中。
- 您需要一个可信的权威服务器来告诉您每个块是否有效。
- 从服务器，您可以获得根哈希，并且随着每个块的到来，您可以开始自己填充默克尔树。
- 但是，您需要下载所有数据才能完成树以验证根。
- 相反，您可以要求服务器向您发送一个哈希块（叶子）到根哈希的路径，并自己验证它。这使您能够验证每个块，如果它有问题，可以从别处请求它，同时下载其他块。此外，您不必维护所有哈希值并自己构建整个默克尔树。因此，验证一个块更快，而且您自己需要存储整个默克尔树的内存也更少。
- 服务器（作为可信权威机构）不持有数据，但它必须拥有默克尔树，包括叶子哈希。
关于数据同步，您基本上有三个选项：
- 下载所有数据，以便您可以验证默克尔根哈希
- 从可信的权威机构下载默克尔树，以便您可以测试不完整的记录集。
- 要求服务器对特定叶子执行审计证明。
验证问答
Q1：为什么不直接问服务器叶子是否存在于具有特定根的树中？
Q2：服务器为什么还要存储叶子哈希的默克尔树？（也请参阅Q4的答案）
A1：您可以这样做，但SHA256哈希只有32字节，虽然这代表了大量的唯一哈希（2^256，1.15*10^77），但我们在树中向上走时对节点对哈希进行哈希处理，可以强烈验证所讨论的哈希属于正确的树。此外，审计证明会验证记录相对于其他叶子的特定顺序。*我们不只是想知道叶子是否存在，我们想验证它是否在树中的特定位置。*
A2：假设您有一个大型数据集，分为小块。首先，您可能不维护整个数据集，而只维护您负责的部分。如果该块发生更改，您只需知道到根的左右分支即可重新计算根哈希。
其副作用是，您只需要维护您块的左右分支，而不是整个默克尔树（包括您不知道或不关心的块的所有叶子哈希）。
为了同步，另一个用户要求您将其根哈希与他们的根哈希进行比较。如果不同，则请求左右子哈希，然后该过程会迭代不匹配项，直到识别出您端的已更改块。现在您只需将更改的块发送给另一个用户，您们就可以再次同步。
检测冲突问答
Q3：如果多个用户修改同一块（基于分布式系统中希望跨多个对等节点复制数据以实现弹性的想法）会发生什么？
A1：只有一个对等节点可以有权更改数据。
A2：哈希可以打时间戳，并且只接受最新的更改，丢弃其他所有内容。
A3：合并差异（自动或需要手动干预）。
A4：只接受最旧的更改，丢弃任何更新的。
A5：技术上讲，一个块永远不应该被更改。如果需要更改，则应将其记录为新事务，以便有可审计的更改历史记录（与默克尔审计不同）。鉴于此，只有指定的权限才能修改事务。
A6：可以使用某种阻塞机制来防止数据被同时修改。例如，您可以获得一个“更改密钥”，当您提交更改时，如果您的更改密钥与当前更改密钥不匹配，您的更改将被拒绝，要求您同步数据，获取新的更改密钥，然后再次提交您的更改。
A7：这里的关键点是，如果块的大小很小，您的更改与他人的更改发生冲突的可能性就很小。
为什么需要证明问答
Q4：为什么服务器在仅仅发送“是/否”响应而不是发送哈希审计跟踪来验证块，而不是直接发送“是/否”响应？
A：这是您验证服务器未被泄露的方式 - 如果它只说“是”，您如何知道可以信任它？通过向您发送左右哈希，服务器告诉您“这是我验证您请求的方式。”试图让您相信您的块有效的服务器无法发送“任何”审计跟踪哈希，因为这会产生不同的根哈希。
参考文献
- 1 Ralph Merkle
- 2 Merkle Tree
- 3 Method of providing digital signatures, patent US 4309569 A
- 4 Bitcoin Developer GuideBlock Chain
- 5 Cassandra's AntiEntropy service
- 6 Merkling in Ethereum
- 7 Consistency Proofs and Audit Proofs
- 8 bitcoin block
- 9 RFC6962Certificate Transparency
- 10 IBM, Maersk Reveal Blockchain Solution for Global Supply Chain
- 11 Google's DeepMind plans bitcoin-style health record tracking for hospitals
- 12 The Blockchain: Capital Markets Use Cases
- 13 Holochain (website)
- 14 Holochain (github)
历史
- 2017年3月13日：初始版本