MMR Leaf Data: off-by-one error in beefy_next_authority_set

[acatangiu]

A given Leaf with MMR 0-based leaf index N-1 is constructed and added to MMR during construction of block N here.

The Leaf data/contents can be seen populated here and it consists of:

// contents for leaf index <N-1> added by block <N>
MmrLeaf {
    version: <leaf-data-format-version>,
    (
        parent_num: <N-1>,
        parent_hash: <hash_of_<N-1>>,
    ),
    extra_data: <para_heads_of_<N-1>>,
    next_auth_set: <next_auth_set_of<N>>,
}

While this is not a show-stopper - (light)clients can simply handle this in their code - it introduces cognitive complexity and code logic corner cases.

We could avoid this and make it easier for users by changing Leaf<N-1> contents to:

// contents for leaf index <N-1> added by block <N>
MmrLeaf {
    version: <leaf-data-format-version>,
    (
        parent_num: <N-1>,
        parent_hash: <hash_of_<N-1>>,
    ),
    extra_data: <para_heads_of_<N-1>>,
-   next_auth_set: <next_auth_set_of<N>>,
+   next_auth_set: <next_auth_set_of<N-1>>,
}

[acatangiu]

AFAICT an easy fix is to move Mmr: pallet_mmr before pallet_session so that it builds its leaf before session is rotated.

But I would prefer a fix contained in pallet_mmr itself since above is prone to developer error when adding pallet_mmr to their runtime.

[Lederstrumpf]

AFAICT an easy fix is to move Mmr: pallet_mmr before pallet_session so that it builds its leaf before session is rotated.

So since session is rotated prior to leaf construction currently, next_auth_set: <next_auth_set_of<N>> (i.e. Pallet::<T>::beefy_next_authorities()) can be distinct on forks of depth 1?

[vgeddes]

We haven't really been affected by this off-by-one issue while developing our light client (or we just worked around it).

The proposed change may affect how our light client detects authority handovers. But I have a feeling there shouldn't be any impact. If there is we can update our code.

Some background on our light client: It receives updates like the following at the start of every beefy session (Assume a session length of 10 blocks). Each update contains the beefy commitment for block N (first block of session) and the MMR leaf for block N-1 (last block of the previous session).

Update:
  BeefyCommitment(block=11) { validatorSetId: 1, ... }
  MmrLeaf(block=10) { nextValidatorSetId: 2, ...}

Update:
  BeefyCommitment(block=21) { validatorSetId: 2, ... }
  MmrLeaf(block=20) { nextvalidatorSetId: 3, ... }

Update:
  BeefyCommitment(block=31) { validatorSetId: 3, ... }
  MmrLeaf(block=30) { nextvalidatorSetId: 4, ... }

The light client knows it can perform an authority handover when the latest update contains a leaf.nextValidatorSetId that is greater than that of the previously observed value (See code here).

[acatangiu]

AFAICT an easy fix is to move Mmr: pallet_mmr before pallet_session so that it builds its leaf before session is rotated.

So since session is rotated prior to leaf construction currently, next_auth_set: <next_auth_set_of<N>> (i.e. Pallet::<T>::beefy_next_authorities()) can be distinct on forks of depth 1?

There is no issue for forks in either option (current behavior & suggested change) because the validator set is identical for blocks at height N (or N+1, ..., N+m) across all forks.

The issue is more about usability in the sense that the BEEFY payload for block N is a MMR root where latest latest leaf is a set of primitives coming from a mix of blocks N-1 and N; it could be simplified to:

(block numbers are 1-indexed whereas leaf indexes are 0-indexed)
BEEFY payload for block N contains MMR root built from leaves indexed L in 0..=N-1, with each Leaf index L containing primitives coming exclusively from block number L.
At block N, the latest leaf L=N-1 contains primitives values pertaining to block N-1 (instead of some from N-1 and some from N).

---

Marking this as "Some day maybe" since existing clients already successfully handle current behavior.

[seunlanlege]

actually have encountered this issue and i created this pr as a fix: #10907

[acatangiu]

actually have encountered this issue and i created this pr as a fix: #10907

this is actually something different - by building leaf on_finalize() you actually get:

// contents for leaf index <N-1> added by block <N>
MmrLeaf {
    version: <leaf-data-format-version>,
    (
        parent_num: <N-1>,
        parent_hash: <hash_of_<N-1>>,
    ),
-   extra_data: <para_heads_of_<N-1>>,
+   extra_data: <para_heads_of_<N>>,
    next_auth_set: <next_auth_set_of<N>>,
}

and at this point you also run into trouble with 1-block deep forks writing different leaf contents to offchain db for same (parent, pos) key.

The offchain-db thing can be fixed by also doing #11799.

---

@seunlanlege Is the mixed layout of MmrLeaf above really better?

Isn't light-client code simpler if it simply references leaf index N when interested in extra_data of block N?
(i.e. for N=5: leaf index 5 is the leaf added by block 6 containing extra_data of block 5)

[seunlanlege]

Isn't light-client code simpler if it simply references leaf index N when interested in extra_data of block N?

So you're correct that this makes sense, but only from a leaf index perspective.

But light clients won't be tracking leaf indexes, they'll be tracking block heights.

And it's a bit wonky from that perspective that a leaf emitted a block N contains data about N-1 especially when there's no clear advantage to having it this way.

Whereas it's easier to reason that a leaf emitted at block N contains information about block N.

Also the leaves in this N-1 will miss the authority set change. So you'll need a leaf N+1 where N is the authority set change height to know exactly the beginning of a new epoch. Which is just cognitive overhead.