fare
commented
5 years ago Yes, there are at least two ways to do poker properly that I know of:
- Have a way for the players to detect that a card was already drawn, and require a redraw; or prove that you didn't fail to require a needed redraw.
- Have each players encrypt a shuffle with commutative homomorphic encryption. To fully decode and reveal a card on the table, both apply their shuffle. To deal a card privately to A, everyone else applies their decryption. There again, either use zkSNARKs to prove that your shuffle is correct, or reveal enough about it at the end.
In either case, some elaborate zero-knowledge proofs seem to be required to do it right. There are many variants of what is usually called "mental poker".
So we don't overconstrain the language
[ ] RPS w/ timeouts (#44) Just like the older "manual" code
[ ] RPS w/o draw (play until someone wins) (#20, #44) This program has arbitrary run-time
[ ] Poker w/o card counting (#20, #44) We don't know how to hide the player's hand without removing card counting (i.e. the same card can appear multiple times at once [i.e. there is no deck, cards are just random numbers in [0,51].])
[ ] Poker w/ card counting (#20, #44, XXX) I don't know if anyone knows how to do this. If it is possible, then it might involve an exotic kind of homomorphic encryption where the players would be able to prove that no duplicated card exists. Maybe it would be possible to have a kind of challenge process where if you used the same card twice, you lose and the other person can make you prove that you didn't do it. No idea really, just rambling.
[ ] Auction with fixed participant set, minimum bid, and "Buy It Now!" maximum This doesn't require any extensions to the language
[ ] Auction with minimum bid, win if no new bid before timeout (#20, #93, #44) This is really easy because the state is just the current bid (starts at minimum bid) and the current winner (starts as the owner). Anyone can send the message that establishes them as the current winner if they transfer more than the current bid. The previous winner gets their money back. If the timeout elapses, then the current winner gets the resource. How do you represent the resource? I think the seller commits to sharing a private key that has meaning outside of the protocol.
[ ] Single-item Vickrey auction (#97, #20, #93, #44) This is like RPS in that everyone pre-commits to their bid, then people take turns revealing their bid and proving that it is the highest, if no one claims that they are the highest bid after a certain period of time, then the last person wins. The problem with this (as described) is that the state is unbounded.
[ ] Multi-item VCG auction (#97, #20, #93, #44) This is just a more complex program where the individual messages have dynamic size because the number of items with prices are dynamic.
[ ] Lottery with fixed payout (#97, #20, #93, #44) The lottery runs until the pot is a particular size and then you pay out. Each participant contributes randomness and claims a participant id. When the pay out happens, the winner is participant with id
randomness % players. This has infinite state because you have to remember all the prior participant id claims.[ ] Lottery with fixed timeout (#97, #20, #93, #44) The lottery runs until a certain time has elapsed and then you pay out. Same system as above.
[ ] Lottery with fixed timeout & payout (#97, #20, #93, #44) Just both
[ ] Lottery with option-contract style reserve tickets (#97, #20, #93, #44) When you buy a ticket, you say what you want the pot to be when your ticket is valid. If the pot reaches that amount, then you can force a payout. If the pot isn't the amount of your reservation, then you can withdraw your money (before or after someone has forced a payout.)
[ ] Lottery variant where ticket is % of fixed pot All of the above, we assume a fixed price for a ticket. We could imagine another version where you are buying a chance of winning. If the pot is X and you transfer in Y and the fixed payout is M, then you have a Y/M% to win and win when the number is between [X, X+Y)