Zero-knowledge proof systems have room for improvement, say cryptography researchers

More developers may soon be able to play a role in advancing zero-knowledge technology. 

Andreessen Horowitz’s crypto research team has published a paper that outlines two new zero-knowledge (zk) proof technologies.

Currently, the two most popular technologies used for zk rollups are zkVMs (zero-knowledge virtual machines) and SNARKs (Succinct Non-Interactive Argument of Knowledge). 

SNARKs and zkVMs are both cryptographic constructs that allow participants to prove that their transactions are legitimate without revealing certain details of those transactions. They offer both scalability benefits (since less data needs to be stored and processed) and privacy benefits. 

The first zk rollups to reach mainnet have already accumulated over $1 billion in total value locked, per L2beat.

But existing SNARK technology can be significantly improved, Justin Thaler, a research partner at a16z, told Blockworks. 

“Current SNARK implementations are sufficiently complicated, they’re almost certainly full of bugs, which could make them useless security-wise,” Thaler said. “We’re talking 10s, 1000s of lines of code, very difficult to understand, and it’s very, very hard to imagine there is not a single bug in these code bases.”

The team at a16z crypto research — in conjunction with researchers from Microsoft, Carnegie Mellon and NYU — have developed a new approach to this problem: Lasso and Jolt.

Meet Lasso and Jolt

Lasso can be used in cryptography to shorten encrypted computational complexities, making them easier to apply practically.

“A key component for modern performative SNARK deployments is something called a lookup argument,” Thaler explained. “Lasso is a new lookup argument with a significantly faster prover.” 

Engineers at a16z initially implementing Lasso conclude that it’s an order of magnitude improvement over existing lookup arguments, Thaler said. 

“The prover is 10x faster — and that’s with our initial, not very optimized implementation,” he said. 

Jolt is a framework used primarily to restructure, convert and change data. Thaler explained that Jolt uses the Lasso lookup argument as a building block to give what is a new approach to designing zkVMs. 

“So what we’re doing is turning each step of the virtual machine into a Lasso,” Thaler said.

Simplifying zk tech for developers

This vision is not necessarily new and comes close to realizing what Barry Whitehat from the Ethereum Foundation calls “lookup singularity.”

“The vision is let’s do SNARK design by only doing lookups,” said Thaler. “We won’t have developers coding by hand very optimized circuits, which is very labor intensive and difficult to audit…we’re coming close to achieving a vision that a lookup can do all virtual machine execution with Lasso.”

Riad Wahby, an assistant professor at Carnegie Mellon University and co-author on the research paper, told Blockworks that it’s unlikely that current zk-rollup implementations will directly benefit from the research, but that the next generation might. 

“For me that’s where the real excitement comes with something like Lasso is that it really enables like much more efficient general purpose, generally programmable proving systems,” Wahby told Blockworks. “Instead of having maybe 100 people in the world who can make significant progress on building the next roll-up, now it’s much wider open, and we’ll see much more innovation.”

Lowering barriers to use elliptic curve cryptography

SNARKs often use a combination of cryptographic primitives, including but not limited to elliptic curve cryptography (ECC) and hashing.

Hashing and ECC are designed for different cryptographic purposes, and while hashing is critical for data integrity checks, ECC is commonly used for encryption and digital signature purposes. 

“There’s nothing fundamentally insecure about hashing-based SNARKS. But for hashing-based SNARKS, they give the protocol designer the flexibility to trade off performance for security,” Thaler said.

The benefit of the Lasso and Jolt technique, Thaler contended, is that it is designed to make elliptic curve cryptography more performative and efficient and removes the need to rely on hashing.

“People who really care about performance might no longer feel such a push to go to the hashing-based [SNARKS],” he said.

Is it VHS vs Betamax or VHS to DVD? 

In the immediate term, the a16z crypto research team has published a draft version of the code on a16z’s GitHub page and hopes to receive external contributions. 

“Taking Lasso and turning it into Jolt will be a significant effort. And we’re hoping not just to do it ourselves,” Thaler said.

In the long term, Thaler hopes the wider ecosystem will build on the code base and techniques introduced by its research paper.

Wahby thinks there is a year or two of engineering work ahead before the research can be turned into production-ready proof systems.

“It’s sort of a total ground up redesign,” Wahby said. But the potential benefits may be worth the wait. “We certainly have room for a VHS to DVD kind of jump,” he said.

Alex Pruden, CEO of Aleo, a privacy-focused zk-based blockchain, told Blockworks in an interview that there are several techniques from the Lasso paper that it plans to integrate.

“Lasso builds on a body of prior work, and the innovations described in the paper are exactly why an open-source ecosystem is such a powerful force for innovation.” Pruden said.

Updated Aug. 10, 2023 at 12:18 pm: Lasso is also not an acronym, as was stated in a previous version of this article. It also listed an incorrect title for Riad Wahby. He is an assistant professor at Carnegie Mellon University.

---

Start your day with top crypto insights from David Canellis and Katherine Ross. Subscribe to the Empire newsletter.

Explore the growing intersection between crypto, macroeconomics, policy and finance with Ben Strack, Casey Wagner and Felix Jauvin. Subscribe to the Forward Guidance newsletter.

Get alpha directly in your inbox with the 0xResearch newsletter — market highlights, charts, degen trade ideas, governance updates, and more.

The Lightspeed newsletter is all things Solana, in your inbox, every day. Subscribe to daily Solana news from Jack Kubinec and Jeff Albus.