General Estimate Safety Consensus Protocols
An "estimate safety consensus protocol" (the terminology will be made clear shortly) requires the following things:
- a set of possible consensus values, (i.e. we need to know what we're deciding on);
- a logic, , in which the propositions are true or false statements about elements of ;
- a category, , (in the mathematical sense, see Wikipedia for an overview) representing the protocol, where the objects in are the protocol states and the morphisms are the protocol executions;
- a function called the estimator which maps protocol states to propositions in the logic,
We say that a proposition,
, has estimate safety on a protocol state, , if for all possible future states of the estimator implies . Given a few reasonable constraints on the logic and estimator (see original paper
for details), we obtain the following consensus safety result: if and have a common future state then their safe estimates cannot be contradictory (i.e. if has estimate safety on then cannot have estimate safety on ). Therefore, if nodes act according to the estimator, they cannot reach states with views that are irreconcilable and hence consensus is always possible. Moreover, once a node sees that a proposition is safe, it knows that proposition will remain true for the final consensus as well.
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,
, will consist of all possible block directed acyclical graphs (blockDAGs). The reason for the DAG structure as opposed to a chain structure is that multiple parent block pointers will be need for some parts of the consensus protocol. A "block" in this context will have the following attributes:
- parent block pointer(s)
- attached "political capital" (we'll get to where this comes from and what it is for shortly)
- 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,
. Here it seems to be easiest and most sensible to think about natural statements which are either true or false. For example, "block is in the DAG" or "block has parent ". Ultimately, the statement we will be most concerned about will be the former, as this is our "fork choice rule". (For a rigorous mathematical treatment, we would need to be much more precise about the details of the logic. But the intuition above is enough for our purposes here.)
The Protocol's Specification
Now we give a detailed specification of the protocol itself, which mathematically we think of as a category,
. The protocol states are elements from the set of triples , where is the intended action, is the balance of "political capital" and is a history of received messages. Messages consist of requests from users to run smart contracts as well as blocks from other validators. Messages which contain blocks must be cryptographically signed by the validator who created it. The protocol executions are the actions "change intent", "act", and "receive message" (as well as the "do nothing" action and any combination of the various actions, as these are the requirements for a category).
Before giving the details of how each protocol execution updates the protocol state, we need to define the estimator,
, because it is needed by the protocol. As mentioned above, the logical propositions which the estimator is most concerned with are those related to which blocks are in the DAG. I.e. is the fork choice rule; it selects which of multiple possible alternative blocks should be selected to continue the structure. In proof-of-work blockchain protocols this corresponds to the head of the chain that has the most work put into it. Here, we use the greedy heaviest observed sub-tree (GHOST) rule, which picks the block with the highest "score" to continue the structure. The score of a block, , with respect to a message history, , is the sum of the weights of the blocks in the DAG of which are the most recent message in from their sender, where the weight of a block is defined (recursively) by , where is a parameter of the protocol, are the blocks acknowledged in and is the amount of political capital attached to . That sentence is a lot to unpack, so let's give an example.
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 - b6, B - b5, 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(b6) = 3, W(b5) = 4f2, and W(b4) = 2f. From these, we determine the score of each by walking through the DAG and obtain Score(b6) = 3 +4f2 + 2f, Score(b5) = 4f2 + 2f, and Score(b4) = 2f. Therefore, b6 has the highest score and so a future block created by A must build from b6, unless she receives a new message which changes the scores.
Notice that if we look back one message (before A created b6), Score(b5) = 4f2 + 2f + 2 (the +2 comes from b1, which would have been A's most recent message if b6 did not exist), was the highest, which is why A would have chosen to create b6 on top of b5. Also note that b3 and b4 can be thought of as the other two validators "promoting" A's block, while b5 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
, where is the amount of political capital earned by the block . Note that the most recent message constraint prevents going back to promote old blocks to get extra political capital. The single acknowledgement only rule similarly prevents rapid "political capital mining" through repeated promotion of the same block.
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
(say 1 week for example). This means finality is relative, depending on when a message was received, but practically that does not pose much of a problem when the timeframe is sufficiently long. This does allow for the possibility of consensus failure if two nodes finalize mutually exclusive blocks, however this situation is also unlikely when the time window is long and due to the incentives discussed in the following section.
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
and GHOST only considers most recent messages) are more likely to be used to continue the DAG because they have a higher score. Thus, promoting is good for everyone since the promoter earns political capital for future use and the promoted is more likely to retain their fees. Joining is hence even more incentivized because it sums over all the benefits of individual promotions.
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:
What should be the value of
? Should it change over time depending on the number of participants in the network? These questions remain to be answered and perhaps some simulations are needed to inform those decisions.
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
, the geometric series will converge to a finite value. Moreover, the single acknowledgement rule prevents the creation of multiple such chains.
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.
- Allow join of confliting blocks, where a solution of the conflict is proposed simultaneously with the acknowledgement of the independent pieces of the blocks.
- 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.