[KirinDave]

In part because this is trodden ground for distributed systems engineers and we know that, on balance, the correct solutions all involve massive centralization.

You don't want that. So we're at a bit of an impasse.

Distributed systems these days mostly argue that you do your trusting up front, outside of the protocol itself. You then validate that the actors share the secrets you all agreed upon, and then optimize the agreement process. Only the most robust systems actually consider "active" dissent; most distributed systems engineers consider this a special case that is most often focused on the idea of "incorrectness" as opposed to "maliciousness."

You can see elements of these assumptions in more modern data structures used for eventual consistency, like CRDTs. CRDTs are amazing and fast and often abstract-able to a trivial programming model. Anyone can use them, but they have to be monotonic, so we can't ever forget bad input, just try and cancel it out.

[Magnap]

In some cases you can forget bad input, though, can't you? It's a rather wasteful example, but if (like you say, having established trust beforehand) every element of a grow-only set is a signed message, you can reject any messages that don't validate against their signature when merging. On one hand, this breaks idempotence. On the other, if we regard that set as a subset of the set of validly signed messages, it could not have been there in the first place, so to speak, so I wouldn't immediately think it breaks any guarantees. As far as I can tell, any properly functioning machine will only ever see correct state this way, unless it receives some state and doesn't merge it with anything, for example when initially starting to participate. However, that's easily fixed by always having some state, for example by starting with the empty set in this case.

[KirinDave]

> you can reject any messages that don't validate against their signature when merging.

That's not really what I meant by "bad". I meant bad as in intent, not structural and immediately verifiable message integrity.

If all entities in the coalescing set can independently verify that a message does not meet its signature requirements, it will be rejected and idempotence is maintained.

If ONE member is somehow deceived about key validity it'll propagate the message into every other member's state, eventually.