Technical analysis how to generate random numbers for Solidity smart contracts

0

 57 total views

Using block hash as a source of randomness can work well in many scenarios, but when it comes to great benefits, it may make the mine work bad.

Original title: ” Random Numbers and Blockchain
Written by: Markus Waas
Translation: Denglian Translation Team

When we talk about random numbers and blockchain, there are actually two issues:

  1. How to generate random numbers in smart contracts?
  2. How to generate random numbers for POS system? Or more generally, how to generate credible random numbers in a public distributed system?

Of course, these two questions also have some overlaps. Some methods used in the first question may also be used in the second question, and vice versa. But I can tell you that the best solution to these two problems may not have been found yet. In fact, these issues are really important, in the words of the famous Donald: “Random numbers should not be generated by random selection.”

Why is it so hard? Well, this is due to the nature of random numbers. One can easily create a seemingly random stream of numbers, but this stream of numbers follows a certain known logic, from enabling the attacker to predict the number.

We might naively propose that each node calculates a random number locally. Then broadcast this random number. Since each node will do the same thing, a function can be used to calculate the final random number. This function takes all the previously generated numbers as input and generates a single output random number, for example: v1 ⊕ v2 - - - ⊕ vn . However, the last node that broadcasts the local random number can wait until it receives the random number from other nodes. Then, he can generate any final random number of the distributed system by choosing a local random number R to satisfy vx = R ⊕ v1 ⊕ v2 - - ⊕ vn . Obviously, such a system for generating random numbers is flawed.

We need a better way. How to solve these problems of random numbers is worth continuing to pay attention to in detail. You can also look at predicting random numbers in Ethereum smart contracts [1]. This article is a good start for discussing the first problem (generating random numbers in smart contracts). As for the second question, there are now some interesting ideas and some seemingly crazy ideas, such as the new idea of ​​the Ethereum Foundation to build thousands of ASICs to verify VDF.

Generate random numbers for Solidity smart contracts

Now, most people know that when people try to generate random numbers in smart contracts, they face a problem. Unfortunately, there is no one-size-fits-all solution. Let me introduce the existing solutions.

Brief review of failed scenarios

Technical analysis how to generate random numbers for Solidity smart contracts

Let’s take a brief look at common solutions and why they are not good. I will not describe it in detail here, because there are already other articles that describe it very well.

Use block variables as random numbers

  • block.number : Block number.

  • block.timestamp : block timestamp.

  • block.difficulty : Block difficulty, that is, how many zeros at the end can make a new hash.

  • block.gaslimit : The gas limit of the block, that is, the maximum gas allowed for each transaction.

  • block.coinbase : The address of the miner who produced the block.

These are obviously wrong choices because they can be predicted by anyone or at least miners. Some ( block.number ) are more predictable than others ( block.difficulty ).

What if we add a private seed to the contract? You can use a passed variable and a privately stored seed as input for calculations to generate random numbers. However, this method does not take into account that it is impossible to store private data in a public network. Although Ethereum has the concept of private storage in smart contracts, anyone running an Ethereum node can still read this storage. Reading the private state or internal state can be achieved through web3.eth.getStorageAt . Therefore, this method only increases the effort of people trying to predict random numbers.

Use block hash

Technically, it is also a block variable, but it has its own parts. The block hash calculation in Ethereum is Keccak256, which is an early implementation of SHA-3. Keccak256 is a one-way function. By requiring a certain number of tail zeros and miner addresses as the salt, the hash value generated cannot be predicted by anyone. Well, this is at least a plan.

First, you have to use it correctly. That is to use the future block hash ! If you are using the current existing hash, obviously, everyone can see it. If you use the hash value of the current block, it will be empty because it has not been mined yet.

How to use future block hashes?

 mapping (address => uint256) gameWeiValues;  
    mapping (address => uint256) blockHashesToBeUsed;  

    function playGame() public {  
        if (!blockHashesToBeUsed[msg.sender]) {  
            // first run, determine block hash to be used  
            blockHashesToBeUsed[msg.sender] = block.number + 2; // use 2 or more  
            gameWeiValues[msg.sender] = msg.value;  
            return;  
        }  

        uint256 randomNumber = uint256(blockhash(blockHashesToBeUsed[msg.sender]));  

        blockHashesToBeUsed[msg.sender] = 0;  
        gameWeiValues[msg.sender] = 0;  

        if (randomNumber != 0 || randomNumber% 2 == 0) {  
            uint256 winningAmount = gameWeiValues[msg.sender] * 2;  
            msg.sender.transfer(winningAmount);  
        }  
    }  

randomNumber != 0 check is essential because Solidity can only backtrack 256 blocks. Therefore, if the player waits for more than 256 blocks, it will be forced to 0. For example, this has been used for hackers SmartBillions [2].

So, is it good to use future block hashes?

It depends on the situation! Do you allow bets with a winning amount higher than the block reward? Then pay attention to the operation of miners. If we assume that the block reward is 3 ETH, any bet over 6 ETH will actually provide miners with an incentive to cheat. Although the miner cannot freely choose the hash value of the block, he can choose not to publish the hash value of the newly discovered block to affect the random number.

Commitment model

Since 1981, the first version of the commitment model has existed. Take a look at Michael Blum’s phone flipping coins[3]. This is an interesting reading. We can simply use hashing in Solidity to achieve this. What is it like?

Let’s use the naive idea from the beginning:

Each node calculates a random number locally. It further broadcasts this random number. Since each node will do the same thing, you can use a function to calculate the final random number, which takes the previously generated number as input and produces a single output, for example, v₁⊕v₂—⊕vₙ.

Now, in the commitment mode, a node will not broadcast a random number, but first calculate the hash value of the number. This hash will be a promise of random values. Then it will broadcast the promise hash. What use is this?

The promise, as the name suggests, is that a node submits the original random value (called reveal) later, because it is impossible to find a collision (another number that produces the same hash). Therefore, in the reveal phase, a node can no longer change its secret original random value. Of course, each node starts the reveal phase only after receiving the promises of all other nodes. The procedure is like this:

  1. All participants, P1Pn , each generate a secret random value Vi .
  2. Pi calculates the promised hash value of its secret random value: Ci = H(Vi) .
  3. Each Pi sends Ci (not Vi ) first.
  4. After receiving all Ci , each Pi sends Vi . All participants can verify the received secret random value by checking Ci == H(Vi) .
  5. When all Vi are revealed and verified, the result of random number generation will be R = V1 ⊕ V2 ⊕ ... ⊕ Vn。(XOR)
  6. If a participant does not reveal his Vi , he automatically loses.

Technical analysis how to generate random numbers for Solidity smart contracts

Doesn’t sound too good to be true? You’re right. This only applies to two nodes, for example, in a casino with a bank and a single player. I have implemented a proof-of-concept prototype in Solidity and AWS Lambda.

Let’s see why this only works for two nodes.

We face the problem of the last node Pi revealing the random value, because it can use its secret value to calculate the final R earlier than others. This is the last revealer problem . The Vi it reveals may no longer affect R However, it may choose not to reveal the value, leaving all other parties with no choice but to stop random number generation. For example, in the case of two users, the unrevealed node may lose the game. However, it is not enough in the case of Eastern participation. Since multiple users participate, only one non-exposed party will suffer losses, so the attacker may do the following:

  1. Create a large number of entities and participate in betting with all entities.
  2. In the reveal phase, keep the secret random value of his last entity.
  3. Wait until every other entity reveals their random value, and then calculate the final result. If a positive result is calculated, then choose to reveal the secret value of the last entity. Otherwise, the final value will not be disclosed. The gambling must be suspended and the player will receive a refund. The attacker only lost one entity’s bet.

Multi-party participation commitment model

The modification of the multi-party environment is fairly simple, but there are some major drawbacks.

Modification: In addition to the promise, each participant also attaches collateral. After the disclosure phase, the mortgage will be refunded to each disclosure entity. If participants do not disclose their secret value, they not only lose the game, but also lose their collateral. In this case, all pledges of non-disclosed entities are divided up by all disclosed entities, or choose to be destroyed.

Impact: Unfortunately, the size of the mortgage required can be ridiculously high. Given a lottery with 10,000 participants, each ticket fee is 4 US dollars, and the participants are refunding the total amount of participants’ deposits of nearly 400 million US dollars (everyone is free to calculate).

In addition, the pledge can also be burned (return the pledge to a bank, random number service organization, charity or other third party, there is a risk of cheating by the recipient). For our lottery example, burning collateral reduces the necessary mortgage size to $39,992, which is still too high for most practical use cases.

There is a similar implementation [4], but it has not been used in practice so far. In ETH2.0, Randao will also be used as the basic random beacon, with VDF (Verifiable Delay Function) on it. We can discuss the usage in ETH2.0 in detail in a later article.

in conclusion

We have studied two methods of multi-party random numbers in Solidity. Although blockhash can work well in many scenarios if it is used properly, its performance is not satisfactory when it comes to great benefits, which will make the mine work bad. Second, the commitment mode is very useful for two-person scenarios. Unfortunately, for most real-world use cases in multiplayer situations, the commitment model is not enough. What can we do? One option may be to use an oracle, which we can discuss in a related blog post.

Reference link

[1] Predict the random number in the Ethereum smart contract:
https://blog.positive.com/predicting-random-numbers-in-ethereum-smart-contracts-e5358c6b8620

[2] Hacker SmartBillions:
https://www.reddit.com/r/ethereum/comments/74d3dc/smartbillions_lottery_contract_just_got_hacked/

[3] Flip the coin on the phone:
https://www.cs.cmu.edu/~mblum/research/pdf/coin/

[4] Similar implementation:
https://github.com/randao/randao

Source link: soliditydeveloper.com

Let’s block ads! (Why?)