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

“我很高兴地宣布一个新的开源项目：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=BoseChaudhuriHocquenghem代码，而不是别的：-)”

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

以下翻译：

Minisketch:一个基于BCH的集合协调库

libminisketch是一个优化的独立MIT license库，有一个集合骨架用于构造和解码。它是PinSketch[1]算法的一个实现。关于这个算法的解释，你可以在这里找到：

https://github.com/SIPA/minischeme/blob/master/doc/math.md

集合中介的草图

。可以看作是一个具有两个特殊属性的“集合校验和”:

1。sketchs有一个预先确定的容量，当一个集合中的元素个数不高于这个容量时，libminisketch总是会从sketch中恢复整个集合。容量为C的B位元素的草图可以存储在bc位中。2.两个集合的草图可以通过将它们相加(XOR)来组合，以获得两个集合之间的对称差异草图(即，所有元素出现在一个输入集合中，但不是所有元素出现在两个输入集合中)。)

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

Alice和Bob都计算了他们的集合元素草图。把爱丽丝的素描发给鲍勃。Bob设置了两个草图，并获得了一个具有对称差异的草图。鲍勃试图从差异草图中恢复元素。Bob将他拥有的每个不同的草图元素发送给Alice。

当差异草图的大小(Alice拥有但Bob没有的元素，加上Bob拥有但Alice没有的元素)不超过Alice发送的草图的容量时，这将总是成功的。有趣的是，不管实际的集合大小如何，这都是有效的，只有差异是重要的。

如果元素比较大，最好在设置元素的hash上计算sketche。在这种情况下，协议中增加了一个额外的步骤，Bob也将他没有的每个元素的散列发送给Alice，Alice用请求的元素进行响应。

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

评测

上面的第一个图表显示了libminisketch的算法/实现在其他三个集合配合下的基准测试。基准测试是在采用英特尔酷睿i7-7820HQCPU、时钟速度锁定在2.4GHz的单核系统上进行的。 该图显示了合并两个草图和解码结果所需的时间。在同一台机器上创建草图的时间约为5 ns(每个容量和每个设置元素)。其他实现有：PinSketch，最初的PinSketch实现。Cpisync是一个软件项目，实现了许多组协调的算法和协议，它包含的基准测试只分析原始CPISync算法的非概率版本[5]。使用4个哈希函数和32位校验和的高性能定制IBLT实现。

对于作者目前青睐的最大尺寸，比如设定容量为4096，相差1024。libminisketch比pinketch快49倍，比cpisync快8000多倍。

蓑衣网小编2022对于计算资源有限的高流量网络服务器来说，libminisketch在实际的集合大小上足够快。

即使在有限的性能延迟的情况下，小的minisketche对于性能改进来说也是足够快的。在上面提到的i7-7820HQ中，只要通信带宽在每秒1千兆以下，就可以在短时间内通过minisketch传输2500个30位条目(相差20个元素)，而不用发送原集。在千兆链路上，八个元素的差异可以在超过五分之一的时间内传递。

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

上面的第三个图表显示了典型IBLT方案相对于其他算法(这些算法接近最优带宽)在不同故障概率水平下的成本。在集合差较小，要求故障率较低的情况下，IBLT占用的带宽是libminisketch sketche的十倍。

上面的图4显示了libminisketch中字段大小对速度的影响。这三行应该是针对：

CLMUL 64位：Intel core i7-7820HQ系统，2.4GHz通用64位：POWER9 CP9M06系统，2.8GHz(Talos II)通用32位：Cortex-A53 (Raspberry Pi3b)在1.2GHz

它表明CLMUL的实现对于某些领域更快(具体来说，GF(2)上有一个xb x 1形式不可约多项式的字段大小，蓑衣网小编2022在较小程度上是一个字段它还显示了在(现在的)32位平台上，对于大于32位的字段，是否存在显著的性能下降。请注意，三条线的性能是不一样的(树莓派3B的32位域比酷睿i7慢10倍左右，而POWER9的速度慢1.3倍左右)。

接下来，我们将PinSketch算法(libminischeme是一个实现)与其他集合调和算法进行比较：

1。草图尺寸：该列表显示了用于协调不同B位元素的草图位尺寸。Pinsketch和CPISync有接近最优的[11]通信开销，这实际上意味着sketch的大小非常接近(或等于)bc比特。这与difference元素的大小相同。对于IBLT，有一个过载系数，它取决于各种设计参数，但通常在2到10之间。

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

创作

创作系统还很初级，欢迎大家改进。

蓑衣网小编2022以下步骤可以工作并生成一个libminisketch.a文件。可以实现链接：

git clone https://github.com/sipa/minisketchcd微型架构/srcmake

用法

在这一部分中，爱丽丝和鲍勃试图找出他们的集合之间的差异，其中爱丽丝设置了[3000.3009]和鲍勃设置[3002.3011].

首先，Alice创建一个草图：

# include # include './include/minischeme . h ' int main(void){ minischeme * sketch _ a=minischeme _ create(12，0，4)；

自变量为：

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

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

3。容量C，指定结果草图可以协调多少差异。

然后Alice将她的元素添加到她的草图中。注意第二次添加同一个元素会再次删除，因为sketch有集合语义，没有多集合语义。

for(int I=3000；i 3010I){ mini sketch _ add _ uint 64(sketch _ a，I)；}

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

size _ tser size=minischeme _ serialized _ size(sketch _ a)；assert(sersize==12 * 4/8)；//4个12位值为6字节. unsigned char * buffer _ a=malloc(sersize)；minisketch_serialize(sketch_a，buffer _ a)；minisketch_destroy(草图_ a)；

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

minischeme * sketch _ b=minischeme _ create(12，0，4)；//Bob自己的sketch for(int I=3002；i 3012I){ mini sketch _ add _ uint 64(sketch _ b，I)；}

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

sketch _ a=minischeme _ create(12，0，4)；//Alice的sketchminisketch _ deserialize(sketch _ a，buffer _ a)；//加载爱丽丝的sketch free(buffer _ a)；//将sketch_a中的元素合并到sketch_b中，结果是一个sketch_b//包含Alice或Bob集合中出现过的所有元素，但不//在both.minisketch_merge(sketch_b，sketch_a)中出现过的所有元素；uint64_t差异[4]；ssize _ t num _ differences=minisketch _ decode(sketch _ b，4，differences)；minisketch_destroy(草图_ a)；minisketch_destroy(草图_ b)；if (num_differences 0) {printf('超过4个差异！\ n’)；} else { ssize _ t I；for(I=0；I数量_差异；i) {printf('%u仅在两个集合之一中 '，(无符号)differences[I])；}}}

在这个例子中，Bob会看到下面的输出：

$ gcc-STD=c99-wall-wextra-o example。/doc/example . c-lsrc/-lminisketch-lstdc。/Example 3000 is ONLY IN THE TWO set之一3011 is ONLY IN THE TWO set之一3001 is ONLY IN THE TWO set之一3010 is ONLY IN THE TWO set之一[X]输出顺序是任意的，在minisketch_decode()的不同操作中会有所不同。

应用

为了优化比特币交易的分布[8]，我们提出了通信高效集合协调，这将允许比特币节点有更多的对等点，减少带宽使用。也可以用于比特币分块分发[9]，尤其是非常低带宽的链路，比如卫星。PGP SKS密钥服务器使用类似的方法(CPISync)来有效地同步它们的数据库。Secure 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]