A Blockchain the Size of a Few Tweets
An introduction to Coda.
This article is one in a series of my 🍌Banana Papers — blockchain whitepapers re-written in an easy to digest (like bananas!) manner. My goal is to help readers quickly understand and evaluate complex blockchain ideas with minimal pain.
Coda is a new cryptocurrency project, led by Evan Shapiro and Izaak Meckler, being built by O(1) Labs, and backed by many investors, including Polychain Capital (Ryan Zurrer/Olaf Carlson-Wee), Naval Ravikant, Fred Ehrsam, and more. The project was just announced in May, and has goals of being the blockchain for storing value and securing digital lives.
Coda — the Easy Explanation
Coda is a new cryptocurrency that — no matter how many transactions are stored on its blockchain, or how complex those transactions are — processes transactions very quickly, with very little space required to verify the blockchain.
Coda — the Detailed Overview
Current cryptocurrencies are slow, and require huge amounts of data to stay synchronized. Bitcoin, for example, can only handle around 3 or 4 transactions per second, and requires a download of around 175 GB to stay synchronized with the blockchain. A normal user can’t or won’t store a blockchain of that size. Because of this, the chain is slowly being centralized to a small group of users who can handle the space requirements. That’s not good.
Coda is a new cryptocurrency that can process thousands of transactions per second, and — no matter how many transactions have occurred through the entire history of the chain — keeps the data needed to verify the chain small enough to store on a smartphone.
A user of Coda needs around just 20 kilobytes and 10 milliseconds to verify their balance. As the Coda websites claims, it’s a blockchain “the size of a few tweets.”
In effect, no matter how many transactions are in the blockchain, Coda is fast with a small footprint. Coda calls these combined features a succinct blockchain.
This succinct blockchain is created through a recursive composition of zk-SNARKs. Understanding that previous sentence is an exercise in cryptography. So let’s start with six basic cryptographic definitions and put them together to create the tech behind Coda.
Cryptographic Hash — a mathematical algorithm that takes an input of any size and outputs a different, (nearly) unique fixed-length string.
So if we want to hash “This is a banana paper” — we send that string of characters through the algorithm and get this output: “DEA3C406BC9982AD485BCDDC4CD1E7B7A6C1CE819786F7520157743CCD93EE5F”
(For a readable, but detailed explanation of how hashing works, check out this page. At a very simplified level, the algorithm converts the text to binary, then takes the binary through a defined series of simple functions, like adding zeros, breaking the number into pieces, adding steps together, and so forth, until there is a fixed-length result that can’t be reversed-engineered.)
The key here is that the same input generates the exact same output (hash value) every time. But, it’s a one-way process — you can’t figure out the input by somehow starting with, and reverse engineering, the output. The only way to figure out the original input is to “brute-force attack,” or do massive amounts of trial and error of input values, until the desired output hash value occurs. Which, in most cases, is nearly impossible.
Although no one can realistically figure out your original value, you can, using the output value, offer proof of knowing the input without having to reveal it. And anyone else who knows (or later knows) the input can verify that you are telling the truth.
Negligible Function — A cryptographic hash where the chances of someone hacking the hashing algorithm through a brute-force attack (as mentioned above) is very, very small. That’s a good thing!
Collision — If there are more possible inputs than outputs in a hashing algorithm, then sometimes different inputs will by definition have the same output value. So — if we hash something using SHA-256 (a popular set of hashing functions that I used in the example above), which uses inputs of any length, but always outputs 256 bits, inevitably (but rarely) there will be the same output for different inputs, or “collisions.”
Collision Resistant Hash Function — a hashing function where the above collisions are rare. That’s a good thing. It’s difficult to create a collision resistant hash function, but the algorithms in modern hash functions do a pretty good job.
zk-SNARK — “Zero Knowledge Succinct Non-Interactive Argument of Knowledge.” zk-SNARKS are a method for someone to prove, very quickly, that they have some piece of information (such as a key) without revealing the actual information, and without having to interact back-and-forth with the person that verifies the information. That’s complicated, and very difficult to explain using an analogy, because this truly is a unique ability that is only possible through cryptography.
But let’s try. Imagine you’re sitting in a wooden desk chair in a small, bare room, lit by florescents, in some downtown police station. Straight out of the movies. And the cops have you connected to this brand-new lie detector that’s right 100% of the time. The detective walks in and says, “We’re on to you. We know you killed Bob. Admit it!”
Now, you didn’t kill Bob. And you can prove it. But the problem is, you don’t want the detective to know how you can prove it, because on the night Bob was killed you were actually at that detective’s house sleeping with his wife!
But calm down, it’s ok. Because this lie detector is special, and it allows you to whisper into a microphone so that only the machine can hear you. So you whisper to the lie detector: “I didn’t kill Bob; and I can prove it because I was at the detective’s house that night.” The lie detector reveals to the detective that you are innocent, but never has to reveal to the detective what you said. You’re safe and on your way home. But be smarter next time and don’t mess around with a cop’s wife.
I’m telling the truth officer. But don’t ask me what I said!
That’s a decent analogy. Not perfect. But the point is: zk-SNARKS are a fast way to prove that what you are saying is true, without having to reveal what you said.
One popular use of zk-SNARKS in the blockchain world is the zCash implementation. In zCash, zk-SNARKS are used to keep transactions private — you can prove that you sent someone else some amount of coins without revealing the details of that transaction.
Exactly how zk-SNARKs work is complicated. You can start here for more details.
Merkle Tree — A tree of hash values (the output from the cryptographic hash described above) in which every node that has no children (a leaf) is the hashed value of an actual piece of data in the system. All the other nodes (that do have children) don’t have the hashed value of data, but instead their value is created by combining, and then hashing, the hashed values of their direct children.
For example, above is an example of a binary hash tree from wikipedia. In this example, hashes 0–0 and 0–1 are the hashed values of the data L1 and L2, respectively, and hash 0 is the hashed value of the combination of hashed values in 0–0 and 0–1.
Merkle Trees are very helpful in that they allow us to verify the entire tree of data, or just a certain branch or leaf of data, with just one hash, and without having to traverse the entire tree. Basically, if you know one node is true, you know all the nodes under it are true. A Merkle Tree says — hey you can trust this guy A, and because you trust this guy A, you can trust all of his children, because he trusts them.
So putting all this together, the technology behind Coda is:
- A negligible, collision-resistant hash function
- in combination with a pair of zk-SNARKs (called Tick and Tock)
- that recursively hash and verify all the blocks of data (or changes between blocks of data) in the blockchain
- and create a Merkle Tree of the zk-SNARKS, hashing multiple children into single parent hashes
- resulting in a single root hash value that represents proof of the entire blockchain
With the succinct blockchain of Coda, we now have a blockchain where “how hard it is to verify the blockchain” is independent of “the length of the chain” — because regardless of how many nodes there are, what you need to verify the chain is always the length of the root hash value. Users simply store the pertinent current state of the chain, along with a SNARK that proves there exists a blockchain behind the scenes that contains all the data. What consists of pertinent for that user could be the very top root node proving the entire chain, or just the path to a middle node needed to prove their balance.
As the Coda website states:
“Coda compresses the entire blockchain into a tiny snapshot … that means that no matter how many transactions are performed, verifying the blockchain remains inexpensive and accessible to everyone.”
To put it in easy to understand terms:
SNARKS are like tiny, unforgable certificates that are created as a result of a computation, and can be used to prove the computation is correct. Think of it as a Sudoku. Sudokus can be really hard to solve, but they are trivial to verify. If you have the SNARK, you can quickly verify that it is telling the truth.
So, since SNARKS verify a computation, and a change to a block on a blockchain is just a computation, when a processor updates a block, it can produce a SNARK. And anyone with that SNARK can very quickly check the computation and know that the result is true.
With Coda, you don’t have to possess the entire history of the blockchain to know, without a doubt, your balance of coins. You just have to know enough — the SNARK (to prove the data is true) plus the tree path to the data that is your balance.
Coda is out to rethink the way that blockchains work — and hopes, through its succinct blockchain, to return the control of the blockchain back to the common user. They have broader visions to eventually move their concept to not just currency, but to smart-contract platforms as well. For more details of how Coda works, check out the full white paper.
Check out my other Banana Papers
Originally published on hackernoon.com