In this work, we improve the scalability of these techniques by proposing new schemes of fully distributed ZKPs. Our schemes can improve the efficiency and the scalability of ZKPs using multiple machines, while the communication among the machines is minimal. With our schemes, the ZKP generation can be distributed to multiple participants in a model similar to the mining pools. Our protocols are based on Plonk, an efficient zero-knowledge proof system with a universal trusted setup. The first protocol is for data-parallel circuits. For computation of \(M\) sub-circuits of size \(T\) each, using \(M\) machines, the prover time is \(O(T\log T + M \log M)\), while the prover time of the original Plonk on a single machine is \(O(MT\log (MT))\). Our protocol incurs only \(O(1)\) communication per machine, and the proof size and verifier time are both \(O(1)\), the same as the original Plonk. Moreover, we show that with minor modifications, our second protocol can support general circuits with arbitrary connections while preserving the same proving, verifying, and communication complexity. The technique is general and may be of independent interest for other applications of ZKP.
We present zkBridge, the first trustless, permissionless, extensible, universal, and efficient cross-chain bridge. With succinct proofs, zkBridge not only guarantees strong security without external assumptions, but also significantly reduces on-chain verification cost. We propose novel succinct proof protocols that are orders-of-magnitude faster than existing solutions for workload in zkBridge. With a modular design, zkBridge enables a broad spectrum of applications, including message passing, token transferring, and other computational logic operating on state changes from different chains. We have already implemented zkBridge between certain chains and evaluated its end-to-end performance. We encourage community members to join us to extend zkBridge to other chains; please fill in the form if you are interested in contributing to this project towards building a universal, secure foundation for multi-chain interoperability...
Zero-knowledge proof is a powerful cryptographic primitive that has found various applications in the real world. However, existing schemes with succinct proof size suffer from a high overhead on the proof generation time that is super-linear in the size of the statement represented as an arithmetic circuit, limiting their efficiency and scalability in practice. In this paper, we present Orion, a new zero-knowledge argument system that achieves \(O(N)\) prover time of field operations and hash functions and \(O(\log^2 N)\) proof size.…
Read Paper View RepoWe propose a new doubly efficient interactive proof protocol for general arithmetic circuits. The protocol generalizes the interactive proof for layered circuits proposed by Goldwasser, Kalai and Rothblum to arbitrary circuits, while preserving the optimal prover complexity that is strictly linear to the size of the circuits. We then construct a new zero knowledge argument scheme for general arithmetic circuits using our new interactive proof protocol together with polynomial commitments. Our experiments show that it only takes 0.3 seconds to generate the proof for a circuit with more than 600,000 gates, which is 13 times faster than the original interactive proof protocol on the corresponding layered circuit. Our implementation can take general arithmetic circuits directly, without transforming them to layered circuits with a high overhead on the size of the circuit.…
Read PaperWe present a new succinct zero knowledge argument scheme for layered arithmetic circuits without trusted setup. The prover time is \(O(C + n \log{n})\) and we have succinct verifier. Our scheme only uses lightweight cryptographic primitives such as collision-resistant hash functions and is plausibly post-quantum secure. Experiments show that it only takes 53 seconds to generate a proof for a circuit computing a Merkle tree with 256 leaves, at least an order of magnitude faster than all other succinct zero knowledge argument schemes.…
Read Paper View RepoWe present Libra, the first zero-knowledge proof system that has both optimal prover time and succinct proof size/verification time. In addition Libra features an one-time trusted setup that depends only on the size of the input to the circuit and not on the circuit logic. Underlying Libra is a new linear-time algorithm for the prover of the interactive proof protocol by Goldwasser, Kalai and Rothblum (also known as GKR protocol), as well as an efficient approach to turn the GKR protocol to zero-knowledge using small masking polynomials. Our implementation shows that it takes 200 seconds to generate a proof for constructing a SHA2-based Merkle tree root on 256 leaves, outperforming all existing zero-knowledge proof systems.…
Read Paper View RepoVerifiable Secret Sharing (VSS) is a foundational cryptographic primitive that serves as an essential building block in multi-party computation and decentralized blockchain applications. One of the most practical ways to construct VSS is through a polynomial commitment, where the dealer commits to a random polynomial whose 0-th coefficient encodes the secret to be shared, and proves the evaluation of the committed polynomial at a different point to each of N verifiers, i.e., the polynomial commitment is used in a "one-to-many" fashion. In this paper, we asymptotically improve polynomial commitment with one-to-many prover batching. We propose two novel schemes. First, we propose a scheme with optimal asymptotics in all dimensions in the trusted setup setting. Second, we propose a transparent scheme whose performance approximately matches the best-known scheme in the trusted setup setting. Our scheme in the trusted setup setting improves the proof size by 20x and the verifier time by 7.8x for \(2^{21}\) parties, with a small overhead on the prover time. Our transparent polynomial commitment removes the trusted setup and further improves the prover time by 2.3x.
Read Paper"We present Hyperproofs, the first vector commitment (VC) scheme that is efficiently maintainable and aggregatable. Our proofs form a tree that can be efficiently maintained: updating all n proofs in the tree after a single leaf change only requires \(O(\log{n})\) time. Importantly, Hyperproofs are efficiently aggregatable, anywhere from 10x to 41x faster than SNARK-based aggregation of Merkle proofs. At the same time, an individual Hyperproof consists of only \(\log{n}\) algebraic hashes and an aggregation of $b$ such proofs is only \(O(\log{b\log{n}})\)-sized. As another benefit over Merkle trees, Hyperproofs are homomorphic: digests (and proofs) for two vectors can be homomorphically combined into a digest (and proofs) for their sum.
Read Paper"Devising a fair-exchange protocol for digital goods has been an appealing line of research in the past decades. In this paper, we propose an improved solution ZKCPlus for practical and flexible fair exchange. ZKCPlus incorporates a new commit-and-prove non-interactive zero-knowledge (CP-NIZK) argument of knowledge under standard discrete logarithmic assumption, which is prover-efficient for data-parallel computations. With this argument we avoid the setup issues of ZKCP and reduce seller's proving overhead, more importantly enable the protocol to handle complicated data validations. We have implemented a prototype of ZKCPlus and built several applications atop it. Our CP-NIZK argument shows an order of magnitude higher proving efficiency than the zkSNARK adopted by ZKCP. We built a realistic application of trading trained CNN models. For a 3-layer CNN containing 8,620 parameters, it takes less than 1 second to prove and verify an inference computation, and also about 1 second to deliver the parameters, which is very promising for practical use.
Read PaperCopyright ©2022 UC Regents | Email us at rdi@berkeley.edu.