Curve trees: Practical and transparent Zero-Knowledge accumulators
发表信息
作者
- Matteo Campanelli
- Mathias Hall-Andersen
- Simon Holmgaard Kamp
笔记
In this work we improve upon the state of the art for practical zero-knowledge for set membership, a building block at the core of several privacy-aware applications, such as anonymous payments, credentials and whitelists. This primitive allows a user to show knowledge of an element in a large set without leaking the specific element. One of the obstacles to its deployment is efficiency. Concretely efficient solutions exist, e.g., those deployed in Zcash Sapling, but they often work at the price of a strong trust assumption: an underlying setup that must be generated by a trusted third party.
在这项工作中，我们改进了集合成员关系实用零知识证明的技术水平，这一核心构件支撑着多项注重隐私的应用，如匿名支付、凭证及白名单机制。该基础技术让用户能够证明自己知晓某个大集合中的元素，而无需透露具体是哪一个元素。然而，其实际应用的一大障碍在于效率问题。虽然已有具体高效的解决方案——例如Zcash Sapling中部署的方案——但这些方案往往以强信任假设为代价：必须依赖可信第三方生成的基础设置。
To find alternative approaches we focus on a common building block: accumulators, a cryptographic data structure which compresses the underlying set. We propose novel, more efficient and fully transparent constructions (i.e., without a trusted setup) for accumulators supporting zero-knowledge proofs for set membership. Technically, we introduce new approaches inspired by “commit-and-prove” techniques to combine shallow Merkle trees and 2-cycles of elliptic curves into a highly practical construction. Our basic accumulator construction—dubbed Curve Trees—is completely transparent (does not require a trusted setup) and is based on simple and widely used assumptions (DLOG and Random Oracle Model). Ours is the first fully transparent construction that obtains concretely small proof/commitment sizes for large sets and a proving time one order of magnitude smaller than proofs over Merkle Trees with Pedersen hash. For a concrete instantiation targeting 128 bits of security we obtain: a commitment to a set of any size is 256 bits; for ∣S∣=240 a zero-knowledge membership proof is 2.9KB, its proving takes 2s and its verification 40ms on an ordinary laptop.
为探寻替代方案，我们聚焦于一个通用构建模块——累加器，这是一种能压缩底层集合的密码学数据结构。针对支持集合成员零知识证明的累加器，我们提出了新颖、更高效且完全透明（即无需可信设置）的构造方法。技术上，我们借鉴”承诺-证明”技术，将浅层默克尔树与椭圆曲线的2-周期巧妙结合，形成高度实用的结构。我们的基础累加器构造（称为”曲线树”）完全透明（无需可信设置），基于简单且广泛采用的假设（离散对数与随机预言模型）。这是首个完全透明的构造方案，针对大规模集合能实现具体微小化的证明/承诺体积，其证明时间比采用Pedersen哈希的默克尔树证明快一个数量级。在实现128位安全性的具体实例中，我们取得：对任意大小集合的承诺仅占256位；当集合规模∣S∣=2⁴⁰时，零知识成员证明仅2.9KB，在普通笔记本电脑上证明耗时2秒，验证仅需40毫秒。
Using our construction as a building block we can design a simple and concretely efficient anonymous cryptocurrency with full anonymity set, which we dub Vcash. Its transactions can be verified in ≈80ms or ≈5ms when batch-verifying multiple (>100) transactions; transaction sizes are 4KB. Our timings are competitive with those of the approach in Zcash Sapling and trade slightly larger proofs (transactions in Zcash Sapling are 2.8KB) for a completely transparent setup.
以我们的构建为基础，我们能够设计出一种既简单又实际高效的匿名加密货币——我们称之为Vcash，它具备完整的匿名集。单笔交易的验证时间约为80毫秒，而批量验证多笔（超过100笔）交易时，时间可缩短至约5毫秒；每笔交易的大小为4KB。在性能上，我们的方案与Zcash Sapling的方法相当，虽然证明略大（Zcash Sapling中的交易大小为2.8KB），但换来了完全透明的设置过程。