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

##### Abstract

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)
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
2022-06-16: revised
See all versions
Short URL
https://ia.cr/2022/170

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 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{https://eprint.iacr.org/2022/170}},
url = {https://eprint.iacr.org/2022/170}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.