- Real world lottery
- Doing a trust less lottery
- Hash Commitments
- Timed Hash Commitments
Setup offline
As always there are two parties, Alice and Bob who want to take a bet with each other over a fair coin toss. There are two parts. First Alice mentions a price and determines if Bob is interested. Bob accepts and then takes a side usually when the coin is in the air. There are a lot of assumptions to ensure fairness and there is trust that the loser will pay. The goal of this lecture is to describe a way to run an online lottery without trust.
Online lottery without trust
Thus it’s a similar setup in that there are two parties but these parties are connected along a network such as the internet. However, there are several reasons that the offline approach will not work. Because both Alice and Bob are remote, it’s more difficult for each of them to verify the fairness of the coin flip. In addition, final payment requires more setup to ensure that the loser just doesn’t walk away and not pay. Lack of trust hurts these setups.
Alice and Bob want to bet on a coin flip remotely.
The solution that the lecturer brings up is hash commitments. A hash commitment allows one to store a fixed value that is know but hidden and later reveal it without modifying this fixed value. There are specific characteristics for publishing some commitment of x. Thus inputting x essentially reveals the commitment at the end.
- Can’t find an x’ != x later such that H(x’) = H(x)
- H(x) reveals no information about x assuming the space of possible is bug.
Hash Commitment lottery – 2 Phase
Thus we now have a new example. There are three parties: Alice, Bob, and Carol and each choose a random number, nonce, respectively x, y, z. Each person must keep this random number to themselves and in round one each will publish some hash using their nonce. By the one-way uniqueness property, publishing the hash of their nonce reveals zero information about their actual nonce. Later the participants will reveal their actual nonce values. Finally, to determine the winner, a function can take in x, y, and z put it into another hash that is known or XOR can be done. This value can then be mod’d by the number of participants, 3 to find the winner. Now we can reason why this solution works.
Everyone can run through the protocol themselves. They guarantee that no one could have lied about their x, y, and z values since in round one, each person had committed the one-way hash result. Thus each person can run the hash function to ensure these values lined up. Furthermore, the final reveal part to get the mod value can also be checked. Because all these functions are known prior to the final run, a participant can choose not to submit their input because they know they’re guaranteed to loser. Thus, this schema is insufficient by itself to create this trustless lottery. Now we are introduced to a slightly better schema, timed hash commitments.
Timed Hash Commitments
As obvious, given this entire lecture are giving uses for bitcoin, use bitcoin blockchain. A timed hash commitment requires that x must be revealed by a certain timestamp. A transaction gets created in a multisig script that will pay the entire bond to one party either if the time expires or the revealed hash indicates a different behavior. Thus if Alice determine she will lose and thus does not participate, Bob can still withdraw funds. Thus the loss to Alice should equal how much she may have won with the lottery. Similarly, the same schema can be used with Alice, Bob, and Carol with each person using a Bond. Unfortunately, ti’s time complexity and bond issue may make it more difficult.