最近在聽區塊鏈 Zero Knowledge Podcast的時候聽到了RSA Accumulator的介紹，搜尋之後發現是個有趣，也略微複雜很多數學的主題，由於它更佳的驗證特性，從Stateless Client到Plasma以及UTXO模型擴容中都有被討論。因此今天就來整理一下自己的學習紀錄，其中有些數學太過艱澀難懂，我就收錄簡單的部分。

Merkle Tree

要了解Accumulator還得從Merkle tree說起。相信大家對於Merkle tree都有一定程度的瞭解，就是一層一層的Hash，最後用固定大小的雜湊值(Merkle root)來表示一個特定的key value table。

最頂端這個root值不能獨自證明什麼，必須要搭配著Merkle proof (Merkle branch)來達到「驗證」的效果。像下圖中的例子，若是要證明綠色方塊的值確實在這個merkle tree中，你需要同時提交所有黃色方塊的值給驗證者，讓他們試著一層一層Hash上來，看看是不是跟root值一樣。

Merkle Proofs (from ethereum blog)

在比特幣中，一個區塊會在區塊頭中會附上該區塊所有交易的merkle root，因此一個只存區塊頭的Light Client可以向全節點(full node)詢問一個交易是否被包含在某個區塊中，全節點可以利用merkle proof來證明自己回答的正確性。以太坊中更廣泛的使用merkle tree，為了讓智能合約對current state有全盤掌握，在每個區塊中除了tx root以外，還含有state root 以及 receipt root。這使得以太可以透過merkle proof來驗證包含用戶餘額、智能合約運行等等查詢的結果。

Accumulator

A cryptographic accumulator is a one-way membership function. It answers a query as to whether a potential candidate is a member of a set without revealing the individual members of the set.

在密碼學中，Accumulator指的是一個能夠在不暴露所有群集元素的情況下，配合證明(proof)確保某個元素在一個群集之中的函數。我們剛剛所看的Merkle tree就可以當作Accumulator的一種，因為透過已知merkle root情況下，配合merkle branch作為proof，我們就能證明一個元素的存在。

註：嚴謹的密碼學定義中，會要求proof 是固定大小，而Merkle tree不符合此一定義，但接下來還是會繼續用大家熟悉的merkle tree做比較。

RSA Accumulator

接著我們直接來看RSA Accumulator。

它的基本數學非常簡單，我們透過一個質數 g 作為基底，再配合一個選擇好的 N = p * q ，其中 p,q 皆為秘密的大質數。

N Value Setup

首先必需介紹一下 N 的選擇。 N是由兩個秘密質數相乘而來，若有人知道其組成，將可以破解RSA Accumulator的驗證。因次對於 N 的選擇，可以選擇相信公開宣布已經銷毀 p, q 的 N 值，或是RSA2048這種目前技術進行分解的大數。另一個可行的方法是透過所謂的Class Group 來進行 N 的創造，但這方面的好像牽扯很多複雜的數學，有興趣的人可以自己參考這篇論文。

Initiation and membership witness

當我們選好了基底 g想要創建一個Accumulator，放入數字 a的時候，就進行 g^a 次方運算，得到Accumulator A 。

A = g^a mod N

若是要加入新的成員到Accumulator中，就繼續執行次方運算。例如我們接著想要加入 a_2, a_3，那麼我們的Accumulator就會變為：

A = A^(a_2 * a_3    ) mod N
  = g^(a_2 * a_3 * a) mod N

若我們想要證明 a_2 確實在這個Accumulator之中，我們需要提供的witness w就是Accumulator扣除了 a_2 的部分，驗證則是試算 w^ a_2 是否等於Accumulator的值

w = g^(a * a_3) mod Nverify:
A = w^a_2 mod N

也可以直接看最直觀的數字例子（先忽略 mod N）：

Adding and Verifying in RSA Accumulator

我們可以發現，不論現在Accumulator已經存放的多少東西，都可以透過在只知道Accumulator目前root value的情況下，以O(1)的複雜度加入元素。這樣的Accumulator 稱為 Dynamic Accumulator，廣泛一點來說就是能夠隨意Update 這個Accumulator。

Aggregating Proofs

除此之外，我們還可以把多個想要驗證的值，合併在一起產生一個witness。例如下圖例子中，我們可以一次驗證5, 13都在Accumulator中。這種能整合多個witness為一的特性稱為累加性(Aggregating)。而有效率的一次產生或驗證多個witness則稱為批次性(Batching)。這兩者都是merkle tree不具備的。

接續上面的例子，我們可以用一個 w 驗證兩個element。

Non-Membership Witness

RSA Accumulator 除了能夠的驗證一個element在一個Accumulator中外，也能夠進一步給出非成員證明(non-membership witness)，及證明一個數字不存在此Accumulator中。驗證方法會需要用到貝祖定理(Bézout’s identity)：

ax + by = m
(x, y)有整數解時若且唯若 m 是(a, b)的最大公因數 d 的倍數。也就是說：ax + by = 1
(x, y)有整數解時若且唯若(a, b)互質。

用上面的例子來看，假如果們要證明數字7不是1105因數，根據貝祖定理，我們只要找到一組滿足 7a + 1105b = 1的整數解即可。完整的過程如下：

non-membership proof with RSA Accumulator

同樣基於貝祖定理，V神在這篇討論文中介紹了另一個驗證方式。沿用上一個例子，若是要證明 x不在集合當中，我們需要找到一個值 r 滿足:

0 < r < x
A * g^r  為 g^x 的整數次方

以下是簡單的證明，表達這個驗證方式跟我們剛剛使用的方式是等效的

Vitalik 的驗證方式證明

能夠進行非成員驗證的Accumulator稱為 Universal Accumulator，一般的merkle tree是無法達成的(必須要有特殊排序才行)。這是個很好用的特性，假如我們用Accumulator紀錄一個UTXO set，我們就可以使用非成員證明來證明在特定區塊高度，某個UTXO不存在。

Proof of Knowledge Schemes

現在我們已經知道RSA如何進行驗證，基本上就是次方的運算。但這在實踐上有個困難點，因為若是結合了許多要驗證的值的話，x 的大小會線性成長，因此我們不會直接提供 x ，而是需要再透過其他proof of knowledge scheme 來間接完成。

我們可以把問題簡化成：已知 u ^ x = w ，如何在不實際運算 u^x 的情況下驗證這件事情。以下我們舉一個簡單例子：Proof of Exponentiation。

Proof of Exponentiation

透過這個Scheme，最後proof大小上會因為 x/B 的步驟而限縮。而驗證時，雖然需要 Verifier 自己算出 r = x mod B ，不過在RSA的使用情境中會比算次方快上許多。

在 Georgios Konstantopoulos 的A Deep Dive on RSA Accumulator這篇文章中更仔細的介紹了不同Proof of Knowledge Scheme如何配合RSA Accumulator進行membership以及non-membership 的驗證，就留給對數學更有興趣的人自己看啦。

Conclusion on RSA Accumulators

最後我們來整理一下RSA Accumulator所有的好處，其中我覺得最重要的是以下兩點，它在我們接下來要討論的Stateless Client中至關重要。

1. Proof大小不隨驗證成員數增加。
2. 不需知道所有State也能進行更新。

Stateless Client

現在的區塊鏈網路中只存在儲存了所有資訊的全節點(Full node)，以及需要與全節點連線才能運作的Light Client。這是因為對於交易是否合法的驗證需要涉及對整個區塊鏈狀態(State)的了解，所以目前所有共識以及驗證都是由全節點完成。

Stateless Client其實是一個從2013年開始就開始被比特幣討論的主題（當時比特幣論壇稱為Storageless Client），簡而言之就是一個「不需要儲存所有State，卻能參與交易驗證」的角色。如果真的有了Stateless Client，網路中的礦工節點以及認證交易的節點，將不再需要花大量的記憶體存所有的帳戶餘額資訊。

Applying RSA Accumulator

區塊鏈現有的merkle tree架構存在一些Stateless Client的障礙。我們以ETH為例，merkle state root 紀錄了所有state的現狀，假設現在有一個只存區塊頭的Stateless Client，我們可以透過提供多個merkle proof來向他證明多個storage的值，接著進一步證明一個交易是合法的。但merkle root 並沒有stateless update的特性，無法在不知道所有state的情況下，靠著我們提供給他的proof來進行state root的更新。也就是說他即使知道我們交易合法，也並不能更新state root接著進行下一個交易的驗證。

若我們能把merkle tree換成RSA Accumulator，理論上就能真正有stateless client參與「交易的驗證」：我們若是要提交交易給一個 stateless client，我們就必須附上所有一個交易會動用到的所有State對應的witness，另一個好消息是我們還可以透過aggregating特性將這個proof變為constant size。在節點收到我們的請求時，他可以快速利用這些witness來驗證並且決定要不要採信該交易。在接受了我們交易後，client也可以快速的update accumulator並接著進行驗證。

Stateless Clients in the Ecosystem

在一個使用者與stateless client的互動模式中，我們將整個驗證過程的成本從「Node儲存State花費的空間」轉嫁到了「使用者計算witness」上。我們可以認真思考一下，這究竟對使用者是一個多大的負擔？

首先要產生對應的witness，代表使用者必須要維護一個 RSA Accumulator。這意味著不斷地監聽以太坊的交易，並且不斷的更新自己的Accumulator，這顯然是一個不合理的要求。

不過也別忘了，網路中還是存在許多的全節點，使用者與全節點的互動不需要有任何改變，因為全節點知曉一切，這可能會讓使用者最終還是選擇將交易提交給全節點當中，而全節點就擔任了聯絡stateless client的角色，當它知道它的廣播對象是stateless的時候，就會附上witness交給這些節點驗證。

有另外一個值得思考的問題就是，究竟整個以太網路中，有多少節點是專注於「交易驗證」，有多少則專注於「給應用層進行查詢和溝通」。有了stateless 的選項之後，我們可以讓專門做驗證的節點以及礦工節點變為 stateless，而全節點可能演變成一個Data Provider的角色，提供給應用層進行餘額等等查詢，也可以是一個witness provider，為使用者維護要與stateless client溝通所需要的Accumulator。這是一個更為健康的生態系，不同的節點若能在一個網路中真正各司其職，相信將會是stateless client能創造最大的價值。

所以，一起期待RSA Accumulator以及Stateless Client的未來吧！

End Game

這是第一次撰寫這麼學術內涵的文章，很多數學看來看去還是決定不要放上來免得打錯或理解錯很尷尬，所以最後寫出來也就不太難了xD。這也是第一次認真的追了很多Ethereum Research 的文章，雖然很多部分還是看不懂，但能夠慢慢Follow上討論進度的感覺還是不錯的。

個人覺得Stateless Client是也是比較簡單理解的，所以這篇文章就提了RSA Accumulator與Stateless Client的關係。不過RSA Accumulator 在Plasma Cash中似乎也是一個討論重點，但個人對Plasma理解不夠深，所以也就沒有近一步研究了，歡迎其他大神來補充。

最後推薦想要更全面的理解RSA Accumulator的朋友可以看一下下面這段Benedikt Bünz（他就是跟Podcast受邀人Ben Fisch一起發了上面那篇Paper的人）的介紹。他裡面對於Accumulator如何應用在UTXO set上面有很全面的剖析，相信大家看完都會很有收穫的。

Benedikt Bünz on RSA Accumulators

最後還是謝謝大家有耐心看完，希望對你有幫助。如果有疑慮或是發現我寫錯的，也歡迎留言討論指教啦！

Reference

The Stateless Client Concept
Accumulators, scalability of UTXO blockchains, and data availability
History, state, and asynchronous accumulators in the stateless model
RSA Accumulators for Plasma Cash history reduction

《Anton Cheng》授權轉載