Efficient Cryptographic Arguments and Proofs – Or How I Became a Fractional Monetary Unit

In 2008, unfortunate investors found their life savings in Bernie Madoff’s hedge fund swindled away in a $65 billion Ponzi scheme. Imagine yourself back in time with an opportunity to invest in his fund that had for years delivered stable returns and pondering Madoff’s assurance that the fund was solvent and doing well. Unfortunately, neither Madoff nor any other hedge fund manager would take kindly to your suggestion of opening their books to demonstrate the veracity of the claim. And even if you somehow got access to all the internal data, it might take an inordinate effort to go through the documents.

Modern day computers share your predicament. When a computer receives the result of a computation from another machine, it can be critical whether the data is correct or not. If the computer had feelings, it would wish for the data to come with evidence of correctness attached. But the sender may not wish to reveal confidential or private information used in the computation. And even if the sender is willing to share everything, the cost of recomputation can be prohibitive.

In 1985, Goldwasser, Micali and Rackoff proposed zero-knowledge proofs as a means to give privacy-preserving evidence. Zero-knowledge proofs are convincing only if the statement they prove is true, e.g. a computation is correct; yet reveal no information except for the veracity of the statement. Their seminal work shows verification is possible without having to sacrifice privacy.

In the following three decades, cryptographers have worked tirelessly at reducing the cost of zero-knowledge proofs. Six years ago, we began the ERC funded project Efficient Cryptographic Argument and Proofs aimed at improving the efficiency of zero-knowledge proofs. In September 2018 the project came to its conclusion and throwing usual academic modesty aside, we have made remarkable progress, and several of our proof systems are provably optimal (up to a constant multiplicative factor).

As described in an earlier post, we improved the efficiency of generalised Sigma-protocols, reducing both the number of rounds in which the prover and verifier interact and the communication, with a proof size around 7 kB even for large and complex statements. Our proof techniques have been optimised and implemented in the Bulletproof system, which is now seeing widespread adoption.

We also developed highly efficient pairing-based non-interactive zero-knowledge proofs (aka zk-SNARKs). Here the communication cost is even lower in practice, enabling proofs to be just a few hundred bytes regardless of the size of the statement being proved. Their compactness and ease of verification make them useful in privacy-preserving cryptocurrencies and blockchain compression.

The proof systems we just described are very compact and very efficient to verify. Lately, we shifted our attention to the last remaining efficiency bottleneck: the prover’s computation. All existing proof systems required superlinear effort for the prover, but our recent proof system showed for the first time how to achieve linear prover effort for arithmetic circuit satisfiability. By linear, we mean that the prover’s computation is bounded by a constant factor (independent of the desired security level) multiplied by the size of the arithmetic circuit, which is theoretically optimal.

For the technically inclined readers, our core idea is to use a combination of linear error-correcting codes and collision-resistant hash functions to build an additively homomorphic commitment scheme. We often use homomorphic commitments in succinct zero-knowledge proofs for two reasons

• Succinctness: a small commitment can bind the prover to a large vector of field elements. This is analogous to how a hash function can produce a compact message digest of a large bitstring.
• Additive homomorphicity: verifiable operations on the commitments correspond to adding the secret committed vector together. Normal hash functions are not homomorphic, but some commitment schemes are. This means simple operations on compact commitments enable the verification of many field additions in parallel.

Our new commitment scheme is “virtually homomorphic” without requiring the underpinning hash function to be homomorphic. This means we can use an arbitrary hash function instead of an expensive commitment scheme based on public-key cryptography, yet still derive all the advantages of homomorphic commitments (an idea also explored independently in Ligero.) How do we do this? Think of the vectors you want to commit to as rows in the matrix A illustrated below.

The prover applies an error-correcting code to each row, which gives her a wider matrix B. She then hashes each column, and the sets of hash-values constitute her commitment to B (and implicitly A). Later in the zero-knowledge proof, the verifier will ask her to open the commitment to a particular linear combination of the rows in A. She, therefore, sends him the linear combination of rows vector. But how does he know whether the linear combination is correct or whether she is lying? This is where the hash-values come into play. The verifier spot-checks by asking her to reveal some of the columns, for which he can then recompute and verify the hash values.

Moreover, because it is a linear error-correcting code, he can also encode the received linear combination and check that it is correct for the revealed columns. By the error-detecting properties of the encoding, this then means that the full linear combination she sent to him must be correct with high probability. Notice she only sends hash-values and reveals a few column vectors, so communication is less than the size of the matrix A and similarly, the verifier only has little computation to do, so we now have a highly efficient “virtually homomorphic” commitment scheme.

Going beyond arithmetic circuit satisfiability, most recently we investigated verifying program execution. Here we imagine the prover has executed a program on some input (secret or public), sent the result to the verifier, and now wants to convince her the output is correct. Our zero-knowledge proof system (a so-called zk-STARK) does well on all performance dimensions:

• Near-constant overhead for the prover
• Sublinear communication
• Sublinear verification time

Moreover, our proof system relies on collision-resistant hash functions, which are believed to be post-quantum secure.

Zero-knowledge proofs are a very active area with many researchers and developers making strong contributions. They are being popularised under names such as Bulletproofs, SNARKs and STARK, derive additional efficiency from impressive advances in compilers that translate correct code execution to zero-knowledge amenable statements; inspire the launch of start-up companies, and are now becoming mature enough for standardisation efforts. We find it very exciting to work in such an active area and seeing almost immediate adoption of our research.

A lot of our impact has been in the blockchain industry; especially in the construction of privacy-friendly cryptocurrencies. A common design paradigm is that anonymous users hold commitments to secret amounts. To spend money, they then use zero-knowledge proofs to demonstrate they are legitimate holders of money, and the transactions are within their spending limits. Recipients get the guarantee from the proofs that the transfer of money is valid, and the senders’ privacy is preserved by the zero-knowledge property such that nobody can tell who spent the money.

If you wondered about the odd second title for the blog post, now comes the explanation. Beam is a recent start-up project in such privacy-friendly cryptocurrencies and just launched their main-net on January 3 this year. Their system includes use of discrete logarithm-based proofs tracing their origin to the ECAP project. And they decided to bestow me a unique honour by naming their smallest unit of exchange Groth (disclaimer: neither I nor UCL are involved in Beam), so 1 Beam = 100,000,000 Groth.