跳到正文
Financial Context Wiki

密碼學累加器

一份以驗證為重點的密碼學累加器指南，涵蓋 RSA 與雜湊式設計、成員與非成員見證、動態更新、區塊鏈用途及維運風險。

更新於

僅供教育用途，不構成投資建議或密碼學實作建議。累加器證明所驗證的是相對於某一項承諾的聲明，而不是底層資料、共識狀態或資料可用性本身。

直接答案

密碼學累加器用一個短值對集合做出承諾，並讓驗證者透過精簡的見證，核驗某個元素是否屬於所承諾的集合。有些方案也能證明非成員關係。驗證者需要累加器值、元素、見證以及方案的公開參數，但不需要集合中的其他所有元素。

集合變更後必須重建的累加器稱為靜態累加器；能在新增或刪除元素時有效率地更新累加器與見證的稱為動態累加器；同時支援成員證明和非成員證明的稱為通用累加器。這些標籤描述的是彼此獨立的能力，動態方案並不會自動成為通用方案。

區塊鏈可以對交易、未花費輸出、帳戶、驗證者或撤銷紀錄做出承諾。較小的承諾可以減少部分參與者持有的狀態，但系統仍須散布底層資料和目前的見證、驗證更新、處理鏈重組，並規定誰有權變更集合。

運作方式

  1. 精確定義集合。 定義標準的元素編碼、重複項目的處理方式、適用時的排序規則、域分離，以及承諾的確切版本。針對一種編碼或狀態根的證明，對另一種編碼或狀態根不提供任何保證。

  2. 執行方案的設定程序。 雜湊式累加器可能只使用公開的雜湊參數。RSA 累加器使用未知階群，通常由 RSA 模數 N 構成；安全性要求未獲授權的一方無法利用其因數分解。其他方案可能使用配對、類群、格或額外公開參數，並各有不同的信任假設。

  3. 將元素映射至代數結構。 在簡化的 RSA 結構中，每個元素 x_i 都以確定性方式映射為互不相同的質數代表 p_i。以 g 為底，累加器為：

    A = g^(p_1 * p_2 * ... * p_n) mod N

  4. 建立成員見證。 對於以 p_i 表示的元素，從指數中略去它對應的因子：

    w_i = g^(product of p_j for all j != i) mod N

  5. 對照確切的累加器驗證。 驗證者檢查輸入是否採用標準形式，並計算：

    w_i^(p_i) mod N = A

    在方案的安全性假設下，要讓集合之外的元素滿足此等式，應當在計算上不可行。但此等式並不能證明元素本身真實或已獲授權。

  6. 分別處理更新和非成員關係。 動態方案規定新增和刪除如何改變 A，以及如何重新整理受影響的見證。通用方案另行提供非成員見證和驗證演算法。實作必須拒絕過期見證，以及綁定至其他狀態的更新。

  7. 按照實際成本比較雜湊式結構。 從廣義來說，Merkle 樹也是雜湊式累加器：它的根很短，但成員證明包含路徑上的相鄰雜湊，因此其大小隨葉節點數量呈對數成長。RSA 類方案可以提供固定大小的單一見證，但證明產生、見證維護、設定和計算各有不同成本。

計算範例

  • Merkle 證明的大小。 一棵擁有 1,048,576 = 2^20 個葉節點的平衡二元 Merkle 樹，需要 20 個相鄰雜湊來構成一條包含路徑。若雜湊為 32 位元組，則在計入葉節點資料、位置位元和序列化開銷之前，證明大小為 20 * 32 = 640 bytes。根仍為 32 位元組。
  • 大小固定不等於工作量固定。 在簡化的 RSA 結構中，集合增大時，A 和單一 w_i 仍各為一個群元素。然而，乘積指數、質數代表產生、批次更新以及更新後見證的散布，仍可能需要大量計算或輔助資料。
  • UTXO 累加器改變了誰儲存什麼。 緊湊狀態節點可以持有未花費輸出的累加器，並且只有在收到輸出及其目前的成員證明時才驗證一筆花費。其他參與者仍須保留足夠的狀態來產生這些證明；更新還必須刪除已花費輸出並加入新建立的輸出。
  • 撤銷沿用相同的邊界。 憑證持有人可以證明某個識別碼仍在有效成員累加器中，也可以用通用設計證明它不在撤銷集合中。證明驗證的是發行者所承諾的集合，而不是發行者採用了公平或正確的撤銷政策。

風險

  • 使用含糊或非標準的元素編碼，讓同一個邏輯項目能夠映射為不同值。
  • 錯誤地將元素映射為質數代表，或未採用方案要求的碰撞控制措施。
  • 信任其因數分解可能已被設定方或攻擊者掌握的 RSA 模數。
  • 未核驗紀錄、參與者假設和參數綁定，就認定多方設定儀式是安全的。
  • 允許管理員在沒有經過驗證的遷移規則時替換公開參數或累加器版本。
  • 對照過期、尚未最終確定或由攻擊者選定的累加器值驗證見證。
  • 採用來自錯誤區塊、分支、時期或集合版本的新增、刪除或見證更新。
  • 誤以為成員見證也能證明元素的有效性、所有權、授權或經濟價值。
  • 誤以為短承諾能讓底層集合變得可用或可復原。
  • 遺失建立目前見證所需的資料或服務，導致有效狀態無法使用。
  • 在應用程式暗中依賴不存在性證明時，省略非成員支援。
  • 將 Merkle 路徑、RSA 見證、多項式開啟和有效性證明混為可互換的物件。
  • 忽視刪除成本、見證更新流量、證明產生延遲或阻斷服務輸入。
  • 未將證明綁定至協定、鏈、合約、狀態根、域和序列化版本。
  • 在沒有獨立測試向量的情況下，依賴單一未經稽核的實作或自訂算術。
  • 誤以為傳統 RSA、配對或離散對數安全性在面對具有密碼學意義的量子電腦時依然成立。

常見誤解

  • 累加器包含集合的壓縮副本。 它是具有綁定性的承諾，而不是可逆的封存檔。
  • 每種累加器都能證明不存在性。 非成員關係必須採用為此能力而設計並經過驗證的方案。
  • 見證大小固定代表總成本固定。 設定、證明產生、更新、儲存和見證散布仍是彼此獨立的成本。
  • 無狀態代表沒有人儲存狀態。 某些參與者必須保留或重建足夠的資料，才能建立元素、更新和見證。
  • 有效證明代表所承諾的項目是真實的。 它只是在特定假設下，將該項目與一項經過驗證的承諾連結起來。
  • Merkle 樹與 RSA 累加器具有相同的信任和效能特性。 它們都用於集合承諾，但採用不同的假設、證明大小、更新流程和失效模式。

相關主題

來源

導覽

搜尋知識庫...