Topic: Proof of Bet - An alternative to everything else (Read 2506 times)
reserved. very nice indeed.
Seems like there is a problem with this proposal in that Sybil betting nodes can easily roll back a chain and create longer chains, by voluntarily violating the rule to ignore no responding winner(1) for some duration to prevent false rollbacks. There is no good way to determine whether a bettor has or has not claimed its win in time.
9. I can think of many possibilities regarding the coins bet of users that loose:
a. They are awarded to the winner.
b. Some percentage is lost and some awarded
c. They are awarded to the winner of a the block that will be mined 100 blocks later .
d. Partially or totally returned to the original owners. (This is something like Proof of Auction)
e. They are lost forever. (I like this one most)
9a and 9c would be straightforward and "winner takes all" is motivating for the participants.a. They are awarded to the winner.
b. Some percentage is lost and some awarded
c. They are awarded to the winner of a the block that will be mined 100 blocks later .
d. Partially or totally returned to the original owners. (This is something like Proof of Auction)
e. They are lost forever. (I like this one most)
Also rate of coin generation (block reward minus burnt bets) is predictable because there
are no burnt coins.
With 9e you couldn't allow more coins to be destroyed than coins generated per block, and
many users accept negative expectancy like when gambling...
I was thinking that only the winner could publish a block, by signing the data in the block with his private key.
Should we really be conflating chain building and consensus forming? Mining could be done just as it is now, but with only the fee incentive driving it. Fees are naturally driven down to the marginal cost of processing them, so this would lead to just the right amount of mining.
The consensus forming, i.e. the determination of which chain wins, is a separate issue, and can be done by separate players - in our case, the people placing bets. And that would just be done as any other transaction. The winner has an address "on file" for his loot to be sent to, so logistically this doesn't seem like a problem.
Plus I wasn't really clear on what it meant for a miner to mine a block in your proposal. Does it just mean build a valid block in the usual way but which spends the reward to his previously published address? Then anyone could submit such a block, right? Are we actually on the same page?
The consensus forming, i.e. the determination of which chain wins, is a separate issue, and can be done by separate players - in our case, the people placing bets. And that would just be done as any other transaction. The winner has an address "on file" for his loot to be sent to, so logistically this doesn't seem like a problem.
Plus I wasn't really clear on what it meant for a miner to mine a block in your proposal. Does it just mean build a valid block in the usual way but which spends the reward to his previously published address? Then anyone could submit such a block, right? Are we actually on the same page?
Leaving the distributed lottery technical issues aside for a moment,
Interestingly then, with these properties and where
w_i = size of wager i
W = sum(w_i) = pot size
B = block reward (inflation reward + fees)
P = probability of reorg
then the expected return on wager i is
E(R_i) = (B + W) * w_i / W * (1 - P)
Assuming the average expected return tends roughly to the average wager as the number of bets becomes large (efficient market hypothesis?), then
P = 1 / (1 + W / B)
i.e. the probability of a reorg can be estimated from the ratio of the total wager to the block reward in a very straightforward way. Kind of a nice feature, if the assumption is actually valid.
With a "house edge" of f, i.e. the average expected return actually tends to (1 - f) * w_ave because people are irrational gambling freaks, then this formula becomes
P = (1 + f * W / B) / (1 + W / B)
I guess this parameter would have to be estimated in practice from the actual frequency of reorgs.
It's also obvious from the first formula that it's in every habitual player's interest to minimize P going forward by cooperating.
4. If a miner includes a bet referring to a prev-hash whose block is NOT contained in the current branch, he can collect the coins for himself by including the bet.
This would provide a huge incentive to roll back the chain. With PoW you can't reclaim work done on alternative chains, so I think coins bet on alternate chains should be deemed toast (but only keep track of branches for so long).Quote
9. I can think of many possibilities regarding the coins bet of users that loose:
a. They are awarded to the winner.
b. Some percentage is lost and some awarded
c. They are awarded to the winner of a the block that will be mined 100 blocks later .
d. Partially or totally returned to the original owners. (This is something like Proof of Auction)
e. They are lost forever. (I like this one most)
If they were all granted to the winner, then it makes betting all the more attractive. The more coins put on the line, the better, right?a. They are awarded to the winner.
b. Some percentage is lost and some awarded
c. They are awarded to the winner of a the block that will be mined 100 blocks later .
d. Partially or totally returned to the original owners. (This is something like Proof of Auction)
e. They are lost forever. (I like this one most)
Interestingly then, with these properties and where
w_i = size of wager i
W = sum(w_i) = pot size
B = block reward (inflation reward + fees)
P = probability of reorg
then the expected return on wager i is
E(R_i) = (B + W) * w_i / W * (1 - P)
Assuming the average expected return tends roughly to the average wager as the number of bets becomes large (efficient market hypothesis?), then
P = 1 / (1 + W / B)
i.e. the probability of a reorg can be estimated from the ratio of the total wager to the block reward in a very straightforward way. Kind of a nice feature, if the assumption is actually valid.
With a "house edge" of f, i.e. the average expected return actually tends to (1 - f) * w_ave because people are irrational gambling freaks, then this formula becomes
P = (1 + f * W / B) / (1 + W / B)
I guess this parameter would have to be estimated in practice from the actual frequency of reorgs.
It's also obvious from the first formula that it's in every habitual player's interest to minimize P going forward by cooperating.
Another problem is how a miner can prove that no nonce lies in the interval he has been given to test.
There exists zero knowledge proof that a committed number lies on a given internal.
How could one construct a proof that there is no number with certain property in an interval ?
There exists zero knowledge proof that a committed number lies on a given internal.
How could one construct a proof that there is no number with certain property in an interval ?
Some incomplete thoughts on how to pick the winner:
Each bet i of N_i satoshis includes a secret number M_i hashed into it. Then a fair random number, M = H(M_1 || M_2 || ... || M_n) can be available later on when all n bets, totaling N satoshis, are in. Then M mod N is between N_1 + N_2 + ... + N_k and N_1 + N_2 + ... + N_(k+1) for only one k between 1 and n. This k is the winner, and his odds are exactly proportional to his wager.
There's a problem though when a player doesn't reveal their secret. I'm thinking this could be solved by having a 1-1 function on the secret numbers that's not too hard to invert, but will take enough time for all the bets to have come in. Any thoughts on what this might be? Too insecure/hard to coordinate?
It can be solved this way:
1. Suppose the n bets are N_1 to N_n and M_i are the secret numbers.
2. Let Q = H(M_1 || M_2 || ... || M_n )
3. The outcome of the bet is computed as M = H( Q || nonce) and nonce = F (Q) . F must be a 1:1 one way function, for example, the discrete logarithm (nonce = F(Q) = DLog2(Q)) . Then there will exists only one nonce value and finding this nonce will be difficult. Also showing the nonce value is sufficient to prove that M is correctly computed, so clients must not perform any work.
The network should adjust the difficulty of F so that it takes, for example, 10 minutes to evaluate, for a 1 minute block interval. Miners that try to exclude bets will have a penalty of computing time so the remaining miners will probably win (and have and advantage of 10:1 in speed). Also it's best that miners cooperate to compute the nonce instead of competing for it!! They could divide the search space between them.
We've transformed a competing system into a cooperative system!
The only problem I see is choosing the right F and dynamically adjusting the difficulty of the problem.
I like the way this one imposes an unrecoverable cost to casting a vote on a chain (not counting the auction scheme you mentioned). I think this is one of the key ingredients that makes PoW work.
What would the operation look like from a lightweight client's point of view? The winners still have to find a small enough hash of their block, correct? Is this what keeps time and prevents a flood of block submissions?
I don't like how it's guaranteed that the miner that risks the most wins though. I have a feeling an alternative should be mimicking PoW in its game dynamics. So could the bets be made more like lottery tickets? Is there any crypto-magic that can be used to randomly select a winner, with odds weighted by amount wagered?
Some incomplete thoughts on how to pick the winner:
Each bet i of N_i satoshis includes a secret number M_i hashed into it. Then a fair random number, M = H(M_1 || M_2 || ... || M_n) can be available later on when all n bets, totaling N satoshis, are in. Then M mod N is between N_1 + N_2 + ... + N_k and N_1 + N_2 + ... + N_(k+1) for only one k between 1 and n. This k is the winner, and his odds are exactly proportional to his wager.
There's a problem though when a player doesn't reveal their secret. I'm thinking this could be solved by having a 1-1 function on the secret numbers that's not too hard to invert, but will take enough time for all the bets to have come in. Any thoughts on what this might be? Too insecure/hard to coordinate?
What would the operation look like from a lightweight client's point of view? The winners still have to find a small enough hash of their block, correct? Is this what keeps time and prevents a flood of block submissions?
I don't like how it's guaranteed that the miner that risks the most wins though. I have a feeling an alternative should be mimicking PoW in its game dynamics. So could the bets be made more like lottery tickets? Is there any crypto-magic that can be used to randomly select a winner, with odds weighted by amount wagered?
Some incomplete thoughts on how to pick the winner:
Each bet i of N_i satoshis includes a secret number M_i hashed into it. Then a fair random number, M = H(M_1 || M_2 || ... || M_n) can be available later on when all n bets, totaling N satoshis, are in. Then M mod N is between N_1 + N_2 + ... + N_k and N_1 + N_2 + ... + N_(k+1) for only one k between 1 and n. This k is the winner, and his odds are exactly proportional to his wager.
There's a problem though when a player doesn't reveal their secret. I'm thinking this could be solved by having a 1-1 function on the secret numbers that's not too hard to invert, but will take enough time for all the bets to have come in. Any thoughts on what this might be? Too insecure/hard to coordinate?
Proof of Bet - An alternative to everything else.
I proposing an alternative to proof of anything, that uses bets, and that does not require an external random source.
I'll call it Proof of Bet. (PoBet)
1. The idea is that to mine a block, users send bets. Bets are either awarded or lost (burnt coins)
2. Whenever a user places a bet, the transaction where the coins are bet is linked to a particular chain block, by sotring a hash of the block. Users bet that that a certain chain block will be the finally accepted one.
Bet = normal transaction whose first output evaluates to false, and also specifies < hash(PrevBlock) , hash(user-pubkey), block-height >
Block-height is how many blocks ahead the bet is placed for. Block-height must specify a block number which is some blocks (say 50) ahead of PrevBlock.
2. The bet affects only the block specified block-height in the chain of PrevBlock.
3. If the same coins are bet twice (for different chains), then the bet is considered invalid and the following miner can be awarded the coins by including both transactions in the block. This avoids double-betting. To be considered a double-bet, the block height values present in the bet messages of the two bets must be near (e.g. 100 blocks away from each other, at most). This allows to release some bets, if an old chain is considered dead by the network.
4. If a miner includes a bet referring to a prev-hash whose block is NOT contained in the current branch, he can collect the coins for himself by including the bet.
5. The user that has achieved to higher bet is the winner and he is able to mine the following block. If he doesn't then the second one can claim the prize by mining the following block, etc. Each client application creates a table WINNERS(i) with as an ordered list (over the bet amount) of hashes of user's pubkeys. WINNERS(1) is the one with highest bet.
6. Users are encouraged (by the application code) to wait some time before accepting a block claimed by a non-first winner (and posting bets linking to it).
The minimum time to accept the winner i could be a function like
MinTimeToAcceptWinner(i) = MinTimeToAcceptWinner(i-1)+t/(k^i)
MinTimeToAcceptWinner(1) = t
7. If it's the improbable case that no award is claimed, then miner of the FIRST block of the chain is awarded the block. If he does not claim, then the second miner that appears on the chain, and so on. (Other is to start with the miners of 1000 blocks back)
8. When a block is mined by a miner that wasn't the winner, e.g. WINNERS(2), then all users will know that there is a possibility of a rollback attack by WINNER(1). In that case they will wait for more work as confirmation on the current chain to prevent that attack. The exact number of confirmation work required to prevent any attack of this kind can be dynamically computer by clients, so confirmation work will be VARIABLE and not fixed, for a certain fixed security threshold.
9. I can think of many possibilities regarding the coins bet of users that loose:
a. They are awarded to the winner.
b. Some percentage is lost and some awarded
c. They are awarded to the winner of a the block that will be mined 100 blocks later .
d. Partially or totally returned to the original owners. (This is something like Proof of Auction)
e. They are lost forever. (I like this one most)
10. Also the bet of the winning user could be awarded to the user (returned) or burn. (I have no idea which is best)
11. To compare the work of two different chains, the total number of coins burnt is used. (The amount of burnt coins depends of the rule chosen in rule 9)
12. It's difficult to roll back a chain after n blocks because some new bets have been stored in the last n blocks.
13. If you want to create an alternate chain, the best you can do is place your own bets, and be awarded the same coins you have bet. The pot is limited to your available resources. On the contrary, the remaining users create a pot that is much bigger. The ratio between pots should be similar to the ratio between owned coins.
14. If a rogue miner X tries to prevent the inclusion of bets from other miners in a mined block, the remaining miners will penalize him by betting on an alternate chain. Then the rogue miner will loose the coins bet in his evil chain, since X bets can be awarded to the "good" miners by rule 4.
15. Normal transactions could include a hash of a previous block in the current chain (e.g. the Hash( block(current-50)) ). This will tie transactions to branches and make it more difficult to grab fees from alternate chains. This also make transactions only valid for a specified time window.
16. As in Bitcoin, periodic checkpoints would help avoid a complete re-creation of the chain.
Do you see any pitfalls?
Best regards,
Sergio.
I proposing an alternative to proof of anything, that uses bets, and that does not require an external random source.
I'll call it Proof of Bet. (PoBet)
1. The idea is that to mine a block, users send bets. Bets are either awarded or lost (burnt coins)
2. Whenever a user places a bet, the transaction where the coins are bet is linked to a particular chain block, by sotring a hash of the block. Users bet that that a certain chain block will be the finally accepted one.
Bet = normal transaction whose first output evaluates to false, and also specifies < hash(PrevBlock) , hash(user-pubkey), block-height >
Block-height is how many blocks ahead the bet is placed for. Block-height must specify a block number which is some blocks (say 50) ahead of PrevBlock.
2. The bet affects only the block specified block-height in the chain of PrevBlock.
3. If the same coins are bet twice (for different chains), then the bet is considered invalid and the following miner can be awarded the coins by including both transactions in the block. This avoids double-betting. To be considered a double-bet, the block height values present in the bet messages of the two bets must be near (e.g. 100 blocks away from each other, at most). This allows to release some bets, if an old chain is considered dead by the network.
4. If a miner includes a bet referring to a prev-hash whose block is NOT contained in the current branch, he can collect the coins for himself by including the bet.
5. The user that has achieved to higher bet is the winner and he is able to mine the following block. If he doesn't then the second one can claim the prize by mining the following block, etc. Each client application creates a table WINNERS(i) with as an ordered list (over the bet amount) of hashes of user's pubkeys. WINNERS(1) is the one with highest bet.
6. Users are encouraged (by the application code) to wait some time before accepting a block claimed by a non-first winner (and posting bets linking to it).
The minimum time to accept the winner i could be a function like
MinTimeToAcceptWinner(i) = MinTimeToAcceptWinner(i-1)+t/(k^i)
MinTimeToAcceptWinner(1) = t
7. If it's the improbable case that no award is claimed, then miner of the FIRST block of the chain is awarded the block. If he does not claim, then the second miner that appears on the chain, and so on. (Other is to start with the miners of 1000 blocks back)
8. When a block is mined by a miner that wasn't the winner, e.g. WINNERS(2), then all users will know that there is a possibility of a rollback attack by WINNER(1). In that case they will wait for more work as confirmation on the current chain to prevent that attack. The exact number of confirmation work required to prevent any attack of this kind can be dynamically computer by clients, so confirmation work will be VARIABLE and not fixed, for a certain fixed security threshold.
9. I can think of many possibilities regarding the coins bet of users that loose:
a. They are awarded to the winner.
b. Some percentage is lost and some awarded
c. They are awarded to the winner of a the block that will be mined 100 blocks later .
d. Partially or totally returned to the original owners. (This is something like Proof of Auction)
e. They are lost forever. (I like this one most)
10. Also the bet of the winning user could be awarded to the user (returned) or burn. (I have no idea which is best)
11. To compare the work of two different chains, the total number of coins burnt is used. (The amount of burnt coins depends of the rule chosen in rule 9)
12. It's difficult to roll back a chain after n blocks because some new bets have been stored in the last n blocks.
13. If you want to create an alternate chain, the best you can do is place your own bets, and be awarded the same coins you have bet. The pot is limited to your available resources. On the contrary, the remaining users create a pot that is much bigger. The ratio between pots should be similar to the ratio between owned coins.
14. If a rogue miner X tries to prevent the inclusion of bets from other miners in a mined block, the remaining miners will penalize him by betting on an alternate chain. Then the rogue miner will loose the coins bet in his evil chain, since X bets can be awarded to the "good" miners by rule 4.
15. Normal transactions could include a hash of a previous block in the current chain (e.g. the Hash( block(current-50)) ). This will tie transactions to branches and make it more difficult to grab fees from alternate chains. This also make transactions only valid for a specified time window.
16. As in Bitcoin, periodic checkpoints would help avoid a complete re-creation of the chain.
Do you see any pitfalls?
Best regards,
Sergio.
Jump to: