Log2 Ancestors Module

[rphmeier]

The idea behind log2 ancestors is to keep a record of some block hashes in the history of the chain.

decl_storage! {
    Ancestors: map BlockNumber => (BlockNumber, Hash);
}
fn initialise() {
    let number = current_number() - 1;
    let parent_hash = parent_hash();

    let mut index = 0;
    let mut working_number = number;
    while index < 32 {
        Ancestors::put(index, (number, parent_hash)); // storage
        if working_number % 2 != 0 { break }
        working_number /= 2;
        index += 1;
    }

    // post-condition: Ancestors(index) stores the hash and
    // number of the last block whose number was divisible by 2^index.
}

We can use this module to safely skip backwards in the finalized chain, so long ancestry proofs become shorter.

[jimpo]

If I understand correctly, the ancestry proofs would consist of a mix of ~log (m - n) headers and storage proofs where m is the height of the chain and n is the height of the ancestor.

Like say the chain height is 17 and you want to prove inclusion of block 5. Then the proof is:

• Block 16 header + storage proof with respect to block 17 state root
• Block 8 header + storage proof with respect to block 16 state root
• Block 6 header + storage proof with respect to block 8 state root
• Block 5 header + storage proof with respect to block 6 state root

This is pretty much the same structure as a Merkle Mountain Range, but more indirect. With a Merkle mountain range, instead of just storing the block hash at the indices, you store the root of a full binary Merkle tree to the previous power of two index. Thus the inclusion proof for the above scenario would be:

• Merkle root over all blocks 1-16 + storage proof with respect to block 17 state root
• Regular merkle branch proving inclusion of header in the above merkle root

This has the same nice property that ancestry proofs for recent blocks are short. The code is barely any more complicated, but does involve one hash evaluation for each execution of the inner loop, which is expected to be constant and log(n) in the worst case.

BUT with the MMR approach, nodes would need separate storage for the non-pruned part of the header tree. This doesn't feel that different from the original proposal, however, where only nodes running in archive mode can generate proofs.

[rphmeier]

The MMR approach seems to require a lot of substrate storage changes and other implementation effort (to avoid duplication - I can't see it being efficient to embed an MMR in the regular state trie).

Whereas the log2-ancestors thing gets us most of the way there with barely any implementation overhead - we will have more indirections, but most likely we won't bother with the hops for small powers-of-two and just return all of those headers.

I'd propose to revisit the MMR later since it is a better way on paper of doing the same thing

[jimpo]

This still has the downside that only archive nodes can produce proofs, aside from the proof size inefficiency.

Two other alternatives:

1. Just store all of the block hashes for the entire chain in storage where the key is PREFIX + LITTLE_ENDIAN(block_number). This increases the chain state by one item every block, but that's not that much data and the proofs are dead simple, log-size, and do not require an archive node to produce.
2. Use an MMR with the MMR peaks stored in the state and put the MMR intermediate nodes in the block headers as a log item. This is clearly a hack, but it's an easy way to look up MMR intermediate nodes required to construct proofs by block number since all nodes store all of the headers. The amount of data is just an extra 32 bytes per header in expectation.

[rphmeier]

Option 2 is pretty crafty put I don't see it working well for already-deployed chains or runtime upgrades in general.

I think srml_system does something similar to option 1 already, although as always it is only trustworthy to light clients on finality.

[jimpo]

Hmm, this Log2 ancestors proposal also seems to be problematic for already-deployed chains since you can't backfill previous states. There could be a hack where the first block that the upgrade is activated on has all previous block hashes then prunes them immediately afterward, but that's gross.

And the BlockHash mapping in srml-system does look like it could work, but there's a pruning window which defaults to 10 blocks.