Crypto Lotteries, Entropy and RSK

Many decentralized applications require the generation of random numbers with a certain amount of entropy. This requirement occurs in simple lotteries and in complex smart-contracts that verify proofs interactively using challenge-response protocols. In this article we focus our attention on blockchain lotteries over the RSK blockchain. If your intention is to develop gambling applications on RSK or a challenge-response protocol that needs an unpredictable challenge value or if you are a smart-contract auditor, then this article is for you. Otherwise, we suggest to memorize the intended main takeaway from this article and move on: the BLOCKHASH opcode in RSK does not currently provide enough security as a seed to derive pseudo-random numbers that lotteries require.

--

BLOCKHASH and Ethereum

Since you have stayed with us, be prepared to go through some RSK internals! Let us start with some historical context. Onchain commit-reveal lotteries date back to 2012 when the SatoshiDice site was born providing: instant prizes, a relatively fair and transparent game based on a seed commit-reveal scheme, running on the Bitcoin blockchain, and sometimes consuming the majority of the Bitcoin block space. Since the commit-reveal scheme requires an operator, Ethereum naturally became popular for hosting operator-free games from launch. These games lasted until the Ethereum gas price skyrocketed, resulting in the abandonment of most games. During those times, gamblers were fascinated with betting against numbers that seemed fairly chosen. Sadly for the users, most lottery smart-contracts that attempted to get entropy from the blockchain were flawed. Unfairness sometimes resulted from unwanted vulnerabilities i.e., letting the miners manipulate the results, but most of the time contracts were specifically backdoored to let the contract owner cheat.

In an article by the author @theRaz0r, different techniques contract owners have used in Ethereum to cheat are described. In RSK, https://smartdice.bet/ (now abandoned) implemented one of these faulty techniques. The above author also proposes different solutions to solve the problem of random number generation in a blockchain. One solution discussed involves using Bitcoin block hashes instead of Ethereum block hashes, because the cost to manipulate them is higher. One way to query the hash of a Bitcoin block in Ethereum in a decentralized way is through the BTCRelay, but the BTCRelay project was halted, probably because it couldn’t establish the right incentives for users to send the new block headers and pay for the gas.

Without access to unbiased and unpredictable random numbers, many Ethereum smart-contracts invoke the BLOCKHASH opcode. If done correctly, as proven by the authors of this paper, a certain amount of entropy can be obtained from block hashes in a blockchain with Nakamoto consensus and proof-of-work. Under the cryptoeconomic model used in the paper, the following is a correct way of using block hashes: once all bets are over, the contract schedules for a future block to query the hash of the previous block, and derive the number from that hash as a seed to a pseudo-random number generator. If multiple lotteries are run in parallel, then the block hash must be hashed again together with a monotonically increasing sequence number and the lottery contract address, to derive the final pseudo-random value. This ensures that the same lottery value is not picked more than once. This Q&A page also discusses the pros and cons of using BLOCKHASH. The following is an example of the use of BLOCKHASH:

Blockhash and RSK

Existing lottery contracts in Ethereum assume that the block hash carries the proof of work, and therefore the hash cannot be fully chosen by an attacker without incurring in losses of unrealized block rewards. However, in RSK the block hash does not carry the proof of work, as the proof of work is given by the associated merge-mined Bitcoin header.

Before RSKIP92 was activated in RSK, the block hash returned by BLOCKHASH was computed as the hash of all fields in the RSK header, including the merge-mining proof. Without any source of malleability, this scheme would have been as secure as Ethereum block hash. However, the merge mining proof allowed for some degree of malleability, where it was possible for a miner to retrieve different block hashes of the same block data and merge-mined Bitcoin block. This problem was corrected when RSKIP92 was activated in 2018 as part of the Orchid network upgrade. Currently the RSK block hash leaves out the merge-mining proof, avoiding any source of malleability after the proof of work is found. The merge-mining proof instead acts as a “witness” of the proof-of-work. The following diagram shows the relation between the RSK block identification hash, the proof of work, and the bitcoin block identification hash.

The relation between the RSK block id and the Bitcoin merge-mined proof-of-work

Using BLOCKHASH to obtain crypto-economically secure entropy is possible after RSKIP92 as previously mentioned. But… do not use BLOCKHASH! While it may be a secure option in the future, the cryptoeconomic security currently obtained from it is insufficient for most use cases.

One of the main disadvantages of using BLOCKHASH is that it can only retrieve a hash from the last 256 hashes, implying that the contract must be called within 2 hours after the waiting period starts. If the contract is not called, either the contract starts over and chooses a new block height to derive the seed (and therefore becomes malleable to transaction censorship) or it must receive all the missing headers and repeatedly connect and compute the hash chain until it computes the missing RSK block hash. This process is complex, error prone and inflexible to block format changes. The waiting period can also expire if the network is congested and the transaction that triggers the retrieval of the random seed cannot make it into the blockchain on time. Two improvement proposals on Ethereum try to overcome this limitation: EIP-210 and EIP-2935. Happily, RSK already implements a precompiled contract similar to EIP-210 that enables accessing the last 4000 block hashes, therefore considerably increasing the cost of performing a censorship attack.

Using the merge-mined Bitcoin block

RSK allows smart-contracts to query the Bitcoin block header hash containing the proof-of-work of the past 4000 blocks directly. The hash obtained may or may not be a Bitcoin block present in the Bitcoin blockchain, as the RSK block difficulty is lower than Bitcoin’s. To obtain this hash, any smart-contract can call a special precompile contract called BlockHeaderContract at address 0x00…001000010. This contract, among other things, provides the method getBitcoinHeader(int256 depth) that returns the Bitcoin block header that is part of the merge-mining proof for a certain RSK block, up to a depth of 4000 blocks. In the “depth” argument, zero means the previous block. If this header is hashed twice with SHA256, the Bitcoin proof-of-work is obtained. Since only valid Bitcoin merge-mined blocks are accepted, it is not necessary for the contract to hash the header twice, and a single hash is enough to obtain a value with cryptoeconomic entropy.

Here we show an example contract that uses this technique:

The acquired random seed does not have a uniform distribution since it contains trailing zeros, but the random seed can be used to derive a number in the desired range using a PRNG.

Security of using BlockHeaderContract in RSK

As a side-chain, RSK does not mint bitcoins, and therefore no block subsidies are provided to miners. Instead, all block rewards come from transaction fees, and as of today, mining rewards provided by fees in RSK are considerably lower than the mining rewards provided by Bitcoin or Ethereum. Discarding an RSK block results in a small monetary loss to the miner, resulting in low cryptoeconomic security when using BLOCKHASH or BlockHeaderContract in RSK. On the other hand, recurrent selfish mining attacks on RSK are attributable. The merge-mining tag associated with a missing RSK block can still be observed in the Bitcoin blockchain and mining pools usually identify themselves in the Bitcoin coinbase field, but this is only a minor deterrent.

Can we do even better in RSK? Yes! We can use the RSK bridge, which is a native smart-contract that validates and stores the headers of the Bitcoin best chain.

Using the Bridge to obtain Bitcoin blocks

Bitcoin headers, which are proven to reach a Bitcoin level of difficulty, can be obtained by querying the bridge and used instead of Bitcoin merge-mined headers, which are only proven to reach the RSK difficulty (that is at most 20 times lower than Bitcoin’s) and lack enough cryptoeconomic security for high lottery prizes. There is currently one disadvantage and one impediment of using the real Bitcoin’s blocks. The disadvantage is that if a contract queries the hash of the Bitcoin’s best chain latest block, then it opens itself to manipulation by the functionaries or the users who submit the block headers to the bridge, as they could delay submissions in order to force the contract to use a previous block header instead of the latest one. Miners can also censor the submission of headers, for their own benefit. This gives miners (or the group that controls submissions) an unfair advantage. Therefore, to make this scheme secure, a query of a Bitcoin block at a certain future height must be scheduled and the Bitcoin block must be checked to have many confirmations.

Here is the smart-contract that uses this technique:

In the example code, the method startWaitForRandomSeed() must be called, and then when isRandomSeedReady() returns true, the method getRandomSeed() returns the seed. The problem is that although the bridge contract has methods to query arbitrary Bitcoin blocks, those methods are currently unavailable for direct contract calls, and can only be called off-chain. The example code will revert execution when the method getBtcBlockchainBlockHashAtDepth() is called. This limitation will be lifted in one of the coming RSK network upgrades. Until this happens, the only way to obtain a Bitcoin block hash is to provide the block hash externally to the smart-contract in the transaction calldata, and let the smart-contract verify that the hash given is part of the bridge contract internal storage, which is part of the world state. This proof requires using at least one unitrie inclusion proof that must also be given in calldata. The added complexity does not seem to pay off, so until the network upgrade occurs, using the BlockHeaderContract is the best choice.

Independent of the blockchain, when block hashes are used as random seeds miners will always have the choice to trade a block reward for an additional chance in an onchain lottery by discarding a privately mined block. As a rule of thumb, no lottery contract that allows miners to buy half of the tickets should pay a prize higher than the block reward, which in the case of Bitcoin is currently 6.25 BTC.

Other uses of random numbers in blockchains

The amount of money at stake can be increased significantly for other protocols, such as when using a block hash derived value as a challenge in a probabilistic challenge-response protocol based on a commit-reveal scheme. For example, consider a sequential protocol where a single user wants to prove to a smart-contract that each value in a committed array of 1000 values is below 10. The user commits to the root of a Merkle tree containing all the values and deposits a stake at a certain block, then thousands of Bitcoin blocks confirm the commitment and the deposit. Then a Bitcoin block hash is used to choose k challenge indices (values between 1 and 1000). At this point the user has to reveal k commitments by showing the Merkle inclusion proofs of the k commitments at the chosen indices. If he does not reveal the k correct values, his stake is slashed. In this protocol the user cannot “buy more tickets” and reach 50% chances to win. If the user wants to cheat on 50% of the committed values, the chances he wins is (2^-k). Therefore even if the cheater can almost double his chances by discarding a block, the benefit is low and the cost is high. When k is high (i.e. k=30), these protocols generally remain secure even using the RSK merge-mined Bitcoin blocks as seeds.

Summary

In RSK’s current state, obtaining cryptoeconomically secure random numbers for lotteries using proof-of-work from RSK blocks obtained by BLOCKHASH is only possible for very low stakes. After some Bridge methods are opened for onchain calls, which will happen in a coming RSK network upgrade, it will become easier and more secure to do it using the Bridge contract to query Bitcoin blocks. Furthermore, if RSK transaction fees increase considerably in the future, then using the BlockHeader contract to get the merge-mined proof-of-work will become a quicker and simpler option.

Special thanks to Sebastian Lindner for reviewing the article!

--

--

Sergio Demian Lerner
RootstockLabs: Research & Technology

Cryptocurrency Security Consultant. Head of Innovation at IOV Labs. Designer of the RSK sidechain (https://rsk.co)