Forecast range for certificate validation

[amesgen]

Especially for #24, it is important that we can actually validate all certs that could boost blocks in a Genesis window. For this, we need to ensure that the forecast range is large enough.

---

Intuitively, it seems to me that what we need is:

• Votes can only be cast for blocks that are at most a stability window old.
• Forecast range of two stability windows for certs. I think the HFC is the only obstacle here, but this might be resolved by not voting across era boundaries?

[amesgen]

Assumptions

• Assumption 1. We can enforce an upper bound perasBlockMaxSlots of the age of a block B that a vote v is voting for, ie B must be at most perasBlockMaxSlots slots older than the first slot of round(v). Concretely, set perasBlockMaxSlots to a chain quality window (kcp/asc slots on Cardano).

• Assumption 2. We can move back epoch nonce snapshotting from 4kcp/asc before an epoch to 7kcp/asc before an epoch.

  This seems fine to me, but we should definitely clarify this. In particular, the Praos parameterization notes require chain quality + chain growth between (so 4kcp/asc) snapshotting the stake distribution and the epoch nonce, while it would only be 10kcp/asc - 7kcp/asc = 3kcp/asc in this proposal. However, this requirement seems overly conservative.

Description of Peras forecasting

In order to validate a vote or certificate X, we need the following state:

• From the Ledger state:

  • The stake distribution, as well as any registered public keys necessary to validate the signature(s).

  • Certain protocol parameters, like max Peras vote/cert size.

  The data should be the same as one would use to validate a header in the same slot as X.¹

• From the Consensus state:

  • The epoch nonce, for the epoch of X.¹

Package up this data in a PerasView. We can get a PerasView out of an extended ledger state st by (Peras-specific) forecasting:

perasForecast ::
     ExtLedgerState                        -- ^ @st@
  -> PerasRoundNo                          -- ^ Peras round we want to validate votes/a certificate in
  -> Either OutsideForecastRange PerasView

We elide configuration data here. The range of forecasting is perasForecastRange = chainGrowthWindow + perasBlockMaxSlots slots (so 4kcp/asc slots).

This function can be implemented on Cardano (for a future Peras-enabled era):

• HFC era transitions are known more than perasForecastRange = 4kcp/asc slots in advance as of Conway: Concretely, assuming chain growth, they are known at least 7kcp/asc in advance.

  The simplest change in the Haskell implementation here would be to increase the safe zone of a future Peras-enabled era from 3kcp/asc to 4kcp/asc, and move the voting deadline back to the start of the epoch (which we could have already done for Conway, but didn't as there was no motivation).

• The stake distribution/protocol parameters are known one epoch in advance (the latter only as of Conway).

• Under assumption 2 above, the epoch nonce is known at least 7kcp/asc slots in advance, so it is known at least 4k/f in advance without being subject to rollback (assuming chain growth).

  In the implementation, this would mean block/slot counting (or a combination of both) similar to the HFC to decide whether the epoch nonce is stable. I think slot counting sounds good; block counting seems dubious in light of Peras (due to boosted blocks).

Importantly, perasForecast satisfies the following property, similar to HFC time translations:

Property (Peras forecast stability): For any two (extended) ledger states st0/st1 that a node can observe (apart from disaster scenarios) with perasForecast r st0 == Just pv0 and perasForecast r st1 == Just pv1, we have pv0 == pv1.

Here, the important bit is the phrasing "ledger states that the node can observe (apart from disaster scenarios)". By this, we mean ledger states that correspond to a block that the node has selected. Due to the kcp rollback restriction, assuming chain growth, a node will never select two ledger states that indicate different eras/stake distributions/epoch nonces for the next epoch.

Side note. These changes would also allow us to increase the regular header forecast range to perasForecastRange if consistency here is desirable (the stability window and Genesis window still needs to remain at 3k/f).

A note on chain growth

We often assume chain growth above. Most directly, chain growth means that there are at least kcp (or kcp+1) blocks in a stability window (of size 3kcp/asc). However, for the discussion above, we actually only rely on a weaker condition, that becomes relevant during low honest participation. Namely, we fundamentally only assume that once we have selected a chain C, we never switch to chain that forks off from C more than a stability window before the tip of C. During low honest participation, this property can be true (when the adversary is sufficiently weak) despite less than kcp blocks arising in a stability window.

Getting rid of Assumption 2?

Ideally, we wouldn't need Assumption 2 (but it also doesn't seem that bad to me). However, I don't see a good alternative.

Fundamentally, we need to know the epoch nonce to validate a vote in general,² and we have no idea what the epoch nonce for the next epoch will be until we have selected sufficiently many (kcp) blocks after the nonce snapshot point.

A few ideas:

1. A vote/certificate always is voting for/certifying a particular block/header. Validating that header means that we have the corresponding epoch nonce (this might be different from the epoch nonce used to validate the header, if the vote is from the successor epoch of the header), so we can validate the vote then.

   However, this significantly complicates the architecture as we now need to account for votes that we have received but can't (yet) validate. In particular, I don't see a (non-super-messy) way to prevent an adversary from sending us lots of unvalidatable votes for blocks that don't actually exist.

   Or we somehow require servers to only send us votes/certificates if they can be certain that we (the client) have the header that they are voting for.

   • Refinement: use the epoch nonce of the block that is being voted for (requires at least one bit of extra info in a vote/cert).

     This is nice because it doesn't require us to have the header that is being voted for. Not true.

     Main downside/weirdness is that there are essentially two committees for certain Peras rounds (those near the start of an epoch), which is confusing, eg it allows up to twice the amount of vote traffic.

2. When we are caught-up, we only need to Peras-forecast a very small amount of slots into the future, so we could just assume that e.g. the epoch nonce corresponding to the currently selected chain is "the" epoch nonce. While syncing, it seems fine to always Peras-forecast from the ledger state corresponding to the LoE (potentially waiting until we have one for the LoE).³

   This seems very ad-hoc, unsatisfying, and easy to make mistakes with.

3. Introduce an extra epoch of delay after the nonce has been snapshot. Very similar in spirit to moving the epoch nonce snapshot point backwards, but doesn't have the downside of shortening the interval between snapshotting the stake distribution and the epoch nonce.

   On the other hand, we now need stronger stake shift assumptions, and changes to stake pools like an epoch longer to come into effect.

   (This is a somewhat more principled variant of the idea from footnote¹, as that one seems very suboptimal.)

4. Stop doing header-body split. Seems like a huge amount of work.

Footnotes

1. Technically, I guess it is possible that we use different (older) data here, but especially for the stake distribution, this seems very confusing (eg a pool having different amounts of stake for Praos and Peras), so we shouldn't pursue this unless we don't see an alternative. ↩ ↩² ↩³

2. With the Fait Accompli committee election scheme, many votes can actually be verified without the epoch nonce, but the adversary can of course just register small pools that are not subject to deterministic allocation, so this doesn't really change the problem. ↩

3. The idea is that the LoE will definitely end up being on all of our selections (or eventually immutable), and we are either forecasting from more than 4k/f slots before the end of the epoch, in which case we can use the current epoch nonce, or we need to forecast into the next epoch, in which case we are forecasting from after the nonce snapshot point. ↩

[amesgen]

One interesting thing is that we also need a (bounded) "negative forecast range" (probably should use a better name for that), in order to validate old certificates in blocks.

This shouldn't be difficult, just need to keep a fairly small amount of old state (e.g. stake distribution + protocol params + epoch nonce for the previous epoch) around. The stake distribution and protocol params of the previous epoch are already recorded in the ledger state for reward calculation.

[amesgen]

The researchers understand the problem/tradeoff here and will report on whether moving the epoch nonce snapshotting earlier is feasible.