Paper 2022/170

gOTzilla: Efficient Disjunctive Zero-Knowledge Proofs from MPC in the Head, with Application to Proofs of Assets in Cryptocurrencies

Foteini Baldimtsi, George Mason University
Panagiotis Chatzigiannis, George Mason University
S. Dov Gordon, George Mason University
Phi Hung Le, George Mason University
Daniel McVicker, George Mason University

We present gOTzilla, a protocol for interactive zero-knowledge 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 1-out-of-N 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 non-algebraic 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 run-time 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 non-algebraic elements.

Available format(s)
Publication info
Published elsewhere. Privacy Enhancing Technologies Symposium 2022
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
2022-06-16: revised
2022-02-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Foteini Baldimtsi and Panagiotis Chatzigiannis and S.  Dov Gordon and Phi Hung Le and Daniel McVicker},
      title = {gOTzilla: Efficient Disjunctive Zero-Knowledge Proofs from MPC in the Head, with Application to Proofs of Assets in Cryptocurrencies},
      howpublished = {Cryptology ePrint Archive, Paper 2022/170},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.