Light clients and downloading block bodies

[tomaka]

After having submitted a transaction, a light client generally wants to know when and where the transaction is included in the finalized chain. This is both for UI purposes and to know when to stop gossiping that transaction.

In order to know when a transaction is included, the light client needs to download the body of each block of the best chain and compare the transactions of the body with the one that it has submitted.

While this is not a problem right now, if block bodies become larger in the future, light clients might have to use a lot of bandwidth just to download block bodies. After all, block bodies is one of the scaling factors of the chain. The busier the chain, the bigger the block bodies.

While a light client could ask a full node to send back a proof that a transaction is in a certain block, the full node could simply lie and pretend that the transaction isn't there. There is no way to prove that a transaction is not in a certain block body without sending the entire block body.

I don't have a solution to that problem, which is why I'm just opening an issue.

[tomaka]

One relatively straight-forward way to solve the problem could be to switch extrinsics_root to using V1 of the trie: https://github.com/paritytech/substrate/blob/ece92d6b30ee7f9fbda7a84bee76f8ff6d2c92a1/frame/system/src/lib.rs#L150

If this is done, we could then add a networking request for light clients to ask full nodes for a Merkle proof of the extrinsics trie that only contains the hashes of the extrinsics.
This proof would be around 35 * k to 40 * k bytes, where k is the number of extrinsics. This seems like a reasonable size to me.

Switching the extrinsics_root to V1 would be a breaking change, but we could reuse the state_version field for the migration (and rename it to system_version for example) by setting it to 2.

Another possibility could be to modify the extrinsics trie so that the trie keys are something like concat(transaction_hash, index). This would make it possible for a full node to generate a very small Merkle proof that an extrinsic is or is not in the block body.

[bkchr]

One relatively straight-forward way to solve the problem could be to switch extrinsics_root to using V1 of the trie:

Sounds like a good start to me.

Maybe we could also introduce a bloom filter as part of the header that provides information about present transactions?

[seunlanlege]

concat(transaction_hash, index)

Light clients don't know the transaction index, i think just using transaction hash as the key is fine.

[tomaka]

The light client doesn't need to know the transaction index.
When a light client wants to know whether a transaction of a certain hash is included, the full node would send to it a Merkle proof of all the nodes whose key starts with that hash.