Author [EN] [ZH] [ES] [PT] [IT] [DE] [FR] [NL] [TR] [SR] [AR] [RU] [EN] [ZH] [ES] [PT] [IT] [DE] [FR] [NL] [TR] [SR] [AR] [RU] [EN] [ZH] [ES] [PT] [IT] [DE] [FR] [NL] [TR] [SR] [AR] [RU] Topic: The way to resolve "The Last Evil Delegate Problem" in DPOS  (Read 1447 times)

0 Members and 1 Guest are viewing this topic.

Offline HackFisher

  • Moderator
  • Hero Member
  • *****
  • Posts: 883
    • View Profile
The way to resolve "The Last Evil Delegate Problem" in DPOS
« on: August 08, 2014, 02:24:07 AM »

In DPOS RNG algorithm, an evil delegate can only choose to throw away an unfavorable random result by intentionally missing block on his slot turn.

This could only be a problem, when the ticket draw interval is less than 101 blocks, because delegate can predict which block he will produce. Then he can choose to buy ticket which will draw in that block.

If the ticket draw interval is larger than 101 blocks, which means there will be at least one shuffle in that period, then the evil delegate can not predict which block he will produce. Then his only strategy is to guess or put tickets in each of the 101 blocks. If guess, his chance is 1/101, the *expect* return he can get back by attacking is the price of that ticket when he lose, because the delegate after him will continue to replace him and draw randomly. If he choose to put ticket in each blocks, his attack cost is (101 * block_ticket_sale), but what's the expected return, still the ticket sale he put in one block, he will lose.

Maybe for some games 101 blocks draw interval is too long for their requirement, and need shorter draw time, the solution is as following:

Ticket result will be drawn by 2 delegates:

The first delegate's random number is only in charge of producing a number X, which is between 1 to 3, and that X will determine the Xth block after him will draw the result random for the ticket. The 2th delegate could be the evil guy who is trying to attack, but he can not predict who will produce the right drawing block before 4 blocks, his attack cost is (3 * block_ticket_sale), but his expect return is still only 1 block_ticket_sale. The only thing game rule need is to set the draw interval 1 block before the first delegate.

Note: block_ticket_sale means all the ticket sale the evil delegate buy in one block.

 
« Last Edit: August 08, 2014, 02:42:50 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 HackFisher

  • Moderator
  • Hero Member
  • *****
  • Posts: 883
    • View Profile
Re: The way to resolve "The Last Evil Delegate Problem" in DPOS
« Reply #1 on: August 08, 2014, 03:23:53 AM »
In some sense, this have something in common with shuffle.

If the delegate can not predict the draw block, his attack cost is always larger than attack return from the perspective of probability
« Last Edit: August 08, 2014, 03:28:44 AM 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 alt

Re: The way to resolve "The Last Evil Delegate Problem" in DPOS
« Reply #2 on: August 08, 2014, 03:38:31 AM »
I prefer  change   evil to selfish
In fact, as a normal user of DAC, we believe that every delegate is selfish
we believe every delegate would choose to miss block if they can profit.
we need set rules to  punish  miss block if possible.

Offline HackFisher

  • Moderator
  • Hero Member
  • *****
  • Posts: 883
    • View Profile
Re: The way to resolve "The Last Evil Delegate Problem" in DPOS
« Reply #3 on: August 08, 2014, 05:20:03 AM »
I prefer  change   evil to selfish
In fact, as a normal user of DAC, we believe that every delegate is selfish
we believe every delegate would choose to miss block if they can profit.
we need set rules to  punish  miss block if possible.

yes, not blaming the evil, so we need to resolve it mathematically within consensus.
The ultimate of this solution can effectively reduce minimum ticket draw time from 101 blocks to 3 blocks and no one will choose to be evil intentionally.
« Last Edit: August 08, 2014, 02:43:59 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.

Online Shentist

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 1605
    • View Profile
    • metaexchange
  • BTS: shentist
Re: The way to resolve "The Last Evil Delegate Problem" in DPOS
« Reply #4 on: August 08, 2014, 05:32:24 AM »
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?

Offline alt

Re: The way to resolve "The Last Evil Delegate Problem" in DPOS
« Reply #5 on: August 08, 2014, 05:42:49 AM »
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?
the average number is not  good, the probability of each number is not equal.

Online Shentist

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 1605
    • View Profile
    • metaexchange
  • BTS: shentist
Re: The way to resolve "The Last Evil Delegate Problem" in DPOS
« Reply #6 on: August 08, 2014, 06:19:26 AM »
then 101 delegate draw a random number and the number who is most drawn will be the number?

Offline xeroc

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 12177
  • ChainSquad GmbH
    • View Profile
    • ChainSquad GmbH
  • BTS: xeroc
  • GitHub: xeroc
Re: The way to resolve "The Last Evil Delegate Problem" in DPOS
« Reply #7 on: August 08, 2014, 11:01:11 AM »
hackfish does not want to wait for 101 delegates to get his randomness .. he wants the randomness as early as 1 block .. but that cannot be truely randomnes as a selfish delegate could miss that 1 block intensionally if the random number is not in his favor .. however, wouldn't then the next block/delgate select the random number which might be trustworthy ..
this increases the luck of the selfish delegate by factor 2.

So hackfish prosposes to let the randomnes decided WHICH delegate (within the next N delegates (equally distributed) - excluding the own(selfish) delegate) should pick your random number ..

I really like that idea very much! only disadvantage is that the delay (until you finally get your random number) is NOT constant and depends on "N" (above)

+5% for that proposal hackfish!
Give BitShares a try! Use the http://testnet.bitshares.eu provided by http://bitshares.eu powered by ChainSquad GmbH

Offline FreeTrade

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 700
    • View Profile
Re: The way to resolve "The Last Evil Delegate Problem" in DPOS
« Reply #8 on: August 08, 2014, 11:17:45 AM »
Another 'evil' delegate problem you might want to consider . .

The last delegate may want to discard a result that is too favorable to someone else.

Let's say there is a large jackpot, and the delegate has a large stake in the DAC . . . maybe the penalty to him for discarding a winning jackpot result is smaller than the penalty for awarding the jackpot (money supply inflation, losing the marketing effect of the jackpot).
“People should be more sophisticated? How are you gonna get that done?” - Jerry Seinfeld reply to Bill Maher

Offline Riverhead

Re: The way to resolve "The Last Evil Delegate Problem" in DPOS
« Reply #9 on: August 08, 2014, 01:13:32 PM »
Wouldn't the jackpot just get awarded in the next block? I'm assuming the network has some way of telling if the winner received their funds. However, your point is well taken.  A bad actor delegate can mess with the system by tampering with blocks.  Perhaps some lessons can be taken from TCP/IP's guaranteed delivery/ack protocol to help with block manipulation?

Offline FreeTrade

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 700
    • View Profile
Re: The way to resolve "The Last Evil Delegate Problem" in DPOS
« Reply #10 on: August 08, 2014, 02:22:14 PM »
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

Offline bytemaster

Re: The way to resolve "The Last Evil Delegate Problem" in DPOS
« Reply #11 on: August 08, 2014, 02:50:20 PM »
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 HackFisher

  • Moderator
  • Hero Member
  • *****
  • Posts: 883
    • View Profile
Re: The way to resolve "The Last Evil Delegate Problem" in DPOS
« Reply #12 on: August 08, 2014, 02:56:59 PM »
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 FreeTrade

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 700
    • View Profile
Re: The way to resolve "The Last Evil Delegate Problem" in DPOS
« Reply #13 on: August 08, 2014, 06:37:50 PM »
Eureka!
“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.

 

Google+