[DecoPerson]

If the CRDT part is done correctly, then replaying a message that sets a key will not change anything, ever.

If the message is:

Key: Foo

Reference CRDT node ID: 7654321 (the last node that the clients knows of that updated the value of ‘Foo’)

Operation: Update

Value: Bar

The ID of this new node: 1122112211

(Omitted for simplicity: Timestamps, hashes, …)

Replaying that message won’t do anything if the target already knows about the existence of that new node.

If the target didn’t know about the node, then I guess you’re helping them sync their own data? Maybe they owe you a thanks? If you knew what each encrypted message contained, you might be able to do some split-state shenanigans; for example: replay the message that sets a “PasswordAuthEnabled” key to “Yes” but deliberately omit the message that changes the “Password” key from its default of “password” to a genuine password. It’s very hard to imagine an actual situation like this occurring, but I guess that’s what makes crypto (and designing secure systems in general) so damn tricky. That and the math. And end users. And…

[makeworld]

I see, thanks. I was focusing on the "idempotent" part but yeah a CRDT would protect against replays. Still not a great design though, still opens yourself up to issues, in case not all messages are part of the CRDT, or you have a buggy CRDT implementation.

[tlb]

It's a shame that the meaning of 'idempotent' has gotten watered down by half-assed implementations. The original NFS paper from Sun [0] claims that write operations are idempotent, but they aren't really. Not if another operation has occurred. Like in:

  write '1' @ 0
  write '2' @ 0
  write '1' @ 0 (replayed through a duplicated packet)

the duplicated write RPC reverts the second write. Duplicated link and rename RPCs are even worse. They added a replay detection cache in the server later to prevent some common error cases, but it fails if the server reboots in the middle.

Anyway, CRDT correctness is hard enough that I'd be reluctant to trust it against an adversary who can inject replays.

[0] https://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=75...