While nodes may be required to re-process all sortitions due to a late-arriving anchor block, nodes do not need to do so eagerly if the anchor block is not part of the canonical Stacks chain. Put another way, if nodes could determine whether or not an anchor block is part of the canonical chain without needing to process any Stacks blocks, then they would not need to reprocess their chainstates if a late-arriving anchor block would not change which Stacks fork was the canonical Stacks chain. The ability to ignore late non-canonical anchor blocks would make the network resilient to the havoc that could be wrecked by naively processing all Stacks blocks as they arrive: if an anchor block is missing for more than one reward cycle, the miners could build a canonical Stacks chain that does not include the missing anchor block in the first place. Nodes that bootstrap after the missing anchor block is rendered non-canonical would not need to process it should it arrive later, since processing it won't help them determine the canonical Stacks chain in the first place.
So, how might nodes determine in advance which anchor blocks to download and which to ignore, without processing any Stacks blocks?
The fact that all prepare-phase block commits use proof-of-burn means that all nodes can process prepare-phase sortitions without needing to have processed any Stacks blocks. This means that if a node can only see the block-commits, it can still determine (1) whether or not a reward cycle chose an anchor block, and (2) whether or not a prepare phase sortition descends from a PoX block commit or a PoB block commit. As described in the following paragraphs, this information is sufficient to determine whether or not the anchor block is part of the canonical Stacks chain.
To see how, we first observe that the act of winning a block is implicitly the act of affirming that a particular subset of anchor blocks were known to the miner -- this block affirms that all anchor blocks that are its ancestors existed on the targeted Stacks chain tip at the time. Similarly, mining a descendant of a PoB ancestor in a PoX reward cycle implicitly affirms that the reward cycle's anchor block was unknown to target chain tip's miners (or at least, the majority of the network did not affirm it, and produced a better chain without it). To capture this, let a sortition's affirmation map be an array AM defined as follows.
For the ith reward cycle:
- AM[i] = 1 if reward cycle i selected an anchor block, and there exists a block-commit in i that descends from the anchor block and is also an ancestor of this sortition. AM[i] == 1 means "this block's miner claims to have known that the anchor block for reward cycle i exists in the canonical chain."
- AM[i] = -1 if reward cycle i selected an anchor block, but there exists a block-commit in i that does not descend from the anchor block and is also an ancestor of this sortition. AM[i] == -1 means "this block's miner denied that the anchor block for reward cycle i exists in the canonical chain."
- AM[i] = 0 otherwise -- i.e. if this sortition has no ancestors in reward cycle i. AM[i] == 0 means "this block's miner has no opinion about the existence of the anchor block for reward cycle i."
Each sortition's AM has a length equal to the number of complete reward cycles that have passed up to this sortition. Note that due to the nature of PoX, a node may not know all sortitions' affirmation maps -- it can only calculate it once the sortition is processed.
Because all prepare-phase block-commits are guaranteed to be proof-of-burn, a node will be able to determine the affirmation maps of each prepare phase sortition. Moreover, when processing all sortitions in the prepare phase, a node can determine whether or not a threshold of prepare-phase sortitions have the same affirmation map. We use this property to determine how "heavy" a given affirmation map is, in order to measure how much cumulative mining effort has gone into a particular affirmation map. The "heaviest" affirmation map will be used to decide which anchor blocks to download, and which to ignore.
To do this, let the burnchain's affirmation vote be an array AV of affirmation maps defined as follows:
For the ith reward cycle:
- AV[i] is the affirmation map of reward cycle i that received a majority of the prepare-phase votes, if one exists.
- AV[i] = [] otherwise
Note that just because a majority of the prepare phases' sortitions have the same AM does not mean that the sortitions chose an anchor block. Two sortitions can have the same AM[i] values but build off of different, conflicting ancestors.
Then, define weight(AM) to be a function calculated recursively as follows:
- If AM = [], then weight(AM) = 0
- Otherwise, weight(AM[0..i]) =
- 1 + weight(AM[0..i-1]) if AM[0..i-1] == AV[i-1]
- weight(AM[0..i-1]) otherwise
The canonical affirmation map CM, which determines which anchor blocks should be downloaded or ignored, is the affirmation map known by the node to have the highest weight() value. If there is a tie, then the affirmation map with that has the lowest j such that AV[j] == AM[0..j] and AV[j+1] != AM[0..j+1] is the winner (i.e. the affirmation map that is longest-known to the network breaks ties).
The value weight(AM) is maximized by choosing AM such that it has the most prefixes {A[0..i-k] | 0 <= k < i} present in the set {AV[k] | 0 <= k < i}, for a given reward cycle i. Choosing i to be equal to the number of reward cycles that exist, then the canonical affirmation map CM is the affirmation map that has received the most confirmations by all prepare-phases on the burnchain so far.
By design, it is increasingly difficult to change a given CM[i] for for smaller values of i. In order to change CM[i-k], over 50% of the mining power must confirm a new CM' at least k more times than CM, where CM'[i-k] != CM[i-k]. This in turn requires over 50% mining support during at least k prepare prepare phases after i -- at least i+1 through i+k, inclusive.
Insofar as dealing with hidden anchor blocks, if a malicious mining coalition succeeded in mining a hidden anchor block in reward cycle i, they would need to keep confirming it in a majority of the subsequent prepare-phases in perpetuity. This is because keeping a hidden anchor block on the canonical affirmation map requires out-mining anyone who would want to vote for an alternative affirmation map that sets the hidden anchor block status to 0. If the attacker cannot do so, then eventually, the rest of the network will build off the Stacks blocks they do possess, and vote for affirmation maps that have the hidden anchor block set to 0. Once the canonical affirmation map declares that the hidden anchor block is missing, then the hidden anchor block's subsequent arrival will not trigger a chain reorganization -- nodes will simply ignore it and pretend that it does not exist.
The canonical affirmation map is only a hint. It is possible for a malicious majority to confirm an affirmation map that corresponds to invalid block-commits, such as PoX block-commits that pay to the wrong addresses or block-commits that were not chosen as a sortition winner. The risk of this happening is mitigated by the fact that we can assume that the majority of mining power is honest and well-connected most of the time, and will either confirm a canonical affirmation map that truly corresponds to valid Stacks chain state once any malicious attack subsides, or prevent an invalid affirmation map from being confirmed.
The formulation of the affirmation map is not consensus-critical, and should not be consensus critical. In general, nodes may decide on their own which Stacks blocks they believe exist and which they believe are lost -- something that is true of all forkable blockchains. However, it is strongly advised that all Stacks nodes follow the same affirmation map formulation; nodes that follow different formulations are unlikely to decide on the same canonical Stacks chain. It is also strongly advised that any attempt to upgrade the affirmation map formulation once mainnet launches happens through a soft fork. Because the canonical affirmation map formulation is only a hint, it is likely that better formulations will be discovered and deployed in the future as the network gains real-world experience with the Stacks chain.
The existence of a canonical affirmation map does not preclude a malicious majority from mining a hidden anchor block, and then releasing it at least one reward cycle later to trigger a deep chain reorganization. The canonical affirmation map formulation only makes it so that any such attacker must obtain majority mining power for O(k) reward cycle prepare phases in order to execute a k-reward-cycle-deep reorganization. Note that the cost of obtaining majority mining power to mine a hidden anchor block, and then do so repeatedly to continuously confirm it in subsequent prepare phases, is cheaper in expectation than obtaining over 50% of the chain's entire mining power.
Once a node has downloaded and processed all prepare phases and block-commits, it can determine the canonical affirmation map. From there, it proceeds to download Stacks blocks from the peer network, according to the following rules:
-
If CM[i] == 1, and an anchor block was chosen for reward cycle i, the node will attempt to download the anchor block. Otherwise, it will not download it, and will not accept it if the block is pushed to it.
-
If CM[i] == 1, and the anchor block downloaded was invalid, unavailable after a timeout, or corresponded to a block-commit that was not the winning sortition, then the node finds the heaviest valid alternative affirmation map CM' where CM'[0..i] = CM[0..i] and CM'[i] != 1. Once it has done so, it resumes downloading blocks using CM' instead.
The canonical Stacks chain will be the longest Stacks chain fork that can be built using the canonical affirmation map.
Since it is an affirmation map, CM increases in length with each additional reward cycle. Let CM' be the next canonical affirmation map after CM, where len(CM) + 1 = len(CM'). If there exists some i such that CM[i] != CM'[i] and i < len(CM), then all nodes will need to reorganize their chainstate by re-processing all sortitions from the start of reward cycle i onward.
Should it be necessary to reorganize the Stacks chain for at least one reward cycle, all network participants will be able to see the reorganization coming. They can do so by watching prepare-phase sortitions as they occur, and determine whether or not the reorg condition above is imminent. Because prepare-phases last for 100 Bitcoin blocks (about 16 hours, 40 minutes), and because a reorg condition can only take place if the new CM' has a strictly higher weight() than CM, the network has time equal to two prepare phases and one reward cycle (about 15 days) to brace for the attack and employ whatever mitigations they deem necessary to deal with downstream consequences. They can, for example, spend 2 weeks acquiring more Bitcoin so they can increase the honest miners' burn rates in the reward cycle that could cause CM' to trigger a reorg, and in doing so, prevent it.
-
A prepare-phase can confirm an affirmation map with a majority vote, not an 80% vote. What this means is that while it's easy to recover from a hidden anchor block (you only need 51%), it also means that once a hidden anchor block is mined, the attacker only needs 51%. I consider this trade-off acceptable, because raising the confirmation threshold above 51% for an affirmation map is the same as lowering the attacker threshold to preserve a canonical affirmation map that contains the hidden anchor block. What do you think?
-
Should this be its own SIP, or should it be part of SIP-007?
So, the above proposal cannot be implemented without a consensus-breaking change.