Closed tarakby closed 9 months ago
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 .
@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
.
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!
I went ahead and split the item tasks in this issue. The first task is now described in https://github.com/onflow/cadence/issues/2869 and I'll try to implement it myself.
@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.
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.
@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.
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.
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).
@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 )
@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
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.
Why this is breaking change? Is it Stable Cadence related?
https://github.com/onflow/cadence/issues/2712#issuecomment-1785810009
@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 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 asUInt64
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.
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)
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: https://github.com/onflow/cadence/pull/2497, https://github.com/onflow/cadence/pull/2510. The documentation changes were also made in https://github.com/onflow/docs/pull/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 - https://github.com/onflow/cadence/pull/2943
@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.
@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?
@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?
@tarakby @turbolent
The benefits are very strong:
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
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. @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
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
@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:
modulo
parameter is more expensive that not using one.
Issue to be solved
The reasons are discussed in https://github.com/onflow/flips/pull/120. This issue should be implemented after the first task described in https://github.com/onflow/cadence/issues/2869.
Suggested Solution
revertibleRandom
interface. The new function signature should befun revertibleRandom<T: FixedSizeUnsignedInteger>([modulo: T]): T
FixedSizeUnsignedInteger
is the listUInt8
,UInt16
,UInt32
,UInt64
,UInt128
,UInt256
,Word8
,Word16
,Word32
,Word64
modulo
is an optional parameter, if provided the returned valuer
satisfies0<= r < modulo
. The function panics ifmodulo == 0
- algorithm implemented should be sample rejection.Note that
fun unsafeRandom(): UInt64
should not be removed to avoid immediate breaking change. Implementation can start by merging https://github.com/onflow/cadence/pull/2706 to use the newInterface
method.