(A formal proof of the security of our pruning protocol can be found here, the purpose of the current post is to provide an intuitive exposition)
Finality is the practice of not allowing reorgs below some fixed depth, pruning is the practice of removing unnecessary block data. The two are strongly coupled: blocks which weren’t finalized may not be pruned. On the other hand, it is not generally true that finalized blocks may be pruned, as the data they contain might be needed to compute the UTXO set of incoming blocks.
More concretely, a pruning block P is a block with the property that any blocks which affect the UTXO set of the virtual block are in its future. Differently put, if when B was discovered it was not in P.Future, then at no point in time will B be in Virtual.Past.
In order to make things meaningful in the context of consensus, we apply the usual trick: we define the pruning block P of a block B, B.P, and then define “the” pruning block to be P=Virtual.P. The way we do this is straightforward: we set a pruning parameter \pi, and then define B.P to be the “block at depth \pi from B ”, that is, B.P is the most recent block in the selected chain of B such that B.BlueScore - B.P.BlueScore > \pi.
We similarly define a finality parameter \phi < \pi, and define B.F to be the block at depth \phi, and in particular “the” finality block is F=Virtual.F. The finality rule becomes very straightforward: any block whose inclusion would cause a reorg after which F is not in the selected chain is considered a finality breaking block. The handling of such a scenario is to alert the community while halting approval of any and all transactions until the community manually resolves the conflict. From the point of view of designing a pruning algorithm, we may assume that this never happens.
Our goal is to design a pruning algorithm which is resistant to pruning attacks. A pruning attack is a scenario where an adversary manages to force the network to require the data of an already pruned block. In particular, of a block outside P.Future. Since P is guaranteed to be in the selected chain by our definitions, and since \phi<\pi, the only way to achieve this is to force the network to require the data of a block in P.Anticone.
Note that no approach can deterministically prevent this scenario. For any block B, a 51% attack can easily make it so that B would be in Virtual.Past at some point, and it follows that any attacker could achieve this feat with positive probability. Our best possible approach is to design the mechanism such that the probability of success decays exponentially fast as a function of the pruning parameter \pi. This kind of “compromise” is not unique to our protocol, and is ubiquitous to any kind of security which relies on PoW.
Our design approach employs the apparatus of invalidation rules. We set some criteria for when a block is considered invalid, and require that the virtual block is always valid, with the hopes that the rules imply that a pruning attack is impossible for a 49% attacker (or more accurately, that the probability of ever carrying such an attack diminishes exponentially with \pi for any \alpha attacker where \alpha < 1/2 is fixed). Such rules must be in consensus, in the sense that one could read from the structure of the graph (and no other external data such as clocks and time signatures) whether a block is valid. This requirement is utterly crucial, since invalidating blocks with respect to inconsistent data will almost certainly lead to some splitting attack in which some blocks are considered invalid by some honest nodes, but are required to calculate the UTXO sets of some other honest nodes.
The first invalidation rule is self evident: if a block is invalid then so is any block pointing to it. Since we discard such blocks, we can’t trust blocks which point at them as the data is unavailable.
Note a crucial subtlety: we do not require that Virtual.Past will not include any blocks in P.Anticone. Such a requirement is far too strong and there are many legitimate scenarios in which it is infringed, even when the network is completely honest (in particular, if P'\in P.Anticone and P,P'\in Virtual.Past then P' will be in the past of any block pointing having the same parents as Virtual). Our requirement has to do with the time the node learned of B. By appealing to time we are actually breaking the consensus: network delay and network topology makes it so different nodes learn of blocks in different orders, making it possible that B violates this condition for one node but not for the other. This makes it impossible to simply require that “blocks which were in P.Anticone when they arrived are invalid”, since this is not a consensus rule.
The solution is to design the system in such a way that even if a block is only accepted by some of the nodes, its data will never actually be required. Intuitively, such blocks diverge from the selected chain in a very deep point: either P itself or a block very close to P (in particular, a block which was created at most twice the roundtrip time of a block since P was discovered by an honest node). This could be used to enforce the policy that such blocks are not needed, but designing a set of rules which achieves this is quite delicate.
The high-level idea of the pruning mechanism is to force any attacker who wishes to perform such an attack, in which the node requires data from a block which was in P.Anticone at the time it was discovered, into a block race. That is, making such an attack possible only if the attacker is able to create blocks at a higher rate than the honest network. We introduce how this is achieved from the bottom up.
The first thing one might try is to invalidate any block B which directly points at a block in B.P.Anticone. This is a good start, but also obviously not sufficient, as it could be easily sidestepped by using an “intermediate” block C which points to a block in P.Anticone and is also a parent of B.
A next reasonable step is to say “OK, so we invalidate B if it has a block P’ in P.Anticone in its past, and there is no block in B.Blueset with P’ in its past. Still, no dice. An attacker can overcome this by having the intermediate block C also point to a block close enough to B so that C be in B.Blueset, but P’ not in C.P.Anticone. It might not be possible to create such a C, but in that case we could just “add more steps”, that is, create C in B.Blueset and C’ in C.Blueset such that P’ is not in C’.P.Anticone. If this is also not possible, we can add yet another step. The overall number of steps we will require is bound by a low constant (up to negligible probability), making a pruning attack feasible.
What we need to do is to somehow verify that the block D in B.Past which is also in B.P.Anticone is not recent, and that it was in the graph long before B. We can’t rely on timestamps to do so. What we can do, is to rely on the protocol. In particular, if D has been known for a while, then there should be honest blocks which know of it. In particular, there should be a block C in B.Blueset such that B.F is in C.SelectedChain (ensuring C is much newer than B.P) and D is in C.Past. We call such a block C a “kosherizing” block. It is a block which is on one hand reliable, and on the other hand familiar with D.
Note that there are two possibilities for C: if D is not in C.P.Anticone, then (assuming C was discovered before B, an assumption we revisit later) D could not have been in P.Anticone when it was discovered. Otherwise, C must also admit a kosherizing block, or it is invalid, and the argument continues inductively.
This leads us to our second invalidation rule: a block B is invalid if there is a block D in B.Past which is in B.P.Anticone, for which there is no kosherizing block.
Are these two rules sufficient to prevent a pruning attack? Not quite, but we are getting there. The problem is that an adversary could still carry out what we call a “climbing attack”. In this attack the adversary first creates a block K which points both to D and to the finality block F. This block will act as a kosherizing block. It then creates a succession of blocks, the first one, K_1, pointing at K, and at the highest block it can on the selected chain such that K remains in its blue set. The next block, K_2, will point to K_1 and the highest chain block it can point to while keeping K_2 in its selected chain, etc., until creating a block high enough that it remains blue while pointing to it and to the current tip. The amount of blocks needed to create this attack is constant, about f/k.
The solution to this problem is to impose a “bounded merge” rule. Recall that the merge set of a block B is defined to be the set of blocks in B.Past which are neither B.SelectedParent nor in B.SelectedParent.Past. The third consensus rule limits the size of this set. That is, we fix some parameter L and impose the rule that a block may not have a merge set of size more than L. We will say something about how L should be chosen in a moment, but for now let us consider the implication of this rule.
Remember that the entire goal of the attack is to make it so that a block which was in P.Anticone while it was discovered will never be in Virtual.past. The attacker has the freedom to choose a chain block P’, create a block in P’.Anticone, and withhold it until P’ is the pruning block. All blocks created up to that point must be withheld.
Let us first consider an attacker which is restricted to a premining attack. That is, the attack mines some blocks on the side, and then releases them all at once and does not create any more blocks. If the attack was successful, this implies that all the blocks created by the attacker are in the merge set of the new virtual block, and in particular, there are at most L of them. This implies at once that choosing L<f/k makes such attacks impossible.
The attacker of course is not bound to this restriction, and may create blocks after the premined blocks were created, in the hope of kosherizing one of the bad blocks further down the line. Now here is the crux: after being published, the honest network will not point at any of the bad blocks, as it will consider all of them red and in particular pointing at them means including in their past a block in P.Anticone with no kosherizing block. The attacker, on the other hand, can not extend the attack to beyond while pointing at chain blocks, since the chain block would be their selected parent, which will make their merge set larger than L. The upshot of all of this is that after publishing the attacker can only make up to L blocks, each of which climbing at most k blocks up the selected chain (as it has to consider the top bad block blue), after which they can not have an honest block be their selected parent. In other words, they are in a block race against the network. At this point the security proof of PHANTOM shows that a <50% attacker will almost certainly lose this race.
Of course, this argument seems only relevant to a particular attack vector, but it is provable that any successful attack must create such a succession (so, in particular, this is the optimal attack).
So, in summary, the three invalidation rules are that a block B is considered invalid if:
- B has an invalid parent,
- B.Mergeset is larger than L, or
- There is a block C which is both in B.Past and B.P.Anticone such that it has no kosherizing block, where a kosherizing block is a block D in B.Blueset such that B.F is in D.SelectedChain, and such that C is in D.Past
The security follows by a theorem (proven by Sutton and myself): under these invalidation rules, and under the assumption that the virtual block must be valid, if the following hold:
- There is never a reorg of depth more than \phi, and
- There is an honest majority,
then if C was in P.Anticone when it was discovered, then the probability that at some point in the future C would be in Virtual.Past is exponentially small in p.