Author Topic: Delegated Proof of Stake (DPOS) White Paper  (Read 80115 times)

0 Members and 1 Guest are viewing this topic.

clout

  • Guest
does dpos or trustee model have faster block times and does that matter?


Offline bytemaster

Shares are already voting at genesis at an even 1% per delegate.

Every transaction moves 1 vote per 'satoshi' of the inputs.

100 delegates is the minimum, it is bootstrapped by us nominating them.... in practice the delegates will be only a small number of individuals with many keys. 

The blockchain tracks a moving average of the transaction fees and pays the delegate that average rather than based upon the transactions they include on their turn, this prevents perverse incentives.

The scoring / ranking strategy is all client side and thus can be changed at any time by any client developer. 
For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline vikram

I have been putting together more detailed algorithm documentation here:

http://bitshares.org/documentation/group__dpos.html

If you see anything that needs correction or clarification let me know... the webpage is generated from the following doxygen file:

https://github.com/BitShares/bitshares_toolkit/blob/master/libraries/blockchain/dpos.dox

My questions:

Quote
At all times every share is either voting for or against some delegate but not both.
Are shares already voting at genesis?

Quote
Every transaction moves a vote from one delegate to either the same delegate or another delegate.
Just a single vote or proportional to stake of transaction inputs? If the latter, then proportional to CDD, input BIPS, or what?

Quote
All delegates must register a unique identifier, that can be used to vote for or against them [...] delegates are registered using the bts::blockchain::claim_name_output class
How is the chain bootstrapped i.e. how are the first blocks created so that prospective delegates can register identifiers? What is the minimum number of delegates needed for the chain to operate?

Quote
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.
So a delegate receives 10% of the transaction fees for a block it signs, while the remaining 90% become company dividends?

Quote
Voting Algorithm [...] Delegate Scoring [...]
Is this simply the particular voting and ranking strategy that will be used by the reference wallet implementation?
« Last Edit: April 15, 2014, 05:53:36 am by unlimited_power »

Offline bytemaster

I have been putting together more detailed algorithm documentation here:

http://bitshares.org/documentation/group__dpos.html

If you see anything that needs correction or clarification let me know... the webpage is generated from the following doxygen file:

https://github.com/BitShares/bitshares_toolkit/blob/master/libraries/blockchain/dpos.dox

For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline bytemaster

So I can 'downvote' his keyhotee id if he messes things up?

Keyhotee IDs have no built in voting system in the original design... just a global 'free' key/value pair system. 
For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline xeroc

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 12922
  • ChainSquad GmbH
    • View Profile
    • ChainSquad GmbH
  • BitShares: xeroc
  • GitHub: xeroc
So I can 'downvote' his keyhotee id if he messes things up?

Offline bytemaster

Could we link the BOD with their individual keyhotee ID such that cheating really hurts?

A delegate could use the same public key as a way to win votes. 
For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline bytemaster

For these representatives, since they know they will generate the certain block at certain timeslot, I think they could define, generate and add some specific tx to the block they made based on the analysis of all the TXs in their hand before they produce the next block. By doing this, they could get additional profit. It's not fair to other players in the market since they manupilate the market directly although on a slight level.

In longterm, maybe we have to take this previlege and its profit as necessary cost of system, but not sure how this will impact the whole market operation and people's confidence to the market. However, during the group discussion of my friends, we have an idea which may resolve this issue.

As mentioned in whitepater, the activity of excluding some TXs on purpose will be found later then that representative might be removed from the list. But the key of this kind of manupilation is the representative could add his/her own tx after he/she checked up all the other TXs, which is almost impossible to be found and punished. So we should split all/each TX in 2 parts. In part one, the TX broadcasted w/ the detailed trade reques content "enclosed". When the representative receive it, he/she could just add this TX into the block to confirm that this TX is valid but no trading actually happened at that time. Then in next block, the part 2, the next representative's job is to "open the envelope" and complete the trading(e.g. match buy orders and sell orders ). Thus, meaningless to add TX even you know what the best deal for this block since the new added order could just be completed at next block.

Not sure if above proposal("envelope transaction") is technically possible and make sense for marketing perspective. Just want to raise this concern and idea for discussion in case the DPOS is so important and we all want to make it as better as possible.

Thanks.

Your solution is technically possible, but I do not think it solves any problems.   No one can be harmed by 'front running' because everyone always gets what they ask for.    The most a delegate cannot execute a buy and sell at the same time based upon picking and choosing transactions in the block so they must always pick a side of the market to be on.   This may given them a slight edge but nothing that would be a worthwhile problem to solve.  The 2 phase approach would require extra blockchain space, the fees charged to make these extra transactions are likely more than could be saved by delegates attempting to manipulate the network.

So while a delegate could gain some small benefit, statistical analysis would quickly reveal they are using this strategy and thus they would likely get voted out if anyone cared.   



For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline xeroc

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 12922
  • ChainSquad GmbH
    • View Profile
    • ChainSquad GmbH
  • BitShares: xeroc
  • GitHub: xeroc
Could we link the BOD with their individual keyhotee ID such that cheating really hurts?

Offline yidaidaxia

  • Full Member
  • ***
  • Posts: 179
    • View Profile
For these representatives, since they know they will generate the certain block at certain timeslot, I think they could define, generate and add some specific tx to the block they made based on the analysis of all the TXs in their hand before they produce the next block. By doing this, they could get additional profit. It's not fair to other players in the market since they manupilate the market directly although on a slight level.

In longterm, maybe we have to take this previlege and its profit as necessary cost of system, but not sure how this will impact the whole market operation and people's confidence to the market. However, during the group discussion of my friends, we have an idea which may resolve this issue.

As mentioned in whitepater, the activity of excluding some TXs on purpose will be found later then that representative might be removed from the list. But the key of this kind of manupilation is the representative could add his/her own tx after he/she checked up all the other TXs, which is almost impossible to be found and punished. So we should split all/each TX in 2 parts. In part one, the TX broadcasted w/ the detailed trade reques content "enclosed". When the representative receive it, he/she could just add this TX into the block to confirm that this TX is valid but no trading actually happened at that time. Then in next block, the part 2, the next representative's job is to "open the envelope" and complete the trading(e.g. match buy orders and sell orders ). Thus, meaningless to add TX even you know what the best deal for this block since the new added order could just be completed at next block.

Not sure if above proposal("envelope transaction") is technically possible and make sense for marketing perspective. Just want to raise this concern and idea for discussion in case the DPOS is so important and we all want to make it as better as possible.

Thanks.
PTS: PmUT7H6e7Hvp9WtKtxphK8AMeRndnow2S8   /   BTC: 1KsJzs8zYppVHBp7CbyvQAYrEAWXEcNvmp   /   BTSX: yidaidaxia (暂用)
新浪微博: yidaidaxia_郝晓曦 QQ:36191175试手补天

Offline vikram

This is awesome. Dan, please update the whitepaper to reflect the updates when you get the time, so that we can continue to publicize it.

Offline CWEvans

  • Full Member
  • ***
  • Posts: 183
    • View Profile
Quote
1.3 Ripple Consensus

The Ripple consensus algorithm allows a group of nodes to agree to reach consensus based upon the concept of a unique node list. The initial unique node list is like a club where 51% of the club members must vote to include a new member. Consensus will follow this core 51% and those outside have no influence. Because this club starts out “centralized” it will remain “centralized” and if it ever becomes corrupted there is nothing the shareholders can do. Like Bitcoin and Peercoin, Ripple separates shareholders from voting rights and is thus much more centralized than other systems.

I'm putting that on a t-shirt!

Categorizing cryptocurrency systems according to the seat of voting power is extremely important.

Quote
2.5 Are 100 Representatives Decentralized?

The definition of decentralized is hard to pin down because it has become a buzzword. We consider the free market to be the ultimate form of decentralization and barriers to entry to be the basis of all centralization. Like many things, there are degrees of centralization so we will instead compare the relative centralization of Delegated Proof of Stake to the other alternatives.

This point is ignored wayyy too often. In every critique, one should state explicitly compared to what.

Quote
3.1 Preventing Exclusion of Transactions

Having 100 representatives each elected by the shareholders and being required to take turns means that any transaction that is approved of by even 1% of the shareholders can be included in less than 30 minutes. This means that no representative can benefit by excluding transactions that vote for other representatives.

This should be expanded on and include an example.

Quote
<h4>4.0 Transactions as Proof of Stake (TaPOS)</h4>

should be: <h3>4.0 Transactions as Proof of Stake (TaPOS)</h3>

Every vote for a delegate can be either *for* or *against* them.   A delegate is ranked according to the sum of the votes for them minus the votes against them.   With this process in place it is now possible for delegates to be fired relatively easily for misbehaving even if the vast majority of a delegates supporters are lazy and not paying attention. 

Although it probably would be overkill in this context, it might be of potential use in a general reputation-scoring system to weight the votes cast as a function of the voter's own ranking in the system.  This way, if a gang of trolls decided to attack a particular user, the impact could be mitigated by the fact that their reputations each carried very little weight.

2) When making a normal transaction the user's wallet always votes for the delegate in their top 10 list with the least votes and pulls votes from the delegate with the most votes.  This will tend to rebalance a user's votes over 10 delegates and help keep the delegate pool well balanced.

Some might find this to be unintuitive. When the time comes, maybe we'll want an animated video that illustrates the underlying logic. Two-and-a-half centuries of representative democracy has many, if not most, believing that first-past-the-post winner-take-all democracy is an immutable force of nature.
« Last Edit: April 06, 2014, 05:27:54 pm by CWEvans »

Offline bytemaster

After talking with Stan on the way to NYC I have a rather significant improvement to DPOS that will make it much more robust:

Every vote for a delegate can be either *for* or *against* them.   A delegate is ranked according to the sum of the votes for them minus the votes against them.   With this process in place it is now possible for delegates to be fired relatively easily for misbehaving even if the vast majority of a delegates supporters are lazy and not paying attention. 

From Sergio Lerner:
Quote
For example, each node should measure:
1. The average latency of each representative
2. The ratio of transactions included in blocks versus the total number of transactions broadcasted (with enough fees).
3. The number of transactions rejected by this block without any reason (discrimination)
4. The number of times a representative has failed to broadcast the block
5. The number of times a representative has cheated by sending his block before his time slot.
6. The number of coins a representative has. (this could be computed if the representative uses the same pubkey for all his coins)

In addition to the statistics Sergio identified there would be the statistic on how often a delegate failed to reference a valid previous block that your client received in time.   This skipping behavior should be punished.

Then we want to have rules that self-regulate / balance the network without significant intervention by the vast majority of the users *or* that will automatically force users to make a judgement when the network needs it.   So here are some additional rules:

0) Assume every wallet has settings that allow the user to specify 10+ delegates that they trust.  They do this one time and never have to touch it unless there are major issues with their list.

1) No delegate may have more than 2% of the vote and this will be enforced by blocking transactions which would push the vote total above 2%.  Users will be warned anytime all of their delegates have over 1.25% of the vote which will give them ample time to select new delegates.   The pro-active users will switch and the inactive users will see their warning go away automatically once the pro-active users switch.   

2) When making a normal transaction the user's wallet always votes for the delegate in their top 10 list with the least votes and pulls votes from the delegate with the most votes.  This will tend to rebalance a user's votes over 10 delegates and help keep the delegate pool well balanced.

3) Any time a client detects any delegate misbehaving by failure to include transactions, produce blocks, or skipping the prior delegates block then the client automatically prioritizes negative votes for this delegate over positive votes for their behaving delegates.    It will not take long for the active transaction volume to accumulate enough negative votes to bump someone from the top 100.  On average it will take less than 24 hours for 0.25% of the share supply to move (assuming it only  moves once per year on average).  0.25% of the users voting against a delegate is likely enough to swing them out of the top 100, especially if clients switch their vote from being 'for' to being 'against' in which case it would be like losing 0.5% in net vote.   

4) Once a delegate is out of the top 200, negative votes are automatically reallocated to positive or negative votes for other delegates. 

5) Many clients can automatically add well behaved delegates to their own approved list after enough observation.  This will allow the network to be self-sustaining while allowing manual intervention by the shareholders if there is a problem. 

At this point we have a solid system that is mostly set it and forget it and which is easily maintained. 




For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline zhangweis

  • Sr. Member
  • ****
  • Posts: 305
    • View Profile
As each transaction contains hash of last block, we can easily get how many blocks it takes a transaction to be included into block chain. This could be a major indicator whether the delegated is performing well as of how much it delays transactions. This indicator can be shown to user (voter) in wallet when they vote. This can encourage delegated to work hard to include transactions as quickly as they can and also discourage cheating by delaying some transactions.
Weibo:http://weibo.com/zhangweis