Proof of Stakea
The proof of stake consensus mechanism implemented in Coda is a version of the Ouroboros Praos protocol, extended and modified slightly for our succinct blockchain. This document will provide an high level overview of how Ouroboros proof of stake works with detailed sections on our changes and additions. For a full description of the Ouroboros protocol, please refer to the original Ouroboros papers: the original and Praos.
A note on Praos, Genesis, and Codaa
Formally, our implementation of Ouroboros is an extension of Praos. There is, however, a newer paper which extends Praos, called Ouroboros Genesis. This extension fixes a vulnerability involving long fork attacks, but this cannot be implemented in a succinct blockchain protocol as described in that paper. Instead, we introduce a new, succinct method for protecting against long fork attacks, which is detailed in another section of this document.
Additions to Praosa
Epoch Ledger Optimizationa
In Ouroboros, nodes need to materialize/keep a ledger at the beginning of the previous epoch in order to VRF evaluations. This is because just having a VRF output is not enough to know that a block was produced honestly. In order to know that a block was won by the node that produced it, the VRF output must be such that it is underneath a threshold determined by the producer's stake, proportional to the total currency in the ledger. In a succinct protocol, such as Coda, materializing/keeping such a ledger in the past is not an easy task. Unlike a non succinct blockchain, nodes cannot arbitrarily request pieces of the chain in the past in order to reconstruct the information they are interested in. This means if we were to implement this feature in a naive manner, we would need to keep in total 3 copies of the entire ledger at any point in time, as well as wait online for at least 2 whole epochs before we could access that information. With some thought, though, we can do much better.
There is a big difference between how Ouroboros proves block winners and how Coda proves them. In Ouroboros, every node needs to validate that a block producer actually won a block when they receive it, meaning they must look up the balance for the public key that evaluated the VRF themselves. In Coda, however, the correctness of the VRF evaluation can be calculated in the SNARK, so other nodes only need to verify the SNARK to know that the block was produced by a winner. Since a producer proves this itself, it can limit the information it needs to store about epoch ledgers to only the account record and the merkle path for any account it can produce blocks for for (itself and all of its delegated accounts). Furthermore, since Ouroboros guarantees us that the point of finality will be reached before two epochs, the producer can wait to capture this information after finalization, futher limiting the information it needs to store. This information is then fed into the SNARK, which proves that: 1) the VRF evaluation is accurate for the provided public key, and 2) the account for the public key exists in the epoch ledger with a balance that creates a VRF threshold greater than the VRF output (using the merkle path to prove the epoch ledger's merkle root from the account). This does not immediately address the issue of a block producer node needing to be online long enough in order to store this necessary information, but it does open up other avenues of the block producer acquiring that information. Mainly, the block producer could request an account record and merkle path proving it's existence at a given epoch ledger. In the current implementation, no nodes store this information and make it available for access, but one could imagine in the future a service being built that would allow block producers to get online and active quicker by providing this information, possibly for some sort of fee.
Long Fork Attack Preventiona
TODO
Configuration Constant Modificationsa
TODO
Implementation Detailsa
TODO