Mechanisms for adding randomness to a subnet

[tactical-retreat]

Context and scope

I'd like to spin up a subnet which can securely provide randomness. It's fine if this has to be done via a precompile.

• The subnet will have a locked down set of validators so we don't have to defend against malicious block producers.
• The randomness shouldn't be guessable, e.g. directly derived from a timestamp
• I'd prefer if the randomness can be verified, but it's not a strong requirement.

I'd appreciate any feedback on these proposed options, or guidance towards a better option.

Discussion and alternatives

Option 1: Random number in difficulty field

The first thing I thought of was to just stick a random number in the difficulty. I see this has been hardcoded to 1 in subnet-evm, and the totalDifficulty hardcoded to the block number.

It looks like I could just update DummyEngine.FinalizeAndAssemble to set a random difficulty? I don't see difficulty validated in DummyEngine.Finalize, but I'm not sure if this would subtly break anything.

This seems like an invasive change compared to a precompile, but relatively simple to maintain. Not verifiable.

Option 2: Read precommitted random numbers from a file

Seems like precompiles have access to the ChainDataDir value. I was thinking of:

• Pregenerating 1 million random numbers by sequentially hashing a random value
• Putting them into a file in reverse order (last hashed number first)
• Adding a precompile that stores a global counter of the idx of the next random number, reading it from a file, updating the idx

This is a less invasive change, and has the advantage that the randomness can be verified (by recomputing the hashes). Slightly more annoying in that we have to provision the files on every validator.

Not sure if this is an appropriate use of ChainDataDir though.

[aaronbuchwald]

Hey @tactical-retreat , thanks for creating this issue.

The long term plan is to utilize the validator set to provide a source of randomness for any VM to use, which we would then use to set the value served by the DIFFICULTY opcode.

We're not planning to add any precompiles to support randomness in the meantime, since we'd prefer not to lock ourselves in to maintaining such a solution that we would want to replace.

If you want to fork Subnet-EVM and modify it to add randomness, then..

Option 1: this seems reasonable. This puts the trust on the block producer to use a random number. If that works for your trust assumptions, then I don't see an issue with this and this sounds like a fairly lightweight and easy to maintain solution as you mentioned.

Option 2: it seems like there may be a few problems with this suggestion. afaict the suggestion here would be to pre-compute all of the values by hashing the result repeatedly, which would allow anyone to predict the whole sequence of values unless I'm misunderstanding.

[joshua-kim]

Adding a source of randomness is definitely something that we are thinking of. I'll try to post a more detailed write up on this issue shortly later this week...

[tactical-retreat]

@joshua-kim sounds good, look forward to reading it.

@aaronbuchwald re: the trust on block producer, I agree, but that's not a concern for this use case. I've already started messing around with this version. I thought it was working but I managed to bork something during testing this morning, I'll fork the repo and publish some changes / notes on what I'm trying, maybe tonight.

Re: the verifiable randomness, the idea is that you start with a seed (lets say '0' for this example, but more random in practice) and then hash that repeatedly to produce the set of random data. And then REVERSE it.

So you have:

rand[0] = hash(0)
rand[1] = hash(rand[0])
rand[2] = hash(rand[1])

Then you play back the values from the end of the array. So in practice you return rand[rand.len - 1] then rand[rand.len - 2] etc.

This prevents the values from being guessable, while still making them verifiable. If you have the series of random numbers provided by the EVM, you can just sequentially apply the hash fn from most recently provided all the way back through oldest provided to verify that the sequence is fair.

But lets put that aside. The list could be a truly random list of numbers with no connection and no verification properties.

Mechanically, is this is an abuse of ChainDataDir? I get the impression that it's intended to be used for outputs, and not inputs, but docs are sparse.

[aaronbuchwald]

Ah I see, I misunderstood. This would be fine to put in ChainDataDir. If you are going to use it, you should assign it a clear name, so that it doesn't conflict with any future usage of ChainDataDir by Subnet-EVM in the future.

imho - I'd recommend against this strategy since it seems a bit brittle. If you are ok with trusting the validator set, trusting the block producer to set the difficulty field with a random value, seems like a better solution.

[tactical-retreat]

Enabling difficulty as a random value was pretty straightforward. Let's just ignore all the stupid things I did along the way.

https://github.com/tactical-retreat/subnet-evm/commit/4d6f05a8a2889d6f657d50ee17db9cf9e93d696d

[joshua-kim]

So adding a source of randomness is definitely something that we're thinking of. Adding it natively into the protocol directly (say a VRF field in the block header) as opposed to having it built as a third-party subnet is something we are considering.

There's a few ways we can go about adding random-ness source - ideally we'd want something verifiable and not trivially gameable.

Here's a few ways of generating randomness and some thoughts on them:

1. Using the block hash - This is quite simple since hashes are random but is trivial to game. The block producer can just tamper with block contents (e.g rearranging transactions) to mine for a "good" block hash that's beneficial to it.
2. Validators pool together data to produce random-ness - This is less gameable but still results in gameability where a validator's data can be omitted to influence the outcome of the random data
3. Signatures over the previous VRF value - We could have an initial VRF value initialized at zero and have each subsequent block's VRF value be the block producer's signature over the previous block's VRF value. This can be done w/ the existing BLS signing avalanche uses. This is still somewhat gameable, but Snowman++ (ref) linearly reduces your ability to game the number since the amount of validators that are eligible to become proposers expands over time. This can still be gamed where a block producer "knows" the random value ahead of time and can choose to not produce the block.
4. There are variants of threshold-based VRF that are harder to game than (3) that I'm not familiar with so I'm going to defer this to @StephenButtolph.

(3) and (4) seem to be the most likely candidates for a native on-chain randomness source if we do decide to go for it.