比特币核心开发者 Pieter Wuille 推出基于 BCH 的开源项目 Miniske

北京时间12月10日，比特币代码的维护者、区块链协议公司Blockstream的联合创始人Pieter Wuille在个人推特上宣布了一个新的开源项目。 他说：

“很高兴宣布一个新的开源项目：一个用于带宽高效集合协调的库。共同贡献者包括 Greg Maxwell、Gleb Naumenko 等。” 然后，Wuille 补充说：“长话短说，这种方法的带宽开销最小（协调需要的数据与发送差异一样多），而 IBLT 可能需要更多的因素。它的缺点是速度较慢，性能是（O (n^2)，而不是 O(n))，但优化速度足够快。

我们创建这个东西的主要原因是在没有太多块中继的情况下改进比特币交易中继（延迟很关键）。 但是，它通常也可以用于许多其他应用程序。

”比特币代码现任首席维护者 Wladimir van der Laan 也转发了这个项目。有趣的是，这个项目的标题居然是“Minisketch：一个基于 BCH 的中心化协调库”。乍一看，你是不是觉得比特币的主要开发者都去为分叉币BCH打工了？

别误会，这个BCH不是那个BCH，智能合约之父Nick Szabo后来解释道：

“这里的 BCH = Bose–Chaudhuri–Hocquenghem 编码，不是指任何其他东西 :-)”Wuille 回应道：“真正的 BCH。”

那么，这个受到众多大神开发者关注的开源项目到底是怎么回事呢？ 我们先看一下它的代码库介绍：

以下为译文：

Minisketch：基于BCH的中心化协调库

libminisketch 是一个经过优化的独立 MIT 许可库，具有用于构建和解码集合草图的 C API，可用于紧凑集合协调和其他应用程序。 它是 PinSketch[1] 算法的实现，您可以在此处找到对其的解释：

集合调解草图

这个库生成的草图可以被认为是具有两个特殊属性的“设置校验和”：

1. sketch有一个预定的容量，当集合中的元素数量不高于容量时，libminisketch总是会从sketch中恢复整个集合。 具有容量为 c 的 b 位元素的草图可以存储在 bc 位中。 2. 两个集合的sketch可以通过相加（XOR）得到两个集合的对称差的sketch（即在一个输入集合中出现的所有元素，而不是在两个输入集合中出现的所有元素）这 。）

这使得它们适用于带宽效率很高的集合协调协议。 如果 Alice 和 Bob 每个人都有一组元素，并且他们怀疑这些集合大部分但不是全部重叠，他们可以使用以下协议让双方学习所有元素：Alice 和 Bob 都计算他们的集合元素草图。 爱丽丝将她的草图发送给鲍勃。 Bob 聚合两个草图并获得对称差草图。 Bob 尝试从差异草图中恢复元素。 Bob 将他拥有的每个 diff sketch 元素发送给 Alice。 当差异草图的大小（Alice 有但 Bob 没有的元素，加上 Bob 有但 Alice 没有的元素）不超过 Alice 发送的草图的容量时，这总是会成功。 有趣的是，这与实际集合大小无关，只有差异很重要。

如果元素很大，最好在集合元素的散列上计算草图。 在这种情况下，协议中添加了一个额外的步骤，其中 Bob 还向 Alice 发送他没有的每个元素的哈希值，Alice 以请求的元素作为响应。

doc/ 目录提供了使用 libminisketch 设计协调协议的额外提示。

评估

上面的第一张图显示了 libminisketch 与其他三个集合协调算法/实现的基准测试结果。 该基准测试是在配备主频为 2.4GHz 的英特尔酷睿 i7-7820HQ CPU 的系统上使用单核执行的。 该图显示了合并两个草图和解码结果所需的时间。 在同一台机器上创建草图的时间约为 5 ns（每容量和每组元素）。 其他实现有：pinsketch，原始的 PinSketch 实现。 cpisync 是一个实现多组协调算法和协议的软件项目，包含仅分析原始 CPISync 算法 [5] 的非概率版本的基准。 使用 4 个哈希函数和 32 位校验和的高性能自定义 IBLT 实现。 对于作者目前偏向的最大尺寸，比如set size为4096，variance为1024，libminisketch比pinketch快49倍，比cpisync快8000多倍。

对于计算资源有限的高流量 Web 服务器，libminisketch 在实际集合大小方面足够快。

即使性能受到延迟限制，小型迷你草图也可以足够快地提高性能。 在上面提到的i7-7820HQ中，只要通信带宽在每秒1Gb或更少，2500个30位的条目（相差20个元素）可以通过minisketch在比发送原始集更短的时间内传输. 在千兆链路上，八个元素的差异可以用五​​分之一以上的时间进行通信。

上面的第二张图显示了相同算法在同一系统上的性能，但这次将容量保持在 128，同时改变差异数以在 1 和 128 之间协调。它显示了 cpisync 调整的速度，主要取决于音量，而 pinsketch/libminisketch 更依赖于差异的数量。

上面的第三张图显示了对于不同级别的故障概率，典型 IBLT 方案相对于其他算法（接近最佳带宽）的开销。 当设置差异较小，要求的故障率较低时，IBLT占用libminisketch sketche带宽的十倍。

上面的图 4 显示了字段大小对 libminisketch 中速度的影响。 这三行分别对应： CLMUL 64-bit: Intel Core i7-7820HQ system, 2.4GHz general 64-bit: POWER9 CP9M06 system, 2.8GHz (Talos II) general 32-bit: 1.2GHz Cortex-A53 (Raspberry Pi 3B ) 它表明 CLMUL 实现对于某些字段更快（具体来说，在 GF(2) 上存在 xb + x + 1 形式的不可约多项式的字段大小，以及较小程度上的 8 位倍数字段）。 它还显示了在（现在）32 位平台上大于 32 位的字段是否存在显着的性能损失。 注意三条线的性能不同（树莓派3B在32位领域比酷睿i7慢10倍左右，POWER9慢1.3倍左右）。

下面我们将 PinSketch 算法（libminisketch 是一种实现）与其他集合协调算法进行比较：

1. 草图尺寸：此列表显示用于协调 c 个不同 b 位元素的草图位尺寸。 PinSketch 和 CPISync 具有接近最优的 [11] 通信开销，这实际上意味着草图大小非常接近（或等于）bc 位。 这与传递 diff 元素所需的大小相同。 对于IBLT，有一个过载系数α，取决于各种设计参数，但通常在2-10之间。

2.解码成功：每当草图设计的容量不低于实际差异大小时，CPISync和PinSketch保证差异的解码总是成功的。 IBLT 总是有失败的机会，尽管可以通过增加通信开销来降低任何机会。 3.解码复杂度：近最优算法节省的空间是以性能为代价的，因为它们的渐近解码复杂度是二次或三次的，而IBLT是线性的。 这意味着对于具有足够大方差的应用程序，使用接近最优的算法可能过于昂贵。 4.差异类型：PinSketch只能计算与合并后的草图的对称差异，而CPISync和IBLT可以区分哪些元素缺失。 当解码器可以访问其中一个集合时，这通常是无关紧要的，因为他可以从其中一个集合中查找对称差异中的每个元素。 5. Safe sketch：草图是否满足安全草图的定义[1]，这意味着对于任何不了解大部分元素的人来说，可以从草图中提取关于集合的最小集合数。 这使得该算法适用于指纹认证等应用。

创建

创建系统仍然很初级，欢迎改进。

以下步骤将起作用并生成一个您可以链接的 libminisketch.a 文件：

git clone https://github.com/sipa/minisketch
cd minisketch/src
make

用法 在这部分中，Alice 和 Bob 试图找到他们的集合之间的差异，其中 Alice 有集合 [3000...3009]，Bob 有集合 [3002...3011]。

首先，Alice 创建了一个草图：

#include 
#include 

#include "../include/minisketch.h"
int main(void) {
minisketch *sketch_a = minisketch_create(12, 0, 4);

论点是：

1.字段大小b，指定要协调的元素的大小。 对于字段大小 b，支持的集合元素范围为从 1 到 2^b-1 的整数。 请注意，元素不能为零。

2.实现数量。 始终支持实现 0，但某些硬件上可能提供更高效的算法。 Sketch 的序列化形式是实现独立的，因此不同的实现是可以互操作的。

3.容量c，指定生成的草图可以协调多少差异。

然后爱丽丝将她的元素添加到她的草图中。 请注意btc开源代码，第二次添加相同的元素将再次删除它，因为草图具有集合语义，而不是多重语义。

for (int i = 3000; i < 3010; ++i) {
minisketch_add_uint64(sketch_a, i);
}

下一步是将草图序列化为字节数组：

size_t sersize = minisketch_serialized_size(sketch_a);
assert(sersize == 12 * 4 / 8); // 4 12-bit values is 6 bytes.
unsigned char *buffer_a = malloc(sersize);
minisketch_serialize(sketch_a, buffer_a);
minisketch_destroy(sketch_a);

然后可以将缓冲区的内容提交给 Bob，Bob 可以创建自己的草图：

minisketch *sketch_b = minisketch_create(12, 0, 4); // Bob's own sketch
for (int i = 3002; i < 3012; ++i) {
minisketch_add_uint64(sketch_b, i);
}

Bob 收到 Alice 的连载草图后，可以协调：

sketch_a = minisketch_create(12, 0, 4); // Alice's sketch
minisketch_deserialize(sketch_a, buffer_a); // Load Alice's sketch
free(buffer_a);
// Merge the elements from sketch_a into sketch_b. The result is a sketch_b
// which contains all elements that occurred in Alice's or Bob's sets, but not
// in both.
minisketch_merge(sketch_b, sketch_a);
uint64_t differences[4];
ssize_t num_differences = minisketch_decode(sketch_b, 4, differences);
minisketch_destroy(sketch_a);
minisketch_destroy(sketch_b);
if (num_differences < 0) {
printf("More than 4 differences!\n");
} else {
ssize_t i;
for (i = 0; i < num_differences; ++i) {
printf("%u is in only one of the two sets\n", (unsigned)differences[i]);
}

}
}

在此示例中，Bob 将看到以下输出：

$ gcc -std=c99 -Wall -Wextra -o example ./doc/example.c -Lsrc/ -lminisketch -lstdc++ && ./example
3000 is in only one of the two sets
3011 is in only one of the two sets
3001 is in only one of the two sets
3010 is in only one of the two sets

输出的顺序是任意的，并且会随着 minisketch_decode() 的运行而变化。

应用

为了优化比特币交易分布 [8]，我们提出了通信高效集协调，这将允许比特币节点拥有更多的对等点，同时减少带宽使用。 它还可以用于比特币块分发 [9]，特别是用于非常低带宽的链路，例如卫星。 PGP SKS 密钥服务器使用类似的方法 (CPISync) 来有效地同步它们的数据库。 安全草图也可以用作辅助数据，以从混淆的生物识别数据中可靠地提取一致的加密密钥，同时最大限度地减少信息泄漏 [1]。 它们可以与 DCNet 结合创建加密的多方匿名通信 [10]。

实施说明

libminisketch 是用 C++11 编写的，但它有一个 C API 用于兼容性目的。

使用的特定算法和优化：

1、有限域实现：

(1) 使用 C 无符号整数位操作的通用实现，以及使用 CLMUL 指令的可用实现。 后者特定于允许优化的不同类别的字段（具有三项式不可约多项式的字段和具有 8 位倍数的字段）。

(2) 用于（重复）平方和求解形式为 x^2+x=a[2] 的方程的预计算表。

(3) 在乘法较快的系统上，使用指数阶梯进行逆计算，否则使用。

(4) 在乘法慢的系统上，使用运行时预计算来加速重复乘法。

(5) 字段元素的序列化，始终将它们表示为最小加权系数上的不可约多项式（使用字典顺序作为关系）GF(2)（参见此列表），但对于某些实现，它们在内部被转换为不同的表示.

2. sketch 算法是针对每个单独的字段专门实现的，允许内联和特定优化，同时避免动态分配和分支成本。

3.草图的解码使用Berlekamp-Massey算法[3]计算特征多项式。

4. 通过使用 Berlekamp 跟踪算法和二次多项式的显式公式 [4] 来求多项式的根。 根发现是随机的，以防止故意触发最坏情况解码时间的对抗性输入。

5. 一种（可能）新颖的优化，结合了唯一根测试和 Berlekamp 追踪算法。

目前我们仍在努力进行一些改进：

1. 高于2的多项式根的显式；

2.次二次乘法和模运算；

3、快速GCD的Semi-GCD算法；

4.增量解码接口：当尝试解码同一组的较长草图时，大多数失败解码中的大部分计算都可以重用；

5.针对x86以外平台的平台特定优化；

6、避免在32位主机上使用慢速uint64_t进行计算；

7. 可选IBLT/Hybrid，同一界面下设置熵编码器；

引文：

[1] 多迪斯、奥斯特洛夫斯基、雷津和史密斯。 模糊提取器：如何从生物识别和其他噪声数据中生成强密钥。 SIAM Journal on Computing，第 38 卷，第 1 期，第 97-139 页，2008 年）。 [网址] [PDF ]

[5] A. Trachtenberg、D. Starobinski 和 S. Agarwal。 使用特征多项式插值的快速 PDA 同步。 会议记录，IEEE 计算机和通信学会第 20 届年度联合会议，美国纽约州纽约市，2002 年，第 1510-1519 页，第 3 卷。 [PDF]

[2] Cherly、Jørgen、Luis Gallardo、Leonid Vaserstein 和 Ethel Wheland。 求解特征二的多项式环上的二次方程。 Publicacions Matemàtiques (1998)：131-142。 [PDF]

[3] J.梅西。 移位寄存器合成和 BCH 解码。 IEEE 信息论交易，卷。 15，没有。 1，第 122-127 页btc开源代码，1969 年 1 月。[PDF]

[4] 巴斯卡尔·比斯瓦斯，文森特·赫伯特。 特征域上多项式的高效求根 2. 2009. hal-00626997。 [网址] [PDF]

[6] Eppstein、David、Michael T. Goodrich、Frank Uyeda 和 George Varghese。 有什么区别？：没有先验上下文的有效集合协调。 ACM SIGCOMM 计算机通信评论，卷。 41，没有。 4，第 218-229 页。 美国计算机学会，2011 年 [PDF]

[7] Goodrich, Michael T. 和 Michael Mitzenmacher。 可逆绽放查找表。 2011 年第 49 届阿勒顿通信、控制和计算年度会议（阿勒顿）(2011)：792-799。 [PDF]

[8] Maxwell, Gregory F. Blocksonly mode BW savings, limits of efficient block xfer, and better relay Bitcointalk 2016, Technical notes on mempool synchronizing relay #bitcoin-wizards 2016。

[9] Maxwell, Gregory F. Block network coding Bitcoin Wiki 2014, Technical notes on efficient block xfer #bitcoin-wizards 2015.

[10] Ruffing、Tim、Moreno-Sanchez、Pedro、Aniket、Kate、P2P 混合和不可链接的比特币交易 NDSS 研讨会 2017 [URL] [PDF]

[11] Y. Misky、A. Trachtenberg、R. Zippel。 设置协调与近乎最佳的通信复杂性。 康奈尔大学，2000 年。[URL] [PDF]