ACP-113: Provable Virtual Machine Randomness

[tsachiherman]

ACP: 113
Title: Provable Virtual Machine Randomness
Author(s): Tsachi Herman <http://github.com/tsachiherman>
Discussions-To: <GitHub Discussion URL (POPULATED BY MAINTAINER, DO NOT SET)>
Status: Proposed
Track: Standards
Replaces (*optional): n/a
Superseded-By (*optional): n/a

Abstract

Avalanche offers developers flexibility through subnets and EVM-compatible smart contracts. However, the platform's deterministic block execution limits the use of traditional random number generators within these contracts.

To address this, a mechanism is proposed to generate verifiable, non-cryptographic random number seeds on the Avalanche platform. This method ensures uniformity while allowing developers to build more versatile applications.

Complete design specifications : #113

[tsachiherman]

Regarding a comment made by @ARR4N:

As this value entirely predictable, I think we should surface a flag that indicates the way in which the entropy was derived: BLS-VRF / HASH. The latter SHOULD NOT (RFC2119) be considered secure.

and @StephenButtolph suggestion to pass the window index to the VM, I think that we might want to think of a way to package both.

[StephenButtolph]

If I were a VM developer, I'd actually care about the number of consecutive block proposals which used the BLS key in slot 0. But I think just telling the VM which slot is being used along mechanism for generating the value is sufficient (and provides full knowledge).

It's important to stress that the hash mechanism is just a stop-gap until all the legacy validators exit the validator set. (which will happen around march 2025) on the primary network... Most subnets will have already rotated before then.

[ARR4N]

I've thought about this some more since making that comment and think the important metric is actually the number of distinct BLS private keys that were used between committing to using some future randomness and actually using it.

If a smart contract uses the entropy to make a decision then any colluding set (including a singleton) of proposers have perfect knowledge of the outcome. However a single honest proposer in a set is sufficient to nullify the collusion (similar logic to zk-SNARK ceremonies).

[StephenButtolph]

I'm not sure that the number of distinct BLS keys is sufficient. I think that this would incentivize splitting stake over as many keys as possible.

It's a bit interesting because there is some information to be gained by knowing that the same BLS key is used... (i.e. Same BLS key implies same owner). But the inverse isn't true (ie. Different BLS key does not imply different owner).

[meaghanfitzgerald]

🔊 ACP-113 DEVELOPER COMMUNITY CALL ANNOUNCEMENT 🔊

Meeting Date/Time: 08-08-2024, 14:30 UTC
Meeting Duration: 1 hour
Moderator: Meaghan FitzGerald

Purpose of the Meeting

In this meeting, we will discuss and determine the desired first use case ACP-113, which proposes a mechanism to generate verifiable, non-cryptographic random number seeds on the Avalanche platform. The platform's deterministic block execution limits the use of traditional random number generators within these contracts. This method ensures uniformity while allowing developers to build more versatile applications.

Who is invited?

Any protocol developer, ACP author, researcher, or Avalanche community member is invited to attend this meeting.

Links

Sign Up Form: Google Form
Youtube Meeting Recording Link

Preparation Material

Mandatory

ACP-113 ReadMe
ACP-113 Discussion

Highly Recommended

Elementary understanding of the following topics would be helpful:
Digital signature schemes
Blockchains in general and the snow protocols in particular

Agenda

The call would cover the rationale and planned implementation of ACP-113 - provable virtual machine randomness. During the call, the following topics will be discussed:
Background information about the cryptographic primitives that would be used.
Recursive signing
Generation of random number from the signature
Bootstrapping and exceptions

[erwindassen]

The link above about Snowman++ link to a "Metal blockchain". What is this and what is the relation to the Avalanche network (other than they use its consensus and overall design)? Is it a friendly fork? Permissionless? Weird that we are linking to it instead of Avalanche's own docs...

[tsachiherman]

you're right. Let me update that!

[tsachiherman]

despite this known vector of attack, would you use the VM randomness generated via ACP-113 in an on-chain implementation?

One potential attack vector involves collusion among multiple proposers to manipulate the random number selection. These attackers could strategically choose to propose or abstain from proposing blocks, effectively introducing a bias into the system. By working together, they could potentially increase their chances of generating a random number favorable to their goals.

However, the effectiveness of this attack is significantly limited for the following reasons:
- Limited options: While colluding attackers expand their potential random number choices, the overall pool remains immense (2^32 possibilities). This drastically reduces their ability to target a specific value.
- Protocol's countermeasure: The protocol automatically eliminates any bias introduced by previous proposals once an honest proposer submits their block.
- Detectability: Exploitation of this attack vector is readily identifiable. A successful attack necessitates coordinated collusion among multiple nodes to synchronize their proposer slots for a specific block height ( the proposer slot order are known in advance ). Subsequent to this alignment, a designated node constructs the block proposal. The network maintains a record of the proposer slot utilized for each block. A value of zero for the proposer slot unequivocally indicates the absence of an exploit. Increasing values correlate with a heightened risk of exploitation. It is important to note that non-zero slot numbers may also arise from transient network disturbances.

While this attack is theoretically possible, its practical impact is negligible due to the vast number of potential outcomes and the protocol's inherent safeguards.

[tactical-retreat]

In the security considerations section, it talks about how the number of options is large and it might require a number of validators to collude in order to target a specific value.

But in many scenarios, the random number is actually modulo a small number, in some cases mod 2 (e.g. a coin flip simulation). If my understanding is correct, a validator could wait for their turn to propose a block, and then either include or exclude a specific tx with a 50% chance based on the value that their block's seed would resolve to.

Is my understanding correct? If so, I think that the practical impact of the security risks here need a bit more consideration.

I wouldn't be willing to use this directly (in a single tx) to resolve randomness if money was involved, but I think in a callback situation (e.g. user commits at block N and then server submits tx at block N+(1 to 3) similar to how Chainlink operates), that would reintroduce difficulty coordinating to attackers without actually requiring / paying fees for Chainlink.

For the C-Chain anyway. I think for Avalanche L1s with a permission-ed validator set this is a clear win, especially compared to the option discussed here (stuffing a random number into the difficulty slot).

How would the VRF values be exposed to users, I assume a new precompile? It's not mentioned in ACP-113.

[tsachiherman]

I think that your analysis here is correct. The randomness delay ( N+m ) would partially solve it.

In order to really solve this problem, we would need to "remove" the ability of the block proposer to decide which transaction would appear in a block. That can be achieved by posting the intent of executing a transaction at block N, with a target of block height N+m. Then, have m votes ( one on each block height ) that confirm/deny that transaction.

If that transaction received enough votes, the transaction would be executed in block N+m.
This would unfortunately introduce an execution delay, but it might be acceptable for financial transactions.

As for your last question, How would the VRF values be exposed to users, I assume a new precompile?, yes, I expect it would be a precompile.

[tactical-retreat]

LGTM, seems like something I'd prefer using over my home-rolled 2-tx non-verifiable randomness and also over the difficulty field randomness hack.