Define a sane "max randomness" lookback limit

[Stebalien]

The builtin actors currently enforce their own limits, but we need to set a global one.

[Stebalien]

Alternatively, we can just charge proportional to the lookback distance.

[Stebalien]

cc @anorth who has thought about this in the past.

[anorth]

I do think there should be a fixed limit, and whatever's required for our current sector onboarding seems like a reasonable guide to start.

[raulk]

Would err on the side of conservativeness, so what @anorth proposed makes sense. We can always expand later, can never constrict.

[Stebalien]

So, the question is: What is required. @ZenGround0 any ideas?

[Stebalien]

I'm punting this to M2.2. We've disabled the related precompile, so this is no longer a critical issue.

[ZenGround0]

One weird but useful benefit to arbitrary or at least longer term lookback is the ability to rerun previous PoReps without trust. There are situations where this might be useful. But If we actually wanted to support this we'd probably want to use an accumulator and have the syscall take a proof. We could do that fairly easily in an upgrade too.

As @anorth says above the easiest safe thing to do is restrict on current PoRep lookback limts.

[Stebalien]

After thinking about this a bit... I think we really can just allow arbitrary lookbacks without too much difficulty, what we need is:

1. A quick lookup table for some subset of epochs before finality. I.e., some way to skip to within N epochs of the target epoch so we only have to walk N epochs.
2. A gas schedule that charges less for "recent" epochs (guaranteed to be cached).

This may also be important with respect to things like time-lock encryption.

[Kubuxu]

This may also be important with respect to things like time-lock encryption.

For drand timelock, the drand randomness is self-certifying by BLS signature verification.

Arbitrary ticket randomness lookup would require the whole chain of block headers (which we do right now AFAIK), but I'm not sure if we want to lock ourselves into it.

A quick lookup table for some subset of epochs before finality. I.e., some way to skip to within N epochs of the target epoch so we only have to walk N epochs.

The optimal data structure for this would be skip-list, allowing for arbitrary lookback using O(log(N)) queries.
The overhead is an object with 1 CIDs per epoch on average. For half of the epochs there would be none (as the link with length 1 is in the block header), 1 additional link in 1/4th of the epochs, 2 additional links in 1/8th and so on.

See https://github.com/Kubuxu/go-skiplist-ipld/, which I developed as a base to enable a decentralised Drand randomness index.
It would need to be adapted for Filecoin to support null epochs.

[Stebalien]

For drand timelock, the brand randomness is self-certifying by BLS signature verification.

Yeah, I guess you're right. We can force users to send this information from off-chain if they need infinite lookback.

Arbitrary ticket randomness lookup would require the whole chain of block headers (which we do right now AFAIK), but I'm not sure if we want to lock ourselves into it.

I think that depends on how much data this is. But my understanding is that it's "not much".

The optimal data structure for this would be skip-list, allowing for arbitrary lookback using O(log(N)) queries.
The overhead is an object with 1 CIDs per epoch on average. For half of the epochs there would be none (as the link with length 1 is in the block header), 1 additional link in 1/4th of the epochs, 2 additional links in 1/8th and so on.

That's assuming we need to walk the chain on-disk. @arajasek found that it's pretty reasonable to simply cache chain info in memory so having an actual skiplist embedded into the chain isn't really necessary.

[Kubuxu]

@arajasek found that it's pretty reasonable to simply cache chain info in memory so having an actual skiplist embedded into the chain isn't really necessary.

Yes, but this full cache has quite a long and unpredictable warmup time. If we want to expose it, we would have to require everyone to pre-warm it on every startup, at which point it will be too slow and annoying so we will be looking for on-disk solution.

We also don't have to embed the skip list into the chain, you can think of it as a side-chain/separate IPLD-based index.

[Stebalien]

If we want to expose it, we would have to require everyone to pre-warm it on every startup, at which point it will be too slow and annoying so we will be looking for on-disk solution.

A few minutes isn't terrible... but yeah, an on-disk solution is probably a good idea (but annoying to maintain).

We also don't have to embed the skip list into the chain, you can think of it as a side-chain/separate IPLD-based index.

If we're doing things locally, I'd just maintain an on-disk by-epoch index. We actually already do this, we just don't keep track of the canonical chain. All that's left would be to mark specific epochs as "finalized".

[Stebalien]

Ok, discussed this with @arajasek. The short-term solution is a simple in-memory lookup table and a lookback limit (2-3 days?).

[arajasek]

Scott's thoughts: To resolve uncertainty around what's best to do, focus on "what use case requires a more complicated answer than 'You can only lookup past 1000 epochs'".

[Stebalien]

The current answer is prove-commit, which I'm pretty sure is 30 days and change (86,550 epochs).

This could be solved by requiring storage providers to submit two pre-commit messages: one pre-commit, and one to confirm pre-commit randomness. We can't do it in one message as we need to wait a delay after the first message for security.

[arajasek]

Unassigning Steb so it looks pretty in my sprint tracker :P

[Stebalien]

From our discussion yesterday:

1. We're not defining a limit.
2. We are defining a sloped lookback cost with a generous y-offset and an overestimation of the slope.

In the future, we'd like to change this to be a constant cost but that requires client guarantees we can't make right now.

[arajasek]

Closing this since we have a good plan now. Next steps are FIP and gas pricing change.