Ancestry / prefix proofs for MMRs

[Lederstrumpf]

For proving a BEEFY voter/signatory equivocation against a finalized signed commitment, the equivocation proofs of #1329 currently include headers that the verifier calculates hashes of and compares with on-chain <frame_system::Pallet<T>>::block_hash(block_number). Since this mapping has a horizon of 4096 blocks, equivocations predating this horizon cannot be slashed. While this thwarts attacks assuming a 2/3rds of validators honestly participate in BEEFY finalization and at least one honest relayer can update the beefy light client at least once every 4096 blocks, this is clearly only a temporary solution. This verification is to be complemented by mmr ancestry/pre-fix proofs for equivocations older than 4096 blocks.

Concretely given a current mmr root r, prove that another mmr root r' is its ancestor.

The nervos library used atm has recently implemented a flavor of ancestry proofs (nervosnetwork/merkle-mountain-range#35), but this requires that all the leaves l added to the mmr since r' are included in the verification call (the current implementation creates a membership proof for leaves l, and the proof items happen to be the peaks of r'). This ends up being an expensive call (O(n_leaves_since_r')): we might then just as well provide a headerchain back to the block including r'.

Efficient MMR ancestry/prefix proofs require proving membership of nodes, whereas the nervos library can currently prove leaves only (both a hardcoded assumption, as well as changes required to the proof structure).
A PoC of membership proofs for nodes can be found here.

Tasks

Beta Give feedback

1. Rebase PoC atop mmr library version currently used (0.5.2)
2. Implement ancestry proof PoC (https://github.com/Lederstrumpf/merkle-mountain-range/tree/linearize-proof-rebase-v0.5.1)
3. Integrate PoC into BEEFY: add support for slashing validators signing forking commitments #1903
4. Optimize PoC (in particular, proof structure can likely be simpler for proving strictly former peaks)
5. Upstream to https://github.com/nervosnetwork/merkle-mountain-range/

[acatangiu]

Let's develop them here https://github.com/paritytech/merkle-mountain-range - we can then upstream to nervos from here.