file: use append only merkle-tree or SMT in the file format to allow for probabilistic verification?

[Roasbeef]

The file format will grow linearly as the number of transfers do. One idea to reduce validation costs somewhat (though it can be parallelized) is to commit to a tree of all the individual transitions in the file. Given this tree, a verifier can use a hash function as a random oracle (a la the fiat shamir transform) to implement probabilistic verification, in a cut-and-choose style. A verifier would then repeat this verification in order to achieve a negligible probability of a fake asset/file.

[bhandras]

Could be useful? https://eprint.iacr.org/2015/007

[Roasbeef]

@bhandras interesting haven't heard of it, will dig in! Originally I was thinking of something like this:

• https://docs.grin.mw/wiki/chain-state/merkle-mountain-range/
• https://github.com/opentimestamps/opentimestamps-server/blob/master/doc/merkle-mountain-range.md

It's a set of complete binary trees that you can just continually append to. This way each time you add a new entry in the file, you just add/merge a sub-tree, and then update the main root.

The flyclient protocol uses them in a few areas: https://eprint.iacr.org/2019/226

[Roasbeef]

FWIW this is also a later optimization that can help allow verifiers to achieve a high assurance (negligible probability of an invalid asset) of the provenance of an asset w/o necessarily having to validate the entire thing.