2018-01-08 --- PoW-style fork-choice rule definitively causes less branching than GHOST

Observations

  1. The total length of blocks off the main DAG grows quadratically, with GHOST growing faster than MaxPC (this is what I'm going to call the PoW-style fork-choice from now on in order to prevent confusion with actual proof-of-work).
  2. The total number of heads of the DAG grows linearly, with MaxPC growing faster than GHOST.

Evidence

  1. Data and plots given below. GHOST in black and MaxPC in red.
    1. File attaching doesn't seem to be working right now...but I'll put a plot here when it is
    2. And I'll put the csv data files here
    3. The fit to GHOST gives a coefficient for the quadratic term of 25.528; the MaxPC coefficient is 21.065. Note that fits constrained the intercept to be 0.
  2. Plots given below, see above CSVs for data
    1. Again, plot here when it works again
    2. GHOST slope from linear fit: 26.297; MaxPC slope: 29.470. Note that fits constrained the intercept to be 0.
  3. Show a plot for the ratio of totalOffDagLength to numNonMainHeads to illustrate how the above two facts influence the average off-DAG length.

Conclusions, Speculation and Future Work

  1. GHOST produces more off-DAG blocks likely because the most successful branch is not chosen quickly, thus eventually leaving long unused branched behind.
  2. MaxPC produces more heads likely because less effort is put into joining them with acknowledgements as the main branch continues to grow. Essentially, many possibilities are given, but the best one is chosen quickly, leading to more heads, but less over all off-DAG length. This makes it quite clear than GHOST is less efficient than MaxPC.
  3. The quadratic growth of the total length and the linear growth of the number of heads also explains the linear behaviour of the average off-DAG length.