Avoid unbounded proofs for SCORU Inbox
This is a follow-up issue for #2759 (closed).
The proofs defined in Sc_rollup_inbox_repr are currently a bit inefficient in the case when they prove the first message in a new level---especially if there are empty levels in between that message and the last one. There is a further issue with the current implementation in that the proofs have unbounded size; if there were many consecutive empty levels in the inbox the list of skips in the proof could be arbitrarily long.
This issue proposes to fix this by either:
-
implementing a slightly more sophisticated inclusion proof that specifies the path taken through the merkelized skip list from the sub-inbox to the super-inbox, and allows you to prove the property of being empty at some of the intermediate inboxes in the path. This wouldn't prevent the proof eventually becoming arbitrarily large, but we could calculate the size-per-empty-level and perhaps the 32kb limit would only be reached once the number of empty levels was so huge that it wouldn't matter that the rollup would be 'dead'.
-
alternatively, refactor the skip list in the inbox so that it misses out empty levels. This might actually be a simplification of the inbox code---the function
archive_if_neededis what needs to change. Then the inbox proof would only ever have to include one element in the list (it could be refactored to have two casesWithin_levelandNext_level). There would still need to be a small change toinclusion_proofto allow it to prove when the inclusion has no levels in between the top levels of each inbox.
In fixing this issue it is worth giving a bit of thought to the very first step that involves the inbox---is it possible this could be especially bad if there are many empty levels before the first non-empty one?
Update: this issue includes three outstanding problems with the inbox implementation and inbox proofs:
- The proofs have unbounded size; if there are many consecutive empty levels the proof may have to include them all.
- The metadata attached to an inbox (current level number, number of messages in current level) are not included in the hashes that go into the skip list. Thus in the current implementation it's possible for an inbox proof to lie about these metadata. The proof validation should only trust what is actually in the merkle trees and the skip list, which currently may not be enough.
- The merkle tree structure for a single level is currently flat, which means if there are a lot of messages in one level the proof-size could get large. (Is this actually an issue? It depends on irmin's implementation of the merkle tree.)
To solve both (1) and (2) we can put slightly more data into the merkle tree of an inbox level; it should be enough to just add the level number itself. Then (2) is solved (as long as we are careful) because the proof can validate that the level is the correct one. This also allows us to solve (1) because the inbox's skip list can completely miss out levels that are empty.
The third of these isn't as high priority but since this issue will be solved with an MR that slightly reshapes the merkle tree for each level, it may as well tackle that too.