re: 0006: Blocks needed for operation inversion depends on the order of the operations

[DavidBuchanan314]

According to my experiments, the set of blocks required to invert a sequence of multiple operations can depend on the order you invert them in (occasionally).

This is a little counterintuitive, since the MST itself is insertion-order-insensitive.

I think it should be specified that verifiers need to invert the operations either "in the same order as the ops list" or "in the reverse order of the ops list" , or some other canonical/deterministic order (doesn't really matter, as long as it's defined)

[bnewbold]

That was also sort of my expectation, personally: that the order of ops list matters.

We debated this internally, and decided to require enough blocks to allow inversion regardless of the order of operations. This trades off a bit of wire overhead (redundant blocks emitted in some corner-cases) to work around naive or incorrect implementations on the consumer side. And to avoiding needing to make a semi-arbitrary ordering decision, and make this all (potentially) a bit easier to reason about.

At least in the TypeScript implementation, we take the interop test files (https://github.com/bluesky-social/atproto-interop-tests/tree/main/firehose) and try all permutations of the ops list.

[DavidBuchanan314]

Hmmmmm, that makes sense, although personally I find "figure out how to include all blocks regardless of order" a pretty hard thing to reason about.

My current (draft, not really tested) PDS-side implementation is fairly direct - I perform the inverse of the operations, and log any blocks that needed to be read during the process: DavidBuchanan314/millipds@4ce60c0#diff-ac30a6340963addff5e40c044875df5a614cc03f700e6408e46ac47342aaf416R319

But, this has the aforementioned order sensitivity (in edge cases). So I'll have to do some more thinking about how to include all the blocks...

[DavidBuchanan314]

I just had another thought about this.

A relay (or other consumer) will verify the inversion proof by inverting the individual operations in some concrete order, even if that order is not defined in a spec.

If the producer of the proof (accidentally or on purpose) constructed a proof that is considered valid in one order but invalid in another (due to strategically missing blocks), some verifying consumers may see it as valid while others will not (even though all consumers are strictly conforming to spec). This seems undesirable.

You could solve this by having consumers verify that all maybe-required blocks are present regardless of operation order - that sounds expensive to do, although maybe there's a cheap method I haven't thought of.