区块链RSA累加器批处理技术解析.doc

区块链RSA累加器批处理技术解析

前言：RSA累加器通过以太坊创始人Vitalik的计算，使用RSA累加器后，原本每年2.5GB的Plasma子链数据，可以被压缩到3.6MB，压缩率达到了惊人的99.856%。

然而，这种技术在其最初的设计当中，需要用到可信设置，而来自斯坦福大学的应用密码学小组则发布了一篇题为《用于IOP和无状态区块链的累加器批处理技术》的论文，论述了一种通过类组（classgroup）而无需可信设置的累加器方法，这些累加器可用于创建无状态区块链（指节点不需要存储整个状态，以确信哪些区块是有效的），以及用于实现高效的UTXOcommitment。

在这篇文章中，以太坊区块链可扩展性和安全研究员GeorgiosKonstantopoulos对该论文进行了审查，并进行了相关总结，以下为译文：

在这篇文章中，我们将尝试深入探索RSA累加器，同时回顾一下斯坦福大学应用密码学小组最近发表的论文，这篇非常重要的论文由BenediktBunz，BenFisch和DanBoneh共同撰写，其题目为《用于IOP和无状态区块链的累加器批处理技术》。

强烈建议大家复习下数学，以便更好地理解这一技术。

背景

自1994年以来，累加器便成为了学术界非常关注的一个话题。其类似于默克尔树（MerkleTree），并被用于以密码方式承诺一组数据的知识。稍后，可通过发布证明来证明数据集中子集的成员身份。在默克尔树（MerkleTree）结构中，证明被称为默克尔分支（或默克尔证明），并且承诺数据的大小是以对数形式增长的。

另一方面，累加器允许以恒定的大小证明成员身份，以及为多个元素批处理证明（默克尔树没有这一特性）。

本文的重点是描述RSA累加器构建区块、如何构建成员和非成员身份的证明，以及如何跨多个区块对它们进行批处理。这种特殊的技术，也在基于UTXO的Plasma中具有应用，并由此产生了Plasma原代变异体。设计一个允许在Plasma中压缩UTXO集的累加器，需要付出大量的努力。

免责声明：为了简单起见，作者模糊处理了这篇文章中的注释（例如不包括G$中的$U、W\或模块化算术的modN）。

术语表（来自［1］的定义）：

累加器：“一个密码学累加器，其会产生对一组元素的短期约束承诺，以及对集合中任何元素的短期成员身份和非成员身份证明。”

动态累加器：“支持添加和删除具有O（1）成本的元素累加器，其与累积元素数量无关。”

通用累加器：“支持成员和非成员身份证明的动态累加器。”

批处理：批验证n个证明，要比验证单个证明要快n倍。

聚合：在一个常量大小的证明中聚合n个成员证明。

未知顺序组：组的顺序是其集合中元素的数目。为了保证所提供的证明的安全性，需要生成一组未知顺序（否则累加器中使用的模数有已知的因子分解，并且可以创建伪证明）。生成它可通过多方计算完成，但如果生成方串通检索生假证明。

从交互式证明，到非交互式证明

在随机Oracle模型中，通过使用Fiat-Shamirheuristic，任何交互式协议都可变成非交互式的（假设我们有一个安全的随机性生成器，例如一个安全的加密哈希函数）。

PoKE2需要两个交互步骤，一个是由验证者挑选给证明者的生成器g，一个是发送挑战值l和a。相反，我们可以哈希当前的“抄本”（transcript），并使用输出作为这些值。因为我们是在随机的Oracle模型中操作的，所以如果这些值是由验证者挑选的（以防证明者作弊，信息，因此不是零知识的！论文作者所使用的技术包括屏蔽输入，这些输入通过使用一种类似Schnorr的协议和佩德森承诺（PedersenCommitments）技术来得到证明。如果你并不熟悉这些术语，可先访问一下这些内容。

RSA累加器

我们在术语表中给出了累加器的定义。现在，我们将讨论支持批量成员证明和非成员证明的通用累加器的构造。

构造累加器需要从一组未知顺序中选择一个模数N，该模数N可以从RSA组中选择（例如，如果你信任RSA实验室，则为RSA-2048），也可以通过可信明。

“如果这个值是一个很大的数字，将其传递给验证者，并且求幂的成本是不可忽略的呢？”

这就是上面的NI-PoKE2协议的由来。相比发送上述所述的证明，我们可以证明验证因子的知识，其会提供一个有效的证明！这似乎不太可能，因为我们的示例很简单，但我们将在下面的批处理成员证明部分中，看到可能发生的情况。

证明非成员身份

非成员证明需要计算我们证明的元素的Bezout系数和集合中元素的乘积。在这里，我们可以找到关于这个主题的优秀指南。

“VitalikButerin还提出了一种证明非成员身份的方法，其中他提到的想法是不确定的。（没有提供其安全性的证明，因此如果你要使用它，可能要小心了！）”

哈希素数

奇质数（