帶批量添加的蓄能器
Camacho表明，在累加器的批量刪除中，更新所有見證的資訊至少與刪除的元素數量呈線性關係。
我想知道是否有批量添加的累加器，其中更新所有見證的資訊在添加的元素數量中是次線性的。在他的論文的結尾，Camacho 寫道：“這樣的累加器可以通過對集合的元素進行簽名來輕鬆實現”。但是，我只對可公開更新的累加器感興趣，任何人（不僅僅是擁有簽名密鑰的特權“經理”）都可以更新累加器。
另一個不可公開更新的累加器是 RSA 累加器，可以通過減少指數模歐拉的總和來進行批處理 $ \phi(n) $ , 由經理保密。
是否有批量添加的可公開更新的累加器？
這是一個強大的概述$$ 1 $$,僅附加具有您所需屬性的累加器。這個累加器最初是由 Reyzin 和 Yakoubov 在$$ 3 $$:
- 支持可證明的批量添加。
- 可公開更新。
- 更新所有見證的資訊在添加的元素數量上是次線性的。
我將通過例子來描述這個方案，因為形式化會很乏味，而且不太可能有啟發性。
首先，看下圖。
它由一片默克爾樹組成。有一個舊蓄電池 $ F_7 $ （橙色節點）和一個新的累加器 $ F_{18} $ （橙色和綠色節點），其中“包括” $ F_7 $ . 事實上，有一個由填充節點組成的僅附加證明（例如，節點 000、0010、00110、00111、01、1000）。
證明者儲存所有葉子和內部節點（包括根節點），而驗證者儲存大小摘要 $ O(\log{n}) $ 由所有根節點組成，其中 $ n $ 是累積元素的數量。
例如，如果你只看 $ F_7 $ （即，忽略所有綠色的東西），它的摘要 $ d_7 $ 由組成 $ {h_{000}, h_{0010}, h_{00110}} $ 在哪裡 $ h_w $ 表示節點的雜湊 $ w $ . 同樣，摘要 $ d_{18} $ 的 $ F_{18} $ 由組成 $ {h_0, h_{1000}} $ .
關鍵思想
該方案只是對 Crosby 和 Wallach 的歷史樹的一個小調整 $$ 2 $$.
添加元素
為了向累加器添加一個元素，證明者將一個葉子附加到森林並**僅在必要時合併節點，**以便所有樹的大小都是 2 的冪。
我認為最好在紙上嘗試一個範例，看看何時合併節點以保持此不變性。正式地，讓 $ w = v|b $ 用前綴表示一個節點 $ v $ 與 $ b\in{0,1} $ 然後讓 $ v|\bar{b} $ 表示它的兄弟，其中 $ \bar{b} = 1-b $ . 這個想法是只合併兄弟節點（即，我們只合併 $ v|0 $ 和 $ v|1 $ 僅當它們都在森林中時）。
例如，節點 1000 沒有（右）兄弟，因此它不能與任何東西合併。相反，節點 01 和節點 00 是兄弟節點，因此它們被合併，從而產生父節點 0。這個過程**可以遞歸地繼續。**例如，考慮添加節點 00111 時發生的情況：00111 與 00110 的第一次合併觸發了另外兩次合併，最終創建了節點 00。
會員證明
元素的證明 $ x $ 在摘要中 $ d $ 只是一條 Merkle 路徑 $ x $ 到根之一 $ d $ . 例如，下圖顯示了兩個不同元素的證明 $ x $ 和 $ y $ 文字摘要 $ d = h_0 $ . 證明為 $ x $ 由填充節點組成（即， $ \pi_x = {h_{00000}, h_{0001}, h_{001}, h_{01}} $ )，而證明 $ y $ 由粗體圓圈節點組成（即， $ \pi_y = {h_{00101},h_{0011}, h_{000}, h_{01}} $ ）。（碰巧證明共享一個公共節點 $ h_{01} $ 我以不同的方式突出顯示。）
僅附加證明
如果您再次查看概覽圖片，您會發現兩者之間的僅附加證明 $ F_7 $ 和 $ F_{18} $ 由來自_ $ F_7 $ 到新的根源 $ F_{18} $ . 具體來說，具有 $ \times $ 對它們進行“去重”：它們是通過對填充節點進行散列計算得出的。
證明還包括額外的根，如 $ h_{1000} $ （圖中也有填寫）。這個證明與歷史樹中的僅附加證明非常相似$$ 2 $$（除了在那篇論文中稱為一致性證明）。
重要的是，僅附加證明的大小 $ d_m $ 和 $ d_n, m<n $ 是 $ O(\log{n}) $ .
更新成員證明（在僅附加證明之後）
在帶有摘要的舊累加器中批量添加後 $ d $ ，驗證者從證明者那裡收到一個僅附加的證明，並確保沒有被惡意刪除 $ d $ 或修改。正如您在問題中指出的那樣，驗證者有一些舊的成員資格證明和舊的摘要 $ d $ 他想要更新，以便他們可以驗證新的摘要 $ d’ $ .
首先，請注意舊的成員資格證明是舊根的兄弟路徑。 第二，請注意， $ d $ 和 $ d’ $ 是從舊根到新根的兄弟路徑。 第三，回想一下僅附加證明是 $ O(\log{n}) $ 大小，在哪裡 $ n $ 是新累加器的大小。
到現在為止，您可能會注意到，可以很容易地使用僅附加證明“組合”舊的成員資格證明，以在新摘要中獲得新的成員資格證明 $ d’ $ . 這必然涉及舊成員證明數量的線性計算，因為驗證者需要全部更新它們。然而，更新舊成員證明所需的頻寬是次線性的，因為它只是 $ O(\log{n}) $ 大小的僅附加證明。
例如，舊的證明 $ y $ 寫給 $ d $ 曾是 $ \pi_y = {h_{00101}} $ 新的證明是 $ \pi_y’ = {h_{00101},h_{0011},h_{000}, h_{01}} $ . 注意驗證者需要計算 $ h_{0011} $ 來自它的兩個孩子：來自 $ F_7 $ 和第 8 片葉子 $ F_18 $ . 驗證者可以很容易地做到這一點，因為它擁有所有必要的資訊：第 8 片葉子是僅附加證明的一部分。
一般來說，可以說這適用於任何元素 $ x $ 在任何摘要中 $ d $ 帶有更新的摘要 $ d’ $ . 同樣，直覺是僅附加證明由從舊根到新根的“去重”Merkle 兄弟路徑組成（例如，沒有意義包括 $ h_{0011} $ 因為它可以從包含的子項中重新計算）。
結論
存在一個強大的、可公開更新的累加器，它具有“批量添加”功能，可以使用次線性頻寬更新舊的成員資格證明。對克羅斯比和瓦拉赫優雅的歷史樹稍作調整$$ 2 $$施工正是如此。
希望這有意義並有所幫助！
參考
$$ 1 $$ “抗碰撞雜湊的強累加器”，作者 Philippe Camacho、Alejandro Hevia、Marcos Kiwi 和 Roberto Opazo $$ 2 $$ “Efficient Data Structures for Tamper-Evident Logging”，作者：Scott A. Crosby 和 Dan S. Wallach $$ 3 $$ “分佈式 PKI 的高效非同步累加器”，Leonid Reyzin 和 Sophia Yakoubov
