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 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 existing client allows a some ambiguity in best-chain selection: when blocks of equal chain-work compete, it prefers the first received.
For simplicity, assume there is no 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 side-chain-initial block will outweigh nine 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 age 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 fees 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 practice, I suspect the time would be less; my calculations are rough. Simulation confirms that after the calculated number of blocks, an honest block is usually in the lead. However, if the checkpoint is further in the past, it takes longer. 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 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 an equal fee.\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;
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 transactions per block: %f\n", avg_tx_per_block);
printf ("checkpoint age: %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 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 (iters > 0)
{
printf ("\rAvg after %u runs: %.4f reorgs, honest lead %.4f, max lead %.4f ",
iter, sum_reorgs / iter, sum_honest_lead / iter,
sum_max_lead / iter);
}
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 excluded fees times the number of orphan blocks,
// plus sum of current fees.
honest_weight = attacker_weight +
(excluded_tx * honest_blocks) + included_tx;
}
else
{
// Extending an honest block.
// Weight adds just current fees.
honest_weight += included_tx + 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;
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 = 300.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. 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 transactions per block: 100.000000 checkpoint age: 0 blocks per run: 2200 Avg after 1000 runs: 33.2040 reorgs, honest lead 9.7170, max lead 22.0240
The result: The attacker caused a reorg (sending the honest transactions back to the memory pool) on average 33.2 times in 2200 blocks. Over those 2200 blocks, on average there were 9.7 honest blocks at the end of the longest chain. Based on the simulation, one expects to see a longest string of 22.0 honest blocks somewhere during the same period.
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. This encourages miners to join the attack.
JohnTobey253 (talk) 23:38, 2 May 2013 (GMT)