Presenting ETHdos numbers: measuring degrees of separation of people (akin to Bacon/Erdos numbers) while hiding individual friendships entirely. This is a first of its kind social experiment demonstrating the composability properties unlocked by recursive ZK-SNARKs.

Recursive ZK-SNARKs are fundamentally cool technology. This summer, we built out a version of SNARK recursion using the groth16 proving system (blog post on 0xPARC blog with more details coming soon!). With this development, we started exploring use cases for recursive SNARKs. Quickly, we realised most usual use cases of Recursive ZK-SNARKs almost entirely ignore the ZK properties of being able to do recursion, mostly using SNARKs for their succinctness properties.

In fact, there’s something fundamentally cool about recursive SNARKs that seems to have been overlooked, and it’s not succinctness (or even compression as I’ve been calling it). ETHdos is our first attempt at exploring this cool new property to instrument a social experiment! So, let’s talk about this property:

What does this mean? In ETHdos, I can prove I am degree 4 from Vitalik by showing that someone who is friends with me is degree 3. I can show there exists a valid path of 4 people between us, without knowing what the first 3 nodes in it look like!

This is something new entirely. Not only are ZK proofs hiding information from external verifiers, but also from the person making the proof!

We’ll talk more about this property and share more detailed thoughts on it at a later time in a blog post on the 0xPARC blog!

For now, let’s dig deeper on how ETHdos works end-to-end:

The ability to hide social graphs while simultaneously selectively sharing properties of it is inherently interesting experimental grounds, and our intention is for ETHdos to serve as a fun proof of concept social experiment to bring attention to recursive SNARK applications.

Here’s a demo video of our user flow:

You can look at an example proof (for my degrees of separation) here. Vitalik started off the graph recently by adding a few of his friends as degree 1, and since then the graph has spread around naturally! If you don’t have a number yet, but are looking to get one, maybe you should ask your friends?

As a disclaimer, note that ETHdos is only meant to be a fun social experiment and a proof of concept for what’s possible. None of our code is audited or recommended for production use without serious considerations. At the very least, the circuits require a trusted setup ceremony, proper auditing (if not formal verification) and significant optimisations before production use.

With this high level design in mind, let’s dig deeper on the ZK circuit’s design:

First, let’s introduce some terminology: We’ll call Vitalik (the starting node) the origin node and introduce the concept of source and sink nodes: A source node creates a ZK proof for a sink node which the sink node can then use to prove their degrees of separation from the origin. For example, in the video above, nibnalin.eth is a sink node, charlie.eth is a source node and vitalik.eth is the origin node.

To create a proof of degrees of separation of the sink node, the source node initiates computation by signing a message and running proof generation for the ZK circuit. The circuit checks the following:

Let’s expand on each of these:

The circuit first verifies that the sink is indeed a friend of the source by requiring the source to sign the message “ETHdos friend: <sink’s address>”. To ensure the correctness of the message being signed, the input signal sink address is used to recreate the message that should have been signed by source’s pub key to authenticate them as a friend. This involves some complicated string mangling to exactly match the format wallets sign messages in. ECDSA signature verification is made possible by the circom-ecdsa library.

Next, we verify that the source address is indeed the claimed degree away. This is where we use SNARK recursion: We verify the ZK proof of the source’s degree inside this ZK circuit. Doing so requires us to input a verification key for the circuit itself, and using that alongside a proof as the input to a groth16 verifier circuit (that we wrote this summer!).

Finally, once we are sure of source’s degree, we verify that the sink is claiming source’s degree + 1 as their own degree correctly.

Notice that the base case for this recursion needs some special handling: If you are vitalik.eth (the origin) making a proof for someone else, there is no “inner proof” to verify, so we replace it with a dummy (wrong) proof and instead add a special case allowing anyone to become degree 1 as long as the ECDSA signature from the source verifies, and the source matches the origin address i.e. only the origin node, vitalik.eth, can add people as degree 1.

Groups within 0xPARC have continually pushed the boundaries of client-side provable circuits. Yet, the largest groth16 snarkjs based circuits we’ve been able to fit on client-side provers are about 10x smaller than this one, so unfortunately, generating proofs on-device for this behemoth 31 million constraint circuit is very infeasible :( So insted, we set up our old trusty zk-node-server (notes about it here) with rapidsnark and Circom’s C++ witness generators. End-to-end proof generation takes about 5 minutes, and interestingly enough, is dominated by witness generation (and not the actual prover) because it is single threaded while the prover is multi-threaded. Therefore, one avenue of interest for future groth16 SNARK recursion based projects might be to look into making Circom’s C++ witness generator highly parallelised for future. After playing around with a number of different params, we also discovered a couple other practical optimisations to make if you’re trying to speed up proof generation for large Circom circuits:

Our on-chain contract is a relatively straightforward ERC721 contract modified to disable transfers to make the tokens soulbound.

Additionally, for maximal decentralisation, we’ve made our NFT art fully on-chain by encoding the token image in our contract! We forked the Uniswap V3 Positions NFT and adapted the cards to our use case. It was really fun to be able to play with art in Solidity, but its definitely not intended to support such use cases as a language.

As a fun aside, our journey of putting together ETHdos has been really fun. A subset of us are high-school friends, and we originally came together earlier this summer to build something fun for ETH NYC. Having played around with recursive SNARKs recently, we were thinking about cool applications we could build with this new primitive. And sitting on the East River coast in New York at 11PM, this idea came around. From there, all it took were two all nighter sprints to build out a prototype over the weekend, only to end it with one of the funniest stories of miscommunication, oversleeping, and rushing through town in Ubers and subways! Ultimately, though, we won ETH NYC and had a really fun time doing so. Perhaps, we’ll save our main-character bollywood epilogue for in-person conversations at some point. :)

Since the ETH NYC weekend, we’ve cleaned up a lot of our frontend and general jank, and it has been quite funny to be able to go from using Vitalik as a meme example in our hackathon demos to having him actually be the origin node for our full release now!

ETHdos is only possible thanks to a ton of support from a number of awesome folks: Yi Sun, Jonathan Wang, Vincent (circom-pairing team), gubsheep, Vitalik Buterin, DC Posch, Lakshman Sankar, Ying Tong, Michael and everyone else in the 0xPARC community! Thanks also to Uniswap (whose NFT art contract we forked) and to Iconoir (whose atom icon we use as our logo).