密碼學累加器

密碼學累加器把一整個元素「集合」壓縮成單一個短值，同時仍讓你能以極小的見證，證明「x 在集合中」（成員資格）——或證明它不在（非成員資格）——而完全不必列出集合本身。可以把它想成一個支援簡潔包含證明的集合雜湊。

主要有兩大家族。默克爾樹是雜湊式累加器：根承諾了集合，而成員證明是一條 O(log n) 的認證分支。RSA 累加器則同時給出常數大小的累加器「與」見證：A = g^(各元素質數之積) mod N；某成員的見證是去掉該成員因子後的累加器，驗證就是一次模冪運算——但它需要可信設置，因為模數 N 的因式分解是有毒廢料。雙線性配對累加器是另一個常數大小的選項。

在區塊鏈中，累加器承諾了精簡的狀態。無狀態用戶端可攜帶一個對 UTXO 集合的常數大小承諾，並在不儲存完整集合的情況下證明某枚幣存在；RSA 累加器正是為此、以及為撤銷清單而被探討。動態累加器支援新增與刪除元素，但實務上的麻煩是：每一個既有見證屆時都必須更新。向量承諾與 KZG（用於 Verkle 樹與 danksharding）是其近親，提供常數大小的證明。