Transparent Logs for Skeptical Clients

假设我们想要维护并发布一个公开的、只能追加的数据日志。同时，假设客户对我们正确实施和操作的日志表示怀疑：我们可能会利用从日志中遗漏事项，或者今天在日志中输入某事，然后明天将其删除。那么我们如何说服客户我们是在规范行为呢？

这篇文章介绍了一种优雅的数据结构，可以用来发布具有以下三个特性的N条记录的日志：

对于长度为N的日志中的任何特定记录R，我们可以构建一个长度为O(lg N) 的证明，允许客户验证R是否在日志中。
对于客户观察到并记住的任何早期日志，我们可以构建一个长度为O(lg N) 的证明，允许客户验证早期日志是否是当前日志的前缀。
审核员可以有效地遍历日志中的记录。

（在这篇文章中，“lg N”表示N的以2为底数的对数，“log”只表示“一系列记录”。）

证书透明度项目就以这种方式发布TLS证书。Google Chrome使用属性（1）来验证增强型验证证书是否已经记录在已知日志中，在接受该证书之前进行确认。属性（2）确保接受过的证书不会无法检测地从此后得到删除（即不会无法检测的从日志中消失）。属性（3）允许审核员在任何之后的时间扫描整个证书登记册（日志记录系统）以便检测被误发或被盗取的证书。所有这些都发生在没有盲目信任该登记册（日志记录系统）本身正在正确操作下。相反, 该日志记录系统的用户——Chrome和所有审核员——作为访问它的一部分来验证日志的正确操作。

本文解释了可验证防篡改性日志(也称透明日志)设计和实现。首先, 我们需要一些密码学基础模块。

1. Cryptographic Hashes, Authentication, and Commitments

密码学哈希函数是一种确定性函数H，它将任意大小的消息M映射到小的且固定大小的输出H(M)，并且具有这样的特性：在实践中，不可能产生任何一对不同的消息M1 ≠ M2，其哈希值H(M1) = H(M2)相同。当然，实际上什么是可行的会改变。在1995年，SHA-1是一个合理的密码哈希函数。到2017年，SHA-1成为了一个破解的密码哈希函数，当研究人员确定并演示了生成冲突消息的实际方法。现在，SHA-256被认为是一个合理的密码哈希函数。最终它也会被破解。

一个（未破解的）密码哈希函数提供了一种将少量可信数据引导到大量数据的方式。假设我想与您共享一个非常大的文件，但我担心数据可能会因随机损坏或中间人攻击而受损。我可以亲自见到您，将文件的 SHA-256 哈希写在一张纸上，然后无论数据位于何种不可靠的路径上，您都可以通过重新计算下载的文件的 SHA-256 哈希来检查您是否获得了正确的数据。如果匹配，那么您可以确定，假设 SHA-256 没有被破解，您已经下载了我打算发送的确切数据位。SHA-256 哈希进行身份验证，即它证明了下载的数据的真实性，尽管它只有 256 位，而下载的数据要大得多。

我们还可以反过来考虑情景，即您不是不信任网络，而是不信任我。如果我告诉您我承诺发送的文件的 SHA-256 哈希值，那么 SHA-256 就是对特定数据序列的可验证承诺。我以后不能发送不同的数据序列并说服您它是我承诺的文件。

单个哈希可以是对任意大量数据的身份验证或承诺，但验证需要对整个数据集进行哈希。为了允许对数据子集进行选择性验证，我们可以使用不仅仅是单个哈希，而是一棵平衡的二进制树，称为 Merkle 树。

2. Merkle Trees（梅克尔树）

梅克尔树是从N个记录构建的，其中N是2的幂次方。首先，每个记录都被独立地进行哈希运算，产生N个哈希值。然后，这些哈希值成对进行哈希运算，产生N/2个新的哈希值。接着，这些哈希值再次成对进行哈希运算，产生N/4个哈希值，依此类推，直到只剩下一个哈希值。下面的图示展示了大小为N = 16的梅克尔树：

底部的方框代表了16个记录。树中的每个数字代表一个单独的哈希值，输入之间通过向下的线连接。我们可以通过它的坐标来引用任何哈希值：级别L哈希编号K，我们将缩写为h(L, K)。在级别0，每个哈希值的输入是一个单独的记录；在更高的级别，每个哈希值的输入是来自下一级别的一对哈希值。

h(0, K) = H(record K)

h(L+1, K) = H(h(L, 2K), h(L, 2K+1))

为了证明特定记录包含在给定顶级哈希表示的树中（也就是，让客户端验证记录，或者验证先前的承诺，或者两者都有），只需提供从记录的哈希开始重新计算整体顶级哈希所需的哈希即可。例如，假设我们想证明某个比特串B实际上是具有顶级哈希T的16条记录树中的第9条记录。我们可以提供这些比特以及其他需要用这些比特重构整个树的哈希输入。具体来说，客户端可以像我们一样推导出：

T = h(4, 0) = H(h(3, 0), h(3, 1)) = H(h(3, 0), H(h(2, 2), h(2, 3))) = H(h(3, 0), H(H(h(1, 4), h(1, 5)), h(2, 3))) = H(h(3, 0), H(H(H(h(0, 8), h(0, 9)), h(1, 5)), h(2, 3))) = H(h(3, 0), H(H(H(h(0, 8), H(record 9)), h(1, 5)), h(2, 3))) = H(h(3, 0), H(H(H(h(0, 8), H(B)), h(1, 5)), h(2, 3)))

如果我们向客户端提供值[h(3, 0), h(0, 8), h(1, 5), h(2, 3)]，客户端可以计算出H(B)，然后使用这个公式组合所有这些哈希值，并检查结果是否与T匹配。如果是这样，客户端可以在密码学上确定B确实是具有顶级哈希T的树中的第9个记录。实际上，证明 B 是带有哈希 T 的 Merkle 树中的记录是通过以 H(B) 作为输入给出 T 的可验证计算来完成的。

从图形上看，证明由路径上的节点的兄弟哈希（蓝圈标出）组成，该路径从被证明的记录一直到树的根节点（黄色高亮部分）。

一般来说，证明给定记录包含在树中需要 lg N 个哈希值，根以下的每一层都有一个哈希值。

将我们的日志作为在Merkle树中哈希的记录序列构建，将为我们提供一种编写有效（长度为lg N）证明特定记录在日志中的方法。但是有两个相关问题需要解决：我们的Merkle树中的日志总数量需要对任何长度N定义，而不仅仅是2的幂，并且我们需要能够编写一个有效证明，该证明可以有效的证明一个日志是另一个日志的前缀。

3. A Merkle Tree-Structured Log

为了将Merkle树推广到非二次幂大小，我们可以将N写成递减的二次幂之和，然后为输入的连续部分构建这些大小的完整Merkle树，最后将至多lg N个完整树一起哈希以产生单个顶级哈希。例如，13 = 8 + 4 + 1：

新标记为“x”的哈希组合了完整的树，从右到左构建，以产生整体树哈希。注意这些哈希必然组合了不同大小的树和因此来自不同级别的哈希；例如，h(3, x) = H(h(2, 2), h(0, 12))。

对于完全Merkle树的证明策略同样适用于这些不完全的树。例如，在尺寸13的树中证明记录9存在是[h(3, 0), h(0, 8), h(1, 5), h(0, 12)]：

注意h(0, 12)包含在证明中是因为它是在计算h(3, x)时h(2, 2) 的兄弟。

我们仍然需要能够编写一个有效的证明，它可以证明大小为N具有哈希T的树的日志是大小为N’ (> N) 具有哈希T’的树的日志前缀。早些时候，通过使用 H(B) 作为输入给出 T 的可验证计算来证明 B 是带有哈希 T 的 Merkle 树中的记录。为了证明具有树哈希T的日志包含在具有树哈希T’的日志中，我们可以遵循相同的想法：给出 T 和 T′ 的可验证计算，其中 T 计算的所有输入也是 T′ 计算的输入。例如，考虑大小为 7 和 13 的树：

在图示中，“x”节点完成了大小为13且哈希值为T13的树，而“y”节点完成了大小为7且哈希值为T7的树。要证明T7的叶子包含在T13中，我们首先以完整子树（用蓝色圈出）来计算T7：

T7 = H(h(2, 0), H(h(1, 2), h(0, 6)))

然后，我们提供T13的计算，根据需要扩展哈希以显示相同的子树。这样做会暴露出兄弟子树（用红色圈出）：

T13 = H(h(3, 0), H(h(2, 2), h(0, 12)))
= H(H(h(2, 0), h(2, 1)), H(h(2, 2), h(0, 12)))
= H(H(h(2, 0), H(h(1, 2), h(1, 3))), H(h(2, 2), h(0, 12)))
= H(H(h(2, 0), H(h(1, 2), H(h(0, 6), h(0, 7)))), H(h(2, 2), h(0, 12)))

假设客户端知道树的大小为7和13，它可以自己推导出所需的分解。我们只需要提供哈希[h(2, 0), h(1, 2), h(0, 6), h(0, 7), h(2, 2), h(0, 12)]。客户端重新计算由哈希暗示的T7和T13，并检查它们是否与原始值匹配。

请注意，这些证明仅使用已完成的（完整的）子树的哈希——也就是说，编号哈希，而不是组合不同大小子树的“x”或“y”哈希。编号哈希是永久性的，意味着一旦此类哈希出现在给定大小的树中，相同的哈希将出现在所有更大尺寸的树中。相比之下，“x”和“y”哈希是短暂性——为单个树计算并再也不会看到。因此，两个不同大小树分解共有的哈希必须始终是永久哈希。

较大树的分解可能使用暴露兄弟子树的短暂哈希，但我们可以轻易地只使用永久性哈希代替。在上述例子中，从T7部分重构T13使用了h(2, 2) 和h(0, 12) 而非假设访问到T13 的h(3,x) 。避免短暂性哈希将最大记录证明长度从lg N个的哈希值扩展到2lg N个的哈希值以及最大树证明长度从 2 lg N 哈希扩展到3 lg N 哈希。

注意包括 T7 和 T13 在内得大多数顶级哈希本身就是短暂性的，需要多达 lg N 永久性哈希来计算。例外情况包括二次幂数尺寸数 T1、T2、T4、T8 等等。

3.0 difference of ephemeral/permanent Hash

在Merkle树中，永久性哈希子树对应于左右子树大小相等且都是完全二叉树（即，树的每个级别都已完全填充）的子树。这种对称性允许在构造更大的树时重复使用这些哈希。

另一方面，短暂性哈希子树对应于左右子树可能大小不同或者并非所有级别都被完全填满的子树。因为这些结构不是对称的，所以它们的哈希不能在构造更大的树时重复使用。

所以下面3.1中的造成的一些现象就很好理解了。

3.1 ephemeral/permanent Hash

使用短暂性哈希会导致长度扩展，因为这些哈希是特定于单个树的，不能在不同的树之间重复使用。这意味着对于每个新的树，都需要计算和存储新的短暂性哈希，从而增加了需要跟踪的总哈希数量。

相比之下，永久性哈希可以在不同的树之间重复使用。一旦为给定子树计算出永久性哈希，就可以在包含相同子树的任何更大的树中再次使用它。这种可重用性使得它们比短暂性哈希更具空间效率。

简单来说：你越依赖短暂（一次性使用）散列，随着数据量增长所需存储空间就越多。这就是避免使用短暂散列有助于保持证明大小较小的原因。

在Merkle树的上下文中，短暂（临时）哈希是特定于特定树结构的哈希，无法在构建更大的树时重复使用。短暂性哈希通常是由于组合不同大小的子树以创建新的、更大的树而产生。说短暂性哈希基于“不完整记录”并不准确——它实际上是基于完整子树，但这些子树可能大小不同。关键点在于，组合不同大小的子树会导致一个不能在构建更大的树时重复使用的哈希。

任何给定Merkle树的顶级哈希（通常被称为”根”或”Merkle根”）确实是有意义的：它作为包含在该树中所有数据的摘要或指纹。如果树内的任何一部分数据发生变化，那么这将导致不同的根哈希。然而，除非其对应子树大小恰好是2的幂，否则这个顶级根哈希也会被视为短暂性。

因此，你可以将短暂性哈希看作是特定于某个具体Merkle 树结构（可能包括不同大小子树组合）并且不能重用于其他更大Merkle 树构建过程中的哈希值。而永久性哈希则能够在多个不同大小Merkle 树间进行重用。

3.2 Storing a Log

存储日志只需要一些只追加文件：第一个文件保存连接的日志记录数据。第二个文件是第一个的索引，保存一系列int64值，表示第一个文件中每条记录的起始偏移量。这个索引允许通过其记录号高效地随机访问任何记录。虽然我们可以仅从记录数据重新计算任何哈希树，但这样做将需要N-1次哈希操作来创建大小为N的树。因此，有效生成证明需要预先计算并以某种更易于访问的形式存储哈希树。

正如我们在上一节中提到的，树之间有很大的共性。特别是，最新的哈希树包含了所有早期哈希树中所有永久性哈希，所以只需“仅”存储最新的哈希树就足够了。实现这一点简单直接的方法是维护lg N个只追加文件，每个都保存着树某一级别上连续序列化的哈希值。因为哈希是固定大小, 通过从适当偏移处读取文件可以高效地读取任意特定hash。

要写入新日志记录, 我们必须将该记录数据附加到数据文件, 将该数据偏移量附加到索引文件，并将该数据hash附加到level-0 hash 文件. 然后, 如果我们在level-0 hash 文件完成了一对hashes, 我们就把这对hashes 的hash 附加到level-1 hash 文件；如果在level-1 hash 文件完成了一对hashes ，那么我们就把那对hashes 的hash 附加到 level-2 hash 文件；依此类推直至整棵树。每次写入日志记录都会至少向一个且最多向lg N 个hash 文件添加一个Hash , 平均每次写入新增不超过两个新Hash。 (具有N片叶子节点的二叉树有N -1个内部节点)

也可以将lg N append-only 哈希文件交织成单独append-only文件，使得日志可以仅存储在三份档案：记录数据、记录索引和哈希值。具体详情请参阅附件A。另外还可能存在将log 存放在一对数据库表中，一个用于记录数据，另一个用于哈希（数据库可以自己提供记录索引）。

无论是在文件中还是在数据库表中，日志的存储形式都是只追加的，所以缓存数据永不过时，这使得拥有并行、只读副本的日志变得微不足道。相比之下，写入日志本质上是集中式的，需要所有记录密集的序列编号（在许多情况下也需要重复抑制）。使用两个表数据库表示法的实现可以将复制和写协调委托给底层数据库，尤其是如果底层数据库是全球复制和一致性的，如Google Cloud Spanner 或 CockroachDB。

“重复抑制”在数据库和日志的上下文中，指的是防止相同的数据被存储或记录多次的过程或机制。这对于维护数据完整性、减少存储需求和提高整体系统效率都非常重要。

例如，在日志系统中，如果相同的事件被记录两次，可能会在分析日志时导致混淆或不准确。重复抑制将通过确保每个独特的事件只被记录一次来防止这种情况。

在你之前关于写入日志本质上是集中化处理并且经常需要”重复抑制”的陈述中，意味着系统需要确保不会有重复条目写入日志。这在分布式系统中尤其重要，因为可能有多个源试图将类似或相同的条目写入日志。

当然仅仅存储日志还不够。我们还必须使其对客户端可用。

3.3 Serving a Log

记住，每个使用日志的客户端都对日志的正确操作持怀疑态度。日志服务器必须使客户端能够轻松验证两件事：首先，任何特定记录是否在日志中；其次，当前的日志是否只是之前观察到的早期日志的追加扩展。

为了有用，日志服务器还必须便于根据某种查找键找到记录，并且必须允许审计员遍历整个日志寻找不属于该处的条目。

在日志系统中，审计员的角色是确保数据完整性并符合预期的规则和标准。这意味着他们需要检查日志中的每一项条目，以验证其是否合法、准确，并符合已建立的协议。

当我们说“寻找不应存在的条目”时，指的是搜索任何不应在日志中出现的条目。这些可能是：

重复条目：例如，同一事件被记录了两次。

错误或无效条目：例如，格式错误或包含无效数据。

恶意或欺诈性条目：例如，在网络攻击或欺诈行为中插入。

通过迭代整个日志来寻找这些不应存在的条目，审计员可以帮助保证数据完整性、提高系统可靠性，并防止潜在问题。

为了做到所有这些，日志服务器必须回答五个查询：

Latest()：返回当前的日志大小和最高级别哈希值，并由服务器进行密码学签名以防止否认。

RecordProof(R, N) 返回可以证明记录 R 包含在大小为 N 的树中的证据。

TreeProof(N, N′) 返回证明大小为 N 的树是大小为 N’ 的树前缀部分（即一部分）的证据。

Lookup(K) 如果有匹配查找键 K 的记录索引 R，则返回该索引 R。

Data(R) 返回与记录 R 关联的数据。

3.4 Verifying a Log(cache and storage consistency)

客户端使用前三个查询来维护其已观察到的最新日志的缓存副本，并确保服务器从未从观察到的日志中删除任何内容。为此，客户端会缓存最近观察到的日志大小N和顶级哈希T。然后，在接受数据位B作为记录号R之前，客户端会验证该记录R是否包含在该日志中。如果需要（也就是说，如果R ≥ 缓存的N），客户端会更新其缓存的N、T为最新日志的N、T，但只有在验证最新日志包含当前缓存日志中所有内容之后才这样做。用伪代码表示如下：

validate(bits B as record R):
    if R ≥ cached.N:
        N, T = server.Latest()
        if server.TreeProof(cached.N, N) cannot be verified:
            fail loudly
        cached.N, cached.T = N, T
    if server.RecordProof(R, cached.N) cannot be verified using B:
        fail loudly
    accept B as record R

客户端的证明验证确保了日志服务器正常运行，至少在客户端看来是这样。如果一个狡猾的服务器可以区分单个客户，它仍然可以向不同的客户提供不同的日志，以便受害者看到其他用户或审计员永远不会看到无效条目。但是，如果服务器对受害者撒谎，则由于受害者要求任何后续日志包括其之前所见过内容意味着服务器必须坚持谎言，并永远提供一个包含谎言信息的替代性log。

这使得最终检测更有可能。例如：如果受害者通过代理访问或将其缓存log与其他client的缓存log比较；或者server对应向哪些clients撒谎出错时（即一个server有计划地对不同的client做了不同的谎言，但是某一次操作它发送谎言的对象发生了错误，日志发错了对象）；这种不一致性将很容易暴露出来。

要求服务器签署Latest()响应使得无法否认存在不一致性，除非该服务器声称已完全被攻击。

客户端检查有点像Git 客户端如何维护自己对远程仓库cached副本，在git pull期间接收更新前，该客户端需要先确认远程仓库包括所有本地提交。（绝杀，客户端检查确实很像git pull操作）

但透明log client只需要下载lg N哈希进行验证，而Git需要下载所有cached.N - N的新数据记录。更一般地说，透明日志客户端可以从日志中选择性地读取和认证单个条目，而不需要下载和存储整个日志的完整副本。

3.5~3.9 Tile Sections（切割日志）

如上所述，存储日志只需要简单的、仅附加的存储空间，这个空间是总日志大小的线性关系，并且服务或访问日志只需要网络流量在总日志大小的对数级别。这完全是一个合理的停止点（并且在RFC 6962中定义的证书透明度就在这里停止）。然而，有一种有用的优化既可以将哈希存储减半，也可以使网络流量更易于缓存，而实现复杂性只会稍微增加。这种优化基于将哈希树分割成瓦片（tiles），就像Google Maps将地球分割成瓦片一样。

这部分是存储部分的优化，教授说先不用看这块。

3.10 Summary

综合来看，我们已经了解了如何发布一个透明的（防篡改、不可变的、只能追加的）日志，具有以下特性：

客户端可以使用O(lg N)数量级的下载字节来验证任何特定记录。
客户端可以使用O(lg N)数量级的下载字节来验证任何新日志是否包含旧日志。
即使对于大型日志，这些验证也可以在约8 kB每个的3个RPC中完成。
用于验证的RPC可以很好地进行代理和缓存，无论是出于网络效率还是可能出于隐私考虑。
审计员可以遍历整个日志寻找错误条目。
写入N条记录定义了N个哈希树序列，在其中第n棵树包含2^n^ – 1个哈希，总共有N^2^个哈希。但是不需要存储N^2^个哈希，整个序列最多可以压缩到2 N个哈希，并且最多需要lg N次读取才能从特定树中重构特定哈希。这块有点抽象，需要后续进行进一步的理解。
您提到的情况是在构建哈希树（通常是Merkle树）时的一种特定情况，其中每个哈希树包含2^n^ - 1个哈希值，总共有N棵这样的哈希树，因此总共有N^2^个哈希值。

让我们更详细地描述这个情况：
1. 有N个哈希树，每个树的深度为n（也就是树中包含n层节点）。
2. 在每个哈希树中，根节点只包含一个哈希值。第二层有2个节点，第三层有4个节点，以此类推，直到第n层有2^(n-1)^个节点。
3. 由于每个哈希树的深度为n，所以每棵树包含的节点总数为2^n^ - 1。这是因为每层的节点数是前一层的节点数的两倍，然后减去1（因为根节点不包含在层级计数中）。
4. 如果有N棵这样的哈希树，每棵树都包含2^n^ - 1个节点，那么总共有N * (2^n^ - 1)个哈希值。
这些 2N 哈希值本身可以压缩为 1.06N 哈希值，代价是可能读取 8 个相邻哈希值以从 2N 中重建任何一个哈希值。

总体而言，这种结构使得日志服务器本身基本上是不受信任的。它不能在未被检测到的情况下删除观察到的记录。它无法对一个客户撒谎，除非该客户永远处于另一条时间线上，因此这可以很轻易的通过与另一客户进行比较来轻松检测该客户的日志是否是有问题的。

该日志本身也容易被代理和缓存，因此即使主服务器消失了，副本仍然可以继续提供缓存日志服务。最后, 审计员们可以检查并移除那些不应存在在log里面的条目, 这样实际上log内容就能够异步地从其使用中进行核实。

后面的Further Reading和Appendix部分目前不需要看。

back.