Add helper functions to generate random numbers from random_seed

[shawntabrizi]

We also needs helper methods to make a reasonable secure random number from the seed. i.e. have more entropy incorporated into it like sender account, extrinsic index etc.
And bunch more helper methods to generate randoms numbers from seed and update seeds within the contract.
Because otherwise each contract within a same block will see a same seed and it can be a security issue. e.g. a contract execution can read the seed, determine if it should do something to change the state (top up account balance), to possibly effect the result of following contract execution in the same block (gambling tx will fail if account have no enough balance, but the the previous tx in the same block can top it up if it thinks it is a favorable game in this block).

Originally posted by @xlc in #53 (comment)

[burdges]

As a rule, there are no random numbers or secrets available in execute block. We'll provide sensible deterministic things that require them, like probabilistic data structures or batch signature verification. All applications mentioned here sounds like either using the collaborative randomness or else Fiat-Shamir transforms.

[shawntabrizi]

@burdges What this is proposing is something like the following:

• Retrieve the random_seed for the current block
• Get the current contract caller
• Get the current extrinsic count
• Hash them and return some u64 that users can easily use

Would you be against providing such a tool? Would you be against calling it something like random_number()

[Robbepop]

@burdges What this is proposing is something like the following:

* Retrieve the random_seed for the current block

* Get the current contract caller

* Get the current extrinsic count

* Hash them and return some u64 that users can easily use

Would you be against providing such a tool? Would you be against calling it something like random_number()

Aaaaaaaaand even more important: Do you think that it would grant enough unpredictability to not be exploited and be usable at least in some cases?

[burdges]

Short answer: No.

Almost all those sources sound useless, not sure what random_seed is. Also a u64 sounds useless.

We've three meaningful on-chain random looking quantities planned for polkadot's launch:

• the collaborative randomness produced and used in BABE is defined like hours before the current block, but that makes VRFs go because VRF keys get registered even hours before that,
• the BABE VRF output that authorizes block production is known to the block producer hours before the current block, and
• the block hash is somewhat chosen by the block producer.

I'm unsure if running the block hash through the VRF ever gives you anything you cannot get from hashing the BABE VRF output with the block hash.

If we want to batch verify signatures, then randomizing using the block hash works by a Fiat-Shamir transform because all the signing keys live inside the block and the verification equation can only be faked with negligible odds.

As an example, if r1 a + r2 b = r1 a' + r2 b' then a=a' and b=b' with high probability, provided r1 and r2 are 128 bit random numbers created by the verifyer. As r1 and r2 are 128 bit numbers, we've such high probability here that the Fiat-Shamir transform (r1,r2) = H(a,b,a',b') works too. Now there are clearly choices of b and b' which convince us that a=a' even when that's false, but actually finding one such choice requires like 2^64 attempts by the forger. If a,b,a',b' live inside the block, then (r1,r2) = H(block_hash) works too, but if I use (r1,r2) = H(a,a') then falsification is trivial.

In other words, we use low quality biasable pseudo-randomness safely because an adversaries must work astronomically hard to find bias that helps them. We'd require far stronger defenses against bias if the adversary starts with better odds.

In fact, there are no randomness sources in polkadot with sufficient quality for gambling because an adversary's odds for winning run like 50% so any bias gives them victory.

You could gamble using threshold cryptography except an adversary might silently control the threshold. You can improve this by using multiple threshold groups, ala RandHeard, but that's rather a complex protocol.

You can gamble using a commit and reveal that straddles a VDF run start, which gives a much simpler protocol. About the coolest such scheme comes from the isogenies-based VDF where everyone encrypts their bets to the VDF output.

[shawntabrizi]

@burdges Thanks for your detailed response.
I just want to clarify that this is the random_seed() I am referring to:
https://github.com/paritytech/substrate/blob/0e6a407a13fbc5a5ad200645aed72bb8a8e528d7/srml/system/src/lib.rs#L435

My understanding was it that it used some algorithm which takes data from the last 81 blocks in such a way that it would be incredibly hard to influence the outcome of the number generated, providing some csrng...

The other hash inputs would not provide anything to the "randomness" other than being used to ensure that all uses of the random_number() function within a block which produce a different number since the seed will be the same throughout the block.

It would be great to understand to what extent this random_seed() can be used, and it would be great to have documentation for that to make sure people do not use it the wrong way. (Happy to help there)

[burdges]

It appears safe_mix::TripleMix::triple_mix is a low influence boolean function that works by a hierarchy of three-way bit wise majority votes. I have not found this algorithm described in the cited paper, only general analysis of low influence boolean functions. I'll also warm the code looks fragile and ignores recent inputs if the iterator has length not a power of 3. paritytech/safe-mix#2

As I understand it, these low influence functions increase our vulnerability to attacker coalitions https://ethresear.ch/t/collective-coin-flipping-csprng/3252/21 making them less secure than the block hash for applications suited to Fiat-Shjamir like batch signature verification.

At the same time, yes random_seed() alters security for simple gambling applications, possibly improving things. In both cases, someone could defraud a gambling contract by attracting corrupt block producers in an organized way, but random_seed() reduces the final block producers influence to roughly O(log n / n), at the cost of giving the previous n block producers some similar influence.

I'd worry that last part makes this even worse than using the last block hash because you know what those older block hashes were before you gamble. I'm actually not exactly sure when low influence boolean function really provide a good solutions in general either. We're talking 81 block producers each with maybe a 7ish % chance to bias the result the way they like. Not so great.

Just fyi, you could use block hashes as randomness only when an adversary has only negligible odds if true randomness were used instead, although a security proof in the random oracle model sounds wise when it really matters.

If you can price griefing, then gambling could be don with commit and reveal: All players commit to their randomness and pay the bet plus griefing fee. All player then reveal their randomness so the game plays out with the last reveal. All players who reveal get their griefing fee back, but any player who does not reveal looses all their money. If you have more than two players then coalitions drive up the griefing fee.

[xlc]

While I am sure it is useful to have a secure random protocol as a library / core ink feature, I think it is out of scope of this issue.
This issue is more about have some helper methods, taking some entropies as input (whether it is secure or not), and produce a serials of easily consumable outputs. such as numbers between in a range.
The default implementation can feed random_seed and extrinsic_index as input and contract developers have option to feed other secure random number that generated using whatever protocol that was considered secure by the developer.

The helper methods just need to:

• easy to use
• no bias. i.e. correctly implemented uniform distribution algorithm instead of just N % (max - min) + min
• avoid reduce entropy from the input. e.g. not using an unsuitable hash function to hash the inputs

[AlistairStewart]

The low influence triplemix is useful. Either as BitwiseIteratedMajority(Last 81 block hashes) or BitwiseIteratedMajority(last 81 VRF reveals) when they are a thing. That does mean that some information about the output is leaked in the last 81 blocks. But in the block hash case, a last guy who brute forces can have much less influence in exchange..

If we use the right hash, either are uniformly distributed if all block producers are honest. We can never avoid the block producer knowing the randomness, so it is only really a tradeoff between influence and how recently we know anything about the output.

[burdges]

For what would this be used? We've ruled out gambling now, except under some toy honesty assumption.

[SkymanOne]

Closing the issue as random function has been removed from ink! core and can now be accessed via chain extension.