BlockHeaderInnerLiteView::block_merkle_root should include entire previous epoch

[MaksymZavershynskyi]

Currently BlockHeaderInnerLiteView::block_merkle_root includes merkle tree built from the headers in the current epoch up until the current block. This creates the following issue:

• Suppose light client's head is currently at block X of epoch E;
• Suppose the node is currently at block Y (Y>X) of epoch E+1;
• Light client requests the next LightClientBlockView from the node and provides information of its last known node (X);
• The node returns the block Y.

Unfortunately, the merkle root of the headers references in Y only includes blocks form epoch E+1. The merkle root of the headers of block X does not include blocks from X+1 to the last block in epoch E. As the result the light client cannot verify transaction outcomes for these blocks.

Potential solutions:

• Light client always requests the last block for each epoch. Unfortunately this means that light client needs to have at least two blocks for each epoch. It also makes the current RPC endpoint for the light clients not self sufficient;
• (proposed solution) the merkle tree of the headers should always include the previous epoch. This creates some overlap between the merkle trees, but it makes it sufficient to have one block per epoch.

[MaksymZavershynskyi]

CC @SkidanovAlex
This is a blocker for the bridge and specifically for Near2EthProver contract that @k06a is currently working on, therefore assigning priority P0.

[SkidanovAlex]

I believe block_merkle_root is a merkle root of all the blocks, not just the blocks in the current epoch.
I might be wrong, but I don't see in the code resetting it on the epoch boundary.

[MaksymZavershynskyi]

@SkidanovAlex I don't understand the format of our merkle tree then. Could you please give example of merkle tree and how it is updated when one block is added to it?

Suppose we have 4 blocks B0, B1, B2, B3. I would expect the merkle tree to look like this:

    root
   /    \
 /\      /\
B0 B1  B2 B3

How do we update it when block B4 is added?

[bowenwang1996]

This is not true. The merkle root include every block up to the previous block of the current head.

[bowenwang1996]

@nearmax we always maintain the path for the next leaf. In this case what we maintain in path is [root]. When B5 comes in the path is updated to [root, B5], which is the path for B6.

[MaksymZavershynskyi]

This is not true. The merkle root include every block up to the previous block of the current head.

I am not sure what do you mean. Also when you say "this is not true" what "this" is referring to?

[bowenwang1996]

@nearmax I was referring to

Unfortunately, the merkle root of the headers references in Y only includes blocks form epoch E+1

I didn't refresh the page so didn't see the two comments above.

[SkidanovAlex]

@nearmax the way I understand the tree, the progression of the hashes is the following:

B0
hash(B0, B1)
hash(hash(B0, B1), B2)
hash(hash(B0, B1), hash(B2, B3))
hash(hash(hash(B0, B1), hash(B2, B3)), B4)
hash(hash(hash(B0, B1), hash(B2, B3)), hash(B4, B5))
hash(hash(hash(B0, B1), hash(B2, B3)), hash(hash(B4, B5), B6))
hash(hash(hash(B0, B1), hash(B2, B3)), hash(hash(B4, B5), hash(B6, B7)))

etc

In short, it is like a regular merkle tree of all the blocks, but the nodes that have only one child are collapsed. E.g. instead of

     A
   /   \
  B     C
 / \   /
D   E F

we get

     A
   /   \
  B     F
 / \   
D   E 

(node C is collapsed, because it only has one child)

I guess documenting it wouldn't hurt :)

[MaksymZavershynskyi]

Do I understand correctly that block_merkle_root is not signed by the validators, it is not included in the actual block header, and it is constructed on the fly when light client RPC query is made based on what was the previous known head?

[bowenwang1996]

@SkidanovAlex you are absolutely right and offered a much better explanation than I did :) It almost makes me wonder who actually implemented this :)
@nearmax

Do I understand correctly that block_merkle_root is not signed by the validators

It is signed by validators since it is part of BlockHeaderInnerLite, which is part of the hash computation for block header and the validators sign the hash of a block header.

[SkidanovAlex]

As per spec, it is part of BlockHeaderInnerLite, as such it is signed, and is not constructed on the fly, it is updated incrementally with every block.

[MaksymZavershynskyi]

So the virtual merkle tree grows endlessly, since we do not reset it between the epochs? Does this mean that the proofs for this tree will become longer and longer as the time passes? (For instances in @SkidanovAlex 's example the proof for B0 went from 0 nodes to 1 to 2).

[SkidanovAlex]

Correct. It grows endlessly with logarithmic speed.
Though you are right that replacing it with the merkle root of the full previous epoch + whatever has already happened in this epoch is sufficient for reasons of proving something that happened between the previous light client block view and the current light client block view, the way it is implemented now it allows the light client to have proofs of inclusion at any point in the past while only keeping one light client block view locally.

UPDATE: couple changes above

[bowenwang1996]

It grows endlessly with logarithmic speed

Yes. I have considered this when I implemented it. But given at the amount of blocks is bounded by u64, the log of which is 64. I think it should be fine :)

[MaksymZavershynskyi]

Yeah, I am mostly concerned with feasibility of verifying long merkle paths in Eth and other blockchains. But it seems like it will take 10 years to get path to be 29 nodes long, which will cost < 100k Eth gas for proof verification. Which should be fine.
Closing this issue now. Thank you @bowenwang1996 and @SkidanovAlex for the explanation.