默克尔树公告板库

该库实现了一个基于默克尔树的可验证公告板。它包含在一个仓库中，其中还包括使用该库的演示Web服务器和MySQL后端。

它能做什么？

有句俗语“信任，但要验证”。不幸的是，通常无法验证，所以如果你是这句话的另一端，你应该“值得信任，但要可验证”。这个设计就是为了帮助一个值得信任的公告板变得可验证。

具体来说，它允许连续地向公告板添加元素。定期，公告板发布一个哈希码，该哈希码是对迄今为止发布的所有元素的承诺。每个人都可以叫他们的朋友检查是否每个人都得到了相同的哈希，作为每个人都在看到相同的公告板的证据。任何人都可以检查任何特定条目是否由该哈希引用，还可以下载整个板（或自上次发布的哈希以来的添加）并检查它与提供的哈希是否兼容。

这使每个人都对公告板运营商的诚信有信心。或者他们已经找到了如何逆SHA2的方法，这被认为是非常困难的。对于“实现世界和平、繁荣和普遍的爱”这样的定义，被认为是困难的。

这与仅发布所有条目的文件并发布该文件的哈希值有什么不同？

这以更简单的方式解决了非常类似的问题，并且除了这个方法的一些优点之外，是首选的。

• 默克尔树允许在不下载整个公告板的情况下检查自己的贡献是否在树中，实际上在时间和空间上与公告板的大小成对数关系。
• 操作员可以选择在发布哈希值后拒绝提供部分树的详细信息，而不会损害其余树的验证。这对于支持审查是至关重要的，这在世界上的许多（大多数？所有？）国家对于许多应用都是法律要求。假设关于这些法律倾向于反对那些可能会使当权者尴尬的事情的标准抱怨。操作员无法隐藏审查的事实。此外，如果你碰巧知道被审查的内容是什么，你可以证明这就是被审查的内容。审查的唯一作用就是拒绝提供计算特定叶子哈希所用的文本。

API

从BulletinBoard结构开始，它有详细的文档。

还有用于包含证明的辅助验证函数，但你应该自己编写，因为整个目的就是不需要信任这个！

后端

公告板需要将信息存储在某个地方。有各种方法可以做到这一点，抽象为后端。你可以很容易地编写自己的后端，或者有各种后端可供选择。

• BackendMemory：将所有内容临时存储在内存中。适用于测试和API演示。
• BackendFlatfile：类似于BackendMemory，但具有平面文件持久存储。适用于原型设计，但不适合生产。这用于演示Web服务器。
• BackendJournal：围绕其他后端的一个包装器，它增加了出版物之间更改的持久存储。对于添加某些后端的批量下载支持很有用。
• BackendMysql：位于merkle-tree-bulletin-board-backend-mysql文件夹中。这是一个mysql或mariadb数据库的示例（可用）后端。这可以很容易地适应不同的SQL数据库。

工作原理

有关一般理论，请参阅维基百科或谷歌。

具体问题根据其特定要求而有所不同。对于公告板，我们希望项目的添加是一个持续的过程，偶尔的出版物与添加不同步。特别是，我们不能假设公告板上有2的幂次条目。我们还记录了项目的文本，而不仅仅是它们的哈希。

系统中存在三种不同类型的节点

• 叶子。公告板上的每个条目都是一个叶子。哈希为0|timestamp|entry
• 分支。每个分支包含一个左节点和一个右节点，这两个节点可能是分支或叶子。分支左侧的所有内容按时间顺序都早于分支右侧的所有内容。分支的两侧将是深度相同的完美平衡二叉树。每个叶子和分支最多有一个父节点。哈希为1|left|right
• 已发布的根。当完成发布时，将创建一个包含先前已发布根（如果有）以及所有当前无父节点的叶子和分支的已发布根节点。其中将有O(log N)个元素，其中N是叶子的数量。哈希为2|timestamp|prior|elements concatenated

请参阅hash_history.rs中的注释，以获得对哈希定义的精确描述。

每次添加条目时，都会创建一个新的叶子节点。该节点被追加到待处理树列表中。（叶子节点被认为是深度为0的树）。如果待处理列表中最后两个条目的深度相同，则从这两个条目中创建一个新的分支，并替换它们在待处理列表中的位置。这个过程会递归进行，直到待处理列表中最后两个条目的深度不同（或者列表中只剩下一个条目）。此列表的长度永远不会超过1加上N的以2为底的对数，其中N是叶子节点的数量。

此待处理列表包含没有父节点的叶子和分支列表；已发布的根实际上是这样的元素列表。这意味着发布根哈希是一个相对较小的操作，与git提交对象非常相似。

许多Merkle树的实现会在发布时将所有节点组合成单个树，并确保该树在未来的发布树中存在。这种常见的做法的好处是发布的根更简单，因为它只包含一个元素，因此对先前发布的根的包含证明只是一个对单个元素的包含证明，而不是多个元素的包含证明。然而，这种方法导致了不平衡的二叉树，并且对新发布的根相对于旧条目的包含证明经常导致性能和/或复杂性的下降。本库中使用的这种方法保证了简单的log N大小包含证明。

示例

以下演示中的图片显示了提交三个条目A、B和C并发布根后的状态。

• A生成了一个哈希值为 013c... 的叶子节点。
• B生成了一个哈希值为 b8ba... 的叶子节点。
• A和B随后合并成了一个哈希值为 e4d5... 的分支。
• C生成了一个哈希值为 23e3... 的叶子节点。
• 发布生成了一个哈希值为 bf9a... 的发布根，它引用了分支 e4d5... 和叶子 23e3...。

然后提交了一个额外的条目"D"并进行了新的发布。

• D生成了一个哈希值为 1f14... 的叶子节点。
• C和D合并成了一个哈希值为 ef57... 的分支。
• AB和CD分支合并成了一个哈希值为 1fd7... 的分支。
• 发布生成了一个哈希值为 dbe3... 的发布根，它引用了分支 1fd7...。

请注意，如果您在演示中做同样的事情，您将得到相同结构但不同的哈希值，因为时间戳包含在内。另外，上面的图片没有显示（由于空间原因）发布根 dbe3... 到先前发布的根 bf9a... 的链接。

以下截图显示了演示网络服务器中关于示例中发布根 dbe3... 中条目A的完整包含证明。

许可协议

版权所有 2021 Thinking Cybersecurity Pty. Ltd.

根据以下之一许可：

• Apache许可证版本2.0（LICENSE-APACHE 或 https://apache.ac.cn/licenses/LICENSE-2.0）
• MIT许可证（LICENSE-MIT 或 http://opensource.org/licenses/MIT）

由您选择。

贡献

除非您明确声明，否则根据Apache-2.0许可证定义的，您有意提交的任何贡献，均应按照上述方式双授权，不附加任何额外条款或条件。

版本日志

• 0.1.0 : 首次发布

• 0.1.1 : 优化标签，文档中的图片通过相对链接指向仓库，因为crates.io上似乎不兼容直接链接图片

• 0.3 : 优化错误处理。将“anyhow”错误替换为更有用的枚举错误（API更改）。删除了itertools和anyhow依赖。