Merkle Tree Proof deep dive.

[jam10o-new]

The merkle tree (and proofs) expected in the dat_verify.rs pallet should match the tree used in hypercore-crypto/hypercore with the exception that the merkle root passed to substrate is the checksum used to calculate the signature, not the roots used to calculate it.

How it's verified in datdot-substrate

Here is the function signature of the submit_proof function:

https://github.com/playproject-io/datdot-substrate/blob/ac0e44e02c34c454c7bda58eee855de2054e34a4/bin/node/runtime/src/dat_verify.rs#L490

where the Proof type is a struct defined here: https://github.com/playproject-io/datdot-substrate/blob/ac0e44e02c34c454c7bda58eee855de2054e34a4/bin/node/runtime/src/dat_verify.rs#L192-L196

this should match the [merkle proofs returned by hypercore]:(https://github.com/mafintosh/hypercore/blob/1082cc5f8803f5bce65686f799784920d1426088/index.js#L537)

First we verify that the proof is being submitted by the correct user:

https://github.com/playproject-io/datdot-substrate/blob/ac0e44e02c34c454c7bda58eee855de2054e34a4/bin/node/runtime/src/dat_verify.rs#L493-L496

(I am considering removing this check)

We verify that the signature provided matches the merkle root (checksum) provided and is signed by the public key associated with the challenge (currently PUBLISHER, should be ENCODER):

https://github.com/playproject-io/datdot-substrate/blob/ac0e44e02c34c454c7bda58eee855de2054e34a4/bin/node/runtime/src/dat_verify.rs#L503-L509

We verify the chunk hash matches the chunk hash provided in the Proof by recalculating it and getting the node with the index of the chunk from the proof:

https://github.com/playproject-io/datdot-substrate/blob/ac0e44e02c34c454c7bda58eee855de2054e34a4/bin/node/runtime/src/dat_verify.rs#L520-L543

finally, based on the index being proved, we calculate the merkle roots (using a hacky linear-time calculation to get the expected indeces the roots should contain), and use them to rebuild the merkle root checksum:

https://github.com/playproject-io/datdot-substrate/blob/ac0e44e02c34c454c7bda58eee855de2054e34a4/bin/node/runtime/src/dat_verify.rs#L544-L568

There is currently an oversight in the lack of verification of intermediary nodes of the merkle path - this would be the final step.

[jam10o-new]

Structs:

https://github.com/playproject-io/datdot-substrate/blob/ac0e44e02c34c454c7bda58eee855de2054e34a4/bin/node/runtime/src/dat_verify.rs#L191-L228

https://github.com/playproject-io/datdot-substrate/blob/ac0e44e02c34c454c7bda58eee855de2054e34a4/bin/node/runtime/src/dat_verify.rs#L87-L91

[jam10o-new]

@RangerMauve are these the pointers you wanted?? :sweat_smile:

[RangerMauve]

I think that looks great, thank you! 💜

[serapath]

https://arxiv.org/abs/2002.07648