Date: Thu, 28 Mar 2024 18:15:39 +0000 (UTC) Message-ID: <1420464253.9.1711649739932@daeeb5886584> Subject: Exported From Confluence MIME-Version: 1.0 Content-Type: multipart/related; boundary="----=_Part_8_875650923.1711649739932" ------=_Part_8_875650923.1711649739932 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Content-Location: file:///C:/exported.html
This description is based on Vlad Zamfir's correct-by-construction = consensus protocols (see papers here and here for detailed descriptions) as well as d= iscussions with Greg Meredith and others on the RChain development tea= m. A simulation engine based on what is described on this page is being dev= eloped. The code is available on RChain's GitHub.
An "estimate safety consensus protocol" (the terminology will be made cl= ear shortly) requires the following things:
We say that a proposition,
, has estimate safety on a protocol state,=20 , if for all possible future states of=20 the estimator implies=20 . Given a few reasonable constraints on the logic and estimator (see&= nbsp;origin= al 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 re= ach 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.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 safe= ty consensus protocol to meet our needs. In doing so we still retain the de= sired consensus safety result above.
First the set of possible consensus values,
, will consist of all possible block directed acyclical graphs (block= DAGs). 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 cons= ensus protocol. A "block" in this context will have the following attribute= s: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 re= levant to the present discussion will be blocks which contain "acknowledgme= nts" 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 "sl= ashing condition" and thus punish validators for producing invalid blocks (= as explained below).
Second, we need to define the logic we use to talk about the blockDAG,&n= bsp;
. Here it seems to be easiest and most sensible to think about natura= l 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.)Now we give a detailed specification of the protocol itself, which mathe= matically 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 vali= dator who created it. The protocol executions are the actions "change inten= t", "act", and "receive message" (as well as the "do nothing" action and an= y combination of the various actions, as these are the requirements for a c= ategory).Before giving the details of how each protocol execution updates the pro= tocol state, we need to define the estimator,
, because it is needed by the protocol. As mentioned above, the logic= al propositions which the estimator is most concerned with are those relate= d 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-o= f-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 su= b-tree (GHOST) rule, which picks the block with the highest "score" to cont= inue 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 (recu= rsively) by , where is a parameter of the protocol, are the blocks acknowledged in and is the amount of political capital attached to=20 . 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 fo= llowing 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 att= ached to the block. Arrows indicate parent block pointers; additionally, th= ose 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) =3D 3, W(b<= sub>5) =3D 4f2, and W(b4) =3D 2f. From these, w= e determine the score of each by walking through the DAG and obtain Score(b= 6) =3D 3 +4f2 + 2f, Score(b5) = =3D 4f2 + 2f, and Score(b4) =3D 2f. Therefore,&n= bsp;b6 has the highest score and so a future block created by A = must build from b6, unless she receives a new message which chan= ges the scores.
Notice that if we look back one message (before A created b6)= , Score(b5) =3D 4f2 + 2f + 2 (the +2 comes = from b1, which would have been A's most recent message if b= 6 did not exist), was the highest, which is why A would have chosen t= o create b6 on top of b5. Also note that b3 and b4 can be thought of as the other two validators "promotin= g" 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 cont= inue without leaving any blocks which are in agreement behind.
Let us now return to specifying the protocol executions. The change inte= nt protocol execution simply changes the intended action, while act trigger= s the current intended action. The two possible intended actions behav= e as follows:
The effect of both executions on the protocol state is to add the produc= ed block to the message history (i.e. a validator instantly receives all me= ssages they send out to the network) and reducing the political capital bal= ance by the amount attached to the block. Additionally, the political capit= al balance is increased based on what was acknowledged in the block accordi= ng 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 acknowledgem= ent only rule similarly prevents rapid "political capital mining" through r= epeated promotion of the same block.The final protocol execution, receive message, is not as simple as it fi= rst 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. Thi= s step is necessary to ensure the integrity of the blockDAG; indeed, s= ince this is a trustless system, all validators must independently check al= l the messages they receive. There are a few different things which must be= validated when a new message is received:
If any of the above are violated, then the message is invalid, and the i= nfraction must be reported. In this circumstance a new "slashing" block wil= l 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 d= epth of a block as a proxy for finality and technically no block is ever tr= uly final. Depth of a block can be used here too to get a sense of how like= ly 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 vali= dator (or user) considers a block to be final after it has been in their me= ssage 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 lon= g and due to the incentives discussed in the following section.As with other blockchains, the validator which proposes a block of trans= actions 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 t= he main DAG, otherwise the transactions in which they were rewarded fees wo= uld be lost. The GHOST fork choice rule causes blocks with more weight to b= e more likely to end up in the main DAG, therefore, a validator who attache= s a lot of political capital to a block they create is more likely to retai= n the fees they were rewarded. Thus, spending political capital when propos= ing blocks is economically incentivized. Moreover, since political capital = is baked into the consensus protocol, the only way to earn political capita= l after spending it is to acknowledge other blocks. Blocks which are acknow= ledged by someone other than their creator (the score of a self-promoted bl= ock, with no additional political capital, is lower than the score of the o= riginal 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
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 capita= l balance to go arbitrarily negative due to slashing (but not through attac= hing 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 ba= lance back above zero, if desired.
The details around what precise amounts will be deduced for various viol= ations has not yet been worked out.
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 simu= lations are needed to inform those decisions.Since political capital is earned only through promoting blocks which al= ready have political capital attached to them, a natural question is where = the first political capital comes from. One solution is to have genesis blo= cks have some amount of political capital attached to them. Then all valida= tors (regardless of when they join) have at least one block to promote in o= rder 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 th= en 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, everyon= e that wants to. If all new users who join the network start with a politic= al capital balance of zero then they cannot propose new blocks (at least no= t ones that will stick around), but they can still participate in the valid= ation 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 t= hrough participating in the consensus process (and bad participation is pun= ished), we ensure that only those really interested in the network can cont= ribute future blocks, while still leaving the option open for anyone to rea= ch that level.
Any time you propose a block, immediately promote it yourself. This prev= ents others from acknowledging your proposed block directly (since only mos= t recent messages can be acknowledged), thus reducing the amount of politic= al capital your opponents can gain from your proposal. This does reduce the= score of the branch you are building (since score only considers most rece= nt messages and the weight of the promote block will be lower than the orig= inal proposal), therefore opening the possibility that your block will lose= the fork choice rule. So, it is not yet clear under what circumstances thi= s strategy to monopolize political capital would be successful.
Flood the network with pointless acknowledgements, attempting to crash s= maller nodes. E.g. write a script that spawns an infinite chain of acknowle= dgement blocks rooted at genesis; instant DoS attack. As discussed above, t= his 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 conceiva= ble way of doing it. A simple (though inconvenient) way of getting around t= his would be to put require the validator to go through a captcha of some s= ort before an acknowledgement can be sent out. Another option would be to h= ave a built-in firewall of sorts that automatically blacklists another vali= dator when this kind of attack is detected.