The 'Useless' Theory Behind Modern SNARKs (ft. Gödel Prize Winner Noam Nisan)

Noam Nisan is a Gödel Prize and Knuth Prize-winning computer scientist at the Hebrew University of Jerusalem and a principal researcher at Starkware. Justin Thaler, author of Proofs Arguments and Zero-Knowledge and co-creator of the Lasso and Jolt systems, also appears. Tim Roughgarden credits Nisan with co-founding algorithmic game theory alongside Mironin through their 1999 mechanism design paper.

Between roughly 1984 and 1989, interactive proofs extended classical mathematical proof by combining interaction and randomness, with Nisan emphasizing that either ingredient alone yields nothing fundamentally new. The intellectual trigger was Richard Lipton's proof of random self-reducibility for the permanent function, which Nisan initially suspected contained an error because the implication seemed too strong. Nisan found the basic multiprover protocol in under a week before leaving on a trip to South America with no internet access, sent it in a one-page email to about a dozen people including Avi Wigderson and Babai, and learned of Adi Shamir's subsequent IP equals PSPACE generalization only when his mother read him a relayed note during a bi-weekly phone call. The LFKN paper, which Nisan dates to 1990 or 1992, contained exactly the Sumcheck Protocol used in modern SNARKs today with no changes, and Nisan describes it as remarkable that the protocol arrived fully formed.

A SNARK is a succinct non-interactive argument of knowledge. Succinctness means the proof is short and fast to verify relative to simply sending the full data. Non-interactive means the proof can be written down and checked by anyone without back-and-forth communication. The argument property means a cheating prover cannot find a convincing false proof without breaking an underlying cryptosystem, which distinguishes it from a classical proof where no convincing false proof exists at all. A SNARK is constructed by taking an interactive proof such as the Sumcheck Protocol, combining it with a commitment scheme to compress a large file into a small binding object, and removing interaction via the Fiat-Shamir transformation. Nisan acknowledges that what the crypto world calls zero-knowledge proofs are mostly used for succinctness rather than for their zero-knowledge privacy property, though Zcash was an early deployment where privacy mattered more.

The first SNARKs combined a probabilistically checkable proof with a commitment scheme, a path Justin argues is redundant because it removes interaction twice. The more efficient approach builds the interactive proof directly with the Sumcheck Protocol and applies Fiat-Shamir only once. During Justin's PhD, a GKR protocol implementation carried roughly a million-fold overhead, making the cloud-computing verification story in papers unrealistic. Nisan adds that viewed from 20 to 30 years ago, even a million-fold overhead would have seemed optimistic, with the actual overhead appearing closer to ten to the fiftieth power. A SNARK prover proving a computer program ran correctly is currently under 100,000 times slower than running the program directly, a slowdown roughly equivalent to having the computational power of a 1995 computer. Nisan says his belief that SNARKs were impractical changed roughly four years before recording, when Eli Ben-Sasson showed him Starkware actually building on the technology and raising serious money.

The key algebraic building block is combining two sub-problems into one via a random algebraic combination, so that solving the combined problem implies correctness of both originals, with a small managed probability of error. Polynomial-based error correcting codes developed around 1990 remain essentially the best known, and everything deployed in practice still relies on them. In specific limited communication complexity settings it is known unconditionally that one cannot do better than the Sumcheck Protocol other than by constant factors. Nisan believes the protocol is not the last word but is confident it will not be replaced in its current form, and expects future improvements to come from how the protocol is wielded rather than from changes to the protocol itself. A forthcoming survey of roughly 33 pages argues the entire SNARK reduces to the Sumcheck Protocol.

After finishing a deanship, Nisan entered the blockchain space through Ben-Sasson and chose to focus on economics and computation rather than cryptography. He and co-author Moshe Babaioff showed that the variable block sizes introduced by EIP-1559 are the actual source of its welfare guarantee, not merely a learning tool for price discovery, and that the mechanism does allocate block space efficiently. Nisan notes EIP-1559 was designed with remarkably good intuition by practitioners who did not perform formal incentive analysis. He identifies multi-dimensional resource pricing as a genuinely unsolved algorithmic problem and is uncertain whether two-dimensional blob pricing achieves meaningful efficiency compared to normal gas. He finds tokenomics and the macroeconomics of blockchains most fascinating but acknowledges existing macroeconomics does not cleanly transfer to blockchain contexts such as token minting and burning decisions.