CODA: zk-SNARKS & recursive composition for a constant-size Blockchain

CODA logo
I actually introduced in my previous post what zero knowledge proofs are just for the sake of introducing this application I am very excited about: CODA.
CODA uses zk-SNARKS to build a tiny, constant-size blockchain. So tiny that it could run natively in browsers!

If you're still reading this after reading the very title of this post, I think I can also assume that you are familiar with the concepts of blockchain and zero knowledge proofs.

CODA is a new cryptocurrency protocol built on a "succinct blockchain". Succinct means here small in size and easy to verify.
It leverages zk-SNARKs to compress the blockchain down to a few Kilobytes, 22KB more exactly.
To put it in perspective, let's compare it to the 2 first blockchains in terms of adoption and market capitalization.
At the time of writing and according to bitinfocharts, the Bitcoin and the Ethereum blockchains are respectively 14 millions and 10.5 millions times bigger than CODA.

Blockchain Size /CODA
Bitcoin 308.38 GB - ever growing 1.4e7
Ethereum 233.00 GB - ever growing 1.06e6
CODA 22 KB - constant 1

One could argue that 200/300GB are still reasonable and affordable volumes of data.
One can buy a 500GB internal SSD SATA drive for 58€ on amazon. So a tech-savvy user is likely to have the ressources to set up a node on a personal computer and join the Bitcoin and Ethereum blockchains as a validating node.
However nowadays most of the computer are...mobile phones. There's no way they can deal with such big amounts of data.

Which is why CODA is so exciting. It reduces so much the technical requirements to run a node that mobile phones could become nodes and verify the whole blockchain. It would solve scalability, security and decentralization challenges.

Reminder

A zk proof proves that a statement is true without revealing any info beyond the validity of the statement itself.

When dealing with a blokchain, what could we possibly want to check?
...That the blockchain is valid! That the blocks are valid and correctly chained together.
What's the big deal?
Normally this validation is the job of validating nodes. Nodes that check whether the blockchain is still valid after submission of a new block. A member/user of the network can decide to trust people to validate for him (delegation) or can decide to perform the validation himself. In this case the user has to carry the costs associated with the validation process: remember the ever growing size of blockchains?

As long as you can be convinced that the blockchain is valid, you actually don't want to bother checking backwards the full blockchain history. You care only about a proof that the blockchain is valid. You don't care about the whole content...sounds like a good application for zk proofs, doesn't it?
This is precisely what CODA does: using zk SNARKs to certify that the blockchain has been validated correclty. Like a proof that an audit was executed properly.

Use of zk SNARKs in CODA

  • updating blockchain is just one computation
  • SNARKS can verify any computation
  • Processors produce SNARKs that certify they are updating the blockchain correctly
  • End users don't check the blockchain themselves, they check the tiny certificates instead

How could we use practically zk SNARKs as verification mechanism in a blockchain architecture?

Naive architecture: 1 SNARK for each block?

One could use them to produce a certificate which says: "I know a block which when applied to a data base of state 1 results in a data base of state 2. We can get from 1 to 2 with this block".
The end user receives:

  • certificate
  • a merkle path into Data Base (DB) of state 2 to check their balance without having to see the complete difference between DB1 and DB2.

What if it is not sure that DB1 is valid? We chain.
Just like the Bitcoin blockchain chains blocks together, we would chain certificates backward to check the validity of the whole chain: not chain of blocks but chain of certificates.

This would be an improvement in size buth the blockchain would still grow linearly.

Better architecture: 1 SNARK for the whole blockchain!

In the previous architecture, 1 SNARK consisted in a certificate attesting the validity of a block:
1 SNARK = 1 check = 1 proof that a block was computed correctly
The idea of composition is to check the checking process.

Recursive composition

Checking the validity of a SNARK is itself a computation and so itself can be certified with a SNARK.
So we check if all the past SNARKs have been computed correctly, which produces... 1 SNARK.

# snarkify(0, 1) = SNARK 1 that proves we can get from 1 to 2
# "snarkify(1, 2) = SNARK 2 that proves we can get from 1 to 2
# snarkify(snarkify(0, 1), snarkify(1, 2)) = SNARK 3 that proves we can get from 0 to 2

# and so on ...
0>1, 1>2 ----> 0>2, 2>3---> 0->3

End user

The download of this final SNARK is a sufficient proof of the blockchain validity: downloading 1KB SNARK ~ validating the whole chain.
In addition, to know his account the user has to download the merkle tree (22 KB).

Conclusion

Let that sink in,
a wallet implemeting the CODA protocol can get fully synchronised and achieve full security after the few milliseconds required to download the single SNARK.
It takes days/weeks to fully sync a node with the Ethereum or Bitcoin blockchains. The node has also to be kept up and running to avoid being left behind and become out of sync.
Everyone can become a validating node without any extra costs.

  • [x] Scalable
  • [x] Decentralized
  • [x] Secure

Perfect solution?
Not quite yet. One limitation of zk-SNARKs is that they rely on a "trusted setup". I haven't found out how CORDA deals with this yet.
zk-STARKs are alernative proofs to zk SNARKS that don't require such a trusted setup. Could we compose zk-STARKs recursively instead?

The video feat. CODA CTO Izaak Meckler that explained me what I've just shared is available here.


You'll only receive email when Gauthier Riou publishes a new post

More from Gauthier Riou