Equilibrium's Infra Bulletin #4: Private Voting, Attack on the NOVA Scheme and Decentralised Proving
Equilibrium Labs builds the state-of-the-art of decentralised infrastructure. We are a global team of ~35 people who tackle challenges around security, privacy and scaling.
This newsletter allows us to share more about what we read, what excites us and what we think is relevant to the space. In addition, you will get a glimpse into the organisation and our culture.
Research, Articles and Industry News:
📚First Ethereum Storage Proof Written In Noir - Recommended by Hannes:
Aztec and Aragon ZK Research released their fourth progress report related to the development of private voting for NounsDAO. As part of the progress, they have managed to create the first Ethereum storage proof written in Noir - a depth 8 storage trie that compiled to 713k constraints and proved in ~2 mins on a laptop. Thanks to the successful completion of storage proofs, a complete version of the ZK circuits for vote submission is now available.
The team is also working on generating storage proofs in the browser. Thus far they have implemented the JavaScript package of the UltraPlonk proving backend and the Noir package for compiling and executing Noir programs in a browser environment. The focus next will be on recursion and multi-threading.
Seeing the progress on the NounsDAO private voting is exciting, as Equilibrium Labs was also involved in the preliminary discussions for creating a research PoC together with Aztec. Unfortunately, we had to drop out due to limited engineering capacity on our side at the time.
Key Takeaway: We’ve covered storage proofs before for trust-minimised cross-chain communication. Proving token ownership for voting is a specific use case of that. Private on-chain voting can be enabled by combining storage proofs with timelocks (draft paper), which only reveals how everyone voted after enough time has passed. The final report for the project is expected by mid-July.
📚The Zero-Knowledge Attack Of The Year Might Just Have Happened, Or How Nova Got Broken - Recommended by Mark:
Nova is one of the most important implementations of a zero-knowledge proof (ZKP) system. It’s an Incrementally Verifiable Computation (IVC) scheme, which allows repeating the same computation ad infinitum before stopping at any given point to create a proof for the whole thing. In contrast with the more familiar approach of proving each instance and then rolling up the result, the IVC is performed before any actual ZKP is produced, making recursion cheaper. Accumulators are part of the recursion (taking two inputs, producing one output). A “strict” accumulator is the direct result of executing a circuit and is not obtained by folding anything.
The initial state 𝑧(0) is fed as input to some function 𝐹 repeatedly (with some other auxiliary inputs aux(i) at the different steps) to finally return 𝑧(𝑖). Nova, or IVC schemes in general, allow creating a proof of that entire computation Two weeks ago, Wilson Nguyen published a paper that demonstrated a false computation accompanied by a valid proof for Nova. Given that the purpose of a ZKP is to certify the results of computation without revealing any information about the computation itself, errors like these are highly concerning. This blog by zkSecurity breaks down the vulnerability and also serves as a great explainer of some fundamental concepts of ZKP schemes.
The source of the vulnerability was that Nova included an additional and unnecessary “strict” accumulator (𝑢^2(𝑖−1) in the diagram below), and checked one of its authentication tags (contained in its public input) instead of the correct one in the other “strict” accumulator (𝑢^1(𝑖) in the diagram below). This was fixed by simply removing the unnecessary accumulator and making sure to verify both tags in the public input of the final “strict” accumulator.
Key Takeaway: It’s important to note that this was an error with the implementation, not the Nova proof system itself (which would have invalidated a ton of proof systems in the Nova family). While the Nova scheme is still standing strong, the vulnerability demonstrates the complexity of this technology and that implementation requires caution.
📚Decentralized Proving, Proof Markets and ZK Infrastructure - Recommended by Olli:
ZKPs can be generated either by the user on their computer (client-side proving) or outsourced to a third-party (server-side proving). Client-side proving is better for privacy preservation and is widely used for example by Zcash. Server-side proving is targeted at computationally-intense proof generation and works well for applications where the ZKP is used for succinctness/scaling since there are no secret inputs (in contrast to privacy solutions).
Source: Figment Capital Proof generation can be decentralised through two main ways: Proof Networks are prover sets that service a single application and all provers compete for that same task. On the other hand, Proof Markets enable multiple applications to submit requests for verifiable computations that provers can bid for. A key challenge with proof markets is matching buyers (proof requesters) and sellers (provers). The two main approaches are auction (provers bid on proof requests) or order book (applications submit how much they are willing to pay and in what time they want the proof to be generated. If the prover’s ask is below that, then it’s a match). Order books are better suited for low-latency use cases since order book bids can be filled immediately.
Source: Figment Capital There are many other tradeoffs to consider. For example, Aggregated Proving can lead to cost savings as it’s cheaper to send back one proof rather than many individual ones, but it also introduces more latency compared to Individual Proving. Another tradeoff is between custom circuits and zkVM. Custom circuits for each application enable better performance but come with integration overhead and additional costs. While a more general-purpose zkVM is slower, it can allow developers to write verifiable programs in higher-level languages (such as Rust or C++) and enables having a single order book.
Source: Figment Capital Key Takeaway: The demand for outsourced proving is likely to increase as more ZK networks launch and applications utilising ZKP become more complex. While most provers today are run by the teams building the applications, decentralised proving has the potential to grow into an essential component of the ZKP infrastructure. Decentralised proving is a topic that we’ve thought a lot about internally, and this article by Figment Capital provides a great introduction to the different nuances to consider - for builders and users alike.
News from our partners:
🤔Post-mortem Analysis Of The Pathfinder Mainnet Outage (Pathfinder is a full node implementation on Starknet that Equilibrium is developing):
On Saturday, 17 June 2023, 18h05 UTC, Pathfinder nodes stopped syncing on mainnet causing an ecosystem-wide outage. The root cause was Pathfinder's failure to sync block 84,448 on mainnet, due to a class hash mismatch. The culprit was JSON’s string encoding. The failing class included non-ASCII characters, causing the final encoded bytes to differ, hence a different hash.
The issue was resolved by re-encoding any non-ASCII characters to match the formatting used by the sequencer. Pathfinder v0.6.1 was released, and the fix was backported to create v0.5.7 for users who hadn't yet upgraded to v0.6
Bugs are part of any software, but there should be procedures in place to minimize the impact of bugs that do slip through. While our procedure here was lacking, mistakes are opportunities to learn. Going forward we will implement better monitoring (especially around mainnet) and automatically notify relevant people. This, combined with a clear line of communication for emergency situations and a response team on stand-by 24/7, enables us to rapidly gather the people required and resolve the situation asap.
Personal recommendations from our team:
📚Reading: How To Do Great Work: When Paul Graham publishes something new, it’s usually worth reading. This one is no exception - offering actionable advice and tools for reflection, no matter which career path you’re currently on.
🎧Listening: George Hotz on Lex Fridman’s Podcast: An interesting conversation spanning Twitter, AI Safety, Self-Driving, AGI and more. Enjoyed by several of our team members!
💡Other: Consensys Partnered With YouGov to survey more than 15,000 people across 15 countries. While surveys should always be taken with a pinch of salt, this one is useful for gauging the interest in data privacy, digital ownership, level of crypto education, and much more. Is there anything that you find surprising?
