Paper 2022/170
gOTzilla: Efficient Disjunctive ZeroKnowledge Proofs from MPC in the Head, with Application to Proofs of Assets in Cryptocurrencies
Abstract
We present gOTzilla, a protocol for interactive zeroknowledge proofs for very large disjunctive statements of the following format: given publicly known circuit $C$, and set of values $Y = \{y_1, \ldots, y_n\}$, prove knowledge of a witness $x$ such that $C(x) = y_1 \lor C(x) = y_2 \lor \cdots \lor C(x) = y_n$. These type of statements are extremely important for the proof of assets (PoA) problem in cryptocurrencies where a prover wants to prove the knowledge of a secret key $sk$ that associates with the hash of a public key $H(pk)$ posted on the ledger. We note that the size of $n$ in popular cryptocurrencies, such as Bitcoin, is estimated to 80 million. For the construction of gOTzilla, we start by observing that if we restructure the proof statement to an equivalent of proving knowledge of $(x,y)$ such that $(C(x) = y) \land (y = y_1 \lor \cdots \lor y = y_n))$, then we can reduce the disjunction of equalities to 1outofN oblivious transfer (OT). Our overall protocol is based on the MPC in the head (MPCitH) paradigm. We additionally provide a concrete, efficient extension of our protocol for the case where $C$ combines algebraic and nonalgebraic statements (which is the case in the PoA application). We achieve an asymptotic communication cost of $O(\log n)$ plus the proof size of the underlying MPCitH protocol. While related work has similar asymptotic complexity, our approach results in concrete performance improvements. We implement our protocol and provide benchmarks. Concretely, for a set of size 1 million entries, the total runtime of our protocol is 14.89 seconds using 48 threads, with 6.18 MB total communication, which is about 4x faster compared to the state of the art when considering a disjunctive statement with algebraic and nonalgebraic elements.
Metadata
 Available format(s)
 Category
 Applications
 Publication info
 Published elsewhere. Privacy Enhancing Technologies Symposium 2022
 Keywords
 secure multiparty computation oblivious transfer zero knowledge disjunctive proofs privacy auditability cryptocurrencies
 Contact author(s)

foteini @ gmu edu
pchatzig @ gmu edu
gordon @ gmu edu
ple13 @ gmu edu
dmcvicke @ gmu edu  History
 20220616: revised
 20220220: received
 See all versions
 Short URL
 https://ia.cr/2022/170
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/170, author = {Foteini Baldimtsi and Panagiotis Chatzigiannis and S. Dov Gordon and Phi Hung Le and Daniel McVicker}, title = {{gOTzilla}: Efficient Disjunctive ZeroKnowledge Proofs from {MPC} in the Head, with Application to Proofs of Assets in Cryptocurrencies}, howpublished = {Cryptology {ePrint} Archive, Paper 2022/170}, year = {2022}, url = {https://eprint.iacr.org/2022/170} }