每晚八點，我們在社區分享知識。

** 樂樂：sensus113
美果大冰：xj73226**

備註入羣，謝謝！

Plasma、Plasma Cash 都面臨這樣的問題：用戶需要保留的歷史數據量以及發送硬幣時需要發給接收方的數據量。
譬如，有條 Plasma 鏈每分鐘被提交一個區塊，每個區塊每分鐘約 216 筆交易（每秒約 1000 筆交易）。再假設每個用戶把硬幣分到約 10 個片斷上。
那麼，爲獲取成功退出所需的全部信息，每個片斷每個區塊都需要一個長度約 16 的 Merkle 分支，一年的話就是 16 個哈希值 *32 字節 *50 萬分鍾 *10 個片斷，約 2.5 GB。也就是說，轉賬、原子交換等類似操作中，這是必須傳輸的數據量。

使用 RSA 累加器可以提高效率。RSA 累加器是一種功能與 Merkle 樹相似的數據結構，能將大量數據壓縮成單個固定大小的“根”，有了數據和根，就可以構建一個能夠“見證人”證明‘數據中任何特定值都屬於（∈）該根表示的數據’。操作如下：選出一個值因數未知的大值 N 以及代表空累加器的生成器 g （例如 g
= 3）。添加 v 值到累加器 A 時，設新累加器 A\’=Av。證明 v 值屬於累加器 A 時，可使用指數知識證明（見下文）來證明知道能使（gv） x =
A 的輔因數 x （注意 x 值有可能非常大，原因是 x 與元素數量呈線性關係，也就是爲何要藉助證明手段而非直接提供 x 值）。

譬如，想要添加 3、5、11 到累加器。則，A = g165。爲證明 3 是 A 的一部分（現在開始用 [g …
A] 表示範圍），使用知識證明方案證明有某輔因數 x 使得（g3） x = A。這種情況下 x = 55，但是有些時候 x 值可能變得非常大。

Wesolowski 曾描述過一種知識證明方案。令 h = gv，z = hx。 選擇等於 hash （h，z） mod N 的 B【B=hash （h，z） mod N】。
計算 b = hfloor （x/B），r = x mod B。 證明就是（b，z），可通過檢查 bBhr = z 來驗證（完整性證明：bB hr = hB *
floor （x/B）+ xmodB = hx）。 注意，此證明大小恆定。

證明某個值 v 不屬於 [g … A] 時，只需要證明自己知道能使 0

現在，規定 Plasma
Cash 根必須帶交易 Merkle 樹以及該區塊中被修改的硬幣指數的 RSA 累加器。退出遊戲中使用交易需要提供 Merkle 證明和 RSA 累加器隸屬證明（proof
of
membership）。也就是說非隸屬 RSA 證明足以向用戶證明該區塊中不包含可在退出遊戲用作交易的數據。然而，我們使用的 RSA 累加器也是累積的，意思是第一個區塊中使用的生成器可以是 3，但是後續的每個區塊中使用的生成器則是前一個區塊累加器的輸出。如此，支持了批量非隸屬證明：爲證明區塊 n
….
n+k 中不涉及給定的硬幣索引，使用區塊 n 的前狀態作發生器，根據累加器在區塊 n+k 之後的後狀態生成非隸屬證明。用戶收到此非隸屬證明時，就能確信無法爲 n
…. n+k 範圍內的任何區塊生成隸屬證明。

這也意味着硬幣的歷史證明大小從每個 Plasma 區塊一個 Merkle 分支變成該硬幣每筆交易兩個 RSA 累加器證明：證明交易發生的隸屬證明以及證明某範圍內交易未發生的非隸屬證明。若每個硬幣平均每天交易一次，且非隸屬 RSA 證明大小約 1kB，一年的總大小約 1Kb*
365 天*10 個片斷，也就是 3.6 MB。

硬幣數量很大時，同樣能進一步優化。可對非隸屬證明批量處理，譬如，若能證明 Ag50 是 g143 的一個冪，則可知 logg （A）= -50 mod143，說明 Ag50 不是 11 或 13 的倍數。這種操作適用於幾百個指數的情形，但如果說想要非常精細的面額，可以批量更多。

樸素 RSA Plasma
Cash 實施中，爲每個硬幣分配一個唯一的素數作硬幣 ID，且該區塊的 RSA 累加器更新包括已花費硬幣的 ID。對於 n 寬度片段用戶，包含證明（proof of
inclusion）大小爲 O （N），排除證明（proof of
exclusion）爲 O （N），運營商開銷爲 O （N），那麼，想要實現非常細化的面額，此方案顯然不夠有效。

首先，需要着手將排除證明大小降低至 O （log （N）），代價是一個硬幣的包含證明大小增至 O （log （N））（N 個硬幣的證明大小僅增加兩倍）。生成一個與硬幣索引相關的素數以及與二叉樹中節點對應的索引子集樹（一棵素數、索引子集樹），假設有 4 個硬幣，如下所示：

要包含硬幣 7，設 A\’= A237；包含硬幣 13 和 17，設 A\’= A2513*17；

包含 11 和 13，設 A\’= A2351113。譬如，想要證明硬幣 17 被包含，需要證明 2517 屬於累加器（即 A\’ 是 A2517 的已知冪）。

爲證明對齊片（aligned
slice）是非隸屬的（一片對應一顆子樹），單個（譬如 3 的）非隸屬證明即可。任意片數都可以構造一個批量處理了子樹的 log （n）證明的證明；一般而言，任何片 [a，b] 都可以分解爲 log （b-a）個相鄰的對齊片。譬如，證明 11、13 和 17 都不屬於累加器時，需要證明 11 和 5 都被排除在外，所以只要證明 logA （A\’） mod55 的值不是 5 或 11 的倍數即可。因此，能夠以緊湊地方式證明非隸屬範圍。遺憾的是，證明隸屬的範圍仍需要所有單個硬幣的批量證明。

其實，這個問題可以通過進一步擴展該方案處理掉，就是搞一片 Merkle 林：

爲證明單一對齊片被包含，需要證明以下幾點：

· 子樹對應的葉子值（及其到該根的所有祖先）被包含。

· 林中任何上層樹中的葉子值未被包含。

· 子樹對應的值未包含在林中任何下層樹中。

用下圖解釋一下。 假設要證明硬幣 1 被包含（左數第二枚硬幣）。 需要證明被包含的值標綠，證明未包含的值標紅：

現在，假設要證明含硬幣 0、1 的對齊片被包含。

一般原則是每 2k 大小級上使用單獨的樹證明一個對齊片被包含，且此隸屬證明包含‘未包含與該片在更高或更低級相交的對齊片’的證明。

現在，爲證明未包含某對齊片，我們進行如下證明（以硬幣 0、1 爲示例）：

如此，證明：

  1. 對齊片 [0 … 3] 不可能被包含（否則需要包含素數 2，但已經證明素數 2 被排除）

  2. 對齊片 [0 … 1] 不可能被包含（否則需要包含素數 7）

  3. 單個硬幣 0 或 1 不可能被包含（否則證明中都需要包含素數 13）

N 個硬幣的全部證明大小都爲 log （n），也包括了驗證、傳輸及構造成本。若所有交易只觸及兩個硬幣的對齊片，那麼任何人都不需要使用素數 19、23、29 或 31 做任何計算。

Plasma
Cash 實施使用數量巨大的硬幣（好比 250 個）時，這個功能就非常有用了。至於如何爲這麼多硬幣分配素數，理想情況下，用到的素數越小越好，原因是爲這些素數生成證明的效率更高。

還有個辦法是以確定性方式按需爲任何給定索引生成素數。鑑於我們對素數間隔有一定的瞭解，只需將 x 映射到 25000*x 以上的第一個素數即可。問題是確定性 100％有效素性測試（deterministic
100% effective primality
tests）運行時間往往很高，因此難以用於鏈上。那麼更簡單的方法則是進行一輪預先計算，生成前 240 個素數的列表然後存儲在 Merkle 樹中；鏈上使用素數的話，需要與 Merkle 分支相結合，而客戶端可以在本地檢檢查這些計算。

每晚八點，我們在社區等你。

我們是祖國的花朵

Nervos CKB 唯一官網：Nervos.org

歡迎關注 Nervos Fans

Nerovs CKB 愛好者社區

Nervos Fans 如下頻道：

NervosFans twitter：@nervosfans

NervosFans微博：@NervosFans

NervosFans 微信公號：Nervosfans**

入羣請加樂樂微信：sensus113

美果大冰微信：xj73226

備註入羣，謝謝！

長按識別二維碼關注：Nervosfans

**
**

點擊 _“閱讀原文 _”查看原文