How to decentralize a prover, according to an engineer who did it for fun

Andrew Milson, a former senior software engineer at Immutable, recently submitted his own proof to StarkWare’s StarkNet verifier on Ethereum.

Generally speaking, a prover is a computational entity responsible for attesting that information is accurate without revealing its underlying data. Provers must create “proofs” that can be easily verified by a verifier. 

The issue today is that many zero-knowledge (ZK) blockchain projects depend on one single, centralized prover. In the event that node fails to submit proofs, transaction finality will be impacted. 

But the process of decentralizing provers is no easy feat. 

Milson’s interest in STARKs is what started the entire ordeal, he told Blockworks. 

“When I found out they could be used to prove very large computations instantly in a small proof, I just lost my mind. It didn’t even seem possible, and the mystery resulted in me becoming obsessed with figuring out how they worked,” Milson said.

During this time, he built miniSTARK, a tool that enables you to prove the integrity of arbitrary computations using STARKs and also spent time learning about Cairo — a STARK programming language. 

“Its simplicity is beautiful, and the fact that StarkNet is built on top of it strikes me as very strong,” Milson said.

Process of submitting proofs

STARK verifiers are very similar in structure to their provers, Milson said.

“Being able to see StarkWare‘s verifier contracts on Ethereum essentially provided me with a blueprint that I was able to follow line by line,” he said.

Milson began copying Solidity contracts into a foundry project and wrote tests for the verifyProof process, he said.

It was an iterative process that involved the following:

1. Modifying Sandstorm and miniSTARK
2. Re-generating the proof
3. Re-running the test

“Each iteration, I’d get slightly more lines of code passing until the whole test worked,” Milson said. “I used the passing proof and submitted it to Ethereum using Etherscanner. It was a real thrill once everything was submitted on-chain.”

Milson believes that being able to submit his own prover is a step towards decentralization for StarkNet. 

“Teams in the community can start integrating the prover into their work which will bring a lot of scale and interesting use cases to the ecosystem, for example, onchain Gaming and ZKML,” he said.

This sentiment is shared by Liron Hayman, the head of business development at Starkware.

“This is a very important milestone towards decentralization of the Starknet tech stack. Andrew was able to develop his prover without viewing the code of StarkWare’s prover,” Hayman told Blockworks. “A mature decentralized blockchain like Starknet requires a vibrant community developing multiple implementations of each component. Andrew’s work is taking STARK technology to serious decentralization — and by extension, towards fulfilling its potential.”

Milson believes his work can also be viewed as an audit of StarkNet’s existing verifier and a testament to the security of the network.

“I inspected every line of code and I couldn’t find a bug which was honestly a bit disappointing considering how juicy StarkNet’s bug bounty program is, but really impressive on StarkWare’s behalf,” Milson said.

Updated on Aug. 14, 2023 at 12:10 pm ET: Andrew Milson is no longer a senior software engineer at Immutable.

---

Get the news in your inbox. Explore Blockworks newsletters:

• The Breakdown: Decoding crypto and the markets. Daily.
• 0xResearch: Alpha in your inbox. Think like an analyst.