fork-consistency · research

Fork consistency

Fork consistency allows an untrusted server to split clients' histories but prevents silently rejoining those histories after they diverge.

In SUNDR, honest clients retain their own last operation and authenticate accepted histories; seeing another branch or communicating can expose divergence, but detection need not be immediate. Moving between clients requires the retained state as well as the key. [1]

Local signature validity, payload equality, extension of a remembered checkpoint and cross-observer agreement are separate checks. RFC 9162 illustrates the distinction for transparency logs; it is not a storage protocol. [3]

Depot uses Fork-Join-Causal consistency and additional protocols to support progress after divergence, rather than the same permanent no-join condition. A read still needs a correct reachable holder. [2]

Hesela's deterministic illustration explicitly restores an old in-memory checkpoint: a previously rejected branch becomes acceptable while a separately retained newer checkpoint still rejects it. Equal final payloads also coexist with incompatible histories. These controls do not test backup software or crashes. [5]

Relations

related
Linearizability, Merkle tree, Replay attack, Session guarantees

Limitations

  • The retained-state assumption excludes silently restoring an older checkpoint; a recovered signing key alone does not establish freshness. [1, 5]
  • The no-wait impossibility result is scoped to asynchronous server-mediated access to at least two single-writer/multi-reader registers, not all authenticated storage. [4]

Citations

  1. Li et al. Secure Untrusted Data Repository (SUNDR). OSDI 2004; sections 2 and 3.1-3.2. (accessed 2026-11-11)
  2. Mahajan et al. Depot: Cloud storage with minimal trust. OSDI 2010; section 1. (accessed 2026-11-11)
  3. RFC 9162: Certificate Transparency Version 2.0. Experimental, 2021; sections 8.3 and 11.3. (accessed 2026-11-11)
  4. Cachin, Keidar and Shraer. Fork Sequential Consistency is Blocking. arXiv:0805.2068v1, 2008; section 2 and Theorem 1. (accessed 2026-11-11)
  5. Hesela: frozen signed-history results, source revision, SHA-256 hashes and offline replay. (accessed 2026-11-11)

Further reading

  1. Hesela: Valid signatures do not establish a shared history. (accessed 2026-11-11)
Sources & caveats
  • Definition scoped to SUNDR; no claim that every signed history implements its protocol. [1]
  • Seven original cases plus six checkpoint/offer controls and encoding/equal-payload checks use real Ed25519 with public fixture keys. No network, durable checkpoint, hardware or deployed-service experiment. [5]
  • The baseline in the replay ZIP is explicitly defective historical code; the corrected verifier rejects noncanonical signature text. [5]
  • RFC 9162 is Experimental and does not specify a gossip protocol. [3]

JSON: /data/terms/fork-consistency.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Fork consistency. Hesela. 2026-11-20. https://hesela.dev/terms/fork-consistency/