Coda: Scaling with zk-SNARKs
Abstract:
Coda uses zk-SNARKs which is a unforgeable certificate to verify many blocks or the entire blockchain to speed up verification.
Commentary:
I’m mind blown. Notes are pretty full below.
Notes:
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
