Update revertibleRandom interface (FLIP 120)

[tarakby]

Issue to be solved

The reasons are discussed in onflow/flips#120.
This issue should be implemented after the first task described in #2869.

Suggested Solution

• update revertibleRandom interface. The new function signature should be fun revertibleRandom<T: FixedSizeUnsignedInteger>([modulo: T]): T
• FixedSizeUnsignedInteger is the list UInt8, UInt16, UInt32, UInt64, UInt128, UInt256, Word8, Word16, Word32, Word64
• modulo is an optional parameter, if provided the returned value r satisfies 0<= r < modulo. The function panics if modulo == 0 - algorithm implemented should be sample rejection.
• Update the documentation

Note that fun unsafeRandom(): UInt64 should not be removed to avoid immediate breaking change.
Implementation can start by merging #2706 to use the new Interface method.

[tarakby]

FYI, I'll provide the sample rejection method to return a random less than modulo, but that can be done as the last implementation step .

[tarakby]

@turbolent would it be simpler for the Cadence team if I separate the first implementation item "add new function revertibleRandom" in a separate issue, and leave the other more complicated items for later?

The reason is that that the first item is what we need to have a safe randomness supported by Cadence. The other items are only functionality improvements.

revertibleRandom would basically be an exact copy of the current function unsafeRandom.

[AlexHentschel]

Following up on a slack conversation with Tarak here:

If I understood correctly, the modulo parameter in the final revertibleRandom is optional. Furthermore, we have a flavour of revertibleRandom generating an UInt64. Hence, one possible expression of revertibleRandom is

fun revertibleRandom(): UInt64

which is essentially the same as the current unsafeRandom. I totally support Tarak's proposal to implement fun revertibleRandom(): UInt64 first, as this would be a really impactful interim deliverable!

[tarakby]

I went ahead and split the item tasks in this issue. The first task is now described in #2869 and I'll try to implement it myself.

[turbolent]

@tarakby That's a good idea. Just adding a revertibleRandom that has the same signature as the current unsafeRandom function should be straight-forward, I think the existing unsafeRandom function already calls ReadRandom from the runtime interface.

[turbolent]

Changing the signature might be a breaking change.

Existing code working like this might not type-check anymore:

let r = revertibleRandom()  // `r` is `UInt64`

Type inference is maybe not sufficient.

[darkdrag00nv2]

@tarakby Hi, I had a small question. I can see that Cadence runtime calls ReadRandom([]byte) error to get the random bytes into a slice. IIUC, the number of bytes written into the slice is equal to the size of the byte slice, based on the below code comment in the flow-go code.

https://github.com/onflow/flow-go/blob/9c88e3183bbc8e8eb65ec0b07e281f190a2d266d/crypto/random/chacha20.go#L111-L112

So if I want to create a random UInt8, the size of the slice should be 1, and it should be 2 for UInt16 and so on. Am I correct?

PS: I'll pick this issue up.

[darkdrag00nv2]

I guess you need to create random (r) UInt64 and mod with modulus (m), then return UInt8( r % m ) Otherwise you may introduce bias.

Right, makes sense. I guess I need to create a random 256 bit integer (r) every time instead of 64 bit and then take modulo, since we also want to support UInt128, UInt256, Word128 and Word256 (The latter two are not mentioned in the FLIP but they are supported data types as well).

[bluesign]

@darkdrag00nv2 I deleted my comment after reading the description of the task, it says - algorithm implemented should be sample rejection. if you will use sample rejection my comment is not valid anymore.

Basically you will reject random, if it is >=MAX-MAX % n. So if n=100, and we want UInt8 (0-255), you will request new random when value >=200 ( hence the rejection when n=0 )

[turbolent]

@darkdrag00nv2 Thank you for picking this up!

You only need to implement the changes to the Cadence API, @tarakby is going to provide the implementation of the actual implementation (Go code) of the function

[darkdrag00nv2]

You only need to implement the changes to the Cadence API, @tarakby is going to provide the implementation of the actual implementation (Go code) of the function

@turbolent Did you mean that I can update the interface of ReadRandom([]byte) error to ReadRandom([]byte, *big.Int) error where the second parameter is the modulo and the runtime will implement the sample rejection?

Also, you were right that this would be a breaking change.

I've opened up a draft PR for this.

[bluesign]

Why this is breaking change? Is it Stable Cadence related?

[darkdrag00nv2]

#2712 (comment)

@bluesign
In the below code, we don't have a way to infer what the type parameter T is. I guess we could introduce a notion of default value of a type parameter and make the default as UInt64 but it is not yet supported in Cadence.

let r = revertibleRandom()

[bluesign]

#2712 (comment)

@bluesign In the below code, we don't have a way to infer what the type parameter T is. I guess we could introduce a notion of default value of a type parameter and make the default as UInt64 but it is not yet supported in Cadence.

let r = revertibleRandom()

Ah yeah, I was thinking we already have this as dynamic, fun revertibleRandom<T: FixedSizeUnsignedInteger>([modulo: T]): T where first T is parameter ( variable ) others are result of a function. Parameterized types confused me probably.

[tarakby]

Thank you @darkdrag00nv2 for picking up this issue!

So if I want to create a random UInt8, the size of the slice should be 1, and it should be 2 for UInt16 and so on. Am I correct?

Yes

we also want to support UInt128, UInt256, Word128 and Word256 (The latter two are not mentioned in the FLIP but they are supported data types as well).

UInt128, UInt256 are actually mentioned in FLIP120 and the description of the issue. However, I didn't include Word128 and Word256 because they were not mentioned in the Cadence doc (https://cadence-lang.org/docs/language/values-and-types).

If you confirm these 2 types are missing from the doc, then we can add them to the doc, and then to the FLIP120 and this issue.

Did you mean that I can update the interface of ReadRandom([]byte) error to ReadRandom([]byte, *big.Int) error where the second parameter is the modulo and the runtime will implement the sample rejection?

ReadRandom would remain the same. It's the interface function that provides the runtime with the randoms bytes it requires. The runtime would then adjust these bytes if needed (when a modulo is needed).

I did mention that I'll provide the implementation for the sample rejection here, but if you would like to go ahead and implement it, you can follow this implementation (https://github.com/onflow/flow-go/blob/master/crypto/random/rand.go#L75-L104) and I'll review it when ready.

The reason for not simply sampling a random and then use the modulo operation is the known modulo bias (the resulting distribution isn't uniform, it's biased towards the smaller numbers). We can avoid that either with sampling 128 extra bits and compute the modulo (bias negligible, but the mod becomes costly), or use the sample rejection (uniform distribution, algorithm returns fast)

[darkdrag00nv2]

If you confirm these 2 types are missing from the doc, then we can add them to the doc, and then to the FLIP120 and this issue.

Yes, Word128 and Word256 are definitely implemented.

PRs: #2497, #2510.
The documentation changes were also made in onflow/docs#114

@turbolent Any idea why they do not show up at https://cadence-lang.org/docs/language/values-and-types.

I did mention that I'll provide the implementation for the sample rejection here, but if you would like to go ahead and implement it, you can follow this implementation (https://github.com/onflow/flow-go/blob/master/crypto/random/rand.go#L75-L104) and I'll review it when ready.

@tarakby I'll prefer if you are able to do it. I'll update the Cadence API and will leave the modulo work as a TODO. Draft PR - #2943

[turbolent]

@darkdrag00nv2 onflow/docs#114 made changes to the upcoming docs, not the doc of the current, released version.

https://cadence-lang.org/docs/language/values-and-types also shows the current, version by default (see 0.42 in the top right). If you select 1.0, the upcoming version, the content shows up.

[turbolent]

@tarakby We'll still need the modulo implementation for the Cadence 1.0 release, do you have an estimate of when that would be ready?

[tarakby]

@turbolent It's my next task after finishing the crypto module migration (still fixing issues there). When is the Cadence 1.0 release supposed to be wrapped up?

[AlexHentschel]

@tarakby @turbolent

side comment regarding the modulo implementation

• I think Tarak's plan was to implement "rejection sampling" (in its most efficient form, which reduces the probability of having to reject samples that were generated outside of the developer-specified interval)

• The benefits are very strong:

  • notably superior runtime compared to a utilizing a mathematical modulo operation
  • no "modulo bias"

  Tarak has explained this very well in the [Cadence] FLIP - random function #120

However, there is a subtle aspect that we should decide on and potentially cover in the documentation

• rejection sampling has a non-deterministic runtime.
• In general, the average runtime is very close to the optimal runtime (suitable value generated on first attempt). Lets call the average runtime $\tau$ for some specific value of modulo . The probability of some call with this modulo parameter taking time $k\cdot\tau$ decreases exponentially with increasing k. Hence, significantly longer runtimes than the average are quite unlikely. But they are possible.
• Therefore, we have to be careful how we meter prng calls:
  • If a prng call costs a fixed amount of computation, we are good.
  • However, if we charge the transaction depending on the amount of samples that the prng draws under the hood, we need to be clear about that in the documentation. In this scenario, a developer or user has to be mindful that transactions with very tight gas limits that utilize randoms might fail very rarely due to random number generation consuming a bit more gas occasionally.

[turbolent]

@tarakby The plan is to release a release candidate by EOY. We'll need it very latest by IMHO mid/end January. You can see the full plan here: https://forum.flow.com/t/cadence-1-0-upgrade-plan/5477

If it's not tractable to add it in time, we can remove the modulo parameter and add it later

[bluesign]

If a prng call costs a fixed amount of computation, we are good

I think it should be fixed cost tbh, predictable costs are better, and there is zero chance of attack on this for resource exhaustion

[tarakby]

@turbolent I can work on it before the holidays.

@AlexHentschel Thanks for raising the metering point.
You are right that a call to revertibleRandom with a modulo parameter isn't constant-time, following the algorithm to be implemented. The probability for the algorithm to return after one try is at least 50% (exact % depends on the modulo value), and it increases fast with the number of tries as you mentioned.
However it is important to add that the alternative solution (modulo reduction) is also not constant-time. It depends on the size of the type chosen by revertibleRandom, and even within the same type, it depends on the modulo value and the "raw" random value. There are ways to make the modular reduction constant-time (for instance in applications where the modulo or final values are sensitive and we don't want timing to leak info) but that's not the case of the Go big integer package.
In general, arithmetic operations implemented simply are not constant-time, and the user isn't always responsible for choosing the inputs in runtime (for instance the raw random value, or in other cases data read from the state, blocks..).

So I think we should meter arithmetic operations with a fixed cost, and there is no need to go down the road of implementing constant-time arithmetics.

For revertibleRandom calls, we could:

• charge fixed cost for each type (cost increases with the byte size of the type used )
• using any modulo parameter is more expensive that not using one.