I was thinking about the consensus rules for picking which block to mine on.
They are basically
A) Mine on the valid chain tip with the greatest POW
B) Break ties for the earliest block received
This is not a strict Nash equilibrium. If most other miners are using this strategy, there is no incentive to break ties correctly.
This means that it is potentially weakly unstable. Since ties happen rarely, it is not that big a deal to just follow the rule in those cases.
Miners don't lose out by following the above strategy so they might as well leave the code as the default rule.
I will only consider the minting fee for this analysis. Breaking ties based on transaction fees is another can of worms. It might be worth it for a miner to break ties in favor of the block that has the fewest transactions, since that leaves more transaction fees "on the table".
I will only consider the top-2 mining locations.
Case 1: Single Chain
Before:
<- A <- B <- C
Build on B:
<- A <- B <- C
.........\
..........`- X
Build on C:
<- A <- B <- C <- X
The miner is assumed to either build on B or C. The miner's block is X.
If the miner builds on B and finds the next block, then they will end up in a tie with C. Most of the other miners will have seen C already, so by rule B, they will build on C. This means that the miner's block is orphaned and they lose the block reward.
If the miner builds on C and finds the next block, then by rule A), most of the other miners will build on their block. This means that they get the block reward.
Build on B: 0
Build on C: +Mint
Best: Build on C
Rule: Build on C
Result: correct incentives
Case 2: Single Chain - miner owns previous
Before:
<- A <- X <- C
Build on B:
<- A <- X <- C
.........\
..........`- Y
Build on C:
<- A <- X <- C <- Y
The miner is assumed to either build on X or C. The miner's block is X and his new block is Y.
If the miner builds on X and finds the next block, then they will end up in a tie with C. Most of the other miners will have seen C already, so by rule B, they will build on C. This means that the miner's new block is orphaned and they lose the extra block reward.
If the miner builds on C and finds the next block, then by rule A), most of the other miners will build on their block. This means that they get both of their block rewards.
Build on X: +Mint
Build on C: +2 Mints
Best: Build on C
Rule: Build on C
Result: correct incentives
Case 3: Tied Chain Fork
Before:
<- A <- B <- C
.........\
..........`- D
Build on C:
<- A <- B <- C <- X
.........\
..........`- D
Build on D:
<- A <- B <- C
.........\
..........`- D <- X
The miner is assumed to either build on C or D. The miner's block is X. C is assumed to be the first seen block.
In both cases, the miner will create a longest chain. This means that by rule A, most of the other miners will build on his block. This means that he gets the minting fee no matter which one he mines.
Build on C: +Mint
Build on D: +Mint
Best: Tie between Build on C and D
Rule: Build on C
Result: no incentive or disincentive to follow rule
Case 4: Tied Chain Fork - Miner involved
Before:
<- A <- B <- C
.........\
..........`- X
Build on C:
<- A <- B <- C <- Y
.........\
..........`- X
Build on X:
<- A <- B <- C
.........\
..........`- X <- Y
The miner is assumed to either build on C or X. The miner's block is X and his new block is Y. C is assumed to be the first seen block.
In both cases, the miner will create a longest chain. This means that by rule A, most of the other miners will build on his block. This means that he gets the minting fee for Y no matter which one he mines.
If he builds on X, he also gets the minting fee for X.
Build on C: +Mint
Build on X: +2 Mints
Best: Build on X
Rule: Build on C
Result: incentive to break rule
------------------------------------
This means that if most miners follow the two rules, then miners have an incentive to follow these rules.
A2) Mine on the valid chain tip with the greatest POW
B2) Otherwise, break ties in favor of mining on your own block
The miner can also follow this rule but the incentives are neutral. They can break or follow it without penalty.
C2) Otherwise, break ties for the earliest block received
This means that the Nash equilibrium is not stable.
If most miners follow A2, B2 and C2, then miners are incentivized to follow rule A2 and B2. This means that it is a better assumption that miners follow those rules, rather than the initial rule A and B.
The problem is that rule C2 is not incentivized. Fortunately, it is not dis-incentivized either.
I suggest a small tweak to the rules that I think create stable set of rules.
This requires computing a delay penalty for each block.
- For each block height record the time of the first block received for that block height
- The delay penalty for each block is equal to the difference between the time the block is received and the time for the first block at that height
The accumulated delay penalty for each block is equal to the sum of all delay penalties back to genesis.
In practice, you only need to compute the delay penalties back to the nearest common ancestor of all tied nodes.
The full rules are
A3) Mine on the valid chain tip with the greatest POW
B3) Otherwise, break ties in favor of mining on your own block
C3) Otherwise, break ties for the block with the smallest accumulated delay penalty
Rule C3 is almost exactly the same as C2) (and B). If both blocks in the tie have the same parent, then the earlier block will automatically have the smallest accumulated delay penalty.
The only case it makes a difference is when the miner has to mine on a tie, i.e. case 3.
Case 3: Tied Chain Fork
Before:
<- A <- B <- C
.........\
..........`- D
Build on C:
<- A <- B <- C <- X
.........\....\
..........`-D..`- E
Build on D:
<- A <- B <- C <- E
.........\
..........`- D <- X
The analysis changes slightly. If the miner wins the next block cleanly (without a near tie), then it doesn't matter which block they build on. They win the minting fee no matter what.
The difference is what happens if they end up in a tie situation. The other miner is assumed to find E at almost the same moment as the miner finds X.
If the miner mines on C, then they have a 50/50 chance of the other miners breaking the tie in their favor, since both X and E have the same parent and were broadcast at the same moment. That means that they get Mint/2 on average.
If the miner mines on D, then they will lose the tie-break. E and X are found at the same time, so neither gets a delay penalty. Since C was found first, D has a delay penalty. This means that there is an accumulated delay penalty for X (D + X) while no delay penalty for E (C + E). This means most of the miners mine on E, so the miner get nothing.
Build on C: +Mint (+Mint/2 in a tie)
Build on D: +Mint (0 in a tie)
Best: Build on C
Rule: Build on C
Result: correct incentives (weaker)
This means that with the delay penalty, the rules are stable. If most of the other miners follow A3, B3 and C3, then it is in the interests of all miners to follow them. C3 is incentivized rather than neutral. The incentive is weaker than normal but it is present. It depends on how often a tie happens.
If ties are very rare, then rules other than A don't matter anyway.
They are basically
A) Mine on the valid chain tip with the greatest POW
B) Break ties for the earliest block received
This is not a strict Nash equilibrium. If most other miners are using this strategy, there is no incentive to break ties correctly.
This means that it is potentially weakly unstable. Since ties happen rarely, it is not that big a deal to just follow the rule in those cases.
Miners don't lose out by following the above strategy so they might as well leave the code as the default rule.
I will only consider the minting fee for this analysis. Breaking ties based on transaction fees is another can of worms. It might be worth it for a miner to break ties in favor of the block that has the fewest transactions, since that leaves more transaction fees "on the table".
I will only consider the top-2 mining locations.
Case 1: Single Chain
Before:
<- A <- B <- C
Build on B:
<- A <- B <- C
.........\
..........`- X
Build on C:
<- A <- B <- C <- X
The miner is assumed to either build on B or C. The miner's block is X.
If the miner builds on B and finds the next block, then they will end up in a tie with C. Most of the other miners will have seen C already, so by rule B, they will build on C. This means that the miner's block is orphaned and they lose the block reward.
If the miner builds on C and finds the next block, then by rule A), most of the other miners will build on their block. This means that they get the block reward.
Build on B: 0
Build on C: +Mint
Best: Build on C
Rule: Build on C
Result: correct incentives
Case 2: Single Chain - miner owns previous
Before:
<- A <- X <- C
Build on B:
<- A <- X <- C
.........\
..........`- Y
Build on C:
<- A <- X <- C <- Y
The miner is assumed to either build on X or C. The miner's block is X and his new block is Y.
If the miner builds on X and finds the next block, then they will end up in a tie with C. Most of the other miners will have seen C already, so by rule B, they will build on C. This means that the miner's new block is orphaned and they lose the extra block reward.
If the miner builds on C and finds the next block, then by rule A), most of the other miners will build on their block. This means that they get both of their block rewards.
Build on X: +Mint
Build on C: +2 Mints
Best: Build on C
Rule: Build on C
Result: correct incentives
Case 3: Tied Chain Fork
Before:
<- A <- B <- C
.........\
..........`- D
Build on C:
<- A <- B <- C <- X
.........\
..........`- D
Build on D:
<- A <- B <- C
.........\
..........`- D <- X
The miner is assumed to either build on C or D. The miner's block is X. C is assumed to be the first seen block.
In both cases, the miner will create a longest chain. This means that by rule A, most of the other miners will build on his block. This means that he gets the minting fee no matter which one he mines.
Build on C: +Mint
Build on D: +Mint
Best: Tie between Build on C and D
Rule: Build on C
Result: no incentive or disincentive to follow rule
Case 4: Tied Chain Fork - Miner involved
Before:
<- A <- B <- C
.........\
..........`- X
Build on C:
<- A <- B <- C <- Y
.........\
..........`- X
Build on X:
<- A <- B <- C
.........\
..........`- X <- Y
The miner is assumed to either build on C or X. The miner's block is X and his new block is Y. C is assumed to be the first seen block.
In both cases, the miner will create a longest chain. This means that by rule A, most of the other miners will build on his block. This means that he gets the minting fee for Y no matter which one he mines.
If he builds on X, he also gets the minting fee for X.
Build on C: +Mint
Build on X: +2 Mints
Best: Build on X
Rule: Build on C
Result: incentive to break rule
------------------------------------
This means that if most miners follow the two rules, then miners have an incentive to follow these rules.
A2) Mine on the valid chain tip with the greatest POW
B2) Otherwise, break ties in favor of mining on your own block
The miner can also follow this rule but the incentives are neutral. They can break or follow it without penalty.
C2) Otherwise, break ties for the earliest block received
This means that the Nash equilibrium is not stable.
If most miners follow A2, B2 and C2, then miners are incentivized to follow rule A2 and B2. This means that it is a better assumption that miners follow those rules, rather than the initial rule A and B.
The problem is that rule C2 is not incentivized. Fortunately, it is not dis-incentivized either.
I suggest a small tweak to the rules that I think create stable set of rules.
This requires computing a delay penalty for each block.
- For each block height record the time of the first block received for that block height
- The delay penalty for each block is equal to the difference between the time the block is received and the time for the first block at that height
The accumulated delay penalty for each block is equal to the sum of all delay penalties back to genesis.
In practice, you only need to compute the delay penalties back to the nearest common ancestor of all tied nodes.
you can just sum up the received time for all blocks back to genesis. Since the first block time for each height is by definition a constant. I think it is clearer if it is made a penalty though.
The full rules are
A3) Mine on the valid chain tip with the greatest POW
B3) Otherwise, break ties in favor of mining on your own block
C3) Otherwise, break ties for the block with the smallest accumulated delay penalty
Rule C3 is almost exactly the same as C2) (and B). If both blocks in the tie have the same parent, then the earlier block will automatically have the smallest accumulated delay penalty.
The only case it makes a difference is when the miner has to mine on a tie, i.e. case 3.
Case 3: Tied Chain Fork
Before:
<- A <- B <- C
.........\
..........`- D
Build on C:
<- A <- B <- C <- X
.........\....\
..........`-D..`- E
Build on D:
<- A <- B <- C <- E
.........\
..........`- D <- X
The analysis changes slightly. If the miner wins the next block cleanly (without a near tie), then it doesn't matter which block they build on. They win the minting fee no matter what.
The difference is what happens if they end up in a tie situation. The other miner is assumed to find E at almost the same moment as the miner finds X.
If the miner mines on C, then they have a 50/50 chance of the other miners breaking the tie in their favor, since both X and E have the same parent and were broadcast at the same moment. That means that they get Mint/2 on average.
If the miner mines on D, then they will lose the tie-break. E and X are found at the same time, so neither gets a delay penalty. Since C was found first, D has a delay penalty. This means that there is an accumulated delay penalty for X (D + X) while no delay penalty for E (C + E). This means most of the miners mine on E, so the miner get nothing.
Build on C: +Mint (+Mint/2 in a tie)
Build on D: +Mint (0 in a tie)
Best: Build on C
Rule: Build on C
Result: correct incentives (weaker)
This means that with the delay penalty, the rules are stable. If most of the other miners follow A3, B3 and C3, then it is in the interests of all miners to follow them. C3 is incentivized rather than neutral. The incentive is weaker than normal but it is present. It depends on how often a tie happens.
If ties are very rare, then rules other than A don't matter anyway.
