Examining Coda’s Cryptographic Proposal For Tiny Blockchains

This issue goes to the heart of how blockchain (typically) works.

Beyond the idea of a chain’s consensus algorithm (i.e., Proof of Stake/Proof of Work/etc.), is the composition of its transactions.

On Bitcoin, for example, each transaction consists of header data:

The pictures above shows the type of information that is usually included in each Bitcoin transaction.

Overall, this information adds up to about 200–250 bytes per transaction (smallest TX on the Bitcoin protocol can only be 100 bytes).

The ‘keys’ and ‘signatures’ account for the bulk of the TX size and that’s attributable, in a large part, to both the ECDSA curve Bitcoin uses (secp256k1) as well as the SHA256 hashed output of public keys.

Various measures such as compressing said public key have helped to a certain extent in terms of cutting down on the size of the transactions, but there’s only so much that can be done without completely altering the way the protocol functions.

So, in analyzing Coda, we’re going to look at:

  1. The cryptography that this project uses
  2. How blocks are formed, what the protocol rules are, and where things are stored
  3. How public keys are created and how the protocol operates

Hunting Down Cryptographic Information as it Pertains to Coda

Going back to the main ‘Coda’ repository — there isn’t much information in the way of cryptography.

So, we were forced to take a brief detour to the Coda whitepaper to get a better idea of what it is they’re trying to do here.

Brief Look at the Coda Whitepaper

In case you’re also looking, the Coda whitepaper can be found here: https://cdn.codaprotocol.com/v2/static/coda-whitepaper-05-10-2018-0.pdf

We won’t waste too much time here, so let’s dive right into it.

Succint Blockchain

According to Coda’s whitepaper, in order to create a blockchain protocol that, ‘achieves both scaling and decentralization’, the developers decided to make Coda a “succinct blockchain”.

In the paper, a ‘succinct blockchain’ is defined as:

“A blockchain for which verifying the current world state requires only a constant amount of data and a constant amount of time. Concretely, a user of Coda requires only 20 kilobytes and about 10 milliseconds to verify their balance. These requirements are independent of the number or complexity of the transactions processed by the blockchain. This allows Coda to scale to large numbers of users while staying accessible to those with relatively limited computing resources.”

The paper further states:

“Coda’s succinct blockchain is enabled by recursive composition of zk-SNARKs [BCCT12]. Recursive composition of SNARKs enable constant-sized proofs of arbitrary, incremental computations. This allows the Coda network to construct a proof of the validity of blockchain state that can be updated incrementally as more blocks are added.”

Before we dissect the information above (fully), let’s see if we can’t find out where more information (in the source code or elsewhere) can be located.

Continuing Our Search for Coda’s Cryptographic Outline

Stumbling on the ‘Coinlist’ link for ‘Coda’ ( https://coinlist.co/build/coda)

Through some cursory Google searching (and searching on GitHub) the above webpage was sourced.

Scrolling down from there (the top), we can see:

Above is our jackpot.

We have:

Coda SNARKs Documentation

The Coda SNARKs Documentation link takes us here: https://github.com/o1-labs/snarky

Noticeably, the URL (and the GitHub) shows us that this repository is controlled by ‘o1 Labs’, which was the name of the second link provided above.

So, let’s checkout o1 Labs and see who they are and what they do.

[site = https://o1labs.org/]

o1 Labs Gloss Over

Here’s a view of the homepage we got when visiting o1labs.org :

Surprisingly, the page doesn’t really give us a lot of information about what’s going on — so its back to the first repo to see what we can glean from the GitHub.

Fortunately, the GitHub provides us with some more information about what it is ‘Snarky’ does in the Readme.md (already open on the main page of the repo).

Specifically, it mentions ‘R1CS SNARKs’, stating that it is, “Modular over the backend SNARK library, and comes with backends from libsnark.”

[Link for libsnark = https://github.com/scipr-lab/libsnark ]

ZKP.Science

A cursory look on the internet (outside of the GitHub that we were just in) for more information about ‘R1CS SNARKs’ took us to ‘zkp.science’.

There are a ton of resources on this page, in general, so this is probably worth saving for all those that are interested.

Looking Up More Information About ‘Recursive SNARKs’

This is critical since Coda listed this as the underpinning of its innovation in the whitepaper where it states:

“Coda’s succinct blockchain is enabled by recursive composition of zk-SNARKs [BCCT12]. Recursive composition of SNARKs enable constant-sized proofs of arbitrary, incremental computations. This allows the Coda network to construct a proof of the validity of blockchain state that can be updated incrementally as more blocks are added.”

A cursory search for more information regarding ‘recursive SNARKs’, brings us to an informative forum post on ethresear.ch concerning their implementation (see below):

https://ethresear.ch/t/reducing-the-verification-cost-of-a-snark-through-hierarchical-aggregation/5128

The article cited in the post can be found here: https://eprint.iacr.org/2014/595.pdf

Its a research study titled, ‘Scalable Zero Knowledge via Cycles of Elliptic Curves’.

No coincidence, this is exactly what Coda is trying to do.

Breakdown of the Process via Illustrations

###

Since the forum post does such a good job dissecting how recursive SNARKs would be implemented on chain, it only seems logical to provide the same illustrations below to assist readers in comprehending how Coda plans on implementing its plan.

The leaf nodes (ie: the batch of proofs to be aggregated together) are inputed as:

A verification key

A proof

A primary inputs of the the proved assignement [sp]

In theory, this could work — but its hard to imagine that every node would be able to verify all transactions on the chain, maintain the state and never need to cache more than 22 kb of data, regardless of the process being run, on a protocol that retains the features of trustlessness/decentralization/distribution (all three requisite in creating a superior solution to Bitcoin).

This is especially true when considering the size of the key signatures that would more than likely be deployed for such a solution.

The remainder of the forum post we referenced above does a great job in tackling that aspect of the idea as well:

Source: https://ethresear.ch/t/reducing-the-verification-cost-of-a-snark-through-hierarchical-aggregation/5128