Byzantine nodes in the wild.

Introduction

So I wasn't interested in confirming that flat Tendermint chokes at 1000 nodes. Of course it does. And running it just to watch it die isn't a finding. What I actually wanted to know is whether you can keep what makes Tendermint worth using in the first place without paying the quadratic tax across the whole network.

The Raft simulation gave me the crash-fault baseline, and an earlier draft of this page worked out the 3f+1 bound on a four-node cluster small enough to reason about by hand. Neither of those goes away here, they just move somewhere else in the design. What's new is the layer on top, a two-tier hierarchy, benchmarked head to head against the flat protocol it's meant to replace, same node count, same fault budget.

You don't scale a quadratic protocol. You hide it inside something smaller.

The 3f+1

A commander and two lieutenants, one of them a traitor, talking through messengers with unsigned messages. Say the commander is the traitor and tells L1 to attack, L2 to retreat. L2 is loyal and passes along what it heard. Now compare that to a world where the commander is loyal and tells both to attack, but L2 is the traitor and lies to L1 about it. From L1's side, the two messages it gets look identical either way, yet it's supposed to attack in one world and not the other. There's no rule that can tell those cases apart from the inside. That's the core problem: not enough information, not a fixable vote-counting bug.

Generalize that and you get

N ≥ 3f + 1

N = total nodes
f = Byzantine nodes tolerated

So tolerating one traitor takes four nodes, not three. This isn't a rule of thumb, it's a proven lower bound. The usual explanation, "honest nodes outvote liars," isn't really why it works. The real reason is quorum intersection: a quorum is 2f+1 nodes, and any two quorums out of 3f+1 total overlap in at least f+1 nodes, which guarantees at least one honest node sits in both. That node won't sign two conflicting values, so two conflicting decisions can never both get a quorum. One caveat: this all assumes unsigned messages. Sign everything, as real BFT systems do, and a traitor can't misquote someone else without getting caught.

None of that changes at scale, it just applies twice: once inside each shard, and again at the top tier over the shards themselves. Tendermint runs at both levels not for speed, its O(n²) cost is the whole reason this piece exists, but because that cost is trivial at shard sizes of 4 to 10. The trick is just never letting one Tendermint instance see more than a handful of nodes at once.

The protocol, shard-and-aggregate

Technically nothing novel here, it's more a new arrangement of an old one, in the spirit of Elastico and SCP-style committee sharding. 1000 nodes get split into shards of a fixed, configurable size, starting at 4 (same f=1 bound the old four-node cluster used, so the earlier math carries over unchanged). Each shard runs its own independent Tendermint instance to agree on that shard's value for the round, and that inner instance has no idea it's part of anything bigger.

The messenger is not a leader

Each shard elects a messenger. I'm deliberately avoiding the word "leader" for it, since it doesn't do what a consensus leader does, no proposing, no voting, zero influence over what its shard decides. Its only job is carrying the shard's already-finalized output up to the top tier, after the shard has already committed. That naming isn't just pedantry, conflating the messenger with the top-tier proposer is exactly how you'd end up trusting one node's word for what an entire shard did.

Which matters because the messenger's word alone isn't trusted anyway. It carries a threshold-signed certificate, cryptographic proof that at least 2f_s+1 nodes in the shard actually signed the value being reported. The top tier checks that certificate itself instead of taking the messenger's claim at face value.

At any given time there are roughly 1000 / shard_size messengers, and together they make up the top tier, which runs Tendermint again, this time over certified shard values, to land on one global decision for the round.

Reshuffling, on a schedule

Shard membership isn't fixed. Every K rounds, a re-sharding step reassigns nodes using a deterministic, verifiable reshuffle seeded by the previous round's committed value, so no single node controls it. The reason this exists, an adaptive adversary that quietly seeds Byzantine nodes into one shard over many rounds, waiting to cross that shard's f bound, is a real threat, and a static assignment does nothing about it.

I want to be clear about what reshuffling isn't, though, it's not a safety guarantee, it's a mitigation, and those are different things. If more than f_s nodes inside one shard turn out Byzantine in coordination, that shard can produce a perfectly valid certificate (2f_s+1 real signatures) behind a value it never should have agreed to, because "should" assumes an honest majority the shard no longer has. The top tier's verification isn't broken here, the signatures are genuinely real, it's just the same boundary problem flat BFT has when you cross f, moved down one level. A shard is only as safe as the global Byzantine ratio and however unlucky that particular draw happened to be. Reshuffling limits how long an adversary can sit still trying to engineer that draw. It doesn't make any one shard, at any one moment, actually safe.

Onto machines

Physical topology

The 1000 nodes run as processes on eight hosts, two per Availability Zone, about 125 each. Placement is the part that matters: a shard's four members go on four different hosts in four different AZs. Colocate two of them and one dead host costs you 2 of 4, past f, which is a fault the protocol never claimed to survive. One member per AZ gets that for free. The messenger is whichever member got elected that round, so the highlight moves between hosts.

What it lies about

Two processes on the same box talk over loopback in microseconds, which no real link matches, so every pair gets a netem profile, same-host ones included. Shaping doesn't fix CPU, though: 125 consensus processes contending for cores show up in the tail, so the absolute latencies here aren't production numbers. Fine, they were never the point. Flat and hierarchical run on the same hosts with only the topology changing, and the ratio is what I'm after.

Data and control plane

The data plane is consensus: shard gossip, the messenger's certificate, then top-tier Tendermint over those certificates. The control plane is one coordinator on a host that runs no nodes. It ticks the reshuffle every K rounds, seeded by the last committed value so nobody controls the draw, keeps the assignment table, and pushes the link profiles.

Results

Three sweeps. The first two run flat and hierarchical side by side over the same node counts, 50 to 1000, same link profiles, same hosts, shard size fixed at 4. The third drops flat entirely and asks the only question that matters once you've decided to shard: what does splitting the network do to the fault bound you started with.

[1] Message load

Does hierarchy actually beat the quadratic, or just move it?

1. Messages per round vs node count

Count every consensus message that crosses the wire in one committed round, both tiers included, and plot it against N on log axes. A quadratic protocol is a straight line of slope 2 here. The question is whether the yellow line bends.

• It doesn't bend. Both lines are straight and, past N=100, parallel. Hierarchy did not change the exponent, both tiers are still O(n²), so the total is still O(n²).
• What it changed is the constant. At N=1000, flat sits at roughly 2M messages per round, hierarchical at roughly 130K. About 15x, and 15x is not an accident: it's the s²=16 you'd predict from shrinking the quadratic tier's population by the shard size.
• Break the yellow number apart and the top tier is nearly all of it. 250 shards of 4 cost about 8K messages of intra-shard gossip combined; the 250 messengers running Tendermint over each other cost about 125K. Roughly 94% of the hierarchical cost is the top tier. The shards are free.
• The gap widens on the left before it stabilizes, about 7x at N=50, 15x by N=1000. Small networks don't have enough nodes for the division to pay off.

The honest reading is that this buys a constant factor, not an asymptote. Which is fine, that was always the deal, but it means the top tier is the thing that eventually breaks, and 250 messengers gossiping quadratically is not a structure that survives another decade of N. The fix isn't a better protocol, it's a third tier, or a bigger shard size. Total cost is about 2(N/s)² + 2Ns, minimized near s = N^(1/3), which for 1000 nodes is 10, not 4.

[2] Throughput

Messages are a proxy. Does the message saving show up as committed rounds per second, and at what size does it start to?

1. Rounds per second vs node count

Same sweep, now measuring what the network actually finishes: committed rounds per second, steady state, no faults injected.

• Flat wins at small N. At 50 nodes flat commits about 210 rounds/sec against hierarchy's 130. Sharding a network this small is a 40% throughput loss for nothing.
• The crossover is somewhere around 150 to 200 nodes. Below it, hierarchy is strictly worse. That's the number worth remembering, because it's the one you'd get wrong by reasoning from the message graph alone.
• At N=1000 the order is reversed and the margin is large: about 12.5 rounds/sec hierarchical against 2.7 flat, a bit over 4.5x.
• The slopes differ more than the endpoints do. Over the 20x span of N, flat drops about 78x while hierarchical drops about 10x. Flat degrades faster than linearly in N; hierarchical degrades sublinearly.

The crossover is the real result here, and it's a latency story, not a bandwidth one. Hierarchy adds a second sequential consensus stage, the shard has to commit and certify before the top tier can even start, so you pay a full extra round of critical path on every round. At 50 nodes that fixed cost dominates and quadratic gossip is cheap enough that nobody notices it. At 1000 nodes the extra stage is noise and the gossip is everything. Hierarchy is a cost you pre-pay and only recover past a threshold, and if you're running under 150 nodes you should not be reading this article for architecture advice.

[3] Where the fault bound went

A global 3f+1 says a third of the network can be Byzantine. Sharding replaces that with one 3f_s+1 per shard. How much weaker is that?

1. Shards past their own f vs fault ratio

250 nodes, 62 shards of 4, so f_s = 1 and a shard is compromised the moment 2 of its 4 members are Byzantine. Sweep the global fraction of Byzantine nodes from 0 to 0.35 and count how many shards end up over their own budget after assignment.

• The safe region is tiny. Zero shards over budget only holds to about 0.05. A flat network at a 5% fault ratio is nowhere near trouble; this one is one bad draw away from it.
• At a 10% fault ratio, 2 shards are already compromised. At 20%, 7. At 30%, 25. At 0.35, 28 of 62, 45% of all shards, and that's a fault ratio a flat network of the same size tolerates outright.
• The curve is just the binomial tail. A shard of 4 fails when 2 or more of its members are faulty, so the expected count is 62 · P(X ≥ 2) for X ~ Bin(4, p), which predicts 3.2 / 6.8 / 11 / 21.6 against the measured 2 / 6 / 7 / 25 at p = 0.10 / 0.15 / 0.20 / 0.30. It tracks. Nothing here is an implementation artifact, it's the arithmetic of small samples.
• The elbow between 0.20 and 0.25, 7 jumping to 18, is sharper than the binomial predicts smoothly. That's a single draw per point, not an average over many, so treat the shape as noisy and the trend as real.

This is the bill for the constant factor in [1]. A compromised shard doesn't degrade, it produces a valid certificate, 2f_s+1 genuine signatures behind a value the shard should never have agreed to, and the top tier has no way to tell that apart from an honest one, because checking the signatures is the whole verification. So the count on this chart isn't a performance number, it's a count of safety violations, and one is enough. The system's real bound is not N ≥ 3f+1, it's 3f_s+1 holding in every shard simultaneously, which at shard size 4 is a drastically stronger requirement than the one you thought you were buying. Reshuffling doesn't fix this, it only bounds how long any single bad draw persists. Shard size does: at s=10, f_s=3, a shard needs 4 of 10 to fail, and the same 20% fault ratio drops the per-shard failure probability from 0.18 to 0.12 while the binomial concentrates harder as s grows. The same s=10 that [1] says is message-optimal at 1000 nodes.

Conclusion

Hierarchy buys back roughly 15x on messages and 4.5x on throughput at 1000 nodes, and it costs a fault bound that used to be global and is now 62 independent local bets, all of which have to win. Both halves of that are consequences of the same choice, shrinking the quadratic tier's population, and neither shows up if you only measure one of them.

Shard size 4 was the wrong pick on both counts. It came from wanting the earlier four-node f=1 math to carry over unchanged, which was a reason to start there, not a reason to stay. The message model and the fault model independently point at 10 for a network this size. The next run is that sweep.

And the crossover at ~150 nodes deserves more respect than it usually gets. Most networks are smaller than that. For them the correct answer is the boring one: run it flat.