[AIP-41][Discussion] Move APIs for public randomness generation

[alinush]

Note: The current v1.2 version of AIP-41 is here.

Short summary

This AIP proposes a new Move module called aptos_std::randomness which enables smart contracts to easily and securely generate publicly-verifiable randomness.

The proposed randomness module leverages an underlying on-chain cryptographic randomness implementation run by the Aptos validators. This implementation, however, is outside the scope of this AIP and will be the focus of a different, future AIP.

The only thing this AIP does assume of the on-chain randomness is that it is unbiasable and unpredictable, even by a malicious minority of the validators (as weighed by stake).

Proposed API (last updated August 11th, 2023)

module aptos_std::randomness {
    use std::vector;

    /// Generates `n` bytes uniformly at random.
    public fun bytes(n: u64): vector<u8> { /* ... */ }

    /// Generates a number uniformly at random.
    public fun u64_integer(): u64 { /* ... */ }
    public fun u256_integer(): u256 { /* ... */ }

    /// Generates a number $n \in [min_incl, max_excl)$ uniformly at random.
    public fun u64_range(min_incl: u64, max_excl: u64): u64 { /* ... */ }
    public fun u256_range(min_incl: u256, max_excl: u256): u256 { /* ... */ }

    /* Similar methods for u8, u16, u32, u64, and u128. */

    /// Generate a permutation of `[0, 1, ..., n-1]` uniformly at random.
    public fun permutation(n: u64): vector<u64> { /* ... */ }

    #[test_only]
    /// Test-only function to set the entropy in the RNG to a specific value, which is useful for
    /// testing.
    public fun set_seed(seed: vector<u8>) { /* ... */ }

    //
    // More functions can be added here to support other randomness generations operations
    //
}

[JacobADevore]

Hey @alinush, would love to connect and help give insights here.

[alinush]

Hey @JacobADevore, great, thank you!

Would you mind sharing your thoughts here, in order to start a public discussion that encourages others to participate as well?

[JacobADevore]

Sounds good @alinush! I wanted to inquire about the exact specifics of the AIP. Currently, the spec declares functions that pass in parameters such as a seed. It would be great if you could specifically say where the randomness is derived from and give some more details. The current implementation states it uses 1.) Calling contract 2.) Seed; both are predictable which in turn wouldn't generate randomness. Maybe I am missing something, but some more context would be great.

[alilloig]

@JacobADevore according to the AIP document...

This AIP is strictly about the proposed API, and not its implementation.

So this is mostly just about the methods the module will expose, rather than about how the random generation will be done:

/// Generates different randomness based on the given seed and the calling contract's address.
public fun generate<T>(seed: &T): Randomness { /* ... */ }

/// Amplifies the generated randomness object into multiple objects.
public fun amplify(r: Randomness, n: u64): vector<Randomness> { /* ... */ }

/// Consumes a `Randomness` object so as to securely generate a random integer $n \in [min_incl, max_excl)$
public fun number(r: Randomness, min_incl: u64, max_excl: u64): u64 { /* ... */ }

/// Consumes a `Randomness` object so as to securely pick a random element from a vector.
public fun pick<T>(r: Randomness, vec: &vector<T>): &T { /* ... */ }

cheers!

[alinush]

Really appreciate you folks taking a close look at this!

Indeed, as you can see, the current AIP status is Draft, which means I still need to finish writing it & explain things a little bit better 😋 ...

But @alilloig is right: this AIP assumes an underlying on-chain randomness implementation (e.g., the validators run some randomness beacon protocol; pick your favorite!) and focuses on what the exposed API to Move developers should look like.

In that sense, the generate() function takes a seed so as to allow developers to generate multiple Randomness objects for different purposes (e.g., by carefully hashing the on-chain randomness with the BCS serialization of the seed).

However, as I type this, I wonder whether we should get rid of this seed argument and simply rely on calls to amplify to generate more pieces of Randomness.

[alilloig]

@alinush you are probably right, as a smart contract developer I don't really care from what seed my random numbers come from, just care about having access to them in the simplest possible way

[alinush]

Indeed. And using external randomness, as we explored in this drand-based lottery example, is quite awkward to (1) implement by developers, (2) use by users, since someone has to post the external randomness, and (3) to audit by external entities due to subtle timing assumptions.

[JacobADevore]

Understood, I appreciate you clearing that up for me.

What do you think of exchanging seeds for amount allowing a user to essentially call random(X) and get back a vector of X elements of randomness? (upper and lower bound for generation) Something like this would be great for DX (developer experience). To achieve X elements of randomness you could use a nonce starting at zero and incrementing for each randomness generated. With a nonce implementation, you might want to use an avalanche effect hashing algorithm though.

Just a few thoughts. I would love to hear what you guys think.

[alinush]

That's an interesting idea!

Would you still keep amplify? If so, could there be confusion on which API to use to generate multiple pieces of Randomness: i.e., one call to generate(n) vs. one call to generate(1) followed by an amplify(n).

Either way, I like the idea of removing the seed and relying on amplifying the randomness as the unique way of generating multiple pieces of randomness.

Another possible simplification could be the use of a RandomnessStream object that you can call next() on, rather than the amplify(n)-based design which requires fixing n as an input.

[alinush]

I've actually just updated the AIP. You can find it here. It should now be fully-contained.

I'm curious about the open question O1 there, on how to deal with repeated calls to generate across the same TXN (whether seeded, unseeded or with an n parameter like you suggested).

[JacobADevore]

Very well written AIP @alinush!

Thoughts on removing seed under the generate() function and allocating the generating function for a single generation of randomness? For multiple forms of randomness, we could use a function called something like generateMultiple(amount) (this would remove the need for amplify).

Think this would be a better DX than having to pass in an empty vector for generating randomness. Removing a Randomness object to be passed into the function generating multiple randomnesses seems like a better DX as well.

Updated: Q1: Ideally I think C would be the best outcome where users can call generate() as many times as needed in the same TXN. If in the implementation this becomes problematic I would say revert back to b to ensure correct usage.

[alinush]

Thank you @JacobADevore and glad you found it well-written! (I tried!)

Regarding option (c), you would have different calls to generate made in the same TXN return different random results, correct? i.e., it's as if each call to generate is just a call to RandomnessStream::next() for the RandomnessStream object created for that TXN.

That option is interesting to ponder as it would be the simplest.

I wonder if developers would be surprised by that kind of non-deterministic behavior within a single TXN's execution and/or if it creates any security issues.

[JacobADevore]

I wouldn't be opposed to either or, I would say allowing the user to generate within a loop is valuable from a DX perspective but I do see the risks from a security perspective. Maybe we can get some more insights from the Aptos team with this specific question at hand.

[alinush]

When you say "generate within a loop", do you assume the option(c) generate design which returns different results every time?

[JacobADevore]

Correct

[banool]

As hinted above, the proposed randomness module would be part of the standard Aptos Move framework, under the aptos_std namespace.

Out of curiosity, why aptos_std vs aptos_framework? I actually don't know how we determine which thing goes where but I notice other consensus-determined value retrieval modules (e.g. timestamp) are in aptos_framework.

I think the API to the module looks great, I have almost no changes to suggest. I assume it is omitted on purpose for brevity, but explanations of things like "amplification" would be helpful.

While I was reading something that came to mind is it'd be nice if there was a variant of generate that didn't require the user to pass in a seed. Then bingo there it is, question 1. I think option B or C are both good options. I think option A is too risky. Even if we include comments, there is a decent chance that people will not read them and use it without realizing that the randomness is not different each time. Indeed if you didn't call this out, I would not have realized this. Option C is likely how users would want it to work. I think the RandomnessStream you mention above is also a decent idea, but Option C is really just a simpler (albeit perhaps less obvious) version of that.

In the developer platform section you mention how we could make the randomness publicly verifiable. This could provide a nice easy API for verification. Have we considered view functions that might help with this? It seems like some key functions could be view functions, like generate. Rather than having to do it off chain and extract all that extra data (block number, txn hash, etc) you could just call a view function (on your own node if you're paranoid) at a specific ledger version.

[MoonShiesty]

number and pick are trivial functions and should be inline

what is the motivation behind making Randomness non-copyable? I can imagine cases where modules might want to reuse the same source of randomness for multiple operations.

[alinush]

Thank you @banool and @MoonShiesty!

@MoonShiesty, the motivation was to prevent developers from accidentally generating identical randomness for two different events. Note that reusing the randomness is still possible but must be made explicit: i.e., once the Randomness object has been consumed into, say, an integer, that integer can be explicitly copied.

However, I think this this Randomness-object-based API is not too great.

So I've just pushed a PR to move away from it and more towards a Rust-like RNG API.

Until it merges, you can see the new API here.

[alinush]

@banool regarding why aptos_std, good question! It could live in aptos_framework too, I suppose. I'll keep track of that as an open question.

[banool]

What is the purpose of the generic type param on the rng method?

public fun rng<T>(): RandomNumberGenerator

[alinush]

What is the purpose of the generic type param on the rng method?

public fun rng<T>(): RandomNumberGenerator

Ugh. That... is a typo! Thank you. Fixing here.

[alinush]

Updated the AIP: Added a test-only function to set the seed (entropy) of the RNG during testing, which should be useful for reproducing bugs:

    /// Test-only function to set the entropy in the RNG to a specific value, which is useful for
    /// testing.
    #[test_only]
    public fun set_seed(seed: vector<u8>);

[zjma]

    /// Returns an RNG for the current TXN and calling Move module. Repeated calls to this function 
    /// ...
    public fun rng(): RandomNumberGenerator { /* ... */ }

why does calling module matter? Could TXN be enough?

[junkil-park]

What is the purpose of exposing RandomNumberGenerator to users? What could go wrong if we hide it like:

fun rng(): RandomNumberGenerator { /* ... */ } // became private
/// Generates a number uniformly at random.
public fun u64(): u64 { let r = rng(); /* ... */ } // the RNG parameter is removed, but retrieved inside of the function

[alinush]

    /// Returns an RNG for the current TXN and calling Move module. Repeated calls to this function 
    /// ...
    public fun rng(): RandomNumberGenerator { /* ... */ }

why does calling module matter? Could TXN be enough?

I don't think it does. I think what's more important is that each time an RNG is created via a call to rng() that the RNG be uniquely-seeded. This could be done by taking into context the calling module & the TXN hash. But in that sense, I think you are right: the TXN hash, which should be unique, should be enough.

I was a bit worried that TXN hashes might not actually be unique due to a scare I once had with Bitcoin TXNs, where coinbase TXNs could actually have the same hash. So it might be worth mitigating against such (current or future) surprises in our design.

[alinush]

What is the purpose of exposing RandomNumberGenerator to users? What could go wrong if we hide it like:

fun rng(): RandomNumberGenerator { /* ... */ } // became private
/// Generates a number uniformly at random.
public fun u64(): u64 { let r = rng(); /* ... */ } // the RNG parameter is removed, but retrieved inside of the function

I think you're right: I don't see anything wrong with that approach either.

It seems to lead to an even easier-to-use randomness module.

[zjma]

    /// Returns an RNG for the current TXN and calling Move module. Repeated calls to this function 
    /// ...
    public fun rng(): RandomNumberGenerator { /* ... */ }

why does calling module matter? Could TXN be enough?

I don't think it does. I think what's more important is that each time an RNG is created via a call to rng() that the RNG be uniquely-seeded. This could be done by taking into context the calling module & the TXN hash. But in that sense, I think you are right: the TXN hash, which should be unique, should be enough.

I was a bit worried that TXN hashes might not actually be unique due to a scare I once had with Bitcoin TXNs, where coinbase TXNs could actually have the same hash. So it might be worth mitigating against such (current or future) surprises in our design.

i was thinking that it's possible to mix in (block-id, in-block-txn-position) to ensure uniqueness?

[alinush]

PSA: AIP-41 has recently been updated to v1.2. The major changes are further simplifications to the API and countermeasures against so-called "test-and-abort" attacks.

See changelog here.

[zjma]

In the lottery example, it's mentioned that any one can submit the txn to pay some gas and reveal the winner. But are they incentivized to do so?

Somehow Drand-based lottery can be designed to avoid this problem: the winner knows they are the winner, and are incentivized to claim the reward.

[alinush]

In the lottery example, it's mentioned that any one can submit the txn to pay some gas and reveal the winner. But are they incentivized to do so?

Somehow Drand-based lottery can be designed to avoid this problem: the winner knows they are the winner, and are incentivized to claim the reward.

That's a good point. The caller of decide_winners is not incentivized. But this is only the simplest example I could come up with.

I guess we can change the code to send a small chunk of the winnings to the caller of decide_winners? So as to (1) pay for their TXN fees and (2) incentivize players to submit it?

(For this, we'd have to pass in a signer as an arg to decide_winners and decide_winners_internal, which is doable.)

[zjma]

In the lottery example, it's mentioned that any one can submit the txn to pay some gas and reveal the winner. But are they incentivized to do so? Somehow Drand-based lottery can be designed to avoid this problem: the winner knows they are the winner, and are incentivized to claim the reward.

That's a good point. The caller of decide_winners is not incentivized. But this is only the simplest example I could come up with.

I guess we can change the code to send a small chunk of the winnings to the caller of decide_winners? So as to (1) pay for their TXN fees and (2) incentivize players to submit it?

(For this, we'd have to pass in a signer as an arg to decide_winners and decide_winners_internal, which is doable.)

I agree that DApp developers can fill the gap in their app-specific way.

I guess I'm more wondering how many dapps may benefit from drand style more than on-chain style. Also how many existing things need to be changed. One thing I can think of is that Petra wallet will no longer be able to show the balance diff preview before user click "sign".

[zjma]

I wonder if both style can be provided.

• an on-chain move API
• outside move, a piece of random bytes published for every block (basically drand without time synchronization problem)

They can come from the same source.

[alinush]

I think it would be nice to have an API standard for verifying off-chain secure randomness & it would have the advantages you mention. However, due to the plethora of off-chain randomness beacons (e.g., drand, SupraOracles, Chainlink, etc) that is probably best done as a separate effort in its own AIP.

[chrisyy2003]

I would like to ask the on-chain cryptographic randomness implementation run by the Aptos validators is it already implemented?

[alinush]

Nope, not yet!