“Hi，这是小5自学算力大集群相关知识的第15篇笔记。从这期开始的3期，我们将开始对区块链技术进行简单了解。本次就让我们从证书透明度与分支一致性说起。”
摘要
“证书透明度” （Certificate Transparency）
如果我们想要构建一个开放的系统，那么很可能找不出一个被所有人普遍信任的权威机构，大家愿意信任它来运行系统或保护它。每个人在某种程度上都可能对其他人持有相互猜疑的态度。因此，在设计分布式系统时，任何类型的互联网广域开放系统都将信任与安全视为顶级系统问题。
构建开放系统的最基本问题在于，当我与另一台计算机或另一个人通信时，是否正在与正确的另一台计算机或网站进行对话。证书透明度正是保证上述问题的其中一个手段。
它所做的大部分工作是确保所有相关方都能看到关于证书的相同信息。这也是一个一致性问题。此外，证书透明性是少数非加密货币应用中采用类似区块链设计的一种。
- 发展历史
1995年之前，人们担忧一种被称为“中间人攻击” (Man in The Middle) 的特定攻击方式。
用户使用浏览器与互联网进行通讯，在访问网站时一般会经过 DNS 服务器进行解析对应的IP地址， DNS 服务器回复相应的IP地址后，便连接到该IP地址，如访问 Gmail。所谓“中间人攻击” ，即有恶意之人设立一个外观酷似 Gmail 服务器的网页服务器，诱导用户输入登录信息和密码。然后，攻击者可能会截获用户的 DNS 数据包，或者猜测何时发送了 DNS 数据包，并伪造一个回复，该回复提供的不是真实 IP 地址或真正的 Gmail.com 服务器，而是攻击者伪造计算机的电子邮件地址。然后用户的浏览器，并非与 Gmail 通信，而是在用户不知情的情况下，实际上与攻击者的计算机进行通信。而攻击者的计算机可以将该信息转发至真实的 Gmail 登录页面。这样一来，如果你遭遇了这种中间人攻击，攻击者的计算机就能记录下你的密码和电子邮件，而你却浑然不觉。
在证书、SSL 和 HTTPS 出现之前，确实没有针对此类攻击的有效防御手段。在90年代中期，人们提出了使用 SSL（或称 TLS）的证书概念，这就是在使用 HTTPS 链接时所采用的安全协议。关键点在于 Gmail.com 将拥有一对公钥和私钥。因此，我们会有一个只有 Gmail 知晓的私钥存放在其服务器中。当用户请求链接时，为了验证当前确实在与 Gmail 对话，用户将要求 Gmail 证明它确实拥有 Gmail 的私钥。
当 Gmail 设置其服务器时，会与证书颁发机构联系。可能是通过电话、电子邮件或其他方式，并表示：我想要一个针对 DNS 名称 gmail.com 的证书。证书颁发机构随后会尝试验证。如果确有此需求，证书颁发机构将向 Gmail.com 提供一份证书。这份证书的核心内容包括：网站服务器的名称、该服务器的公钥，以及使用证书颁发机构的私钥对这份证书进行的签名。这可以被视为一个自包含的断言，通过验证签名来检查，即证书颁发机构对 Gmail.com 的公钥确实是此公钥的声明。
在 Gmail.com 服务器上，我们只需保留证书的一个副本。若用户通过 https 连接至 Gmail 服务器，其首要操作便是向他发送此证书。接着，浏览器会发送一些信息，例如如一个随机数给服务器，并要求其使用私钥对其进行签名。然后，浏览器可以使用证书中的公钥来验证这个随机数，即其随机数，是否确实由与证书中的公钥相关联的私钥签名。由于恶意服务器并没有 Gmail 证书的私钥，所以无法对用户发来的随机数进行正确的签名，这样一来使得中间人攻击变得相当困难。但随着时间的推移，有一些证书颁发给了那些只想窥探他人流量并发起中间人攻击的人，而他们也确实发起了中间人攻击。
这尤其令人困扰，因为难预防，毕竟证书授权机构众多，并非所有机构都能做到尽善尽美。那么，针对这一问题我们能做些什么呢？
一种可能性是建立一个单一的在线数据库，存储所有有效的证书，以便当浏览器与网站联系时，网站会提供一个证书，该证书可能有效也可能无效。那么，或许可以设想浏览器会联系全球看效的证书没据库，询问：这真的是一张证书吗，还是由流氓证书颁发机构发放的伪造证书？
但这样做法存在诸多问题。其中一个问题是，任何人如何区分有效的、正确颁发的证书与伪造的证书，因为在通常情况下用户不并不清楚谁是 DNS 名称的合法拥有者。此外，还需要允许证书持有者更换证书颁发机构或更新其证书，或者他们可能丢失私钥并需要新的证书来替换旧证书，因为使用了新的公私钥对。因此，人们的证书总是在不断变化。最后，即便从技术上讲有可能区分正确的证书与伪造的证书，但并不存在一个被所有人信赖的实体来执行这一区分。
然而，证书透明性的本质在于，它正竭尽所能朝着建立一个有效且可信赖的证书数据库迈进。
- 证书透明度的一般策略
证书透明性的特点在于它是一个审计系统，因为要判断某人是否拥有某个名称，其难度之大几乎不可能仅凭主观决定。证书透明性并非一个防止不良事件发生的构建系统，它要求能够立即察觉到某证书是伪造的。也就是说，它旨在使所有信息公开，以便关注此信息的人可以进行检查。它仍会允许人们发放虚假证书，但将确保这些证书公开，让所有人都能看到，包括拥有该名称的人，即虚假证书中出现的那个名称的所有者。因此，这解决了证书颁发机构可以签发虚假证书，而无人知晓的问题。所以它具有一种审计的特性，而非预防的特性。
通常情况下，当首次设置 Web 服务器时，他们会向数百个 CA （证书颁发机构）之一请求证书。而证书颁发机构会将该证书发回给Web服务器。同时，证书授权机构会将证书副本或等效信息发送至证书透明度日志服务器。在实际系统中，将会有多个独立的证书透明度日志服务器。该服务一直在维护一个日志，记录了所有已颁发的证书或证书颁发机构告知它的所有证书。当它收到一个新的证书时，会将其追加到其日志中。因此，一段时间后，这个日志可能包含数百万个证书。
现在，当浏览器，或者某个人想要访问一个网站时，他们会建立一个 HTTPS 连接 Gmail ， Gmail 会向他们发送一个证书，浏览器将把这个证书发送给证书日志服务器并询问：这个证书是否在日志中？证书日志服务器的回答将是肯定或否定，即证书是否存在于日志中。如果进行了缓存，浏览器将会继续使用它。
虽然它记录在日志中，但这并不意味着它就不是虚假的。因为任何证书颁发机构，包括那些恶意或管理不善的机构，任何证书颁发机构都能够将证书插入日志系统，从而可能诱使用户使用。实际情况是，除非证书在日志中，否则任何浏览器都不会使用它。与此同时， Gmail 将运行 CT 系统所称的监控程序。我们暂且假设每个网站都有一个与之关联的监控器。这个监控器还会定期与证书日志服务器通信。并请求：请给我一份您的日志副本，或者请给我自上次请求以来您日志中新增内容的副本。这意味着监视器将会逐渐积累，它将能够识别日志中存在的每一个证书。由于该监控器与 Gmail 关联，它知晓 Gmail 正确的证书是哪一个。因此，如果某个恶意证书颁发机构为 Gmail 颁发了一个并非 Gmail 本身所请求的证书，那 Gmail的监控程序会在证书日志中偶然发现它。
当然，恶意证书颁发机构无需将其证书发送给证书日志系统。在那种情况下，当浏览器可能不小心连接到攻击者的服务器，而攻击者的服务器提供了伪造的证书。如果该证书未被记录在案，浏览器便不会信任它，并会终止连接，因为它不在记录之中。因此，日志在某种程度上起到了强制作用。因为浏览器要求证书必须存在于日志中，所以日志强制所有证书都必须公开。但这个方案在很大程度上取决于浏览器看到与监控器相同的日志内容。
然而，我们无法确定系统中的任何组件是否可信。因此，我们需要构建的是一个日志系统，即使日志操作员可能不合作、不可信，我们仍能确保，或至少知道是否并非如此，即浏览器和监控器所看到的是相同的日志内容。如果浏览器使用了日志中的证书，拥有该名称的监控器最终将会看到它。
我们需要构建的是一个仅可追加的日志系统，以确保它无法向浏览器展示证书后，在监控器察觉之前将其删除。不存在分叉的情况，即我们不希望日志系统基本上保留两份日志，一份展示给浏览器，另一份展示给监控器。但其仍是不可信的，我们不能确保证书服务器是正确的。日志系统所需的关键特性，不仅仅是日志服务器本身，而是包括日志服务器及其各种校验机制在内的整个系统，必须防止数据的删除。
- 证书透明度方案的一些细节
第一步是被称为 Merkle 树的东西。日志服务器被期望在日志基础之上构建的内容。这个概念是指实际的日志本身，它是一系列证书的序列，如证书一、证书二，据推测是按照证书颁发机构要求将证书添加到系统的顺序排列的。
我们并不希望浏览器必须下载整个日志。因此，我们需要工具来使日志系统能够向浏览器发送可靠的摘要，或明确无误地概括日志内容。
基本方案是，日志服务器将使用加密散列来对日志中的完整记录集进行散列处理，以生成单个加密散列值，该散列值通常约为256位长。因此，加密哈希函数概括了日志的内容。其具体实现方式是基于一种树状结构的双元素组合，其中我们总是在最底层（第0层）将成对数字进行哈希运算。
每个日志条目都有一个哈希值。因此，在基础层面上，我们将拥有每个日志条目、每个证书的哈希值，然后将对成对的数据进行哈希处理。在下一层级，我们将对这两部分分别进行哈希处理，并将结果相互拼接，即这两个哈希值的拼接。之后，在最高层级上，将拥有一个哈希。我们在做的是对这两个哈希的拼接进行哈希处理。而这个单一的哈希值在这里是一种明确的替代，代表完整的日志。
这些加密散列函数（如SHA-256）的特性之一是，要找到两个输入使得散列函数产生相同的输出，是不可行的。这意味着，如果你告诉某人哈希函数的输出结果，你只能找到唯一的一个输入，能够产生那个输出。因此，如果日志服务器以这种方式对日志内容进行哈希处理，那么只有这一特定序列的日志记录才能生成该哈希值。我们有充分的保证，日志服务器无法找到另一个日志，该日志产生的最终树哈希与这一系列日志条目相同。
这就是 Merkle 树的大致结构。将其顶端称为带签名的树头。在实际操作中，日志服务器会获取位于树顶部的哈希值，并用其私钥对其进行签名，然后将签名后的结果提供给客户端、浏览器和监控器。重点是，一旦日志服务流向浏览器或监控器展示了一个特定的签名树头部，它就承诺了某些特定的日志内容，因为它将无法再生成其他能产生相同哈希值的日志内容。
如何扩展目志，以及如何为任意数量的记录添加日志记录？
我们假设日志始终以2的倍数增长，这虽然不切实际，但有助于简化解释。当证书机构发送新证书以添加到日志时，日志服务器将等待，直到它拥有的新记录数量与旧记录数量相等，然后生成另一个树头。实现这一过程的方式是，为了扩展日志，日志服务器会等待收集到另外四条记录，然后像之前一样两两进行哈希处理，接着将生成个新的树头，该树头是这两个哈希值串联后的哈希结果。
这意味着随着时间的推移，日志服务器的日志不断增长，它会生成一系列越来越高、越来越合的树头，随着日志的增长，这个序列也在不断提升。
利用 Merkle 树来强制日志服务器证明其在维护的日志中关于某些特定事项的证明能力。
一种证明方式被称之为“包含证明”。就是浏览器在接收到 Web 服务器刚刚提供的证书时所需进行的验证过程，即确认该证书是否确实存在于日志中。它会请求证书，并询问日志服务器：“这里有一个证书，您知道它是否在您的日志中吗？”证书服务器将返回一个证明，不仅证实该证书存在于日志中，还明确指出其在日志中的位置。当然，浏览器需要这个证明，因为它不希望使用一个不在日志中的证书。如果证书不在日志中，监控器就无法看到它，我们将无法防范证书伪造的风险。这是对日志服务器最终的制约手段，即浏览器内部拥有一份可接受的日志服务器列表。这些证明将成为证据的一部分，用以在某个日志服务器表现出恶意行为时，将其从日志系统中移除。
我们假设浏览器已拥有正确的签名树头，并正在请求证明。为了简化说明，我们将讲解如何处理包含两个记录的日志。浏览器实际上拥有一个特定的签名树头（signed tree head）。假设位于已签名树头下的正确日志是由特定证书A和B组成的二元素日志A、B。这意味着正确的 Merkle 树对应于此，由A和B的哈希值组成。然后，签名树头实际上是A的哈希值与B的哈希值拼接后的哈希值，假设这就是日志服务器实际提供给客户端的证书的签名树头。
因为客户端只知道这个值，即最终的哈希值，实际上并不了解日志中的内容。如果浏览器请求证明 A存 在于日志中，那么日志服务器能返回的证明就是 A 在日志中的证明，即 A 在日志中的位置以及日志中其他元素的哈希值。结果返回0和B的哈希值。这些信息足以让客户端确信A确实位于位置0。因此，浏览器现在知道了哈希值 A 和哈希值 B ，它可以将它们一起进行哈希处理，执行这个哈希操作，并查看结果是否与其所拥有的签名树头相同。在较大的日志中，如果需要证明 A 确实存在，只需拥有从每个哈希的另一分支到签名树顶端的哈希序列即可。
如果日志服务器为浏览器伪造了一份完全不同的日志，这份日志与任何其他人的日志都不一样，只包含恶意日志服务器想要诱骗该客户端相信的虚假证书。需要怎么办？
通常情况下，事情的发展是这样的。我们会拥有一个浏览器，它一直能够看到正确的日志，直到某个时刻，有人试图对其进行攻击。此时浏览器仍然能够访问其通常看到的所有网站。同时还能使用一种包含虚假证书的不同日志，这种日志是日志服务器想要欺骗特定客户端，即那个受害浏览器的。这是一种分叉攻击，或者更广泛地说，是双重签发（equivocation）。
之所以将这种攻击称为分叉攻击，是因为如果我们暂时忽略 Merkle 树，仅考虑日志，通常该日志中已存有数百万份证书，且每个人都已见过日志的开头部分。在某个时间点，我们希望发起攻击，诱使我们的目标使用某个伪造证书B，但我们不希望向其他人展示B，当然也不包括监控者。因此，我们将创建另一个日志，它照常继续记录并包含新的提交，但绝对不包含伪造的证书B。这看起来就像是一个分叉，因为监控显示的主日志在某种程度上偏离了主干，而我们现在构建的这个日志，特别是用来诱骗受害者的，则属于另一个分叉。
这里发生的情况是，那些未受攻击的监视器和人将会看到一个特定的签名树头。假设已签署的树头为1。而受害者将看到其他某个已签名的树头，它与恶意服务器向监控器展示的签名树头不同。如果浏览器和监视器能够交流信息，它们或许能立即意识到所观察的是不同的“树”。因此，我们需要做的关键事情是让系统中的不同参与者能够比较签名树头。而证书透明性对此有一个称为“流言”（gossip）的规定。其实质是，所有参与者都会将自己最近见过的已签名树头放入一个大型共享池中，供大家检查。以试图确定是否存在不一致的已签名树头，这些不一致显然表明了分叉的日志。
那么问题来了，给定两个签名树头，我们如何判断是否有证据表明日志已被分叉？
使得这一问题变得困难的是，即便日志尚未被分叉，随着其记录的增加，新的签名树头将不断成为当前状态。或许在这个时间点，签名树头1是日志的合法签名树头，随后叉添加了一些证书，签名树头3成为了日志的正确头部，接着是签名树头4。所以需要区分以下情况：一个已签名的树头确实描述了一个前缀，即一个日志是另一个由已签名树头描述的目志的前缀，因为这正是合法的情况，即，这两个已签名的树头虽然不同，但第二个确实涵盖了第一个。
我们希望区分两种情况：两个不同的带符号树头，其中任何一个都不描述另一个日志的前缀。所以现在的规则是，我们给定了两个有符号树头，H1 和 H2，我们的问题是：H1的日志前缀是否存在？如果答案是否定的，那就意味着日志服务器已经将我们分叉，并且正在对某一部分隐藏某些信息。
随着日志的增长，我们所看到的是一系列树头的标记，每个标记随着日志大小的翻倍，生成新的哈希值，而该哈希函数的结果是下一个签名树头部的输入之一。对于任意两个合法的签名树头，若 H1 的日志是 H2 的前缀，则意味着可能此处 H1 为前者，H2 为后者，且它们之间将存在这种关系。即 H2 是通过取 H1，与某些其他元素进行哈希运算，再与另一元素哈希，如此反复直至得到 H2。这意味着，如果浏览器或监控器要求日志服务器证明 H1 的日志确实是 H2 日志的前缀，日志服务器需要提供的是从 H1 到 H2 路径上每个签名树顶端哈希的另一侧的序列。经过计算如果与 H2 相符，那么这就是 H2 是 H1 后缀的一个证明，否则日志显然试图使你分叉。
该方案旨在浏览器将定期与某个中央存储库或一组中央存储库进行通信，并向已签名的树头池贡献它们最近从目志服务器看到的已签名树头。同时，浏览器也会定期从其他浏览器所见的已签名树头池中随机抽取元素，并随机选择这些元素。存在多个这样的收集池，由不同的人运行，以便在其中一个作弊时提供证明。然后，无论浏览器从池中随机抽取哪个已签名树头，它都会要求目志服务器为此对已签名树头生成日志一致性证明。还有一个地方需要这些一致性证明，不仅仅是在传播信息时，其实在浏览器的日常运行过程中也同样需要。
难点在于，假设浏览器看到的是与所有人一致的日志版本，但此时一个日志服务器试图诱使它使用这个伪造的证书。在下一次浏览器（并未意识到任何异常）与日志服务器通信时，日志服务器可能会表示：“哦，这里有了一份新日志，包含了许多新内容。” 这里是当前新日志的有符号树头。如果浏览器接受了，那么现在完全失去了任何出错的证据，因为现在浏览器正在使用与其他所有人相同的树结构。
我们期望的是，如果日志服务向浏览器显示了某个特定的日志，那么浏览器就不能被欺骗而切换到其他日志。即确保浏览器仅能看到对其已见日志的严格扩展。并且不会简单地切换到一个与浏览器之前所见日志不兼容的日志。我们正在寻找的特性实际上被称为“分支一致性” (fork consistency) 。
“分支一致性” (fork consistency)
“分支一致性” (fork consistency) 所指的是，若浏览器已被分叉至与其他人不同的分支，则它必须保持在那个分支上，且绝不应有能力切换回主分支。原因在于我们需要保留这个不良的签名树头及其后继者。以便当浏览器参与 gossip 协议时，它所贡献的签名树头是其他人所没有的，并且无法通过日志一致性证明来证明其兼容性。
每当日志服务器告知浏览器：“这里有一个新的更长的日志的签名树头” ，浏览器将要求，在日志服务器提供证明新签名树头描述的是旧签名树头的后缀的日志一致性证明之前，不会接受这个新的签名树头。
当然，如果日志服务器已经分叉了浏览器，并且它保持浏览器在同一分叉上，那么它就能够生成证明。这其实是在自掘坟墓，因为它正在生成越来越多的签名树头，这些最终都会被 gossip 协议捕捉到。且这样无法通过删除分支来抹去证据。
这个系统，这些日志一致性证明提供了对于一致性的保障以及在一致性基础上加上 gossip 机制，并要求对于通过其找到的签名树头进行日志一致性证明。二者相結合。使得所有参与者看到相同日志的可能性大大增加，并且如果他们看到的日志不一致，也能通过日志一致性证明的失败来检测到这一事实。
尽管该系统大体上是相当去中心化的，但仍存在着众多的证书颁发机构和证书透明度日志服务器，而浏览器供应商却寥寥无几。这使得浏览器供应商处于一个相当强势的地位。由于它们维护着可接受的证书颁发机构列表和日志服务器，因此它们确实拥有很大的权力。
总结：每个人都看到相同的日志，即使其中一些参与者是恶意的。要么每个人都看到相同的日志，要么他们能从失败的证明中积累证据，表明事态有些蹊跷。由于使用这些证书的浏览器和运行监控的 DNS 名称所有者都能看到相同的日志，因此监控系统能够检测到问题，从而使得浏览器即便无法实际检测到伪造的证书，也能至少确信，如果存在伪造证书，监控系统将会发现它们，并可能将其列入撤销名单。
另一点是：如果无法找到阻止不良行为的方法，或许可以构建一个至少可用的系统，它依赖于审计而非预防措施。也就是说，能够在事后检测到不良事件。
以上内容来自对 MIT 《分布式系统 6.824》的学习笔记，在此特别声明。