Author Topic: The way to resolve "The Last Evil Delegate Problem" in DPOS  (Read 12748 times)

0 Members and 1 Guest are viewing this topic.

Offline liondani

  • Hero Member
  • *****
  • Posts: 3737
  • Inch by inch, play by play
    • View Profile
    • My detailed info
  • BitShares: liondani
  • GitHub: liondani
and it forces delegates to get their job really serious... 

Offline bytemaster

Come'on FreeTrade tell us your thoughts.  You can't go around teasing like that.  Shame shame.

Well it is a problem that I've been ruminating on for months, and I have been working on a competing/complementary/co-operating lottery DAC. So maybe you can understand why I'm not ready to put it out there just yet.
   

Yes I understand but my question would be why tell us you figured something out in the first place? :)  Although it is a good motivator...

Bytemaster -  The problem with the wager being lost if a delegate excludes is that it would never ever be acceptable for that to be a rule.  The server screws up so you lose your wager ?  One bad delegate could chase off half your user base.

The delegate would have to pay up the wager too, or that is a rule to be exploited to hurt the network.  So now if delegate has to pay up on a missing transaction, then transaction fees have to be increased to make up for this.  Maybe it could work out, no real clue.

Assuming delegates aim for 99% uptime, this would amount to a 1% chance of losing or a 1% rake. 
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 gamey

  • Hero Member
  • *****
  • Posts: 2253
    • View Profile
Come'on FreeTrade tell us your thoughts.  You can't go around teasing like that.  Shame shame.

Well it is a problem that I've been ruminating on for months, and I have been working on a competing/complementary/co-operating lottery DAC. So maybe you can understand why I'm not ready to put it out there just yet.
   

Yes I understand but my question would be why tell us you figured something out in the first place? :)  Although it is a good motivator...

Bytemaster -  The problem with the wager being lost if a delegate excludes is that it would never ever be acceptable for that to be a rule.  The server screws up so you lose your wager ?  One bad delegate could chase off half your user base.

The delegate would have to pay up the wager too, or that is a rule to be exploited to hurt the network.  So now if delegate has to pay up on a missing transaction, then transaction fees have to be increased to make up for this.  Maybe it could work out, no real clue.
I speak for myself and only myself.

Offline FreeTrade

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 700
    • View Profile
Come'on FreeTrade tell us your thoughts.  You can't go around teasing like that.  Shame shame.

Well it is a problem that I've been ruminating on for months, and I have been working on a competing/complementary/co-operating lottery DAC. So maybe you can understand why I'm not ready to put it out there just yet.
   
“People should be more sophisticated? How are you gonna get that done?” - Jerry Seinfeld reply to Bill Maher

Offline FreeTrade

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 700
    • View Profile
If the wagers are secret until the user claims them that prevents delegates from excluding winning wagers.

I like this idea - it fixes the potential issue of delegates deep-sixing other people's jackpots.
“People should be more sophisticated? How are you gonna get that done?” - Jerry Seinfeld reply to Bill Maher

Offline bytemaster

If the wagers are secret until the user claims them that prevents delegates from excluding winning wagers.
If wagers are automatically lost if the delegate fails to produce a block, that prevents a delegate from getting a second chance and doubling his odds.

With these two rules in place you can have a secure dice roll with 1 confirmation (10 seconds) unless one person controls two delegate slots.

If someone controls 2 delegate slots back-to-back then they have 10 seconds to do a proof-of-work search to find a winning ticket and submit it. 

So the question is how many delegates can be controlled by one person.  The answer should be less than 50 and could probably be less than 25.   So you are looking at a 4 minute delay to make sure that no one person can get so many delegates in a row.

However, now you have to worry about colluding delegates.  By waiting 101 blocks you can be sure that if ONE of them is honest then the result is "random".  If you only wait 25 blocks then you are trusting that 25% or more of the delegates are honest. 

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 gamey

  • Hero Member
  • *****
  • Posts: 2253
    • View Profile
Come'on FreeTrade tell us your thoughts.  You can't go around teasing like that.  Shame shame.

It is an interesting thing.  From a user's perspective you have to worry about the Delegate colluding with the network to cheat the user.  From the network's perspective you have to worry about a player colluding with a Delegate.

A delegate colluding with a player is a far bigger issue, because there is a significantly greater pay off for the cheat.  However that is not what user's are concerned over, so it is a bit of a wash from a developer's perspective.

One could keep track of  the wagers that were on the missed and unmissed blocks.  Eventually it should become apparent if someone is cheating.  Then they are removed as a Delegate and one of the trusted Delegates could come up with other delegates.  Every now and then let in a new delegate from an untrusted source.

There may be some crypto-function where all the RNG's could be signed on some multi-sig like function the previous round.  I wish I knew more about high level crypto constructs and their applicability.  If the RNG had some like way to reveal itself with a majority, then the solution might lie there. 

If you stretched the game cycle to include multiple cycles you can have player present their RNG hash with wager.  Block producer puts out their RNG on same block as RNG hash.  Player then reveals their true RNG.  If player withholds, then they lose their wager.  Real simple, what would be wrong with this ?  It turns average action turn into 25 seconds ..  Meh.  Actually thats not true as client can display results before it is accepted on blockchain.  This still allows the player to collude with DAC.  So DAC needs a majority of some set of people who control the RNG to reveal it, removing the power from one delegate's hands.
« Last Edit: August 10, 2014, 10:37:01 pm by gamey »
I speak for myself and only myself.

Offline HackFisher

  • Moderator
  • Hero Member
  • *****
  • Posts: 883
    • View Profile
Eureka!

Wow, what's that?
I think I've got it, but not sure what I want to do with it yet.

You can tell me secretly, I won't tell others.  :D
Maybe I have things to do with it.
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 liondani

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

Offline FreeTrade

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 700
    • View Profile
“People should be more sophisticated? How are you gonna get that done?” - Jerry Seinfeld reply to Bill Maher

Offline HackFisher

  • Moderator
  • Hero Member
  • *****
  • Posts: 883
    • View Profile
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 FreeTrade

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 700
    • View Profile
“People should be more sophisticated? How are you gonna get that done?” - Jerry Seinfeld reply to Bill Maher

Offline HackFisher

  • Moderator
  • Hero Member
  • *****
  • Posts: 883
    • View Profile
where can i find something about RNG DPOS? would like to think about it.

would it not possible to let 101 delegate draw the numbers and everydelagte will produce a random number betwenn 1 and 101 the average number is the delegate which numbers are used?


Here is a draft white paper:
https://docs.google.com/document/d/1KkaAnuM0a_YU2yMaeDSDiyNUv96c9TrYrCjKadC01yA/edit

We need deterministic way to reach consensus, otherwise the consensus might be broken. With DPOS, I realized that there always will be one guy who can affect the random result before the last second.

The first time I was try to resolve this, I have a idea that one block is from two source delegate:

Quote
There are two independent queue of delegates, each have 101 delegates with the same 10s interval steps.
In every delegate slot, two delegates from two source list, need to produce and broadcast two blocks (one is normal  block data like now with secret and transactions, another one block data contains only secret ).

The other normal client will receive both of these two different block and merged them into one block before inserting to the final shared chain.

After I wrote the last sentence, I found that one of the two source delegate could be bad, and choose to receive  another source broadcast block to it first, which means, competing for the last position of random chain factors, and then attack intentionally by missing blocks, this is why I have to give up this approach, and call it ""Last Delegate being Evil Problem""
« Last Edit: August 08, 2014, 03:03:06 pm by HackFisher »
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

I believe you can get it down to a CONSTANT time. 

The core problem is that if a delegate intentionally chooses to miss a block he gets to go again (doubling his chances).

I would instead make the game one of:  if no block is produced then everyone loses.   Consider this the "house edge". 

A delegate can no longer use skipping a block to double his chances.  The only thing a delegate can do is make everyones' chances to go 0.

Delegates that don't produce blocks get fired so there is no profit in them skipping a block.

There still remains the issue FreeTrade brought up:  a delegate could skip a block to harm someone else who would have won the jackpot.  If paying out the jackpot would dilute shareholders then this could in-theory be profitable to the delegate.  However this couldn't happen consistently without it really harming the market value of the network.

The solution here is to simply limit the winnings to a jackpot that doesn't dilute shareholders.
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 FreeTrade

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 700
    • View Profile
Wouldn't the jackpot just get awarded in the next block?

No, the winning draw would never be made public. No-one would be any the wiser.
“People should be more sophisticated? How are you gonna get that done?” - Jerry Seinfeld reply to Bill Maher