Madars Virza | Research Scientist
Madars recently completed his MIT PhD thesis on zero-knowledge cryptography. His publications on zkSNARKs laid the foundation for the Zerocash protocol. Madars has presented his work at conferences around the world. He is a scientist for both the A.I. Initiative and the Digital Currency Initiative at the Media Lab.
Projects
Publications
Abstract:
We design, implement, and evaluate a zero knowledge succinct non-interactive argument (SNARG) for Rank-1 Constraint Satisfaction (R1CS), a widely-deployed NP language undergoing standardization. Our SNARG has a transparent setup, is plausibly post-quantum secure, and uses lightweight cryptography. A proof attesting to the satisfiability of n constraints has size 𝑂(log2𝑛)O(log2n); it can be produced with 𝑂(𝑛log𝑛)O(nlogn) field operations and verified with O(n). At 128 bits of security, proofs are less than 250kB250kB even for several million constraints, more than 10×10× shorter than prior SNARGs with similar features.
A key ingredient of our construction is a new Interactive Oracle Proof (IOP) for solving a univariate analogue of the classical sumcheck problem [LFKN92], originally studied for multivariate polynomials. Our protocol verifies the sum of entries of a Reed–Solomon codeword over any subgroup of a field.
We also provide 𝚕𝚒𝚋𝚒𝚘𝚙libiop, a library for writing IOP-based arguments, in which a toolchain of transformations enables programmers to write new arguments by writing simple IOP sub-components. We have used this library to specify our construction and prior ones, and plan to open-source it.
By Ethan Heilman (Boston Uni), Neha Narula (MIT Media Lab), Garrett Tanzer (Harvard), James Lovejoy (MIT Media Lab), Michael Colavita (Harvard), Madars Virza (MIT Media Lab), and Tadge Dryja (MIT Media Lab)
We present attacks on the cryptography formerly used in the IOTA blockchain, including under certain conditions the ability to forge signatures. We developed practical attacks on IOTA’s cryptographic hash function Curl-P-27, allowing us to quickly generate short colliding messages. These collisions work even for messages of the same length. Exploiting these weaknesses in Curl-P-27, we broke the EU-CMA security of the former IOTA Signature Scheme (ISS). Finally, we show that in a chosen-message setting we could forge signatures and multi-signatures of valid spending transactions (called bundles in IOTA).
Auditing and financial oversight are critical to proving institutions are complying with regulation. This paper presents zkLedger, the first system to protect ledger participants’ privacy and provide fast, provably correct auditing.
Videos and Lectures
