self.echocount: dict[bytes, set[int]] # which senders echoed each digest
Bracha's Algorithm implements reliable broadcast over a network of N = 3f+1 nodes, tolerating up to f Byzantine (arbitrarily malicious) nodes. The core idea is quorum intersection: any two sets of N−f nodes (size 2f+1) overlap in at least f+1 honest nodes, guaranteeing agreement.
Sender(node s, message m):
1. Sign payload = (s, m, seq)
2. Send ⟨SEND, payload, σ_s⟩ to ALL nodes
Every node i (including sender):
Upon 1st valid ⟨SEND, payload, σ_s⟩:
→ Broadcast ⟨ECHO, payload, σ_i⟩ to all nodes
Upon ≥ N−f = 2f+1 distinct ⟨ECHO, payload, *⟩:
→ Broadcast ⟨READY, payload, σ_i⟩ to all nodes
Upon ≥ f+1 distinct ⟨READY, payload, *⟩:
→ Broadcast ⟨READY, payload, σ_i⟩ (amplify if not yet sent)
Upon ≥ 2f+1 distinct ⟨READY, payload, *⟩:
→ Deliver m (invoke callback)
BrachaNode# Core state tracked per message digest
self.echo_count: dict[bytes, set[int]] # which senders echoed each digest
self.ready_count: dict[bytes, set[int]] # which senders sent ready for each digest
self.sent_echo: set[bytes] # digests we already echoed
self.sent_ready: set[bytes] # digests we already sent ready for
self.delivered: set[bytes] # digests already delivered (integrity)
# Message authentication: every message carries an HMAC-SHA256 signature
# verified against the sender's public key before processing
Critical thresholds (with proof):
| Threshold | Value | Purpose |
|---|---|---|
| ECHO count ≥ | N−f = 2f+1 | Guarantees at least f+1 honest nodes echoed (quorum) |
| READY amplify ≥ | f+1 | Single honest node's READY triggers broadcast to all |
| READY deliver ≥ | 2f+1 | Guarantees at least one honest node sent READY → agreement |
Every message is signed with the sender's private key (using HMAC-SHA256 on a canonical JSON payload of {sender, msg, seq}). Recipients verify against the sender's public key before accepting any message. This prevents impersonation and message tampering.
| Behavior | How the protocol resists |
|---|---|
| Silent nodes | Thresholds account for f missing responses; N−f = 2f+1 suffices |
| Equivocation | Each node tracks distinct senders, not raw message count. Malicious nodes get only one vote per message digest |
| Bad signatures | Signature verification drops invalid messages immediately |
| Malicious sender | If sender sends nothing → no honest node reaches SEND threshold. If sender sends garbage → signature fails |
| Selective forwarding | Any honest node that reaches 2f+1 READYs triggers amplification at f+1, spreading to all honest nodes |
### Test Suite: 22 tests, all passing | # | Test | N, f | Malicious | Behavior | Result | |---|------|------|-----------|----------|--------| | 1–3 | **Validity** | 4/1, 7/2, 10/3 | None | — | All honest deliver ✓ | | 4–6 | **Agreement** | 4/1, 7/2, 10/3 | f nodes | Silent | All honest deliver ✓ | | 7–12 | **Integrity** | 7/2 | 1 node | Silent | All honest ≤1 delivery ✓ | | 13 | **Equivocation** | 7/2 | f=2 nodes | Equivocate | All honest deliver ✓ | | 14 | **Malicious sender** | 4/1 | Sender | Silent | No honest delivers ✓ | | 15 | **Bad signature** | 4/1 | Sender | Bad sig | No honest delivers ✓ | | 16–19 | **Multiple msgs** | 4/1 | None | — | All deliver both ✓ | | 20 | **Quorum intersection** | 7/2 | — | — | Intersection=f+1=3 ✓ | | 21 | **Max f malicious** | 7/2 | f=2 | Silent | All honest deliver ✓ | | 22 | **Mixed equivocate** | 10/3 | f=3 | Equivocate | All honest deliver ✓ | ### Edge Cases Verified - **Quorum intersection proof**: With N=3f+1, any two sets of size 2f+1 intersect in at least f+1 nodes. Test 20 numerically verifies this. - **f+1 amplification**: If only one honest node sees 2f+1 ECHOs, its READY propagates because others need only f+1 READYs to also send READY. - **Concurrent broadcasts**: Multiple messages from the same sender are tracked independently by digest (which includes a sequence number). - **Malicious sender collusion**: f malicious nodes cannot prevent honest nodes from delivering, nor can they cause delivery of a message the honest sender never sent. - **No double-delivery**: The `delivered` set prevents delivering the same message digest twice (integrity). ---
{"model": "claude-sonnet-4", "problem_class": "byzantine-broadcast-protocol", "result": "passed", "tests": 22}