Bitcoin Wiki - User contributions [en]

Abe

2014-03-27T15:07:32Z

JohnTobey253: Update link.

[[File:penny-abe-160.png|thumb|160px|Abe]]

'''Abe''' is a free, open-source [[block chain browser]] released by [[User:JohnTobey253|John Tobey]] under the [[wikipedia:Affero General Public License|Affero General Public License]].

Written in [[wikipedia:Python (programming language)|Python]] and portable [[wikipedia:SQL|SQL]],<ref>https://bitcointalk.org/index.php?topic=16141.0</ref> Abe draws inspiration from [[Bitcoin Block Explorer]] and seeks some level of compatibility with it but uses a completely new implementation.<ref>https://raw.github.com/bitcoin-abe/bitcoin-abe/master/README.md</ref>

==See Also==

* [[Block chain browser]]

== External Links ==

* [http://bcv.coinwallet.pl/ Demonstration site]
* [https://bitcointalk.org/index.php?topic=22785.0 Project announcement]
* [https://github.com/bitcoin-abe/bitcoin-abe Project on Github]

==References==
<references />

[[Category:Block chain browsers]]
[[Category:Free Software]]
[[Category:Open Source]]

Abe

2014-03-27T15:06:41Z

JohnTobey253: Updated links.

[[File:penny-abe-160.png|thumb|160px|Abe]]

'''Abe''' is a free, open-source [[block chain browser]] released by [[User:JohnTobey253|John Tobey]] under the [[wikipedia:Affero General Public License|Affero General Public License]].

Written in [[wikipedia:Python (programming language)|Python]] and portable [[wikipedia:SQL|SQL]],<ref>https://bitcointalk.org/index.php?topic=16141.0</ref> Abe draws inspiration from [[Bitcoin Block Explorer]] and seeks some level of compatibility with it but uses a completely new implementation.<ref>https://raw.github.com/bitcoin-abe/bitcoin-abe/master/README.md</ref>

==See Also==

* [[Block chain browser]]

== External Links ==

* [http://bcv.coinwallet.pl/ Demonstration site]
* [https://bitcointalk.org/index.php?topic=22785.0 Project announcement]
* [https://github.com/jtobey/bitcoin-abe Project on Github]

==References==
<references />

[[Category:Block chain browsers]]
[[Category:Free Software]]
[[Category:Open Source]]

Talk:Proof of blockchain fair sharing

2013-05-06T18:19:27Z

JohnTobey253: /* Work-fee-since-checkpoint as chain weight metric */ more simulation and discussion of difficulty adjustments

== 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:

<nowiki>// 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;
}
</nowiki>

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.

[[User:JohnTobey253|JohnTobey253]] ([[User talk:JohnTobey253|talk]]) 23:38, 2 May 2013 (GMT)

Talk:Proof of blockchain fair sharing

2013-05-06T18:01:08Z

JohnTobey253: /* Work-fee-since-checkpoint as chain weight metric */ simulation results: clarification

== 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:

<nowiki>// 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;
}
</nowiki>

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.

[[User:JohnTobey253|JohnTobey253]] ([[User talk:JohnTobey253|talk]]) 23:38, 2 May 2013 (GMT)

Talk:Proof of blockchain fair sharing

2013-05-06T17:57:04Z

JohnTobey253: /* Work-fee-since-checkpoint as chain weight metric */ more discussion of simulation result

== 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:

<nowiki>// 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;
}
</nowiki>

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 honest lead is 30 (30% power over 100 blocks) and so 27.9 indicates very few honest blocks lost in the attack.

[[User:JohnTobey253|JohnTobey253]] ([[User talk:JohnTobey253|talk]]) 23:38, 2 May 2013 (GMT)

Talk:Proof of blockchain fair sharing

2013-05-06T17:31:30Z

JohnTobey253: /* Work-fee-since-checkpoint as chain weight metric */ details about attack resolution; comparison to original chain-work formula

== 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:

<nowiki>// 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;
}
</nowiki>

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 the first 2200's 50. 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, already after 1000 blocks it would be essentially over:

$ ./wfscp 70 20 100 0 1000 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: 1000
1000 run avg: 0.903 reorgs, honest lead 298.030, max lead 298.030, honest 100.0%

[[User:JohnTobey253|JohnTobey253]] ([[User talk:JohnTobey253|talk]]) 23:38, 2 May 2013 (GMT)

Talk:Proof of blockchain fair sharing

2013-05-03T06:30:12Z

JohnTobey253: /* Work-fee-since-checkpoint as chain weight metric */ reordered sections

== 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 existing client allows some ambiguity in best-chain selection: when blocks of equal chain-work compete, it prefers the first received.

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 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 far in the past, it takes longer.

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:

<nowiki>// 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;
}
</nowiki>

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 the first 2200's 50. 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, already after 1000 blocks it would be essentially over:

$ ./wfscp 70 20 100 0 1000 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: 1000
1000 run avg: 0.903 reorgs, honest lead 298.030, max lead 298.030, honest 100.0%

[[User:JohnTobey253|JohnTobey253]] ([[User talk:JohnTobey253|talk]]) 23:38, 2 May 2013 (GMT)

Talk:Proof of blockchain fair sharing

2013-05-03T02:54:02Z

JohnTobey253: /* Work-fee-since-checkpoint as chain weight metric */ clarity tweaks

== 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 existing client allows some ambiguity in best-chain selection: when blocks of equal chain-work compete, it prefers the first received.

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 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 far in the past, it takes longer. Here is the C program I used to simluate attacks:

<nowiki>// 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;
}
</nowiki>

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 the first 2200's 50. 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, already after 1000 blocks it would be essentially over:

$ ./wfscp 70 20 100 0 1000 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: 1000
1000 run avg: 0.903 reorgs, honest lead 298.030, max lead 298.030, honest 100.0%

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.

[[User:JohnTobey253|JohnTobey253]] ([[User talk:JohnTobey253|talk]]) 23:38, 2 May 2013 (GMT)

Talk:Proof of blockchain fair sharing

2013-05-03T02:34:27Z

JohnTobey253: /* Work-fee-since-checkpoint as chain weight metric */ tweaked wording

== 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:

<nowiki>// 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;
}
</nowiki>

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 the first 2200's 50. 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, already after 1000 blocks it would be essentially over:

$ ./wfscp 70 20 100 0 1000 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: 1000
1000 run avg: 0.903 reorgs, honest lead 298.030, max lead 298.030, honest 100.0%

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.

[[User:JohnTobey253|JohnTobey253]] ([[User talk:JohnTobey253|talk]]) 23:38, 2 May 2013 (GMT)

Talk:Proof of blockchain fair sharing

2013-05-03T01:24:42Z

JohnTobey253: /* Work-fee-since-checkpoint as chain weight metric */ prettier C

== 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:

<nowiki>// 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;
}
</nowiki>

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 honest 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 the first 2200's 50. 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, already after 1000 blocks it would be essentially over:

$ ./wfscp 70 20 100 0 1000 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: 1000
1000 run avg: 0.903 reorgs, honest lead 298.030, max lead 298.030, honest 100.0%

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.

[[User:JohnTobey253|JohnTobey253]] ([[User talk:JohnTobey253|talk]]) 23:38, 2 May 2013 (GMT)

Talk:Proof of blockchain fair sharing

2013-05-03T01:20:34Z

JohnTobey253: /* Work-fee-since-checkpoint as chain weight metric */ minor rewording

== 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:

<nowiki>// 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;
}
</nowiki>

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 honest 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 the first 2200's 50. 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, already after 1000 blocks it would be essentially over:

$ ./wfscp 70 20 100 0 1000 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: 1000
1000 run avg: 0.903 reorgs, honest lead 298.030, max lead 298.030, honest 100.0%

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.

[[User:JohnTobey253|JohnTobey253]] ([[User talk:JohnTobey253|talk]]) 23:38, 2 May 2013 (GMT)

Talk:Proof of blockchain fair sharing

2013-05-03T01:08:53Z

JohnTobey253: /* Work-fee-since-checkpoint as chain weight metric */ simulation: bug fixes, more examples

== 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:

<nowiki>// 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;
}
</nowiki>

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 honest 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 the first 2200's 50. 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, already after 1000 blocks it would be essentially over:

$ ./wfscp 70 20 100 0 1000 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: 1000
1000 run avg: 0.903 reorgs, honest lead 298.030, max lead 298.030, honest 100.0%

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.

[[User:JohnTobey253|JohnTobey253]] ([[User talk:JohnTobey253|talk]]) 23:38, 2 May 2013 (GMT)

Talk:Proof of blockchain fair sharing

2013-05-02T23:43:09Z

JohnTobey253: /* Work-fee-since-checkpoint as chain weight metric */ tweak input description

== 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:

<nowiki>// 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 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 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;
}
</nowiki>

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.

[[User:JohnTobey253|JohnTobey253]] ([[User talk:JohnTobey253|talk]]) 23:38, 2 May 2013 (GMT)

Talk:Proof of blockchain fair sharing

2013-05-02T23:38:35Z

JohnTobey253: /* Work-fee-since-checkpoint as chain weight metric */ simulation program and result

== 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:

<nowiki>// 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;
}
</nowiki>

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.

[[User:JohnTobey253|JohnTobey253]] ([[User talk:JohnTobey253|talk]]) 23:38, 2 May 2013 (GMT)

Talk:Proof of blockchain fair sharing

2013-05-02T20:49:30Z

JohnTobey253: /* Work-fee-since-checkpoint as chain weight metric */ comment regarding block-generation rewards

Talk:Proof of blockchain fair sharing

2013-05-02T20:42:20Z

JohnTobey253: /* Work-fee-since-checkpoint as chain weight metric */ added a few details

Talk:Proof of blockchain fair sharing

2013-05-02T19:55:04Z

JohnTobey253: /* Work-fee-since-checkpoint as chain weight metric */ minor tweak

Talk:Proof of blockchain fair sharing

2013-05-02T18:44:00Z

JohnTobey253: /* Work-fee-since-checkpoint as chain weight metric */ tweak

Talk:Proof of blockchain fair sharing

2013-05-02T18:38:15Z

JohnTobey253: /* Work-fee-since-checkpoint as chain weight metric */ tweak

Talk:Proof of blockchain fair sharing

2013-05-02T18:25:45Z

JohnTobey253: Undo revision 37459 by JohnTobey253 (talk)

Talk:Proof of blockchain fair sharing

2013-05-02T18:18:52Z

JohnTobey253: /* Work-fee-since-checkpoint as chain weight metric */ no need to "disregard questionable checkpoints"

Talk:Proof of blockchain fair sharing

2013-05-02T18:02:37Z

JohnTobey253: /* Work-fee-since-checkpoint as chain weight metric */ tweaks

Talk:Proof of blockchain fair sharing

2013-05-02T17:59:52Z

JohnTobey253: /* Work-fee-since-checkpoint as chain weight metric */ tweaks

Talk:Proof of blockchain fair sharing

2013-05-02T17:55:06Z

JohnTobey253: add section heading

Talk:Proof of blockchain fair sharing

2013-05-02T17:52:48Z

JohnTobey253: Work-fees-since-checkpoint as chain-height 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 ''chain work-fee since checkpoint'':

SUM(fee[j]*SUM(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 indirectly, '''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 prevent questionable checkpoints when one notices an attack in progress.

Network disagreement regarding checkpoints and orphaned blocks seen 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).

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 several of the attacker's blocks.

How soon? 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

In practice, I suspect the time would be less; my calculations are still rough. However, if the checkpoint is further in the past, it takes longer.

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 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 mandatory upgrade. However, it works best with unlimited block size, at least as regards fee-bearing transactions.

[[User:JohnTobey253|JohnTobey253]] ([[User talk:JohnTobey253|talk]]) 17:52, 2 May 2013 (GMT)

Abe

2013-03-20T18:34:31Z

JohnTobey253: update: abe.john-edwin-tobey.org not offline currently

[[File:penny-abe-160.png|thumb|160px|Abe]]

'''Abe''' is a free, open-source [[block chain browser]] released by [[User:JohnTobey253|John Tobey]] under the [[wikipedia:Affero General Public License|Affero General Public License]].

Written in [[wikipedia:Python (programming language)|Python]] and portable [[wikipedia:SQL|SQL]],<ref>https://bitcointalk.org/index.php?topic=16141.0</ref> Abe draws inspiration from [[Bitcoin Block Explorer]] and seeks some level of compatibility with it but uses a completely new implementation.<ref>https://raw.github.com/jtobey/bitcoin-abe/master/README.md</ref>

==See Also==

* [[Block chain browser]]

== External Links ==

* [http://abe.bitcoinstats.org:2750 Demonstration site]
* [http://abe.john-edwin-tobey.org/ Original demonstration site]
* [https://bitcointalk.org/index.php?topic=22785.0 Project announcement]
* [https://github.com/jtobey/bitcoin-abe Project on Github]

==References==
<references />

[[Category:Block chain browsers]]
[[Category:Free Software]]
[[Category:Open Source]]

Firstbits

2012-06-13T02:23:27Z

JohnTobey253: Flagged statement needing citation

'''Firstbits''' refers to the practice of abbreviating a [[Bitcoin address]] such that only enough of the initial characters of the address are given so that the full address can be identified from the [[block chain]]. It also refers to the website http://www.Firstbits.com.

The term Firstbits was popularized by the Firstbits website, which was provided with the intent of a "Bitcoin address shortener", working similar to a URL shortener. Firstbits.com performs a lookup service, giving the full address from the block chain from the initial portion of an address. Anyone with access to a complete copy of the block chain can independently perform the same lookup done by Firstbits.com.

Any time a Bitcoin address is used for transactional purposes and appears in the block chain, its firstbits - or the prefix that uniquely identifies that address within the block chain - are considered assigned at that time. If another address is created and used with the same prefix at a later time, the firstbits of that new address will be at least one character longer, as the shorter prefix remains reserved for the address that used it first. No action on the part of any user is required for firstbits to be assigned - any transaction activity (receiving or sending) for an address for the first time results in firstbits becoming automatically assigned.

Unlike Bitcoin addresses, firstbits are deemed assigned in a '''case-insensitive''' manner.

The firstbits of the very first address to be used by [[Satoshi]] in the [[genesis block]] of the [[block chain]] will have been '''"1"'''.

==Criticism==
Firstbits is generally considered to be a bad idea because it encourages transaction spam.
This position is held by most, if not all, of Bitcoin developers.{{Citation needed}}

Abe

2012-01-22T19:08:16Z

JohnTobey253: Updated link

[[File:penny-abe-160.png|thumb|160px|Abe]]

'''Abe''' is a free, open-source [[block chain browser]] released by [[User:JohnTobey253|John Tobey]] under the [[wikipedia:Affero General Public License|Affero General Public License]].

Written in [[wikipedia:Python (programming language)|Python]] and portable [[wikipedia:SQL|SQL]],<ref>https://bitcointalk.org/index.php?topic=16141.0</ref> Abe draws inspiration from [[Bitcoin Block Explorer]] and seeks some level of compatibility with it but uses a completely new implementation.<ref>https://raw.github.com/jtobey/bitcoin-abe/master/README.md</ref>

==See Also==

* [[Block chain browser]]

== External Links ==

* [http://abe.john-edwin-tobey.org/ Demonstration site]
* [https://bitcointalk.org/index.php?topic=22785.0 Project announcement]
* [https://github.com/jtobey/bitcoin-abe Project on Github]

==References==
<references />

[[Category:Block chain browsers]]
[[Category:Free Software]]
[[Category:Open Source]]

Alternative chain

2011-10-16T04:42:59Z

JohnTobey253: /* Protecting against double proof */ minor tweaks

An '''alternative chain''' is a system using the block chain algorithm to achieve distributed consensus on a particular topic. Alternative chains may share miners with a '''parent''' network such as Bitcoin's; this is called '''merged mining'''. Alternative chains have been suggested as ways to implement DNS, SSL certificate authorities, timestamping, file storage and voting systems.

== Objective ==

Bitcoin uses the [[block chain]] algorithm to achieve distributed consensus on who owns what coins. Block chains were invented specifically for the Bitcoin project but they can be applied anywhere a distributed consensus needs to be established in the presence of malicious or untrustworthy actors.

Whilst it's possible to abuse the Bitcoin financial block chain for other purposes, it's better to set up an alternative network and chain which share the same miners. There are several reasons to do this.

* The block chain is a large, complex data structure shared between many people. Verifying its integrity requires many slow (and thus expensive) operations like ECDSA verifications and disk seeks. Everyone who takes part in Bitcoin today runs a node and thus maintains the whole thing. Whilst in future end-users will probably use more efficient but slightly less secure modes (SPV), merchants and miners will probably always pay the full costs for the upkeep of this shared data structure. All these people today are united by a common interest in a new form of payments. They may or may not also be interested in other schemes. So one reason to keep the Bitcoin chain for finance is it's unfair to externalize the costs of unrelated schemes onto people who are interested only in payments - the canonical example being merchants. Increasing the cost of accepting Bitcoins for goods and services hurts everyone who uses the system by reducing the number of merchants or increasing their costs.

* Another reason is that it's just bad engineering to cram every possible distributed quorum into the design constraints of Bitcoin. The transaction format Bitcoin uses is flexible but ultimately designed for finance. You cannot leave out the "value" field. It's always there, even if it'd make no sense for your particular application. Building non-financial applications on top of a financial system results in bizarre protocols and code that are difficult to understand, leading to maintainability problems.

* One final reason is that [[Satoshi Nakamoto|Satoshi]] was opposed to putting non-Bitcoin related data into the main chain. As creator of the system, his opinion should carry a lot of weight with anyone serious about extending it.

=== Designing a new network ===

To create a new network that uses Nakamoto block chains, you need to start by defining what a transaction in your new network means. Bitcoin transactions split and combine value using scripts, but yours don't have to do that. They could be anything. Here's an example of a simple DNS style "transaction" described using [http://code.google.com/p/protobuf/ Google protocol buffers] syntax.

message NameTx {
required string name = 1;
repeated bytes ip_addresses = 2;
required bytes pubkey = 3;
enum ClaimType {
NEW_NAME,
TRANSFER
}
required ClaimType type = 4;

// Only used if type == TRANSFER. The new owner of the name and signature proving current ownership.
optional bytes dest_pubkey = 5;
optional bytes signature = 6;
}

This is very different to a Bitcoin style transaction. There's no concept of inputs, outputs, addresses, values or scripts. It's got what you need for a very simple DNS style scheme (that lacks abuse controls etc) and nothing more. There's also no concept of a "coinbase" transaction.

The block definition is also up to you. It does not have to be formatted in the same way as Satoshi chose, but you need most of the same conceptual parts. You also need to store something else, some data from Bitcoin. Here's a minimal example of what's needed:

message MyBlock {
required bytes prev_block_hash = 1;
required uint32 difficulty = 2;
required uint32 time = 3;

repeated MyTx transactions = 4;
}

message SuperBlock {
required MyBlock my_data = 1;
required BitcoinData bitcoin_data = 2;
}

It's important to observe what we don't have as well as what we do. We don't have the following fields from Satoshis format:

# version: protobufs handles the versioning of binary data formats for us
# merkle root: you can choose to arrange your transactions into a merkle root if you like, so you can use the same disk space reclamation trick Satoshi did. But it's strictly optional. If you want to simplify things down you can skip it.
# nonce

== Sharing work ==

The bitcoin_data field is how you share work with miners today (assuming they opt in by installing your software alongside their bitcoin node). It's defined like this:

message BitcoinData {
// A Bitcoin format block header. Because it's in Satoshis custom format we represent this as a byte array.
required bytes header = 1;

// The first transaction from the block.
required bytes coinbase_tx = 2;

// The merkle branch linking the coinbase transaction to the header.
required bytes coinbase_merkle_branch = 3;

// The coinbase scriptSig contains bits of data in order. Which one is our hash?
required int coinbase_tx_index = 4;
}

All you need to share work is the above four things.

A [[wikipedia:Merkle tree]] is a data structure in which each node in the tree is a hash. The leaf nodes are hashes of the things you want to include in the tree. The interior nodes are hashes of the concatenations of the child nodes. A merkle branch is a part of a merkle tree which allows you to cryptographically prove that something you're given was in the tree, without needing everything that was in the tree. They are calculated by the CBlock::GetMerkleBranch() function in the Bitcoin code.

We store a merkle branch here for efficiency. It means no matter how large the current Bitcoin block is, your alternative network only needs to handle a small amount of data. You could just store the entire Bitcoin block - that would be simpler but inefficient.

The merkle branch links the coinbase transaction to the block header, so you can prove it was in that block. The coinbase TX is a regular Bitcoin coinbase (that makes new coins and claims fees), except the scriptSig on its input contains an extra entry that todays scriptSigs don't. That extra entry is a hash of your block structure. The coinbase scriptSig today is formatted like this:

void IncrementExtraNonce(CBlock* pblock, CBlockIndex* pindexPrev, unsigned int& nExtraNonce, int64& nPrevTime)
{
.....
pblock->vtx[0].vin[0].scriptSig = CScript() << pblock->nBits << CBigNum(nExtraNonce);
.....
}

Just the difficulty bits and the "extra nonce". But it's actually allowed to contain anything, as long as it's not too big. So in your new blocks it'd be:

<MyBlock hash> <nBits> <nExtraNonce>

To get the MyBlock hash into Bitcoin requires a presently unimplemented RPC command, "setextrahashes". It'd update a global list and the IncrementExtraNonce function would include the extra hashes when the scriptSig is built. This is a very simple change to Bitcoin.

In the scriptSig above the coinbase_tx_index would be zero. It's possible to work on an arbitrary number of alternative chains simultaneously:

<MyBlock hash> <SomeOtherChainBlock hash> <nBits> <nExtraNonce>

in which case the BitcoinData message for SomeOtherChain would be 1 rather than zero.

A more complex change is the other new RPC. Because you have your own chain, it has its own difficulty. Most likely it'll be different to Bitcoins own. So you need a way to tell Bitcoin "when you find a block that matches an extradifficulty, please let me know". To mine on multiple difficulties at once, the node vends work (via getwork) matching the easiest difficulty. When a miner reports finding a solution the difficulty is checked to see which chains it is sufficiently difficult for.

Important note: Your chain has its own difficulty and as such the block creation rate is independent of how much mining takes place.

== Independent node software ==

Your new network has its own codebase. It can be written in whatever language you like, use whatever P2P protocol you like, store its data however you like and so on.

When a node on your network receives a message informing it about a new transaction, it verifies that transaction follows the rules of your network. To use our simple DNS example it would verify that if you're claiming a new name, it doesn't already exist and if you're transferring a name that the signatures are correct.

If the transaction is valid, it's added to your current MyBlock message. That message is serialized to binary (protobufs does this for you), hashed and then your node makes an RPC to Bitcoin telling it what the current extra hash is. When Bitcoin finds a Bitcoin-format block of the right difficulty for your network, it informs your software and passes the block header, coinbase transaction and merkle branch to it. Your node combines them together into a BitcoinData message, which is then glued together with your alternative chains block. This "superblock" is then broadcast via your independent P2P network.

When a node on your new network receives a superblock it does the following things:

# Verifies the MyBlock contents are correct, ie, that the transactions follow the rules.
# Verifies that the MyBlock prev hash makes it fit somewhere in the chain and that the difficulty is correct.
# Hashes the MyBlock structure and then verifies that this hash appears in the BitcoinData coinbase scriptSig, in the right place.
# Extracts the merkle root of the Bitcoin format block from the header and then verifies that the coinbase tx provided did, in fact, exist in that block (using the branch, root, tx and header together).
# Verifies that the hash of the Bitcoin format block header is below the difficulty found in the MyBlock structure.

You've now verified that a sufficiently hard proof of work was done over the contents of the MyBlock structure, so your node can relay the newly found block (or if you don't use a P2P network make it available on your server, etc).

On the other side when Bitcoin finds a block that is correct for the Bitcoin network and chain, it broadcasts it and obviously the hash of your MyBlock is included. Fortunately this is only an additional 33 bytes overhead so nobody cares about it - the pollution of the financial chain is both trivial and constant. Note that regular Bitcoin nodes just ignore this extra hash, it doesn't mean anything to them.

== Handling your new block chain ==

You have to handle re-organizations. This is a standard part of the block chain algorithm. When a re-org occurs you have to verify that the state of your world still makes sense. For example in the new chain maybe somebody else now owns a resource you thought you owned. It's up to you how to inform your users of these events and what app specific logic is appropriate here.

You can choose your own parameters for the new chain. As an example, Satoshi chose to target one new block every ten minutes as a tradeoff between latency and wasted work. You could choose something much larger (hours, days) or much faster if you're willing to tolerate more splits due to blocks being found simultaneously. Bitcoin retargets the difficulty roughly every two weeks. You could choose some other length of time.

To store the block chain, Satoshi chose to use Berkeley DB as a way to index from transactions to the blocks they appeared in (amongst other things). You could use any database you liked.

== Paying for resources on alternative chains with Bitcoins ==

A commonly cited reason for putting DNS related data into the financial chain is the desire to pay for names with Bitcoins. You can do this with an independent chain too, because you make the rules and can link the two chains together as you see fit.

To start, decide on the purpose of your payments and who will receive the coins - if anyone. In the case of a DNS system, there are two reasons you might want to pay for names:

# To prevent abuse by people claiming all interesting names via a dictionary attack.
# To incentivise people to run your software and mine on your alternative chain.

In the first case really nobody should receive the payment. The money is being put up as a collateral and has no other use, so as long as it's sitting around unspent that is good enough. In the second case the payment should go to the miner working on the DNS chain.

To implement this we extend our hypothetical DNS transaction message like this:

message NameTx {
required string name = 1;
repeated bytes ip_addresses = 2;
required bytes pubkey = 3;
enum ClaimType {
NEW_NAME,
TRANSFER
}
required ClaimType type = 4;

// Only used if type == TRANSFER. The new owner of the name and signature proving current ownership.
optional bytes dest_pubkey = 5;
optional bytes signature = 6;

// Only used if type == NEW_NAME.
optional bytes collateral_signature = 7;
optional string miner_address = 8;
optional uint64 miner_fee = 9;
}

The collateral_signature field contains an ECDSA signature generated from a public key that holds some Bitcoins. The miner address is blank when the name purchaser creates the transaction and is filled out after a miner receives it, but before they begin working on it.

To buy a name that costs 10 BTC with a miner fee of 2 BTC, a user presses the "buy name" button in their DNS software. It talks to their local Bitcoin node via RPC and does the following:

# Creates a new Bitcoin address (key).
# Sends 10 BTC to the new address (a send-to-self transaction).
# Extracts the key from Bitcoin, meaning it's no longer available to spend in your wallet.
# Stores the key in a local DNS data file ("wallet") somewhere.
# Sets the miner_fee field to the pre-agreed value of 2 BTC.
# Takes the public key part and uses it to sign a version of the NameTx that lacks collateral_signature (a signature can't sign itself) and miner_address.
# The signature is placed in collateral_signature field.
# The transaction is sent to a miner who charges 2 BTC.

When the miner receives the transaction, it verifies that the 10 BTC is not spent:

# The ECDSA public key recovery algorithm is run on the collateral_signature. It can yield several possible keys.
# The public keys recovered are used to verify the signature is correct. This step also figures out which of the possible keys is the right one.
# The correct public key is turned into a Bitcoin address (by hashing it)
# The DNS node software queries Bitcoin to discover whether that address has 10 BTC associated with it, or whether the balance of that address is lower. Note that todays software does not index the balance of every address in the system, but it can be added (the Block Explorer does this).
# If the address does indeed have 10 unspent Bitcoins then the collateral is present and it's OK to serve the name

The miner then creates a new Bitcoin address for themselves and sets miner_address to contain it, then includes it into the current block being worked on. After a block matching the DNS chains difficulty is found, it is broadcast. Other nodes do the following:

# For each transaction, repeat the verification steps to ensure the collateral is not spent.
# Check the balance of the miners own address.
# If the balance is not yet equal to miner_fee, the name is put into a "pending" state in which it is owned but not served in response to DNS queries.

The user observes the broadcast and sees that their name is now pending payment, so they send 2 BTC to the address they find in their transaction. As nodes notice the payment becoming confirmed they start responding to DNS queries for that name (ie, the ownership process is complete).

When the user gets tired of owning the name, he can simply re-import the collateral key into his wallet and spend the coins. The DNS network will soon observe that the coins are spent and make the name available for purchasing by somebody else.

== Incentivising non-resource based chains ==

It's possible to incentivise mining on an alt-chain even if that chain does not have any concept of ownership, ie, if the act of finding a block itself is what is being paid for. An example of this is a timestamping chain in which presence in a block alone is sufficient to satisfy the user.

To implement this, set up a new chain as normal. Blocks in this new chain arrange transactions into a merkle tree in the same manner as Bitcoin does. A client that wants something incorporated into a block connects directly to some miners and submits their transaction. The miners add their address to the transaction as normal. Once a miner finds a block, it immediately sends the block to connected clients whose transactions made it in, but does not broadcast the new block to other miners. The clients respond with a valid Bitcoin transaction which pays for block inclusion. Once all clients have paid up the transaction is broadcast.

If a client has disconnected or does not pay quickly enough, their transaction can be replaced inside the block with its hash. In this way the blocks validity is preserved because the merkle tree is still valid. The newly found alt-block is broadcast, minus the transaction of the delinquent customer. As long as clients are still connected the payment process for all found transactions can be completed quickly: it would only take a few seconds to gather the payments and broadcast those on the Bitcoin network, minimizing the chance of a race that would require you to trust the miner to reinclude your transactions in the next block despite having already been paid.

== Mining on the alt-chain but not Bitcoin ==

So far we've considered a scheme in which all alt-chain miners simultaneously mine on Bitcoin. It's possible some people may wish to mine on your chain but not Bitcoin, perhaps because the cost of keeping up with the Bitcoin transaction rate has become too high for them to bother.

To mine without an attached Bitcoin node, your software can simply implement the same getwork protocol Bitcoin itself does. When a mining tool requests work your program would generate a correctly formatted but ultimately bogus Bitcoin block. The contents of this block don't need to be correct because it will never be broadcast on the Bitcoin network, for example, the prevBlockHash field can be all zeros. It exists purely for backwards compatibility. Whilst the block needs a valid merkle root and a coinbase transaction, no other transactions are required and the only part of the coinbase tx that matters is the part holding the hash.

== Scaling up ==

In the simple scheme each alt-chain being worked on needs 33 bytes in the Bitcoin coinbase transaction (1 for the length and 32 for the hash). Note that if there are two independent miners working on two different alt-chains, you still only need 1 hash in the coinbase scriptSig because the hash isn't meaningful to anyone else on the Bitcoin network. If miners only want to work a handful of chains this overhead is trivially dwarfed by the rest of the data in a Bitcoin block.

But if a miner wishes to work on hundreds, thousands or millions of alternative chains the size of the coinbase scriptSig would balloon and become unworkable. To solve this, the hash stored in the scriptSig can be the root of yet another merkle tree, this time a tree over the hashes of all blocks being worked on. The BitcoinData message is extended like this:

message MyBlock {
required bytes prev_block_hash = 1;
required uint32 difficulty = 2;
required uint32 time = 3;

repeated MyTx transactions = 4;
}

message SuperBlock {
required MyBlock my_data = 1;
required BitcoinData bitcoin_data = 2;
}

message BitcoinData {
// A Bitcoin format block header. Because it's in Satoshis custom format we represent this as a byte array.
required bytes header = 1;

// The first transaction from the block.
required bytes coinbase_tx = 2;

// The merkle branch linking the coinbase transaction to the header.
required bytes coinbase_merkle_branch = 3;

// The merkle branch linking MyBlock to the merkle root in the coinbase_tx.
required bytes altblock_merkle_branch = 4;
}

The verification step becomes a bit more complex:

# Verify the header is of sufficient difficulty for the alt-chain
# Verify coinbase_tx was a part of that block by checking the coinbase_merkle_branch is linked to the merkle root in the header.
# Extract the root of the second merkle tree from the coinbase_tx (call it 2MR).
# Hash the alt-chain block (my_data), verify that altblock_merkle_branch links the my_data hash to 2MR.

You have now proven that the MyBlock instance was worked on, along with perhaps thousands of other chains you don't have to know anything about.

This is an advanced technique which is probably not worth implementing unless the additional scalability is required. It can be introduced in a backwards compatible manner for new chains without impacting older networks.

=== Protecting against double proof ===

The merkle tree approach to scalability comes with a caveat. If naïvely implemented, a miner could cheat the proof-of-work system by putting more than one alt-chain block header into one Bitcoin block. This "cheating" would not cause a problem if the alt-chain blocks all had the same previous-block hash: one or another would win the race, as happens when competing blocks enter the network. The problem would arise if a linked series of alt-chain blocks all existed in one Bitcoin block's auxiliary merkle trees. The miner could work on them all at once, getting more from his hashes than difficulty warrants.

Namecoin's [http://dot-bit.org/forum/viewtopic.php?f=5&t=269&start=11 solution] is to constrain the paths by which alt-chain blocks may be embedded in Bitcoin blocks. This works, but it complicates the picture for miners and chain designers in a future with many alternative chains.

Perhaps a better solution for new chains is to prevent the existence of linked series of alt-chain blocks which lack proof of work. For example, one could require each alt-chain block to refer (perhaps via its own coinbase or a new header field) to the "solution" (target-meeting hash of parent chain block) as well as the hash of the previous block in the alt chain. (In Bitcoin, these two hashes are the same.) This would force blocks to refer not just to the previous block in the chain but to the proof of work on that block. A series of alt-chain blocks all being worked on would not make sense, because the second block in the series would refer to the first block's solution, so the first block would have been solved already.

== Generalized proof of work ==

Hashes embedded in transactions and headers, merkle branches, and [[Nonce|nonces]] all contribute to the goal of [[Proof of work|proving work]] on a block header. One can express all as sequences of these basic operations:

* prepend a byte string to the current data
* append a byte string to the current data
* hash the current data

For maximum flexibility, a work-sharing chain's block acceptance algorithm might accept proof in the form of a script using just these operations. The script would receive as input an alternative chain block header, and the hash of its output would have to satisfy the chain's difficulty.

This design would even support plain Bitcoin proof of work, where the "header" consists of all [[Protocol Specification#block|Bitcoin block header fields]] except the nonce, and the proof-of-work script simply appends the nonce. Thus, one can think of the work-sharing rules as an extension of the original Bitcoin rules.

==External Links==

* [https://bitcointalk.org/index.php?topic=6197.0 BitDNS in the words of Satoshi]
* [http://dot-bit.org/Merged_Mining Merged Mining] in Namecoin
* [http://dot-bit.org/forum/viewtopic.php?f=5&t=269 Namecoin forum discussion]
* [https://bitcointalk.org/index.php?topic=46927.msg572981#msg572981 Forum thread about double proof]

[[Category:Technical]]

Merged mining

2011-10-16T04:17:57Z

JohnTobey253: Redirect to Alternative Chains

#REDIRECT [[Alternative Chains]]

Alternative chain

2011-10-16T04:17:00Z

JohnTobey253: Introduce term 'merged mining'

An '''alternative chain''' is a system using the block chain algorithm to achieve distributed consensus on a particular topic. Alternative chains may share miners with a '''parent''' network such as Bitcoin's; this is called '''merged mining'''. Alternative chains have been suggested as ways to implement DNS, SSL certificate authorities, timestamping, file storage and voting systems.

== Objective ==

Bitcoin uses the [[block chain]] algorithm to achieve distributed consensus on who owns what coins. Block chains were invented specifically for the Bitcoin project but they can be applied anywhere a distributed consensus needs to be established in the presence of malicious or untrustworthy actors.

Whilst it's possible to abuse the Bitcoin financial block chain for other purposes, it's better to set up an alternative network and chain which share the same miners. There are several reasons to do this.

* The block chain is a large, complex data structure shared between many people. Verifying its integrity requires many slow (and thus expensive) operations like ECDSA verifications and disk seeks. Everyone who takes part in Bitcoin today runs a node and thus maintains the whole thing. Whilst in future end-users will probably use more efficient but slightly less secure modes (SPV), merchants and miners will probably always pay the full costs for the upkeep of this shared data structure. All these people today are united by a common interest in a new form of payments. They may or may not also be interested in other schemes. So one reason to keep the Bitcoin chain for finance is it's unfair to externalize the costs of unrelated schemes onto people who are interested only in payments - the canonical example being merchants. Increasing the cost of accepting Bitcoins for goods and services hurts everyone who uses the system by reducing the number of merchants or increasing their costs.

* Another reason is that it's just bad engineering to cram every possible distributed quorum into the design constraints of Bitcoin. The transaction format Bitcoin uses is flexible but ultimately designed for finance. You cannot leave out the "value" field. It's always there, even if it'd make no sense for your particular application. Building non-financial applications on top of a financial system results in bizarre protocols and code that are difficult to understand, leading to maintainability problems.

* One final reason is that [[Satoshi Nakamoto|Satoshi]] was opposed to putting non-Bitcoin related data into the main chain. As creator of the system, his opinion should carry a lot of weight with anyone serious about extending it.

=== Designing a new network ===

To create a new network that uses Nakamoto block chains, you need to start by defining what a transaction in your new network means. Bitcoin transactions split and combine value using scripts, but yours don't have to do that. They could be anything. Here's an example of a simple DNS style "transaction" described using [http://code.google.com/p/protobuf/ Google protocol buffers] syntax.

message NameTx {
required string name = 1;
repeated bytes ip_addresses = 2;
required bytes pubkey = 3;
enum ClaimType {
NEW_NAME,
TRANSFER
}
required ClaimType type = 4;

// Only used if type == TRANSFER. The new owner of the name and signature proving current ownership.
optional bytes dest_pubkey = 5;
optional bytes signature = 6;
}

This is very different to a Bitcoin style transaction. There's no concept of inputs, outputs, addresses, values or scripts. It's got what you need for a very simple DNS style scheme (that lacks abuse controls etc) and nothing more. There's also no concept of a "coinbase" transaction.

The block definition is also up to you. It does not have to be formatted in the same way as Satoshi chose, but you need most of the same conceptual parts. You also need to store something else, some data from Bitcoin. Here's a minimal example of what's needed:

message MyBlock {
required bytes prev_block_hash = 1;
required uint32 difficulty = 2;
required uint32 time = 3;

repeated MyTx transactions = 4;
}

message SuperBlock {
required MyBlock my_data = 1;
required BitcoinData bitcoin_data = 2;
}

It's important to observe what we don't have as well as what we do. We don't have the following fields from Satoshis format:

# version: protobufs handles the versioning of binary data formats for us
# merkle root: you can choose to arrange your transactions into a merkle root if you like, so you can use the same disk space reclamation trick Satoshi did. But it's strictly optional. If you want to simplify things down you can skip it.
# nonce

== Sharing work ==

The bitcoin_data field is how you share work with miners today (assuming they opt in by installing your software alongside their bitcoin node). It's defined like this:

message BitcoinData {
// A Bitcoin format block header. Because it's in Satoshis custom format we represent this as a byte array.
required bytes header = 1;

// The first transaction from the block.
required bytes coinbase_tx = 2;

// The merkle branch linking the coinbase transaction to the header.
required bytes coinbase_merkle_branch = 3;

// The coinbase scriptSig contains bits of data in order. Which one is our hash?
required int coinbase_tx_index = 4;
}

All you need to share work is the above four things.

A [[wikipedia:Merkle tree]] is a data structure in which each node in the tree is a hash. The leaf nodes are hashes of the things you want to include in the tree. The interior nodes are hashes of the concatenations of the child nodes. A merkle branch is a part of a merkle tree which allows you to cryptographically prove that something you're given was in the tree, without needing everything that was in the tree. They are calculated by the CBlock::GetMerkleBranch() function in the Bitcoin code.

We store a merkle branch here for efficiency. It means no matter how large the current Bitcoin block is, your alternative network only needs to handle a small amount of data. You could just store the entire Bitcoin block - that would be simpler but inefficient.

The merkle branch links the coinbase transaction to the block header, so you can prove it was in that block. The coinbase TX is a regular Bitcoin coinbase (that makes new coins and claims fees), except the scriptSig on its input contains an extra entry that todays scriptSigs don't. That extra entry is a hash of your block structure. The coinbase scriptSig today is formatted like this:

void IncrementExtraNonce(CBlock* pblock, CBlockIndex* pindexPrev, unsigned int& nExtraNonce, int64& nPrevTime)
{
.....
pblock->vtx[0].vin[0].scriptSig = CScript() << pblock->nBits << CBigNum(nExtraNonce);
.....
}

Just the difficulty bits and the "extra nonce". But it's actually allowed to contain anything, as long as it's not too big. So in your new blocks it'd be:

<MyBlock hash> <nBits> <nExtraNonce>

To get the MyBlock hash into Bitcoin requires a presently unimplemented RPC command, "setextrahashes". It'd update a global list and the IncrementExtraNonce function would include the extra hashes when the scriptSig is built. This is a very simple change to Bitcoin.

In the scriptSig above the coinbase_tx_index would be zero. It's possible to work on an arbitrary number of alternative chains simultaneously:

<MyBlock hash> <SomeOtherChainBlock hash> <nBits> <nExtraNonce>

in which case the BitcoinData message for SomeOtherChain would be 1 rather than zero.

A more complex change is the other new RPC. Because you have your own chain, it has its own difficulty. Most likely it'll be different to Bitcoins own. So you need a way to tell Bitcoin "when you find a block that matches an extradifficulty, please let me know". To mine on multiple difficulties at once, the node vends work (via getwork) matching the easiest difficulty. When a miner reports finding a solution the difficulty is checked to see which chains it is sufficiently difficult for.

Important note: Your chain has its own difficulty and as such the block creation rate is independent of how much mining takes place.

== Independent node software ==

Your new network has its own codebase. It can be written in whatever language you like, use whatever P2P protocol you like, store its data however you like and so on.

When a node on your network receives a message informing it about a new transaction, it verifies that transaction follows the rules of your network. To use our simple DNS example it would verify that if you're claiming a new name, it doesn't already exist and if you're transferring a name that the signatures are correct.

If the transaction is valid, it's added to your current MyBlock message. That message is serialized to binary (protobufs does this for you), hashed and then your node makes an RPC to Bitcoin telling it what the current extra hash is. When Bitcoin finds a Bitcoin-format block of the right difficulty for your network, it informs your software and passes the block header, coinbase transaction and merkle branch to it. Your node combines them together into a BitcoinData message, which is then glued together with your alternative chains block. This "superblock" is then broadcast via your independent P2P network.

When a node on your new network receives a superblock it does the following things:

# Verifies the MyBlock contents are correct, ie, that the transactions follow the rules.
# Verifies that the MyBlock prev hash makes it fit somewhere in the chain and that the difficulty is correct.
# Hashes the MyBlock structure and then verifies that this hash appears in the BitcoinData coinbase scriptSig, in the right place.
# Extracts the merkle root of the Bitcoin format block from the header and then verifies that the coinbase tx provided did, in fact, exist in that block (using the branch, root, tx and header together).
# Verifies that the hash of the Bitcoin format block header is below the difficulty found in the MyBlock structure.

You've now verified that a sufficiently hard proof of work was done over the contents of the MyBlock structure, so your node can relay the newly found block (or if you don't use a P2P network make it available on your server, etc).

On the other side when Bitcoin finds a block that is correct for the Bitcoin network and chain, it broadcasts it and obviously the hash of your MyBlock is included. Fortunately this is only an additional 33 bytes overhead so nobody cares about it - the pollution of the financial chain is both trivial and constant. Note that regular Bitcoin nodes just ignore this extra hash, it doesn't mean anything to them.

== Handling your new block chain ==

You have to handle re-organizations. This is a standard part of the block chain algorithm. When a re-org occurs you have to verify that the state of your world still makes sense. For example in the new chain maybe somebody else now owns a resource you thought you owned. It's up to you how to inform your users of these events and what app specific logic is appropriate here.

You can choose your own parameters for the new chain. As an example, Satoshi chose to target one new block every ten minutes as a tradeoff between latency and wasted work. You could choose something much larger (hours, days) or much faster if you're willing to tolerate more splits due to blocks being found simultaneously. Bitcoin retargets the difficulty roughly every two weeks. You could choose some other length of time.

To store the block chain, Satoshi chose to use Berkeley DB as a way to index from transactions to the blocks they appeared in (amongst other things). You could use any database you liked.

== Paying for resources on alternative chains with Bitcoins ==

A commonly cited reason for putting DNS related data into the financial chain is the desire to pay for names with Bitcoins. You can do this with an independent chain too, because you make the rules and can link the two chains together as you see fit.

To start, decide on the purpose of your payments and who will receive the coins - if anyone. In the case of a DNS system, there are two reasons you might want to pay for names:

# To prevent abuse by people claiming all interesting names via a dictionary attack.
# To incentivise people to run your software and mine on your alternative chain.

In the first case really nobody should receive the payment. The money is being put up as a collateral and has no other use, so as long as it's sitting around unspent that is good enough. In the second case the payment should go to the miner working on the DNS chain.

To implement this we extend our hypothetical DNS transaction message like this:

message NameTx {
required string name = 1;
repeated bytes ip_addresses = 2;
required bytes pubkey = 3;
enum ClaimType {
NEW_NAME,
TRANSFER
}
required ClaimType type = 4;

// Only used if type == TRANSFER. The new owner of the name and signature proving current ownership.
optional bytes dest_pubkey = 5;
optional bytes signature = 6;

// Only used if type == NEW_NAME.
optional bytes collateral_signature = 7;
optional string miner_address = 8;
optional uint64 miner_fee = 9;
}

The collateral_signature field contains an ECDSA signature generated from a public key that holds some Bitcoins. The miner address is blank when the name purchaser creates the transaction and is filled out after a miner receives it, but before they begin working on it.

To buy a name that costs 10 BTC with a miner fee of 2 BTC, a user presses the "buy name" button in their DNS software. It talks to their local Bitcoin node via RPC and does the following:

# Creates a new Bitcoin address (key).
# Sends 10 BTC to the new address (a send-to-self transaction).
# Extracts the key from Bitcoin, meaning it's no longer available to spend in your wallet.
# Stores the key in a local DNS data file ("wallet") somewhere.
# Sets the miner_fee field to the pre-agreed value of 2 BTC.
# Takes the public key part and uses it to sign a version of the NameTx that lacks collateral_signature (a signature can't sign itself) and miner_address.
# The signature is placed in collateral_signature field.
# The transaction is sent to a miner who charges 2 BTC.

When the miner receives the transaction, it verifies that the 10 BTC is not spent:

# The ECDSA public key recovery algorithm is run on the collateral_signature. It can yield several possible keys.
# The public keys recovered are used to verify the signature is correct. This step also figures out which of the possible keys is the right one.
# The correct public key is turned into a Bitcoin address (by hashing it)
# The DNS node software queries Bitcoin to discover whether that address has 10 BTC associated with it, or whether the balance of that address is lower. Note that todays software does not index the balance of every address in the system, but it can be added (the Block Explorer does this).
# If the address does indeed have 10 unspent Bitcoins then the collateral is present and it's OK to serve the name

The miner then creates a new Bitcoin address for themselves and sets miner_address to contain it, then includes it into the current block being worked on. After a block matching the DNS chains difficulty is found, it is broadcast. Other nodes do the following:

# For each transaction, repeat the verification steps to ensure the collateral is not spent.
# Check the balance of the miners own address.
# If the balance is not yet equal to miner_fee, the name is put into a "pending" state in which it is owned but not served in response to DNS queries.

The user observes the broadcast and sees that their name is now pending payment, so they send 2 BTC to the address they find in their transaction. As nodes notice the payment becoming confirmed they start responding to DNS queries for that name (ie, the ownership process is complete).

When the user gets tired of owning the name, he can simply re-import the collateral key into his wallet and spend the coins. The DNS network will soon observe that the coins are spent and make the name available for purchasing by somebody else.

== Incentivising non-resource based chains ==

It's possible to incentivise mining on an alt-chain even if that chain does not have any concept of ownership, ie, if the act of finding a block itself is what is being paid for. An example of this is a timestamping chain in which presence in a block alone is sufficient to satisfy the user.

To implement this, set up a new chain as normal. Blocks in this new chain arrange transactions into a merkle tree in the same manner as Bitcoin does. A client that wants something incorporated into a block connects directly to some miners and submits their transaction. The miners add their address to the transaction as normal. Once a miner finds a block, it immediately sends the block to connected clients whose transactions made it in, but does not broadcast the new block to other miners. The clients respond with a valid Bitcoin transaction which pays for block inclusion. Once all clients have paid up the transaction is broadcast.

If a client has disconnected or does not pay quickly enough, their transaction can be replaced inside the block with its hash. In this way the blocks validity is preserved because the merkle tree is still valid. The newly found alt-block is broadcast, minus the transaction of the delinquent customer. As long as clients are still connected the payment process for all found transactions can be completed quickly: it would only take a few seconds to gather the payments and broadcast those on the Bitcoin network, minimizing the chance of a race that would require you to trust the miner to reinclude your transactions in the next block despite having already been paid.

== Mining on the alt-chain but not Bitcoin ==

So far we've considered a scheme in which all alt-chain miners simultaneously mine on Bitcoin. It's possible some people may wish to mine on your chain but not Bitcoin, perhaps because the cost of keeping up with the Bitcoin transaction rate has become too high for them to bother.

To mine without an attached Bitcoin node, your software can simply implement the same getwork protocol Bitcoin itself does. When a mining tool requests work your program would generate a correctly formatted but ultimately bogus Bitcoin block. The contents of this block don't need to be correct because it will never be broadcast on the Bitcoin network, for example, the prevBlockHash field can be all zeros. It exists purely for backwards compatibility. Whilst the block needs a valid merkle root and a coinbase transaction, no other transactions are required and the only part of the coinbase tx that matters is the part holding the hash.

== Scaling up ==

In the simple scheme each alt-chain being worked on needs 33 bytes in the Bitcoin coinbase transaction (1 for the length and 32 for the hash). Note that if there are two independent miners working on two different alt-chains, you still only need 1 hash in the coinbase scriptSig because the hash isn't meaningful to anyone else on the Bitcoin network. If miners only want to work a handful of chains this overhead is trivially dwarfed by the rest of the data in a Bitcoin block.

But if a miner wishes to work on hundreds, thousands or millions of alternative chains the size of the coinbase scriptSig would balloon and become unworkable. To solve this, the hash stored in the scriptSig can be the root of yet another merkle tree, this time a tree over the hashes of all blocks being worked on. The BitcoinData message is extended like this:

message MyBlock {
required bytes prev_block_hash = 1;
required uint32 difficulty = 2;
required uint32 time = 3;

repeated MyTx transactions = 4;
}

message SuperBlock {
required MyBlock my_data = 1;
required BitcoinData bitcoin_data = 2;
}

message BitcoinData {
// A Bitcoin format block header. Because it's in Satoshis custom format we represent this as a byte array.
required bytes header = 1;

// The first transaction from the block.
required bytes coinbase_tx = 2;

// The merkle branch linking the coinbase transaction to the header.
required bytes coinbase_merkle_branch = 3;

// The merkle branch linking MyBlock to the merkle root in the coinbase_tx.
required bytes altblock_merkle_branch = 4;
}

The verification step becomes a bit more complex:

# Verify the header is of sufficient difficulty for the alt-chain
# Verify coinbase_tx was a part of that block by checking the coinbase_merkle_branch is linked to the merkle root in the header.
# Extract the root of the second merkle tree from the coinbase_tx (call it 2MR).
# Hash the alt-chain block (my_data), verify that altblock_merkle_branch links the my_data hash to 2MR.

You have now proven that the MyBlock instance was worked on, along with perhaps thousands of other chains you don't have to know anything about.

This is an advanced technique which is probably not worth implementing unless the additional scalability is required. It can be introduced in a backwards compatible manner for new chains without impacting older networks.

=== Protecting against double proof ===

The merkle tree approach to scalability comes with a caveat. If naïvely implemented, a miner could cheat the proof-of-work system by putting more than one alt-chain block header into one Bitcoin block. This "cheating" would not cause a problem if the alt-chain blocks all had the same previous-block hash: one or another would win the race, as happens when competing blocks enter the network. The problem would arise if a linked series of alt-chain blocks all existed in one Bitcoin block's auxiliary merkle trees. The miner could work on them all at once, getting more from his hashes than difficulty warrants.

Namecoin's [http://dot-bit.org/forum/viewtopic.php?f=5&t=269&start=11 solution] is to constrain the paths by which alt-chain blocks may be embedded in Bitcoin blocks. This works, but it complicates the picture for miners and chain designers in a future with many alternative chains.

Perhaps a better solution for new chains is to prevent the existence of linked series of alt-chain blocks which lack proof of work. For example, one could require each aux chain block to refer (perhaps via its own coinbase or a new header field) to the "solution" (target-meeting hash of parent chain block) as well as the hash of the previous block in the alt chain. (In Bitcoin, these two hashes are the same.) This would force blocks to refer not just to the previous block in the chain but to the proof of work on that block. A series of alt-chain blocks all being worked on would not make sense, because the second block in the series would have to reference the first block's solution, so the first block would have to have been solved.

== Generalized proof of work ==

Hashes embedded in transactions and headers, merkle branches, and [[Nonce|nonces]] all contribute to the goal of [[Proof of work|proving work]] on a block header. One can express all as sequences of these basic operations:

* prepend a byte string to the current data
* append a byte string to the current data
* hash the current data

For maximum flexibility, a work-sharing chain's block acceptance algorithm might accept proof in the form of a script using just these operations. The script would receive as input an alternative chain block header, and the hash of its output would have to satisfy the chain's difficulty.

This design would even support plain Bitcoin proof of work, where the "header" consists of all [[Protocol Specification#block|Bitcoin block header fields]] except the nonce, and the proof-of-work script simply appends the nonce. Thus, one can think of the work-sharing rules as an extension of the original Bitcoin rules.

==External Links==

* [https://bitcointalk.org/index.php?topic=6197.0 BitDNS in the words of Satoshi]
* [http://dot-bit.org/Merged_Mining Merged Mining] in Namecoin
* [http://dot-bit.org/forum/viewtopic.php?f=5&t=269 Namecoin forum discussion]
* [https://bitcointalk.org/index.php?topic=46927.msg572981#msg572981 Forum thread about double proof]

[[Category:Technical]]

Alternative chain

2011-10-16T04:09:51Z

JohnTobey253: Added section: Protecting against double proof

An '''alternative chain''' is a system using the block chain algorithm to achieve distributed consensus on a particular topic, whilst sharing miners with the Bitcoin network. Alternative chains have been suggested as ways to implement DNS, SSL certificate authorities, timestamping, file storage and voting systems.

== Objective ==

Bitcoin uses the [[block chain]] algorithm to achieve distributed consensus on who owns what coins. Block chains were invented specifically for the Bitcoin project but they can be applied anywhere a distributed consensus needs to be established in the presence of malicious or untrustworthy actors.

Whilst it's possible to abuse the Bitcoin financial block chain for other purposes, it's better to set up an alternative network and chain which share the same miners. There are several reasons to do this.

* The block chain is a large, complex data structure shared between many people. Verifying its integrity requires many slow (and thus expensive) operations like ECDSA verifications and disk seeks. Everyone who takes part in Bitcoin today runs a node and thus maintains the whole thing. Whilst in future end-users will probably use more efficient but slightly less secure modes (SPV), merchants and miners will probably always pay the full costs for the upkeep of this shared data structure. All these people today are united by a common interest in a new form of payments. They may or may not also be interested in other schemes. So one reason to keep the Bitcoin chain for finance is it's unfair to externalize the costs of unrelated schemes onto people who are interested only in payments - the canonical example being merchants. Increasing the cost of accepting Bitcoins for goods and services hurts everyone who uses the system by reducing the number of merchants or increasing their costs.

* Another reason is that it's just bad engineering to cram every possible distributed quorum into the design constraints of Bitcoin. The transaction format Bitcoin uses is flexible but ultimately designed for finance. You cannot leave out the "value" field. It's always there, even if it'd make no sense for your particular application. Building non-financial applications on top of a financial system results in bizarre protocols and code that are difficult to understand, leading to maintainability problems.

* One final reason is that [[Satoshi Nakamoto|Satoshi]] was opposed to putting non-Bitcoin related data into the main chain. As creator of the system, his opinion should carry a lot of weight with anyone serious about extending it.

=== Designing a new network ===

To create a new network that uses Nakamoto block chains, you need to start by defining what a transaction in your new network means. Bitcoin transactions split and combine value using scripts, but yours don't have to do that. They could be anything. Here's an example of a simple DNS style "transaction" described using [http://code.google.com/p/protobuf/ Google protocol buffers] syntax.

message NameTx {
required string name = 1;
repeated bytes ip_addresses = 2;
required bytes pubkey = 3;
enum ClaimType {
NEW_NAME,
TRANSFER
}
required ClaimType type = 4;

// Only used if type == TRANSFER. The new owner of the name and signature proving current ownership.
optional bytes dest_pubkey = 5;
optional bytes signature = 6;
}

This is very different to a Bitcoin style transaction. There's no concept of inputs, outputs, addresses, values or scripts. It's got what you need for a very simple DNS style scheme (that lacks abuse controls etc) and nothing more. There's also no concept of a "coinbase" transaction.

The block definition is also up to you. It does not have to be formatted in the same way as Satoshi chose, but you need most of the same conceptual parts. You also need to store something else, some data from Bitcoin. Here's a minimal example of what's needed:

message MyBlock {
required bytes prev_block_hash = 1;
required uint32 difficulty = 2;
required uint32 time = 3;

repeated MyTx transactions = 4;
}

message SuperBlock {
required MyBlock my_data = 1;
required BitcoinData bitcoin_data = 2;
}

It's important to observe what we don't have as well as what we do. We don't have the following fields from Satoshis format:

# version: protobufs handles the versioning of binary data formats for us
# merkle root: you can choose to arrange your transactions into a merkle root if you like, so you can use the same disk space reclamation trick Satoshi did. But it's strictly optional. If you want to simplify things down you can skip it.
# nonce

== Sharing work ==

The bitcoin_data field is how you share work with miners today (assuming they opt in by installing your software alongside their bitcoin node). It's defined like this:

message BitcoinData {
// A Bitcoin format block header. Because it's in Satoshis custom format we represent this as a byte array.
required bytes header = 1;

// The first transaction from the block.
required bytes coinbase_tx = 2;

// The merkle branch linking the coinbase transaction to the header.
required bytes coinbase_merkle_branch = 3;

// The coinbase scriptSig contains bits of data in order. Which one is our hash?
required int coinbase_tx_index = 4;
}

All you need to share work is the above four things.

A [[wikipedia:Merkle tree]] is a data structure in which each node in the tree is a hash. The leaf nodes are hashes of the things you want to include in the tree. The interior nodes are hashes of the concatenations of the child nodes. A merkle branch is a part of a merkle tree which allows you to cryptographically prove that something you're given was in the tree, without needing everything that was in the tree. They are calculated by the CBlock::GetMerkleBranch() function in the Bitcoin code.

We store a merkle branch here for efficiency. It means no matter how large the current Bitcoin block is, your alternative network only needs to handle a small amount of data. You could just store the entire Bitcoin block - that would be simpler but inefficient.

The merkle branch links the coinbase transaction to the block header, so you can prove it was in that block. The coinbase TX is a regular Bitcoin coinbase (that makes new coins and claims fees), except the scriptSig on its input contains an extra entry that todays scriptSigs don't. That extra entry is a hash of your block structure. The coinbase scriptSig today is formatted like this:

void IncrementExtraNonce(CBlock* pblock, CBlockIndex* pindexPrev, unsigned int& nExtraNonce, int64& nPrevTime)
{
.....
pblock->vtx[0].vin[0].scriptSig = CScript() << pblock->nBits << CBigNum(nExtraNonce);
.....
}

Just the difficulty bits and the "extra nonce". But it's actually allowed to contain anything, as long as it's not too big. So in your new blocks it'd be:

<MyBlock hash> <nBits> <nExtraNonce>

To get the MyBlock hash into Bitcoin requires a presently unimplemented RPC command, "setextrahashes". It'd update a global list and the IncrementExtraNonce function would include the extra hashes when the scriptSig is built. This is a very simple change to Bitcoin.

In the scriptSig above the coinbase_tx_index would be zero. It's possible to work on an arbitrary number of alternative chains simultaneously:

<MyBlock hash> <SomeOtherChainBlock hash> <nBits> <nExtraNonce>

in which case the BitcoinData message for SomeOtherChain would be 1 rather than zero.

A more complex change is the other new RPC. Because you have your own chain, it has its own difficulty. Most likely it'll be different to Bitcoins own. So you need a way to tell Bitcoin "when you find a block that matches an extradifficulty, please let me know". To mine on multiple difficulties at once, the node vends work (via getwork) matching the easiest difficulty. When a miner reports finding a solution the difficulty is checked to see which chains it is sufficiently difficult for.

Important note: Your chain has its own difficulty and as such the block creation rate is independent of how much mining takes place.

== Independent node software ==

Your new network has its own codebase. It can be written in whatever language you like, use whatever P2P protocol you like, store its data however you like and so on.

When a node on your network receives a message informing it about a new transaction, it verifies that transaction follows the rules of your network. To use our simple DNS example it would verify that if you're claiming a new name, it doesn't already exist and if you're transferring a name that the signatures are correct.

If the transaction is valid, it's added to your current MyBlock message. That message is serialized to binary (protobufs does this for you), hashed and then your node makes an RPC to Bitcoin telling it what the current extra hash is. When Bitcoin finds a Bitcoin-format block of the right difficulty for your network, it informs your software and passes the block header, coinbase transaction and merkle branch to it. Your node combines them together into a BitcoinData message, which is then glued together with your alternative chains block. This "superblock" is then broadcast via your independent P2P network.

When a node on your new network receives a superblock it does the following things:

# Verifies the MyBlock contents are correct, ie, that the transactions follow the rules.
# Verifies that the MyBlock prev hash makes it fit somewhere in the chain and that the difficulty is correct.
# Hashes the MyBlock structure and then verifies that this hash appears in the BitcoinData coinbase scriptSig, in the right place.
# Extracts the merkle root of the Bitcoin format block from the header and then verifies that the coinbase tx provided did, in fact, exist in that block (using the branch, root, tx and header together).
# Verifies that the hash of the Bitcoin format block header is below the difficulty found in the MyBlock structure.

You've now verified that a sufficiently hard proof of work was done over the contents of the MyBlock structure, so your node can relay the newly found block (or if you don't use a P2P network make it available on your server, etc).

On the other side when Bitcoin finds a block that is correct for the Bitcoin network and chain, it broadcasts it and obviously the hash of your MyBlock is included. Fortunately this is only an additional 33 bytes overhead so nobody cares about it - the pollution of the financial chain is both trivial and constant. Note that regular Bitcoin nodes just ignore this extra hash, it doesn't mean anything to them.

== Handling your new block chain ==

You have to handle re-organizations. This is a standard part of the block chain algorithm. When a re-org occurs you have to verify that the state of your world still makes sense. For example in the new chain maybe somebody else now owns a resource you thought you owned. It's up to you how to inform your users of these events and what app specific logic is appropriate here.

You can choose your own parameters for the new chain. As an example, Satoshi chose to target one new block every ten minutes as a tradeoff between latency and wasted work. You could choose something much larger (hours, days) or much faster if you're willing to tolerate more splits due to blocks being found simultaneously. Bitcoin retargets the difficulty roughly every two weeks. You could choose some other length of time.

To store the block chain, Satoshi chose to use Berkeley DB as a way to index from transactions to the blocks they appeared in (amongst other things). You could use any database you liked.

== Paying for resources on alternative chains with Bitcoins ==

A commonly cited reason for putting DNS related data into the financial chain is the desire to pay for names with Bitcoins. You can do this with an independent chain too, because you make the rules and can link the two chains together as you see fit.

To start, decide on the purpose of your payments and who will receive the coins - if anyone. In the case of a DNS system, there are two reasons you might want to pay for names:

# To prevent abuse by people claiming all interesting names via a dictionary attack.
# To incentivise people to run your software and mine on your alternative chain.

In the first case really nobody should receive the payment. The money is being put up as a collateral and has no other use, so as long as it's sitting around unspent that is good enough. In the second case the payment should go to the miner working on the DNS chain.

To implement this we extend our hypothetical DNS transaction message like this:

message NameTx {
required string name = 1;
repeated bytes ip_addresses = 2;
required bytes pubkey = 3;
enum ClaimType {
NEW_NAME,
TRANSFER
}
required ClaimType type = 4;

// Only used if type == TRANSFER. The new owner of the name and signature proving current ownership.
optional bytes dest_pubkey = 5;
optional bytes signature = 6;

// Only used if type == NEW_NAME.
optional bytes collateral_signature = 7;
optional string miner_address = 8;
optional uint64 miner_fee = 9;
}

The collateral_signature field contains an ECDSA signature generated from a public key that holds some Bitcoins. The miner address is blank when the name purchaser creates the transaction and is filled out after a miner receives it, but before they begin working on it.

To buy a name that costs 10 BTC with a miner fee of 2 BTC, a user presses the "buy name" button in their DNS software. It talks to their local Bitcoin node via RPC and does the following:

# Creates a new Bitcoin address (key).
# Sends 10 BTC to the new address (a send-to-self transaction).
# Extracts the key from Bitcoin, meaning it's no longer available to spend in your wallet.
# Stores the key in a local DNS data file ("wallet") somewhere.
# Sets the miner_fee field to the pre-agreed value of 2 BTC.
# Takes the public key part and uses it to sign a version of the NameTx that lacks collateral_signature (a signature can't sign itself) and miner_address.
# The signature is placed in collateral_signature field.
# The transaction is sent to a miner who charges 2 BTC.

When the miner receives the transaction, it verifies that the 10 BTC is not spent:

# The ECDSA public key recovery algorithm is run on the collateral_signature. It can yield several possible keys.
# The public keys recovered are used to verify the signature is correct. This step also figures out which of the possible keys is the right one.
# The correct public key is turned into a Bitcoin address (by hashing it)
# The DNS node software queries Bitcoin to discover whether that address has 10 BTC associated with it, or whether the balance of that address is lower. Note that todays software does not index the balance of every address in the system, but it can be added (the Block Explorer does this).
# If the address does indeed have 10 unspent Bitcoins then the collateral is present and it's OK to serve the name

The miner then creates a new Bitcoin address for themselves and sets miner_address to contain it, then includes it into the current block being worked on. After a block matching the DNS chains difficulty is found, it is broadcast. Other nodes do the following:

# For each transaction, repeat the verification steps to ensure the collateral is not spent.
# Check the balance of the miners own address.
# If the balance is not yet equal to miner_fee, the name is put into a "pending" state in which it is owned but not served in response to DNS queries.

The user observes the broadcast and sees that their name is now pending payment, so they send 2 BTC to the address they find in their transaction. As nodes notice the payment becoming confirmed they start responding to DNS queries for that name (ie, the ownership process is complete).

When the user gets tired of owning the name, he can simply re-import the collateral key into his wallet and spend the coins. The DNS network will soon observe that the coins are spent and make the name available for purchasing by somebody else.

== Incentivising non-resource based chains ==

It's possible to incentivise mining on an alt-chain even if that chain does not have any concept of ownership, ie, if the act of finding a block itself is what is being paid for. An example of this is a timestamping chain in which presence in a block alone is sufficient to satisfy the user.

To implement this, set up a new chain as normal. Blocks in this new chain arrange transactions into a merkle tree in the same manner as Bitcoin does. A client that wants something incorporated into a block connects directly to some miners and submits their transaction. The miners add their address to the transaction as normal. Once a miner finds a block, it immediately sends the block to connected clients whose transactions made it in, but does not broadcast the new block to other miners. The clients respond with a valid Bitcoin transaction which pays for block inclusion. Once all clients have paid up the transaction is broadcast.

If a client has disconnected or does not pay quickly enough, their transaction can be replaced inside the block with its hash. In this way the blocks validity is preserved because the merkle tree is still valid. The newly found alt-block is broadcast, minus the transaction of the delinquent customer. As long as clients are still connected the payment process for all found transactions can be completed quickly: it would only take a few seconds to gather the payments and broadcast those on the Bitcoin network, minimizing the chance of a race that would require you to trust the miner to reinclude your transactions in the next block despite having already been paid.

== Mining on the alt-chain but not Bitcoin ==

So far we've considered a scheme in which all alt-chain miners simultaneously mine on Bitcoin. It's possible some people may wish to mine on your chain but not Bitcoin, perhaps because the cost of keeping up with the Bitcoin transaction rate has become too high for them to bother.

To mine without an attached Bitcoin node, your software can simply implement the same getwork protocol Bitcoin itself does. When a mining tool requests work your program would generate a correctly formatted but ultimately bogus Bitcoin block. The contents of this block don't need to be correct because it will never be broadcast on the Bitcoin network, for example, the prevBlockHash field can be all zeros. It exists purely for backwards compatibility. Whilst the block needs a valid merkle root and a coinbase transaction, no other transactions are required and the only part of the coinbase tx that matters is the part holding the hash.

== Scaling up ==

In the simple scheme each alt-chain being worked on needs 33 bytes in the Bitcoin coinbase transaction (1 for the length and 32 for the hash). Note that if there are two independent miners working on two different alt-chains, you still only need 1 hash in the coinbase scriptSig because the hash isn't meaningful to anyone else on the Bitcoin network. If miners only want to work a handful of chains this overhead is trivially dwarfed by the rest of the data in a Bitcoin block.

But if a miner wishes to work on hundreds, thousands or millions of alternative chains the size of the coinbase scriptSig would balloon and become unworkable. To solve this, the hash stored in the scriptSig can be the root of yet another merkle tree, this time a tree over the hashes of all blocks being worked on. The BitcoinData message is extended like this:

message MyBlock {
required bytes prev_block_hash = 1;
required uint32 difficulty = 2;
required uint32 time = 3;

repeated MyTx transactions = 4;
}

message SuperBlock {
required MyBlock my_data = 1;
required BitcoinData bitcoin_data = 2;
}

message BitcoinData {
// A Bitcoin format block header. Because it's in Satoshis custom format we represent this as a byte array.
required bytes header = 1;

// The first transaction from the block.
required bytes coinbase_tx = 2;

// The merkle branch linking the coinbase transaction to the header.
required bytes coinbase_merkle_branch = 3;

// The merkle branch linking MyBlock to the merkle root in the coinbase_tx.
required bytes altblock_merkle_branch = 4;
}

The verification step becomes a bit more complex:

# Verify the header is of sufficient difficulty for the alt-chain
# Verify coinbase_tx was a part of that block by checking the coinbase_merkle_branch is linked to the merkle root in the header.
# Extract the root of the second merkle tree from the coinbase_tx (call it 2MR).
# Hash the alt-chain block (my_data), verify that altblock_merkle_branch links the my_data hash to 2MR.

You have now proven that the MyBlock instance was worked on, along with perhaps thousands of other chains you don't have to know anything about.

This is an advanced technique which is probably not worth implementing unless the additional scalability is required. It can be introduced in a backwards compatible manner for new chains without impacting older networks.

=== Protecting against double proof ===

The merkle tree approach to scalability comes with a caveat. If naïvely implemented, a miner could cheat the proof-of-work system by putting more than one alt-chain block header into one Bitcoin block. This "cheating" would not cause a problem if the alt-chain blocks all had the same previous-block hash: one or another would win the race, as happens when competing blocks enter the network. The problem would arise if a linked series of alt-chain blocks all existed in one Bitcoin block's auxiliary merkle trees. The miner could work on them all at once, getting more from his hashes than difficulty warrants.

Namecoin's [http://dot-bit.org/forum/viewtopic.php?f=5&t=269&start=11 solution] is to constrain the paths by which alt-chain blocks may be embedded in Bitcoin blocks. This works, but it complicates the picture for miners and chain designers in a future with many alternative chains.

Perhaps a better solution for new chains is to prevent the existence of linked series of alt-chain blocks which lack proof of work. For example, one could require each aux chain block to refer (perhaps via its own coinbase or a new header field) to the "solution" (target-meeting hash of parent chain block) as well as the hash of the previous block in the alt chain. (In Bitcoin, these two hashes are the same.) This would force blocks to refer not just to the previous block in the chain but to the proof of work on that block. A series of alt-chain blocks all being worked on would not make sense, because the second block in the series would have to reference the first block's solution, so the first block would have to have been solved.

== Generalized proof of work ==

Hashes embedded in transactions and headers, merkle branches, and [[Nonce|nonces]] all contribute to the goal of [[Proof of work|proving work]] on a block header. One can express all as sequences of these basic operations:

* prepend a byte string to the current data
* append a byte string to the current data
* hash the current data

For maximum flexibility, a work-sharing chain's block acceptance algorithm might accept proof in the form of a script using just these operations. The script would receive as input an alternative chain block header, and the hash of its output would have to satisfy the chain's difficulty.

This design would even support plain Bitcoin proof of work, where the "header" consists of all [[Protocol Specification#block|Bitcoin block header fields]] except the nonce, and the proof-of-work script simply appends the nonce. Thus, one can think of the work-sharing rules as an extension of the original Bitcoin rules.

==External Links==

* [https://bitcointalk.org/index.php?topic=6197.0 BitDNS in the words of Satoshi]
* [http://dot-bit.org/Merged_Mining Merged Mining] in Namecoin
* [http://dot-bit.org/forum/viewtopic.php?f=5&t=269 Namecoin forum discussion]
* [https://bitcointalk.org/index.php?topic=46927.msg572981#msg572981 Forum thread about double proof]

[[Category:Technical]]

Abe

2011-10-16T02:59:34Z

JohnTobey253: Updated links

[[File:penny-abe-160.png|thumb|160px|Abe]]

'''Abe''' is a free, open-source [[block chain browser]] released by [[User:JohnTobey253|John Tobey]] under the [[wikipedia:Affero General Public License|Affero General Public License]].

Written in [[wikipedia:Python (programming language)|Python]] and portable [[wikipedia:SQL|SQL]],<ref>https://forum.bitcoin.org/index.php?topic=16141.0</ref> Abe draws inspiration from [[Bitcoin Block Explorer]] and seeks some level of compatibility with it but uses a completely new implementation.<ref>https://raw.github.com/jtobey/bitcoin-abe/master/README.md</ref>

==See Also==

* [[Block chain browser]]

== External Links ==

* [http://abe.john-edwin-tobey.org/ Demonstration site]
* [https://bitcointalk.org/index.php?topic=16141.0 Project announcement]
* [https://github.com/jtobey/bitcoin-abe Project on Github]

==References==
<references />

[[Category:Block chain browsers]]
[[Category:Free Software]]
[[Category:Open Source]]

Alternative chain

2011-09-13T04:56:24Z

JohnTobey253: External links

An '''alternative chain''' is a system using the block chain algorithm to achieve distributed consensus on a particular topic, whilst sharing miners with the Bitcoin network. Alternative chains have been suggested as ways to implement DNS, SSL certificate authorities, timestamping, file storage and voting systems.

== Objective ==

Bitcoin uses the [[block chain]] algorithm to achieve distributed consensus on who owns what coins. Block chains were invented specifically for the Bitcoin project but they can be applied anywhere a distributed consensus needs to be established in the presence of malicious or untrustworthy actors.

Whilst it's possible to abuse the Bitcoin financial block chain for other purposes, it's better to set up an alternative network and chain which share the same miners. There are several reasons to do this.

* The block chain is a large, complex data structure shared between many people. Verifying its integrity requires many slow (and thus expensive) operations like ECDSA verifications and disk seeks. Everyone who takes part in Bitcoin today runs a node and thus maintains the whole thing. Whilst in future end-users will probably use more efficient but slightly less secure modes (SPV), merchants and miners will probably always pay the full costs for the upkeep of this shared data structure. All these people today are united by a common interest in a new form of payments. They may or may not also be interested in other schemes. So one reason to keep the Bitcoin chain for finance is it's unfair to externalize the costs of unrelated schemes onto people who are interested only in payments - the canonical example being merchants. Increasing the cost of accepting Bitcoins for goods and services hurts everyone who uses the system by reducing the number of merchants or increasing their costs.

* Another reason is that it's just bad engineering to cram every possible distributed quorum into the design constraints of Bitcoin. The transaction format Bitcoin uses is flexible but ultimately designed for finance. You cannot leave out the "value" field. It's always there, even if it'd make no sense for your particular application. Building non-financial applications on top of a financial system results in bizarre protocols and code that are difficult to understand, leading to maintainability problems.

* One final reason is that [[Satoshi Nakamoto|Satoshi]] was opposed to putting non-Bitcoin related data into the main chain. As creator of the system, his opinion should carry a lot of weight with anyone serious about extending it.

=== Designing a new network ===

To create a new network that uses Nakamoto block chains, you need to start by defining what a transaction in your new network means. Bitcoin transactions split and combine value using scripts, but yours don't have to do that. They could be anything. Here's an example of a simple DNS style "transaction" described using [http://code.google.com/p/protobuf/ Google protocol buffers] syntax.

message NameTx {
required string name = 1;
repeated bytes ip_addresses = 2;
required bytes pubkey = 3;
enum ClaimType {
NEW_NAME,
TRANSFER
}
required ClaimType type = 4;

// Only used if type == TRANSFER. The new owner of the name and signature proving current ownership.
optional bytes dest_pubkey = 5;
optional bytes signature = 6;
}

This is very different to a Bitcoin style transaction. There's no concept of inputs, outputs, addresses, values or scripts. It's got what you need for a very simple DNS style scheme (that lacks abuse controls etc) and nothing more. There's also no concept of a "coinbase" transaction.

The block definition is also up to you. It does not have to be formatted in the same way as Satoshi chose, but you need most of the same conceptual parts. You also need to store something else, some data from Bitcoin. Here's a minimal example of what's needed:

message MyBlock {
required bytes prev_block_hash = 1;
required uint32 difficulty = 2;
required uint32 time = 3;

repeated MyTx transactions = 4;
}

message SuperBlock {
required MyBlock my_data = 1;
required BitcoinData bitcoin_data = 2;
}

It's important to observe what we don't have as well as what we do. We don't have the following fields from Satoshis format:

# version: protobufs handles the versioning of binary data formats for us
# merkle root: you can choose to arrange your transactions into a merkle root if you like, so you can use the same disk space reclamation trick Satoshi did. But it's strictly optional. If you want to simplify things down you can skip it.
# nonce

== Sharing work ==

The bitcoin_data field is how you share work with miners today (assuming they opt in by installing your software alongside their bitcoin node). It's defined like this:

message BitcoinData {
// A Bitcoin format block header. Because it's in Satoshis custom format we represent this as a byte array.
required bytes header = 1;

// The first transaction from the block.
required bytes coinbase_tx = 2;

// The merkle branch linking the coinbase transaction to the header.
required bytes coinbase_merkle_branch = 3;

// The coinbase scriptSig contains bits of data in order. Which one is our hash?
required int coinbase_tx_index = 4;
}

All you need to share work is the above four things.

A [[wikipedia:Merkle tree]] is a data structure in which each node in the tree is a hash. The leaf nodes are hashes of the things you want to include in the tree. The interior nodes are hashes of the concatenations of the child nodes. A merkle branch is a part of a merkle tree which allows you to cryptographically prove that something you're given was in the tree, without needing everything that was in the tree. They are calculated by the CBlock::GetMerkleBranch() function in the Bitcoin code.

We store a merkle branch here for efficiency. It means no matter how large the current Bitcoin block is, your alternative network only needs to handle a small amount of data. You could just store the entire Bitcoin block - that would be simpler but inefficient.

The merkle branch links the coinbase transaction to the block header, so you can prove it was in that block. The coinbase TX is a regular Bitcoin coinbase (that makes new coins and claims fees), except the scriptSig on its input contains an extra entry that todays scriptSigs don't. That extra entry is a hash of your block structure. The coinbase scriptSig today is formatted like this:

void IncrementExtraNonce(CBlock* pblock, CBlockIndex* pindexPrev, unsigned int& nExtraNonce, int64& nPrevTime)
{
.....
pblock->vtx[0].vin[0].scriptSig = CScript() << pblock->nBits << CBigNum(nExtraNonce);
.....
}

Just the difficulty bits and the "extra nonce". But it's actually allowed to contain anything, as long as it's not too big. So in your new blocks it'd be:

<MyBlock hash> <nBits> <nExtraNonce>

To get the MyBlock hash into Bitcoin requires a presently unimplemented RPC command, "setextrahashes". It'd update a global list and the IncrementExtraNonce function would include the extra hashes when the scriptSig is built. This is a very simple change to Bitcoin.

In the scriptSig above the coinbase_tx_index would be zero. It's possible to work on an arbitrary number of alternative chains simultaneously:

<MyBlock hash> <SomeOtherChainBlock hash> <nBits> <nExtraNonce>

in which case the BitcoinData message for SomeOtherChain would be 1 rather than zero.

A more complex change is the other new RPC. Because you have your own chain, it has its own difficulty. Most likely it'll be different to Bitcoins own. So you need a way to tell Bitcoin "when you find a block that matches an extradifficulty, please let me know". To mine on multiple difficulties at once, the node vends work (via getwork) matching the easiest difficulty. When a miner reports finding a solution the difficulty is checked to see which chains it is sufficiently difficult for.

Important note: Your chain has its own difficulty and as such the block creation rate is independent of how much mining takes place.

== Independent node software ==

Your new network has its own codebase. It can be written in whatever language you like, use whatever P2P protocol you like, store its data however you like and so on.

When a node on your network receives a message informing it about a new transaction, it verifies that transaction follows the rules of your network. To use our simple DNS example it would verify that if you're claiming a new name, it doesn't already exist and if you're transferring a name that the signatures are correct.

If the transaction is valid, it's added to your current MyBlock message. That message is serialized to binary (protobufs does this for you), hashed and then your node makes an RPC to Bitcoin telling it what the current extra hash is. When Bitcoin finds a Bitcoin-format block of the right difficulty for your network, it informs your software and passes the block header, coinbase transaction and merkle branch to it. Your node combines them together into a BitcoinData message, which is then glued together with your alternative chains block. This "superblock" is then broadcast via your independent P2P network.

When a node on your new network receives a superblock it does the following things:

# Verifies the MyBlock contents are correct, ie, that the transactions follow the rules.
# Verifies that the MyBlock prev hash makes it fit somewhere in the chain and that the difficulty is correct.
# Hashes the MyBlock structure and then verifies that this hash appears in the BitcoinData coinbase scriptSig, in the right place.
# Extracts the merkle root of the Bitcoin format block from the header and then verifies that the coinbase tx provided did, in fact, exist in that block (using the branch, root, tx and header together).
# Verifies that the hash of the Bitcoin format block header is below the difficulty found in the MyBlock structure.

You've now verified that a sufficiently hard proof of work was done over the contents of the MyBlock structure, so your node can relay the newly found block (or if you don't use a P2P network make it available on your server, etc).

On the other side when Bitcoin finds a block that is correct for the Bitcoin network and chain, it broadcasts it and obviously the hash of your MyBlock is included. Fortunately this is only an additional 33 bytes overhead so nobody cares about it - the pollution of the financial chain is both trivial and constant. Note that regular Bitcoin nodes just ignore this extra hash, it doesn't mean anything to them.

== Handling your new block chain ==

You have to handle re-organizations. This is a standard part of the block chain algorithm. When a re-org occurs you have to verify that the state of your world still makes sense. For example in the new chain maybe somebody else now owns a resource you thought you owned. It's up to you how to inform your users of these events and what app specific logic is appropriate here.

You can choose your own parameters for the new chain. As an example, Satoshi chose to target one new block every ten minutes as a tradeoff between latency and wasted work. You could choose something much larger (hours, days) or much faster if you're willing to tolerate more splits due to blocks being found simultaneously. Bitcoin retargets the difficulty roughly every two weeks. You could choose some other length of time.

To store the block chain, Satoshi chose to use Berkeley DB as a way to index from transactions to the blocks they appeared in (amongst other things). You could use any database you liked.

== Paying for resources on alternative chains with Bitcoins ==

A commonly cited reason for putting DNS related data into the financial chain is the desire to pay for names with Bitcoins. You can do this with an independent chain too, because you make the rules and can link the two chains together as you see fit.

To start, decide on the purpose of your payments and who will receive the coins - if anyone. In the case of a DNS system, there are two reasons you might want to pay for names:

# To prevent abuse by people claiming all interesting names via a dictionary attack.
# To incentivise people to run your software and mine on your alternative chain.

In the first case really nobody should receive the payment. The money is being put up as a collateral and has no other use, so as long as it's sitting around unspent that is good enough. In the second case the payment should go to the miner working on the DNS chain.

To implement this we extend our hypothetical DNS transaction message like this:

message NameTx {
required string name = 1;
repeated bytes ip_addresses = 2;
required bytes pubkey = 3;
enum ClaimType {
NEW_NAME,
TRANSFER
}
required ClaimType type = 4;

// Only used if type == TRANSFER. The new owner of the name and signature proving current ownership.
optional bytes dest_pubkey = 5;
optional bytes signature = 6;

// Only used if type == NEW_NAME.
optional bytes collateral_signature = 7;
optional string miner_address = 8;
optional uint64 miner_fee = 9;
}

The collateral_signature field contains an ECDSA signature generated from a public key that holds some Bitcoins. The miner address is blank when the name purchaser creates the transaction and is filled out after a miner receives it, but before they begin working on it.

To buy a name that costs 10 BTC with a miner fee of 2 BTC, a user presses the "buy name" button in their DNS software. It talks to their local Bitcoin node via RPC and does the following:

# Creates a new Bitcoin address (key).
# Sends 10 BTC to the new address (a send-to-self transaction).
# Extracts the key from Bitcoin, meaning it's no longer available to spend in your wallet.
# Stores the key in a local DNS data file ("wallet") somewhere.
# Sets the miner_fee field to the pre-agreed value of 2 BTC.
# Takes the public key part and uses it to sign a version of the NameTx that lacks collateral_signature (a signature can't sign itself) and miner_address.
# The signature is placed in collateral_signature field.
# The transaction is sent to a miner who charges 2 BTC.

When the miner receives the transaction, it verifies that the 10 BTC is not spent:

# The ECDSA public key recovery algorithm is run on the collateral_signature. It can yield several possible keys.
# The public keys recovered are used to verify the signature is correct. This step also figures out which of the possible keys is the right one.
# The correct public key is turned into a Bitcoin address (by hashing it)
# The DNS node software queries Bitcoin to discover whether that address has 10 BTC associated with it, or whether the balance of that address is lower. Note that todays software does not index the balance of every address in the system, but it can be added (the Block Explorer does this).
# If the address does indeed have 10 unspent Bitcoins then the collateral is present and it's OK to serve the name

The miner then creates a new Bitcoin address for themselves and sets miner_address to contain it, then includes it into the current block being worked on. After a block matching the DNS chains difficulty is found, it is broadcast. Other nodes do the following:

# For each transaction, repeat the verification steps to ensure the collateral is not spent.
# Check the balance of the miners own address.
# If the balance is not yet equal to miner_fee, the name is put into a "pending" state in which it is owned but not served in response to DNS queries.

The user observes the broadcast and sees that their name is now pending payment, so they send 2 BTC to the address they find in their transaction. As nodes notice the payment becoming confirmed they start responding to DNS queries for that name (ie, the ownership process is complete).

When the user gets tired of owning the name, he can simply re-import the collateral key into his wallet and spend the coins. The DNS network will soon observe that the coins are spent and make the name available for purchasing by somebody else.

== Incentivising non-resource based chains ==

It's possible to incentivise mining on an alt-chain even if that chain does not have any concept of ownership, ie, if the act of finding a block itself is what is being paid for. An example of this is a timestamping chain in which presence in a block alone is sufficient to satisfy the user.

To implement this, set up a new chain as normal. Blocks in this new chain arrange transactions into a merkle tree in the same manner as Bitcoin does. A client that wants something incorporated into a block connects directly to some miners and submits their transaction. The miners add their address to the transaction as normal. Once a miner finds a block, it immediately sends the block to connected clients whose transactions made it in, but does not broadcast the new block to other miners. The clients respond with a valid Bitcoin transaction which pays for block inclusion. Once all clients have paid up the transaction is broadcast.

If a client has disconnected or does not pay quickly enough, their transaction can be replaced inside the block with its hash. In this way the blocks validity is preserved because the merkle tree is still valid. The newly found alt-block is broadcast, minus the transaction of the delinquent customer. As long as clients are still connected the payment process for all found transactions can be completed quickly: it would only take a few seconds to gather the payments and broadcast those on the Bitcoin network, minimizing the chance of a race that would require you to trust the miner to reinclude your transactions in the next block despite having already been paid.

== Mining on the alt-chain but not Bitcoin ==

So far we've considered a scheme in which all alt-chain miners simultaneously mine on Bitcoin. It's possible some people may wish to mine on your chain but not Bitcoin, perhaps because the cost of keeping up with the Bitcoin transaction rate has become too high for them to bother.

To mine without an attached Bitcoin node, your software can simply implement the same getwork protocol Bitcoin itself does. When a mining tool requests work your program would generate a correctly formatted but ultimately bogus Bitcoin block. The contents of this block don't need to be correct because it will never be broadcast on the Bitcoin network, for example, the prevBlockHash field can be all zeros. It exists purely for backwards compatibility. Whilst the block needs a valid merkle root and a coinbase transaction, no other transactions are required and the only part of the coinbase tx that matters is the part holding the hash.

=== Scaling up ===

In the simple scheme each alt-chain being worked on needs 33 bytes in the Bitcoin coinbase transaction (1 for the length and 32 for the hash). Note that if there are two independent miners working on two different alt-chains, you still only need 1 hash in the coinbase scriptSig because the hash isn't meaningful to anyone else on the Bitcoin network. If miners only want to work a handful of chains this overhead is trivially dwarfed by the rest of the data in a Bitcoin block.

But if a miner wishes to work on hundreds, thousands or millions of alternative chains the size of the coinbase scriptSig would balloon and become unworkable. To solve this, the hash stored in the scriptSig can be the root of yet another merkle tree, this time a tree over the hashes of all blocks being worked on. The BitcoinData message is extended like this:

message MyBlock {
required bytes prev_block_hash = 1;
required uint32 difficulty = 2;
required uint32 time = 3;

repeated MyTx transactions = 4;
}

message SuperBlock {
required MyBlock my_data = 1;
required BitcoinData bitcoin_data = 2;
}

message BitcoinData {
// A Bitcoin format block header. Because it's in Satoshis custom format we represent this as a byte array.
required bytes header = 1;

// The first transaction from the block.
required bytes coinbase_tx = 2;

// The merkle branch linking the coinbase transaction to the header.
required bytes coinbase_merkle_branch = 3;

// The merkle branch linking MyBlock to the merkle root in the coinbase_tx.
required bytes altblock_merkle_branch = 4;
}

The verification step becomes a bit more complex:

# Verify the header is of sufficient difficulty for the alt-chain
# Verify coinbase_tx was a part of that block by checking the coinbase_merkle_branch is linked to the merkle root in the header.
# Extract the root of the second merkle tree from the coinbase_tx (call it 2MR).
# Hash the alt-chain block (my_data), verify that altblock_merkle_branch links the my_data hash to 2MR.

You have now proven that the MyBlock instance was worked on, along with perhaps thousands of other chains you don't have to know anything about.

This is an advanced technique which is probably not worth implementing unless the additional scalability is required. It can be introduced in a backwards compatible manner for new chains without impacting older networks.

== Generalized proof of work ==

Hashes embedded in transactions and headers, merkle branches, and [[Nonce|nonces]] all contribute to the goal of [[Proof of work|proving work]] on a block header. One can express all as sequences of these basic operations:

* prepend a byte string to the current data
* append a byte string to the current data
* hash the current data

For maximum flexibility, a work-sharing chain's block acceptance algorithm might accept proof in the form of a script using just these operations. The script would receive as input an alternative chain block header, and the hash of its output would have to satisfy the chain's difficulty.

This design would even support plain Bitcoin proof of work, where the "header" consists of all [[Protocol Specification#block|Bitcoin block header fields]] except the nonce, and the proof-of-work script simply appends the nonce. Thus, one can think of the work-sharing rules as an extension of the original Bitcoin rules.

==External Links==

* [https://bitcointalk.org/index.php?topic=6197.0 BitDNS in the words of Satoshi]
* [http://dot-bit.org/Merged_Mining Merged Mining] in Namecoin
* [http://dot-bit.org/forum/viewtopic.php?f=5&t=269 Namecoin forum discussion]

[[Category:Technical]]

Software

2011-09-08T01:53:00Z

JohnTobey253: Added Abe under "Web apps (opensource)"

List of Bitcoin-related software. See also [[:Category:Software|Category:Software]].

==Bitcoin clients==
===Bitcoin clients===
*[[Original Bitcoin client|Bitcoin client]] - standard Bitcoin client, recommended for installation
*[[bitcoind]] - GUI-less version of the standard Bitcoin client, providing [[API reference (JSON-RPC)|JSON-RPC]] interface (see also -server option of the standard client)

===Frontends to bitcoind===
*[[BitcoinApp]] - RPC client for iOS devices (iPhone, iPad, iPodTouch)
*[[Bitcoiner]] - Java RPC client (Android)
*[[Bitcoin-js-remote]] - JavaScript RPC client, support for QR codes
*[[Bitcoin-qt]] - C++/Qt based tabbed UI for Bitcoin, Linux/MacOSX/Windows, full-featured
*[[Python Bitcoinclient]] - Python RPC client
*[[Spesmilo]] - Python/PySide RPC client
*[[Bitcoin-python]] - Python API
*[[Java Bitcoin Client]] - Java API
*[[Wallet.Net]] - Windows (soon to be cross platform) Full Featured, secure RPC client
*[[FastCat BRPC]] - Fast low memory footprint Windows client!
Alternative, experimental implementations:
*[[BitDroid]] - Java client
*[[Bitdollar]] - C++/Qt client, unstable beta version
*[[BitCoinJ]] - Java client by Google, early development stage
*[[Freecoin]] - C++ client, supports alternative currencies like [[Beertoken]]
*[[Pycoin]] - Python client
*[[QBitcoin]] - C++/Qt client, unfinished
*[[BCCAPI]] (Bitcoin Client API) - a java library designed for making secure light-weight bitcoin clients.

===Frontends to eWallet===
*[[BitPay]] - Android application

==Bitcoin Trade Data==
*[[Bitcoin Charts]] – Html website that has trading data for virtual all the bitcoin markets.
*[[MtGox Live]] - Html website that shows a live fee of [[MtGox]] trade data in an innovative chart form. (Must Use Chrome)
*[[BitcoinNotify]] - Realtime Bitcoin price alerts (via SMS, Jabber, e-mail or HTTP call) on major exchanges
*[[Bitcoinity]] - Html Ajax website that shows a live feed of [[MtGox]], [[TradeHill]], and [[BitMarket]].
*[[Bitcoin Sentiment Index]] - A financial index that collects and disseminates sentiment data about bitcoin.
*[[Preev]] - Bitcoin converter with live exchange rates.

==Bitcoin software==

===Web interfaces for merchants===
*[[MyBitcoin]] - Buy Now button to insert on websites
*[[Bitcoin Evolution]] - Non wallet-based Buy Now button to insert into websites (handles sales tracking; client must be used for actual transaction)
*[[Btceconomy]] - a JavaScript widget listing items for sale
*[[Javascript Bitcoin Converter]] - currency conversion

===Web apps (opensource)===
*[[Bitcoin Central]] - currency exchange
*[[Bitcoin Poker Room]] - poker site
*[[Abe]] - block chain viewer

===Browser extensions===
*[[Bitcoin Extension]] - check balance and send bitcoins (Chrome)
*[[Bitcoin Ticker]] - monitoring price (Chrome)
*[[Bitcoin Prices (extension)]] - monitoring price (Firefox)
*[[Bitcoin Tool]] - recognizes Bitcoin addresses on websites (Firefox, Chrome, IE)

===PC apps===
*[[BTConvert]] - currency conversion
*[[Sierra Chart MtGox Bridge]] - real-time charting
*[[BTC Trader]] - live charting and tech-analysis
*[[BitTicker]] - monitoring price (Mac OS X)
*[[ToyTrader]] - a command line trading tool for [[MtGox]]
*[[goxsh]] - a command-line frontend to the [[MtGox|Mt. Gox Bitcoin Exchange]] (Python)

===Mobile apps===
==== iPhone / iPad ====
*[[Bitcoin Ticker (iPhone)]] - monitoring price w/push notifications
*[[BitCoins Mobile]] - First iPad native app! Live market data, news feeds, mining pool statistics, full screen exchange price charts, bitcoin network statistical charts. (iPad only, iPhone/iPod Touch coming soon!)
*[https://github.com/teeman/BitcoinTrader BitcoinTrader] - Spend/receive BTC via QR codes, trade, deposit/withdraw, etc. Supports Mt. Gox, TradeHill, ExchB, CampBX, and InstaWallet.
==== Android ====
* Direct link to Android Market bitcoin apps. https://market.android.com/search?q=bitcoin
*[[Bitcoin Wallet]] - This is the most functional android bitcoin wallet application. https://market.android.com/details?id=de.schildbach.wallet
*[[Bitcoin Android]] - Does not appear to be being maitained anymore. https://market.android.com/details?id=com.bitcoinandroid
*[[Bitpay]] - Is not related to the bit-pay.com online payment processor. Does not appear to be being maintained. https://market.android.com/details?id=com.bitcoin.bitpay

*[[Bitcoin Alert]] - monitoring price (Android)
*[[BitcoinX]] - monitoring price (Android)
*[[BtcMobile]] - monitoring price and mining pool statistics (iPhone/iPad, Android)
*[[Miner Status]] - monitoring miner status (Android)
*[[SMS Bitcoins]] - transactions by SMS
*[[Bitcoin Wallet Balance]] - view your balance in real time on your android phone

===Other device apps===
*[[Zen Cart Bitcoin Payment Module]] - a payment module that interacts with bitcoind for the Zen Cart eCommerce shopping chart

===Operating systems===
*[[LinuxCoin]] - a lightweight Debian-based OS, with the Bitcoin client and GPU mining software

===Mining apps===
*[[Poclbm]] - Python/OpenCL GPU miner ([[Poclbm-gui|GUI]])
*[[Poclbm-mod]] - more efficient version of [[Poclbm]] ([[Poclbm-mod-gui|GUI]])
*[[DiabloMiner]] - Java/OpenCL GPU miner ([[DiabloMiner.app|MAC OS X GUI]])
*[[RPC Miner]] - remote RPC miner ([[RPCminer.app|MAC OS X GUI]])
*[[Phoenix miner]] - miner
*[[Cpu Miner]] - miner
*[[Ufasoft miner]] - miner
*[[Pyminer]] - Python miner, reference implementation
*[[Remote miner]] - mining pool software
*[[Open Source FGPA Bitcoin Miner]] - a miner that makes use of an FPGA Board

===Mining Pool Servers (backend)===
*[[Pushpoold]] - The original mining pool server
*[[Poold]] - Python mining pool server
*[[PoolServerJ]] - Java mining pool server

===Utilities, libraries, and interfaces:===
*[[Bitcointools]] - a set of Python tools accessing the transaction database and the wallet
*[[Finance::MtGox]] - a Perl module which interfaces with the Mt. Gox API
*[[BitcoinCrypto]] - a lightweight Bitcoin crypto library for Java/Android
*[[Bitcoin Dissector]] - a wireshark dissector for the bitcoin protocol

===Lists of software===
*[[BitGit]] - list of Bitcoin-related opensource projects hosted at Git

===Developer resources===
*[[:Category:Developer|Category:Developer]]
*[[:Category:Technical|Category:Technical]]
*[[Original Bitcoin client/API calls list]]
*[[API reference (JSON-RPC)]]

===Other===
*[[Namecoin]] - a distributed naming system based on Bitcoin technology
*[[Bitcoin Consultancy]] - an organization providing open source software and Bitcoin-related consulting
*[[Open Transactions]] - a financial crypto and digital cash software library, complementary to Bitcoin
*[[Moneychanger]] - Java-based GUI for [[Open Transactions]]
*[http://btcnames.org/ BTCnames] - a webbased aliasing service which allows to handle unlimited names for your BTC deposit hashes
*[[Devcoin]] - the open source developer coin

Abe

2011-07-14T20:27:14Z

JohnTobey253: /* External Links */ updated demo site URL

[[File:penny-abe-160.png|thumb|160px|Abe]]

'''Abe''' is a free, open-source [[block chain browser]] released by [[User:JohnTobey253|John Tobey]] under the [[wikipedia:Affero General Public License|Affero General Public License]].

Written in [[wikipedia:Python (programming language)|Python]] and portable [[wikipedia:SQL|SQL]],<ref>https://forum.bitcoin.org/index.php?topic=16141.0</ref> Abe draws inspiration from [[Bitcoin Block Explorer]] and seeks some level of compatibility with it but uses a completely new implementation.<ref>https://raw.github.com/jtobey/bitcoin-abe/master/README.txt</ref>

==See Also==

* [[Block chain browser]]

== External Links ==

* [http://abe.john-edwin-tobey.org/ Demonstration site]
* [https://forum.bitcoin.org/index.php?topic=16141.0 Project announcement]
* [https://github.com/jtobey/bitcoin-abe Project on Github]

==References==
<references />

[[Category:Block chain browsers]]
[[Category:Free Software]]
[[Category:Open Source]]

Nonce

2011-06-30T13:05:34Z

JohnTobey253: Soften "impossible" wrt breaking the hash function.

The "nonce" in a bitcoin [[block]] is a 32-bit (4-byte) field whose value is set so that the [[hash]] of the block will contain a run of zeros. The rest of the fields may not be changed, as they have a defined meaning.

Any change to the the block data (such as the nonce) will make the block hash completely different. Since it is [[wikipedia:Cryptographic hash function|believed infeasible]] to predict which combination of bits will result in the right hash, many different nonce values are tried, and the hash is recomputed for each value until a hash containing the required number of zero bits is found. As this iterative calculation requires time and resources, the presentation of the block with the correct nonce value constitutes [[proof of work]].

[[Category:Technical]]
[[Category:Vocabulary]]

Alternative chain

2011-06-29T15:32:29Z

JohnTobey253: /* Generalized proof of work */ tense agreement.

An '''alternative chain''' is a system using the block chain algorithm to achieve distributed consensus on a particular topic, whilst sharing miners with the Bitcoin network. Alternative chains have been suggested as ways to implement DNS, SSL certificate authorities, timestamping, file storage and voting systems.

=== Objective ===

Bitcoin uses the [[block chain]] algorithm to achieve distributed consensus on who owns what coins. Block chains were invented specifically for the Bitcoin project but they can be applied anywhere a distributed consensus needs to be established in the presence of malicious or untrustworthy actors.

Whilst it's possible to abuse the Bitcoin financial block chain for other purposes, it's better to set up an alternative network and chain which share the same miners. There are several reasons to do this.

* The block chain is a large, complex data structure shared between many people. Verifying its integrity requires many slow (and thus expensive) operations like ECDSA verifications and disk seeks. Everyone who takes part in Bitcoin today runs a node and thus maintains the whole thing. Whilst in future end-users will probably use more efficient but slightly less secure modes (SPV), merchants and miners will probably always pay the full costs for the upkeep of this shared data structure. All these people today are united by a common interest in a new form of payments. They may or may not also be interested in other schemes. So one reason to keep the Bitcoin chain for finance is it's unfair to externalize the costs of unrelated schemes onto people who are interested only in payments - the canonical example being merchants. Increasing the cost of accepting Bitcoins for goods and services hurts everyone who uses the system by reducing the number of merchants or increasing their costs.

* Another reason is that it's just bad engineering to cram every possible distributed quorum into the design constraints of Bitcoin. The transaction format Bitcoin uses is flexible but ultimately designed for finance. You cannot leave out the "value" field. It's always there, even if it'd make no sense for your particular application. Building non-financial applications on top of a financial system results in bizarre protocols and code that are difficult to understand, leading to maintainability problems.

* One final reason is that Satoshi was opposed to putting non-Bitcoin related data into the main chain. As creator of the system, his opinion should carry a lot of weight with anyone serious about extending it.

=== Designing a new network ===

To create a new network that uses Nakamoto block chains, you need to start by defining what a transaction in your new network means. Bitcoin transactions split and combine value using scripts, but yours don't have to do that. They could be anything. Here's an example of a simple DNS style "transaction" described using [http://code.google.com/p/protobuf/ Google protocol buffers] syntax.

message NameTx {
required string name = 1;
repeated bytes ip_addresses = 2;
required bytes pubkey = 3;
enum ClaimType {
NEW_NAME,
TRANSFER
}
required ClaimType type = 4;

// Only used if type == TRANSFER. The new owner of the name and signature proving current ownership.
optional bytes dest_pubkey = 5;
optional bytes signature = 6;
}

This is very different to a Bitcoin style transaction. There's no concept of inputs, outputs, addresses, values or scripts. It's got what you need for a very simple DNS style scheme (that lacks abuse controls etc) and nothing more. There's also no concept of a "coinbase" transaction.

The block definition is also up to you. It does not have to be formatted in the same way as Satoshi chose, but you need most of the same conceptual parts. You also need to store something else, some data from Bitcoin. Here's a minimal example of what's needed:

message MyBlock {
required bytes prev_block_hash = 1;
required uint32 difficulty = 2;
required uint32 time = 3;

repeated MyTx transactions = 4;
}

message SuperBlock {
required MyBlock my_data = 1;
required BitcoinData bitcoin_data = 2;
}

It's important to observe what we don't have as well as what we do. We don't have the following fields from Satoshis format:

# version: protobufs handles the versioning of binary data formats for us
# merkle root: you can choose to arrange your transactions into a merkle root if you like, so you can use the same disk space reclamation trick Satoshi did. But it's strictly optional. If you want to simplify things down you can skip it.
# nonce

=== Sharing work ===

The bitcoin_data field is how you share work with miners today (assuming they opt in by installing your software alongside their bitcoin node). It's defined like this:

message BitcoinData {
// A Bitcoin format block header. Because it's in Satoshis custom format we represent this as a byte array.
required bytes header = 1;

// The first transaction from the block.
required bytes coinbase_tx = 2;

// The merkle branch linking the coinbase transaction to the header.
required bytes coinbase_merkle_branch = 3;

// The coinbase scriptSig contains bits of data in order. Which one is our hash?
required int coinbase_tx_index = 4;
}

All you need to share work is the above four things.

A [[wikipedia:Merkle tree]] is a data structure in which each node in the tree is a hash. The leaf nodes are hashes of the things you want to include in the tree. The interior nodes are hashes of the concatenations of the child nodes. A merkle branch is a part of a merkle tree which allows you to cryptographically prove that something you're given was in the tree, without needing everything that was in the tree. They are calculated by the CBlock::GetMerkleBranch() function in the Bitcoin code.

We store a merkle branch here for efficiency. It means no matter how large the current Bitcoin block is, your alternative network only needs to handle a small amount of data. You could just store the entire Bitcoin block - that would be simpler but inefficient.

The merkle branch links the coinbase transaction to the block header, so you can prove it was in that block. The coinbase TX is a regular Bitcoin coinbase (that makes new coins and claims fees), except the scriptSig on its input contains an extra entry that todays scriptSigs don't. That extra entry is a hash of your block structure. The coinbase scriptSig today is formatted like this:

void IncrementExtraNonce(CBlock* pblock, CBlockIndex* pindexPrev, unsigned int& nExtraNonce, int64& nPrevTime)
{
.....
pblock->vtx[0].vin[0].scriptSig = CScript() << pblock->nBits << CBigNum(nExtraNonce);
.....
}

Just the difficulty bits and the "extra nonce". But it's actually allowed to contain anything, as long as it's not too big. So in your new blocks it'd be:

<MyBlock hash> <nBits> <nExtraNonce>

To get the MyBlock hash into Bitcoin requires a presently unimplemented RPC command, "setextrahashes". It'd update a global list and the IncrementExtraNonce function would include the extra hashes when the scriptSig is built. This is a very simple change to Bitcoin.

In the scriptSig above the coinbase_tx_index would be zero. It's possible to work on an arbitrary number of alternative chains simultaneously:

<MyBlock hash> <SomeOtherChainBlock hash> <nBits> <nExtraNonce>

in which case the BitcoinData message for SomeOtherChain would be 1 rather than zero.

A more complex change is the other new RPC. Because you have your own chain, it has its own difficulty. Most likely it'll be different to Bitcoins own. So you need a way to tell Bitcoin "when you find a block that matches an extradifficulty, please let me know". To mine on multiple difficulties at once, the node vends work (via getwork) matching the easiest difficulty. When a miner reports finding a solution the difficulty is checked to see which chains it is sufficiently difficult for.

Important note: Your chain has its own difficulty and as such the block creation rate is independent of how much mining takes place.

=== Independent node software ===

Your new network has its own codebase. It can be written in whatever language you like, use whatever P2P protocol you like, store its data however you like and so on.

When a node on your network receives a message informing it about a new transaction, it verifies that transaction follows the rules of your network. To use our simple DNS example it would verify that if you're claiming a new name, it doesn't already exist and if you're transferring a name that the signatures are correct.

If the transaction is valid, it's added to your current MyBlock message. That message is serialized to binary (protobufs does this for you), hashed and then your node makes an RPC to Bitcoin telling it what the current extra hash is. When Bitcoin finds a Bitcoin-format block of the right difficulty for your network, it informs your software and passes the block header, coinbase transaction and merkle branch to it. Your node combines them together into a BitcoinData message, which is then glued together with your alternative chains block. This "superblock" is then broadcast via your independent P2P network.

When a node on your new network receives a superblock it does the following things:

# Verifies the MyBlock contents are correct, ie, that the transactions follow the rules.
# Verifies that the MyBlock prev hash makes it fit somewhere in the chain and that the difficulty is correct.
# Hashes the MyBlock structure and then verifies that this hash appears in the BitcoinData coinbase scriptSig, in the right place.
# Extracts the merkle root of the Bitcoin format block from the header and then verifies that the coinbase tx provided did, in fact, exist in that block (using the branch, root, tx and header together).
# Verifies that the hash of the Bitcoin format block header is below the difficulty found in the MyBlock structure.

You've now verified that a sufficiently hard proof of work was done over the contents of the MyBlock structure, so your node can relay the newly found block (or if you don't use a P2P network make it available on your server, etc).

On the other side when Bitcoin finds a block that is correct for the Bitcoin network and chain, it broadcasts it and obviously the hash of your MyBlock is included. Fortunately this is only an additional 33 bytes overhead so nobody cares about it - the pollution of the financial chain is both trivial and constant. Note that regular Bitcoin nodes just ignore this extra hash, it doesn't mean anything to them.

=== Handling your new block chain ===

You have to handle re-organizations. This is a standard part of the block chain algorithm. When a re-org occurs you have to verify that the state of your world still makes sense. For example in the new chain maybe somebody else now owns a resource you thought you owned. It's up to you how to inform your users of these events and what app specific logic is appropriate here.

You can choose your own parameters for the new chain. As an example, Satoshi chose to target one new block every ten minutes as a tradeoff between latency and wasted work. You could choose something much larger (hours, days) or much faster if you're willing to tolerate more splits due to blocks being found simultaneously. Bitcoin retargets the difficulty roughly every two weeks. You could choose some other length of time.

To store the block chain, Satoshi chose to use Berkeley DB as a way to index from transactions to the blocks they appeared in (amongst other things). You could use any database you liked.

=== Paying for resources on alternative chains with Bitcoins ===

A commonly cited reason for putting DNS related data into the financial chain is the desire to pay for names with Bitcoins. You can do this with an independent chain too, because you make the rules and can link the two chains together as you see fit.

To start, decide on the purpose of your payments and who will receive the coins - if anyone. In the case of a DNS system, there are two reasons you might want to pay for names:

# To prevent abuse by people claiming all interesting names via a dictionary attack.
# To incentivise people to run your software and mine on your alternative chain.

In the first case really nobody should receive the payment. The money is being put up as a collateral and has no other use, so as long as it's sitting around unspent that is good enough. In the second case the payment should go to the miner working on the DNS chain.

To implement this we extend our hypothetical DNS transaction message like this:

message NameTx {
required string name = 1;
repeated bytes ip_addresses = 2;
required bytes pubkey = 3;
enum ClaimType {
NEW_NAME,
TRANSFER
}
required ClaimType type = 4;

// Only used if type == TRANSFER. The new owner of the name and signature proving current ownership.
optional bytes dest_pubkey = 5;
optional bytes signature = 6;

// Only used if type == NEW_NAME.
optional bytes collateral_signature = 7;
optional string miner_address = 8;
optional uint64 miner_fee = 9;
}

The collateral_signature field contains an ECDSA signature generated from a public key that holds some Bitcoins. The miner address is blank when the name purchaser creates the transaction and is filled out after a miner receives it, but before they begin working on it.

To buy a name that costs 10 BTC with a miner fee of 2 BTC, a user presses the "buy name" button in their DNS software. It talks to their local Bitcoin node via RPC and does the following:

# Creates a new Bitcoin address (key).
# Sends 10 BTC to the new address (a send-to-self transaction).
# Extracts the key from Bitcoin, meaning it's no longer available to spend in your wallet.
# Stores the key in a local DNS data file ("wallet") somewhere.
# Sets the miner_fee field to the pre-agreed value of 2 BTC.
# Takes the public key part and uses it to sign a version of the NameTx that lacks collateral_signature (a signature can't sign itself) and miner_address.
# The signature is placed in collateral_signature field.
# The transaction is sent to a miner who charges 2 BTC.

When the miner receives the transaction, it verifies that the 10 BTC is not spent:

# The ECDSA public key recovery algorithm is run on the collateral_signature. It can yield several possible keys.
# The public keys recovered are used to verify the signature is correct. This step also figures out which of the possible keys is the right one.
# The correct public key is turned into a Bitcoin address (by hashing it)
# The DNS node software queries Bitcoin to discover whether that address has 10 BTC associated with it, or whether the balance of that address is lower. Note that todays software does not index the balance of every address in the system, but it can be added (the Block Explorer does this).
# If the address does indeed have 10 unspent Bitcoins then the collateral is present and it's OK to serve the name

The miner then creates a new Bitcoin address for themselves and sets miner_address to contain it, then includes it into the current block being worked on. After a block matching the DNS chains difficulty is found, it is broadcast. Other nodes do the following:

# For each transaction, repeat the verification steps to ensure the collateral is not spent.
# Check the balance of the miners own address.
# If the balance is not yet equal to miner_fee, the name is put into a "pending" state in which it is owned but not served in response to DNS queries.

The user observes the broadcast and sees that their name is now pending payment, so they send 2 BTC to the address they find in their transaction. As nodes notice the payment becoming confirmed they start responding to DNS queries for that name (ie, the ownership process is complete).

When the user gets tired of owning the name, he can simply re-import the collateral key into his wallet and spend the coins. The DNS network will soon observe that the coins are spent and make the name available for purchasing by somebody else.

=== Incentivising non-resource based chains ===

It's possible to incentivise mining on an alt-chain even if that chain does not have any concept of ownership, ie, if the act of finding a block itself is what is being paid for. An example of this is a timestamping chain in which presence in a block alone is sufficient to satisfy the user.

To implement this, set up a new chain as normal. Blocks in this new chain arrange transactions into a merkle tree in the same manner as Bitcoin does. A client that wants something incorporated into a block connects directly to some miners and submits their transaction. The miners add their address to the transaction as normal. Once a miner finds a block, it immediately sends the block to connected clients whose transactions made it in, but does not broadcast the new block to other miners. The clients respond with a valid Bitcoin transaction which pays for block inclusion. Once all clients have paid up the transaction is broadcast.

If a client has disconnected or does not pay quickly enough, their transaction can be replaced inside the block with its hash. In this way the blocks validity is preserved because the merkle tree is still valid. The newly found alt-block is broadcast, minus the transaction of the delinquent customer. As long as clients are still connected the payment process for all found transactions can be completed quickly: it would only take a few seconds to gather the payments and broadcast those on the Bitcoin network, minimizing the chance of a race that would require you to trust the miner to reinclude your transactions in the next block despite having already been paid.

=== Mining on the alt-chain but not Bitcoin ===

So far we've considered a scheme in which all alt-chain miners simultaneously mine on Bitcoin. It's possible some people may wish to mine on your chain but not Bitcoin, perhaps because the cost of keeping up with the Bitcoin transaction rate has become too high for them to bother.

To mine without an attached Bitcoin node, your software can simply implement the same getwork protocol Bitcoin itself does. When a mining tool requests work your program would generate a correctly formatted but ultimately bogus Bitcoin block. The contents of this block don't need to be correct because it will never be broadcast on the Bitcoin network, for example, the prevBlockHash field can be all zeros. It exists purely for backwards compatibility. Whilst the block needs a valid merkle root and a coinbase transaction, no other transactions are required and the only part of the coinbase tx that matters is the part holding the hash.

=== Scaling up ===

In the simple scheme each alt-chain being worked on needs 33 bytes in the Bitcoin coinbase transaction (1 for the length and 32 for the hash). Note that if there are two independent miners working on two different alt-chains, you still only need 1 hash in the coinbase scriptSig because the hash isn't meaningful to anyone else on the Bitcoin network. If miners only want to work a handful of chains this overhead is trivially dwarfed by the rest of the data in a Bitcoin block.

But if a miner wishes to work on hundreds, thousands or millions of alternative chains the size of the coinbase scriptSig would balloon and become unworkable. To solve this, the hash stored in the scriptSig can be the root of yet another merkle tree, this time a tree over the hashes of all blocks being worked on. The BitcoinData message is extended like this:

message MyBlock {
required bytes prev_block_hash = 1;
required uint32 difficulty = 2;
required uint32 time = 3;

repeated MyTx transactions = 4;
}

message SuperBlock {
required MyBlock my_data = 1;
required BitcoinData bitcoin_data = 2;
}

message BitcoinData {
// A Bitcoin format block header. Because it's in Satoshis custom format we represent this as a byte array.
required bytes header = 1;

// The first transaction from the block.
required bytes coinbase_tx = 2;

// The merkle branch linking the coinbase transaction to the header.
required bytes coinbase_merkle_branch = 3;

// The merkle branch linking MyBlock to the merkle root in the coinbase_tx.
required bytes altblock_merkle_branch = 4;
}

The verification step becomes a bit more complex:

# Verify the header is of sufficient difficulty for the alt-chain
# Verify coinbase_tx was a part of that block by checking the coinbase_merkle_branch is linked to the merkle root in the header.
# Extract the root of the second merkle tree from the coinbase_tx (call it 2MR).
# Hash the alt-chain block (my_data), verify that altblock_merkle_branch links the my_data hash to 2MR.

You have now proven that the MyBlock instance was worked on, along with perhaps thousands of other chains you don't have to know anything about.

This is an advanced technique which is probably not worth implementing unless the additional scalability is required. It can be introduced in a backwards compatible manner for new chains without impacting older networks.

=== Generalized proof of work ===

Hashes embedded in transactions and headers, merkle branches, and [[Nonce|nonces]] all contribute to the goal of [[Proof of work|proving work]] on a block header. One can express all as sequences of these basic operations:

* prepend a byte string to the current data
* append a byte string to the current data
* hash the current data

For maximum flexibility, a work-sharing chain's block acceptance algorithm might accept proof in the form of a script using just these operations. The script would receive as input an alternative chain block header, and the hash of its output would have to satisfy the chain's difficulty.

This design would even support plain Bitcoin proof of work, where the "header" consists of all [[Protocol Specification#block|Bitcoin block header fields]] except the nonce, and the proof-of-work script simply appends the nonce. Thus, one can think of the work-sharing rules as an extension of the original Bitcoin rules.

[[Category:Technical]]

Alternative chain

2011-06-29T15:30:21Z

JohnTobey253: /* Generalized proof of work */ tweaks.

An '''alternative chain''' is a system using the block chain algorithm to achieve distributed consensus on a particular topic, whilst sharing miners with the Bitcoin network. Alternative chains have been suggested as ways to implement DNS, SSL certificate authorities, timestamping, file storage and voting systems.

=== Objective ===

Bitcoin uses the [[block chain]] algorithm to achieve distributed consensus on who owns what coins. Block chains were invented specifically for the Bitcoin project but they can be applied anywhere a distributed consensus needs to be established in the presence of malicious or untrustworthy actors.

Whilst it's possible to abuse the Bitcoin financial block chain for other purposes, it's better to set up an alternative network and chain which share the same miners. There are several reasons to do this.

* The block chain is a large, complex data structure shared between many people. Verifying its integrity requires many slow (and thus expensive) operations like ECDSA verifications and disk seeks. Everyone who takes part in Bitcoin today runs a node and thus maintains the whole thing. Whilst in future end-users will probably use more efficient but slightly less secure modes (SPV), merchants and miners will probably always pay the full costs for the upkeep of this shared data structure. All these people today are united by a common interest in a new form of payments. They may or may not also be interested in other schemes. So one reason to keep the Bitcoin chain for finance is it's unfair to externalize the costs of unrelated schemes onto people who are interested only in payments - the canonical example being merchants. Increasing the cost of accepting Bitcoins for goods and services hurts everyone who uses the system by reducing the number of merchants or increasing their costs.

* Another reason is that it's just bad engineering to cram every possible distributed quorum into the design constraints of Bitcoin. The transaction format Bitcoin uses is flexible but ultimately designed for finance. You cannot leave out the "value" field. It's always there, even if it'd make no sense for your particular application. Building non-financial applications on top of a financial system results in bizarre protocols and code that are difficult to understand, leading to maintainability problems.

* One final reason is that Satoshi was opposed to putting non-Bitcoin related data into the main chain. As creator of the system, his opinion should carry a lot of weight with anyone serious about extending it.

=== Designing a new network ===

To create a new network that uses Nakamoto block chains, you need to start by defining what a transaction in your new network means. Bitcoin transactions split and combine value using scripts, but yours don't have to do that. They could be anything. Here's an example of a simple DNS style "transaction" described using [http://code.google.com/p/protobuf/ Google protocol buffers] syntax.

message NameTx {
required string name = 1;
repeated bytes ip_addresses = 2;
required bytes pubkey = 3;
enum ClaimType {
NEW_NAME,
TRANSFER
}
required ClaimType type = 4;

// Only used if type == TRANSFER. The new owner of the name and signature proving current ownership.
optional bytes dest_pubkey = 5;
optional bytes signature = 6;
}

This is very different to a Bitcoin style transaction. There's no concept of inputs, outputs, addresses, values or scripts. It's got what you need for a very simple DNS style scheme (that lacks abuse controls etc) and nothing more. There's also no concept of a "coinbase" transaction.

The block definition is also up to you. It does not have to be formatted in the same way as Satoshi chose, but you need most of the same conceptual parts. You also need to store something else, some data from Bitcoin. Here's a minimal example of what's needed:

message MyBlock {
required bytes prev_block_hash = 1;
required uint32 difficulty = 2;
required uint32 time = 3;

repeated MyTx transactions = 4;
}

message SuperBlock {
required MyBlock my_data = 1;
required BitcoinData bitcoin_data = 2;
}

It's important to observe what we don't have as well as what we do. We don't have the following fields from Satoshis format:

# version: protobufs handles the versioning of binary data formats for us
# merkle root: you can choose to arrange your transactions into a merkle root if you like, so you can use the same disk space reclamation trick Satoshi did. But it's strictly optional. If you want to simplify things down you can skip it.
# nonce

=== Sharing work ===

The bitcoin_data field is how you share work with miners today (assuming they opt in by installing your software alongside their bitcoin node). It's defined like this:

message BitcoinData {
// A Bitcoin format block header. Because it's in Satoshis custom format we represent this as a byte array.
required bytes header = 1;

// The first transaction from the block.
required bytes coinbase_tx = 2;

// The merkle branch linking the coinbase transaction to the header.
required bytes coinbase_merkle_branch = 3;

// The coinbase scriptSig contains bits of data in order. Which one is our hash?
required int coinbase_tx_index = 4;
}

All you need to share work is the above four things.

A [[wikipedia:Merkle tree]] is a data structure in which each node in the tree is a hash. The leaf nodes are hashes of the things you want to include in the tree. The interior nodes are hashes of the concatenations of the child nodes. A merkle branch is a part of a merkle tree which allows you to cryptographically prove that something you're given was in the tree, without needing everything that was in the tree. They are calculated by the CBlock::GetMerkleBranch() function in the Bitcoin code.

We store a merkle branch here for efficiency. It means no matter how large the current Bitcoin block is, your alternative network only needs to handle a small amount of data. You could just store the entire Bitcoin block - that would be simpler but inefficient.

The merkle branch links the coinbase transaction to the block header, so you can prove it was in that block. The coinbase TX is a regular Bitcoin coinbase (that makes new coins and claims fees), except the scriptSig on its input contains an extra entry that todays scriptSigs don't. That extra entry is a hash of your block structure. The coinbase scriptSig today is formatted like this:

void IncrementExtraNonce(CBlock* pblock, CBlockIndex* pindexPrev, unsigned int& nExtraNonce, int64& nPrevTime)
{
.....
pblock->vtx[0].vin[0].scriptSig = CScript() << pblock->nBits << CBigNum(nExtraNonce);
.....
}

Just the difficulty bits and the "extra nonce". But it's actually allowed to contain anything, as long as it's not too big. So in your new blocks it'd be:

<MyBlock hash> <nBits> <nExtraNonce>

To get the MyBlock hash into Bitcoin requires a presently unimplemented RPC command, "setextrahashes". It'd update a global list and the IncrementExtraNonce function would include the extra hashes when the scriptSig is built. This is a very simple change to Bitcoin.

In the scriptSig above the coinbase_tx_index would be zero. It's possible to work on an arbitrary number of alternative chains simultaneously:

<MyBlock hash> <SomeOtherChainBlock hash> <nBits> <nExtraNonce>

in which case the BitcoinData message for SomeOtherChain would be 1 rather than zero.

A more complex change is the other new RPC. Because you have your own chain, it has its own difficulty. Most likely it'll be different to Bitcoins own. So you need a way to tell Bitcoin "when you find a block that matches an extradifficulty, please let me know". To mine on multiple difficulties at once, the node vends work (via getwork) matching the easiest difficulty. When a miner reports finding a solution the difficulty is checked to see which chains it is sufficiently difficult for.

Important note: Your chain has its own difficulty and as such the block creation rate is independent of how much mining takes place.

=== Independent node software ===

Your new network has its own codebase. It can be written in whatever language you like, use whatever P2P protocol you like, store its data however you like and so on.

When a node on your network receives a message informing it about a new transaction, it verifies that transaction follows the rules of your network. To use our simple DNS example it would verify that if you're claiming a new name, it doesn't already exist and if you're transferring a name that the signatures are correct.

If the transaction is valid, it's added to your current MyBlock message. That message is serialized to binary (protobufs does this for you), hashed and then your node makes an RPC to Bitcoin telling it what the current extra hash is. When Bitcoin finds a Bitcoin-format block of the right difficulty for your network, it informs your software and passes the block header, coinbase transaction and merkle branch to it. Your node combines them together into a BitcoinData message, which is then glued together with your alternative chains block. This "superblock" is then broadcast via your independent P2P network.

When a node on your new network receives a superblock it does the following things:

# Verifies the MyBlock contents are correct, ie, that the transactions follow the rules.
# Verifies that the MyBlock prev hash makes it fit somewhere in the chain and that the difficulty is correct.
# Hashes the MyBlock structure and then verifies that this hash appears in the BitcoinData coinbase scriptSig, in the right place.
# Extracts the merkle root of the Bitcoin format block from the header and then verifies that the coinbase tx provided did, in fact, exist in that block (using the branch, root, tx and header together).
# Verifies that the hash of the Bitcoin format block header is below the difficulty found in the MyBlock structure.

You've now verified that a sufficiently hard proof of work was done over the contents of the MyBlock structure, so your node can relay the newly found block (or if you don't use a P2P network make it available on your server, etc).

On the other side when Bitcoin finds a block that is correct for the Bitcoin network and chain, it broadcasts it and obviously the hash of your MyBlock is included. Fortunately this is only an additional 33 bytes overhead so nobody cares about it - the pollution of the financial chain is both trivial and constant. Note that regular Bitcoin nodes just ignore this extra hash, it doesn't mean anything to them.

=== Handling your new block chain ===

You have to handle re-organizations. This is a standard part of the block chain algorithm. When a re-org occurs you have to verify that the state of your world still makes sense. For example in the new chain maybe somebody else now owns a resource you thought you owned. It's up to you how to inform your users of these events and what app specific logic is appropriate here.

You can choose your own parameters for the new chain. As an example, Satoshi chose to target one new block every ten minutes as a tradeoff between latency and wasted work. You could choose something much larger (hours, days) or much faster if you're willing to tolerate more splits due to blocks being found simultaneously. Bitcoin retargets the difficulty roughly every two weeks. You could choose some other length of time.

To store the block chain, Satoshi chose to use Berkeley DB as a way to index from transactions to the blocks they appeared in (amongst other things). You could use any database you liked.

=== Paying for resources on alternative chains with Bitcoins ===

A commonly cited reason for putting DNS related data into the financial chain is the desire to pay for names with Bitcoins. You can do this with an independent chain too, because you make the rules and can link the two chains together as you see fit.

To start, decide on the purpose of your payments and who will receive the coins - if anyone. In the case of a DNS system, there are two reasons you might want to pay for names:

# To prevent abuse by people claiming all interesting names via a dictionary attack.
# To incentivise people to run your software and mine on your alternative chain.

In the first case really nobody should receive the payment. The money is being put up as a collateral and has no other use, so as long as it's sitting around unspent that is good enough. In the second case the payment should go to the miner working on the DNS chain.

To implement this we extend our hypothetical DNS transaction message like this:

message NameTx {
required string name = 1;
repeated bytes ip_addresses = 2;
required bytes pubkey = 3;
enum ClaimType {
NEW_NAME,
TRANSFER
}
required ClaimType type = 4;

// Only used if type == TRANSFER. The new owner of the name and signature proving current ownership.
optional bytes dest_pubkey = 5;
optional bytes signature = 6;

// Only used if type == NEW_NAME.
optional bytes collateral_signature = 7;
optional string miner_address = 8;
optional uint64 miner_fee = 9;
}

The collateral_signature field contains an ECDSA signature generated from a public key that holds some Bitcoins. The miner address is blank when the name purchaser creates the transaction and is filled out after a miner receives it, but before they begin working on it.

To buy a name that costs 10 BTC with a miner fee of 2 BTC, a user presses the "buy name" button in their DNS software. It talks to their local Bitcoin node via RPC and does the following:

# Creates a new Bitcoin address (key).
# Sends 10 BTC to the new address (a send-to-self transaction).
# Extracts the key from Bitcoin, meaning it's no longer available to spend in your wallet.
# Stores the key in a local DNS data file ("wallet") somewhere.
# Sets the miner_fee field to the pre-agreed value of 2 BTC.
# Takes the public key part and uses it to sign a version of the NameTx that lacks collateral_signature (a signature can't sign itself) and miner_address.
# The signature is placed in collateral_signature field.
# The transaction is sent to a miner who charges 2 BTC.

When the miner receives the transaction, it verifies that the 10 BTC is not spent:

# The ECDSA public key recovery algorithm is run on the collateral_signature. It can yield several possible keys.
# The public keys recovered are used to verify the signature is correct. This step also figures out which of the possible keys is the right one.
# The correct public key is turned into a Bitcoin address (by hashing it)
# The DNS node software queries Bitcoin to discover whether that address has 10 BTC associated with it, or whether the balance of that address is lower. Note that todays software does not index the balance of every address in the system, but it can be added (the Block Explorer does this).
# If the address does indeed have 10 unspent Bitcoins then the collateral is present and it's OK to serve the name

The miner then creates a new Bitcoin address for themselves and sets miner_address to contain it, then includes it into the current block being worked on. After a block matching the DNS chains difficulty is found, it is broadcast. Other nodes do the following:

# For each transaction, repeat the verification steps to ensure the collateral is not spent.
# Check the balance of the miners own address.
# If the balance is not yet equal to miner_fee, the name is put into a "pending" state in which it is owned but not served in response to DNS queries.

The user observes the broadcast and sees that their name is now pending payment, so they send 2 BTC to the address they find in their transaction. As nodes notice the payment becoming confirmed they start responding to DNS queries for that name (ie, the ownership process is complete).

When the user gets tired of owning the name, he can simply re-import the collateral key into his wallet and spend the coins. The DNS network will soon observe that the coins are spent and make the name available for purchasing by somebody else.

=== Incentivising non-resource based chains ===

It's possible to incentivise mining on an alt-chain even if that chain does not have any concept of ownership, ie, if the act of finding a block itself is what is being paid for. An example of this is a timestamping chain in which presence in a block alone is sufficient to satisfy the user.

To implement this, set up a new chain as normal. Blocks in this new chain arrange transactions into a merkle tree in the same manner as Bitcoin does. A client that wants something incorporated into a block connects directly to some miners and submits their transaction. The miners add their address to the transaction as normal. Once a miner finds a block, it immediately sends the block to connected clients whose transactions made it in, but does not broadcast the new block to other miners. The clients respond with a valid Bitcoin transaction which pays for block inclusion. Once all clients have paid up the transaction is broadcast.

If a client has disconnected or does not pay quickly enough, their transaction can be replaced inside the block with its hash. In this way the blocks validity is preserved because the merkle tree is still valid. The newly found alt-block is broadcast, minus the transaction of the delinquent customer. As long as clients are still connected the payment process for all found transactions can be completed quickly: it would only take a few seconds to gather the payments and broadcast those on the Bitcoin network, minimizing the chance of a race that would require you to trust the miner to reinclude your transactions in the next block despite having already been paid.

=== Mining on the alt-chain but not Bitcoin ===

So far we've considered a scheme in which all alt-chain miners simultaneously mine on Bitcoin. It's possible some people may wish to mine on your chain but not Bitcoin, perhaps because the cost of keeping up with the Bitcoin transaction rate has become too high for them to bother.

To mine without an attached Bitcoin node, your software can simply implement the same getwork protocol Bitcoin itself does. When a mining tool requests work your program would generate a correctly formatted but ultimately bogus Bitcoin block. The contents of this block don't need to be correct because it will never be broadcast on the Bitcoin network, for example, the prevBlockHash field can be all zeros. It exists purely for backwards compatibility. Whilst the block needs a valid merkle root and a coinbase transaction, no other transactions are required and the only part of the coinbase tx that matters is the part holding the hash.

=== Scaling up ===

In the simple scheme each alt-chain being worked on needs 33 bytes in the Bitcoin coinbase transaction (1 for the length and 32 for the hash). Note that if there are two independent miners working on two different alt-chains, you still only need 1 hash in the coinbase scriptSig because the hash isn't meaningful to anyone else on the Bitcoin network. If miners only want to work a handful of chains this overhead is trivially dwarfed by the rest of the data in a Bitcoin block.

But if a miner wishes to work on hundreds, thousands or millions of alternative chains the size of the coinbase scriptSig would balloon and become unworkable. To solve this, the hash stored in the scriptSig can be the root of yet another merkle tree, this time a tree over the hashes of all blocks being worked on. The BitcoinData message is extended like this:

message MyBlock {
required bytes prev_block_hash = 1;
required uint32 difficulty = 2;
required uint32 time = 3;

repeated MyTx transactions = 4;
}

message SuperBlock {
required MyBlock my_data = 1;
required BitcoinData bitcoin_data = 2;
}

message BitcoinData {
// A Bitcoin format block header. Because it's in Satoshis custom format we represent this as a byte array.
required bytes header = 1;

// The first transaction from the block.
required bytes coinbase_tx = 2;

// The merkle branch linking the coinbase transaction to the header.
required bytes coinbase_merkle_branch = 3;

// The merkle branch linking MyBlock to the merkle root in the coinbase_tx.
required bytes altblock_merkle_branch = 4;
}

The verification step becomes a bit more complex:

# Verify the header is of sufficient difficulty for the alt-chain
# Verify coinbase_tx was a part of that block by checking the coinbase_merkle_branch is linked to the merkle root in the header.
# Extract the root of the second merkle tree from the coinbase_tx (call it 2MR).
# Hash the alt-chain block (my_data), verify that altblock_merkle_branch links the my_data hash to 2MR.

You have now proven that the MyBlock instance was worked on, along with perhaps thousands of other chains you don't have to know anything about.

This is an advanced technique which is probably not worth implementing unless the additional scalability is required. It can be introduced in a backwards compatible manner for new chains without impacting older networks.

=== Generalized proof of work ===

Hashes embedded in transactions and headers, merkle branches, and [[Nonce|nonces]] all contribute to the goal of [[Proof of work|proving work]] on a block header. One can express all as sequences of these basic operations:

* prepend a byte string to the current data
* append a byte string to the current data
* hash the current data

For maximum flexibility, a work-sharing chain's block acceptance algorithm might accept proof in the form of a script using just these operations. The script would receive as input an alternative chain block header, and the hash of its output would have to satisfy the chain's difficulty.

This design would even support plain Bitcoin proof of work, where the "header" consists of all [[Protocol Specification#block|Bitcoin block header fields]] except the nonce, and the proof-of-work script would simply append the nonce. Thus, one can think of the work-sharing rules as an extension of the original Bitcoin rules.

[[Category:Technical]]

Alternative chain

2011-06-29T15:26:58Z

JohnTobey253: /* Generalized proof of work */ minor correction.

An '''alternative chain''' is a system using the block chain algorithm to achieve distributed consensus on a particular topic, whilst sharing miners with the Bitcoin network. Alternative chains have been suggested as ways to implement DNS, SSL certificate authorities, timestamping, file storage and voting systems.

=== Objective ===

Bitcoin uses the [[block chain]] algorithm to achieve distributed consensus on who owns what coins. Block chains were invented specifically for the Bitcoin project but they can be applied anywhere a distributed consensus needs to be established in the presence of malicious or untrustworthy actors.

Whilst it's possible to abuse the Bitcoin financial block chain for other purposes, it's better to set up an alternative network and chain which share the same miners. There are several reasons to do this.

* The block chain is a large, complex data structure shared between many people. Verifying its integrity requires many slow (and thus expensive) operations like ECDSA verifications and disk seeks. Everyone who takes part in Bitcoin today runs a node and thus maintains the whole thing. Whilst in future end-users will probably use more efficient but slightly less secure modes (SPV), merchants and miners will probably always pay the full costs for the upkeep of this shared data structure. All these people today are united by a common interest in a new form of payments. They may or may not also be interested in other schemes. So one reason to keep the Bitcoin chain for finance is it's unfair to externalize the costs of unrelated schemes onto people who are interested only in payments - the canonical example being merchants. Increasing the cost of accepting Bitcoins for goods and services hurts everyone who uses the system by reducing the number of merchants or increasing their costs.

* Another reason is that it's just bad engineering to cram every possible distributed quorum into the design constraints of Bitcoin. The transaction format Bitcoin uses is flexible but ultimately designed for finance. You cannot leave out the "value" field. It's always there, even if it'd make no sense for your particular application. Building non-financial applications on top of a financial system results in bizarre protocols and code that are difficult to understand, leading to maintainability problems.

* One final reason is that Satoshi was opposed to putting non-Bitcoin related data into the main chain. As creator of the system, his opinion should carry a lot of weight with anyone serious about extending it.

=== Designing a new network ===

To create a new network that uses Nakamoto block chains, you need to start by defining what a transaction in your new network means. Bitcoin transactions split and combine value using scripts, but yours don't have to do that. They could be anything. Here's an example of a simple DNS style "transaction" described using [http://code.google.com/p/protobuf/ Google protocol buffers] syntax.

message NameTx {
required string name = 1;
repeated bytes ip_addresses = 2;
required bytes pubkey = 3;
enum ClaimType {
NEW_NAME,
TRANSFER
}
required ClaimType type = 4;

// Only used if type == TRANSFER. The new owner of the name and signature proving current ownership.
optional bytes dest_pubkey = 5;
optional bytes signature = 6;
}

This is very different to a Bitcoin style transaction. There's no concept of inputs, outputs, addresses, values or scripts. It's got what you need for a very simple DNS style scheme (that lacks abuse controls etc) and nothing more. There's also no concept of a "coinbase" transaction.

The block definition is also up to you. It does not have to be formatted in the same way as Satoshi chose, but you need most of the same conceptual parts. You also need to store something else, some data from Bitcoin. Here's a minimal example of what's needed:

message MyBlock {
required bytes prev_block_hash = 1;
required uint32 difficulty = 2;
required uint32 time = 3;

repeated MyTx transactions = 4;
}

message SuperBlock {
required MyBlock my_data = 1;
required BitcoinData bitcoin_data = 2;
}

It's important to observe what we don't have as well as what we do. We don't have the following fields from Satoshis format:

# version: protobufs handles the versioning of binary data formats for us
# merkle root: you can choose to arrange your transactions into a merkle root if you like, so you can use the same disk space reclamation trick Satoshi did. But it's strictly optional. If you want to simplify things down you can skip it.
# nonce

=== Sharing work ===

The bitcoin_data field is how you share work with miners today (assuming they opt in by installing your software alongside their bitcoin node). It's defined like this:

message BitcoinData {
// A Bitcoin format block header. Because it's in Satoshis custom format we represent this as a byte array.
required bytes header = 1;

// The first transaction from the block.
required bytes coinbase_tx = 2;

// The merkle branch linking the coinbase transaction to the header.
required bytes coinbase_merkle_branch = 3;

// The coinbase scriptSig contains bits of data in order. Which one is our hash?
required int coinbase_tx_index = 4;
}

All you need to share work is the above four things.

A [[wikipedia:Merkle tree]] is a data structure in which each node in the tree is a hash. The leaf nodes are hashes of the things you want to include in the tree. The interior nodes are hashes of the concatenations of the child nodes. A merkle branch is a part of a merkle tree which allows you to cryptographically prove that something you're given was in the tree, without needing everything that was in the tree. They are calculated by the CBlock::GetMerkleBranch() function in the Bitcoin code.

We store a merkle branch here for efficiency. It means no matter how large the current Bitcoin block is, your alternative network only needs to handle a small amount of data. You could just store the entire Bitcoin block - that would be simpler but inefficient.

The merkle branch links the coinbase transaction to the block header, so you can prove it was in that block. The coinbase TX is a regular Bitcoin coinbase (that makes new coins and claims fees), except the scriptSig on its input contains an extra entry that todays scriptSigs don't. That extra entry is a hash of your block structure. The coinbase scriptSig today is formatted like this:

void IncrementExtraNonce(CBlock* pblock, CBlockIndex* pindexPrev, unsigned int& nExtraNonce, int64& nPrevTime)
{
.....
pblock->vtx[0].vin[0].scriptSig = CScript() << pblock->nBits << CBigNum(nExtraNonce);
.....
}

Just the difficulty bits and the "extra nonce". But it's actually allowed to contain anything, as long as it's not too big. So in your new blocks it'd be:

<MyBlock hash> <nBits> <nExtraNonce>

To get the MyBlock hash into Bitcoin requires a presently unimplemented RPC command, "setextrahashes". It'd update a global list and the IncrementExtraNonce function would include the extra hashes when the scriptSig is built. This is a very simple change to Bitcoin.

In the scriptSig above the coinbase_tx_index would be zero. It's possible to work on an arbitrary number of alternative chains simultaneously:

<MyBlock hash> <SomeOtherChainBlock hash> <nBits> <nExtraNonce>

in which case the BitcoinData message for SomeOtherChain would be 1 rather than zero.

A more complex change is the other new RPC. Because you have your own chain, it has its own difficulty. Most likely it'll be different to Bitcoins own. So you need a way to tell Bitcoin "when you find a block that matches an extradifficulty, please let me know". To mine on multiple difficulties at once, the node vends work (via getwork) matching the easiest difficulty. When a miner reports finding a solution the difficulty is checked to see which chains it is sufficiently difficult for.

Important note: Your chain has its own difficulty and as such the block creation rate is independent of how much mining takes place.

=== Independent node software ===

Your new network has its own codebase. It can be written in whatever language you like, use whatever P2P protocol you like, store its data however you like and so on.

When a node on your network receives a message informing it about a new transaction, it verifies that transaction follows the rules of your network. To use our simple DNS example it would verify that if you're claiming a new name, it doesn't already exist and if you're transferring a name that the signatures are correct.

If the transaction is valid, it's added to your current MyBlock message. That message is serialized to binary (protobufs does this for you), hashed and then your node makes an RPC to Bitcoin telling it what the current extra hash is. When Bitcoin finds a Bitcoin-format block of the right difficulty for your network, it informs your software and passes the block header, coinbase transaction and merkle branch to it. Your node combines them together into a BitcoinData message, which is then glued together with your alternative chains block. This "superblock" is then broadcast via your independent P2P network.

When a node on your new network receives a superblock it does the following things:

# Verifies the MyBlock contents are correct, ie, that the transactions follow the rules.
# Verifies that the MyBlock prev hash makes it fit somewhere in the chain and that the difficulty is correct.
# Hashes the MyBlock structure and then verifies that this hash appears in the BitcoinData coinbase scriptSig, in the right place.
# Extracts the merkle root of the Bitcoin format block from the header and then verifies that the coinbase tx provided did, in fact, exist in that block (using the branch, root, tx and header together).
# Verifies that the hash of the Bitcoin format block header is below the difficulty found in the MyBlock structure.

You've now verified that a sufficiently hard proof of work was done over the contents of the MyBlock structure, so your node can relay the newly found block (or if you don't use a P2P network make it available on your server, etc).

On the other side when Bitcoin finds a block that is correct for the Bitcoin network and chain, it broadcasts it and obviously the hash of your MyBlock is included. Fortunately this is only an additional 33 bytes overhead so nobody cares about it - the pollution of the financial chain is both trivial and constant. Note that regular Bitcoin nodes just ignore this extra hash, it doesn't mean anything to them.

=== Handling your new block chain ===

You have to handle re-organizations. This is a standard part of the block chain algorithm. When a re-org occurs you have to verify that the state of your world still makes sense. For example in the new chain maybe somebody else now owns a resource you thought you owned. It's up to you how to inform your users of these events and what app specific logic is appropriate here.

You can choose your own parameters for the new chain. As an example, Satoshi chose to target one new block every ten minutes as a tradeoff between latency and wasted work. You could choose something much larger (hours, days) or much faster if you're willing to tolerate more splits due to blocks being found simultaneously. Bitcoin retargets the difficulty roughly every two weeks. You could choose some other length of time.

To store the block chain, Satoshi chose to use Berkeley DB as a way to index from transactions to the blocks they appeared in (amongst other things). You could use any database you liked.

=== Paying for resources on alternative chains with Bitcoins ===

A commonly cited reason for putting DNS related data into the financial chain is the desire to pay for names with Bitcoins. You can do this with an independent chain too, because you make the rules and can link the two chains together as you see fit.

To start, decide on the purpose of your payments and who will receive the coins - if anyone. In the case of a DNS system, there are two reasons you might want to pay for names:

# To prevent abuse by people claiming all interesting names via a dictionary attack.
# To incentivise people to run your software and mine on your alternative chain.

In the first case really nobody should receive the payment. The money is being put up as a collateral and has no other use, so as long as it's sitting around unspent that is good enough. In the second case the payment should go to the miner working on the DNS chain.

To implement this we extend our hypothetical DNS transaction message like this:

message NameTx {
required string name = 1;
repeated bytes ip_addresses = 2;
required bytes pubkey = 3;
enum ClaimType {
NEW_NAME,
TRANSFER
}
required ClaimType type = 4;

// Only used if type == TRANSFER. The new owner of the name and signature proving current ownership.
optional bytes dest_pubkey = 5;
optional bytes signature = 6;

// Only used if type == NEW_NAME.
optional bytes collateral_signature = 7;
optional string miner_address = 8;
optional uint64 miner_fee = 9;
}

The collateral_signature field contains an ECDSA signature generated from a public key that holds some Bitcoins. The miner address is blank when the name purchaser creates the transaction and is filled out after a miner receives it, but before they begin working on it.

To buy a name that costs 10 BTC with a miner fee of 2 BTC, a user presses the "buy name" button in their DNS software. It talks to their local Bitcoin node via RPC and does the following:

# Creates a new Bitcoin address (key).
# Sends 10 BTC to the new address (a send-to-self transaction).
# Extracts the key from Bitcoin, meaning it's no longer available to spend in your wallet.
# Stores the key in a local DNS data file ("wallet") somewhere.
# Sets the miner_fee field to the pre-agreed value of 2 BTC.
# Takes the public key part and uses it to sign a version of the NameTx that lacks collateral_signature (a signature can't sign itself) and miner_address.
# The signature is placed in collateral_signature field.
# The transaction is sent to a miner who charges 2 BTC.

When the miner receives the transaction, it verifies that the 10 BTC is not spent:

# The ECDSA public key recovery algorithm is run on the collateral_signature. It can yield several possible keys.
# The public keys recovered are used to verify the signature is correct. This step also figures out which of the possible keys is the right one.
# The correct public key is turned into a Bitcoin address (by hashing it)
# The DNS node software queries Bitcoin to discover whether that address has 10 BTC associated with it, or whether the balance of that address is lower. Note that todays software does not index the balance of every address in the system, but it can be added (the Block Explorer does this).
# If the address does indeed have 10 unspent Bitcoins then the collateral is present and it's OK to serve the name

The miner then creates a new Bitcoin address for themselves and sets miner_address to contain it, then includes it into the current block being worked on. After a block matching the DNS chains difficulty is found, it is broadcast. Other nodes do the following:

# For each transaction, repeat the verification steps to ensure the collateral is not spent.
# Check the balance of the miners own address.
# If the balance is not yet equal to miner_fee, the name is put into a "pending" state in which it is owned but not served in response to DNS queries.

The user observes the broadcast and sees that their name is now pending payment, so they send 2 BTC to the address they find in their transaction. As nodes notice the payment becoming confirmed they start responding to DNS queries for that name (ie, the ownership process is complete).

When the user gets tired of owning the name, he can simply re-import the collateral key into his wallet and spend the coins. The DNS network will soon observe that the coins are spent and make the name available for purchasing by somebody else.

=== Incentivising non-resource based chains ===

It's possible to incentivise mining on an alt-chain even if that chain does not have any concept of ownership, ie, if the act of finding a block itself is what is being paid for. An example of this is a timestamping chain in which presence in a block alone is sufficient to satisfy the user.

To implement this, set up a new chain as normal. Blocks in this new chain arrange transactions into a merkle tree in the same manner as Bitcoin does. A client that wants something incorporated into a block connects directly to some miners and submits their transaction. The miners add their address to the transaction as normal. Once a miner finds a block, it immediately sends the block to connected clients whose transactions made it in, but does not broadcast the new block to other miners. The clients respond with a valid Bitcoin transaction which pays for block inclusion. Once all clients have paid up the transaction is broadcast.

If a client has disconnected or does not pay quickly enough, their transaction can be replaced inside the block with its hash. In this way the blocks validity is preserved because the merkle tree is still valid. The newly found alt-block is broadcast, minus the transaction of the delinquent customer. As long as clients are still connected the payment process for all found transactions can be completed quickly: it would only take a few seconds to gather the payments and broadcast those on the Bitcoin network, minimizing the chance of a race that would require you to trust the miner to reinclude your transactions in the next block despite having already been paid.

=== Mining on the alt-chain but not Bitcoin ===

So far we've considered a scheme in which all alt-chain miners simultaneously mine on Bitcoin. It's possible some people may wish to mine on your chain but not Bitcoin, perhaps because the cost of keeping up with the Bitcoin transaction rate has become too high for them to bother.

To mine without an attached Bitcoin node, your software can simply implement the same getwork protocol Bitcoin itself does. When a mining tool requests work your program would generate a correctly formatted but ultimately bogus Bitcoin block. The contents of this block don't need to be correct because it will never be broadcast on the Bitcoin network, for example, the prevBlockHash field can be all zeros. It exists purely for backwards compatibility. Whilst the block needs a valid merkle root and a coinbase transaction, no other transactions are required and the only part of the coinbase tx that matters is the part holding the hash.

=== Scaling up ===

In the simple scheme each alt-chain being worked on needs 33 bytes in the Bitcoin coinbase transaction (1 for the length and 32 for the hash). Note that if there are two independent miners working on two different alt-chains, you still only need 1 hash in the coinbase scriptSig because the hash isn't meaningful to anyone else on the Bitcoin network. If miners only want to work a handful of chains this overhead is trivially dwarfed by the rest of the data in a Bitcoin block.

But if a miner wishes to work on hundreds, thousands or millions of alternative chains the size of the coinbase scriptSig would balloon and become unworkable. To solve this, the hash stored in the scriptSig can be the root of yet another merkle tree, this time a tree over the hashes of all blocks being worked on. The BitcoinData message is extended like this:

message MyBlock {
required bytes prev_block_hash = 1;
required uint32 difficulty = 2;
required uint32 time = 3;

repeated MyTx transactions = 4;
}

message SuperBlock {
required MyBlock my_data = 1;
required BitcoinData bitcoin_data = 2;
}

message BitcoinData {
// A Bitcoin format block header. Because it's in Satoshis custom format we represent this as a byte array.
required bytes header = 1;

// The first transaction from the block.
required bytes coinbase_tx = 2;

// The merkle branch linking the coinbase transaction to the header.
required bytes coinbase_merkle_branch = 3;

// The merkle branch linking MyBlock to the merkle root in the coinbase_tx.
required bytes altblock_merkle_branch = 4;
}

The verification step becomes a bit more complex:

# Verify the header is of sufficient difficulty for the alt-chain
# Verify coinbase_tx was a part of that block by checking the coinbase_merkle_branch is linked to the merkle root in the header.
# Extract the root of the second merkle tree from the coinbase_tx (call it 2MR).
# Hash the alt-chain block (my_data), verify that altblock_merkle_branch links the my_data hash to 2MR.

You have now proven that the MyBlock instance was worked on, along with perhaps thousands of other chains you don't have to know anything about.

This is an advanced technique which is probably not worth implementing unless the additional scalability is required. It can be introduced in a backwards compatible manner for new chains without impacting older networks.

=== Generalized proof of work ===

Hashes embedded in transactions, merkle branches, and [[Nonce|nonces]] all contribute to the goal of [[Proof of work|proving work]] on a block header. One can express all three as sequences of these basic operations:

* prepend a byte string to the current data
* append a byte string to the current data
* hash the current data

For maximum flexibility, a work-sharing chain's block acceptance algorithm might accept proof in the form of a script using just these operations. The script would receive as input an alternative chain block header, and the hash of its output would have to match the chain's difficulty.

This design would even support plain Bitcoin proof of work, where the "header" consists of all [[Protocol Specification#block|Bitcoin block header fields]] except the nonce, and the proof-of-work script would simply append the nonce. Thus, one can think of the work-sharing rules as an extension of the original Bitcoin rules.

[[Category:Technical]]

Alternative chain

2011-06-29T15:20:17Z

JohnTobey253: Generalized proof of work

An '''alternative chain''' is a system using the block chain algorithm to achieve distributed consensus on a particular topic, whilst sharing miners with the Bitcoin network. Alternative chains have been suggested as ways to implement DNS, SSL certificate authorities, timestamping, file storage and voting systems.

=== Objective ===

Bitcoin uses the [[block chain]] algorithm to achieve distributed consensus on who owns what coins. Block chains were invented specifically for the Bitcoin project but they can be applied anywhere a distributed consensus needs to be established in the presence of malicious or untrustworthy actors.

Whilst it's possible to abuse the Bitcoin financial block chain for other purposes, it's better to set up an alternative network and chain which share the same miners. There are several reasons to do this.

* The block chain is a large, complex data structure shared between many people. Verifying its integrity requires many slow (and thus expensive) operations like ECDSA verifications and disk seeks. Everyone who takes part in Bitcoin today runs a node and thus maintains the whole thing. Whilst in future end-users will probably use more efficient but slightly less secure modes (SPV), merchants and miners will probably always pay the full costs for the upkeep of this shared data structure. All these people today are united by a common interest in a new form of payments. They may or may not also be interested in other schemes. So one reason to keep the Bitcoin chain for finance is it's unfair to externalize the costs of unrelated schemes onto people who are interested only in payments - the canonical example being merchants. Increasing the cost of accepting Bitcoins for goods and services hurts everyone who uses the system by reducing the number of merchants or increasing their costs.

* Another reason is that it's just bad engineering to cram every possible distributed quorum into the design constraints of Bitcoin. The transaction format Bitcoin uses is flexible but ultimately designed for finance. You cannot leave out the "value" field. It's always there, even if it'd make no sense for your particular application. Building non-financial applications on top of a financial system results in bizarre protocols and code that are difficult to understand, leading to maintainability problems.

* One final reason is that Satoshi was opposed to putting non-Bitcoin related data into the main chain. As creator of the system, his opinion should carry a lot of weight with anyone serious about extending it.

=== Designing a new network ===

To create a new network that uses Nakamoto block chains, you need to start by defining what a transaction in your new network means. Bitcoin transactions split and combine value using scripts, but yours don't have to do that. They could be anything. Here's an example of a simple DNS style "transaction" described using [http://code.google.com/p/protobuf/ Google protocol buffers] syntax.

message NameTx {
required string name = 1;
repeated bytes ip_addresses = 2;
required bytes pubkey = 3;
enum ClaimType {
NEW_NAME,
TRANSFER
}
required ClaimType type = 4;

// Only used if type == TRANSFER. The new owner of the name and signature proving current ownership.
optional bytes dest_pubkey = 5;
optional bytes signature = 6;
}

This is very different to a Bitcoin style transaction. There's no concept of inputs, outputs, addresses, values or scripts. It's got what you need for a very simple DNS style scheme (that lacks abuse controls etc) and nothing more. There's also no concept of a "coinbase" transaction.

The block definition is also up to you. It does not have to be formatted in the same way as Satoshi chose, but you need most of the same conceptual parts. You also need to store something else, some data from Bitcoin. Here's a minimal example of what's needed:

message MyBlock {
required bytes prev_block_hash = 1;
required uint32 difficulty = 2;
required uint32 time = 3;

repeated MyTx transactions = 4;
}

message SuperBlock {
required MyBlock my_data = 1;
required BitcoinData bitcoin_data = 2;
}

It's important to observe what we don't have as well as what we do. We don't have the following fields from Satoshis format:

# version: protobufs handles the versioning of binary data formats for us
# merkle root: you can choose to arrange your transactions into a merkle root if you like, so you can use the same disk space reclamation trick Satoshi did. But it's strictly optional. If you want to simplify things down you can skip it.
# nonce

=== Sharing work ===

The bitcoin_data field is how you share work with miners today (assuming they opt in by installing your software alongside their bitcoin node). It's defined like this:

message BitcoinData {
// A Bitcoin format block header. Because it's in Satoshis custom format we represent this as a byte array.
required bytes header = 1;

// The first transaction from the block.
required bytes coinbase_tx = 2;

// The merkle branch linking the coinbase transaction to the header.
required bytes coinbase_merkle_branch = 3;

// The coinbase scriptSig contains bits of data in order. Which one is our hash?
required int coinbase_tx_index = 4;
}

All you need to share work is the above four things.

A [[wikipedia:Merkle tree]] is a data structure in which each node in the tree is a hash. The leaf nodes are hashes of the things you want to include in the tree. The interior nodes are hashes of the concatenations of the child nodes. A merkle branch is a part of a merkle tree which allows you to cryptographically prove that something you're given was in the tree, without needing everything that was in the tree. They are calculated by the CBlock::GetMerkleBranch() function in the Bitcoin code.

We store a merkle branch here for efficiency. It means no matter how large the current Bitcoin block is, your alternative network only needs to handle a small amount of data. You could just store the entire Bitcoin block - that would be simpler but inefficient.

The merkle branch links the coinbase transaction to the block header, so you can prove it was in that block. The coinbase TX is a regular Bitcoin coinbase (that makes new coins and claims fees), except the scriptSig on its input contains an extra entry that todays scriptSigs don't. That extra entry is a hash of your block structure. The coinbase scriptSig today is formatted like this:

void IncrementExtraNonce(CBlock* pblock, CBlockIndex* pindexPrev, unsigned int& nExtraNonce, int64& nPrevTime)
{
.....
pblock->vtx[0].vin[0].scriptSig = CScript() << pblock->nBits << CBigNum(nExtraNonce);
.....
}

Just the difficulty bits and the "extra nonce". But it's actually allowed to contain anything, as long as it's not too big. So in your new blocks it'd be:

<MyBlock hash> <nBits> <nExtraNonce>

To get the MyBlock hash into Bitcoin requires a presently unimplemented RPC command, "setextrahashes". It'd update a global list and the IncrementExtraNonce function would include the extra hashes when the scriptSig is built. This is a very simple change to Bitcoin.

In the scriptSig above the coinbase_tx_index would be zero. It's possible to work on an arbitrary number of alternative chains simultaneously:

<MyBlock hash> <SomeOtherChainBlock hash> <nBits> <nExtraNonce>

in which case the BitcoinData message for SomeOtherChain would be 1 rather than zero.

A more complex change is the other new RPC. Because you have your own chain, it has its own difficulty. Most likely it'll be different to Bitcoins own. So you need a way to tell Bitcoin "when you find a block that matches an extradifficulty, please let me know". To mine on multiple difficulties at once, the node vends work (via getwork) matching the easiest difficulty. When a miner reports finding a solution the difficulty is checked to see which chains it is sufficiently difficult for.

Important note: Your chain has its own difficulty and as such the block creation rate is independent of how much mining takes place.

=== Independent node software ===

Your new network has its own codebase. It can be written in whatever language you like, use whatever P2P protocol you like, store its data however you like and so on.

When a node on your network receives a message informing it about a new transaction, it verifies that transaction follows the rules of your network. To use our simple DNS example it would verify that if you're claiming a new name, it doesn't already exist and if you're transferring a name that the signatures are correct.

If the transaction is valid, it's added to your current MyBlock message. That message is serialized to binary (protobufs does this for you), hashed and then your node makes an RPC to Bitcoin telling it what the current extra hash is. When Bitcoin finds a Bitcoin-format block of the right difficulty for your network, it informs your software and passes the block header, coinbase transaction and merkle branch to it. Your node combines them together into a BitcoinData message, which is then glued together with your alternative chains block. This "superblock" is then broadcast via your independent P2P network.

When a node on your new network receives a superblock it does the following things:

# Verifies the MyBlock contents are correct, ie, that the transactions follow the rules.
# Verifies that the MyBlock prev hash makes it fit somewhere in the chain and that the difficulty is correct.
# Hashes the MyBlock structure and then verifies that this hash appears in the BitcoinData coinbase scriptSig, in the right place.
# Extracts the merkle root of the Bitcoin format block from the header and then verifies that the coinbase tx provided did, in fact, exist in that block (using the branch, root, tx and header together).
# Verifies that the hash of the Bitcoin format block header is below the difficulty found in the MyBlock structure.

You've now verified that a sufficiently hard proof of work was done over the contents of the MyBlock structure, so your node can relay the newly found block (or if you don't use a P2P network make it available on your server, etc).

On the other side when Bitcoin finds a block that is correct for the Bitcoin network and chain, it broadcasts it and obviously the hash of your MyBlock is included. Fortunately this is only an additional 33 bytes overhead so nobody cares about it - the pollution of the financial chain is both trivial and constant. Note that regular Bitcoin nodes just ignore this extra hash, it doesn't mean anything to them.

=== Handling your new block chain ===

You have to handle re-organizations. This is a standard part of the block chain algorithm. When a re-org occurs you have to verify that the state of your world still makes sense. For example in the new chain maybe somebody else now owns a resource you thought you owned. It's up to you how to inform your users of these events and what app specific logic is appropriate here.

You can choose your own parameters for the new chain. As an example, Satoshi chose to target one new block every ten minutes as a tradeoff between latency and wasted work. You could choose something much larger (hours, days) or much faster if you're willing to tolerate more splits due to blocks being found simultaneously. Bitcoin retargets the difficulty roughly every two weeks. You could choose some other length of time.

To store the block chain, Satoshi chose to use Berkeley DB as a way to index from transactions to the blocks they appeared in (amongst other things). You could use any database you liked.

=== Paying for resources on alternative chains with Bitcoins ===

A commonly cited reason for putting DNS related data into the financial chain is the desire to pay for names with Bitcoins. You can do this with an independent chain too, because you make the rules and can link the two chains together as you see fit.

To start, decide on the purpose of your payments and who will receive the coins - if anyone. In the case of a DNS system, there are two reasons you might want to pay for names:

# To prevent abuse by people claiming all interesting names via a dictionary attack.
# To incentivise people to run your software and mine on your alternative chain.

In the first case really nobody should receive the payment. The money is being put up as a collateral and has no other use, so as long as it's sitting around unspent that is good enough. In the second case the payment should go to the miner working on the DNS chain.

To implement this we extend our hypothetical DNS transaction message like this:

message NameTx {
required string name = 1;
repeated bytes ip_addresses = 2;
required bytes pubkey = 3;
enum ClaimType {
NEW_NAME,
TRANSFER
}
required ClaimType type = 4;

// Only used if type == TRANSFER. The new owner of the name and signature proving current ownership.
optional bytes dest_pubkey = 5;
optional bytes signature = 6;

// Only used if type == NEW_NAME.
optional bytes collateral_signature = 7;
optional string miner_address = 8;
optional uint64 miner_fee = 9;
}

The collateral_signature field contains an ECDSA signature generated from a public key that holds some Bitcoins. The miner address is blank when the name purchaser creates the transaction and is filled out after a miner receives it, but before they begin working on it.

To buy a name that costs 10 BTC with a miner fee of 2 BTC, a user presses the "buy name" button in their DNS software. It talks to their local Bitcoin node via RPC and does the following:

# Creates a new Bitcoin address (key).
# Sends 10 BTC to the new address (a send-to-self transaction).
# Extracts the key from Bitcoin, meaning it's no longer available to spend in your wallet.
# Stores the key in a local DNS data file ("wallet") somewhere.
# Sets the miner_fee field to the pre-agreed value of 2 BTC.
# Takes the public key part and uses it to sign a version of the NameTx that lacks collateral_signature (a signature can't sign itself) and miner_address.
# The signature is placed in collateral_signature field.
# The transaction is sent to a miner who charges 2 BTC.

When the miner receives the transaction, it verifies that the 10 BTC is not spent:

# The ECDSA public key recovery algorithm is run on the collateral_signature. It can yield several possible keys.
# The public keys recovered are used to verify the signature is correct. This step also figures out which of the possible keys is the right one.
# The correct public key is turned into a Bitcoin address (by hashing it)
# The DNS node software queries Bitcoin to discover whether that address has 10 BTC associated with it, or whether the balance of that address is lower. Note that todays software does not index the balance of every address in the system, but it can be added (the Block Explorer does this).
# If the address does indeed have 10 unspent Bitcoins then the collateral is present and it's OK to serve the name

The miner then creates a new Bitcoin address for themselves and sets miner_address to contain it, then includes it into the current block being worked on. After a block matching the DNS chains difficulty is found, it is broadcast. Other nodes do the following:

# For each transaction, repeat the verification steps to ensure the collateral is not spent.
# Check the balance of the miners own address.
# If the balance is not yet equal to miner_fee, the name is put into a "pending" state in which it is owned but not served in response to DNS queries.

The user observes the broadcast and sees that their name is now pending payment, so they send 2 BTC to the address they find in their transaction. As nodes notice the payment becoming confirmed they start responding to DNS queries for that name (ie, the ownership process is complete).

When the user gets tired of owning the name, he can simply re-import the collateral key into his wallet and spend the coins. The DNS network will soon observe that the coins are spent and make the name available for purchasing by somebody else.

=== Incentivising non-resource based chains ===

It's possible to incentivise mining on an alt-chain even if that chain does not have any concept of ownership, ie, if the act of finding a block itself is what is being paid for. An example of this is a timestamping chain in which presence in a block alone is sufficient to satisfy the user.

To implement this, set up a new chain as normal. Blocks in this new chain arrange transactions into a merkle tree in the same manner as Bitcoin does. A client that wants something incorporated into a block connects directly to some miners and submits their transaction. The miners add their address to the transaction as normal. Once a miner finds a block, it immediately sends the block to connected clients whose transactions made it in, but does not broadcast the new block to other miners. The clients respond with a valid Bitcoin transaction which pays for block inclusion. Once all clients have paid up the transaction is broadcast.

If a client has disconnected or does not pay quickly enough, their transaction can be replaced inside the block with its hash. In this way the blocks validity is preserved because the merkle tree is still valid. The newly found alt-block is broadcast, minus the transaction of the delinquent customer. As long as clients are still connected the payment process for all found transactions can be completed quickly: it would only take a few seconds to gather the payments and broadcast those on the Bitcoin network, minimizing the chance of a race that would require you to trust the miner to reinclude your transactions in the next block despite having already been paid.

=== Mining on the alt-chain but not Bitcoin ===

So far we've considered a scheme in which all alt-chain miners simultaneously mine on Bitcoin. It's possible some people may wish to mine on your chain but not Bitcoin, perhaps because the cost of keeping up with the Bitcoin transaction rate has become too high for them to bother.

To mine without an attached Bitcoin node, your software can simply implement the same getwork protocol Bitcoin itself does. When a mining tool requests work your program would generate a correctly formatted but ultimately bogus Bitcoin block. The contents of this block don't need to be correct because it will never be broadcast on the Bitcoin network, for example, the prevBlockHash field can be all zeros. It exists purely for backwards compatibility. Whilst the block needs a valid merkle root and a coinbase transaction, no other transactions are required and the only part of the coinbase tx that matters is the part holding the hash.

=== Scaling up ===

In the simple scheme each alt-chain being worked on needs 33 bytes in the Bitcoin coinbase transaction (1 for the length and 32 for the hash). Note that if there are two independent miners working on two different alt-chains, you still only need 1 hash in the coinbase scriptSig because the hash isn't meaningful to anyone else on the Bitcoin network. If miners only want to work a handful of chains this overhead is trivially dwarfed by the rest of the data in a Bitcoin block.

But if a miner wishes to work on hundreds, thousands or millions of alternative chains the size of the coinbase scriptSig would balloon and become unworkable. To solve this, the hash stored in the scriptSig can be the root of yet another merkle tree, this time a tree over the hashes of all blocks being worked on. The BitcoinData message is extended like this:

message MyBlock {
required bytes prev_block_hash = 1;
required uint32 difficulty = 2;
required uint32 time = 3;

repeated MyTx transactions = 4;
}

message SuperBlock {
required MyBlock my_data = 1;
required BitcoinData bitcoin_data = 2;
}

message BitcoinData {
// A Bitcoin format block header. Because it's in Satoshis custom format we represent this as a byte array.
required bytes header = 1;

// The first transaction from the block.
required bytes coinbase_tx = 2;

// The merkle branch linking the coinbase transaction to the header.
required bytes coinbase_merkle_branch = 3;

// The merkle branch linking MyBlock to the merkle root in the coinbase_tx.
required bytes altblock_merkle_branch = 4;
}

The verification step becomes a bit more complex:

# Verify the header is of sufficient difficulty for the alt-chain
# Verify coinbase_tx was a part of that block by checking the coinbase_merkle_branch is linked to the merkle root in the header.
# Extract the root of the second merkle tree from the coinbase_tx (call it 2MR).
# Hash the alt-chain block (my_data), verify that altblock_merkle_branch links the my_data hash to 2MR.

You have now proven that the MyBlock instance was worked on, along with perhaps thousands of other chains you don't have to know anything about.

This is an advanced technique which is probably not worth implementing unless the additional scalability is required. It can be introduced in a backwards compatible manner for new chains without impacting older networks.

=== Generalized proof of work ===

Hashes embedded in transactions, merkle branches, and [[Nonce|nonces]] all contribute to the goal of [[Proof of work|proving work]] on a block header. One can express all three as sequences of these basic operations:

* prepend a byte string to the current data
* append a byte string to the current data
* hash the current data

For maximum flexibility, a work-sharing chain's block acceptance algorithm might accept proof in the form of a script using just these operations. The script would receive as input an alternative chain block, and the hash of its output would have to match the chain's difficulty.

This design would even support plain Bitcoin proof of work, where the "header" consists of all [[Protocol Specification#block|Bitcoin block header fields]] except the nonce, and the proof-of-work script would simply append the nonce. Thus, one can think of the work-sharing rules as an extension of the original Bitcoin rules.

[[Category:Technical]]

Bitcoin Days Destroyed

2011-06-29T14:43:29Z

JohnTobey253: Lowercase "Abe"

Bitcoin Days Destroyed is a measure of the transaction volume of Bitcoin. <ref>[http://forum.bitcoin.org/index.php?topic=6172.msg90789#msg90789 ByteCoin's Proposal to use Bitcoin Days Destroyed as a measure of transaction volume]</ref> A bounty for a script to compute the Bitcoin Days Destroyed by the transactions in a block has been awarded. <ref>[http://forum.bitcoin.org/index.php?topic=9300.0 Bounty Award to develop a script to compute the BitcoinDays Destroyed by the transactions in a block.]</ref> [[Abe]] is a [[block chain browser]] that computes this statistic in real time.

==Calculation==

===Example===

If someone has 100BTC that they received a week ago and they spend it then 700 bitcoin days have been destroyed. If they take those 100BTC and send them to several addresses and then spend them then although the total transaction volume could be arbitrarily large the number of bitcoindays destroyed is still 700.

==Graph of Bitcoin Days Destroyed==

Percentage of Bitcoin Days destroyed vs block number, as of June 17th 2011.
[[File:June-17th-days-destroyed.png]]

==References==
<references/>

[[Category:Economics]]

Abe

2011-06-29T14:42:22Z

JohnTobey253: Use special syntax for Wikipedia links.

[[File:penny-abe-160.png|thumb|160px|Abe]]

'''Abe''' is a free, open-source [[block chain browser]] released by [[User:JohnTobey253|John Tobey]] under the [[wikipedia:Affero General Public License|Affero General Public License]].

Written in [[wikipedia:Python (programming language)|Python]] and portable [[wikipedia:SQL|SQL]],<ref>https://forum.bitcoin.org/index.php?topic=16141.0</ref> Abe draws inspiration from [[Bitcoin Block Explorer]] and seeks some level of compatibility with it but uses a completely new implementation.<ref>https://raw.github.com/jtobey/bitcoin-abe/master/README.txt</ref>

==See Also==

* [[Block chain browser]]

== External Links ==

* [http://john-edwin-tobey.org:2750/ Demonstration site]
* [https://forum.bitcoin.org/index.php?topic=16141.0 Project announcement]
* [https://github.com/jtobey/bitcoin-abe Project on Github]

==References==
<references />

[[Category:Block chain browsers]]
[[Category:Free Software]]
[[Category:Open Source]]

Abe

2011-06-28T16:12:58Z

JohnTobey253: Renamed "ABE" to "Abe", added a redirect.

[[File:penny-abe-160.png|thumb|160px|Abe]]

'''Abe''' is a free, open-source [[block chain browser]] released by [[User:JohnTobey253|John Tobey]] under the [http://en.wikipedia.org/wiki/Affero_General_Public_License Affero General Public License].

Written in [http://en.wikipedia.org/wiki/Python_%28programming_language%29 Python] and portable [http://en.wikipedia.org/wiki/SQL SQL],<ref>https://forum.bitcoin.org/index.php?topic=16141.0</ref> Abe draws inspiration from [[Bitcoin Block Explorer]] and seeks some level of compatibility with it but uses a completely new implementation.<ref>https://raw.github.com/jtobey/bitcoin-abe/master/README.txt</ref>

==See Also==

* [[Block chain browser]]

== External Links ==

* [http://john-edwin-tobey.org:2750/ Demonstration site]
* [https://forum.bitcoin.org/index.php?topic=16141.0 Project announcement]
* [https://github.com/jtobey/bitcoin-abe Project on Github]

==References==
<references />

[[Category:Block chain browsers]]
[[Category:Free Software]]
[[Category:Open Source]]

ABE

2011-06-28T16:12:26Z

JohnTobey253: Renamed "ABE" to "Abe", added a redirect.

#REDIRECT[[Abe]]

Block chain browser

2011-06-26T20:44:51Z

JohnTobey253: Replace individual links with category link.

A '''block chain browser''' such as [[Bitcoin Block Explorer]] [http://blockexplorer.com/] is a program or web site that lets users search and navigate a [[block chain]]. Uses include:

* checking [[address]] balances
* tracking coin transfer histories
* watching for [[transaction]] acceptance
* monitoring the [[Difficulty|network hash rate]] and other statistics

Block chain browsers typically offer:

* a list of a chain's recent [[blocks]] [http://blockexplorer.com/]
* transactions in a given block [http://blockexplorer.com/b/133310]
* links to the previous and next transaction involving each input and output [http://blockexplorer.com/t/2oajkZh1uz]
* a list of all transactions involving a given address [http://blockexplorer.com/a/7Djn6doKaa]
* current and historical address balances
* a way to search for blocks, transactions, and addresses

==See Also==

* [[:Category:Block chain browsers]]

Namecoin block explorer

2011-06-26T20:44:17Z

JohnTobey253: Very basic info.

The '''Namecoin block explorer''' [http://explorer.dot-bit.org/] is an online [[block chain browser]] for [[Namecoin]].

In addition to block, transaction, and address details, the Namecoin block explorer displays name operations and the effect of network fees on the number of coins outstanding.

[[Category:Block chain browsers]]

ABE

2011-06-26T18:19:20Z

JohnTobey253: Show URL in references section.

[[File:penny-abe-160.png|thumb|160px|ABE]]

'''ABE''' is a free, open-source [[block chain browser]] released by [[User:JohnTobey253|John Tobey]] under the [http://en.wikipedia.org/wiki/Affero_General_Public_License Affero General Public License].

Written in [http://en.wikipedia.org/wiki/Python_%28programming_language%29 Python] and portable [http://en.wikipedia.org/wiki/SQL SQL],<ref>https://forum.bitcoin.org/index.php?topic=16141.0</ref> ABE draws inspiration from [[Bitcoin Block Explorer]] and seeks some level of compatibility with it but uses a completely new implementation.<ref>https://raw.github.com/jtobey/bitcoin-abe/master/README.txt</ref>

==See Also==

* [[Block chain browser]]

== External Links ==

* [http://john-edwin-tobey.org:2750/ Demonstration site]
* [https://forum.bitcoin.org/index.php?topic=16141.0 Project announcement]
* [https://github.com/jtobey/bitcoin-abe Project on Github]

==References==
<references />

[[Category:Block chain browsers]]
[[Category:Free Software]]
[[Category:Open Source]]

ABE

2011-06-26T14:51:29Z

JohnTobey253: Logo, more details

[[File:penny-abe-160.png|thumb|160px|ABE]]

'''ABE''' is a free, open-source [[block chain browser]] released by [[User:JohnTobey253|John Tobey]] under the [http://en.wikipedia.org/wiki/Affero_General_Public_License Affero General Public License].

Written in [http://en.wikipedia.org/wiki/Python_%28programming_language%29 Python] and portable [http://en.wikipedia.org/wiki/SQL SQL],<ref>[https://forum.bitcoin.org/index.php?topic=16141.0]</ref> ABE draws inspiration from [[Bitcoin Block Explorer]] and seeks some level of compatibility with it but uses a completely new implementation.<ref>https://raw.github.com/jtobey/bitcoin-abe/master/README.txt</ref>

==See Also==

* [[Block chain browser]]

== External Links ==

* [http://john-edwin-tobey.org:2750/ Demonstration site]
* [https://forum.bitcoin.org/index.php?topic=16141.0 Project announcement]
* [https://github.com/jtobey/bitcoin-abe Project on Github]

==References==
<references />

[[Category:Block chain browsers]]
[[Category:Free Software]]
[[Category:Open Source]]

File:Penny-abe-160.png

2011-06-26T14:39:52Z

JohnTobey253: ABE logo, 160x160 PNG

== Summary ==
ABE logo, 160x160 PNG
== Licensing ==
{{self|GFDL|cc-by-sa-all|migration=redundant}}