Page Comparison

This description is based on Vlad Zamfir's correct-by-construction consensus protocols (see papers here and here for detailed descriptions) as well as discussions with Greg Meredith and others on the RChain development team. A simulation engine based on what is described on this page is being developed. The code is available on RChain's GitHub.

General Estimate Safety Consensus Protocols

An "estimate safety consensus protocol" (the terminology will be made clear shortly) requires the following things:

1. a set of possible consensus values, 

   Mathinline
   host 7bf7a548-f937-390d-b7ee-64c4940fe12e body \mathbf{C}

    (i.e. we need to know what we're deciding on);
2. a logic,

   Mathinline
   host 7bf7a548-f937-390d-b7ee-64c4940fe12e body \mathcal{L}_\mathbf{C}

   , in which the propositions are true or false statements about elements of 

   Mathinline
   host 7bf7a548-f937-390d-b7ee-64c4940fe12e body \mathbf{C}

   ;
3. a category, 

   Mathinline
   host 7bf7a548-f937-390d-b7ee-64c4940fe12e body \mathbf{\Sigma}

   , (in the mathematical sense, see Wikipedia for an overview) representing the protocol, where the objects in 

   Mathinline
   host 7bf7a548-f937-390d-b7ee-64c4940fe12e body \mathbf{\Sigma}

    are the protocol states and the morphisms are the protocol executions;
4. a function called the estimator which maps protocol states to propositions in the logic, 

   Mathinline
   host 7bf7a548-f937-390d-b7ee-64c4940fe12e body \mathcal{E}: ob(\mathbf{\Sigma}) \rightarrow prop(\mathcal{L}_\mathbf{C})

We say that a proposition,

RChain's Estimate Safety Consensus Protocol

THIS SPECIFICATION IS NO LONGER ACCURATE. THE RESEARCH INTO THE USAGE OF POLITICAL CAPITAL SHOWED THAT IT WAS NOT NECESSARILY A GOOD IDEA. SEE Details of Proof-of-Stake in RChain FOR A MORE RECENT DESCRIPTION.

For RChain we need to fill in the pieces of a generic estimate safety consensus protocol to meet our needs. In doing so we still retain the desired consensus safety result above.

The Consensus Values

First the set of possible consensus values, 

• parent block pointer(s)
• attached "political capital" (we'll get to where this comes from and what it is for shortly)
• data
• justification (pointers to other blocks the validator had seen when this block was created)

The data a block contains will depend on what sort of block it is. Most relevant to users will be blocks which contain a "schedule" of transactions that occur on the RhoVM (more details on that elsewhere). However, most relevant to the present discussion will be blocks which contain "acknowledgments" of other blocks in the DAG. These blocks play an important role in the consensus protocol, as we will soon see. The data could also enforce a "slashing condition" and thus punish validators for producing invalid blocks (as explained below).

The Logic and Propositions

Second, we need to define the logic we use to talk about the blockDAG, 

The Protocol's Specification

Now we give a detailed specification of the protocol itself, which mathematically we think of as a category, 

Before giving the details of how each protocol execution updates the protocol state, we need to define the estimator, 

Suppose there are 3 validators: A, B, and C. Let us take the perspective of A and suppose she has a message history which is consistent with the following diagram:

In the diagram, blocks are aligned above their creator, each is labelled with a name (for future reference) and the amount of political capital attached to the block. Arrows indicate parent block pointers; additionally, those marked with "ack" also indicate acknowledgment data of the target block is present in the source block. This message history shows that the latest message from each sender is: A - b₆, B - b₅, C - b4; therefore, only these blocks will have a non-zero score. Using the formula above, the weight of each of these blocks is: W(b₆) = 3, W(b₅) = 4f², and W(b₄) = 2f. From these, we determine the score of each by walking through the DAG and obtain Score(b₆) = 3 +4f² + 2f, Score(b₅) = 4f² + 2f, and Score(b₄) = 2f. Therefore, b₆ has the highest score and so a future block created by A must build from b₆, unless she receives a new message which changes the scores.

Notice that if we look back one message (before A created b₆), Score(b₅) = 4f² + 2f + 2 (the +2 comes from b₁, which would have been A's most recent message if b₆ did not exist), was the highest, which is why A would have chosen to create b₆ on top of b₅. Also note that b₃ and b₄ can be thought of as the other two validators "promoting" A's block, while b₅ acts as a "join" of the previous two non-conflicting blocks into a single block, thus allowing the structure to continue without leaving any blocks which are in agreement behind.

Let us now return to specifying the protocol executions. The change intent protocol execution simply changes the intended action, while act triggers the current intended action. The two possible intended actions behave as follows:

• Propose - Create a schedule of transactions from one or more of the unprocessed smart contract requests in the message history. Create a block with parents based on names involved in the contract (see Namespaces for more details) and the GHOST fork choice rule (see specification above), some amount of political capital attached (chosen by validator, note that more political capital means more weight for the block, which in turn means it is more likely to be selected by the GHOST fork choice rule), the schedule created as the data, and all blocks from the message history as the justification (an optimization here would be to only include blocks that are relevant in the justification instead of all blocks).
• Acknowledge - I.e. promote or join. Choose any number of independent blocks which are the most recent message in the message history from that sender (note that one block is always an option, which would be "promoting"). Independent is defined as neither being reachable from the other through DAG connections and any data contained in the parts of their DAGs which are not connected do not conflict. Create a block with the chosen blocks as parents, some amount of political capital (note that this could be zero and the block still has weight due to the recursive definition of weight on the acknowledgments, but a non-zero amount could also be chosen to further increase the weight), the chosen blocks as acknowledgments in the data and all blocks from the message history as the justification (an optimization here would be to only include blocks that are relevant in the justification instead of all blocks). Note that none of the chosen blocks can have been acknowledged by the validator previously (this is verified through the block justification).

The effect of both executions on the protocol state is to add the produced block to the message history (i.e. a validator instantly receives all messages they send out to the network) and reducing the political capital balance by the amount attached to the block. Additionally, the political capital balance is increased based on what was acknowledged in the block according to the recursive formula 

The final protocol execution, receive message, is not as simple as it first appears. Of course, it adds the new message to the message history, but it is also important that the message is validated during this action. This step is necessary to ensure the integrity of the blockDAG; indeed, since this is a trustless system, all validators must independently check all the messages they receive. There are a few different things which must be validated when a new message is received:

• The message does not produce an equivocation - An equivocation is defined as a pair of messages from the same sender where neither justifies the other; that is to say that neither message appears in the justification (or recursively inside those justifications) of the other message. This is a type of Byzantine fault because it shows that the sender is behaving as if they are running two independent versions of the protocol. Otherwise, the latest message from a sender would include all past messages from that sender in its justification.
• If the message is a proposed block of transactions, then those transactions are valid - I.e. the smart contracts were not already executed by a previous block and using the transactions to update the virtual machine state succeeds without errors. E.g. a transaction which causes a double spend should be an error and thus not valid.
• If the message is a join-type acknowledgement, then the blocks which are acknowledged are all indeed independent and have not been acknowledged by the same sender previously - E.g. the same transaction is not run in more than one acknowledged block.
• If the message is a slashing block, then it does indeed correspond to a real violation.
• If the message is any sort of acknowledgement, then all blocks which are acknowledged are themselves valid - I.e. this bullet makes validation a recursive process.

If any of the above are violated, then the message is invalid, and the infraction must be reported. In this circumstance a new "slashing" block will be created which punishes the offending sender(s) of the invalid message(s).

One final piece of the protocol is a notion of finality, i.e. how do we know when a block will be in the DAG forever? Current blockchains use the depth of a block as a proxy for finality and technically no block is ever truly final. Depth of a block can be used here too to get a sense of how likely it is that a block will remain part of the main DAG, however we can also introduce reasonable "synchrony constraints" to have true finality. A validator (or user) considers a block to be final after it has been in their message history for a time 

Economic Considerations: Incentives for earning and spending political capital

As with other blockchains, the validator which proposes a block of transactions also includes some transactions reflecting the "fees" (in the form of REV) earned by the validator for performing the computation. Therefore, a validator is incentivized to ensure that a block they create remains in the main DAG, otherwise the transactions in which they were rewarded fees would be lost. The GHOST fork choice rule causes blocks with more weight to be more likely to end up in the main DAG, therefore, a validator who attaches a lot of political capital to a block they create is more likely to retain the fees they were rewarded. Thus, spending political capital when proposing blocks is economically incentivized. Moreover, since political capital is baked into the consensus protocol, the only way to earn political capital after spending it is to acknowledge other blocks. Blocks which are acknowledged by someone other than their creator (the score of a self-promoted block, with no additional political capital, is lower than the score of the original since 

The benefits of incentivizing behaviour in this way are 

• automatic validator rotation – since the best way to earn political capital is from what others have spent, flow of political capital (and thus ability to propose blocks) is between different validators;
• reduced forking – promoting and joining work to keep a single main DAG;
• improved liveness – promoting and joining weed out alternative forks quickly.

Slashing: Punishments for invalid blocks

Validators who produce invalid blocks should be prevented from doing so again in the future, therefore the punishment should involve a reduction in their balance of political capital. In fact, allowing the political capital balance to go arbitrarily negative due to slashing (but not through attaching to a block, otherwise political capital would be in limitless supply) would prevent a bad validator from proposing blocks for as long as desired. However, reconciliation would always be possible in principle because the validator could still earn political capital and slowly bring their balance back above zero, if desired.

The details around what precise amounts will be deduced for various violations has not yet been worked out.

The one free parameter in the protocol: 

Mathinline
host 7bf7a548-f937-390d-b7ee-64c4940fe12e body f

What should be the value of

Initiating the protocol: Where do the first validators and political capital come from?

Since political capital is earned only through promoting blocks which already have political capital attached to them, a natural question is where the first political capital comes from. One solution is to have genesis blocks have some amount of political capital attached to them. Then all validators (regardless of when they join) have at least one block to promote in order to increase their political capital balance from the initial value of zero. The single acknowledgement rule prevents this from being exploited to gain unbounded amounts of political capital. Note that even if a validator created an infinite chain of promotion blocks stemming from the genesis then because 

A related question is who gets to be validators? A simple answer, which is enabled by this framework is: everyone. Yes, everyone; at least, everyone that wants to. If all new users who join the network start with a political capital balance of zero then they cannot propose new blocks (at least not ones that will stick around), but they can still participate in the validation process. Or they can go on with a balance of zero as a regular user, its totally up to them. Again, since political capital can only be earned through participating in the consensus process (and bad participation is punished), we ensure that only those really interested in the network can contribute future blocks, while still leaving the option open for anyone to reach that level.

Bad Behaviour Technically Allowed in Present Protocol Specification

• Any time you propose a block, immediately promote it yourself. This prevents others from acknowledging your proposed block directly (since only most recent messages can be acknowledged), thus reducing the amount of political capital your opponents can gain from your proposal. This does reduce the score of the branch you are building (since score only considers most recent messages and the weight of the promote block will be lower than the original proposal), therefore opening the possibility that your block will lose the fork choice rule. So, it is not yet clear under what circumstances this strategy to monopolize political capital would be successful.

• Flood the network with pointless acknowledgements, attempting to crash smaller nodes. E.g. write a script that spawns an infinite chain of acknowledgement blocks rooted at genesis; instant DoS attack. As discussed above, this attack is not encouraged within the system itself, but if there is some external reason why someone wants to bring down RChain, this is a conceivable way of doing it. A simple (though inconvenient) way of getting around this would be to put require the validator to go through a captcha of some sort before an acknowledgement can be sent out. Another option would be to have a built-in firewall of sorts that automatically blacklists another validator when this kind of attack is detected.

Future Optimizations

• Allow join of confliting blocks, where a solution of the conflict is proposed simultaneously with the acknowledgement of the independent pieces of the blocks.

Other Notes

• What happens when a validator leaves for several months and then returns - how is trust re-established without opening the network to attack?
  • Political capital is earned through being active in the consensus process and hence a proxy for trust. This question is a good argument for political capital to have a "half-life" of some kind. This would mean that when the validator returns they would need to re-engage with the network before regaining their previous status. How long this half-life should be is up for debate.
• Do we have a solution to the Prisoner's dilemma? Transaction receipts (in lieu of every validator validating every shard that shares cross-shard state) create a Prisoner’s dilemma.
  • Prisoner's dilemma, when played as an infinitely repeated game (as it would be in this case), has an optimal strategy of cooperate by default and even forgive one defect before losing trust. We simply allow the game to play out and trustworthy namespaces will get along fine, while non-trustworthy ones are isolated from the rest of the network. We should also have at least some cross-namespace validators to ensure that one bad player does not ruin the reputation of an entire namespace.
• Is it possible to manipulate the consensus protocol to get free storage? I.e. if consensus history needs to be stored forever as proof of the consensus result, could that information be used by a client instead of paying for proper storage?
  • Possibly... Could try to avoid such situations by enforcing a normal form of the data stored in acknowledgement blocks.