FVM: Randomness lookbacks and gas costs

[arajasek]

Background

The FVM today has two syscalls involving randomness: get_beacon_randomness, which fetches randomness from Drand (today), and get_chain_randomness, which fetches randomness from the blockchain itself (ticket randomness). The FVM forwards both syscalls to the client, since it does not have access to chain history; the client then walks up the chain to fetch the appropriate randomness, and returns it to the client.

The FVM today does not implement lookback limits on either call, so theoretically a call might walk back all the way to genesis.

In practice, the builtin actors themselves, which are (today) the only callers of these syscalls impose their own limits. The EVM actor, which runs user-defined code, only ever asks for randomness at the execution epoch. The other builtin-actors ask for randomness from a range of epochs, but the maximum possible lookback today is about 30 days*.

Fetching randomness today charges a fixed gas cost of 21000, regardless of how far back the randomness is.

Motivation

The situation today is a little insecure, since longer lookbacks can take longer. If the builtin-actors started querying for randomness all the way back to genesis, 21000 would definitely not cover the time taken.

More importantly, native WASM actors cannot be considered until we make a change here. We can either:

• restrict how far a lookback is allowed
• have some linear-ish scale for randomness lookbacks, similar to what we have for the tipset_cid syscall today

Proposal

After some discussion, we'd like to propose:

• NOT enforcing a lookback limit: this is no change from current behaviour, just explicitly allowing for unbounded lookbacks
• modifying the gas cost for randomness lookbacks to be linear in lookback offset.

Proposed gas changes

We'd like to assume that clients have a skiplist that allows for skipping 20 epochs at a time while walking up the chain. This is an assumption already baked into the gas for computing Tipset CIDs, and I believe is true of all 3 major Filecoin implementations. Note that this is only a floor to how performant clients can be, that we use to determine the protocol's costs. A more efficient client could easily implement constant-time lookup for all heights, and thus outperform the protocol's floor.

With the 20-length skiplist assumption, fetching randomness can require:

• Offset/20 "skips" of the skiplist
• Up to 19 tipset traversals once we've "skipped" enough
• Base costs of the extern, hashing to create the digest, etc.

Based on that, I'd like to propose that we modify the randomness syscalls to have a cost of:

X * offset / 20 + Y * 19 + Z, where X, Y, and Z will be determined from benchmarking (likely will be the same as we benchmarked when setting gas values for Tipset CID calculation).

Tipset CIDs

Although unrelated to randomness, we perform very similar work in order to calculate tipset CIDs. Today, tipset CIDs can only be requested within finality epochs. Gas costs for requesting a tipset CID are split into 2 cases:

• a special case for requesting the current tipset's CID (no lookback needed)
• a pessimistic worst-case number for requesting a tipset CID with an offset of finality, which is applied to all other tipsets

As part of this proposal, we can consider:

• Allowing for unbounded tipset CID lookbacks
• Modifying the tipset CID gas calculation to use a similar linear scale (really the very same linear scale, with minor modifications).

Note that this would only affect FEVM smart contracts ("EVM actors") today, since the other builtin-actors never request tipset CIDs (as of v11).

Alternatives

We can consider simply setting a hard lookback limit if we'd like, but it's easy enough to allow for unbounded lookbacks in reasonable costs (and likely to remain easy to do so). There are certain hypothetical use-cases for unbounded lookbacks (eg. here, which motivates this.

We can also consider setting a more aggressive performance requirement for clients (eg. constant-time lookup for all epochs). This would require some feature development in all clients, though, which in my opinion isn't worth the minor gas savings.

Feedback

Feedback requested!

Footnotes

*because the maximum ProveCommitDuration is 30 days, so the "seal" randomness can be about 30 days before when verifying ProveCommits.

[arajasek]

Tipset CIDs

As part of this proposal, we can consider:

• Allowing for unbounded tipset CID lookbacks
• Modifying the tipset CID gas calculation to use a similar linear scale (really the very same linear scale, with minor modifications).

After some quick discussion, we've decided the FIP will propose making both these changes for tipset CIDs too.