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.

#4

I’ve spent considerable time thinking about this.

With an abundance of caution, I believe we can achieve numbers that are -in select use cases- an acceptable replacement for random numbers. Let’s call these pseudorandom numbers.

Truly random is not possible, as all nodes must derive at the same random number in the VM to determine the state of a transaction, and that by definition is not random.

For usecases where pseudorandom is good enough, there are options.

Step 1. Generating a “secret” hash tree.
It is possible to take any random number and sha256d hash it say 1 million times. Then, once a block or once a minute (or whatever the release schedule is), these hashes can be released in reverse order as a cashtoken (with commitment <20 bytes sha256d hash for that level><4 bytes int of level>. This means that it is trivial to check that the hash released is the one that (once hashed) matches the previously released one, and that the level/height is increased by exactly 1.

A contract that accesses the pseudorandom number needs to be designed that it requires the pseudorandom input from (let’s say) a cashtoken at pseudorandom chain height 12345.

Pros

  • Easy to implement,
  • It is not possible to change the hash that will be released, as then it won’t match the previous hash.

Cons

  • Someone knows the hashes that are released. Maybe everyone except you knows these hashes before they are released, there is no way of knowing.
  • If for whatever reason the pseudorandom number at your required height is not released, the contract needs to have a fallback scenario. This is the dilemma because withholding this number potentially changes the outcome of the script contract.

Additional steps

  • Rather than using a single source of pseudorandomness, multiple sources can be used. If these sources do not collaborate and are properly secured, the resulting number is not known to anyone in advance. This increases the risk of one of the sources of pseudorandomness not giving the required value.
  • The pseudorandomness sources can put up some sort of collateral that if no valid number is published on time, their collateral is taken.
  • A combination of “known” and “unknown” pseudorandomness sources could be combined. For unknown entities, it wouldn’t be possible to identlfy and pressure them into giving details to you.

Step 2. Introduce more pseudorandomness
For example, you can take the txid inputs, unlocking scripts, etc of ALL input transactions from all parties. Any number of random bytes can be added in the unlocking p2sh scripts.

Pros

  • This increases the amount of “randomness” that is added into the pseudorandom number – provided it is timed correctly.
  • The parties in step 1 have no control over this seed-data. This means that, even if they collaborate and know the value of their pseudorandom number beforehand, they cannot know this data and thus have no control over the final pseudorandom number.

Cons

  • Timing is important, because the ability to change the outcome of the final pseudorandom number enables negation of the previous steps. E.g. the last person to add a “random” number into the XOR function completely determines the outcome.

Step 3: Correct timing
The contracts that depend on the pseudorandom numbers need to be created (signed and mined) before the Oracle that creates the secret hash in step 1 is published.

Example
Alice and Bob set up a transaction where they will use pseudorandom oracle C and D. Let’s say at oracle C height 1234 and oracle D height 3333.

They each fund a contract that:

Requires only 2 inputs (one for Alice, one for Bob).
Alice and Bob both have encoded data into their p2sh.
Unlock script:

<key.schnorr_signature.all_outputs>
<key.public_key>
<randomdata.public_key>

Lock script:

OP_HASH160
<$(<randomdata.public_key> OP_HASH160)> OP_EQUALVERIFY
OP_DUP
OP_HASH160 <$(<key.public_key> OP_HASH160)> OP_EQUALVERIFY
OP_CHECKSIG

Takes the input at index 0 and 1 and hashes the bytecode into the output commitment, eg.

<2> OP_TXINPUTCOUNT OP_EQUALVERIFY
<0> OP_UTXOBYTECODE
<1> OP_UTXOBYTECODE
OP_CAT OP_HASH160
<0> OP_UTXOTOKENCOMMITMENT OP_EQUALVERIFY
(amongst other opcodes)

Is spendable only by a transaction that uses a specific pseudorandom oracle. Let’s say 3 inputs, 1) the tx above. 2) the oracle C, 3) the oracle D.

<1> OP_UTXOTOKENCATEGORY
<0xaabbccddee...ff> OP_EQUALVERIFY
<2> OP_UTXOTOKENCATEGORY
<0x0011223344...55> OP_EQUALVERIFY
<1> OP_UTXOTOKENCOMMITMENT
<32> OP_SPLIT
<1234> OP_EQUALVERIFY
<2> OP_UTXOTOKENCOMMITMENT
<32> OP_SPLIT
<3333> OP_EQUALVERIFY
OP_CAT
<0> OP_UTXOTOKENCATEGORY
<0x9988776655...44> OP_EQUALVERIFY
<0> OP_UTXOTOKENCOMMITMENT
OP_CAT
OP_HASH160 // the pseudorandom nr

It is important that the oracles have NOT yet published the values at the specified heights at the time the contract between Alice and Bob was created.

Headaches:

What if Alice, Oracle C and Oracle D are the same person / collude?

Then, as soon as Bob signs his funding transaction, Alice will already know the outcome of the pseudorandom number.

Solution 1:

We can include the hash of the blockchain at a specific header. I’ve played around with this (and so has bitcoincashautist) but my implementation is limited by the difficulty verification (only counts the amount of 0’s due to limitations in the script. I’m not sure how bchautist does a proper verification even with bigints as there is no exponential function in script). But, let’s say that’s solved. We can then use the value of a specific block header into the hash.

Solution 2:

Alice and Bob execute an additional step. For example, each will create a in their p2sh script, but in the first script they will use <(<randomdata> OP_HASH160 OP_HASH160)> as unlock and in the second <( OP_HASH160)>.

If Alice signs the first transaction, she still doesn’t know the random data from Bob and this cannot precalulate the pseudorandom number (even if she is the same entity as Oracle C and Oracle D).

The contract should have a penalty clause, if either party doesn’t sign within x blocks, then the full amount + a fine (part of the input) is given to the other party.

With solution 2, you can debate whether the rest of the steps are needed. That depends on the level of certainty that is needed. Not only between Alice and Bob, but also for any other third party that is interested in the results.

1 Like
#5

Have you considered just keeping the first ‘offer’ as a partially funded transaction on the company servers in order to avoid using a transaction on-chain for an offer that may never get accepted?

Then when the offer is accepted the tx is funded and broadcast. If it is not accepted the user can just “double spend” the funds making a new offer. (Its not really double spending if it never got broadcast)
The only ‘risk’ here is that your company starts accepting an offer after the time-point has passed, stealing your users funds. Seems low risk to me.