Reckle Trees: Updatable Merkle Batch Proofs with Applications
发表信息
作者
- Charalampos Papamanthou
- Shravan Srinivasan
- Nicolas Gailly
- Ismael Hishon-Rezaizadeh
- Andrus Salumets
- Stjepan Golemac
笔记
Abstract 与GPT翻译 We propose Reckle trees, a new vector commitment based on succinct RECursive arguments and MerKLE trees. Reckle trees’ distinguishing feature is their support for succinct batch proofs that are updatable - enabling new applications in the blockchain setting where a proof needs to be computed and efficiently maintained over a moving stream of blocks. Our technical approach is based on embedding the computation of the batch hash inside the recursive Merkle verification via a hash-based accumulator called canonical hashing. Due to this embedding, our batch proofs can be updated in logarithmic time, whenever a Merkle leaf (belonging to the batch or not) changes, by maintaining a data structure that stores previously-computed recursive proofs. Assuming enough parallelism, our batch proofs are also computable in O(log n) parallel time - independent of the size of the batch. As a natural extension of Reckle trees, we also introduce Reckle+ trees. Reckle+ trees provide updatable and succinct proofs for certain types of Map/Reduce computations. In this setting, a prover can commit to a memory M and produce a succinct proof for a Map/Reduce computation over a subset I of M. The proof can be efficiently updated whenever I or M changes.
我们提出Reckle树，这是一种基于简洁递归论证（RECursive arguments）与默克尔树（MerKLE trees）的新型向量承诺方案。其核心特性在于支持可更新的简洁批量证明——这一特性为区块链环境开辟了新应用场景，其中需对不断更新的区块流进行证明计算并高效维护。我们的技术路径通过名为规范哈希（canonical hashing）的基于哈希的累加器，将批量哈希计算嵌入递归式默克尔验证过程中。得益于这种嵌入设计，每当默克尔叶节点（无论是否属于该批次）发生变动时，通过维护存储预计算递归证明的数据结构，我们的批量证明可在对数时间内完成更新。在充分并行条件下，批量证明的计算同样仅需O(log n)并行时间——与批次规模无关。作为Reckle树的自然延伸，我们还引入了Reckle+树，它为特定类型的Map/Reduce计算提供可更新且简洁的证明机制。在此框架下，证明者可对内存M作出承诺，并为M的子集I上的Map/Reduce计算生成简洁证明。当I或M发生变更时，该证明可被高效更新。
We present and experimentally evaluate two applications of Reckle+ trees, dynamic digest translation and updatable BLS aggregation. In dynamic digest translation we are maintaining a proof of equivalence between Merkle digests computed with different hash functions, e.g., one with a SNARK-friendly Poseidon and the other with a SNARK-unfriendly Keccak. In updatable BLS aggregation we maintain a proof for the correct aggregation of a t-aggregate BLS key, derived from a t-subset of a Merkle-committed set of individual BLS keys. Our evaluation using Plonky2 shows that Reckle trees and Reckle+ trees have small memory footprint, significantly outperform previous approaches in terms of updates (10× to 15×) and verification (4.78× to 1485×) time, enable applications that were not possible before due to huge costs involved (Reckle trees are up to 200× faster), and have similar aggregation performance with previous implementations of batch proofs.