FNP Byzantine Fault Tolerance & Threat Model

fnp advanced 8 min read

ELI5

A Byzantine replica is a server that lies. Instead of following the protocol correctly, it tries to cheat to reorder edits, delete edits, or pretend to be someone else. FNP’s Byzantine defenses ensure that even if the server goes rogue, it can’t cheat without cryptographic proof — like requiring everyone to sign off on any changes.

Technical Deep Dive

Byzantine Fault Model

Byzantine failure: A component can fail in arbitrary ways (lie, cheat, send contradictory messages).

FNP threat model:

Threat	Attacker Capability	FNP Defense
Forge operation	Create fake INSERT/DELETE operations	Dilithium signature verification; only holder of private key can sign
Reorder operations	Change order of edits in merge	Dilithium timestamps + Lamport clock monotonicity check
Delete edits	Remove operations from history	Audit log + git commit immutability; operations are historical records
Impersonate user	Forge Alice’s edits as Alice	Dilithium requires Alice’s private key; asymmetric crypto
Modify content	Change encrypted content in-flight	Halo2 proof verification fails; server rejects modified content
Collude replicas	Multiple Byzantine nodes coordinate	Deterministic CRDT prevents ordering manipulation; majority honesty not required
Replay old edits	Resubmit old operations	Operation IDs + Lamport clocks make duplicates detectable
Clock manipulation	Claim operations in fake order	Lamport clock monotonicity per replica; backwards clock = rejection

Cryptographic Defenses

Against forging signatures:

Work required: 2^256 (brute-force Dilithium, attempting all private keys)
Quantum resistance: Even with quantum computer, 2^128 operations needed (Grover’s algorithm)
Verdict: Unforgeable by realistic attacker

Against reordering:

Each operation signed with Dilithium
Any reordering changes the merkle tree root
Clients detect reordering via proof verification
Verdict: Reordering detectable

Against colluding Byzantine replicas:

CRDT merge is deterministic; all replicas compute identical result
No single replica can force an ordering different from others
Collusion doesn’t help (result must still be a valid CRDT merge)
Verdict: Resistant even with f < n Byzantine replicas

Threat Assumptions

In-scope attacks (FNP defends):

Server is compromised and sends wrong data
Server tries to reorder edits
Attacker tries to forge edits
Attacker replays old edits
Network is eavesdropped
Future quantum computers attack old ciphertexts

Out-of-scope attacks (not defended):

Client malware (user’s own machine is compromised)
Quantum computers attacking live TLS (already quantum-resistant via quantum KEM)
Social engineering (attacker tricks user into sharing key)
Physical server theft (key material stored in HSM, not on disk)

Deterministic CRDT Resilience

The CRDT merge property prevents Byzantine servers from forcing incorrect orderings:

Honest client computes: MERGE(ops_a, ops_b) = result1
Byzantine server claims: result2 (different order)

Result1 and result2 must satisfy CRDT properties:
- Same positions inserted/deleted
- Only order differs

If order differs, Byzantine server's result is invalid CRDT.
Honest clients reject it.

No consensus needed — CRDT determinism replaces voting.

Key Terms

Byzantine fault → Arbitrary failure; attacker acts maliciously
Non-repudiation → Signer can’t deny signing (Dilithium provides this)
Merkle tree → Hash tree; any modification changes root; prevents undetected tampering
Deterministic merge → All replicas compute same result; prevents server-side reordering

Q&A

Q: What if the server refuses to send the audit log? A: Clients store their own copies of operations. A missing audit log is a denial-of-service (server not responsive), not a Byzantine attack. FNP detects refusal and alerts users.

Q: Can Byzantine replicas create new documents? A: Yes, but documents are cryptographically signed by creators. A Byzantine server can’t forge a document from a user without their private key.

Q: What’s the minimum number of honest replicas needed? A: Just one! CRDT determinism means a single honest replica is enough to detect Byzantine behavior. Traditional Byzantine systems (PBFT) require 2f+1 replicas to tolerate f Byzantine nodes. FNP needs only 1.

Examples

Byzantine resilience is like a voting system with cryptographic audit trail: even if a voting machine is hacked, the audit tape (Dilithium signatures) proves the hack. The paper trail (git commit history) is immutable, so hacking one machine doesn’t rewrite history.

neighbors on the map

FNP End-to-End Encryption & Zero Trust Architecture understanding FNP's security layers