Talk:Proof of blockchain fair sharing

Work-fee-since-checkpoint as chain weight metric

How about the following implementation. Everything stays the same as current Bitcoin except the definition of best chain. Instead of total chain work as defined by

SUM(difficulty[i])

over all blocks i in the chain, we define chain weight as work-fee since checkpoint:

SUM(fee[j]*difficulty[i])

Here, j ranges over all fee-bearing transactions in a given branch since the last checkpoint, and i ranges over all valid blocks that contain transaction j, directly or through an ancestor, including orphaned blocks. Checkpoints may be specified by administrative fiat, by a central authority (as currently), or by one of the proposed proof-of-stake checkpointing schemes, so long as one can disregard questionable checkpoints when one notices an attack in progress.

Network disagreement over checkpoints and varying knowledge of orphaned blocks will eventually work itself out, I think, faster and more automatically than under current conditions (which rely on manual intervention to develop and patch the block-acceptance algorithm in reaction to attacks). Note that even the original client allows some ambiguity in best-chain selection: when blocks of equal chain-work compete, it prefers the first received. The new formula yields practically the same result in the absence of 51% attacks and network partitions. Each new block adds weight in proportion to its difficulty. The fee component usually affects only contests between blocks of equal height, in which case it rewards transaction inclusion.

For simplicity, assume that we have abolished the block-size limit. A typical chain under 90% attack will have a side chain about every ninth block. Side chains occasionally grow longer than one block, but typically, the first block in a side chain contains all the excluded transactions from previous side chains since the attack began. Eventually, each such first block will outweigh nine (or any number) of the attacker's blocks. Excluded transactions will have multiple confirmations with increasing frequency. Only during periods of high attacker luck will they revert to unconfirmed, and such events will occur with decreasing frequency over time. Merchants might reasonably begin to count orphaned blocks as contributing something to the number of transaction confirmations.

How soon will one honest block weigh the same as nine of the attacker's blocks? It depends on the checkpoint freshness and the proportion of transaction fees excluded by the attacker. In the happy case where the last checkpoint immediately precedes the attack, my calculations show an approximate upper bound of

2 * (A/H)^3 * (I/E)

blocks, where A is the attacker strength, H is the honest network strength, I is the average fees included by the attacker, per block, and E is the average available new transaction fees excluded (foregone) by the attacker, per block. For example, an attacker with 90% trying to exclude 40% of transactions (weighted by fee) can succeed for

2 * (0.9/0.1)^3 * (0.6/0.4) =~ 2200 blocks

A 70% attacker can exclude 10% of transaction fees for

2 * (0.7/0.3)^3 * (0.9/0.1) =~ 230 blocks

The more draconian the attacker, the shorter the attack. An attacker with 90% who tries to exclude 90% of transaction fees will fail after

2 * (0.9/0.1)^3 * (0.1/0.9) =~ 162 blocks

In simulated attacks, the time is less; my calculations are rough. If the checkpoint is far in the past, it takes longer, but the eventual result is the same: the honest network creates ever-longer side chains. Indeed, if the checkpoint is well placed and

A*I < H * (I+E)

the attacker's advantage is nullified, and the honest network wins without intervention. Otherwise, the lead keeps going back and forth, with ever longer honest branches, until the honest participants agree on a checkpoint that decides the contest in their favour.

Corollaries:

• Orphaned block hashes are no longer wasted but protect the network.
• Transaction fees protect the network in a new, more direct way.
• Good citizens may be able to fight an attack by submitting fee-bearing transactions that the attacker would exclude, increasing E.
• Conversely, an attacker submitting self-transactions to increase I would put those fees at risk of capture by the (eventually victorious) honest network.
• Keeping up-to-date on checkpoints protects users by speeding up the resolution of this kind of attack.
• Intuitively, the chain weight formula rewards confirmation of fee-bearing transactions as opposed to simply "work".
• This change does not affect block acceptance criteria, so it is arguably not a hard fork or a mandatory upgrade. However, it works best with unlimited block size, at least as regards fee-bearing transactions.
• This formula works best when transaction fees dominate block-generation rewards. The attacker keeps its generated coins even after giving up. Thus, block-generation rewards still encourage miners to join the attack.

Here is the C program I used to simluate attacks:

// Public domain.

#include <stdio.h>
#include <stdlib.h>

static int
usage ()
{
  printf ("Usage: wfscp [ATTACKER_SHARE [INCLUSION_RATE [TX_PER_BLOCK [CP_AGE [BLOCKS_PER_ITER [ITERS [RANDOM_SEED]]]]]]]\n");
  printf ("Simulate work-fee-since-checkpoint under attack by an entity\n");
  printf ("controlling ATTACKER_SHARE%% (between 0 and 100) of hash power\n");
  printf ("and seeking to include only INCLUSION_RATE%% (0 to 100) of\n");
  printf ("transactions (weighted by fee).\n");
  printf ("Run ITERS simulations, each lasting BLOCKS_PER_ITER blocks.\n");
  printf ("TX_PER_BLOCK is the rate of fee-bearing transactions per block, pre-attack.\n");
  printf ("CP_AGE is the difference in height between the last pre-attack\n");
  printf ("block and the last checkpoint.\n");
  printf ("The integer RANDOM_SEED initializes the random number stream.\n");
  printf ("For simplicity, all transactions are assumed to carry a fee of 1 unit.\n");
  printf ("For simplicity, difficulty is assumed constant.\n");
  return 0;
}

static void
wfscp (double attacker_share, double inclusion_rate, double avg_tx_per_block,
       unsigned int checkpoint_age, unsigned int blocks_per_iter,
       unsigned int iters)
{
  unsigned int iter = 0;
  double sum_reorgs = 0.0;
  unsigned int count_honest_ahead = 0;
  double sum_honest_lead = 0.0;
  double sum_max_lead = 0.0;

  printf ("attacker share: %f%%\n", 100.0 * attacker_share);
  printf ("attacker transaction inclusion rate: %f%%\n", 100.0 * inclusion_rate);
  printf ("average fee-bearing transactions per block: %f\n", avg_tx_per_block);
  printf ("checkpoint age in blocks: %u\n", checkpoint_age);
  printf ("blocks per run: %u\n", blocks_per_iter);

  for (;; iter++)
    {
      unsigned int attacker_blocks = 0, honest_blocks = 0;
      double attacker_weight = checkpoint_age * (checkpoint_age + 1) * avg_tx_per_block / 2;
      double honest_weight = attacker_weight;
      double excluded_weight = 0.0;
      double included_tx = checkpoint_age * avg_tx_per_block, excluded_tx = 0.0;
      unsigned int honest_lead = 0;
      unsigned int max_lead = 0;
      unsigned int reorgs = 0;

      if (iter > 0)
        {
          printf ("\r%u run avg: %.3f reorgs, honest lead %.3f, max lead %.3f, honest %.1f%%   ",
                  iter, sum_reorgs / iter, sum_honest_lead / iter,
                  sum_max_lead / iter, count_honest_ahead * 100.0 / iter);
          fflush (stdout);
        }
      if (iter >= iters)
        {
          break;
        }

      for (; attacker_blocks + honest_blocks < blocks_per_iter;)
        {
          double r = drand48 () * (avg_tx_per_block + 1.0);

          if (r < attacker_share)
            {
              // Attacker extends the last attacker block.
              attacker_blocks++;

              // New weight is the parent block's weight
              // (attacker_weight) plus SUM(fee[j]) over included
              // transactions.  Difficulty assumed constant 1.0.
              attacker_weight += included_tx;

              if (honest_lead > 0 && attacker_weight > honest_weight)
                {
                  reorgs++;
                  honest_lead = 0;
                }
            }
          else if (r < 1.0)
            {
              // Honest miner extends the best block.
              honest_blocks++;

              if (honest_lead == 0)
                {
                  // Extending attacker's block.
                  // New weight is the parent block's value (attacker_weight)
                  // plus one for each time an excluded fee has occurred in
                  // an orphaned, honest block (excluded_weight),
                  // plus the sum of current fees (included_tx + excluded_tx).
                  honest_weight = attacker_weight + excluded_weight
                    + included_tx + excluded_tx;
                }
              else
                {
                  // Extending an honest block.
                  // Weight adds just current fees.
                  honest_weight += included_tx + excluded_tx;
                }

              excluded_weight += excluded_tx;
              honest_lead += 1;
              if (honest_lead > max_lead)
                {
                  max_lead = honest_lead;
                }
            }
          else if (r < inclusion_rate * avg_tx_per_block + 1.0)
            {
              included_tx += 1.0;
            }
          else
            {
              excluded_tx += 1.0;
            }
        }
      sum_reorgs += reorgs;
      count_honest_ahead += (honest_lead > 0 ? 1 : 0);
      sum_honest_lead += honest_lead;
      sum_max_lead += max_lead;
    }
  printf ("\n");
}

int
main (int argc, char** argv)
{
  double attacker_share = 0.7;
  double inclusion_rate = 0.5;
  double avg_tx_per_block = 200.0;
  unsigned int checkpoint_age = 0;
  unsigned int blocks_per_iter = 1000;
  unsigned int iters = 1000;

  if (argc > 1 && argv[1][0]) attacker_share = atof (argv[1]) / 100.0;
  if (attacker_share == 0.0) return usage ();
  if (argc > 2 && argv[2][0]) inclusion_rate = atof (argv[2]) / 100.0;
  if (argc > 3 && argv[3][0]) avg_tx_per_block = atof (argv[3]);
  if (argc > 4 && argv[4][0]) checkpoint_age = atoi (argv[4]);
  if (argc > 5 && argv[5][0]) blocks_per_iter = atoi (argv[5]);
  if (argc > 6 && argv[6][0]) iters = atoi (argv[6]);
  if (argc > 7 && argv[7][0]) srand48 (atol (argv[7]));

  wfscp (attacker_share, inclusion_rate, avg_tx_per_block, checkpoint_age,
         blocks_per_iter, iters);

  return 0;
}

Here is an example run where the attacker generates 90% of blocks and seeks to exclude 40% of transactions (inclusion rate 60%). A checkpoint occurs (or is placed during the attack) at the start of the attack. The simulation lasts 2200 blocks and repeats 1000 times:

$ ./wfscp 90 60 100 0 2200 1000 0
attacker share: 90.000000%
attacker transaction inclusion rate: 60.000000%
average fee-bearing transactions per block: 100.000000
checkpoint age in blocks: 0
blocks per run: 2200
1000 run avg: 49.980 reorgs, honest lead 5.608, max lead 15.016, honest 89.6%

The result: The attacker caused a reorg (sending all disapproved transactions back to the memory pool) on average 50 times in 2200 blocks. At the end of those 2200 blocks, on average there were 5.6 honest blocks at the end of the longest chain. In 89.6% of the runs, the 2200th block was honest. Based on the simulation, one expects to see a longest string of 15.0 honest blocks somewhere among the 2200 blocks. Running to 10 thousand blocks, we get:

$ ./wfscp 90 60 100 0 10000 1000 0
...same as above...
blocks per run: 10000
1000 run avg: 82.755 reorgs, honest lead 21.567, max lead 50.008, honest 97.3%

Here, our 90% attacker has to wait up to 50 blocks between times when it has the lead. The last 7800 blocks see only about 33 reorgs, compared to 50 in the first 2200. Of course, 90% is a pretty strong operation, and 60% compliance with the Gum Mint's registration requirement seems rather high. If the attack had only 70% power and 20% compliance, it would satisfy the constraint mentioned above, namely:

A   * I   < H   * (I+E)
0.7 * 0.2 < 0.3 * 1

After just 100 blocks, it would be essentially over:

./wfscp 70 20 100 0 100 1000 0
attacker share: 70.000000%
attacker transaction inclusion rate: 20.000000%
average fee-bearing transactions per block: 100.000000
checkpoint age in blocks: 0
blocks per run: 100
1000 run avg: 0.898 reorgs, honest lead 27.927, max lead 28.004, honest 100.0%

Note here that the theoretical maxium (average) honest lead is 30 (30% power over 100 blocks) and so 27.9 indicates very few honest blocks lost in the attack. On the other hand, if we start with a month-old (4400-block) checkpoint, recovery is slower, but still well in hand by 10 thousand blocks:

./wfscp 70 20 100 4400 10000 1000 0
attacker share: 70.000000%
attacker transaction inclusion rate: 20.000000%
average fee-bearing transactions per block: 100.000000
checkpoint age in blocks: 4400
blocks per run: 10000
1000 run avg: 67.015 reorgs, honest lead 1026.510, max lead 1205.691, honest 100.0%

Until now, I have ignored difficulty adjustments. To the extent that changing difficulty affects these scenarios, it will permit relatively faster extension of honest branches, since the honest network has less hashing power than the attacker. This benefit is limited, but not entirely negated, by the weighting of difficulty in the chain-selection formula.

JohnTobey253 (talk) 23:38, 2 May 2013 (GMT)