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

0 Members and 1 Guest are viewing this topic.

Offline bytemaster

A lot of time and effort has gone into designing the voting system as it is today.   While many kinds of voting are possible in theory we are trying to work within the following constraints:

1) most users are lazy and will not vote, if they did vote most users wouldn't know how to evaluate delegate performance.  This means the voting process needs to be simple with a reasonable automatic voting algorithm based only on statistical data about a delegates performance.

2) Voting shouldn't cost anything and should be transparently invoked as part of normal operation. 

3) Voting is a way of exercising your influence over a percent of the block production proportional to your stake via a delegate.  It should not result in the majority dictating the rules on who all delegates should be or those with a minority opinion will have no representation among the delegates.   

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 Agent86

  • Sr. Member
  • ****
  • Posts: 471
  • BTSX: agent86
    • View Profile
Quote
More importantly, storage requirement (not the blockchain, the constructed chain DB) increases to the same amount as it would be if you put the entire new vote set in each transaction.
I'm not sure I agree with this either.  The constructed database doesn't even have to specify which particular stake each vote comes from, it just needs to collect the aggregate votes for each delegate and then add or subtract from that accordingly.

No, I think you can't get around storing the votes because you have to know who to subtract the vote from (or with diffs, who you are allowed to subtract from). I think it is amortized w.r.t. transaction fees paid but it will still increase our max blockchain size by a large constant factor, terabytes instead of 100s of GB
Toast is right you need to store who everyone is voting for (multiple delegates instead of 1),  If you make a transaction that says I only want to vote for delegate 4, You need to know that your stake was previously voting for delegates 1,2,&3 to know who to take votes away from.  (sorry, I posted without thinking)

Maybe people would have less reason to split up their stake to vote for different people?
I think people have to pay an annual registration fee for delegates so maybe this keeps people from registering junk delegates?
« Last Edit: June 19, 2014, 11:49:29 am by Agent86 »

Offline liondani

  • Hero Member
  • *****
  • Posts: 3737
  • Inch by inch, play by play
    • View Profile
    • My detailed info
  • BitShares: liondani
  • GitHub: liondani


. What am I missing that dictates the voting information has to be stored indefinitely ?  Once someone changes their vote why do you need to keep around all the historical votes ?

+5%




Sent from my ALCATEL ONE TOUCH 997D using Tapatalk


Offline gamey

  • Hero Member
  • *****
  • Posts: 2253
    • View Profile
I am already assuming compression and maximum pruning. A side chain doesn't save space since it is required for validation.

Sent from my SCH-I535 using Tapatalk

So if you prune the vote sidechain every week (or day) it still blows up so much to be an issue?  Wow.  I guess I can see that with the possible number of delegates etc.  I always kinda assume my suggestions are obvious to you guys, but I post them on the off chance they're not.... never know.

If you could prune the sidechain every week then you could prune the main chain every week too. As long as you need the sidechain to validate a block then it's pointless to not just include that data in the main chain, the client will need both.

I guess it has to be one big deterministic machine from the genesis block.  I mean that would obviously be the most simple and trustful way to do it. However, it isn't so intuitive to me that this is necessary.  It seems that perhaps once the blocks are signed etc and within a certain amount of days the voting data could be discarded.  I guess it would be the same as discarding the hash values from blocks.

So why couldn't there be a chain/list of hashes to validate the blocks?  So you keep the voting info around for some reasonable time in a separate chain and discard/prune it.  The main chain has hashes for longterm/auxillary validation.

What am I missing that dictates the voting information has to be stored indefinitely ?  Once someone changes their vote why do you need to keep around all the historical votes ?
I speak for myself and only myself.

Offline toast

  • Hero Member
  • *****
  • Posts: 4001
    • View Profile
  • BitShares: nikolai
I am already assuming compression and maximum pruning. A side chain doesn't save space since it is required for validation.

Sent from my SCH-I535 using Tapatalk

So if you prune the vote sidechain every week (or day) it still blows up so much to be an issue?  Wow.  I guess I can see that with the possible number of delegates etc.  I always kinda assume my suggestions are obvious to you guys, but I post them on the off chance they're not.... never know.

If you could prune the sidechain every week then you could prune the main chain every week too. As long as you need the sidechain to validate a block then it's pointless to not just include that data in the main chain, the client will need both.
Do not use this post as information for making any important decisions. The only agreements I ever make are informal and non-binding. Take the same precautions as when dealing with a compromised account, scammer, sockpuppet, etc.

Offline gamey

  • Hero Member
  • *****
  • Posts: 2253
    • View Profile
I am already assuming compression and maximum pruning. A side chain doesn't save space since it is required for validation.

Sent from my SCH-I535 using Tapatalk

So if you prune the vote sidechain every week (or day) it still blows up so much to be an issue?  Wow.  I guess I can see that with the possible number of delegates etc.  I always kinda assume my suggestions are obvious to you guys, but I post them on the off chance they're not.... never know.
I speak for myself and only myself.

Offline toast

  • Hero Member
  • *****
  • Posts: 4001
    • View Profile
  • BitShares: nikolai
I am already assuming compression and maximum pruning. A side chain doesn't save space since it is required for validation.

Sent from my SCH-I535 using Tapatalk

Do not use this post as information for making any important decisions. The only agreements I ever make are informal and non-binding. Take the same precautions as when dealing with a compromised account, scammer, sockpuppet, etc.

Offline gamey

  • Hero Member
  • *****
  • Posts: 2253
    • View Profile
All the various compression methods any decent programmer should be aware of.  If you guys think it is too much data then perhaps a separate chain.  The requirements of a chain that keeps track of funds and decisions regarding funds is far different than the requirements of knowing who voted for who.  Voting state is not required to be kept forever.  So a smaller chain that is pruned would be sufficient.  It adds to complexity but not terribly so.

Sent from my SM-N900P using Tapatalk

« Last Edit: June 19, 2014, 03:01:55 am by gamey »
I speak for myself and only myself.

Offline Agent86

  • Sr. Member
  • ****
  • Posts: 471
  • BTSX: agent86
    • View Profile

No, I think you can't get around storing the votes because you have to know who to subtract the vote from (or with diffs, who you are allowed to subtract from). I think it is amortized w.r.t. transaction fees paid but it will still increase our max blockchain size by a large constant factor, terabytes instead of 100s of GB.

Let's try to think of a solution to the storage requirements for approval voting.
+5%

Offline toast

  • Hero Member
  • *****
  • Posts: 4001
    • View Profile
  • BitShares: nikolai
it is very easy for an attacker to max out the bandwidth, forcing other people to pay a higher transaction fee once they want to vote using the stake they received from him (trx fee is per-byte).
I think I addressed this by allowing a transaction to simply state "all prior delegate selections are void"  It doesn't need to individually specify to not vote for each delegate that was previously selected.

point for you!

Quote
More importantly, storage requirement (not the blockchain, the constructed chain DB) increases to the same amount as it would be if you put the entire new vote set in each transaction.
I'm not sure I agree with this either.  The constructed database doesn't even have to specify which particular stake each vote comes from, it just needs to collect the aggregate votes for each delegate and then add or subtract from that accordingly.

No, I think you can't get around storing the votes because you have to know who to subtract the vote from (or with diffs, who you are allowed to subtract from). I think it is amortized w.r.t. transaction fees paid but it will still increase our max blockchain size by a large constant factor, terabytes instead of 100s of GB.

Quote
Quote
A bad delegate can:
* exclude transactions
* miss blocks on purpose (delay confirmations)
* exacerbate an current fork by a block
* pay only his supporters out of his income

The last one is the only one that could complicate things. The only stable situations I can imagine are if he would always get voted out in favor of someone paying normal dividends, or if every delegate is paying only his supporters and the situation looks almost identical.

I think "approval voting" will not reward vote buying.  So I'm not worried about delegates only paying their supporters using approval voting.  Bad delegates will get voted out even if it isn't immediate and it doesn't seem like they have much to gain by misbehaving.

If all delegates only pay their own supporters the situation is not at all "almost identical."  It means that delegates can't give money to a developer or spend money on a marketing campaign that benefits everyone, because their voters just want as much of a kickback as they can get.  It's not a good situation.  If delegate positions can be bought than someone can buy over 50% of the delegates.

I would be very surprised if we don't eventually move away from the current voting proposal or get out-competed by someone else who does it right.  I'm not saying it would be an immediate disaster because there probably isn't anyone interested in creating problems.

There will almost certainly be improvements to the voting system. The more important question is, when do we cross the point of no return? The scary thought is that it could be right out of the gate, but I'm not sure.

Quote
Also from a user experience perspective it is way easier to just select the delegates you like, rather than having these trust scores and balancing which stake goes to which delegate and when to downvote etc. It's a turn off, hard to understand, and is flawed anyway.  Why try to get people used to it?

This is also a good point.


Let's try to think of a solution to the storage requirements for approval voting.
Do not use this post as information for making any important decisions. The only agreements I ever make are informal and non-binding. Take the same precautions as when dealing with a compromised account, scammer, sockpuppet, etc.

Offline gamey

  • Hero Member
  • *****
  • Posts: 2253
    • View Profile

This is interesting.  It does become quite apparent that downvoting costs a user where upvoting can only help them. (using a few assumptions)

Looking at the different voting systems would be very useful. 

Perhaps separating downvoting from upvoting so they are no longer mutually exclusive.  So you get both an upvote and a downvote.  That means that the choice to downvote will not have a cost associated with it. I need to reread a lot of this thread though to understand the implications.
I speak for myself and only myself.

Offline carpet ride

  • Hero Member
  • *****
  • Posts: 544
    • View Profile
Since the topic has picked up some steam, I think it's worth noting that there are a quite a few more voting methods, such as Penrose, Kemeny-Young, and the maximum likelihood method

See a more complete list here: http://en.wikipedia.org/wiki/Category:Voting_systems

« Last Edit: June 19, 2014, 01:15:37 am by bed »
All opinions are my own. Anything said on this forum does not constitute an intent to create a legal obligation between myself and anyone else.
Check out my blog: http://CertainAssets.com
Buy the ticket, take the ride.

Offline Agent86

  • Sr. Member
  • ****
  • Posts: 471
  • BTSX: agent86
    • View Profile
it is very easy for an attacker to max out the bandwidth, forcing other people to pay a higher transaction fee once they want to vote using the stake they received from him (trx fee is per-byte).
I think I addressed this by allowing a transaction to simply state "all prior delegate selections are void"  It doesn't need to individually specify to not vote for each delegate that was previously selected.
More importantly, storage requirement (not the blockchain, the constructed chain DB) increases to the same amount as it would be if you put the entire new vote set in each transaction.
I'm not sure I agree with this either.  The constructed database doesn't even have to specify which particular stake each vote comes from, it just needs to collect the aggregate votes for each delegate and then add or subtract from that accordingly.

A bad delegate can:
* exclude transactions
* miss blocks on purpose (delay confirmations)
* exacerbate an current fork by a block
* pay only his supporters out of his income

The last one is the only one that could complicate things. The only stable situations I can imagine are if he would always get voted out in favor of someone paying normal dividends, or if every delegate is paying only his supporters and the situation looks almost identical.

I think "approval voting" will not reward vote buying.  So I'm not worried about delegates only paying their supporters using approval voting.  Bad delegates will get voted out even if it isn't immediate and it doesn't seem like they have much to gain by misbehaving.

If all delegates only pay their own supporters the situation is not at all "almost identical."  It means that delegates can't give money to a developer or spend money on a marketing campaign that benefits everyone, because their voters just want as much of a kickback as they can get.  It's not a good situation.  If delegate positions can be bought than someone can buy over 50% of the delegates.

I would be very surprised if we don't eventually move away from the current voting proposal or get out-competed by someone else who does it right.  I'm not saying it would be an immediate disaster because there probably isn't anyone interested in creating problems.

Also from a user experience perspective it is way easier to just select the delegates you like, rather than having these trust scores and balancing which stake goes to which delegate and when to downvote etc. It's a turn off, hard to understand, and is flawed anyway.  Why try to get people used to it?

Offline toast

  • Hero Member
  • *****
  • Posts: 4001
    • View Profile
  • BitShares: nikolai
I'll ask BM to examine this more carefully, I am warming up to it a bit.

I want to clear up what we were discussing about the extra space requirements: You are right that transactions do not necessarily have to be significantly bigger as you only need to broadcast the diff. But it is very easy for an attacker to max out the bandwidth, forcing other people to pay a higher transaction fee once they want to vote using the stake they received from him (trx fee is per-byte).

More importantly, storage requirement (not the blockchain, the constructed chain DB) increases to the same amount as it would be if you put the entire new vote set in each transaction.

Quote
How much damage can a delegate that turns bad do if they aren't voted out instantly?  I feel like bytemaster has said a bad delegate can't do much damage and can't gain much but I would like clarification.

A bad delegate can:
* exclude transactions
* miss blocks on purpose (delay confirmations)
* exacerbate an current fork by a block
* pay only his supporters out of his income

The last one is the only one that could complicate things. The only stable situations I can imagine are if he would always get voted out in favor of someone paying normal dividends, or if every delegate is paying only his supporters and the situation looks almost identical.
Do not use this post as information for making any important decisions. The only agreements I ever make are informal and non-binding. Take the same precautions as when dealing with a compromised account, scammer, sockpuppet, etc.

Offline Agent86

  • Sr. Member
  • ****
  • Posts: 471
  • BTSX: agent86
    • View Profile
Yea, I guess my voting proposal is called "approval voting"
Regarding multiple-winner approval voting:

Quote
Approval voting can be extended to multiple winner elections. The naive way to do so is as block approval voting, a simple variant on block voting where each voter can select an unlimited number of candidates and the candidates with the most approval votes win. This does not provide proportional representation and is subject to the Burr dilemma, among other problems.

Other ways of extending Approval voting to multiple winner elections have been devised. Among these are proportional approval voting[48] for determining a proportional assembly, and Minimax Approval[49] for determining a consensus assembly where the least satisfied voter is satisfied the most.
So the wiki has a sentence that says it's not good for multi-winner voting (without citation).  However following their links shows that multi-winner approval voting is the preferred method of:

American Statistical Association (ASA)
Game Theory Society (GTS)
American Mathematical Society (AMS)
Mathematical Association of America (MAA)

Maybe these guys are on to something?

I think doing our homework on voting theory is well worth the time but we also need to look at how it relates to our unique application with unique attributes.  For instance, our elections are "real time" so everyone can see who everyone else is voting for and the system has a chance to come to "equilibrium."  I think this is potentially a huge advantage over systems with a single time point vote.

Ranking is not needed because ranking is used for "instant run off" elections.  You need this because if you voted for a candidate that didn't stand a chance you only find out later and wish you could have put your vote to better use.  But with "real time" voting you can look at the layout and vote accordingly.  No one has more info than anyone else.

The main complaint against approval voting seems to be that it doesn't provide "proportional representation."  For instance if 60% of population is Repubican and 40% is Democrat and they elect reps by nationwide approval voting, all the winners could be republican.  And I guess the idea is that congress should have 40% democrats if 40% of population is democrat.  Personally, I don't agree with the premise.  The point of voting is to come to a consensus and your 40% democrats aren't going to get their way when anything is voted on in congress anyway. "proportional representation" seems chaotic.  This way you can have a congress with a single digit approval rating and everyone gets voted back in because they only have to aggressively court their own constituents by doing things like sending pork barrel projects back to their districts and they don't give a rat's a$$ what the rest of the country thinks of them.  Do we need to make sure there is a rep in congress to represent the interests of the 5% of the population that are extreme racists?  Do they need proportional representation?  What other subgroup of extremists need to have their views "represented"?  It's silly IMHO. Perhaps the existence of 2 political parties in the first place is an indication of a broken system.

The other complaint I found against approval voting (for single position election) is that it could advantage a strategic voter with better info.  For example, approving of your second choice could cause your first choice to lose when they otherwise wouldn't, but if you had good polling data you would know who to support.  I think this is solved by the fact that we vote in "real time."

Anyway, approval voting seems significantly more robust to me than current implementation, easier to understand, and MUCH more useful if we hope to put money into the hands of delegates who advance the interests of the DAC in other ways.

Reaction time may be worth discussing because a lot of people will have large stakes in cold storage, not everyone is ready to voice an opinion and vote out a bad actor on the drop of a hat.  How much damage can a delegate that turns bad do if they aren't voted out instantly?  I feel like bytemaster has said a bad delegate can't do much damage and can't gain much but I would like clarification.  BM?

Sidenote suggestion:
When somebody gets assessed a 5% one year inactivity fee, their stake votes should automatically be removed from the voting algorithm because they are clearly "asleep at the wheel" assuming they haven't lost their private keys.