BitShares Toolkit
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
Delegated Proof of Stake

Documents assumptions, algorithms, and details of DPOS Implementation. More...

Documents assumptions, algorithms, and details of DPOS Implementation.

Delegated Proof of Stake (DPOS) is a process by which shareholders can exersize their influence over the generation of blocks by contributing to the selection of delegates. Delegates have one role: produce blocks at the scheduled time and include as many valid transactions as possible.

The following sections outline the algorithm used to ensure the most effective and reliable block generation possible. The network establishes a set of rules and and procedures that aim to keep power decentralized and rapidly handle any abuse.

Assumptions & Invariants

  1. For the purpose of this algorithm design we are making the assumption that the client is synchronized via NTP to within a couple of seconds of UTC time.
  1. At all times every share is either voting for or against some delegate but not both. Every transaction moves a vote from one delegate to either the same delegate or another delegate.
  1. At all times no delegate may have more than 2% of the vote. Any transaction or block that would give a delegate more than 2% of the vote is to be rejected.
  1. Anyone with sufficient stake has a right to vote for themself and produce blocks at the scheduled time. If someone abuses this role then others can deny them this right by voting against them. In this way even large shareholders are kept in check if enough small shareholders stand against them.
  1. The goal of the following algorithm is to minimize extra load on the network in order to maximize transaction processing. The network should operate normally with no extra transactions by the users. To achieve this every transaction (bts::blockchain::transaction) includes an extra field bts::blockchain::transaction::vote that indicates which delegate all outputs for that transaction will vote for.

Delegate Registration

  1. All delegates must register a unique identifier, that can be used to vote for or against them.

    • because this identifier is referenced by every transaction, it is ideal to use as few bytes as possible to represent it. (see fc::signed_int)
    • votes can be for or against a particular delegate, the sign of the delegate identifier indicates whether the votes are positive or negative.
    • delegates are registered using the bts::blockchain::claim_name_output class

      • When bts::blockchain::claim_name_output::delegate_id is 0 indicates that the name is not elegible to receive votes, if the name already has votes then those votes are no longer counted in the ranking of delegates as the delegate has resigned.
      • bts::blockchain::claim_name_output::name can be used to provide a globally unique human readable handle for any purpose.
      • bts::blockchain::claim_name_output::data can be used to provide additional data about the delegate, such as a website.
  1. When registering an identifier a signup fee equal to 100 times the average revenue per block must be paid.

    • This will insure that a delegate must produce at least 1000 blocks to break even and discourage people from running for the delegate position that are not serious.
    • 1000 blocks is between 2 weeks and 2 months depending upon the block interval chosen by the network.
  1. All delegates must renew their registration once per year
    • those in the top 100 may renew for free after 11 months.
    • those who are not in the top 100 must pay the registration fee again.
  1. When a delegate registers they must also specify a unique name, and an optional value to associate with that name. This allows a delegate to include information such as a website along with their registration.

Voting Algorithm

Every wallet contains the following information:

  1. trusted_delegates - array of delegate IDs that are trusted unless evidence to the contrary is observed by the client.
  1. distrusted_delegates - an array of delegate IDs that are implicitly distrusted regardless of any evidence.
  1. observed_delegates - an array of delegate IDs and observed statistical data sorted by this data.

The blockchain tracks the following:

  1. ranked_delegates - a sorted array of all delegates in the block chain by net votes (for - against)

When generating a transaction the wallet must pick exactly one delegate to vote for using the following algorithm:

  1. If any distrusted_delegates are in the top 200 of the ranked_delegates, vote against the distrusted delegate with the highest current rank.
  1. If not voting against anyone, and there are trusted_delegates outside the top 100, vote for the trusted_delegate with the highest rank outside the top 100.
  1. If all trusted_delegates are inside the top 100, vote for the trusted delegate with the lowest rank.
  1. If there are no trusted_delegates in then vote for the observed_delegate with the highest score and less than 1% of the vote.

When generating a transaction the wallet must pick who to take votes from by selecting inputs. The following process is to be used.

  1. If any unspent outputs are voting for a delegate in the distrusted_delegates list, then select all such outputs as inputs to the transaction. This will maximize the rate at which this distrusted delegate will be voted out.
  1. If any unspent outputs are more than 11 months old, then pro-actively include them to renew them.
  1. If more outputs are required, select them in order from oldest to newest to minimize the risk of inactivity fees.

Delegate Scoring

When scoring a delegate a client attempts to guage their performance based upon their own observation of the network. This performance will measure the following statistics

  1. total blocks produced - total blocks produced and signed by this delegate
  1. total blocks missed - if a delegate was scheduled to produce a block and the block was not produced and included in the chain,
  1. median late latency - delta time between when the block was received and when the block should have been produced. This can be caused by many factors, some of which may not be the fault of the producer.
  1. median early latency - if a block arrives early, this measures how early it arrives. This is an indication that either the clients clock is delayed, or the delegate is slow. A delegate that is consistantly earlier than its peers is likely attempting to cheat this metric. A delegate that is consitantly later (late latency) is likely slow. By weighting early/late latency equally no client can gain an advantage over peers and all must strive to achieve the same statistics as all other delegates.
  1. percent of known transactions included in the block that were received prior to the blocks scheduled production time.

    • the ideal value here is 1
  1. percent of unknown transactions included in the block, an indication the delegate may be generating secret transactions.

    • the ideal value here is 0.
  1. total invalid blocks signed, this should be 0 and if it becomes 1 or more the delegate should be fired
  1. percent of maximum fee paid to delegate. The maximum is 10% of average per-block revenue of last 100 blocks.

    • the ideal value here is 0, but delegates do not work for free. Cheaper delegates are ranked higher.

To calculate a delegate score there is no absolute measures we can use, instead we can only compare delegates against eachother. To do this we will rank delegates by each field and then calculate the average of their ranking in each category, perhapse weighted by some constant.

Block Validation

When a block is received the wallet should perform the following actions:

  1. Lookup the observed_delegates record and note the following:

    1. latency
    1. percent of expected transactions that the block included
    1. percent of unexpected transactions that the block included
    1. Validate the block and push it onto the block chain

      1. the last transaction in the block may include a payment to the delegate for up to 10% of the average revenue earned by the network over the last 100 blocks.

Block Producer

Any wallet that contains a registered delegate ID ranked in the top 100 knows when to produce a block based upon the current time. After each block is pushed onto the blockchain, a wallet will lookup the rank of their delegate_id, if the rank is less than 100 then they know the next time that they will produce a block is:

CURRENT_TIME = UTC_SEC / BLOCK_INTERVAL
ROUND_TIME = (CURRENT_TIME / 100) * 100
PRODUCE_TIME = (ROUND_TIME + RANK) * BLOCK_INTERVAL
If PRODUCE_TIME < CURRENT_TIME then PRODUCE_TIME += 100 * BLOCK_INTERVAL

A single wallet may contain multiple delegate IDs.

Confict Resolution

Assume delegates A through F are expected to produce blocks at timeslots 0 through 6 you would end up with a chain that looks like:

A->B->C->D->E->F

However, the order in which blocks are produced can change based upon the contents of the block so suppose B fails to produce a block and thus certain votes are not cast and the new chain looks like:

A->!B->H->I->J->K

If a client is forced to choose between these two alternative chains, then it picks the longer chain, A->B->C->D->E->F over the shorter chain A->H->I->J->K.

Another case is the event where missing B doesn't change the delegate ranking, so delegate C can choose to produce any of the following chains:

W->Z->A->B->C
W->Z->A---->C
W->Z------->C
W---------->C
*---------->C

This can be done for either malicious reasons or because of a network split. In this particular case either node B or C could be the guilty party. If B waited to send then C is legitimate in building off of A, where as if B sent on time the C is attempting to harm B. C cannot sign two different blocks without getting fired, so whatever choice he makes is 'final' for him.

At this point D will pick one of the following:

W->Z->A->B---->D
W->Z->A---->C->D

This will produce two chains that are each the same length but skipped different nodes. D will pick based upon whether he saw B when it was expected. At this point both alternatives are about equal and delegate E gets to resolve the dispute by picking either

W->Z->A->B---->D->E
W->Z->A---->C->D->E

Once E chooses the longest chain is once again clearly defined. If D or E fails to produce a block on time, then this decision making process will continue until one chain is longer than the other. So long as no delegate signs two blocks on different chains or for the same timeslot this process should be guranteed to resolve in an unambigious manner.

Collusion

It may be possible for delegates to collude to produce the following alternatives:

A->B0->C0->D0->...
A->B1->C1->D1->...

In this event you can be sure that delegates B, C and D will be fired once their fraud is detected. In the mean time delegates E through Z would resolve the dispute as soon as it got to their turn (assuming they were online). If all nodes were 'off line' and had no way to determine whehter D or D1 came first then the ultimate dispute resolution is handled by TaPOS (Transactions as Proof of Stake) where the individuals making the transactions included by B-D recorded what they saw at the time. TaPOS over such a short time horizon could be manipulated by a large shareholder (which a delegate is is likely to be.

Conclusion

It will always be possible to identify which chain was public and seen by the most shareholders/delegates by simply inspecting the data after the fact. Any time a delegate misses a block everyone on the network knows that confirmation times must increase to allow enough follow-on delegates to vote on what they saw by producing a block for one chain or another.