这篇博客文章使用MathJax渲染数学。您需要启用JavaScript才能使MathJax正常工作。
在最近的一些研究中，海蒂和我需要解决以下问题：假设您要在两个节点之间同步哈希图，例如Git存储库。在Git中，每个提交都由其哈希标识，并且一个提交可能包括以前的提交的哈希值（如果是合并提交，则一个提交可能包含多个哈希）。我们想弄清楚两个节点相互发送的最小提交集，以使它们的图相同。
您可能会想：这不是一个解决的问题吗，每次执行git pull或git push时，Git都必须执行此操作！是的，有些情况很简单，但有些情况则比较棘手。 Git使用的算法并不是特别有据可查，无论如何我们都认为我们可以做得更好。
例如，假设我们有两个节点，每个节点都有以下两个哈希图之一（圆圈是提交，箭头表示一个提交引用了另一个哈希），蓝色部分（提交A及其左侧的提交）是这两个图之间共享，而暗灰色和浅灰色部分仅存在于两个图之一。
我们要协调两个节点的状态，以便一个节点发送所有深灰色的提交，另一个节点发送所有浅灰色的提交，并且最后都得到下图：
我们如何有效地找出两个节点需要发送给彼此的提交？
首先，用一些术语来说，如果B引用了A的哈希，或者如果B的哈希引用链通向A，则提交A是提交B的前身。如果A是B的前身，那么B是a最后，将图的标头定义为没有后继的提交。在上面的示例中，标头是B，C和D（这与Git定义HEAD的方式略有不同）。
如果是“快进”情况，对帐算法很容易：也就是说，如果一个节点的头提交了另一个节点已经拥有的提交。在这种情况下，一个节点向另一个节点发送其头的哈希，而另一个节点向另一个节点发送答复所有作为第一个节点头的后继对象的提交。但是，在上面的示例中，情况更加棘手，另一个节点不知道一个节点的头B和C，而第一个节点同样不知道头D。
为了调和两个图，我们想弄清楚哪些提交是两个图的头的最新公共先行者（在示例中也称为公共祖先，在示例中标记为A），然后节点可以相互发送所有是共同的前任的继任者。
第一次尝试，我们可以尝试：两个节点互相发送自己的头；如果那些包含任何未知的前任哈希值，它们会请求这些哈希值并重复执行，直到所有哈希值都解析为已知的提交为止。这样，节点逐渐从头到通用的前任工作，这是可行的，但是如果图形包含很长的图则速度很慢提交链，因为所需的往返次数等于从头到共同的前任的最长路径的长度。
Git使用的“智能”传输协议本质上是这样工作的，只是它一次发送32个散列以减少往返次数。为什么32？谁知道。这是一个折衷方案：发送更多的哈希值以减少往返次数，但每个请求/响应都更大。大概他们认为32是延迟和带宽之间的合理折衷。
最新版本的Git还支持实验性的“跳过”算法，可以使用fetch.negotiationAlgorithm配置选项启用该算法。该算法允许跳过某些提交，而不是在每次往返过程中前进一定数量的前任程序。每次往返的跳跃大小都类似于斐波那契数列（即成指数增长）。这将往返次数减少为\（O（\ log n）\），但最终超越了通用的前任，因此协议可能最终不必要地传输了另一个节点已经拥有的提交。
在我们今天可以在arXiv上提供的新论文草案中，我和海蒂（Heidi）提出了另一种算法来执行这种调节，如果您知道Bloom过滤器的工作原理，这很简单。
除了发送其头部的哈希值之外，每个节点还构造一个Bloom过滤器，其中包含它知道的提交哈希值。在我们的原型中，我们为每个提交分配10位（1.25字节）。这个数字可以调整，但是请注意与每次提交都发送完整的16字节（对于SHA-1，由Git使用）或32字节（对于SHA-256，这是更安全的）哈希相比，它要紧凑得多。从上次协调状态到特定节点的时间开始，然后Bloom过滤器仅需要包含自上次协调以来添加的提交。
当一个节点收到这样的Bloom过滤器时，它会检查自己的提交哈希，以查看它们是否出现在过滤器中。任何哈希没有出现在Bloom过滤器中的提交及其后继，都可以立即发送到另一个节点，因为我们可以确保其他节点不知道这些提交，对于哈希确实出现在Bloom筛选器中的任何提交，其他节点很可能知道该提交，但是由于误报，其他节点很有可能节点实际上不知道那些提交。
收到所有未在Bloom筛选器中出现的提交后，我们检查是否知道其所有前任哈希值，如果缺少，则使用与之前相同的图遍历算法在单独的往返中请求它们。假阳性概率的工作方式，需要n次往返的概率随n的增长呈指数下降。例如，您可能有1％的机会需要两次往返，有0.01％的机会需要三次往返，有0.0001％的机会需要进行四次往返，等等。几乎所有对帐都在一次往返中完成。
与Git使用的跳过算法不同，我们的算法永远不会不必要地发送另一端已经拥有的任何提交，并且即使对于较大的提交历史记录，Bloom过滤器也非常紧凑。
在本文中，我们还证明了该算法即使在任意数量的恶意节点存在的情况下也允许节点同步其状态，从而使其不受Sybil攻击的影响，然后继续证明一个定理，该定理表明了哪些类型的应用程序可以和不可以以Sybil免疫方式实施，而无需任何Sybil对策，例如工作量证明或对许可区块链的集中控制。
所有这些都与本地优先点对点应用程序直接相关，在这些应用程序中，运行在不同设备上的应用程序需要同步其状态，而不必彼此信任或依赖任何受信任的服务器。我认为这也与使用哈希图，但我对此并不了解。因此，同步Git提交历史只是许多可能的用例之一–我刚刚使用了它，因为大多数开发人员至少会对它有所了解！
该算法和定理的详细信息在论文中，因此在这里我不再赘述。相反，我将简要提及一些未纳入论文的有趣事情。
您可能会想知道一件事：我们不能只将提交哈希值截断为10位并发送，而不是创建每个提交10位的Bloom过滤器，这将使用相同数量的网络带宽，并且看起来像它应该是等效的。
但是，事实并非如此：Bloom过滤器的性能远优于截断的哈希值。我将使用少量概率论来解释原因。
假设我们有一个包含\（n \）个不同项的哈希图，并且我们希望每个项目使用\（b \）位（因此数据结构的总大小为\（m = bn \）位）。使用截断的哈希，每个\（b \）位哈希有\（2 ^ b \）个可能值，因此，给定两个独立选择的，均匀分布的哈希，它们相同的概率为\（2 ^ {-b} \）。
如果我们有\（n \）个均匀分布的哈希，则它们与给定的\（b \）位哈希值都不同的概率为\（（1-2 ^ {-b}）^ n \）。因此，正概率是给定\（b \）位哈希等于一个或多个\（n \）哈希的概率：
另一方面，使用布隆（Bloom）过滤器时，首先将所有\（m \）位设置为零，然后对于每个项目，将\（k \）位设置为1。 ，给定位为零的概率为\（1-1 / m \）。因此，在执行\（kn \）位设置操作后，给定位仍为零的概率为\（（1-1 // m）^ {kn} \）。
当我们检查某个项目的\（k \）位并且它们全为1时，布隆过滤器的误报为肯定，即使该项目不在集合中也是如此。
从这些表达式中并不能看出这两者中哪个更好，所以针对不同数量的项\（n \）和参数\（b = 10 \），\（ k = 7 \），\（m = bn \）：
对于布隆（Bloom）过滤器，只要我们根据项目数量成比例地增加过滤器的大小（此处每个项目有10位），假阳性概率就几乎保持恒定在0.8％左右。尺寸的行为会更糟，并且，如果出现超过1,000个项目，则误报率超过50％。
这样做的原因是：使用10位截断的散列只有1,024个可能的哈希值，如果我们有1,000个不同的项，则已经采用了1,024个可能的值中的大多数。概率常数，随着项目数的增加，我们将不得不为每个项目使用更多的位，因此数据结构的总大小将比项目数的线性增长快。
如此看来，Bloom过滤器的工作原理与它们一样出色，每项仅使用固定位数！
上面给出的Bloom过滤器误报公式是经常被引用的公式，但实际上并不完全正确。确切地说，这是确切的误报概率的下限（开放获取论文）。
出于好奇，我写了一个Python脚本来计算被截断的哈希的误报概率，使用近似公式的Bloom过滤器和使用精确公式的Bloom过滤器。幸运的是，对于我们感兴趣的参数值，近似值和精确概率很小。要点还包含一个Gnuplot脚本来生成上面的图。
Peter建议Cockoo过滤器的性能可能比Bloom过滤器更好，但我们尚未对此进行研究。说实话，Bloom过滤器方法已经可以很好地工作了，而且它是如此简单，以至于我不确定增加更复杂的数据结构的复杂性确实是值得的。
今天就这些了。我们的论文在arxiv.org/abs/2012.00472。希望您发现这很有趣，如果您最终使用该算法，请告诉我们！
要在我写新东西时得到通知，请在Twitter上关注我或输入您的电子邮件地址：
我不会将您的地址提供给其他任何人，不会向您发送任何垃圾邮件，您可以随时退订。