5

Suppose I would like to organize a honest lottery and prevent cheating when we need to find a winner. I known problem of random number in the known network arises.

I would like to try the following algorithm to prevent cheating.

The idea is to use hash of a block but the block number is not known for miners/participants and organizers to prevent cheating.

  1. On start organizer defines a random uint64 - key number to be used in the winner random number calculation. The uint number is big enough and known to organizer only on start.
  2. Organizer fixes the key number by providing hash of sum - the number plus current block hash (as a salt). The key hash is stored in the Lottery contract and available for all the participants. Then key hash is used to prevent organizers cheating and fixes the key number.
  3. Participants buy tickets and the Lottery contract stores all the participant addresses. The addresses are used on winner calculation as well.
  4. When conditions are fulfilled (e.g. all the tickets are sold or necessary amount of blocks are generated or just after some time) organizer starts winner calculations.
  5. Organizer provides the stored key number and confirms the number is exactly the same by calculating the key hash (entered on init).
  6. The key number is added to the sum of addresses and we got mod 255 of the sum to detect number of block which hash is used to detect winner. Key number + address1 + address2 ... + addressN % 255 = number of winner block (the block hash is used to get winner number)

To person who want to guess winning number it is not possible to get the number - in the contract we have just hash of the number. The number is rather big uint64 (or could be even bigger) to prevent "unhashing" the number. For organizers the number is fixed and is futile because all the tickets owners addresses must be known to calculate the winner.

Opinions? Any holes in the logic?

UPDATE: After discussing the suggested algorithm there is an improvement.

  1. When a participant buys a ticket it is allowed to pass additional has for participant key number which is also used in the winner calculation.
  2. Suppose ticket price is 100%.
  3. When participant want to provide own participant key number he pays more e.g. 300%.
  4. When the participant key number is provided during the winner detection round 210% of ticket price is returned.
  5. If the participant key number is not provided the sum is added to the lottery prize.

Thus everybody who has doubts about organizer honesty can add own random part. Not providing the key means such a person lost the deposit. Such honesty providers can have cheaper (in fact) tickets.

6
+50

The organizer can cheat the system by attempting many different addresses, which, when added to your formula Key number + address1 + address2 ... + addressN % 255 as the last address and getting the hash of the block, make this address the winner.

You can think about it this way:

  • If your system is secure, there is no way to cheat the system.
  • If there is no way to cheat the system, the organizer also cannot cheat the system.
  • If there is no way for organizer to cheat the system, then knowing the key number doesn't give you any way to cheat the system. (Otherwise the organizer would cheat the system because he knows the key number)
  • If knowing the key number doesn't give you any way to cheat the system, the system is as secure with the key number as without the key number.
  • You can get rid of the key number. The formula Key number + address1 + address2 ... + addressN % 255 is as secure as this one address1 + address2 ... + addressN % 255.
  • However, the above formula without the key number is insecure as it's subject to the same attack I described in the beginning. Right before the time when the winner is decided someone can atempt a bunch of addresses and find one that makes him the winner.
  • This means that the formula with the key number is insecure also.

As a result we came to a contradiction - we made the assumption that our system is secure in the beginning and at the end concluded that it's insecure. Thus our assumption is not correct.


What you should do instead is split the lottery into 2 phases:

  1. When buying a ticket participants must include with the transaction:

    • hash of some random number.
    • cost of the ticket.
    • some fairly large deposit.
  2. When all tickets are sold (or after some expiration) everyone who bought a ticket in the 1st phase must reveal the secret number.

    • When you reveal your secret number you get your deposit back.
    • After everyone revealed their secret number, those secret numbers together are used as source of randomness to determine the winner, e.g. concat them and hash.
    • If anyone didn't reveal their secret number (or after some expiration), the lottery is cancelled: everyone who revealed their secret numbers can withdraw the price they paid for tickets. Everyone who didn't reveal the secret number loses their deposit and the cost of ticket.
    • The deposit provides the incentive to reveal the secret number. The reason why lottery must be cancelled if anyone didn't reveal their secret number is there is a way to cheat the system by not exposing the secret number if it's favorable for the attacker.

In a similar way RANDAO is implemented. Check out the section Additional Rules and Incentives for other things you need to make sure to prevent the possibility of cheating.

In particular, the deposit size summed with the ticket price has to be not lesser than the maximum reward (normally, total amount in the lottery). Any deposit smaller than this will give an opportunity for cheating as explained by lungj here

  • It is a bit different. Sum of addresses defines number of block which hash is used to define winner. The block number is found after the last address is added. In theory when you buy last ticket you can try to cheat to point to block which makes your ticket winner. Here you are right. What if we use block hashes instead of addresses. E.g. blocknumber - 5's hash? – StanislavL Jan 6 '18 at 5:36
  • Even if you use block hashes instead of address, these blockhashes are known to organizer at the point when he wants to add the last address right? So it doesn't make it more secure. In general, the source of randomness shouldn't come from a single person or known in advance. Do you see any flaws in the system that I proposed? – medvedev1088 Jan 6 '18 at 8:02
  • 1
    @medvedev1088 yes, I can find a flaw. Multiple ways of exploiting, depending on specifics. For example, if lottery is perfectly fair (no house edge) split amongst winners, one person can buy a (possibly) large share of tickets to make it likely he/she will win. But if he or she is not going to be the winner, withholds revealing the number in one of the tickets. As long as deposit and ticket cost is less than the expected winnings, this is a net positive expected payout. Indeed, the only way to mitigate this is if each deposit is reciprocal of its fraction of jackpot (I.e., outlay=jackpot) – lungj Jan 6 '18 at 20:33
  • Of course, as I showed in that case, that particular attack is mitigated so long as participants are okay with tying up an amount equal to the jackpot. Also requires one to know jackpot total in advance. – lungj Jan 6 '18 at 20:35
  • @lungji Please explain. How come it's a positive expected payout? If any of the participants doesn't reveal the secret number the lottery is canceled, everyone can withdraw the ticket cost, except the one who didn't reveal (also loses the deposit). In every case where an attacker doesn't reveal it's a net negative. – medvedev1088 Jan 6 '18 at 22:41
0

what about something like this:

// half pseudo-code - focus on one participant

bytes32 hashedSaltFromParticipant;
string saltFromParticipant;
unit256 participationTimestamp;
uint256 highestTicket;
uint256 ticketNr;
address addressOfParticipant;
address highestParticipant;

function buyLotteryTicket(_hashedSaltFromParticipant) payable
{
    participationTimestamp = now;
    hashedSaltFromParticipant = _hashedSaltFromParticipant; 
    addressOfParticipant = msg.sender;
}

function revealMyTicket(saltFromParticipant)
{
    require(keccak256(saltFromParticipant) == hashedSaltFromParticipant);
    tempTicketNr = keccak256(addressOfParticipant + saltFromParticipant + participationTimestamp);
    ticketNr = removeAllCharactersButDigits(tempTicketNr);
    if (ticketNr > highestTicket){
        highestTicket = ticketNr;
        highestParticipant = msg.sender;
    }
}

// the winner is hold in highestParticipant at the end of the lottery
// those who failed to provide the right salt either loose their ticket or can withdraw it with a fee
// still has the open problem, of what to do if two participants have the same ticketNr
  • addressOfParticipant + saltFromParticipant + participationTimestamp the combination is known to participant. participationTimestamp could be generated by miner to have highest possible value. Also address could be generated by any participants – StanislavL Jan 10 '18 at 10:38
  • saltFromParticipant is only revealed at the end of the lottery by the participant, but he doesn't know the others, thus, predicting the result of the hash function should provide enough randomness, imho – smaco Jan 11 '18 at 12:28
  • It's exactly the way the participant can cheat choosing salt+address in such a way that combination with timestamp (also can be chosen by miner ) is max – StanislavL Jan 11 '18 at 12:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.