前言：RSA累加器通過(guò)以太坊創(chuàng)始人Vitalik的計(jì)算，使用RSA累加器后，原本每年2.5 GB的Plasma子鏈數(shù)據(jù)，可以被壓縮到3.6 MB，壓縮率達(dá)到了驚人的99.856%。

然而，這種技術(shù)在其最初的設(shè)計(jì)當(dāng)中，需要用到可信設(shè)置，而來(lái)自斯坦福大學(xué)的應(yīng)用密碼學(xué)小組則發(fā)布了一篇題為《用于IOP和無(wú)狀態(tài)區(qū)塊鏈的累加器批處理技術(shù)》的論文，論述了一種通過(guò)類組（ class group）而無(wú)需可信設(shè)置的累加器方法，這些累加器可用于創(chuàng)建無(wú)狀態(tài)區(qū)塊鏈（指節(jié)點(diǎn)不需要存儲(chǔ)整個(gè)狀態(tài)，以確信哪些區(qū)塊是有效的），以及用于實(shí)現(xiàn)高效的UTXO commitment。

在這篇文章中，以太坊區(qū)塊鏈可擴(kuò)展性和安全研究員Georgios Konstantopoulos對(duì)該論文進(jìn)行了審查，并進(jìn)行了相關(guān)總結(jié)，以下為譯文：

在這篇文章中，我們將嘗試深入探索RSA累加器，同時(shí)回顧一下斯坦福大學(xué)應(yīng)用密碼學(xué)小組最近發(fā)表的論文，這篇非常重要的論文由Benedikt Bunz，Ben Fisch和Dan Boneh共同撰寫，其題目為《用于IOP和無(wú)狀態(tài)區(qū)塊鏈的累加器批處理技術(shù)》。

強(qiáng)烈建議大家復(fù)習(xí)下數(shù)學(xué)，以便更好地理解這一技術(shù)。

背景

自1994年以來(lái)，累加器便成為了學(xué)術(shù)界非常關(guān)注的一個(gè)話題。其類似于默克爾樹（Merkle Tree），并被用于以密碼方式承諾一組數(shù)據(jù)的知識(shí)。稍后，可通過(guò)發(fā)布證明來(lái)證明數(shù)據(jù)集中子集的成員身份。在默克爾樹（Merkle Tree）結(jié)構(gòu)中，證明被稱為默克爾分支（或默克爾證明），并且承諾數(shù)據(jù)的大小是以對(duì)數(shù)形式增長(zhǎng)的。

另一方面，累加器允許以恒定的大小證明成員身份，以及為多個(gè)元素批處理證明（默克爾樹沒(méi)有這一特性）。

本文的重點(diǎn)是描述RSA累加器構(gòu)建區(qū)塊、如何構(gòu)建成員和非成員身份的證明，以及如何跨多個(gè)區(qū)塊對(duì)它們進(jìn)行批處理。這種特殊的技術(shù)，也在基于UTXO的Plasma中具有應(yīng)用，并由此產(chǎn)生了Plasma原代變異體。設(shè)計(jì)一個(gè)允許在Plasma中壓縮UTXO集的累加器，需要付出大量的努力。

免責(zé)聲明：為了簡(jiǎn)單起見，作者模糊處理了這篇文章中的注釋（例如不包括G$中的$U、W或模塊化算術(shù)的mod N）。

術(shù)語(yǔ)表（來(lái)自［1］的定義）：

累加器：“一個(gè)密碼學(xué)累加器，其會(huì)產(chǎn)生對(duì)一組元素的短期約束承諾，以及對(duì)集合中任何元素的短期成員身份和非成員身份證明。”

動(dòng)態(tài)累加器：“支持添加和刪除具有O（1） 成本的元素累加器，其與累積元素?cái)?shù)量無(wú)關(guān)?！?/p>

通用累加器：“支持成員和非成員身份證明的動(dòng)態(tài)累加器。”

批處理：批驗(yàn)證n個(gè)證明，要比驗(yàn)證單個(gè)證明要快n倍。

聚合：在一個(gè)常量大小的證明中聚合n個(gè)成員證明。

未知順序組：組的順序是其集合中元素的數(shù)目。為了保證所提供的證明的安全性，需要生成一組未知順序（否則累加器中使用的模數(shù)有已知的因子分解，并且可以創(chuàng)建偽證明）。生成它可通過(guò)多方計(jì)算完成，但如果生成方串通檢索生成的數(shù)的階乘，則這是不安全的。它可通過(guò)使用類組在沒(méi)有可信設(shè)置的情況下生成（注：這點(diǎn)是非常重要的）。

隱序組的簡(jiǎn)潔證明

Wesolowski在［2］中提出了指數(shù)方案的知識(shí)證明，證明者試圖說(shuō)服驗(yàn)證者他們知道一個(gè)數(shù)字x，這樣，在已知基數(shù)u下，使得u^x=w成立。

讓我們舉個(gè)例子，以2為基數(shù)（u=2），w=16，則得出x=4。我們?cè)趺醋?？我們把X發(fā)送給驗(yàn)證者，它們必須執(zhí)行2^4，并對(duì)照W檢查結(jié)果。如果匹配，它們便會(huì)相信。以下兩個(gè)步驟似乎很明顯：

驗(yàn)證者必須執(zhí)行u^x ：對(duì)于大數(shù)字來(lái)說(shuō)，這是一個(gè)代價(jià)高昂的操作；

將x傳輸?shù)津?yàn)證者：x可能很大，因此傳輸它所需的帶寬可能不小；

讓我們看看有什么協(xié)議可以解決這一挑戰(zhàn)。這些協(xié)議都是交互式的，這意味著驗(yàn)證者和證明者互相發(fā)送“挑戰(zhàn)”（challenge），這些挑戰(zhàn)在協(xié)議的后續(xù)步驟中會(huì)被使用，以確保協(xié)議的安全。

求冪證明（PoE，第3.1節(jié)）

首先，讓我們看看如何讓驗(yàn)證者信服，而不需要它們實(shí)際運(yùn)行整個(gè)求冪運(yùn)算。

求冪證明（注：當(dāng)前版本的論文中有一個(gè)小錯(cuò)誤，在第8頁(yè)中，作者設(shè)置q=g^q而不是u^q。

“只有當(dāng)驗(yàn)證者能夠比計(jì)算u^x更快地計(jì)算余數(shù)r時(shí)，該協(xié)議才有用。它解決了求冪問(wèn)題，但仍然要求證明者向驗(yàn)證者傳輸一個(gè)潛在的大x，或者x是公開的?！?/p>

離散對(duì)數(shù)知識(shí)證明（PoKE， 第3.3節(jié)）

相比傳輸x，我們可傳輸r。證明變?yōu)椋≦，r），而驗(yàn)證者必須另外檢查r是否小于l（PoKE*協(xié)議）。當(dāng)對(duì)手可自由地選擇基數(shù)u時(shí)，這會(huì)是不安全的！

驗(yàn)證者被證明者愚弄了，他們知道z： u^z=w，而不知道z！

這里破解協(xié)議的細(xì)節(jié)在于，證明者選擇了基數(shù)u=g^x，因此x與l是互質(zhì)（co-prime）的。

我們可確定，上述協(xié)議適用于在公共參考字符串（CRS）中編碼和固定的基數(shù)g，簡(jiǎn)單來(lái)說(shuō)，各方事先就基數(shù)g達(dá)成一致，并且不能被對(duì)手任意選擇。

該協(xié)議可通過(guò)以下方式進(jìn)行修復(fù)：

對(duì)于固定的g，證明z=g^x離散對(duì)數(shù)x的知識(shí)；

證明同一x也是基為u，w的離散對(duì)數(shù)；

所以最后的協(xié)議（PoKE）是：

證明現(xiàn)在是2組元素Q和Q’。 我們能做得更好嗎？

將證明減少到一個(gè)組元素，這可通過(guò)添加其它交互步驟來(lái)完成：

驗(yàn)證者需要發(fā)送一個(gè)額外的挑戰(zhàn)alpha，以便證明者無(wú)法創(chuàng)建假證明。

從交互式證明，到非交互式證明

在隨機(jī)Oracle模型中，通過(guò)使用Fiat-Shamir heuristic，任何交互式協(xié)議都可變成非交互式的（假設(shè)我們有一個(gè)安全的隨機(jī)性生成器，例如一個(gè)安全的加密哈希函數(shù)）。

PoKE2需要兩個(gè)交互步驟，一個(gè)是由驗(yàn)證者挑選給證明者的生成器g，一個(gè)是發(fā)送挑戰(zhàn)值l和a。相反，我們可以哈希當(dāng)前的“抄本”（transcript），并使用輸出作為這些值。因?yàn)槲覀兪窃陔S機(jī)的Oracle模型中操作的，所以如果這些值是由驗(yàn)證者挑選的（以防證明者作弊，或者它們來(lái)自哈希函數(shù)）則沒(méi)有什么區(qū)別，因?yàn)檫@兩者在統(tǒng)計(jì)上是不可區(qū)分的！

每一方生成挑戰(zhàn)參數(shù)，而不需要交互，每次使用哈希函數(shù)和協(xié)議的當(dāng)前抄本

上述技術(shù)涉及證明函數(shù)w=f（x）=u^x（標(biāo)量值）的原像（preimage）知識(shí)。

這些技術(shù)也可以擴(kuò)展到支持同態(tài)原像知識(shí)的證明，即證明長(zhǎng)度n向量x的知識(shí)，使得φ（x）=w。

它們也可以在零知識(shí)下執(zhí)行。對(duì)于已知g，PoKE需要發(fā)送g^x。在驗(yàn)證協(xié)議的正確性時(shí)，我們假設(shè)存在一個(gè)模擬器，該模擬器能夠通過(guò)了解驗(yàn)證內(nèi)容x來(lái)模擬g^x。這會(huì)泄漏信息，因此不是零知識(shí)的！論文作者所使用的技術(shù)包括屏蔽輸入，這些輸入通過(guò)使用一種類似Schnorr的協(xié)議和佩德森承諾（Pedersen Commitments）技術(shù)來(lái)得到證明。如果你并不熟悉這些術(shù)語(yǔ)，可先訪問(wèn)一下這些內(nèi)容。

RSA累加器

我們?cè)谛g(shù)語(yǔ)表中給出了累加器的定義?，F(xiàn)在，我們將討論支持批量成員證明和非成員證明的通用累加器的構(gòu)造。

構(gòu)造累加器需要從一組未知順序中選擇一個(gè)模數(shù)N，該模數(shù)N可以從RSA組中選擇（例如，如果你信任RSA實(shí)驗(yàn)室，則為RSA-2048），也可以通過(guò)可信設(shè)置生成。

RSA累加器的初始狀態(tài)，是從未知順序g組中采樣的生成器，這意味著累加器中的元素列表為空［］。

如［3］所述，累加器必須具有準(zhǔn)交換數(shù)學(xué)性質(zhì)。

將元素x添加到累加器a，是通過(guò)將累加器提升到元素A’ = A^x mod N 來(lái)完成的。（為了簡(jiǎn)單起見，此處我們省略mod N）

證明成員身份

證明累加器中某個(gè)元素的成員身份，需要顯示該元素的值和驗(yàn)證因子。

驗(yàn)證因子或共同因子是累加器中所有值的乘積（除了我們正證明的包含值）

（值，驗(yàn)證因子）對(duì)是包含在集合中的證明。

“如果這個(gè)值是一個(gè)很大的數(shù)字，將其傳遞給驗(yàn)證者，并且求冪的成本是不可忽略的呢？”

這就是上面的NI-PoKE2協(xié)議的由來(lái)。相比發(fā)送上述所述的證明，我們可以證明驗(yàn)證因子的知識(shí)，其會(huì)提供一個(gè)有效的證明！這似乎不太可能，因?yàn)槲覀兊氖纠芎?jiǎn)單，但我們將在下面的批處理成員證明部分中，看到可能發(fā)生的情況。

證明非成員身份

非成員證明需要計(jì)算我們證明的元素的Bezout系數(shù)和集合中元素的乘積。在這里，我們可以找到關(guān)于這個(gè)主題的優(yōu)秀指南。

“Vitalik Buterin還提出了一種證明非成員身份的方法，其中他提到的想法是不確定的。（沒(méi)有提供其安全性的證明，因此如果你要使用它，可能要小心了?。?/p>

哈希素?cái)?shù)

奇質(zhì)數(shù)（即不帶2的素?cái)?shù)）既需要用于知識(shí)證明協(xié)議，也需要用于累加器元素。如果累積的元素不是素?cái)?shù)，那么對(duì)手可在元素不在集合中的情況下，愚弄驗(yàn)證者包含了該元素。

因此，我們必須將累積元素限制為素?cái)?shù)，否則對(duì)手可以證明包含累積元素的任何因子（在這種情況下，證明包含3是因?yàn)樗?的因子）。

此外，如果NI-PoKE2中的挑戰(zhàn)值l不是素?cái)?shù)，那么我們會(huì)得到另一種協(xié)同因子攻擊，其中攻擊者可以計(jì)算q，r，從而愚弄驗(yàn)證者包含了某個(gè)元素，這類似于 PoKE*攻擊。

聚合和批處理證明

回憶一下定義：

聚合：將多個(gè)證明組合在一個(gè)常量大小的證明中；

批處理：一次性驗(yàn)證多個(gè)證明，而不是單次地驗(yàn)證所有的證明；

聚合和批處理成員證明是是非常簡(jiǎn)單的，只需將被證明的值相乘，并為它們提供一個(gè)共同因素：

我們可以很快看出，如果我們想要為很多元素創(chuàng)建成員身份的聚合證明，那么值在傳輸時(shí)會(huì)變大，并且驗(yàn)證者需要執(zhí)行昂貴的指數(shù)運(yùn)算。為此，我們使用NI-PoKE2來(lái)證明我們知道因子g^65，而不需要向驗(yàn)證者發(fā)送231，驗(yàn)證者也不需要進(jìn)行昂貴的指數(shù)計(jì)算（我們實(shí)現(xiàn)了批量驗(yàn)證！）

批處理非成員證明，是通過(guò)計(jì)算元素 （a’， b’）積的Bezout系數(shù)來(lái)完成的，然后具有與以前相同的證明（g^a’，b’）。合并驗(yàn)證因子的大小，與提供兩個(gè)獨(dú)立的驗(yàn)證因子大致相同。

這可以通過(guò)將證明設(shè)置為（g^a’， A^b’） 來(lái)解決。為了確保安全，證明者還必須提供一個(gè)NI-PoKE2，以證明對(duì)b‘的了解。

第3步的NI-PoKE2是為了安全考慮，否則對(duì)手可能會(huì)設(shè)置v = g * d^（-xy），并在不知道b的情況下愚弄驗(yàn)證者。

這可以通過(guò)應(yīng)用NI-PoE來(lái)提高效率，這樣驗(yàn)證者就不需要在最后一步執(zhí)行求冪運(yùn)算。

在一個(gè)恒定大小驗(yàn)證因子的情況下，目前并沒(méi)有有效的算法來(lái)聚合非成員證明。

移除可信設(shè)置

所有的指數(shù)運(yùn)算都關(guān)于模N，這是一個(gè)具有未知素?cái)?shù)因子分解的數(shù)字。這是因?yàn)樘峁┑乃凶C明，都在未知順序組的通用組模型中（第2頁(yè)），并且需要強(qiáng)RSA假設(shè)和自適應(yīng)根假設(shè)。

在不知道相關(guān)私鑰的情況下生成公鑰是困難的。如論文第2頁(yè)中的［2］所述，我們可通過(guò)執(zhí)行安全的多方計(jì)算來(lái)創(chuàng)建所需的數(shù)字，但必須相信參與受信任設(shè)置的各方?jīng)]有串通來(lái)找回秘密。Wesolowski在［2］中通過(guò)所謂的“類組”（class groups）而提出了另一種選擇：

“一個(gè)更好的方法是使用虛二次序（imaginary quadraTIc order）的類組。事實(shí)上，通過(guò)選擇一個(gè)隨機(jī)的判別式，我們可以很容易地生成一個(gè)虛二次序，當(dāng)判別式足夠大時(shí)，就無(wú)法計(jì)算類組的順序。”

目前，Chia正在為有效計(jì)算這種“類組”而進(jìn)行競(jìng)爭(zhēng)，同時(shí)還提供了一份有關(guān)其背后所需理論的綜合性論文。

結(jié)論

如果你能看到這里，那么祝賀你！

我們簡(jiǎn)要介紹了RSA累加器的工作原理，以及如何構(gòu)造有效證明累加器中元素的成員身份和非成員身份的方案。原論文作者還提供了構(gòu)造向量承諾的方法，其在不同的索引處有成批的opening，這不是默克爾樹的特征。作者構(gòu)建了第一個(gè)能夠?qū)崿F(xiàn)O（1）opening的向量承諾方案（這里的opening指證明在承諾中某一指標(biāo)上某一要素的價(jià)值）。

應(yīng)用例子

這些累加器可用于創(chuàng)建無(wú)狀態(tài)區(qū)塊鏈（指節(jié)點(diǎn)不需要存儲(chǔ)整個(gè)狀態(tài)，以確信哪些區(qū)塊是有效的）。它們還可用于實(shí)現(xiàn)高效的UTXO承諾，允許用戶在不知道整個(gè)UTXO集的情況下發(fā)布交易。最后，向量承諾可用于創(chuàng)建簡(jiǎn)短的交互式Oracle證明，這一過(guò)程比使用默克爾樹（Merkle Tree）結(jié)構(gòu)更為有效。

下一步是什么？

這是一篇非常好的論文，它介紹并形式化了很多可用于區(qū)塊鏈結(jié)構(gòu)擴(kuò)展性的原語(yǔ)。

特別是，RSA累加器已吸引了Plasma研究社區(qū)成員的關(guān)注，他們正設(shè)法利用它來(lái)壓縮Plasma Cash的UTXO歷史。最近，ethresear.ch上已經(jīng)有很多關(guān)于如何構(gòu)造它的文章。因此，在下一篇文章中，我們將對(duì)當(dāng)前的方案、它們的優(yōu)缺點(diǎn)以及哪一個(gè)方案最為有效進(jìn)行盤點(diǎn)。

對(duì)于可利用向量承諾的非同質(zhì) Plasma 結(jié)構(gòu)，我也非常感興趣。

誰(shuí)知道呢，也許已經(jīng)有人在做這個(gè)了？

關(guān)于這一話題，接下來(lái)的文章題目會(huì)是： Plasma中的RSA累加器分類。