HackMD
Recursive SNARKs
There’s something fundamentally cool that seems to have been overlooked about recursive SNARKs, and it’s not succinctness (or even compression as I’ve been calling it, for the lack of a better word). Although that is cool too, I will defer cool ideas from that to the end of this post. First, it’s important to talk about this property I’ve so far been calling: composability.
Composability
In one sentence: a prover can now prove assertions about facts they do not fully know themselves.
What does this mean? In ETHdos, I can prove I am degree 4 by knowing just a ZK proof that a friend of mine is degree 3. I can prove the validity of the entire path, while not knowing anything about the path myself.
This is something new entirely. How do you make this useful?
Where can I find facts I do not know?
One class of such facts is sourced from cryptography: Digital Signature algorithms. I do not know valid signatures corresponding to someone else’s public key. But I can prove knowledge of their existence (actually, prove that someone besides them knows of their existence, which is equivalent) from a zk proof inside my own zk proof and wrap it with more statements on top.
What do signatures do? A signature itself can be used to assert facts about the world relating to the private key owner.
There’s a property of “hardness” to this fact, as well as others in this class I can think of off the top of my head. These are problems in NP, sure, but what are some things people tuck in these crypto boxes?
There’s something weird about this composability - when we think of SNARKs we think of a prover proving statements they know to a verifier, not a prover proving statements they do not know. It’s not just a scaling improvement, the applications of recursive SNARKs are richer than plain SNARKs.
There is one other necessary condition to be able to use these effectively: the new prover should have at least some knowledge to add onto to the previous proof. Otherwise the previous guy generating the inner layer SNARK would’ve been able to make the same assertions without the involvement of this guy - so the outer prover needs at least one extra fact they know to “compose” with a set of inner facts.
This means that there must necessarily be some collaborative component to the full proof generation. I must contribute something to my larger proof otherwise I am useless.
This description almost begs for the existence of a partial information game. I will think more about this later.
One other interesting idea of an app you could build with this is trust-less, private liquidity channels (or even proper state channels with a bit more effort), revealing none of the intermediate transactions to anyone except each other, no HTLC or wait periods necessary.[1]
What are other sick things you can make that I am not realizing? Is even the definition of this property sufficient and necessary?
Succinctness
Using ZK SNARKs as rollups is very mechanical, it’s really just an abuse of the property of succinctness of ZK proofs, and perhaps the right way to look at it is that recursion enables compression.
But there are some properties this succinctness seems to enable that are beyond the scope of just compression. For one you can do true conditional statements using recursive checks: you can use a recursive snark to write, for instance, a constant cost selector! You prove the execution of a selector inside a snark, so you can roll it up inside a larger circuit. This is quite interesting, with a good enough DSL its allowing our SNARK circuits to make the jump from being just finite state machines to proper Turing complete machines with loops and true signal dependent conditionals.
Not clear where to go with this, seems like the seeds to a future infinite DSL for ZK proofs.
Other simple ideas to note for the sake of completeness/inspiration:
Isokratia: just roll up off chain votes and post on chain, abuse of compression properties
Light client: Prove the validity of entire blockchain in one zk proof, abuse of succinctness
Indexer: Put a simple SQL/VM for aggregation of time series’s data of a blockchain, prove execution from tip blockhash. Abuse of compression properties
Here’s a full description of the liquidity channel protocol using this: you both escrow into a contract and do a bunch of transactions off chain between each other, revealing none of the intermediate transactions to anyone except each other. At each time, you maintain a roll up zk proof that has 3 public inputs: balances and number of txes (for indexing, this will be useful later). Each time I want to make a proof, I generate a signature authing a tx at a particular state, and roll it up into a new zk proof and give it to my counterparty. My counterparty does the exact same thing back. At no point are signatures revealed to each other and only balance sheet is revealed. At any point one of them decides to settle, they go on chain and show this zk proof to contract, revealing only final balances. Additionally you need a escalation game style mechanism in case any single party tries to go to chain and censor some suffix of transactions you want the counter party to be able to show a “larger” (by number of transactions) zk proof. Can you pull off an entire Lightning network? Seems tough due to the escalation game mechanism. In general it seems it’s easy to censor/deny existence of information. ↩︎
