作者：Nadav Kohen
来源：https://suredbits.com/how-neutrino-works/ & https://suredbits.com/how-neutrino-works-part-2/
之前我们已经介绍了 Neutirno 是什么以及作为比特币的一种新型轻客户端，它能为钱包带来什么。在本文中，我们会深入了解 Neutrino 的工作原理。
BIP158
Neutrino 由 BIP 157 和 BIP 158 详述。BIP 158 详细说明了 Neutrino 所用的数据结构，这种数据使得客户端可以隐私地探测出他们需要下载的区块数据，也是本篇的重点。BIP 157 定义了 Neutrino 客户端所用的 P2P 消息，以及这些客户端和他们的服务端应该做什么操作。BIP 157 是本系列下一篇文章的重点（编者注：与本篇合二为一）。
所谓的过滤器（filter），就是一种数据结构，它有一个主要的方程叫做 “匹配方程（matching）”；输入一些数据，该函数会返回 “正确（True）” 或者 “错误（False）”。给出一组数据，我们就可以创建出一个过滤器，对任何来自该组数据的输入返回正确，而对其余一切数据返回错误。最简单的过滤器就是把所有的数据都存在一个列表里，然后按顺序遍历列表、检查是否有元素与输入数据相匹配。概率性过滤器（probabilistic filter）跟普通过滤器非常相似，只不过，它有一定的小概率 —— 称为 “容错率” —— 在数据并不来源于建构过滤器的初始集合时也依然返回正确。这个概率是可以配置的，但 Neutrino 节点当前使用的容错率是 1/784931。
虽然设定容错率有其缺点，但好处也是巨大的：概率性过滤器与原始数据相比，通常都小得多。它们的效率一般都非常高。这些特点使得它们非常适合用于比特币轻客户端。（冷知识：Bitcoin Core 软件现在也在使用这些过滤器作为全节点的过渡性数据结构，用来检查特定的数据是否存在于一个区块中。）
BIP 158 定义了一种新的（比特币）概率性过滤器，它使用 Golomb 编码的哈希值集合（后文有详情）。大体上来看，它用在 Neutrino 节点中的方式是：对每个区块，都确定性地创建出一个这样的过滤器；一个区块过滤器的体积大概是其源区块的十分之一，并且可以匹配用在区块的输入和输出中的所有脚本公钥（理解成地址）；然后，这些过滤器由服务端（全节点）发送给客户端（Neutrino 节点），后者可以检查自己关心的地址在不在其中。如果结果是阳性，客户端就可以下载完整的区块并作进一步的验证。
这下，你应该对这些过滤器的用法有初步概念了。如果你不熟悉哈希函数，建议你先看看这份简介再回来阅读本文。
BIP 158 过滤器使用 Siphash 函数，它会接收一个键（key）和一些数据，然后输出一个 64 位的伪随机数。然后我们把这个哈希值压缩到一个小得多的范围（数据集的大小 * 784931）。Siphash 函数是专为速度优化的。不过，由于输出只有 64 位（压缩之后会变得更小），这个哈希函数不是抗碰撞的，最终其容错率为 1/784931。而在 Neutrino 中，容错的情形就是被查询的数据与集合中的某个数据并不相同但有一样的哈希值。
记住了这些，下面就来看看 BIP 158 区块过滤器是如何构造的：首先，对所有相关的区块数据运行 Siphash 函数并使用区块哈希值为键。这就既保证了确定性，又保证了每个区块都会改变键。其次，以升序排列这些哈希值。然后，计算这些哈希值的差值。假设 Siphash 函数的行为会像一个哈希函数的理想情形，我们预期这些插值的分布接近于几何分布。这使得这些差值成了 Golomb-Rice 编码的理想目标，这种编码技术是为了压缩几何分布的值而优化的。稍后我会详细说明这一点，但现在，我们继续讲：下一步就是压缩这些值。做完了上面四个步骤之后，我们现在有了一个紧凑的区块过滤器，可以发给 Neutrino 轻客户端了！
要想在一个区块过滤器中发现有没有我们想找的数据，步骤就刚好反过来：首先，解码以 Golomb-Rice 编码的数据集。然后，通过累加差值获得所有哈希值。如果你要找的正是其中某个，你实际上并不需要解码整个集合，因为你可以按顺序一边解码一边累加，直到你得出匹配的数据或者处理完整个集合（因为它是有个有序的集合）。而且，更好的是，如果你要找多个匹配数据，所需花费的时间应该会跟你先对目标排序然后一次性遍历过滤器的时间一样长。
BIP 158 Golomb-Rice 编码
使用 BIP 158 指定的参数的 Golomb-Rice 编码方法如下：找出你要编码的数 —— 在这里就是两个哈希值的差值 —— 然后求出它除以 2 ^ 19 的商和余数，也就是找出 q 和 r 使得 q * 2^19 + r 等于你要编码的数。这个计算实际上是非常快的，因为我们的数都是二进制的。只需要在被除数的（从后面开始算的）第 19 位把它分成两半即可（前半部分为 q，后半部分为 r），后面的 19 位就是余数；就像在十进制下，一个数除以 10 ^ 19 的时候，它后面的 19 位就是余数一样。下一步，以一元形式重写 q（q 本身就非常小）（一元形式在骑缝号中很常见，例如 7 写作 1111111），后面跟上一个 0，再跟上余数 r。这个编码使我们可以按顺序写下每个哈希值，而无需隔开它们、注明它的长度。我们可以一直读取数字，直到撞上一个 0，然后再读后面 19 位，就好。
举一些简单的例子。假设我们想编码两个二进制数：011 | 0110000011010110001 和 100|0011010011010001110 （数字中间的竖杠后面就是 19 位）。
我们可以将商 “011” 解读为 “3”，然后以一元形式重写并接上一个 0，就是 “1110”，再接上余数 “0110000011010110001”，就编码好了。第二个数也作同样的处理，商 “110” 在二进制下表示 4，于是我们重写成 “1111”，接上 “0” 再接上它的余数，就成了结果 “111100011010011010001110”。
以 Golomb 编码两个数的最终结果是 “11100110000011010110001111100011010011010001110”。
看起来有一堆的 1 和 0，但实际上，它比正常情况下保存在计算机中的数要紧凑得多；正常情况下，我们保存一个数的时候要在前面填充很多个 0 ，使之成为 64 位的。这意味着，在压缩之前，我们一开始要保存的数实际上是：
00000000000000000000000000000000000000000001101100000110101100010000000000000000000000000000000000000000001000011010011010001110
所以我们应该都能同意，压缩过后的格式好得多。集合中的数字越多，这种节约就越显著。虽然这样构造的过滤器（的体积）依然会随着数据数量的增长而线性增长，Golomb 编码是几何分布的数据的最优前缀码。在实践中，对轻节点来说，它将任一区块的数据都降低到几 kb 的量级，这已经够了。
在解码时，我们就按顺序读取，直到遇上第一个零，然后我们再读取后面的 19 位，例如：1110 | 0110000011010110001。然后，我们将开头的一元形式翻译回原来的二进制，接上后面的 19 位就得到我们的第一个数字： 0110110000011010110001。对剩下的数字，我们也做同样的操作，按顺序读取，直到遇上 0，然后读取后面的 19 位。只要集合中还有数字，我们就重复这个过程，直到解码出所有的元素。
这就是 BIP 158 概率性过滤器的的构造方式以及它时如何查找匹配数据的。在下一篇文章中，我们会讨论 Neutrino 客户端如何使用这些过滤器来尽可能减少自己需要下载的数据，同时又知道自己不会错过任何需要的数据。
- - -
在深入研究 BIP 157 定义的 P2P 消息之前，我们要先讲讲另一种 “新的” 结构，“区块过滤器头”。比特币区块有区块头，这是最基本的，它是 80 字节的元数据，足以让客户端确保自己在跟踪的是一条最长的链。类似的，区块过滤器也有 32 字节的头数据，帮助客户端跟踪最长的区块过滤器链条。区块过滤器头就是一个哈希值，关联着该区块过滤器的哈希值以及前一个区块过滤器的头：
区块过滤器 #n 的头 = Hash(Hash(区块过滤器 #n)||区块过滤器 #n-1 的头)
现在，我们有了区块过滤器和过滤器头，来看看 Neutrino 的 P2P 消息。BIP 157 定义了三种新的请求消息：getcfilters、getcfheaders 和 getcfcheckpt 以及相应的响应消息：cfilter、cfheaders 和 cfcheckpt（注：“cf” 就是 “紧凑过滤器” 的缩写）。从字面意义上就可以考出， getcfilters 和 getcfheaders 分别是请求一些过滤器和过滤器头。而 getcfcheckpt 是请求逢千号区块的区块过滤器的头，即 “请给我区块号 1000、2000、3000 等区块的区块过滤器头”。注意，这些新消息对比特币 P2P 网络中的所有节点都是可用的得了，不仅仅是 Neutrino 节点。
我们现在已经有了所有运行 Neutrino 节点所需的工具：区块过滤器、过滤器头，以及发送和接收它们的 P2P 消息。
那么，Neutrino 节点到底如何运行呢？
假设我现在启动了一个全新的 Neutrino 节点。它会先下载区块头链并验证工作量证明。这也是所有比特币节点（全节点、BIP 37 节点、Neutrino 节点）会采取的第一步。Neutrino 节点也会从对等节点处下载区块过滤器头链。具体来说，客户端会向所有的对等节点表示自己希望下载检查点（逢千号的区块）过滤器头，并确保所有的对等节点都同意。节点可以从不同的对等节点处下载不同段的千号区块头。做完这两个步骤之后，节点可以开始（从对等节点处）下载区块过滤器，并验证这些过滤器于过滤器头相匹配。当然，有了这些过滤器，客户端就可以看出某个区块是否提到了自己有兴趣的输出。发现了匹配之后，Neutrino 节点就使用比特币 P2P 网络 —— 没有用于下载过滤器的随机对等节点 —— 下载完整的区块。
不论这个过程中哪个环节出了错，或者发现了两个对等节点发送了相互矛盾的区块过滤器头或者过滤器，Neutrino 节点都必须质问这些对等节点并发现这项。办法是通过对千号区块过滤器头集合的二分搜索，来发现两个节点最早在哪个过滤器上出现了分歧。发现了第一个分歧所在之后，Neutrino 客户端就（从没有提供过滤器的随机对等节点处）下载完整的区块，并从头计算区块过滤器和过滤器头。然后，TA 就有能力辨别出哪个对等节点在说谎，并且不再接受对方的消息了。
这样一来，Neutrino 节点就可以保证，只要自己连上了一个诚实的对等节点，所有的欺诈节点都会被发现并被自己禁言！
BIP 157 并没有指定节点应该持久化保存多少个区块过滤器和过滤器头。相反，每个节点都可以自己决定保存多少个。对于许多节点来说（比如，使用手机的节点），可能保存最后 100 个左右的过滤器是最合适的。这使得基于 Neutrino 的钱包的存储负担相当小。
另一方面，如果一个节点有能令保存所有的区块过滤器 —— 体积依然比全部区块要小得多 —— 那它就有能力进行非常快速的钱包扫描。这是每一个钱包和用户都要考虑的取舍：是要存储空间，还是要扫描速度？对于大部分轻节点来说，它可能不会包含旧地址，而只会创建新地址。所以抛弃旧的区块过滤器可能更好。
如我们前面所述，BIP 157 所定义的新型 P2P 消息在整个比特币 P2P 网络中都已经可用。我预计，未来绝大多数全节点都会支持 Neutrino 服务器功能。这是很重要的，因为对 Neutrino 的隐私模型来说，提供过滤器的节点不能同时是提供完整区块的节点。这是因为如果一个节点既提供区块过滤器，又向发起这个请求的节点提供相应的完整区块，它就可以推断区块中有该请求节点关心的输出。如果这样的事情多次发生，请求节点的隐私可能很快就会泄露。最好的做法是避免这一点：有一个足够大的对等节点群体提供过滤器，而另一群足够大的对等节点提供完整区块，并且，在需要请求一个完整区块时，可以从后面这个群体中随机挑选。未来，如果可行的话，一些节点可能会支持使用 “隐私信息检索” 来下载完整区块，从而在根本上 “解决” 这个问题。
这就是 Neutrino 节点的全部了。它们通过跟踪区块过滤器头来验证区块过滤器，然后用过滤器来查看区块中是否有跟自己有关的输出，然后隐私地下载相应的完整区块。最后，只要其对等节点中有一个是诚实的，它们就有能力质疑和禁言任何恶意的对等节点。
（完）