When Every Block Counts, Except the Ones That Don’t
What the mathematics of bounded-anticone certification says about the blockDAG protocols — and why the problem is in the specification, not the code
The pitch for blockDAG protocols is easy to like. Nakamoto consensus throws work away. When two miners find blocks at nearly the same time, one block wins the fork race and the other becomes an orphan: its work is discarded, its transactions are set aside, its author is unpaid. The wider the network and the faster the block rate, the more often this happens, and the more the system spends its security budget on work it then deletes. BlockDAG protocols — PHANTOM, GHOSTDAG, and the parameterless DAGKnight that followed them — promise to fix exactly this. Keep every block. Let the structure branch. Instead of choosing one path and orphaning the rest, order the whole directed acyclic graph and let every honest block find its place in the sequence. Nothing is wasted; everyone is paid; throughput rises.
This essay is about a gap between that promise and what the underlying mechanism actually guarantees. The gap is not a bug in any implementation. It is a property of the rule these protocols are instances of, and it survives every attempt to implement that rule better. I want to set it out carefully, because the conclusion is uncomfortable and the temptation to wave it away is strong. The claim is not that blockDAGs are broken, or that the protocols do not work, or that their authors made an error of arithmetic. The claim is narrower and harder to escape: the specific device by which these protocols decide which blocks “count” — a local density condition on the set of accepted blocks — has consequences that no choice of algorithm can remove, and several of those consequences run directly against the promise that every honest block is honored.
A note on register before we begin. I am not a blockDAG partisan, and this is not a takedown either. The most useful thing one can do with a family of protocols that has attracted real deployment and real money is to state precisely what its central mechanism does and does not deliver, in terms that do not depend on trusting anyone’s summary — including mine. Everything below reduces to counting arguments about graphs. Where a claim needs a probabilistic assumption, I will say so and name the assumption; where it does not, the claim holds outright. That distinction turns out to matter a great deal, because most of what is troubling here needs no probability at all.
The mechanism, stated plainly
Strip away the protocol-specific machinery and a blockDAG ordering rule does two things. It reads the local graph of blocks — who named whom at creation — and from that graph alone it produces two outputs: a total order on all the blocks, and a distinguished subset it certifies. The certified set is the part of the graph the protocol treats as having been produced in conformance with the rules. In deployed systems, membership in the certified set is what governs reward, and what determines the weight a block lends to the blocks built on top of it. A block that fails to be certified is not deleted — it keeps its slot in the order — but it is demoted: it does not count in the ways that matter.
The condition that decides certification is the heart of the matter. Every proposed rule in this family certifies a set with a bounded-anticone property. The anticone of a block is the set of blocks that neither reach it nor are reached from it — the blocks whose order relative to it the graph simply does not settle, because they were created concurrently and named neither the block nor anything downstream of it. A set of blocks is a k-cluster if every block in the set has at most k other members of the set in its anticone. Certify a k-cluster; that is the rule.
The intuition is reasonable, and I want to give it its due before dismantling it. An honest node, following the protocol, names every tip of its current view and broadcasts immediately. Its block is therefore named by everything created more than one network delay later, and it names everything created more than one delay earlier. The blocks concurrent with it — the ones in its anticone — are confined to a narrow window of about two network delays. A block that has been withheld, by contrast, fails to be named by everything created during the withholding, so its anticone swells with the duration of the concealment. Bounding the anticone is meant to admit the first kind of block and turn away the second. It is a test for concurrency-that-was-honest versus concurrency-that-was-manufactured.
The trouble is that the test cannot tell the two apart, that the price of fooling it is fixed and small, and that even when it is not fooled at all it discards honest work. Let me take these in turn.
First crack: the test cannot be exact
Consider two runs of the system, side by side. In the first, no node misbehaves; every block is delivered to every honest node within the delay bound; two blocks happen to be created within one delay of each other and are therefore concurrent, each unaware of the other at creation. In the second run, a single faulty node creates a block, gives it the same predecessors and the same contents as one of the honest blocks from the first run, and quietly withholds it for exactly one delay before releasing it.
Now ask what any honest node sees. In both runs, at every honest node other than the one that authored the block in the first run, the sequence of blocks that arrive, and the naming relationships among them, are identical. The two runs produce the same labelled graph. And since the ordering rule reads the graph and nothing else — it has no trustworthy clock, no authenticated creation time, no verified author identity, because timestamps are strings a faulty author writes at will — the rule returns the same answer in both runs. It certifies the same set and produces the same order.
The consequence is a dichotomy with no comfortable branch. If the rule certifies the withheld block in the second run, then it must also certify the honest block it is indistinguishable from — fine — but then it certifies withheld blocks in general, and the density condition was supposed to prevent exactly that. If instead the rule declines to certify the withheld block, then, because the two runs are the same graph, it also declines to certify the honest block in the first run, in which nobody misbehaved at all. There is no predicate computable from the graph that fires on exactly the faulty blocks, because “faulty” is a fact about history and the graph does not carry history. The question is never whether honest blocks get demoted. It is only how many.
This is worth pausing on, because it dissolves a natural hope. One might imagine that a cleverer certification rule — a better statistic, a smarter tie-break, a more discerning notion of which blocks “look honest” — could sort the sheep from the goats. It cannot, and the reason is not that the right statistic has yet to be found. It is that the information required to separate the two runs is not present in the object the rule is allowed to read. No amount of cleverness recovers information that was never there.
The veto, and its exact price
Now the mechanism turns from passive to active. Suppose k + 1 certified blocks sit in the anticone of some block z. Then z cannot be certified — not by this rule, not by any rule in the family. The reason is immediate from the definition: if z were certified, it would be a member of the certified set with k + 1 members of that set in its anticone, violating the k-cluster condition. The density condition, imposed to bound what an adversary can smuggle into the certified set, is simultaneously a lever: anyone holding k + 1 suitably placed certified blocks can veto the certification of any target they choose.
How many blocks does the veto cost? Exactly k + 1, and this is tight on both sides. With only k certified blocks in a target’s anticone, the target remains certifiable — one can exhibit a k-cluster containing it — so k never suffices. And a set of pairwise-incomparable certified blocks can have at most k + 1 members, so the vetoing set is as wide as any certified set is allowed to be. The number k + 1 is at once the smallest force that vetoes and the largest incomparable set that certifies. The attacker operates precisely at the ceiling the honest protocol sets for itself.
None of this depends on any assumption about network timing, block rates, or probability. It is a fact about a graph and a subset. And it applies to every rule that certifies a k-cluster, including the rule that certifies a largest possible k-cluster — the one that makes no approximation error at all. That last point is what forecloses the escape route of “well, real implementations are cleverer.” The results here are proved for the whole class of bounded-anticone rules at once, cardinality-optimal members included. There is no better member to retreat to.
It is worth making the tightness concrete, because “exactly k + 1” is the kind of phrase that slides past the eye. Take k = 1, the smallest interesting case. A single certified block in a target’s anticone leaves the target certifiable: one can write down a valid 1-cluster containing both. Add a second certified block to that anticone, incomparable to the first, and the target is finished — any set containing all three now has a block with two others in its anticone, one too many. The jump from certifiable to vetoed happens at the addition of a single block, and it happens at every value of k: the k-th block still leaves the door open, the (k + 1)-th closes it. There is no gradual erosion, no margin to tune, no safety factor to add. The mechanism is a cliff, and the attacker knows exactly where the edge is, because the edge is written into the definition of what the honest protocol will certify. A defender who raises k to make the cliff more expensive to reach simultaneously widens the anticone the honest set will tolerate — which is to say, weakens the very detection the condition was imposed to perform. The parameter is loaded against its own purpose from both directions at once.
The fan: one node, no waiting
Figure 1. A single faulty node creates k + 1 blocks (red) that all name a common ancestor a_L and name none of one another. The set passes the k-cluster test at its maximum admissible width. Every block of the honest target chain Z (blue) has all k + 1 fan blocks in its anticone, and so cannot be certified while the fan stands. The fan requires no withholding and no coordination: the blocks can be created and released together.
The veto would be less alarming if assembling k + 1 blocks in a target’s anticone were expensive or slow. It is neither. Figure 1 shows the cheapest possible construction — I will call it the fan. A single faulty node creates k + 1 blocks, each naming a common ancestor, and — this is the whole trick — each naming none of the others. Because a faulty node is under no obligation to name the tips it holds, nothing forces these blocks to reference one another, even though their author holds all of them. They are pairwise concurrent by construction. Released together, they land in the graph as k + 1 mutually-incomparable blocks, all sitting in the anticone of every block on the target chain that forks from the same ancestor.
Two things make the fan sharp. First, it passes the density test. The fan together with its trunk is itself a valid k-cluster — each fan block has exactly k others in its anticone, which is within bound — so certifying it is entirely consistent with the rule. The extreme violation of the honest naming discipline, k + 1 blocks each ignoring all the others, is exactly the configuration the density test waves through, at maximum width. Second, the fan requires no withholding. The witness construction that first suggested the veto needed k + 1 blocks created in sequence, each naming the last; the fan needs no sequence and no waiting. The blocks are minted in a single instant and released at once.
And the fan does not stop at one target. A single fan of k + 1 blocks vetoes every block on every chain that forks from its anchor. Point it at r separate honest chains of length N and it demotes rN honest blocks at a fixed cost of k + 1. The ratio of damage to cost grows without bound in the number of targets and in their length. In the machine-checked instances that accompany this analysis, a fan at k = 124 — a parameter in the range deployed systems have used — demotes just under twenty-four honest blocks for every block the attacker spends. There is no rate assumption anywhere in that statement. It is a count.
The result that should give one pause
Figure 2. Two maximum k-clusters of identical cardinality. The upper set P consists of the k + 1 witnesses (red) followed by a ballast chain (green); the lower set Q is the honest target chain (blue). Both fork from a_L, are mutually incomparable, and have exactly the same size 1 + L + N. A rule that certifies P — attaining the exact optimum — leaves every block of Q uncertified, and each of those blocks belongs to the equally-optimal Q. The loss is not an approximation error; it is a choice between two right answers.
Here is where the standard defenses stop working entirely. Faced with everything above, one might still say: the certified set may lose a few honest blocks at the margins, but a good rule certifies almost as many blocks as the largest possible certified set, so the loss is bounded and small; improve the optimization and you improve the outcome.
Figure 2 refutes this. It shows a graph carrying two maximum k-clusters — two certified sets, each of the largest possible size, of exactly equal cardinality. Their symmetric difference contains an entire honest chain of length N, and N is free: make it as large as you like. One optimum, the set P, consists of the k + 1 witnesses padded with ballast to the target size. The other, Q, is the honest target chain itself. Both are maximum. A rule that certifies P attains the optimum exactly — it makes no cardinality error whatsoever — and in doing so leaves every one of the N honest blocks of Q uncertified, each of which lies in the equally-optimal Q.
Read that again, because it is the crux. There is no approximation loss. There is no ground truth that makes either answer wrong. The rule is asked to choose between two right answers of identical size, and the honest chain is what it discards when it chooses the other. An approximation-ratio analysis — the natural instrument for a subset-selection problem — is simply the wrong tool, because it measures a quantity (size of the certified set) that is not where the loss lives. The loss lives in membership: which blocks, not how many. A rule that achieves ratio exactly one on every input can still throw an unbounded number of honest blocks overboard on this family, because the family carries two optima and the conclusion is symmetric between them.
The construction is not exotic and does not require an adversary to build the honest chain. Every block of the target chain can be created by a scrupulously honest node in an admissible run; the witnesses can be supplied by a faulty node whose blocks simply arrive later. The smallest instance fits in nine blocks and has been checked by hand and by machine.
It gets worse without an adversary
Everything so far involves a faulty node somewhere, if only to supply the witnesses. The next result removes even that.
Suppose the honest nodes are transiently split into two groups that cannot reach one another for a while — an ordinary network partition, the kind that happens without malice when a transatlantic link degrades or a data center is islanded. During the split, each side builds blocks; neither side names the other’s, because neither side can see the other’s. When the partition heals and the two sides’ blocks finally meet in a single view, they form two mutually-incomparable sets, each block of one side sitting in the anticone of every block of the other.
Now the exclusion arithmetic bites. If both sides produced more than k blocks during the split, then in any certified k-cluster, at least one side must have at least (its size − k) of its blocks left out. Not because anyone attacked anything — because the density condition cannot admit more than k blocks from each of two mutually-incomparable sets simultaneously. The honest work of one side is excluded by the honest work of the other, deterministically, with a bound that grows as the partition lengthens. No faulty node appears anywhere in this statement. The mechanism that was supposed to let every block count instead forces honest blocks to cancel each other whenever the network briefly fails to be a single connected whole — which is to say, under exactly the conditions a partition-tolerant system is meant to weather.
Two more properties, briefly
Two further facts round out the picture, and both cut against intuitions the “every block counts” framing invites.
First, certification is not monotone. One expects that learning more of the graph can only add to what one is willing to certify — that certification, like confirmation depth, only ever strengthens. It does not. A block certified in a smaller view can be un-certified when the view grows, because the arrival of a fan into a block’s anticone can push the count past k and evict a block that was previously fine. Adding information withdraws certification. Whatever else one wants from a ledger, this is an awkward property: a block can look settled and then unsettle itself as the graph fills in.
Second, demotion is not merely a label. In the natural rules that place uncertified blocks after the certified blocks they are concurrent with — a reasonable convention, since certification is meant to express precedence — the fan does not only strip the honest chain of certification. It shoves every honest block behind the k + 1 blocks that one faulty node minted in an instant. The honest author is not just unpaid; they are reordered behind the attacker. The device meant to prevent manufactured concurrency from jumping the queue lets it jump the queue.
Why none of this is fixable in the usual sense
The reflex, confronting a list like this, is to look for the implementation error. There is none to find, and the reason is structural. Every result above is proved for the entire class of rules defined by three conditions — the certified set is a k-cluster, the order respects reachability, and the rule reads the graph alone — and for nothing more specific. In particular, the class contains the rules that certify a largest possible k-cluster, which commit no approximation error at all. If a defect held only for some greedy heuristic, one could answer it with a better heuristic. These defects hold for the optimal members too. There is no better member of the class to escape to, because the defects are consequences of the defining conditions, not of any approximation to them.
That is the sense in which the problem is in the specification. The bounded-anticone condition is not a lossy approximation of some cleaner ideal that a future algorithm will realize. It is the ideal, in this family, and the ideal has these properties. To remove them one must change what “certified” means — abandon the k-cluster condition, or add to the rule some input it is currently forbidden (a trustworthy clock, an authenticated identity, a bound on concurrency supplied as a hypothesis rather than read from the graph). Each of those is a different protocol with different assumptions, and each must be analyzed on its own terms. What cannot be done is to keep the mechanism as specified and engineer the pathologies away.
What this does not say
Rigor cuts both ways, and an honest account has to mark its own limits, or it becomes the very advocacy it set out to examine.
None of the above shows that any deployed blockDAG network has suffered these failures, or that it will. The constructions are admissible in the model; whether the graphs that arise in practice tend toward them is an empirical question this analysis does not touch. Nor do the results say anything about agreement — whether honest nodes eventually converge on the same order. That is a separate property, genuinely independent of the density condition, and a blockDAG protocol may well establish it by a separate argument; the demotions described here happen whether or not the nodes agree, and if they agree, they agree on the demotion. The exclusion results are also silent about which side of a split loses its blocks; the statement is symmetric, and identifying the loser would require more than the mechanism provides.
And the probabilistic register, where most of the marketing lives, is deliberately quarantined here. The one place where a distribution enters — pricing how long it takes an attacker to accumulate k + 1 blocks, which follows a Gamma law under a Poisson model of block creation — is the only claim above that rests on such an assumption, and I have flagged it as such. Everything else is combinatorics: true in every admissible run, no matter how blocks arrive. That is precisely why it is hard to dismiss. One can argue about whether real block arrivals are Poisson. One cannot argue about whether k + 1 mutually-incomparable blocks in an anticone violate a k-cluster. They do, by definition, always.
The shape of the thing
Return to the promise. Nakamoto consensus wastes honest work, and the waste is visible and quantifiable: the orphan rate. BlockDAGs were built to end that waste by keeping every block and certifying the honest ones. What the mathematics of bounded-anticone certification shows is that the waste has not been abolished but relocated — from a visible orphan rate to an invisible demotion rate, one that no measure of certified-set size detects, that a single faulty node can drive up at fixed cost without waiting, and that a blameless network partition can produce with no faulty node at all. The honest blocks are no longer deleted. They are kept, and reordered behind the attacker’s, and not paid, and the accounting shows a full ledger the whole time.
That is not a reason to abandon the idea of ordering a graph instead of a chain. It is a reason to be exact about what the ordering device costs, and to stop describing bounded-anticone certification as though it delivers the thing its name suggests. Every block does count, in the trivial sense that every block stays in the order. Which blocks count in the sense that matters — reward, weight, precedence — is decided by a mechanism whose deepest properties, provable without a single probabilistic assumption, run against the promise. The right response to a protocol family this widely deployed is neither to cheer it nor to bury it, but to say precisely what it does. This is an attempt at that.
References
Sompolinsky, Y., & Zohar, A. (2018). PHANTOM, GHOSTDAG: Two Scalable BlockDAG Protocols. Cryptology ePrint Archive, Paper 2018/104. https://eprint.iacr.org/2018/104
Sompolinsky, Y., Wyborski, S., & Zohar, A. (2021). PHANTOM GHOSTDAG: A Scalable Generalization of Nakamoto Consensus. In Proceedings of the 3rd ACM Conference on Advances in Financial Technologies (AFT ‘21), pp. 57–70. Association for Computing Machinery. https://dl.acm.org/doi/10.1145/3479722.3480990
Sompolinsky, Y., & Sutton, M. (2022). The DAGKnight Protocol: A Parameterless Generalization of Nakamoto Consensus. Cryptology ePrint Archive, Paper 2022/1494. https://eprint.iacr.org/2022/1494
The constructions and counts in this essay are combinatorial and machine-checked; the verification enumerates every subset of each generated graph and tests the exclusion bound exhaustively, and it proves — rather than estimates — maximum-k-cluster optimality on the smaller instances. The two figures are drawn from the smallest and the canonical instances of the two constructions discussed. Where a claim rests on a probabilistic model of block creation, that is the only such claim, and it is marked in the text; every other statement holds in every admissible run.