Randomness in BCH Script

Technical
#1

It has repeatedly come up in developer discussions how you would generate a random number in script, the usecase is often related to gambling or lotteries.

Deterministic Transactions

Bitcoin Cash transactions are deterministic which means the transaction will always fail/succeed with the same transaction context. This obviously means there could not be a true OP_GETRANDOMNUMBER as this would violate this core principle.

Trusted Oracle

One solution would be to have a trusted oracle provide a random number, if this oracle is credibly neutral then this could be an option, but if ‘the house’ runs the oracle then you are essentially playing a rigged game.

Provably Fair

One interesting non-contract solution has been developed and used for a long time by Satoshi Dice: its trust model is that it is provably fair with some delay. So should the service ever do payouts dishonestly/incorrectly this would be auditable by the lack of published proof or an invalid proof. This does not mean it cannot cheat, it simply means that the service is committed to transparency and has built up reputation by having a long series of provably fair bets before hand.

from the website ‘Provably Fair’ page:

In order to ensure that there is no way for the system to change the outcome of a bet, the secret keys used are decided ahead of time. They are not released right away, since they could be used to submit selective transactions and win bets unfairly. However, the hash of the secrets is released and forever recorded in the blockchain. After the secrets are release users can verify that preceeding bets were provably fair.

Each bet transaction that comes in is assigned to the secret key of the current day when it is first processed. In most cases this will be as soon as the transaction is broadcast on the bitcoin network. However it could be later if the system has some problems processing or an outage. All times are in UTC (GMT).

Hashes Are Not Random

First some things which are not random:

  • the transaction id is not random, it can be pre-computed and manipulated by changing inputs/outputs/locktimes before broadcasting
  • blockhashes are not even truly random, if your lottery grows to millions worth of USD, you need to take into consideration that miners can manipulate the block contents and hence change the resulting hash and outcome of the contract

Just generally, hashes are not random if their underlying contents are not random, and can be manipulated by someone.

Even hashes of a random number are not random when the space of numbers is too small: you can easily pre-compute all hashes of 1 byte numbers, hence the hashes are not true one-way functions anymore.

Start of a Solution

Instead of having a trusted party generate a number or using hashes which are available on the BCH blockchain, the design will be involve having at least two parties independently generate a number and committing to this hidden number without revealing it. The numbers together can then be hashed or XORed and the result will be random if atleast one of the generated numbers is random.

Now the question becomes: if a user and a betting service would enter into a contract and they would both have to commit to a hidden number, what would their incentives be to pick a random number?

Hidden Commitments Are Not Random

Importantly we need to reason in a setting with a adversarial counterparty, and have to think about the game theory of what happens when parties act dishonestly.

The fact that unknown != random is important for designing multi party randomness, for example in BCH Guru contracts players secretly commit to a prediction on the future price of a crypto asset, these hidden predictions are unknown from the perspective of player2 but they aren’t random! Players will predict in a calculated way based on the current price and the general price momentum.

Using multi-party Commitments for Randomness

The argument from a game-theory POV is that if the counterparty would give a non random number, it would be at their disadvantage for winning the bet. This is because both numbers would be used to produce the hash so if you can get any information about the counter party number, you could pick a number that will win with greater probability by pre-calculating the hashes.

@bitcoincashautist wrote

if you want to lose you pick a guessable number. if you want the game be fair to you you gen a random number and hash it and release the hash

your counterparty does the same

then when it’s time to settle you both reveal the numbers do H(a+b) and the hash determines the winner

Simultaneous Commitments

A remaining difficulty in a setting of UTXOs and transactions is how to make sure both commitments are also tied to each other and that the commitments are revealed simultaneously, or at least in a way where neither person can still opt-out easily by double spending after the reveal.

also the last party to publish their number can publish the number itself instead of hash since there is no party after them that could try to abuse this knowledge

this makes calculating the outcome easier since at least one party don’t need to reveal the number separately

So what we arrived at was similar to how BCH Guru contracts work to enable a 2 player game of hidden price predictions. For the Guru bets there are 2 smart contracts and 3 transactions for a full bet:

  1. offer is created by Player 1 with commits to his hidden number (prediction)
  2. offer is accepted by a player 2 (original uxto destroyed &hidden commitment is carried over), 2nd player does not have to hide his number (prediction)
    — player 1 reveals the number of his commitment—
  3. bet is resolved and resulting payouts happen

Note: Player 1 (the service) could withhold the number of his commitment, so there should be way where the contract is resolved without this information and the withholding party is punished. Withholding should not result in a better outcome than losing, so game theory matters for the implementation details.

The Guru contracts were open sourced some time ago, and have a similar mechanism already implemented and live on mainnet:

By extending the guru contracts for two-party commitments to combine both results, either through hashing or XORing, the end result would be random if either one of the numbers is random.

Interested to hear what other schemes exist for randomness in BCH Script!

1 Like
#2

This depends on how you approach the problem.

I have been thinking about using Blockhashes for lottery for years.

Basically, to mitigate this problem:

  • You use hashes of multiple blocks hashed together with another type of hashing algo like Whirpool or SHA512
  • You add more variables like TXID, Blocktime to the hashing input
  • You choose blockshashes that will be included in the hash deterministically, depending on the resulting hash

Ultimate equation would be something like:

LOTTERY_HASH = WHIRLPOOL(
SHA256(BLOCKHASH_N) + 
SHA256(DETERMINISTICALLY_PICK_10_BLOCKHASHES_FROM_LAST_128_BLOCKS(N-10, BLOCKHASH_N) +
BLOCKTIME(N),
LAST_TXID
)

What the function “DETERMINISTICALLY_PICK_10_BLOCKHASHES_FROM_LAST_128_BLOCKS” does, it looks at given blockhash_n, and basing on it, it picks 10 blocks out of 128 depending on the first X bits (EDIT: or all bits) of the blockhash_n after/excluding leading zeroes. Extremely hard to game.

This should be already too hard to game to even attempt it. And we can add more variables that are hard to adversarily prepare/game into the mix.

Basically, to game such a randomly generated number, a miner would have to control 100% of hashing power to have any probability of success, otherwise it’s completely impractical/impossible to achieve.

#3

PS.

The Truly Random Number generation idea is just a stub, a concept, it is not the finished idea.

I already see lots of room for improvement, maybe I will write it later.

But I think it should be enough for you guys to get the general understanding of the concept.