I have a difficult protocol design problem that I need some suggestions for to explore. Please read the requirements carefully because they are very specific, and leave the "it's impossible" comments at the door, because I *know* that this is a seemingly impossible problem already.

(The problem description is also intentionally generalized and reduced down to its core mathematical problem, to avoid unintentional assumptions.)

I have a distributed protocol. The different parties involved mutually distrust each other. They can each contribute mutations to a shared state log, based on some unspecified authorization algorithm which allows for revoking access of other parties. The parties eventually converge onto an identical view of the state, though temporary partitions may occur.

The problem is that a genuine partition followed by a delayed delivery of mutations, seems indistinguishable from a malicious attempt at subverting an access revocation through backdating of mutations.

In both cases, one or more mutations are received which are dated to a timestamp that was potentially a long time ago, and that may be working off an old version of the state.

There is (currently) no shared clock, and there is a small but non-zero span of time between the most recent accepted mutation from a revoked party, and the actual revocation of their access.

How do I prevent backdating, without losing resilience to partitions?

I'm not necessarily looking for full-blown solutions (though those would be welcome!), but even just pointers on relevant research would be welcome, as long as it is research that accounts for all the properties here: untrusted parties, no shared clock, exploitable timespan before revocation.

@joepie91 that's an interesting problem. Can you expand on "no shared clock" requirement?

I don't think it's possible to distinguish between the two scenarios by definition, but! Assuming you have more peers than two and some vector clock kind of structure is acceptable, it could possibly help with bullshit detection.

E.g. if node B says it did a thing 123 at T-10, but node C previously said it received messages about 121 from B at T-5, that's sus.

So like ugh blockchain but opposite, more like neighborhood watch.

@joepie91 especially if "123" is a hash of previous states, so basically every node keeps its own ugh chain of changes that can't be rolled back.

In that case backdating can only be possible if a node did zero communication on the whole network for the whole duration of the supposed partition. So you need to have a whole node dedicated to pulling the stunt once.

Which may or may not be feasible depending on how much there is to gain and lose.