vindex: incremental verification #91
Description
Apologies if I misread the documentation and you already have thought about or are planning this:
It would be neat if verifying updates to the summary map could be done incrementally without storing the whole map. Then a lightweight witness could itself sign off on the summary map, without needing to re-compute or store the map itself.
The crypto machinery for this is mostly straightforward. An inclusion proof for a merkle trie (or other authenticated data structure) is almost the same as a modification proof, since you can encode a lookup proof to a leaf in the old trie, and then re-use that to compute the hash of the trie with a different leaf. This update proof can be stored and published the same way as the log.
Happy to prototype if y’all are interested.