Coda: Scaling with zk-SNARKs

SF Blockchain Week post #5


Coda uses zk-SNARKs which is a unforgeable certificate to verify many blocks or the entire blockchain to speed up verification.


I’m mind blown. Notes are pretty full below.


The life of a full node

Problem: many end users do no validation

Why? Full nodes have enormous resource requirements

Intensive to run on a computer

Impossible to run on mobile

Delegate trust to third parties, full nodes, miners

Need way to be convinced of the current state without seeing the history of that state

The root problem: verification mechanism

Imagine if every time you spent a dollar, you had to check the entire history of how that dollar had been spent

Toward a solution

If only we had some way to certify that someone had already checked the history for us. Like a certificate.

It’s easier to check an audited statement than to look for yourself

zk-SNARKs: unforgeable certificates

Amazing cryptographic primitive

zk-SNARKs are a certificate for prove that a computation was performed correctly

tiny, < 1 kB

easy to check, 10ms

versatile, works for any computation

Tiny and easy to check no matter how complicated the computation is

How this is used in Coda

Updating a blockchain is just a computation

SNARKs can certify any computation

So, have processors produce SNARKs that certify they are updating the blockchain correctly

Instead of end-users checking the blockchain themselves, they check the certificate instead

The certificate is tiny and easy to check!

Get full node level of security

Attempt 1: use one SNARK for each block

Processor produces SNARK while updating the database of accounts

Certificate says “I know a block which when applied to DB 1 results in DB 2”

It’s a SNARK, so ~1kb

End user, receives Merkle path into DB 2 to check their balance

Chaining certificates

You can get from DB 0 to DB 1

DB 1 to DB 2

DB 2 to DB 3

DB 3 to DB 4

Therefore DB 0 to DB 4

But this doesn’t solve the fundamental problem of linear growth

Attempt 2: use one SNARK for the whole blockchain

Recursive composition

Checking a SNARK is itself a computation, and so can itself be certified with a SNARK

We can chain multiple SNARKs together to get one SNARK that stands in for all of them

Scalability — usually thinking about increasing throughput, but that only makes verification harder