Hey stackers, i got something tasty for you today.
I was inspired by @aftermath's post here: https://stacker.news/items/317289
I challenged myself to construct a lottery protocol where:
  • Off-chain deposits and payouts are supported
  • Players can verify the outcome was fair
  • Players can prove to outside observers whenever the lottery coordinator cheats
  • The lottery coordinator can prove to outside observers that it selected winners honestly
  • Players remain 100% anonymous from each other; No P2P messaging needed.
  • The on-chain transaction footprint is efficient and minimized
Turns out, this is actually more than just possible, it can be generalized to work for any Discreet Log Contract .
This means any kind of oracle-based contract (e.g. sports betting, derivatives, CFDs, etc) can be conducted off-chain without any of the DLC players needing to send or receive on-chain transactions or converse P2P. Participants in a DLC can instead use one untrusted coordinator who provides the on-chain capital while everyone else transacts off-chain. I call this person the 'market maker', and they can charge fees for their capital services.

review pls?

Bear in mind i just wrote this myself and finished it today. I'm hoping I didn't make any glaring errors which would make the whole protocol impossible. Please have a read and tell me if I'm crazy. I'll also be submitting this idea to the DLC-dev mailing list to get more opinions.
Players can prove to outside observers whenever the lottery coordinator cheats
Sounds like it can equally be called "provably unfair"
Good idea! As a step towards making it trustess, you might want to check out "oblivious signing"1 which uses adaptor signatures and something called oblivious transfer to achieve a trustless off-chain coinflip and which can probably be generalized into a lottery.
I also implemented a simple demonstration/test2 of the underlying ecc math that makes oblivious signing work and which you might also find helpful.
Neat! i can see how this works for a two-player coin flip, but i'm not sure how one might generalize it for n players.
Notice how in Lloyd's coin-flip lottery, one of the Pick transactions would need to be chosen arbitrarily by Alice. Bob might be able to claim the output of the Pick TX depending on his choice of bit, and depending which Pick transaction Alice chose.
The problem with protocols that involve more than 2 agents is that everyone has to assume everyone else is colluding with each other. If you add a third player (Carol) who also receives an oblivious signature from Alice, then how can Bob be sure that Carol isn't colluding with Alice? If the two collude, then Carol can simply tell Alice which Pick transaction to publish so that Carol wins the 3-way lottery, thus taking Bob's money.
For an n-player lottery to work fairly, it has to be impossible for anybody to predict or dictate the outcome in advance, as long as at least one player is honest.
Ok, I am shooting from the hip here quickly (so what follows could very well be wrong), but let's try this:
  1. do you see how it is easy to extend a 1 of 2 oblivious transfer (oblivious signing in our case) to a 1 of n?
  2. if so, then Alice funds the output with amount U and can sell sell a ticket to each Bob for an amount slightly more than U / n (it is slightly more so that, in expectation she can earn a profit).
  3. if one of the Bob's wins they will, naturally, move/claim the utxo
  4. if more than one Bob wins, they will have a fee fight
I think for large enough n and slow enough ticket sales, these issues are surmountable, no?
The issue is that none of your Bobs can trust each other not to collude with Alice. If even one player colludes with Alice, they can steal everyone else's money by simply telling Alice which Pick transaction to publish.
I added a test demonstrating 1 of n oblivious signing. It does not quite solve the problem you point out, but it gets closer (notice how Alice can privately shuffle the messages and yet Bob still receives one and only one valid signature, while Alice still remains oblivious as to which one he receives).
Thanks for engaging on this. I hope it is helpful and we each further our own understanding of these concepts. I see what you are saying, and you very well might be correct.
Still, it feels like there is probably some way to do it with oblivious signing that would satisfy your objection.
Nice idea!
The provably fair lottery doesn't need any oracles. The Bitcoin is an oracle.
Players can prove to outside observers whenever the lottery coordinator cheats
Can you explain this in more detail? What would happen if a coordinator cheats?
It's all detailed here. Specifically:
This lottery protocol is not entirely trustless, as the market maker has the sole ability to determine which of the players receives the jackpot money. However, all the complexity described above is designed to assure players that, in the event of cheating by the market maker, they can construct an irrefutable proof that the market maker cheated. The market maker can similarly prove irrefutably that a lottery was executed honestly and fairly.
The market maker can also cheat by going offline (not awarding the jackpot at all), but I also describe how they can commit to revealing at least one winner
To prove his intent to cooperate, the market maker can commit extra collateral to the lottery, forcing himself to reveal one of the outcome secrets shortly after the settlement height h, or else forfeiting his collateral. The satoshi value of this collateral can vary, but to be a worthwhile incentive, it should be enough to put the market maker at a meaningful net loss if surrendered.