2018-01-02 --- Model of Total PC and Quantifying Branching
Observations
- To prevent exponential growth of political capital, the following relation should hold: . Where is the fraction of new blocks which are acknowledgements in equilibrium (depends on the strategies employed by the validators), is the fraction of PC earned by acknowledging a block and is the number of validators.
- The PoW-like fork-choice rule causes measurably less branching than GHOST, but both show more branching happening over time.
Evidence
We set up a simple dynamical model of the total amount of PC as follows. Let
be as above, be the amount of PC controlled by validators at time , and be the amount of PC in blocks available for acknowledgement at time . and change over time according to the equationsTime is measured discretely in "rounds" and we assume that all validators act once in each round, each producing one block (acknowledge or propose). Since only the most recent block from each validator can be acknowledged, this means that exactly the blocks from the previous round are available for acknowledgement and no others. This is why the first term of Eq. (1) is a "persistence" term of the PC with the validators between rounds, but there is no corresponding term in Eq. (2); PC available for acknowledgement in blocks does not persist from round to round. The second term in Eq. (1) and first term in Eq. (2) correspond to proposals. Since a fraction
of the validators are acknowledging each round, therefore a fraction are proposing. We assume that these validators spend all their political capital to do this, thus the total amount of PC available to the validators decreases by the same fraction. These proposals become blocks to be acknowledged, so correspondingly, the amount of PC available in blocks increases by the same amount. The last term in both equations is the acknowledgement term. Since validators each acknowledge blocks, earning a fraction of what is available, the amount of PC the validators have increases by . However, those acknowledgement blocks can be acknowledged by other validators in the next round, therefore, the amount of PC available in blocks to be acknowledged increases by the same amount.
Rewriting Eq. (1) and Eq. (2) as a single matrix equation, we getIn order for this dynamical system to have a stable, non-trivial equilibrium, we need the largest (in absolute value) eigenvalue of the matrix to be equal to 1; larger than 1 and the system will blow up – exhibiting the exponential growth we saw in the simulation, less than 1 and eventually all the PC will decay away. One can show that if
then the largest eigenvalue is and the second eigenvalue is given by . Therefore, it is also desirable (though not necessary) for since then both eigenvalues will be positive and thus no oscillations on the way to equilibrium.We measure branching as the average length of branches which are not chosen by the fork-choice rule. This calculated by finding all blocks which are not the parent of another block (i.e. the heads of the DAG), excluding the one chosen by fork-choice, and counting the number of blocks between head head and its greatest common parent with the fork-choice head. Plots of this quantity are shown below for both PoW and GHOST fork-choice rules. We see that GHOST grows more quickly and therefore ends larger than PoW.
- AverageOffDagBranchLength_ghost.csv;
- AverageOffDagBranchLength_pow.csv;
- Both shown on the same plot for clarity:
- AverageOffDagBranchLength_ghost.csv;
Conclusions, Speculations and Future Work
- I should try to confirm the predictions of the model in the simulation. In particular, comparing the observed exponential growth rate to the model prediction in the data I have, and trying a simulation with the constraint enforced. It should be noted that there are stochastic effects in the simulation which the model "averages over" (i.e. it is a mean field model), so perfect agreement is not needed, but it would be nice if the predicitions were close to the simulation.
- The GHOST protocol seems to fall into a pattern in which the branching grows linearly over time. That may also be true for PoW, but if it is, the slope is much smaller. More data is needed to see how the branching continues to evolve over time.