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

编译：洒脱喜

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

“很高兴地宣布一个新的开源项目：https://github.com/sipa/minisketch ，这是一个用于带宽效率集协调的库。包括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许可库，其带有用于构造和解码集sketche的C API，可用于紧凑集协调以及其他应用程序。它是PinSketch[1]算法的一个实现，关于此算法的解释，你可以在这里找到：

https://github.com/sipa/minisketch/blob/master/doc/math.md

用于集调解的Sketche

Sketches，如该库所生成的，可以看作具有两个特殊属性的“设置校验和”：

1、Sketches具有预定容量，并且当集中的元素数量不高于容量时，libminisketch将始终从sketch中恢复整个集。具有容量c的b位元素的sketch，可以以bc位存储。 2、可以通过添加它们（XOR）来组合两个集的sketches，以获得两个集之间对称性差异的sketch（即，在一个输入集合中出现的所有元素，但不是两个输入集合中出现的所有元素。）

这使它们适用于带宽效率非常高的集协调协议。如果Alice和Bob各自拥有一组元素，并且他们怀疑这些集大部分但并非都是完全重叠的，他们可以使用以下协议来让双方学习所有的元素：

Alice和Bob都计算了他们的集元素sketch。

Alice把她的sketch发送给Bob。

Bob集合两个sketch，并获得了对称差异的sketch。

Bob试图从差异sketch中恢复元素。

Bob将他所拥有的每个差异sketch元素都发送给Alice。

当差异sketch的大小（Alice拥有但Bob没有的元素，加上Bob拥有但Alice没的元素）不超过Alice发送的sketch容量时，这将会始终是成功的。有趣的是，无论实际设定的大小如何，这都是有效的，只有差异是重要的。

如果元素很大，则最好在设置元素的哈希上计算sketche。在这种情况下，在协议中添加了一个额外的步骤，其中Bob还将他没有的每个元素的哈希发送给Alice，而Alice用所请求的元素进行响应。

doc /目录提供了使用libminisketch设计协调协议的其他技巧。

评估

上面的第一个图表，显示了libminisketch与其他三个集协调算法/实现的基准结果。该基准测试是在具有Intel Core i7-7820HQCPU、时钟速度锁定在2.4GHz的系统上使用单核执行的。该图显示了合并两个sketche和解码结果所需要的时间。在同一台机器上创建sketch的时间大约是 5 ns （每个容量和每个设置元素）。其他实现是：

pinsketch，最初的PinSketch实现。

cpisync，一个实现很多组协调算法和协议的软件项目，包含的基准测试仅分析原始CPISync算法的非概率版本[5]。

使用4个哈希函数和32位校验和的高性能自定义IBLT实现。

对于目前作者偏向的最大大小，例如集容量为4096，差异为1024，libminisketch比pinketch快49倍，比cpisync快8000多倍。

libminisketch对于计算资源有限的高流量网络服务器而言，它在实际的集大小中是足够快的。

即使在性能延迟限制的情况下，小型minisketche对于性能提高而言也可以是足够快的。在上面提到的 i7-7820HQ中，只要通信带宽为每秒1千兆位或更少，就可以在较短的时间内通过minisketch传送2500 个30位条目（差异为20个元素），而不是发送原始集。在千兆位链路上，八元素差值可以在超过五分之一的时间内进行通信。

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

上面的第三个图表，显示了对于不同级别的故障概率大小，典型IBLT方案相对其他算法（这些算法接近最优带宽）的开销。当集差值较小，且所需故障率较低时，IBLT占用的带宽数是libminisketch sketche 的十倍。

上面的图4显示了libminisketch中字段大小对速度的影响。这三条线分别应对于：

CLMUL 64位：英特尔核心i7-7820HQ系统，2.4GHz

通用64位：POWER9 CP9M06系统，2.8GHz（Talos II）

通用32位：1.2GHz的Cortex-A53 (Raspberry Pi 3B)

它显示了CLMUL实现对于某些字段而言是更快的（具体来说，在GF（2）上存在xb + x + 1形式的不可约多项式的字段大小，以及在较小程度上是8位倍数的字段）。它还显示了（现在）32位平台上大于32位的字段是否存在显着的性能下降。 请注意，三条线的表现是不同的（Raspberry Pi 3B的32位字段比Core i7慢约10倍，而POWER9的速度则慢约1.3倍）。

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

1、Sketch大小：此列表显示了用于协调c个不同b位元素的sketch位大小。 PinSketch和CPISync具有接近最佳的[11]通信开销，实际上这意味着sketch大小非常接近于（或等于）bc位。这与传递差异元素所需的大小是相同的。对于IBLT，存在着过载因子α，其取决于各种设计参数，但通常在2-10之间。

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

创建

创建系统目前还很初级，欢迎大家对其进行改进。

下面的步骤可以工作，并生成一个libminisketch.a文件，你可实现链接：

git clone https://github.com/sipa/minisketchcd minisketch/srcmake

用法

在这部分当中， Alice和Bob试图找出他们的集之间的差别，其中Alice有集[3000 ... 3009]，而 Bob有集 [3002 ... 3011]。

首先，Alice创建一个sketch:

#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，指定结果sketch可以协调多少差异。

然后Alice将她的元素添加到她的sketch当中。请注意，第二次添加相同的元素会再次删除它，因为sketch具有集语义，而不是多集语义。

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

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

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可以创建自己的sketch:

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

在Bob收到Alice的序列化sketch之后，他可以进行协调：

sketch_a = minisketch_create(12, 0, 4); // Alice's sketchminisketch_deserialize(sketch_a, buffer_a); // Load Alice's sketchfree(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++ && ./example3000 is in only one of the two sets3011 is in only one of the two sets3001 is in only one of the two sets3010 is in only one of the two sets

输出的顺序是任意的，并且在minisketch_decode()的不同运行中会有所不同。

应用

为了优化比特币交易分布[8]，我们提出了通信高效集协调，这将允许比特币节点具有更多的对等节点，同时减少带宽使用。它也可以用于比特币区块分布[9]，特别是对于非常低的带宽链路，例如卫星。PGP SKS密钥服务器使用类似的方法（CPISync）来有效地同步它们的数据库。安全sketche还可用作帮助数据，从而可靠地从模糊生物特征数据中提取一致的密码密钥，同时泄漏最少的信息[1]。它们可以与dcnet组合，以创建加密多方匿名通信[10]。

实现说明

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

使用的特定算法和优化：

1、有限域实现：

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

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

（3）在乘法比较快的系统上，使用指数阶梯进行逆计算，否则使用扩展GCD算法。

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

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

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

3、sketch的解码使用Berlekamp-Massey算法[3]来计算特征多项式。

4、找到多项式的根，是利用Berlekamp跟踪算法和二次多项式的显式公式[4]完成的。根的发现是随机的，以防止有意触发最坏情况解码时间的敌对输入。

5、一种（可能的）新颖优化结合了对独特根的测试和Berlekamp跟踪算法。

目前我们仍在做一些改进工作：

1、高于2的多项式根的显式公式；

2、次二次乘法和模算法；

3、快速GCD的半GCD算法；

4、用于增量解码的接口：在尝试解码同一组的较长sketch时，可重用大多数失败解码中的多数计算；

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

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

7、可选的IBLT / Hybrid和在同一接口下设置熵编码器；

引用文献：

[1] Dodis, Ostrovsky, Reyzin and Smith. Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data. SIAM Journal on Computing, volume 38, number 1, pages 97-139, 2008). [URL] [PDF]

[5] A. Trachtenberg, D. Starobinski and S. Agarwal. Fast PDA synchronization using characteristic polynomial interpolation. Proceedings, Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies, New York, NY, USA, 2002, pp. 1510-1519 vol.3. [PDF]

[2] Cherly, Jørgen, Luis Gallardo, Leonid Vaserstein, and Ethel Wheland. Solving quadratic equations over polynomial rings of characteristic two. Publicacions Matemàtiques (1998): 131-142. [PDF]

[3] J. Massey. Shift-register synthesis and BCH decoding. IEEE Transactions on Information Theory, vol. 15, no. 1, pp. 122-127, January 1969. [PDF]

[4] Bhaskar Biswas, Vincent Herbert. Efficient Root Finding of Polynomials over Fields of Characteristic 2. 2009. hal-00626997. [URL] [PDF]

[6] Eppstein, David, Michael T. Goodrich, Frank Uyeda, and George Varghese. What's the difference?: efficient set reconciliation without prior context. ACM SIGCOMM Computer Communication Review, vol. 41, no. 4, pp. 218-229. ACM, 2011. [PDF]

[7] Goodrich, Michael T. and Michael Mitzenmacher. Invertible bloom lookup tables. 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton) (2011): 792-799. [PDF]

[8] Maxwell, Gregory F. Blocksonly mode BW savings, the 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 Mixing and Unlinkable Bitcoin Transactions NDSS Symposium 2017 [URL] [PDF]

[11] Y. Misky, A. Trachtenberg, R. Zippel. Set Reconciliation with Nearly Optimal Communication Complexity. Cornell University, 2000. [URL] [PDF]