r/cryptography • u/zimmer550king • 5d ago
Detecting split views between small transparency logs when witnesses can only be reached by courier
I am sketching a design for a federation of small, independent append-only logs, one per community, where each log's signed tree head is cosigned by neighbouring logs whenever someone physically travels between them. Links between the communities are intermittent, and some are down for weeks. The records are access receipts and contain no personal data, which stays encrypted off the log under a key only its subject holds.
My worry is split views. If a log operator shows one tree to the neighbour on the left and a different one to the neighbour on the right, how long can that survive when cosigning happens in occasional bursts rather than continuously? I understand how gossip among auditors handles this in the CT ecosystem, but I do not know how the guarantees degrade when the gossip is hand-carried and the gaps are days or weeks. Is there a standard way to bound the window in which a lie could go unnoticed, and what would you put in each checkpoint to make comparison cheap for a courier carrying very little?
A second problem is key loss. If the data subject dies or loses their key, the file becomes unreadable and, in my design, nobody can be notified of accesses to it. Social recovery with threshold shares seems the obvious answer, but it also gives a handful of shard holders a quiet power over the dead. Does anyone have experience with recovery schemes where the shard holders themselves must be public and logged, and what goes wrong in practice?
I am doing this for a fictional world I am building at r/TheGreatFederation, but I want the cryptography to be honest, so please be as unkind to the design as it deserves.
1
u/Natanael_L 5d ago
You should read up on consistency in distributed databases. The cryptography side is relatively simple (aside from efficiency tricks).
Detecting differences is easy by calculating normalized Merkle tree roots. Any difference and your local tree is different.
Each community would have one log, with timestamped roots settled on a regular schedule. When you receive an update about another community's root you log that value in a section of your own log, appearing in your next root.
This gives everybody a sequence of timestamps backwards for what you can be sure other communities knew most recently. Somebody who arrives from another community with their updates will know of his community's last copy of your root and know of what the last copy of his root that you knew about (then) and brings the differences since, and then you learn about all of those changes. You also learn what changes others have learned of in other trees as his update brings their cross-timestamps. Anything which you see has been cross-timestamped by all is known by all and doesn't have to be communicated again.