Bitcoin Wiki - User contributions [en]

Talk:Thin Client Security

2015-02-28T06:14:52Z

Eldentyrell:

Lapp0, please stop deleting my content, which has been on this wiki page for over three years now. If you think it's suddenly no longer true, discuss here first. In particular, you wrote:

Transactions don't become more valid with more block preceding it's proof.

Chains become more trustworthy as they become (difficultywise-)longer. This is the most basic principle of blockchain consensus.

I have to keep putting that "(difficultywise-)" in there so pedantic people don't pounce on me... a 100,000-block chain all at difficulty=1 is "difficultywise-shorter" than a 100-block chain at current difficulty levels (or a one-block chain for that matter). It's not the number of blocks, but their total difficulty.

You also wrote:

The vagueness of what Full-chain is should be elaborated on probably explaining it uses SPV proofs

No, full-chain clients such as the Satoshi client do not use SPV in any way, shape, or form. A full-chain client is a client that implements the main algorithm outlined in Satoshi's whitepaper.

[[User:Eldentyrell|Eldentyrell]] ([[User talk:Eldentyrell|talk]]) 03:05, 26 February 2015 (UTC)

This page looks very confused/wrong in many respects. I'm not sure how it can be fixed easily, since it is unclear what exactly it intends to say.
* Generally "thin clients" do not include pruned full nodes, which have processed every block, but afterward discarded (and no longer store) them.
* Even thin clients generally verify block heights as well as depth.
* Thin clients never (neither for height nor depth) check blocks are valid ("well-formed"?). This is the fundamental difference between full nodes vs thin clients.
* Transaction validity is independent of its inclusion in any blockchain.
--[[User:Luke-jr|Luke-jr]] ([[User talk:Luke-jr|talk]]) 07:58, 26 February 2015 (UTC)

Luke, thanks for your thoughts. Regarding your points,

* Good point, I have partitioned "full-chain" into two separate subtypes (those which do and those which don't retain blocks after validating)
* SPV clients do not verify block height. I can take the existing 345308-block bitcoin blockchain, append a single block that re-spends coins I sent two years ago, and use that 345309-block chain to fool an SPV client. By wasting hashpower whose market value is as most one block reward I can fool an SPV client with it, since it will appear to be the difficultywise-longest chain by one block. I cannot fool the Satoshi client this way even with the hashpower of the entire network at my disposal.
* True. I think you may have hastily misread "transaction validity" as "block validity".
* True. I think you may have hastily misread "transaction validity" as "block validity".

Thanks again!

[[User:Eldentyrell|Eldentyrell]] ([[User talk:Eldentyrell|talk]]) 23:14, 26 February 2015 (UTC)

* Since this article deals with security, I do not think the distinction between pruned vs non-pruned is relevant - both nodes have equal security implications.
* SPV nodes are aware that your invalid 345309th block has a height higher than any other chain, and thus verify the block height before considering that chain "best". They do not, as you mention, validate the contents of any of those blocks, and can be fooled this way, but that is unrelated to the block's height.
* I was referring to the statement that "the validity of a transaction is determined by its height", which is simply not true. A transaction is valid before and even if it is never mined.
--[[User:Luke-jr|Luke-jr]] ([[User talk:Luke-jr|talk]]) 01:42, 27 February 2015 (UTC)

* Ok
* Ah, now I see why we disagree: I don't consider the last block of an ill-formed chain of 345309 blocks to be "of height 345309".

Is there a term other than "height X" you would recommend in order to describe the property of being the Xth block of a completely well-formed blockchain that obeys all the block validation rules (particularly no double-spends)? This is the property that SPV clients are not able to check. If there is a better name for this property I'll rewrite that section to use it.

I think the other issue here is my use of the term "valid transaction". I've been using that to describe a transaction that has been accepted by the network and that clients can safely assume is irreversible. I guess that term is sort of ambiguous; I can see how it could also be used to describe mempool transactions that aren't yet part of any block but could legitimately be included in the next one. What is the generally-accepted adjective for in-the-chain-and-safe-to-assume-is-totally-irreversible? I've substituted "accepted transaction" in the article where that was the intended meaning, but if there's a more widely-used phrase let me know. I also made a second edit to separate out "acceptance" from "degree of irreversibility" since "degree of irreversibility" is always measured the same way by all kinds of clients (number of confirmations, i.e. depth).

[[User:Eldentyrell|Eldentyrell]] ([[User talk:Eldentyrell|talk]]) 06:02, 28 February 2015 (UTC)

Full-chain is not well defined and isn't common terminology. If you are saying the Satoshi client is full-chain, then you probably mean full node. "full network node" or "full node" is common terminology and is used in the original Bitcoin whitepaper.

Your definition of transaction validity isn't common and is even incompatible with the Bitcoin whitepaper.

You added "A full-chain client trusts the [[Protocol_rules#Blocks well-formed|difficultywise-longest]] block chain it can find." which is only true for SPV clients, so you can see why I would be confused as to what this poorly defined "full-chain" client does.

I don't think the bitcoin wiki is an appropriate place to redefine terminology.

Finally, I am not deleting your content, I am deleting the wikis content because it is wrong. Please stop blindly reverting my edits, you removing spelling corrections indicates that you don't care about the accuracy of the wiki as much as maximizing the amount of text written by you on the wiki.
--[[User:Lapp0|Lapp0]] ([[User talk:Lapp0|talk]])

== Major Restructuring ==

This page was riddled with incorrect uses of words and the creation of new terminology. This leaves the reader confused or mislead. I have restructured this page and attempted to remove most of the inaccurate parts. It's not that I "think it's suddenly no longer true", I know that it hasn't been true for three years and no one has caught it until now.

--[[User:Lapp0|Lapp0]] ([[User talk:Lapp0|talk]])

Talk:Thin Client Security

2015-02-28T06:08:40Z

Eldentyrell:

Lapp0, please stop deleting my content, which has been on this wiki page for over three years now. If you think it's suddenly no longer true, discuss here first. In particular, you wrote:

Transactions don't become more valid with more block preceding it's proof.

Chains become more trustworthy as they become (difficultywise-)longer. This is the most basic principle of blockchain consensus.

I have to keep putting that "(difficultywise-)" in there so pedantic people don't pounce on me... a 100,000-block chain all at difficulty=1 is "difficultywise-shorter" than a 100-block chain at current difficulty levels (or a one-block chain for that matter). It's not the number of blocks, but their total difficulty.

You also wrote:

The vagueness of what Full-chain is should be elaborated on probably explaining it uses SPV proofs

No, full-chain clients such as the Satoshi client do not use SPV in any way, shape, or form. A full-chain client is a client that implements the main algorithm outlined in Satoshi's whitepaper.

[[User:Eldentyrell|Eldentyrell]] ([[User talk:Eldentyrell|talk]]) 03:05, 26 February 2015 (UTC)

This page looks very confused/wrong in many respects. I'm not sure how it can be fixed easily, since it is unclear what exactly it intends to say.
* Generally "thin clients" do not include pruned full nodes, which have processed every block, but afterward discarded (and no longer store) them.
* Even thin clients generally verify block heights as well as depth.
* Thin clients never (neither for height nor depth) check blocks are valid ("well-formed"?). This is the fundamental difference between full nodes vs thin clients.
* Transaction validity is independent of its inclusion in any blockchain.
--[[User:Luke-jr|Luke-jr]] ([[User talk:Luke-jr|talk]]) 07:58, 26 February 2015 (UTC)

Luke, thanks for your thoughts. Regarding your points,

* Good point, I have partitioned "full-chain" into two separate subtypes (those which do and those which don't retain blocks after validating)
* SPV clients do not verify block height. I can take the existing 345308-block bitcoin blockchain, append a single block that re-spends coins I sent two years ago, and use that 345309-block chain to fool an SPV client. By wasting hashpower whose market value is as most one block reward I can fool an SPV client with it, since it will appear to be the difficultywise-longest chain by one block. I cannot fool the Satoshi client this way even with the hashpower of the entire network at my disposal.
* True. I think you may have hastily misread "transaction validity" as "block validity".
* True. I think you may have hastily misread "transaction validity" as "block validity".

Thanks again!

[[User:Eldentyrell|Eldentyrell]] ([[User talk:Eldentyrell|talk]]) 23:14, 26 February 2015 (UTC)

* Since this article deals with security, I do not think the distinction between pruned vs non-pruned is relevant - both nodes have equal security implications.
* SPV nodes are aware that your invalid 345309th block has a height higher than any other chain, and thus verify the block height before considering that chain "best". They do not, as you mention, validate the contents of any of those blocks, and can be fooled this way, but that is unrelated to the block's height.
* I was referring to the statement that "the validity of a transaction is determined by its height", which is simply not true. A transaction is valid before and even if it is never mined.
--[[User:Luke-jr|Luke-jr]] ([[User talk:Luke-jr|talk]]) 01:42, 27 February 2015 (UTC)

* Ok
* Ah, now I see why we disagree: I don't consider the last block of an ill-formed chain of 345309 blocks to be "of height 345309".

Is there a term other than "height X" you would recommend in order to describe the property of being the Xth block of a completely well-formed blockchain that obeys all the block validation rules (particularly no double-spends)? This is the property that SPV clients are not able to check. If there is a better name for this property I'll rewrite that section to use it.

I think the other issue here is my use of the term "valid transaction". I've been using that to describe a transaction that has been accepted by the network and that clients can safely assume is irreversible. I guess that term is sort of ambiguous; I can see how it could also be used to describe mempool transactions that aren't yet part of any block but could legitimately be included in the next one. What is the generally-accepted adjective for in-the-chain-and-safe-to-assume-is-totally-irreversible? I've substituted "irreversible transaction" in the article where that was the intended meaning, but if there's a more widely-used phrase let me know.

[[User:Eldentyrell|Eldentyrell]] ([[User talk:Eldentyrell|talk]]) 06:02, 28 February 2015 (UTC)

Full-chain is not well defined and isn't common terminology. If you are saying the Satoshi client is full-chain, then you probably mean full node. "full network node" or "full node" is common terminology and is used in the original Bitcoin whitepaper.

Your definition of transaction validity isn't common and is even incompatible with the Bitcoin whitepaper.

You added "A full-chain client trusts the [[Protocol_rules#Blocks well-formed|difficultywise-longest]] block chain it can find." which is only true for SPV clients, so you can see why I would be confused as to what this poorly defined "full-chain" client does.

I don't think the bitcoin wiki is an appropriate place to redefine terminology.

Finally, I am not deleting your content, I am deleting the wikis content because it is wrong. Please stop blindly reverting my edits, you removing spelling corrections indicates that you don't care about the accuracy of the wiki as much as maximizing the amount of text written by you on the wiki.
--[[User:Lapp0|Lapp0]] ([[User talk:Lapp0|talk]])

== Major Restructuring ==

This page was riddled with incorrect uses of words and the creation of new terminology. This leaves the reader confused or mislead. I have restructured this page and attempted to remove most of the inaccurate parts. It's not that I "think it's suddenly no longer true", I know that it hasn't been true for three years and no one has caught it until now.

--[[User:Lapp0|Lapp0]] ([[User talk:Lapp0|talk]])

Thin Client Security

2015-02-28T06:08:10Z

Eldentyrell: Refine distinction between "acceptance" and "irreversibility"

Recently there have been a number of proposals for bitcoin clients which do not store a complete copy of every block in the entire block chain. This page will refer to all such clients as "thin clients". This page is meant to be a place to try to make sense of the security and trust implications of the various schemes.

== Block Height vs. Depth ==

It is important to distinguish between block height verification and block depth verification.

A client verifies the height H of a block by checking that there are H block '''before''' it, all of which are well-formed and obey the maximum-difficulty-adjustment-rate rule. Currently only the Satoshi client, libbitcoin, and btcd do block height verification. Block height is the fundamental anchor of trustless security in the Bitcoin system.

A client verifies the depth D of a block by checking that there are D blocks '''after''' it (also called "confirmations"), all of which are well-formed. SPV clients substitute block depth for block height as a transaction acceptance check. All clients use block depth as a measure of the liklihood of a [[Chain_Reorganization|block chain reorganization]] producing a new longer fork which excludes the transaction.

See also [https://bitcointalk.org/index.php?topic=88208.msg987429#msg987429 some comments on probabilistic verification of block height].

== Full-Chain Clients ==

The "thick" bitcoin client downloads a copy of the entire chain, including all transactions (not just headers). It will be used as the reference point for security comparisons below.

=== Block '''Height''' as a Transaction Acceptance Check ===

A full-chain client trusts the [[Protocol_rules#Blocks well-formed|difficultywise-longest]] block chain it can find. Any transaction on the difficultywise-longest well-formed chain is considered to have been accepted by the network. Therefore, the acceptance of a transaction is determined by its height -- i.e. how many blocks come ''before'' it.

A transaction's ''depth'' (the number of blocks ''after'' it) is used to determine ''irreversibility'' -- the likelihood of the transaction being undone due to the emergence of a longer fork.

==== [[bitcoind|bitcoin-qt]] ====

==== [https://github.com/conformal/btcd btcd] ====

=== Block Retention ===

Once a full-chain client has downloaded the entire chain, it typically retains it (as the Satoshi client did/does).

Satoshi's original paper mentions the possibility of pruning individual transactions from the Merkle tree, which allows for pruned full-chain nodes, which verify the entire transaction history but do not retain it.

== Header-Only Clients ==

These client downloads a complete copy of the headers for all blocks in the entire block chain. This means that the download and storage requirements scale linearly with the amount of time since bitcoin was invented; it would be preferable to have the scaling be logarithmic or even constant.

=== Simplified Payment Verification (SPV) ===

This scheme is described in section 8 of the [http://bitcoin.org/bitcoin.pdf original bitcoin whitepaper].

==== Block '''Depth''' as a Transaction Acceptance Check ====

As Satoshi writes, "[the thin client] can't check the transaction for himself, but by linking it to a place in the chain, he can see that a network node has accepted it, and blocks added after it further confirm the network has accepted it." If we take "X" to be the "number of blocks added after it", then SPV essentially trusts that a transaction X blocks deep in the chain does not have inputs which were already spent further back in the chain. Therefore, the acceptance of a transaction is determined by its depth -- i.e. how many blocks come ''after'' it. Other thin client protocols also include this assumption.

This is very different from the trust model in the "thick" client: the thick client verifies that a transaction's inputs are unspent by actually checking the whole chain up to that point -- there is no "X blocks deep" involved here. The thick client uses "X blocks deep" (aka "confirmations") only ''after'' it has already decided that a transaction is accepted (i.e. no [[Double-spending|double-spends]]), as a gauge of ''irreversibility'' -- how likely it is that a longer fork in the chain will emerge which excludes that transaction.

It is very important to understand how the same property ("X blocks deep") is used to verify two different properties in the thick client and SPV cases. '''The thick client never uses block depth as a measure of transaction acceptance; the SPV client does'''.

This is a concern in a situation where an SPV client is subjected to a double-spend attack by somebody who controls its network connection. For example, suppose you are at a wi-fi cafe and are paying for something using your smartphone -- the cafe owner controls your network connection. Satoshi acknowledges this implicitly when he writes that "the verification is reliable as long as honest nodes control the network" -- to be completely pedantic, this means that the verification is reliable as long as honest nodes control '''the part of the network that the SPV client is able to communicate with'''. In an attack-by-ISP scenario this may not be a sufficiently strong security property. The attacker would not need to overpower "the rest of the network" because the client is unable to communicate with it.

==== [[BitCoinJ|bitcoinj]] ====

Simplified Payment Verification is the verification mechanism used in [[BitCoinJ|bitcoinj]].

A security analysis of some of the issues in bitcoinj can be found [http://code.google.com/p/bitcoinj/wiki/SecurityModel here]; however:

* The claim that "picking 10 nodes and requiring all of them to be consistent needs much less trust" overlooks the problem of [https://en.bitcoin.it/wiki/Weaknesses#Cancer_nodes "cancer nodes"] and [http://en.wikipedia.org/wiki/Sybil_attack Sybil attacks].
* Many of the security claims are qualified by some form of "if you don't think an attacker controls your internet connection"; see the previous section for a discussion of why this is problematic.

==== [https://bitcointalk.org/index.php?topic=128055.0 picocoin] ====

Simplified Payment Verification is the verification mechanism used in picocoin.

The library (libccoin) that picocoin is based on includes code for validating scripts and blocks; this could potentially be used to implement a full-chain client.

==== [[Electrum]] ====

Electrum fetches blockchain information from Electrum servers, bitcoin nodes that index the blockchain by address.
Electrum performs Simple Payment Verification to check the transactions returned by servers.
For this, it fetches blokchain headers from about 10 random servers.
In addition, Electrum servers are authenticated by SSL, in order to protect users from MITM attacks.

=== Unused Output Tree in the Block chain (UOT) ===

There have been several proposals (the first appears to be [https://bitcointalk.org/index.php?topic=21995.0 this one] by gmaxwell, who called it an "open transaction tree", although the term "open" is now taken to mean "not yet mined into the block chain" rather than "unspent") to form a tree of unused transaction outputs at each block in the chain, hash it as a Merkle tree, and encode the root hash in the block chain (probably as part of the coinbase input). This will be called an Unused Output Tree (UOT). The first detailed proposal so far appears to be [https://en.bitcoin.it/wiki/User:DiThi/MTUT Alberto Torres' proposal]; etotheipi's [https://bitcointalk.org/index.php?topic=88208.0 ultimate block chain compression] is a variant of this.

If such UOT hashes were included in the block chain, a client which shipped with a [https://en.bitcoin.it/wiki/Vocabulary checkpoint] block that had a UOT would only need to download blocks after the checkpoint. Moreover, once the client had downloaded those blocks and confirmed their UOTs, it could discard all but the most recent block containing a UOT.

This would also let a thin client reduce the question of "is this output unspent" to the question of "is this block super-well-formed" where "well-formed" means "well-formed according to the normal block chain rules and additionally has an Unused Output Tree which is accurate and truthful". This is still a long way from the low level of trust involved in the thick client, but it is a major improvement over all existing proposals.

It is unlikely that bitcoin would ever arrive at a state where every single block had a UOT, since this would require upgrading 100% of the miners on the network, or else convincing enough miners to reject blocks which do not contain a UOT. The latter strategy risks creating block chain forks, which can be expensive (in reward terms) to miners. Therefore, any UOT strategy would need to cope with the fact that not every block contains a UOT.

Hostile miners may insert blocks into the chain which have what claims to be a UOT, but which is actually invalid. It is unlikely that such blocks could be kept out of the chain because, again, this would require adding a new block well-formedness criterion, and miners implementing this new criterion would risk "mining on the wrong side" of a fork, which could cost them a lot of money. Therefore, any UOT strategy would need to cope with the fact that not every block containing a UOT entry can be trusted.

Note that at the present moment no standard format for such Unused Output Tree hashes has been agreed upon, nor do any of the blocks in the chain contain them. The [https://bitcointalk.org/index.php?topic=91954 ultraprune] feature added to bitcoind-0.8 maintains a similar data structure on the client's disk. It does not put this data structure or its hash anywhere in the block chain.

== Server-Trusting Clients ==

These clients involve some (usually low) level of trust in the server they rely upon. Mechanisms for authenticating the server, and for confirming that the server has not been compromised, are usually not explained.

All thin clients listed below currently connect to a single server, and are vulnerable to an attack similar to a double-spend. The attack can be run by that single server - the server can just lie to them that they received a Bitcoin transaction, and they, assuming the server does not lie, perform some service, transfer funds or send goods without actually receiving any Bitcoin in exchange. Therefore, they are implicitly trusting it.

Future enhancements have been suggested that will have the client talk to multiple servers and broadcast transactions and query all of them. Unfortunately it is well known to security researchers that this does not actually increase security; it simply makes the exploits more complicated and difficult to find. Security researchers have a name for this phenomenon: it is called a "Sybil attack"<ref>http://en.wikipedia.org/wiki/Sybil_attack</ref>. [https://bitcointalk.org/index.php?topic=88208.msg975201#msg975201 This post] on bitcointalk explains how some governments (notably Iran and China) already perform these sorts of attacks on their own citizens, with the coerced assistance of SSL certificate authorities.

Clients with a checkpoint (even a very old one) that download and validate the headers for the whole block chain are [http://bitcoinmedia.com/the-irc-bootstrap-method-is-flawed/#comment-4243 not vulnerable] to Sybil attacks in the following sense: they can always ensure that an attack would cost more than the amount being stolen.

=== [[BCCAPI]] ===

== Other ==

* A [http://sourceforge.net/mailarchive/message.php?msg_id=28633866 thread] on bitcoin-dev
* A [http://bitcoin.stackexchange.com/questions/2584/is-reclaiming-disk-space-already-implemented-how-effective-will-it-be/2589 question] on bitcoin.stackexchange.com
* The [[Weaknesses#Sybil_attack|sybil attack (also known as "cancer nodes")]] paragraph explains some of the issues with thin clients that base security on trusting whatever "a majority of the IP addresses I can see" say.
* [http://bitcoin.stackexchange.com/questions/2613/how-secure-are-various-models-of-bitcoin-clients related discussion on Stack Exchange]
* A hypothesized [https://bitcointalk.org/index.php?topic=134318.msg1441171#msg1441171 intermediate security class] between SPV and full-chain validation.

<references>

[[Category:Technical]]
[[category:Clients]]
[[Category:Security]]

Thin Client Security

2015-02-28T06:03:05Z

Eldentyrell: Replace "valid" with "irreversible" where appropriate (see talk)

Recently there have been a number of proposals for bitcoin clients which do not store a complete copy of every block in the entire block chain. This page will refer to all such clients as "thin clients". This page is meant to be a place to try to make sense of the security and trust implications of the various schemes.

== Block Height vs. Depth ==

It is important to distinguish between block height verification and block depth verification.

A client verifies the height H of a block by checking that there are H block '''before''' it, all of which are well-formed and obey the maximum-difficulty-adjustment-rate rule. Currently only the Satoshi client, libbitcoin, and btcd do block height verification. Block height is the fundamental anchor of trustless security in the Bitcoin system.

A client verifies the depth D of a block by checking that there are D blocks '''after''' it (also called "confirmations"), all of which are well-formed. SPV clients substitute block depth for block height as a transaction irreversibility check. All clients use block depth as a measure of the liklihood of a [[Chain_Reorganization|block chain reorganization]] producing a new longer fork which excludes the transaction.

See also [https://bitcointalk.org/index.php?topic=88208.msg987429#msg987429 some comments on probabilistic verification of block height].

== Full-Chain Clients ==

The "thick" bitcoin client downloads a copy of the entire chain, including all transactions (not just headers). It will be used as the reference point for security comparisons below.

=== Block '''Height''' as a Transaction Irreversibility Check ===

A full-chain client trusts the [[Protocol_rules#Blocks well-formed|difficultywise-longest]] block chain it can find. Any transaction on the difficultywise-longest well-formed chain is considered irreversible. Therefore, the irreversibility of a transaction is determined by its height -- i.e. how many blocks come ''before'' it. A transaction's ''depth'' (the number of blocks ''after'' it) is used to determine the likelihood of the transaction being undone due to the emergence of a longer fork.

==== [[bitcoind|bitcoin-qt]] ====

==== [https://github.com/conformal/btcd btcd] ====

=== Block Retention ===

Once a full-chain client has downloaded the entire chain, it typically retains it (as the Satoshi client did/does).

Satoshi's original paper mentions the possibility of pruning individual transactions from the Merkle tree, which allows for pruned full-chain nodes, which verify the entire transaction history but do not retain it.

== Header-Only Clients ==

These client downloads a complete copy of the headers for all blocks in the entire block chain. This means that the download and storage requirements scale linearly with the amount of time since bitcoin was invented; it would be preferable to have the scaling be logarithmic or even constant.

=== Simplified Payment Verification (SPV) ===

This scheme is described in section 8 of the [http://bitcoin.org/bitcoin.pdf original bitcoin whitepaper].

==== Block '''Depth''' as a Transaction Irreversibility Check ====

As Satoshi writes, "[the thin client] can't check the transaction for himself, but by linking it to a place in the chain, he can see that a network node has accepted it, and blocks added after it further confirm the network has accepted it." If we take "X" to be the "number of blocks added after it", then SPV essentially trusts that a transaction X blocks deep in the chain does not have inputs which were already spent further back in the chain. Therefore, the irreversibility of a transaction is determined by its depth -- i.e. how many blocks come ''after'' it. Other thin client protocols also include this assumption.

This is very different from the trust model in the "thick" client: the thick client verifies that a transaction's inputs are unspent by actually checking the whole chain up to that point -- there is no "X blocks deep" involved here. The thick client uses "X blocks deep" (aka "confirmations") only once it has already decided that a transaction is irreversible (i.e. no [[Double-spending|double-spends]]). At that point it uses "X blocks deep" to decide how likely it is that a longer fork in the chain will emerge which excludes that transaction.

It is very important to understand how the same property ("X blocks deep") is used to verify two different properties in the thick client and SPV cases. '''The thick client never uses block depth as a measure of transaction irreversibility; the SPV client does'''.

This is a concern in a situation where an SPV client is subjected to a double-spend attack by somebody who controls its network connection. For example, suppose you are at a wi-fi cafe and are paying for something using your smartphone -- the cafe owner controls your network connection. Satoshi acknowledges this implicitly when he writes that "the verification is reliable as long as honest nodes control the network" -- to be completely pedantic, this means that the verification is reliable as long as honest nodes control '''the part of the network that the SPV client is able to communicate with'''. In an attack-by-ISP scenario this may not be a sufficiently strong security property. The attacker would not need to overpower "the rest of the network" because the client is unable to communicate with it.

==== [[BitCoinJ|bitcoinj]] ====

Simplified Payment Verification is the verification mechanism used in [[BitCoinJ|bitcoinj]].

A security analysis of some of the issues in bitcoinj can be found [http://code.google.com/p/bitcoinj/wiki/SecurityModel here]; however:

* The claim that "picking 10 nodes and requiring all of them to be consistent needs much less trust" overlooks the problem of [https://en.bitcoin.it/wiki/Weaknesses#Cancer_nodes "cancer nodes"] and [http://en.wikipedia.org/wiki/Sybil_attack Sybil attacks].
* Many of the security claims are qualified by some form of "if you don't think an attacker controls your internet connection"; see the previous section for a discussion of why this is problematic.

==== [https://bitcointalk.org/index.php?topic=128055.0 picocoin] ====

Simplified Payment Verification is the verification mechanism used in picocoin.

The library (libccoin) that picocoin is based on includes code for validating scripts and blocks; this could potentially be used to implement a full-chain client.

==== [[Electrum]] ====

Electrum fetches blockchain information from Electrum servers, bitcoin nodes that index the blockchain by address.
Electrum performs Simple Payment Verification to check the transactions returned by servers.
For this, it fetches blokchain headers from about 10 random servers.
In addition, Electrum servers are authenticated by SSL, in order to protect users from MITM attacks.

=== Unused Output Tree in the Block chain (UOT) ===

There have been several proposals (the first appears to be [https://bitcointalk.org/index.php?topic=21995.0 this one] by gmaxwell, who called it an "open transaction tree", although the term "open" is now taken to mean "not yet mined into the block chain" rather than "unspent") to form a tree of unused transaction outputs at each block in the chain, hash it as a Merkle tree, and encode the root hash in the block chain (probably as part of the coinbase input). This will be called an Unused Output Tree (UOT). The first detailed proposal so far appears to be [https://en.bitcoin.it/wiki/User:DiThi/MTUT Alberto Torres' proposal]; etotheipi's [https://bitcointalk.org/index.php?topic=88208.0 ultimate block chain compression] is a variant of this.

If such UOT hashes were included in the block chain, a client which shipped with a [https://en.bitcoin.it/wiki/Vocabulary checkpoint] block that had a UOT would only need to download blocks after the checkpoint. Moreover, once the client had downloaded those blocks and confirmed their UOTs, it could discard all but the most recent block containing a UOT.

This would also let a thin client reduce the question of "is this output unspent" to the question of "is this block super-well-formed" where "well-formed" means "well-formed according to the normal block chain rules and additionally has an Unused Output Tree which is accurate and truthful". This is still a long way from the low level of trust involved in the thick client, but it is a major improvement over all existing proposals.

It is unlikely that bitcoin would ever arrive at a state where every single block had a UOT, since this would require upgrading 100% of the miners on the network, or else convincing enough miners to reject blocks which do not contain a UOT. The latter strategy risks creating block chain forks, which can be expensive (in reward terms) to miners. Therefore, any UOT strategy would need to cope with the fact that not every block contains a UOT.

Hostile miners may insert blocks into the chain which have what claims to be a UOT, but which is actually invalid. It is unlikely that such blocks could be kept out of the chain because, again, this would require adding a new block well-formedness criterion, and miners implementing this new criterion would risk "mining on the wrong side" of a fork, which could cost them a lot of money. Therefore, any UOT strategy would need to cope with the fact that not every block containing a UOT entry can be trusted.

Note that at the present moment no standard format for such Unused Output Tree hashes has been agreed upon, nor do any of the blocks in the chain contain them. The [https://bitcointalk.org/index.php?topic=91954 ultraprune] feature added to bitcoind-0.8 maintains a similar data structure on the client's disk. It does not put this data structure or its hash anywhere in the block chain.

== Server-Trusting Clients ==

These clients involve some (usually low) level of trust in the server they rely upon. Mechanisms for authenticating the server, and for confirming that the server has not been compromised, are usually not explained.

All thin clients listed below currently connect to a single server, and are vulnerable to an attack similar to a double-spend. The attack can be run by that single server - the server can just lie to them that they received a Bitcoin transaction, and they, assuming the server does not lie, perform some service, transfer funds or send goods without actually receiving any Bitcoin in exchange. Therefore, they are implicitly trusting it.

Future enhancements have been suggested that will have the client talk to multiple servers and broadcast transactions and query all of them. Unfortunately it is well known to security researchers that this does not actually increase security; it simply makes the exploits more complicated and difficult to find. Security researchers have a name for this phenomenon: it is called a "Sybil attack"<ref>http://en.wikipedia.org/wiki/Sybil_attack</ref>. [https://bitcointalk.org/index.php?topic=88208.msg975201#msg975201 This post] on bitcointalk explains how some governments (notably Iran and China) already perform these sorts of attacks on their own citizens, with the coerced assistance of SSL certificate authorities.

Clients with a checkpoint (even a very old one) that download and validate the headers for the whole block chain are [http://bitcoinmedia.com/the-irc-bootstrap-method-is-flawed/#comment-4243 not vulnerable] to Sybil attacks in the following sense: they can always ensure that an attack would cost more than the amount being stolen.

=== [[BCCAPI]] ===

== Other ==

* A [http://sourceforge.net/mailarchive/message.php?msg_id=28633866 thread] on bitcoin-dev
* A [http://bitcoin.stackexchange.com/questions/2584/is-reclaiming-disk-space-already-implemented-how-effective-will-it-be/2589 question] on bitcoin.stackexchange.com
* The [[Weaknesses#Sybil_attack|sybil attack (also known as "cancer nodes")]] paragraph explains some of the issues with thin clients that base security on trusting whatever "a majority of the IP addresses I can see" say.
* [http://bitcoin.stackexchange.com/questions/2613/how-secure-are-various-models-of-bitcoin-clients related discussion on Stack Exchange]
* A hypothesized [https://bitcointalk.org/index.php?topic=134318.msg1441171#msg1441171 intermediate security class] between SPV and full-chain validation.

<references>

[[Category:Technical]]
[[category:Clients]]
[[Category:Security]]

Talk:Thin Client Security

2015-02-28T06:02:53Z

Eldentyrell:

Lapp0, please stop deleting my content, which has been on this wiki page for over three years now. If you think it's suddenly no longer true, discuss here first. In particular, you wrote:

Transactions don't become more valid with more block preceding it's proof.

Chains become more trustworthy as they become (difficultywise-)longer. This is the most basic principle of blockchain consensus.

I have to keep putting that "(difficultywise-)" in there so pedantic people don't pounce on me... a 100,000-block chain all at difficulty=1 is "difficultywise-shorter" than a 100-block chain at current difficulty levels (or a one-block chain for that matter). It's not the number of blocks, but their total difficulty.

You also wrote:

The vagueness of what Full-chain is should be elaborated on probably explaining it uses SPV proofs

No, full-chain clients such as the Satoshi client do not use SPV in any way, shape, or form. A full-chain client is a client that implements the main algorithm outlined in Satoshi's whitepaper.

[[User:Eldentyrell|Eldentyrell]] ([[User talk:Eldentyrell|talk]]) 03:05, 26 February 2015 (UTC)

This page looks very confused/wrong in many respects. I'm not sure how it can be fixed easily, since it is unclear what exactly it intends to say.
* Generally "thin clients" do not include pruned full nodes, which have processed every block, but afterward discarded (and no longer store) them.
* Even thin clients generally verify block heights as well as depth.
* Thin clients never (neither for height nor depth) check blocks are valid ("well-formed"?). This is the fundamental difference between full nodes vs thin clients.
* Transaction validity is independent of its inclusion in any blockchain.
--[[User:Luke-jr|Luke-jr]] ([[User talk:Luke-jr|talk]]) 07:58, 26 February 2015 (UTC)

Luke, thanks for your thoughts. Regarding your points,

* Good point, I have partitioned "full-chain" into two separate subtypes (those which do and those which don't retain blocks after validating)
* SPV clients do not verify block height. I can take the existing 345308-block bitcoin blockchain, append a single block that re-spends coins I sent two years ago, and use that 345309-block chain to fool an SPV client. By wasting hashpower whose market value is as most one block reward I can fool an SPV client with it, since it will appear to be the difficultywise-longest chain by one block. I cannot fool the Satoshi client this way even with the hashpower of the entire network at my disposal.
* True. I think you may have hastily misread "transaction validity" as "block validity".
* True. I think you may have hastily misread "transaction validity" as "block validity".

Thanks again!

[[User:Eldentyrell|Eldentyrell]] ([[User talk:Eldentyrell|talk]]) 23:14, 26 February 2015 (UTC)

* Since this article deals with security, I do not think the distinction between pruned vs non-pruned is relevant - both nodes have equal security implications.
* SPV nodes are aware that your invalid 345309th block has a height higher than any other chain, and thus verify the block height before considering that chain "best". They do not, as you mention, validate the contents of any of those blocks, and can be fooled this way, but that is unrelated to the block's height.
* I was referring to the statement that "the validity of a transaction is determined by its height", which is simply not true. A transaction is valid before and even if it is never mined.
--[[User:Luke-jr|Luke-jr]] ([[User talk:Luke-jr|talk]]) 01:42, 27 February 2015 (UTC)

* Ok
* Ah, now I see why we disagree: I don't consider the last block of an ill-formed chain of 345309 blocks to be "of height 345309".

Is there a term other than "height X" you would recommend in order to describe the property of being the Xth block of a completely well-formed blockchain that obeys all the block validation rules (particularly no double-spends)? This is the property that SPV clients are not able to check. If there is a better name for this property I'll rewrite that section to use it.

I think the other issue here is my use of the term "valid transaction". I've been using that to describe a transaction that has been accepted by the network and that clients can safely assume is irreversible. I guess that term is sort of ambiguous; I can see how it could also be used to describe mempool transactions that aren't yet part of any block but could legitimately be included in the next one. What is the generally-accepted adjective for in-the-chain-and-safe-to-assume-is-totally-irreversible? I've substituted "irreversible transaction" in the article where that was the intended meaning, but if there's a more widely-used phrase let me know.

[[User:Eldentyrell|Eldentyrell]] ([[User talk:Eldentyrell|talk]]) 06:02, 28 February 2015 (UTC)

Full-chain is not well defined and isn't common terminology. If you are saying the Satoshi client is full-chain, then you probably mean full node. "full network node" or "full node" is common terminology and is used in the original Bitcoin whitepaper.

Your definition of transaction validity isn't common and is even incompatible with the Bitcoin whitepaper.

You added "A full-chain client trusts the [[Protocol_rules#Blocks well-formed|difficultywise-longest]] block chain it can find." which is only true for SPV clients, so you can see why I would be confused as to what this poorly defined "full-chain" client does.

I don't think the bitcoin wiki is an appropriate place to redefine terminology.

Finally, I am not deleting your content, I am deleting the wikis content because it is wrong. Please stop blindly reverting my edits, you removing spelling corrections indicates that you don't care about the accuracy of the wiki as much as maximizing the amount of text written by you on the wiki.
--[[User:Lapp0|Lapp0]] ([[User talk:Lapp0|talk]])

== Major Restructuring ==

This page was riddled with incorrect uses of words and the creation of new terminology. This leaves the reader confused or mislead. I have restructured this page and attempted to remove most of the inaccurate parts. It's not that I "think it's suddenly no longer true", I know that it hasn't been true for three years and no one has caught it until now.

--[[User:Lapp0|Lapp0]] ([[User talk:Lapp0|talk]])

Talk:Thin Client Security

2015-02-26T23:28:32Z

Eldentyrell:

Talk:Thin Client Security

2015-02-26T23:21:25Z

Eldentyrell:

Talk:Thin Client Security

2015-02-26T23:19:50Z

Eldentyrell:

Thin Client Security

2015-02-26T23:19:16Z

Eldentyrell: As per Luke-Jr: pruned full nodes have processed every block, but afterward discarded (and no longer store) them

Recently there have been a number of proposals for bitcoin clients which do not store a complete copy of every block in the entire block chain. This page will refer to all such clients as "thin clients". This page is meant to be a place to try to make sense of the security and trust implications of the various schemes.

== Block Height vs. Depth ==

It is important to distinguish between block height verification and block depth verification.

A client verifies the height H of a block by checking that there are H block '''before''' it, all of which are well-formed and obey the maximum-difficulty-adjustment-rate rule. Currently only the Satoshi client, libbitcoin, and btcd do block height verification. Block height is the fundamental anchor of trustless security in the Bitcoin system.

A client verifies the depth D of a block by checking that there are D blocks '''after''' it (also called "confirmations"), all of which are well-formed. SPV clients substitute block depth for block height as a transaction validity check. All clients use block depth as a measure of the liklihood of a [[Chain_Reorganization|block chain reorganization]] producing a new longer fork which excludes the transaction.

See also [https://bitcointalk.org/index.php?topic=88208.msg987429#msg987429 some comments on probabilistic verification of block height].

== Full-Chain Clients ==

The "thick" bitcoin client downloads a copy of the entire chain, including all transactions (not just headers). It will be used as the reference point for security comparisons below.

=== Block '''Height''' as a Transaction Validity Check ===

A full-chain client trusts the [[Protocol_rules#Blocks well-formed|difficultywise-longest]] block chain it can find. Any transaction on the difficultywise-longest well-formed chain is considered valid. Therefore, the validity of a transaction is determined by its height -- i.e. how many blocks come ''before'' it. A transaction's ''depth'' (the number of blocks ''after'' it) is used to determine the likelihood of the transaction being invalidated due to the emergence of a longer fork.

==== [[bitcoind|bitcoin-qt]] ====

==== [https://github.com/conformal/btcd btcd] ====

=== Block Retention ===

Once a full-chain client has downloaded the entire chain, it typically retains it (as the Satoshi client did/does).

Satoshi's original paper mentions the possibility of pruning individual transactions from the Merkle tree, which allows for pruned full-chain nodes, which verify the entire transaction history but do note retain it.

== Header-Only Clients ==

These client downloads a complete copy of the headers for all blocks in the entire block chain. This means that the download and storage requirements scale linearly with the amount of time since bitcoin was invented; it would be preferable to have the scaling be logarithmic or even constant.

=== Simplified Payment Verification (SPV) ===

This scheme is described in section 8 of the [http://bitcoin.org/bitcoin.pdf original bitcoin whitepaper].

==== Block '''Depth''' as a Transaction Validity Check ====

As Satoshi writes, "[the thin client] can't check the transaction for himself, but by linking it to a place in the chain, he can see that a network node has accepted it, and blocks added after it further confirm the network has accepted it." If we take "X" to be the "number of blocks added after it", then SPV essentially trusts that a transaction X blocks deep in the chain does not have inputs which were already spent further back in the chain. Therefore, the validity of a transaction is determined by its depth -- i.e. how many blocks come ''after'' it. Other thin client protocols also include this assumption.

This is very different from the trust model in the "thick" client: the thick client verifies that a transaction's inputs are unspent by actually checking the whole chain up to that point -- there is no "X blocks deep" involved here. The thick client uses "X blocks deep" (aka "confirmations") only once it has already decided that a transaction is valid (i.e. no [[Double-spending|double-spends]]). At that point it uses "X blocks deep" to decide how likely it is that a longer fork in the chain will emerge which excludes that transaction.

It is very important to understand how the same property ("X blocks deep") is used to verify two different properties in the thick client and SPV cases. '''The thick client never uses block depth as a measure of transaction validity; the SPV client does'''.

This is a concern in a situation where an SPV client is subjected to a double-spend attack by somebody who controls its network connection. For example, suppose you are at a wi-fi cafe and are paying for something using your smartphone -- the cafe owner controls your network connection. Satoshi acknowledges this implicitly when he writes that "the verification is reliable as long as honest nodes control the network" -- to be completely pedantic, this means that the verification is reliable as long as honest nodes control '''the part of the network that the SPV client is able to communicate with'''. In an attack-by-ISP scenario this may not be a sufficiently strong security property. The attacker would not need to overpower "the rest of the network" because the client is unable to communicate with it.

==== [[BitCoinJ|bitcoinj]] ====

Simplified Payment Verification is the verification mechanism used in [[BitCoinJ|bitcoinj]].

A security analysis of some of the issues in bitcoinj can be found [http://code.google.com/p/bitcoinj/wiki/SecurityModel here]; however:

* The claim that "picking 10 nodes and requiring all of them to be consistent needs much less trust" overlooks the problem of [https://en.bitcoin.it/wiki/Weaknesses#Cancer_nodes "cancer nodes"] and [http://en.wikipedia.org/wiki/Sybil_attack Sybil attacks].
* Many of the security claims are qualified by some form of "if you don't think an attacker controls your internet connection"; see the previous section for a discussion of why this is problematic.

==== [https://bitcointalk.org/index.php?topic=128055.0 picocoin] ====

Simplified Payment Verification is the verification mechanism used in picocoin.

The library (libccoin) that picocoin is based on includes code for validating scripts and blocks; this could potentially be used to implement a full-chain client.

==== [[Electrum]] ====

Electrum fetches blockchain information from Electrum servers, bitcoin nodes that index the blockchain by address.
Electrum performs Simple Payment Verification to check the transactions returned by servers.
For this, it fetches blokchain headers from about 10 random servers.
In addition, Electrum servers are authenticated by SSL, in order to protect users from MITM attacks.

=== Unused Output Tree in the Block chain (UOT) ===

There have been several proposals (the first appears to be [https://bitcointalk.org/index.php?topic=21995.0 this one] by gmaxwell, who called it an "open transaction tree", although the term "open" is now taken to mean "not yet mined into the block chain" rather than "unspent") to form a tree of unused transaction outputs at each block in the chain, hash it as a Merkle tree, and encode the root hash in the block chain (probably as part of the coinbase input). This will be called an Unused Output Tree (UOT). The first detailed proposal so far appears to be [https://en.bitcoin.it/wiki/User:DiThi/MTUT Alberto Torres' proposal]; etotheipi's [https://bitcointalk.org/index.php?topic=88208.0 ultimate block chain compression] is a variant of this.

If such UOT hashes were included in the block chain, a client which shipped with a [https://en.bitcoin.it/wiki/Vocabulary checkpoint] block that had a UOT would only need to download blocks after the checkpoint. Moreover, once the client had downloaded those blocks and confirmed their UOTs, it could discard all but the most recent block containing a UOT.

This would also let a thin client reduce the question of "is this output unspent" to the question of "is this block super-well-formed" where "well-formed" means "well-formed according to the normal block chain rules and additionally has an Unused Output Tree which is accurate and truthful". This is still a long way from the low level of trust involved in the thick client, but it is a major improvement over all existing proposals.

It is unlikely that bitcoin would ever arrive at a state where every single block had a UOT, since this would require upgrading 100% of the miners on the network, or else convincing enough miners to reject blocks which do not contain a UOT. The latter strategy risks creating block chain forks, which can be expensive (in reward terms) to miners. Therefore, any UOT strategy would need to cope with the fact that not every block contains a UOT.

Hostile miners may insert blocks into the chain which have what claims to be a UOT, but which is actually invalid. It is unlikely that such blocks could be kept out of the chain because, again, this would require adding a new block well-formedness criterion, and miners implementing this new criterion would risk "mining on the wrong side" of a fork, which could cost them a lot of money. Therefore, any UOT strategy would need to cope with the fact that not every block containing a UOT entry can be trusted.

Note that at the present moment no standard format for such Unused Output Tree hashes has been agreed upon, nor do any of the blocks in the chain contain them. The [https://bitcointalk.org/index.php?topic=91954 ultraprune] feature added to bitcoind-0.8 maintains a similar data structure on the client's disk. It does not put this data structure or its hash anywhere in the block chain.

== Server-Trusting Clients ==

These clients involve some (usually low) level of trust in the server they rely upon. Mechanisms for authenticating the server, and for confirming that the server has not been compromised, are usually not explained.

All thin clients listed below currently connect to a single server, and are vulnerable to an attack similar to a double-spend. The attack can be run by that single server - the server can just lie to them that they received a Bitcoin transaction, and they, assuming the server does not lie, perform some service, transfer funds or send goods without actually receiving any Bitcoin in exchange. Therefore, they are implicitly trusting it.

Future enhancements have been suggested that will have the client talk to multiple servers and broadcast transactions and query all of them. Unfortunately it is well known to security researchers that this does not actually increase security; it simply makes the exploits more complicated and difficult to find. Security researchers have a name for this phenomenon: it is called a "Sybil attack"<ref>http://en.wikipedia.org/wiki/Sybil_attack</ref>. [https://bitcointalk.org/index.php?topic=88208.msg975201#msg975201 This post] on bitcointalk explains how some governments (notably Iran and China) already perform these sorts of attacks on their own citizens, with the coerced assistance of SSL certificate authorities.

Clients with a checkpoint (even a very old one) that download and validate the headers for the whole block chain are [http://bitcoinmedia.com/the-irc-bootstrap-method-is-flawed/#comment-4243 not vulnerable] to Sybil attacks in the following sense: they can always ensure that an attack would cost more than the amount being stolen.

=== [[BCCAPI]] ===

== Other ==

* A [http://sourceforge.net/mailarchive/message.php?msg_id=28633866 thread] on bitcoin-dev
* A [http://bitcoin.stackexchange.com/questions/2584/is-reclaiming-disk-space-already-implemented-how-effective-will-it-be/2589 question] on bitcoin.stackexchange.com
* The [[Weaknesses#Sybil_attack|sybil attack (also known as "cancer nodes")]] paragraph explains some of the issues with thin clients that base security on trusting whatever "a majority of the IP addresses I can see" say.
* [http://bitcoin.stackexchange.com/questions/2613/how-secure-are-various-models-of-bitcoin-clients related discussion on Stack Exchange]
* A hypothesized [https://bitcointalk.org/index.php?topic=134318.msg1441171#msg1441171 intermediate security class] between SPV and full-chain validation.

<references>

[[Category:Technical]]
[[category:Clients]]
[[Category:Security]]

Talk:Thin Client Security

2015-02-26T23:14:08Z

Eldentyrell: response to Luke-Jr

Talk:Thin Client Security

2015-02-26T03:05:43Z

Eldentyrell:

Talk:Thin Client Security

2015-02-26T03:05:29Z

Eldentyrell: Created page with "Lapp0, please stop deleting my content, which has been on this wiki page for over three years now. If you think it's suddenly no longer true, discuss here first. In particul..."

Thin Client Security

2015-02-26T02:57:20Z

Eldentyrell: Undo revision 54610 by Lapp0 - (difficultywise-)longer chains are harder to forge and therefore more trusted... this is the most basic principle of blockchain consensus.

Recently there have been a number of proposals for bitcoin clients which do not store a complete copy of every block in the entire block chain. This page will refer to all such clients as "thin clients". This page is meant to be a place to try to make sense of the security and trust implications of the various schemes.

== Block Height vs. Depth ==

It is important to distinguish between block height verification and block depth verification.

A client verifies the height H of a block by checking that there are H block '''before''' it, all of which are well-formed and obey the maximum-difficulty-adjustment-rate rule. Currently only the Satoshi client, libbitcoin, and btcd do block height verification. Block height is the fundamental anchor of trustless security in the Bitcoin system.

A client verifies the depth D of a block by checking that there are D blocks '''after''' it (also called "confirmations"), all of which are well-formed. SPV clients substitute block depth for block height as a transaction validity check. All clients use block depth as a measure of the liklihood of a [[Chain_Reorganization|block chain reorganization]] producing a new longer fork which excludes the transaction (i.e. [[Orphan_Block|orphaning]] its block).

See also [https://bitcointalk.org/index.php?topic=88208.msg987429#msg987429 some comments on probabilistic verification of block height].

== Full-Chain Clients ==

The "thick" bitcoin client downloads a copy of the entire chain, including all transactions (not just headers). It will be used as the reference point for security comparisons below.

=== Block '''Height''' as a Transaction Validity Check ===

A full-chain client trusts the [[Protocol_rules#Blocks well-formed|difficultywise-longest]] block chain it can find. Any transaction on the difficultywise-longest well-formed chain is considered valid. Therefore, the validity of a transaction is determined by its height -- i.e. how many blocks come ''before'' it. A transaction's ''depth'' (the number of blocks ''after'' it) is used to determine the likelihood of the transaction being invalidated due to the emergence of a longer fork.

==== [[bitcoind|bitcoin-qt]] ====

==== [https://github.com/conformal/btcd btcd] ====

== Header-Only Clients ==

These client downloads a complete copy of the headers for all blocks in the entire block chain. This means that the download and storage requirements scale linearly with the amount of time since bitcoin was invented; it would be preferable to have the scaling be logarithmic or even constant.

=== Simplified Payment Verification (SPV) ===

This scheme is described in section 8 of the [http://bitcoin.org/bitcoin.pdf original bitcoin whitepaper].

==== Block '''Depth''' as a Transaction Validity Check ====

As Satoshi writes, "[the thin client] can't check the transaction for himself, but by linking it to a place in the chain, he can see that a network node has accepted it, and blocks added after it further confirm the network has accepted it." If we take "X" to be the "number of blocks added after it", then SPV essentially trusts that a transaction X blocks deep in the chain does not have inputs which were already spent further back in the chain. Therefore, the validity of a transaction is determined by its depth -- i.e. how many blocks come ''after'' it. Other thin client protocols also include this assumption.

This is very different from the trust model in the "thick" client: the thick client verifies that a transaction's inputs are unspent by actually checking the whole chain up to that point -- there is no "X blocks deep" involved here. The thick client uses "X blocks deep" (aka "confirmations") only once it has already decided that a transaction is valid (i.e. no [[Double-spending|double-spends]]). At that point it uses "X blocks deep" to decide how likely it is that a longer fork in the chain will emerge which excludes that transaction.

It is very important to understand how the same property ("X blocks deep") is used to verify two different properties in the thick client and SPV cases. '''The thick client never uses block depth as a measure of transaction validity; the SPV client does'''.

This is a concern in a situation where an SPV client is subjected to a double-spend attack by somebody who controls its network connection. For example, suppose you are at a wi-fi cafe and are paying for something using your smartphone -- the cafe owner controls your network connection. Satoshi acknowledges this implicitly when he writes that "the verification is reliable as long as honest nodes control the network" -- to be completely pedantic, this means that the verification is reliable as long as honest nodes control '''the part of the network that the SPV client is able to communicate with'''. In an attack-by-ISP scenario this may not be a sufficiently strong security property. The attacker would not need to overpower "the rest of the network" because the client is unable to communicate with it.

==== [[BitCoinJ|bitcoinj]] ====

Simplified Payment Verification is the verification mechanism used in [[BitCoinJ|bitcoinj]].

A security analysis of some of the issues in bitcoinj can be found [http://code.google.com/p/bitcoinj/wiki/SecurityModel here]; however:

* The claim that "picking 10 nodes and requiring all of them to be consistent needs much less trust" overlooks the problem of [https://en.bitcoin.it/wiki/Weaknesses#Cancer_nodes "cancer nodes"] and [http://en.wikipedia.org/wiki/Sybil_attack Sybil attacks].
* Many of the security claims are qualified by some form of "if you don't think an attacker controls your internet connection"; see the previous section for a discussion of why this is problematic.

==== [https://bitcointalk.org/index.php?topic=128055.0 picocoin] ====

Simplified Payment Verification is the verification mechanism used in picocoin.

The library (libccoin) that picocoin is based on includes code for validating scripts and blocks; this could potentially be used to implement a full-chain client.

==== [[Electrum]] ====

Electrum fetches blockchain information from Electrum servers, bitcoin nodes that index the blockchain by address.
Electrum performs Simple Payment Verification to check the transactions returned by servers.
For this, it fetches blokchain headers from about 10 random servers.
In addition, Electrum servers are authenticated by SSL, in order to protect users from MITM attacks.

=== Unused Output Tree in the Block chain (UOT) ===

There have been several proposals (the first appears to be [https://bitcointalk.org/index.php?topic=21995.0 this one] by gmaxwell, who called it an "open transaction tree", although the term "open" is now taken to mean "not yet mined into the block chain" rather than "unspent") to form a tree of unused transaction outputs at each block in the chain, hash it as a Merkle tree, and encode the root hash in the block chain (probably as part of the coinbase input). This will be called an Unused Output Tree (UOT). The first detailed proposal so far appears to be [https://en.bitcoin.it/wiki/User:DiThi/MTUT Alberto Torres' proposal]; etotheipi's [https://bitcointalk.org/index.php?topic=88208.0 ultimate block chain compression] is a variant of this.

If such UOT hashes were included in the block chain, a client which shipped with a [https://en.bitcoin.it/wiki/Vocabulary checkpoint] block that had a UOT would only need to download blocks after the checkpoint. Moreover, once the client had downloaded those blocks and confirmed their UOTs, it could discard all but the most recent block containing a UOT.

This would also let a thin client reduce the question of "is this output unspent" to the question of "is this block super-well-formed" where "well-formed" means "well-formed according to the normal block chain rules and additionally has an Unused Output Tree which is accurate and truthful". This is still a long way from the low level of trust involved in the thick client, but it is a major improvement over all existing proposals.

It is unlikely that bitcoin would ever arrive at a state where every single block had a UOT, since this would require upgrading 100% of the miners on the network, or else convincing enough miners to reject blocks which do not contain a UOT. The latter strategy risks creating block chain forks, which can be expensive (in reward terms) to miners. Therefore, any UOT strategy would need to cope with the fact that not every block contains a UOT.

Hostile miners may insert blocks into the chain which have what claims to be a UOT, but which is actually invalid. It is unlikely that such blocks could be kept out of the chain because, again, this would require adding a new block well-formedness criterion, and miners implementing this new criterion would risk "mining on the wrong side" of a fork, which could cost them a lot of money. Therefore, any UOT strategy would need to cope with the fact that not every block containing a UOT entry can be trusted.

Note that at the present moment no standard format for such Unused Output Tree hashes has been agreed upon, nor do any of the blocks in the chain contain them. The [https://bitcointalk.org/index.php?topic=91954 ultraprune] feature added to bitcoind-0.8 maintains a similar data structure on the client's disk. It does not put this data structure or its hash anywhere in the block chain.

== Server-Trusting Clients ==

These clients involve some (usually low) level of trust in the server they rely upon. Mechanisms for authenticating the server, and for confirming that the server has not been compromised, are usually not explained.

All thin clients listed below currently connect to a single server, and are vulnerable to an attack similar to a double-spend. The attack can be run by that single server - the server can just lie to them that they received a Bitcoin transaction, and they, assuming the server does not lie, perform some service, transfer funds or send goods without actually receiving any Bitcoin in exchange. Therefore, they are implicitly trusting it.

Future enhancements have been suggested that will have the client talk to multiple servers and broadcast transactions and query all of them. Unfortunately it is well known to security researchers that this does not actually increase security; it simply makes the exploits more complicated and difficult to find. Security researchers have a name for this phenomenon: it is called a "Sybil attack"<ref>http://en.wikipedia.org/wiki/Sybil_attack</ref>. [https://bitcointalk.org/index.php?topic=88208.msg975201#msg975201 This post] on bitcointalk explains how some governments (notably Iran and China) already perform these sorts of attacks on their own citizens, with the coerced assistance of SSL certificate authorities.

Clients with a checkpoint (even a very old one) that download and validate the headers for the whole block chain are [http://bitcoinmedia.com/the-irc-bootstrap-method-is-flawed/#comment-4243 not vulnerable] to Sybil attacks in the following sense: they can always ensure that an attack would cost more than the amount being stolen.

=== [[BCCAPI]] ===

== Other ==

* A [http://sourceforge.net/mailarchive/message.php?msg_id=28633866 thread] on bitcoin-dev
* A [http://bitcoin.stackexchange.com/questions/2584/is-reclaiming-disk-space-already-implemented-how-effective-will-it-be/2589 question] on bitcoin.stackexchange.com
* The [[Weaknesses#Sybil_attack|sybil attack (also known as "cancer nodes")]] paragraph explains some of the issues with thin clients that base security on trusting whatever "a majority of the IP addresses I can see" say.
* [http://bitcoin.stackexchange.com/questions/2613/how-secure-are-various-models-of-bitcoin-clients related discussion on Stack Exchange]
* A hypothesized [https://bitcointalk.org/index.php?topic=134318.msg1441171#msg1441171 intermediate security class] between SPV and full-chain validation.

<references>

[[Category:Technical]]
[[category:Clients]]
[[Category:Security]]

Thin Client Security

2015-02-16T08:41:30Z

Eldentyrell: Lapp0: misspellings corrected.

Recently there have been a number of proposals for bitcoin clients which do not store a complete copy of every block in the entire block chain. This page will refer to all such clients as "thin clients". This page is meant to be a place to try to make sense of the security and trust implications of the various schemes.

== Block Height vs. Depth ==

It is important to distinguish between block height verification and block depth verification.

A client verifies the height H of a block by checking that there are H block '''before''' it, all of which are well-formed and obey the maximum-difficulty-adjustment-rate rule. Currently only the Satoshi client, libbitcoin, and btcd do block height verification. Block height is the fundamental anchor of trustless security in the Bitcoin system.

A client verifies the depth D of a block by checking that there are D blocks '''after''' it (also called "confirmations"), all of which are well-formed. SPV clients substitute block depth for block height as a transaction validity check. All clients use block depth as a measure of the liklihood of a [[Chain_Reorganization|block chain reorganization]] producing a new longer fork which excludes the transaction (i.e. [[Orphan_Block|orphaning]] its block).

See also [https://bitcointalk.org/index.php?topic=88208.msg987429#msg987429 some comments on probabilistic verification of block height].

== Full-Chain Clients ==

The "thick" bitcoin client downloads a copy of the entire chain, including all transactions (not just headers). It will be used as the reference point for security comparisons below.

=== Block '''Height''' as a Transaction Validity Check ===

A full-chain client trusts the [[Protocol_rules#Blocks well-formed|difficultywise-longest]] block chain it can find. Any transaction on the difficultywise-longest well-formed chain is considered valid. Therefore, the validity of a transaction is determined by its height -- i.e. how many blocks come ''before'' it. A transaction's ''depth'' (the number of blocks ''after'' it) is used to determine the likelihood of the transaction being invalidated due to the emergence of a longer fork.

==== [[bitcoind|bitcoin-qt]] ====

==== [https://github.com/conformal/btcd btcd] ====

== Header-Only Clients ==

These client downloads a complete copy of the headers for all blocks in the entire block chain. This means that the download and storage requirements scale linearly with the amount of time since bitcoin was invented; it would be preferable to have the scaling be logarithmic or even constant.

=== Simplified Payment Verification (SPV) ===

This scheme is described in section 8 of the [http://bitcoin.org/bitcoin.pdf original bitcoin whitepaper].

==== Block '''Depth''' as a Transaction Validity Check ====

As Satoshi writes, "[the thin client] can't check the transaction for himself, but by linking it to a place in the chain, he can see that a network node has accepted it, and blocks added after it further confirm the network has accepted it." If we take "X" to be the "number of blocks added after it", then SPV essentially trusts that a transaction X blocks deep in the chain does not have inputs which were already spent further back in the chain. Therefore, the validity of a transaction is determined by its depth -- i.e. how many blocks come ''after'' it. Other thin client protocols also include this assumption.

This is very different from the trust model in the "thick" client: the thick client verifies that a transaction's inputs are unspent by actually checking the whole chain up to that point -- there is no "X blocks deep" involved here. The thick client uses "X blocks deep" (aka "confirmations") only once it has already decided that a transaction is valid (i.e. no [[Double-spending|double-spends]]). At that point it uses "X blocks deep" to decide how likely it is that a longer fork in the chain will emerge which excludes that transaction.

It is very important to understand how the same property ("X blocks deep") is used to verify two different properties in the thick client and SPV cases. '''The thick client never uses block depth as a measure of transaction validity; the SPV client does'''.

This is a concern in a situation where an SPV client is subjected to a double-spend attack by somebody who controls its network connection. For example, suppose you are at a wi-fi cafe and are paying for something using your smartphone -- the cafe owner controls your network connection. Satoshi acknowledges this implicitly when he writes that "the verification is reliable as long as honest nodes control the network" -- to be completely pedantic, this means that the verification is reliable as long as honest nodes control '''the part of the network that the SPV client is able to communicate with'''. In an attack-by-ISP scenario this may not be a sufficiently strong security property. The attacker would not need to overpower "the rest of the network" because the client is unable to communicate with it.

==== [[BitCoinJ|bitcoinj]] ====

Simplified Payment Verification is the verification mechanism used in [[BitCoinJ|bitcoinj]].

A security analysis of some of the issues in bitcoinj can be found [http://code.google.com/p/bitcoinj/wiki/SecurityModel here]; however:

* The claim that "picking 10 nodes and requiring all of them to be consistent needs much less trust" overlooks the problem of [https://en.bitcoin.it/wiki/Weaknesses#Cancer_nodes "cancer nodes"] and [http://en.wikipedia.org/wiki/Sybil_attack Sybil attacks].
* Many of the security claims are qualified by some form of "if you don't think an attacker controls your internet connection"; see the previous section for a discussion of why this is problematic.

==== [https://bitcointalk.org/index.php?topic=128055.0 picocoin] ====

Simplified Payment Verification is the verification mechanism used in picocoin.

The library (libccoin) that picocoin is based on includes code for validating scripts and blocks; this could potentially be used to implement a full-chain client.

==== [[Electrum]] ====

Electrum fetches blockchain information from Electrum servers, bitcoin nodes that index the blockchain by address.
Electrum performs Simple Payment Verification to check the transactions returned by servers.
For this, it fetches blokchain headers from about 10 random servers.
In addition, Electrum servers are authenticated by SSL, in order to protect users from MITM attacks.

=== Unused Output Tree in the Block chain (UOT) ===

There have been several proposals (the first appears to be [https://bitcointalk.org/index.php?topic=21995.0 this one] by gmaxwell, who called it an "open transaction tree", although the term "open" is now taken to mean "not yet mined into the block chain" rather than "unspent") to form a tree of unused transaction outputs at each block in the chain, hash it as a Merkle tree, and encode the root hash in the block chain (probably as part of the coinbase input). This will be called an Unused Output Tree (UOT). The first detailed proposal so far appears to be [https://en.bitcoin.it/wiki/User:DiThi/MTUT Alberto Torres' proposal]; etotheipi's [https://bitcointalk.org/index.php?topic=88208.0 ultimate block chain compression] is a variant of this.

If such UOT hashes were included in the block chain, a client which shipped with a [https://en.bitcoin.it/wiki/Vocabulary checkpoint] block that had a UOT would only need to download blocks after the checkpoint. Moreover, once the client had downloaded those blocks and confirmed their UOTs, it could discard all but the most recent block containing a UOT.

This would also let a thin client reduce the question of "is this output unspent" to the question of "is this block super-well-formed" where "well-formed" means "well-formed according to the normal block chain rules and additionally has an Unused Output Tree which is accurate and truthful". This is still a long way from the low level of trust involved in the thick client, but it is a major improvement over all existing proposals.

It is unlikely that bitcoin would ever arrive at a state where every single block had a UOT, since this would require upgrading 100% of the miners on the network, or else convincing enough miners to reject blocks which do not contain a UOT. The latter strategy risks creating block chain forks, which can be expensive (in reward terms) to miners. Therefore, any UOT strategy would need to cope with the fact that not every block contains a UOT.

Hostile miners may insert blocks into the chain which have what claims to be a UOT, but which is actually invalid. It is unlikely that such blocks could be kept out of the chain because, again, this would require adding a new block well-formedness criterion, and miners implementing this new criterion would risk "mining on the wrong side" of a fork, which could cost them a lot of money. Therefore, any UOT strategy would need to cope with the fact that not every block containing a UOT entry can be trusted.

Note that at the present moment no standard format for such Unused Output Tree hashes has been agreed upon, nor do any of the blocks in the chain contain them. The [https://bitcointalk.org/index.php?topic=91954 ultraprune] feature added to bitcoind-0.8 maintains a similar data structure on the client's disk. It does not put this data structure or its hash anywhere in the block chain.

== Server-Trusting Clients ==

These clients involve some (usually low) level of trust in the server they rely upon. Mechanisms for authenticating the server, and for confirming that the server has not been compromised, are usually not explained.

All thin clients listed below currently connect to a single server, and are vulnerable to an attack similar to a double-spend. The attack can be run by that single server - the server can just lie to them that they received a Bitcoin transaction, and they, assuming the server does not lie, perform some service, transfer funds or send goods without actually receiving any Bitcoin in exchange. Therefore, they are implicitly trusting it.

Future enhancements have been suggested that will have the client talk to multiple servers and broadcast transactions and query all of them. Unfortunately it is well known to security researchers that this does not actually increase security; it simply makes the exploits more complicated and difficult to find. Security researchers have a name for this phenomenon: it is called a "Sybil attack"<ref>http://en.wikipedia.org/wiki/Sybil_attack</ref>. [https://bitcointalk.org/index.php?topic=88208.msg975201#msg975201 This post] on bitcointalk explains how some governments (notably Iran and China) already perform these sorts of attacks on their own citizens, with the coerced assistance of SSL certificate authorities.

Clients with a checkpoint (even a very old one) that download and validate the headers for the whole block chain are [http://bitcoinmedia.com/the-irc-bootstrap-method-is-flawed/#comment-4243 not vulnerable] to Sybil attacks in the following sense: they can always ensure that an attack would cost more than the amount being stolen.

=== [[BCCAPI]] ===

== Other ==

* A [http://sourceforge.net/mailarchive/message.php?msg_id=28633866 thread] on bitcoin-dev
* A [http://bitcoin.stackexchange.com/questions/2584/is-reclaiming-disk-space-already-implemented-how-effective-will-it-be/2589 question] on bitcoin.stackexchange.com
* The [[Weaknesses#Sybil_attack|sybil attack (also known as "cancer nodes")]] paragraph explains some of the issues with thin clients that base security on trusting whatever "a majority of the IP addresses I can see" say.
* [http://bitcoin.stackexchange.com/questions/2613/how-secure-are-various-models-of-bitcoin-clients related discussion on Stack Exchange]
* A hypothesized [https://bitcointalk.org/index.php?topic=134318.msg1441171#msg1441171 intermediate security class] between SPV and full-chain validation.

<references>

[[Category:Technical]]
[[category:Clients]]
[[Category:Security]]

Thin Client Security

2015-02-02T09:02:58Z

Eldentyrell: Correct, you misunderstood. Difficultywise-longer chain = more work spent on it = harder to forge = greater consensus.

Recently there have been a number of proposals for bitcoin clients which do not store a complete copy of every block in the entire block chain. This page will refer to all such clients as "thin clients". This page is meant to be a place to try to make sense of the security and trust implications of the various schemes.

== Block Height vs. Depth ==

It is important to distinguish between block height verification and block depth verification.

A client verifies the height H of a block by checking that there are H block '''before''' it, all of which are well-formed and obey the maximum-difficulty-adjustment-rate rule. Currently only the Satoshi client, libbitcoin, and btcd do block height verification. Block height is the fundamental anchor of trustless security in the Bitcoin system.

A client verifies the depth D of a block by checking that there are D blocks '''after''' it (also called "confirmations"), all of which are well-formed. SPV clients substitute block depth for block height as a transaction validity check. All clients use block depth as a measure of the liklihood of a [[Chain_Reorganization|block chain reorganization]] producing a new longer fork which excludes the transaction (i.e. [[Orphan_Block|orphaning]] its block).

See also [https://bitcointalk.org/index.php?topic=88208.msg987429#msg987429 some comments on probabilistic verification of block height].

== Full-Chain Clients ==

The "thick" bitcoin client downloads a copy of the entire chain, including all transactions (not just headers). It will be used as the reference point for security comparisions below.

=== Block '''Height''' as a Transaction Validity Check ===

A full-chain client trusts the [[Protocol_rules#Blocks well-formed|difficultywise-longest]] block chain it can find. Any transaction on the difficultywise-longest well-formed chain is considered valid. Therefore, the validity of a transaction is determined by its height -- i.e. how many blocks come ''before'' it. A transaction's ''depth'' (the number of blocks ''after'' it) is used to determine the likelihood of the transaction being invalidated due to the emergence of a longer fork.

==== [[bitcoind|bitcoin-qt]] ====

==== [https://github.com/conformal/btcd btcd] ====

== Header-Only Clients ==

These client downloads a complete copy of the headers for all blocks in the entire block chain. This means that the download and storage requirements scale linearly with the amount of time since bitcoin was invented; it would be preferable to have the scaling be logarithmic or even constant.

=== Simplified Payment Verification (SPV) ===

This scheme is described in section 8 of the [http://bitcoin.org/bitcoin.pdf original bitcoin whitepaper].

==== Block '''Depth''' as a Transaction Validity Check ====

As Satoshi writes, "[the thin client] can't check the transaction for himself, but by linking it to a place in the chain, he can see that a network node has accepted it, and blocks added after it further confirm the network has accepted it." If we take "X" to be the "number of blocks added after it", then SPV essentially trusts that a transaction X blocks deep in the chain does not have inputs which were already spent further back in the chain. Therefore, the validity of a transaction is determined by its depth -- i.e. how many blocks come ''after'' it. Other thin client protocols also include this assumption.

This is very different from the trust model in the "thick" client: the thick client verifies that a transaction's inputs are unspent by actually checking the whole chain up to that point -- there is no "X blocks deep" involved here. The thick client uses "X blocks deep" (aka "confirmations") only once it has already decided that a transaction is valid (i.e. no [[Double-spending|double-spends]]). At that point it uses "X blocks deep" to decide how likely it is that a longer fork in the chain will emerge which excludes that transaction.

It is very important to understand how the same property ("X blocks deep") is used to verify two different properties in the thick client and SPV cases. '''The thick client never uses block depth as a measure of transaction validity; the SPV client does'''.

This is a concern in a situation where an SPV client is subjected to a double-spend attack by somebody who controls its network connection. For example, suppose you are at a wi-fi cafe and are paying for something using your smartphone -- the cafe owner controls your network connection. Satoshi acknowledges this implicitly when he writes that "the verification is reliable as long as honest nodes control the network" -- to be completely pedantic, this means that the verification is reliable as long as honest nodes control '''the part of the network that the SPV client is able to communicate with'''. In an attack-by-ISP scenario this may not be a sufficiently strong security property. The attacker would not need to overpower "the rest of the network" because the client is unable to communicate with it.

==== [[BitCoinJ|bitcoinj]] ====

Simplified Payment Verification is the verification mechanism used in [[BitCoinJ|bitcoinj]].

A security analysis of some of the issues in bitcoinj can be found [http://code.google.com/p/bitcoinj/wiki/SecurityModel here]; however:

* The claim that "picking 10 nodes and requiring all of them to be consistent needs much less trust" overlooks the problem of [https://en.bitcoin.it/wiki/Weaknesses#Cancer_nodes "cancer nodes"] and [http://en.wikipedia.org/wiki/Sybil_attack Sybil attacks].
* Many of the security claims are qualified by some form of "if you don't think an attacker controls your internet connection"; see the previous section for a discussion of why this is problematic.

==== [https://bitcointalk.org/index.php?topic=128055.0 picocoin] ====

Simplified Payment Verification is the verification mechanism used in picocoin.

The library (libccoin) that picocoin is based on includes code for validating scripts and blocks; this could potentially be used to implement a full-chain client.

==== [[Electrum]] ====

ThomasV [https://en.bitcoin.it/w/index.php?title=Thin_Client_Security&action=historysubmit&diff=42844&oldid=36519 claims] that "Electrum, it is doing SPV since 2012".

=== Unused Output Tree in the Block chain (UOT) ===

There have been several proposals (the first appears to be [https://bitcointalk.org/index.php?topic=21995.0 this one] by gmaxwell, who called it an "open transaction tree", although the term "open" is now taken to mean "not yet mined into the block chain" rather than "unspent") to form a tree of unused transaction outputs at each block in the chain, hash it as a Merkle tree, and encode the root hash in the block chain (probably as part of the coinbase input). This will be called an Unused Output Tree (UOT). The first detailed proposal so far appears to be [https://en.bitcoin.it/wiki/User:DiThi/MTUT Alberto Torres' proposal]; etotheipi's [https://bitcointalk.org/index.php?topic=88208.0 ultimate block chain compression] is a variant of this.

If such UOT hashes were included in the block chain, a client which shipped with a [https://en.bitcoin.it/wiki/Vocabulary checkpoint] block that had a UOT would only need to download blocks after the checkpoint. Moreover, once the client had downloaded those blocks and confirmed their UOTs, it could discard all but the most recent block containing a UOT.

This would also let a thin client reduce the question of "is this output unspent" to the question of "is this block super-well-formed" where "well-formed" means "well-formed according to the normal block chain rules and additionally has an Unused Output Tree which is accurate and truthful". This is still a long way from the low level of trust involved in the thick client, but it is a major improvement over all existing proposals.

It is unlikely that bitcoin would ever arrive at a state where every single block had a UOT, since this would require upgrading 100% of the miners on the network, or else convincing enough miners to reject blocks which do not contain a UOT. The latter strategy risks creating block chain forks, which can be expensive (in reward terms) to miners. Therefore, any UOT strategy would need to cope with the fact that not every block contains a UOT.

Hostile miners may insert blocks into the chain which have what claims to be a UOT, but which is actually invalid. It is unlikely that such blocks could be kept out of the chain because, again, this would require adding a new block well-formedness criterion, and miners implementing this new criterion would risk "mining on the wrong side" of a fork, which could cost them a lot of money. Therefore, any UOT strategy would need to cope with the fact that not every block containing a UOT entry can be trusted.

Note that at the present moment no standard format for such Unused Output Tree hashes has been agreed upon, nor do any of the blocks in the chain contain them. The [https://bitcointalk.org/index.php?topic=91954 ultraprune] feature added to bitcoind-0.8 maintains a similar data structure on the client's disk. It does not put this data structure or its hash anywhere in the block chain.

== Server-Trusting Clients ==

These clients involve some (usually low) level of trust in the server they rely upon. Mechanisms for authenticating the server, and for confirming that the server has not been compromised, are usually not explained.

All thin clients listed below currently connect to a single server, and are vulnerable to an attack similar to a double-spend. The attack can be run by that single server - the server can just lie to them that they received a Bitcoin transaction, and they, assuming the server does not lie, perform some service, transfer funds or send goods without actually receiving any Bitcoin in exchange. Therefore, they are implicitly trusting it.

Future enhancements have been suggested that will have the client talk to multiple servers and broadcast transactions and query all of them. Unfortunately it is well known to security researchers that this does not actually increase security; it simply makes the exploits more complicated and difficult to find. Security researchers have a name for this phenomenon: it is called a "Sybil attack"<ref>http://en.wikipedia.org/wiki/Sybil_attack</ref>. [https://bitcointalk.org/index.php?topic=88208.msg975201#msg975201 This post] on bitcointalk explains how some governments (notably Iran and China) already perform these sorts of attacks on their own citizens, with the coerced assistance of SSL certificate authorities.

Clients with a checkpoint (even a very old one) that download and validate the headers for the whole block chain are [http://bitcoinmedia.com/the-irc-bootstrap-method-is-flawed/#comment-4243 not vulnerable] to Sybil attacks in the following sense: they can always ensure that an attack would cost more than the amount being stolen.

=== [[BCCAPI]] ===

== Other ==

* A [http://sourceforge.net/mailarchive/message.php?msg_id=28633866 thread] on bitcoin-dev
* A [http://bitcoin.stackexchange.com/questions/2584/is-reclaiming-disk-space-already-implemented-how-effective-will-it-be/2589 question] on bitcoin.stackexchange.com
* The [[Weaknesses#Sybil_attack|sybil attack (also known as "cancer nodes")]] paragraph explains some of the issues with thin clients that base security on trusting whatever "a majority of the IP addresses I can see" say.
* [http://bitcoin.stackexchange.com/questions/2613/how-secure-are-various-models-of-bitcoin-clients related discussion on Stack Exchange]
* A hypothesized [https://bitcointalk.org/index.php?topic=134318.msg1441171#msg1441171 intermediate security class] between SPV and full-chain validation.

<references>

[[Category:Technical]]
[[category:Clients]]
[[Category:Security]]

Hardfork Wishlist

2014-03-30T13:22:00Z

Eldentyrell: /* Bug fixes */

The '''Hardfork Wishlist''' is to record changes to Bitcoin that might be desirable, but that will require a [[Hardfork|"hard" block-chain split]] (everybody must upgrade, old software will not accept blocks/transactions created with the new [[Protocol rules|rules]], considering them to be [[Invalid block|invalid blocks]]).

This page is ''not'' for changes that can be accomplished in way that is compatible with old software (for example, by making transactions [[Nonstandard block|nonstandard]] or by [[Discouraged block|discouraging blocks]]).

This page is also not for changes that can be accomplished by a [[Softfork]]. See [[Softfork_wishlist]].

== Changes to hard-coded limits ==
* Replace hard-coded maximum block size (1,000,000 bytes) and maximum number of signature operations per block (20,000) with ???.

== Major structural changes ==
* "Flip the chain", instead of committing to new transactions, commit to the summaries of open transactions: [https://bitcointalk.org/index.php?topic=505.0] [https://bitcointalk.org/index.php?topic=21995.0] [https://en.bitcoin.it/wiki/User:DiThi/MTUT#PROPOSAL:_Merkle_tree_of_unspent_transactions_.28MTUT.29.2C_for_serverless_thin_clients_and_self-verifiable_prunned_blockchain.] [https://bitcointalk.org/index.php?topic=88208.0]
* Increased efficiency for merged mining: restructure the primary header to make the bitcoin specific data non-mandatory. (e.g. the block chain specific stuff would go into second header connected by a header tree), making the primary headers pure timestamps and nonces.
* Switch to block hashing algorithm secure against block withholding attacks.

== Transaction behavior changes==
* Improved signature types to allow for partial malleability of outputs. (e.g. make it easier to add a fee onto someone else's transaction, or to take fees from a transaction without outputs set aside for that purpose)
* Elimination of output scripts: all transactions pay-to-scripthash, probably with a single byte indicating the scripthash type. Other than reducing effective output script secrecy (which is not possible without OP_EVAL anyways) this is believed to be costless, and the secrecy can be recovered with recursive OP_EVAL. The motivation here is that data in outputs is far more expensive than inputs because some outputs may be never prunable, and pay-to-scripthash minimizes output size without harming total size.
* Allow soft-spending of generation outputs without confirmations (outputs of these transactions might also appear as generation themselves)
* Allow additional inputs to generation transactions
* Add new signature hashtype to include value of TxOut being spent, in the hash to be signed. Doing this would remove the requirement that offline signing devices be sent all supporting transactions with the transaction-to-be-signed, just to confirm the transaction fee.

== Privacy ==
* Better privacy using [http://en.wikipedia.org/wiki/Non-interactive_zero-knowledge_proof NIZKP]s, as proposed in [http://zerocoin.org Zerocoin] or similar.

== Currency changes==
''Please don't list anything here which would significantly change the committed overall economics of the system, it's safe to assume anything with significant economic impact will _never_ be changed in Bitcoin<ref>[http://bitcointalk.org/index.php?topic=45468.msg542375#msg542375 Suggested MAJOR change to Bitcoin]</ref>, because such changes would undermine the trust people have in the system, though they may form the basis of an interesting [[alternative chain]].
* Increase currency divisibility.

== Navel gazing / Protocol housekeeping==
* Byte order consistency (big endian)
* Eliminate redundancies in the variable length integer encodings, possibly switch to a standard.
* Avoiding hashes covering malleable fields

== Bug fixes ==
* CHECKMULTISIG popping one-too-many items off the stack
* Difficulty adjustment periods should overlap (prevent potential 'timejacking') Note: An ideal adjustment algorithm would ensure there is no easy dispute on "next target" for any block. Eg, it should not be possible for MinerX to set his block time 2 hours in the future to achieve a slightly higher difficulty and win any same-block-height race by default.
* Difficulty adjustment should adapt to sudden hashrate loss. Note: many altchains which have attempted this have created significant security vulnerabilities in the process, but experimentation continues.
* Scripts should be fully enabled after a careful audit.
* Miners/relays should not be able to inject extra arbitrary data into transactions?
* Use the previous block hash as an explicit or implicit prev_in in coinbases when hashing them to make it ~impossible to get a duplicate coinbase, thus removing the need for a pruning node to remember coinbase hashes to prevent duplicates consistently with the rest of the network. Note that this problem has already been solved with a softfork in [https://bitcointalk.org/index.php?topic=92558.0 BIP34].
* coinbases must be parseable.
* This changes would involve converting old blocks: uint64_t for timestamp field in blocks.
* Retarget using previous 2016 intervals instead of 2015 intervals; this bug enables Artforz' [https://bitcointalk.org/index.php?topic=43692.msg521772#msg521772 time warp attack].

==See Also==
*[[Prohibited changes]]

==References==
<references />

[[Category:Technical]]
[[Category:Developer]]

Hardfork Wishlist

2014-03-30T13:05:29Z

Eldentyrell: add timewarp attack

The '''Hardfork Wishlist''' is to record changes to Bitcoin that might be desirable, but that will require a [[Hardfork|"hard" block-chain split]] (everybody must upgrade, old software will not accept blocks/transactions created with the new [[Protocol rules|rules]], considering them to be [[Invalid block|invalid blocks]]).

This page is ''not'' for changes that can be accomplished in way that is compatible with old software (for example, by making transactions [[Nonstandard block|nonstandard]] or by [[Discouraged block|discouraging blocks]]).

This page is also not for changes that can be accomplished by a [[Softfork]]. See [[Softfork_wishlist]].

== Changes to hard-coded limits ==
* Replace hard-coded maximum block size (1,000,000 bytes) and maximum number of signature operations per block (20,000) with ???.

== Major structural changes ==
* "Flip the chain", instead of committing to new transactions, commit to the summaries of open transactions: [https://bitcointalk.org/index.php?topic=505.0] [https://bitcointalk.org/index.php?topic=21995.0] [https://en.bitcoin.it/wiki/User:DiThi/MTUT#PROPOSAL:_Merkle_tree_of_unspent_transactions_.28MTUT.29.2C_for_serverless_thin_clients_and_self-verifiable_prunned_blockchain.] [https://bitcointalk.org/index.php?topic=88208.0]
* Increased efficiency for merged mining: restructure the primary header to make the bitcoin specific data non-mandatory. (e.g. the block chain specific stuff would go into second header connected by a header tree), making the primary headers pure timestamps and nonces.
* Switch to block hashing algorithm secure against block withholding attacks.

== Transaction behavior changes==
* Improved signature types to allow for partial malleability of outputs. (e.g. make it easier to add a fee onto someone else's transaction, or to take fees from a transaction without outputs set aside for that purpose)
* Elimination of output scripts: all transactions pay-to-scripthash, probably with a single byte indicating the scripthash type. Other than reducing effective output script secrecy (which is not possible without OP_EVAL anyways) this is believed to be costless, and the secrecy can be recovered with recursive OP_EVAL. The motivation here is that data in outputs is far more expensive than inputs because some outputs may be never prunable, and pay-to-scripthash minimizes output size without harming total size.
* Allow soft-spending of generation outputs without confirmations (outputs of these transactions might also appear as generation themselves)
* Allow additional inputs to generation transactions
* Add new signature hashtype to include value of TxOut being spent, in the hash to be signed. Doing this would remove the requirement that offline signing devices be sent all supporting transactions with the transaction-to-be-signed, just to confirm the transaction fee.

== Privacy ==
* Better privacy using [http://en.wikipedia.org/wiki/Non-interactive_zero-knowledge_proof NIZKP]s, as proposed in [http://zerocoin.org Zerocoin] or similar.

== Currency changes==
''Please don't list anything here which would significantly change the committed overall economics of the system, it's safe to assume anything with significant economic impact will _never_ be changed in Bitcoin<ref>[http://bitcointalk.org/index.php?topic=45468.msg542375#msg542375 Suggested MAJOR change to Bitcoin]</ref>, because such changes would undermine the trust people have in the system, though they may form the basis of an interesting [[alternative chain]].
* Increase currency divisibility.

== Navel gazing / Protocol housekeeping==
* Byte order consistency (big endian)
* Eliminate redundancies in the variable length integer encodings, possibly switch to a standard.
* Avoiding hashes covering malleable fields

== Bug fixes ==
* CHECKMULTISIG popping one-too-many items off the stack
* Difficulty adjustment periods should overlap (prevent potential 'timejacking') Note: An ideal adjustment algorithm would ensure there is no easy dispute on "next target" for any block. Eg, it should not be possible for MinerX to set his block time 2 hours in the future to achieve a slightly higher difficulty and win any same-block-height race by default.
* Difficulty adjustment should adapt to sudden hashrate loss. Note: many altchains which have attempted this have created significant security vulnerabilities in the process, but experimentation continues.
* Scripts should be fully enabled after a careful audit.
* Miners/relays should not be able to inject extra arbitrary data into transactions?
* Use the previous block hash as an explicit or implicit prev_in in coinbases when hashing them to make it ~impossible to get a duplicate coinbase, thus removing the need for a pruning node to remember coinbase hashes to prevent duplicates consistently with the rest of the network. Note that this problem has already been solved with a softfork in [https://bitcointalk.org/index.php?topic=92558.0 BIP34].
* coinbases must be parseable.
This changes would involve converting old blocks:
* uint64_t for timestamp field in blocks.
* Retarget using previous 2016 intervals instead of 2015 intervals; this bug enables Artforz' [https://bitcointalk.org/index.php?topic=43692.msg521772#msg521772 time warp attack].

==See Also==
*[[Prohibited changes]]

==References==
<references />

[[Category:Technical]]
[[Category:Developer]]

Proof of burn

2014-03-25T13:32:04Z

Eldentyrell: Undo revision 45350 by Eldentyrell (talk)

'''Proof of burn''' is method for bootstrapping one cryptocurrency off of another. The idea is that miners should show proof that they ''burned'' some coins - that is, sent them to a verifiably unspendable address. This is expensive from their individual point of view, just like proof of work; but it consumes no resources other than the burned underlying asset. To date, all proof of burn cryptocurrencies work by burning proof-of-work-mined cryptocurrencies, so the ultimate source of scarcity remains the proof-of-work-mined "fuel".

There are likely many possible variants of proof of burn. This page currently describes [[User:Ids|Iain Stewart]]'s version. Other people can add variant versions that still belong to the broad proof of burn idea.

== Iain Stewart's version of proof of burn ==

=== Introduction and motivation ===

The key idea of proof-of-burn (this would also apply to proof-of-stake, by the way) is that when choosing the thing which is to qualify as a "difficulty", i.e. to require miners to exhibit proof that they've "done something that's tough to do", all that matters is that ''an individual miner'' finds the task expensive. (Well... it also matters that everyone else should find it cheap to verify that it has been done.) It doesn't need to be the case that real resources are consumed in the real economy.

With proof-of-work, it so happens that real resources are indeed consumed - mining rigs are produced, with human labour and materials as input, electricity is used, and all these things have to be bid away from their real-economy best alternative uses. (Or, if they're produced ''in addition'' to what would have been produced, the total of leisure time is less than it could have been. Something real is grabbed as input.) And while a cryptocurrency is being set up (i.e. [the fast early phase of] its initial distribution) - or, more precisely, while ''the first'' cryptocurrency is being set up; more on this distinction later! - no good alternative has been proposed. (And I'm not proposing one.) But once a cryptocurrency is up and running, with its initial distribution close to completed, new possibilities arise, for tasks to "feel expensive" to a miner but not actually "be expensive" from a god-like whole-economy perspective.

Proof-of-stake (of the "Cunicula variety", I mean) is in fact arguably already an example of such a task. It feels awfully expensive, to a miner, to save up a lot of bitcoins and become a big stakeholder; but from a whole-economy viewpoint, this is a swapping of assets' ownership labels around, it's not a burning of electricity or the like. However, I thought it would be interesting to invent a task that is absolutely, nakedly, unambiguously an example of the contrast between the two viewpoints. And yes, there is one: burning the currency!

By "burning" a tranche of bitcoins I just mean sending them to an address which is unspendable. The precise technical details of this will vary from cryptocurrency to cryptocurrency. With Bitcoin, any address which is [the RIPEMD160/SHA256 hash of] a script that evaluates to false will do. So, the script should do a "deliberately silly" thing - instead of things like "check such-and-such signature, and put the validity result on the stack", it should do something like "add 2 and 2, and now check if what's on top of the stack is equal to 5". (Or just "push 4, and check if it's equal to 5". Anything of that sort.) There are thus an unbounded number of such scripts, with entropy saturating RIPEMD160 since you can choose big numbers to taste. So, bitcoins sent to such a txout can never be redeemed on a future txin. (Barring the cracking of RIPEMD160 and the finding of an alternative matching script, that is. If ''that'' happens, the cryptocurrency is in big trouble anyway!)

With this definition of burning, it's not obvious to blockchain-watchers that some bitcoins ''have'' been burnt, at the time of burning. They've been sent to an address which doesn't stand out from any other. It's only later, when a miner who burned them earlier now wants to exhibit proof that "yes, these coins are burnt", that blockchain-watchers get their proof. (Which basically consists of exhibiting the script that manifestly always evaluates to false, and hashes to the address.) If it's thought desirable that the act of burning should be obvious right away, rather than later, then this can be achieved: burning merely needs to be defined as sending to some ''fixed'' unspendable address, with no variation - e.g. we could settle on the hash of "push 4, and check if it's equal to 5".

So, miners are creating candidate winning blocks by saying to the listening world, not "Look! I've done this many trillion hashes! [or struck lucky with fewer: you, the listening world, wouldn't know the difference... but this doesn't matter...]", but rather "Look! Two months ago I burned this many bitcoins!". In both cases, "this many" means an adjustable difficulty parameter, which the network adjusts from time to time (fortnightly, in today's Bitcoin) to squeeze out marginal miners (and keep more-efficient-than-marginal ones in profit) to just the extent needed to regulate block creation to a preferred pace (one per 10 minutes, in today's Bitcoin).

Why that phrase "Two months ago"? The broad principle is as follows. A miner mustn't be able to just burn some bitcoins ''right now'' and say "OK, I've burned them! Now let me have all those latest juicy transaction fees that have arrived in the past few minutes! Thanks!" That extremely recent act of burning could be undone in a block chain reorganisation; and then the same miner would be able to "re-burn" those same coins in an attempt to grab a block afresh, post-reorganisation. That would constitute a breakdown in the analogy of burning with proof-of-work hashing. A trillion proof-of-work hashes on a pre-reorg block are of no value on the post-reorg chain. A proof-of-work miner must simply shrug and say "Oh well, that's those expenses [electricity, mining rig rental / imputed rental,...] lost and gone... time to try again!" And that's the way things should be, for security - it '''should not''' be as cheap to extend the height of two or more competing chains as it is to focus on one. (And having decided to focus on one, a miner ''should'' incur a risk of lost expense if their choice turns out to be "the wrong one" in network consensus terms.)

The above point makes it clear why the act of burning should be a decent interval earlier than the act of exhibiting proof. Two months may be overdoing it, but the protocol should require it to be sufficiently far back that there's no practical possibility of it being undone. There are in fact some further issues, to do with making sure it's not cheap for a miner to ''re-exhibit'' their proof (of having performed a suitably substantial burn a suitably long time ago) on multiple competing chains. Details to follow.

Now then! How much burning will actually happen, under this protocol? The answer is straightforward enough, though its implications are quite broad and in some ways surprising. Miners will burn bitcoins at an average rate '''very close to''' the average rate that ordinary users are sending them fees (and any coin-minting still going on too of course), minus the miners' true real-resource costs (i.e. the hardware and electricity and the like for handling transactions and blocks and burn proofs - these costs will be far lower than the hashing costs incurred under proof-of-work, but of course still non-zero). This follows by the same sort of "approach to equilibrium" reasoning that tells us that miners will ''expend real resources on proof-of-work'' to roughly that extent - if they didn't, mining would be supra-normally profitable, and new entrants would be attracted into the trade. If burning coins, rather than buying a lot of kit from a mining rig supplier, is the expense incurred by a miner to compete for the revenue stream, the same economic principles apply.

=== Technical sketch of proof of burn: "Burnt coins are mining rigs!" ===

''Iain Stewart writes:'' In this subsection I give a provisional technical sketch of the operational details of the proof-of-burn protocol I've currently settled on. It can be summed up in the following pithy slogan:

'''''"Burnt coins are mining rigs!"'''''

What that slogan means will become clear as I go on. Basically, proof-of-work is so elegant, in so many different ways, excepting its high real-resource cost, that I decided my attempt at an alternative to it, avoiding its real-resource cost, should mimic it as faithfully as possible in every other aspect. Well, only readers can judge whether I've succeeded!

The key is to use a '''stream of true randomness''' - see below for where ''that'' comes from! - to simulate the generating of random hashes that a real proof-of-work mining rig would produce. Now, obviously we don't want to "simulate" every actual hash! A "simulation" of proof-of-work at ''that'' level of detail would just ''be'' proof-of-work! Rather, we want to mimic the statistical properties of a mining rig's stream of hashes, to just the level of detail required to give the same sort of pattern of meeting / not meeting a moving difficulty target, and all the rest of it, that we get with the real thing.

So: first of all, what exactly is my "stream of true randomness"? Chop up time into units considerably shorter than the intended inter-block time, but with no need to go much finer than general network latency. (Seconds will do, I think.) For each second, t, we need a uniform random number between 0 and 1 assigned to it, RAND(t). This sounds as if we need some awful dependency on a fragile central source - some high-powered laser at NASA pouring out quantum noise every second, or something - with all the trust and failure issues that would imply. Fortunately, for simulating mining rigs, we don't need anything like that. All that matters is that, to someone "buying a simulated mining rig" (burning some bitcoins, that is!) at time t, they can't predict the value of RAND(any t' 2 months or more to the future of t). [Where "2 months" means the dead time a burnt coin must wait before it becomes a simulated active mining rig. See introductory motivating section above. It's basically just a generous waiting period to make sure a burnt coin is truly definitely burnt, and won't have any chance of being "unburnt" in a chain reorg, by the time it comes into use in mining.] We do '''not''' need fresh statistical independence of RAND(t) w.r.t. all of RAND(t-1), RAND(t-2), RAND(t-3), etc. (And we don't mind if the stream is known a "short" time into the future - e.g. a week or two; at any rate a small portion of the waiting period.)

Such a lesser goal can, I believe, be achieved with just a few tens of bits of true randomness per week. Quality is what matters, not quantity! I suggest tapping into the world's most highly-audited source of low-bit-rate true randomness: lotteries. These (the big reputable ones anyway) are already subject to elaborate inspection of the machinery that tosses the balls around and draws some of them out. And the results are publicised so widely, in so many newspapers, TV channels, websites etc, as to make it impossible for anyone to lie about them.

Roughly weekly, a config-file (lottery-results.dat or whatever) should get "the latest lottery results" appended to it. There is no hurry about this, it doesn't need to be exactly every week, or even the same lottery every time, it just needs several tens of bits of fresh lottery data added roughly weekly. I believe there would be no trouble propagating this to all nodes, by out-of-band means if necessary. The format should be utterly simple and transparent, a 1-line plain text description of the results and the timestamp (t in RAND(t)) from which they are to be paid attention to, onwards. Like this:

.
.
.
for use from 2013-06-24 00:00:00 onwards: UK national lottery 2013-06-12: 4 9 20 22 37 42, bonus ball 19
for use from 2013-07-01 00:00:00 onwards: UK national lottery 2013-06-19: 7 12 14 19 33 41, bonus ball 28

(Obviously the meta-level words "for use from... onwards" aren't really needed - I just put them in for clarity.) Each line is added in a leisurely, unhurried fashion, at some time (it doesn't matter when) between the draw and the intended start-paying-attention-to-it date. (Some time between 2013-06-19 and 2013-07-01 00:00:00, in the case of the example last line above.) This gives plenty of time for people to add it themselves, from their favourite news source, and check by out-of-band means that they've added what everybody else has added, right down to spelling and punctuation. (Which in practice probably means copying it from somewhere. The point is, the "somewhere" doesn't need to be trusted - a lie, or an unexpected variation in format or spelling or punctuation, would be called out well within the leisurely timescale.)

RAND(t) is then HASH(config-file [excluding any lines that are "for use from ''time later than t'' onwards" of course], plus t itself [in some standard format, e.g. 2013-07-02 23:14:05, or just the Unix numeric time] as a final line). - Or if you like, HASH(HASH(config-file) ++ t), for efficiency. (Where "++" means "append together in some standard fashion".) "HASH()" is your favourite hash function, e.g. SHA256(SHA256()). Thus RAND(t) is a 256-bit integer, which we regard conceptually as a real number between 0 and 1 by putting a binary point in front.

(I'm aware that people on the forums are coming up with randomness protocols for proof-of-stake, proof-of-activity and the like which ''don't'' involve external true randomness like lotteries - they just hash the last hundred blocks' hashes together, or something like that. I don't think this is good enough. [For their application or for mine!] Someone producing the latest block, given the previous 99, can privately produce billions of cheap variations on it, by varying the order the transactions are listed etc, until they find, and publish, the one that "games" the randomness in their favour. However, if I'm wrong about this, and hashing the last hundred blocks is in fact fine, then good! We can drop the lottery rigmarole! Anyway, for the rest of this description, I'll simply assume that RAND(t) becomes available for all t, but remains unknown until a week or two before t, and in particular, RAND(2 months or more from now) is "massively unknown" right now - unknown with many tens to hundreds of bits of unknowable future entropy. That's all that matters for turning burnt coins into simulated mining rigs.)

Right then! What do we do with this RAND(t) stream? We simulate the capricious behaviour of a true proof-of-work mining rig! Let us assume that, in the real proof-of-work world, you can buy an h hashes/second mining rig for b=c*h BTC. (c varies with technical progress, BTC price fluctuations, etc; but in the simulated world it can just be left constant.) Or, inverting this, if you spend b BTC, you acquire a mining rig of h=b/c hashes/s power. Now, what does it actually mean for your rig to perform h hashes during 1 second? It means you're producing h uniform random numbers between 0 and 1. (That binary point again!) But you don't really care what they all are individually - how well you did during that 1 second is defined as "what was the '''lowest''' hash value you produced during that 1 second?". This is then inspected for whether it beats [is lower than] the network's current target; or, perhaps, whether it beats the lesser [i.e. numerically greater] target of a pooled mining operation. If it's good enough, that precious lowest hash is published to the network (or mining pool), and the others are just thrown away (not published). If it's not good enough, even the [not-so-]precious lowest hash isn't published - and certainly not the others. So, in the simulation, we only need to produce, for each second, a simulated "lowest hash for that 1 second". The "others" don't have to exist at all!

For reproducing (statistically) the pattern of hits and misses w.r.t. targets tough enough to not be achieving several hits within 1 second, and for h>>1, we can take the simulated lowest hash for time t to be (1/h) * HASH(signatures-of-the-act-of-burning-the-b-BTC ++ RAND(t)). [In fact this even works for h<1, despite the rather surreal appearance of "lowest hashes" >1 every so often in that case - i.e. values outside the range that ''real'' lowest (or any other!) hashes can ever actually be: it turns out this surreal behaviour is just what's needed to degrade the probability of beating the target by just the right amount. Values >1 in effect represent "I didn't generate any hashes at all during this particular 1-second window".]

Two further subtleties. First of all, it turns out to be desirable to include the block number (chain height @ 1 per block) in the formula - just to keep the owners of simulated mining rigs "on their toes" and not be able to tell a week or so in advance when they'll be lucky. (This encourages them to run a continuous full node. Maybe that's not in fact that important.) So we take simulated-lowest-hash = (1/h) * HASH(signatures-of-the-act-of-burning-the-b-BTC ++ block-number-of-would-be-block ++ RAND(t)). (We should '''not''' include finer details of the block, to avoid "gaming" a la the hundred blocks business I mentioned earlier. - Or if I'm wrong about that, then OK, by all means mix in finer details of the block!)

Secondly, it turns out that to keep the burning process going forever, rather than a pulse of initial burning that no-one ever again wants to contribute further burning to, we should simulate one more property of real-world mining rigs: they break down! That is, we should demurrage away the strength of a simulated mining rig. (A plea to the reader: Don't be alarmed by the word "demurrage". This is '''burnt''' coins I'm talking about - they ''should'' be treated "harshly", in whatever style mimics real-world mining rigs to the required fidelity. Ordinary unburnt coins are not being demurraged! [Unless that's independently desirable as a policy matter, e.g. if it's felt that network strength can only be achieved via more revenue for miners than fees alone will ever provide.]) A real mining rig likely works at full tilt for a few years and then conks out. We ''could'' demurrage each burnt coin in that style - it abruptly expires E years after its creation - but I think a smooth exponential demurrage is nicer, i.e. its burnt value after y years is b'=b*exp(-y/E). Thus h = b'/c = (b/c)*exp(-y/E). [And 1/h = c/b' = (c/b)*exp(y/E).]

Taking these two further subtleties into account, we get the following formula:

simulated-lowest-hash(t) = (c/b)*exp([t - t_burning]/E) * HASH(signatures-of-the-act-of-burning-the-b-BTC ++ block-number-of-would-be-block ++ RAND(t)).

So there you have it! With this formula, life as a miner is spookily similar to the real proof-of-work case. You "buy a mining rig" - you burn coins, and that hits ''you'' in exactly the way sending off money to a chip supplier would have hit you, even though over the whole economy, no real resources have been expended - and you then hope that, by submitting lucky hashes to the network in the form of blocks, you can make more back in fees over time than you spent initially. If you don't keep connected to the network, you won't know what transactions are eligible for including in your next would-be block, and your next lucky hash will run to waste. Meanwhile, other people are "buying mining rigs" (burning coins) too, either freshly or to make up for the "wearing out" of their existing ones; and the network is adjusting its target hash value [reciprocal difficulty] to regulate the rate all this mining effort is producing blocks at, to some preferred average rate. All spookily normal, in other words!

Now, I'm being a little bit disingenuous to say that ''everything'' is normal. We need protection against certain things (use of a lucky hash on two or more competing chains; timestamp-falsification abuse) which either do not exist at all under true proof-of-work - the former - or exist but with the consequences and mitigation strategy being different in detail - the latter. I believe I have a way of standing up to the various forms of malice we need to worry about of those kinds. More to follow soon hopefully!

=== Economic implications ===

The key insight is that verifiably, publicly burning some coins of a known-total-stock-issued currency is the same as "remurrage" (opposite of "demurrage" - it may not be a correct word, but it's a nice back-formation) on the remainder. That is, if there are verifiably 21 million issued-and-not-burned coins, and then you go to sleep and wake up later and there are now only 20 million issued-and-not-burned coins, that's the same as if some magic genie multiplied all wake-up-time nominal bitcoin figures by 21/20. Another way to see the identity of real effect would be to redefine "burning n bitcoins" to mean, not "sending n to an unspendable address", but rather "scattering" the n bitcoins, i.e. sending them to '''every existing''' [non-zero-balance] address, in proportion to the balance [sum of unspent txouts] already stored in each. This would be a horribly gigantic transaction to actually do explicitly, but the point is, burning can be thought of "as if" done that way. (Slogan: Quantity-deflation is remurrage in disguise, in exactly the same way that quantity-inflation is demurrage in disguise.)

So, what ''that'' means is, if while you're sleeping you (a non-miner) hold 1 bitcoin purely passively, i.e. it just sits undisturbed on the blockchain, well, when you wake up, it's as if you've received a "dividend" (of 5% in the particular numeric example above) on top of the general economy-tracking price we expect of a constant-quantity currency. In a world with actual, visibly performed remurrage, this is made explicit - your balance is now 21/20, with the nominal circulation [issued-and-not-burned, and remurraged for good measure] constant at 21 million. You can go and spend the 1/20 "dividend" on some treat, and still have the same fraction (1 out of 21 million) of the money stock as when you went to sleep.

In a world ''without'' any attempt at explicit remurrage, the real facts of the situation are (of course!) the same, but their nominal expression is not perhaps so instantly obvious. Your nominal holding is unchanged at 1; but this is now 1 part in 20 million of the whole money stock, not the 1 part in 21 million it was before. So, you can go and spend 1/21 of it on some treat, taking your nominal balance down to 20/21, and ''that'' nominal balance is the same (1 out of 21 million) fraction of the money stock as when you went to sleep.

So, basically, if you're holding bitcoins and trying to hold an "economy-tracking amount", no more and no less, you find you can go out into the market and use the fraction of your holdings that counts as "dividend above and beyond economy-tracking" on some treat or other. (Indeed, "you can go out..." should read "you ''must'' go out...", if you're really determined to pursue precisely that tracking strategy.)

Who's selling you the real resources embodied in the "treat"? And what's ''their'' motive? Well, transaction fee payers presumably like to re-stock their bitcoin real balances to roughly the same [economy-tracking] level as before, on average - they're paying for the transaction processing as a service. These fees are then burned by miners. (Well, not literally the fees themselves - the fees themselves are ''collected'' by miners, but the way they achieve this is to burn an approximately equal amount, as explained earlier.) So, ordinary Bitcoin users, to achieve their desired re-stocking, have to either produce slightly more, or consume slightly less, or a proper or improper mixture thereof, than they would have needed to in a hypothetical (presumably impracticable) alternative world where they pay no fees for their everyday transactions (and some magic mining-god just altruistically and reliably creates a blockchain out of all the transactions, without charging anybody anything). [This follows directly from their re-stocking desire, and has nothing to do with proof-of-burn specifically. That is, they have to do this regardless of whether the protocol is proof-of-work, proof-of-stake, proof-of-burn or whatever.] It's that extra gap between production and consumption - "extra" on top of whatever gap people are already choosing as a real saving[/dis-saving] strategy - that goes on to the market, for you and all other bitcoin holders to bid off the market by spending on your "treat".

This whole stable pattern of spending habits is, perhaps surprisingly, the same pattern of real resource allocation as would have happened if Cunicula's proof of stake (with close to 100% stake / 0% work admixture) had been in operation, and all bitcoin holders, large and small, had enthusiastically thrown their bitcoins (that is, their stream of bitcoin days destroyed) into the stake-claiming process. The fraction of fees they'd collect if they did that would be just like the "dividend" as I called it above - it would be like explicit remurrage, except instead of being automatic, it would require each holder's active participation (i.e. they couldn't just go to sleep, unless they left some sort of "trusted bot" running and using their private keys to sign their stream of bitcoin days destroyed). So, if you like, proof-of-burn is like automated, 100%-stakeholder-participation Cunicula-style proof-of-stake!

Incidentally, it's also fascinating to consider what happens if the community does decide a demurraging of [ordinary, unburnt] coins, the revenue being added as a coin-[re-]minting stream to the flow of fees, ''is'' necessary to continue with forever, for the sake of network strength. The amazing answer, as far as I can honestly work out, is that in long-run equilibrium, the burn rate is just such as '''to make hardly any of this demurrage ''real'' demurrage at all!''' [The implicit remurrage of burning almost exactly cancels the explicit demurrage of network-strengthening coin-[re-]minting! (Or if you like, the implicit demurrage of inflationary fresh-coin-minting.) Either way, we ''seem'' to get the possibility of amazing network strength "for free"!] This opens up the shocking possibility of turning up the demurrage/inflation rate to startlingly high levels - 5% of money stock / year, 10% of money stock / year... levels that would bring the whole cryptocurrency into disrepute in the true proof-of-work case, since coin-holders really would suffer that actual amount of explicit or implicit demurrage - and yet '''not''' hitting coin-holders with more than a frictional residual fraction of that ''in real terms'' at all, because of the way burning simulates remurrage! Extraordinary stuff! I plan to say more about this soon - but this quick teaser description should already be food for thought.

=== Coin-burning as a tool for transition between cryptocurrencies ===

Proof of burn may also be of interest as a tool for managing an orderly transition from one cryptocurrency ("oldcoin", let's call it) to another ("newcoin"). If the developers of newcoin are looking for a way of avoiding proof-of-work's real resource consumption '''even in newcoin's initial distribution phase''', they can't use proof of newcoin-burn: newcoins don't exist yet. But they ''can'' use proof of oldcoin-burn! (Assuming their reason for creating newcoin is '''not''' a doubting of oldcoin's security model, anyway. - Or at least, not a doubting severe enough to affect sufficiently deeply buried oldcoins, these being the candidates for burning.)

The newcoin blockchain would thus start with (at least a hash referring to) a complete catalogue of all the [sufficiently deeply buried] unspent txouts of oldcoin. Miners would then exhibit burning events within oldcoin up to a certain date; after which, the protocol would switch to burning of newcoin itself (and the dependency on oldcoin could even be thrown away entirely, if a checkpoint of that transition moment was promulgated and accepted by the newcoin community).

This has the nice consequence that, if people throughout the broader economy are gradually deserting oldcoin (as newcoin catches on), '''''its value need not collapse!''''' Instead, oldcoin gets burnt in the transition process, neatly reducing its nominal supply in just such a way as to roughly keep pace with its declining real demand. Meanwhile, those same acts of burning are minting fresh newcoins, at just the pace required to keep up with newcoin's ''growing'' real demand. (At least, that's the case if miners anticipate the transition speed correctly, and enter / exit the coins' respective mining trades at a pace that competes away supra-normal profits. We also have to assume that the ''total'' real demand for both[/all...] cryptocurrencies is roughly stable in "economy-tracking" terms; or at least, that miners anticipate the time path of the size of total real demand, and of its currency-by-currency composition, correctly, or near enough correctly.)

'''To sum up:''' proof of burn ''could'', just maybe, qualify as a new tool to greatly assist overall (multi-cryptocurrency) economic robustness and stability!

== Earlier work suggesting a role for the burning of coins ==

[https://bitcointalk.org/index.php?topic=131139.msg1404195#msg1404195 Forum member ripper234 points out] an earlier work by forum member [https://bitcointalk.org/index.php?action=profile;u=3313 dacoinminster] suggesting coins could be burnt as one component of a broader protocol. [https://bitcointalk.org/index.php?topic=56901.0 The earlier work] is [http://bitcoin.stackexchange.com/questions/2458/is-dacoinminsters-second-bitcoin-whitepaper-logically-economically-consistent discussed on StackExchange]. It revolves around a centralised "trusted entity" system, and so is not directly comparable to decentralised proof-of-burn mining; but it may be of interest to some readers.

== See also ==
*[[Proof_of_work|Proof of work]]
*[[Proof_of_Stake|Proof of stake]]

[[category:mining]]

Proof of burn

2014-03-25T06:26:26Z

Eldentyrell:

'''Proof of burn''' is a potential alternative to [[Proof_of_work|proof of work]] and [[Proof_of_Stake|proof of stake]] as a "scarce resource" to be exhibited by miners competing for the stream of rewards (minted coins and transaction fees) which a cryptocurrency's design makes available. The idea is that miners should show proof that they ''burned'' some coins - that is, sent them to a verifiably unspendable address. This is expensive from their individual point of view, just like proof of work; but unlike proof of work, it consumes no real resources from a whole economy perspective. This has interesting implications, discussed below.

There are likely many possible variants of proof of burn. This page currently describes [[User:Ids|Iain Stewart]]'s version. Other people can add variant versions that still belong to the broad proof of burn idea.

== Iain Stewart's version of proof of burn ==

=== Introduction and motivation ===

The key idea of proof-of-burn (this would also apply to proof-of-stake, by the way) is that when choosing the thing which is to qualify as a "difficulty", i.e. to require miners to exhibit proof that they've "done something that's tough to do", all that matters is that ''an individual miner'' finds the task expensive. (Well... it also matters that everyone else should find it cheap to verify that it has been done.) It doesn't need to be the case that real resources are consumed in the real economy.

With proof-of-work, it so happens that real resources are indeed consumed - mining rigs are produced, with human labour and materials as input, electricity is used, and all these things have to be bid away from their real-economy best alternative uses. (Or, if they're produced ''in addition'' to what would have been produced, the total of leisure time is less than it could have been. Something real is grabbed as input.) And while a cryptocurrency is being set up (i.e. [the fast early phase of] its initial distribution) - or, more precisely, while ''the first'' cryptocurrency is being set up; more on this distinction later! - no good alternative has been proposed. (And I'm not proposing one.) But once a cryptocurrency is up and running, with its initial distribution close to completed, new possibilities arise, for tasks to "feel expensive" to a miner but not actually "be expensive" from a god-like whole-economy perspective.

Proof-of-stake (of the "Cunicula variety", I mean) is in fact arguably already an example of such a task. It feels awfully expensive, to a miner, to save up a lot of bitcoins and become a big stakeholder; but from a whole-economy viewpoint, this is a swapping of assets' ownership labels around, it's not a burning of electricity or the like. However, I thought it would be interesting to invent a task that is absolutely, nakedly, unambiguously an example of the contrast between the two viewpoints. And yes, there is one: burning the currency!

By "burning" a tranche of bitcoins I just mean sending them to an address which is unspendable. The precise technical details of this will vary from cryptocurrency to cryptocurrency. With Bitcoin, any address which is [the RIPEMD160/SHA256 hash of] a script that evaluates to false will do. So, the script should do a "deliberately silly" thing - instead of things like "check such-and-such signature, and put the validity result on the stack", it should do something like "add 2 and 2, and now check if what's on top of the stack is equal to 5". (Or just "push 4, and check if it's equal to 5". Anything of that sort.) There are thus an unbounded number of such scripts, with entropy saturating RIPEMD160 since you can choose big numbers to taste. So, bitcoins sent to such a txout can never be redeemed on a future txin. (Barring the cracking of RIPEMD160 and the finding of an alternative matching script, that is. If ''that'' happens, the cryptocurrency is in big trouble anyway!)

With this definition of burning, it's not obvious to blockchain-watchers that some bitcoins ''have'' been burnt, at the time of burning. They've been sent to an address which doesn't stand out from any other. It's only later, when a miner who burned them earlier now wants to exhibit proof that "yes, these coins are burnt", that blockchain-watchers get their proof. (Which basically consists of exhibiting the script that manifestly always evaluates to false, and hashes to the address.) If it's thought desirable that the act of burning should be obvious right away, rather than later, then this can be achieved: burning merely needs to be defined as sending to some ''fixed'' unspendable address, with no variation - e.g. we could settle on the hash of "push 4, and check if it's equal to 5".

So, miners are creating candidate winning blocks by saying to the listening world, not "Look! I've done this many trillion hashes! [or struck lucky with fewer: you, the listening world, wouldn't know the difference... but this doesn't matter...]", but rather "Look! Two months ago I burned this many bitcoins!". In both cases, "this many" means an adjustable difficulty parameter, which the network adjusts from time to time (fortnightly, in today's Bitcoin) to squeeze out marginal miners (and keep more-efficient-than-marginal ones in profit) to just the extent needed to regulate block creation to a preferred pace (one per 10 minutes, in today's Bitcoin).

Why that phrase "Two months ago"? The broad principle is as follows. A miner mustn't be able to just burn some bitcoins ''right now'' and say "OK, I've burned them! Now let me have all those latest juicy transaction fees that have arrived in the past few minutes! Thanks!" That extremely recent act of burning could be undone in a block chain reorganisation; and then the same miner would be able to "re-burn" those same coins in an attempt to grab a block afresh, post-reorganisation. That would constitute a breakdown in the analogy of burning with proof-of-work hashing. A trillion proof-of-work hashes on a pre-reorg block are of no value on the post-reorg chain. A proof-of-work miner must simply shrug and say "Oh well, that's those expenses [electricity, mining rig rental / imputed rental,...] lost and gone... time to try again!" And that's the way things should be, for security - it '''should not''' be as cheap to extend the height of two or more competing chains as it is to focus on one. (And having decided to focus on one, a miner ''should'' incur a risk of lost expense if their choice turns out to be "the wrong one" in network consensus terms.)

The above point makes it clear why the act of burning should be a decent interval earlier than the act of exhibiting proof. Two months may be overdoing it, but the protocol should require it to be sufficiently far back that there's no practical possibility of it being undone. There are in fact some further issues, to do with making sure it's not cheap for a miner to ''re-exhibit'' their proof (of having performed a suitably substantial burn a suitably long time ago) on multiple competing chains. Details to follow.

Now then! How much burning will actually happen, under this protocol? The answer is straightforward enough, though its implications are quite broad and in some ways surprising. Miners will burn bitcoins at an average rate '''very close to''' the average rate that ordinary users are sending them fees (and any coin-minting still going on too of course), minus the miners' true real-resource costs (i.e. the hardware and electricity and the like for handling transactions and blocks and burn proofs - these costs will be far lower than the hashing costs incurred under proof-of-work, but of course still non-zero). This follows by the same sort of "approach to equilibrium" reasoning that tells us that miners will ''expend real resources on proof-of-work'' to roughly that extent - if they didn't, mining would be supra-normally profitable, and new entrants would be attracted into the trade. If burning coins, rather than buying a lot of kit from a mining rig supplier, is the expense incurred by a miner to compete for the revenue stream, the same economic principles apply.

=== Technical sketch of proof of burn: "Burnt coins are mining rigs!" ===

''Iain Stewart writes:'' In this subsection I give a provisional technical sketch of the operational details of the proof-of-burn protocol I've currently settled on. It can be summed up in the following pithy slogan:

'''''"Burnt coins are mining rigs!"'''''

What that slogan means will become clear as I go on. Basically, proof-of-work is so elegant, in so many different ways, excepting its high real-resource cost, that I decided my attempt at an alternative to it, avoiding its real-resource cost, should mimic it as faithfully as possible in every other aspect. Well, only readers can judge whether I've succeeded!

The key is to use a '''stream of true randomness''' - see below for where ''that'' comes from! - to simulate the generating of random hashes that a real proof-of-work mining rig would produce. Now, obviously we don't want to "simulate" every actual hash! A "simulation" of proof-of-work at ''that'' level of detail would just ''be'' proof-of-work! Rather, we want to mimic the statistical properties of a mining rig's stream of hashes, to just the level of detail required to give the same sort of pattern of meeting / not meeting a moving difficulty target, and all the rest of it, that we get with the real thing.

So: first of all, what exactly is my "stream of true randomness"? Chop up time into units considerably shorter than the intended inter-block time, but with no need to go much finer than general network latency. (Seconds will do, I think.) For each second, t, we need a uniform random number between 0 and 1 assigned to it, RAND(t). This sounds as if we need some awful dependency on a fragile central source - some high-powered laser at NASA pouring out quantum noise every second, or something - with all the trust and failure issues that would imply. Fortunately, for simulating mining rigs, we don't need anything like that. All that matters is that, to someone "buying a simulated mining rig" (burning some bitcoins, that is!) at time t, they can't predict the value of RAND(any t' 2 months or more to the future of t). [Where "2 months" means the dead time a burnt coin must wait before it becomes a simulated active mining rig. See introductory motivating section above. It's basically just a generous waiting period to make sure a burnt coin is truly definitely burnt, and won't have any chance of being "unburnt" in a chain reorg, by the time it comes into use in mining.] We do '''not''' need fresh statistical independence of RAND(t) w.r.t. all of RAND(t-1), RAND(t-2), RAND(t-3), etc. (And we don't mind if the stream is known a "short" time into the future - e.g. a week or two; at any rate a small portion of the waiting period.)

Such a lesser goal can, I believe, be achieved with just a few tens of bits of true randomness per week. Quality is what matters, not quantity! I suggest tapping into the world's most highly-audited source of low-bit-rate true randomness: lotteries. These (the big reputable ones anyway) are already subject to elaborate inspection of the machinery that tosses the balls around and draws some of them out. And the results are publicised so widely, in so many newspapers, TV channels, websites etc, as to make it impossible for anyone to lie about them.

Roughly weekly, a config-file (lottery-results.dat or whatever) should get "the latest lottery results" appended to it. There is no hurry about this, it doesn't need to be exactly every week, or even the same lottery every time, it just needs several tens of bits of fresh lottery data added roughly weekly. I believe there would be no trouble propagating this to all nodes, by out-of-band means if necessary. The format should be utterly simple and transparent, a 1-line plain text description of the results and the timestamp (t in RAND(t)) from which they are to be paid attention to, onwards. Like this:

.
.
.
for use from 2013-06-24 00:00:00 onwards: UK national lottery 2013-06-12: 4 9 20 22 37 42, bonus ball 19
for use from 2013-07-01 00:00:00 onwards: UK national lottery 2013-06-19: 7 12 14 19 33 41, bonus ball 28

(Obviously the meta-level words "for use from... onwards" aren't really needed - I just put them in for clarity.) Each line is added in a leisurely, unhurried fashion, at some time (it doesn't matter when) between the draw and the intended start-paying-attention-to-it date. (Some time between 2013-06-19 and 2013-07-01 00:00:00, in the case of the example last line above.) This gives plenty of time for people to add it themselves, from their favourite news source, and check by out-of-band means that they've added what everybody else has added, right down to spelling and punctuation. (Which in practice probably means copying it from somewhere. The point is, the "somewhere" doesn't need to be trusted - a lie, or an unexpected variation in format or spelling or punctuation, would be called out well within the leisurely timescale.)

RAND(t) is then HASH(config-file [excluding any lines that are "for use from ''time later than t'' onwards" of course], plus t itself [in some standard format, e.g. 2013-07-02 23:14:05, or just the Unix numeric time] as a final line). - Or if you like, HASH(HASH(config-file) ++ t), for efficiency. (Where "++" means "append together in some standard fashion".) "HASH()" is your favourite hash function, e.g. SHA256(SHA256()). Thus RAND(t) is a 256-bit integer, which we regard conceptually as a real number between 0 and 1 by putting a binary point in front.

(I'm aware that people on the forums are coming up with randomness protocols for proof-of-stake, proof-of-activity and the like which ''don't'' involve external true randomness like lotteries - they just hash the last hundred blocks' hashes together, or something like that. I don't think this is good enough. [For their application or for mine!] Someone producing the latest block, given the previous 99, can privately produce billions of cheap variations on it, by varying the order the transactions are listed etc, until they find, and publish, the one that "games" the randomness in their favour. However, if I'm wrong about this, and hashing the last hundred blocks is in fact fine, then good! We can drop the lottery rigmarole! Anyway, for the rest of this description, I'll simply assume that RAND(t) becomes available for all t, but remains unknown until a week or two before t, and in particular, RAND(2 months or more from now) is "massively unknown" right now - unknown with many tens to hundreds of bits of unknowable future entropy. That's all that matters for turning burnt coins into simulated mining rigs.)

Right then! What do we do with this RAND(t) stream? We simulate the capricious behaviour of a true proof-of-work mining rig! Let us assume that, in the real proof-of-work world, you can buy an h hashes/second mining rig for b=c*h BTC. (c varies with technical progress, BTC price fluctuations, etc; but in the simulated world it can just be left constant.) Or, inverting this, if you spend b BTC, you acquire a mining rig of h=b/c hashes/s power. Now, what does it actually mean for your rig to perform h hashes during 1 second? It means you're producing h uniform random numbers between 0 and 1. (That binary point again!) But you don't really care what they all are individually - how well you did during that 1 second is defined as "what was the '''lowest''' hash value you produced during that 1 second?". This is then inspected for whether it beats [is lower than] the network's current target; or, perhaps, whether it beats the lesser [i.e. numerically greater] target of a pooled mining operation. If it's good enough, that precious lowest hash is published to the network (or mining pool), and the others are just thrown away (not published). If it's not good enough, even the [not-so-]precious lowest hash isn't published - and certainly not the others. So, in the simulation, we only need to produce, for each second, a simulated "lowest hash for that 1 second". The "others" don't have to exist at all!

For reproducing (statistically) the pattern of hits and misses w.r.t. targets tough enough to not be achieving several hits within 1 second, and for h>>1, we can take the simulated lowest hash for time t to be (1/h) * HASH(signatures-of-the-act-of-burning-the-b-BTC ++ RAND(t)). [In fact this even works for h<1, despite the rather surreal appearance of "lowest hashes" >1 every so often in that case - i.e. values outside the range that ''real'' lowest (or any other!) hashes can ever actually be: it turns out this surreal behaviour is just what's needed to degrade the probability of beating the target by just the right amount. Values >1 in effect represent "I didn't generate any hashes at all during this particular 1-second window".]

Two further subtleties. First of all, it turns out to be desirable to include the block number (chain height @ 1 per block) in the formula - just to keep the owners of simulated mining rigs "on their toes" and not be able to tell a week or so in advance when they'll be lucky. (This encourages them to run a continuous full node. Maybe that's not in fact that important.) So we take simulated-lowest-hash = (1/h) * HASH(signatures-of-the-act-of-burning-the-b-BTC ++ block-number-of-would-be-block ++ RAND(t)). (We should '''not''' include finer details of the block, to avoid "gaming" a la the hundred blocks business I mentioned earlier. - Or if I'm wrong about that, then OK, by all means mix in finer details of the block!)

Secondly, it turns out that to keep the burning process going forever, rather than a pulse of initial burning that no-one ever again wants to contribute further burning to, we should simulate one more property of real-world mining rigs: they break down! That is, we should demurrage away the strength of a simulated mining rig. (A plea to the reader: Don't be alarmed by the word "demurrage". This is '''burnt''' coins I'm talking about - they ''should'' be treated "harshly", in whatever style mimics real-world mining rigs to the required fidelity. Ordinary unburnt coins are not being demurraged! [Unless that's independently desirable as a policy matter, e.g. if it's felt that network strength can only be achieved via more revenue for miners than fees alone will ever provide.]) A real mining rig likely works at full tilt for a few years and then conks out. We ''could'' demurrage each burnt coin in that style - it abruptly expires E years after its creation - but I think a smooth exponential demurrage is nicer, i.e. its burnt value after y years is b'=b*exp(-y/E). Thus h = b'/c = (b/c)*exp(-y/E). [And 1/h = c/b' = (c/b)*exp(y/E).]

Taking these two further subtleties into account, we get the following formula:

simulated-lowest-hash(t) = (c/b)*exp([t - t_burning]/E) * HASH(signatures-of-the-act-of-burning-the-b-BTC ++ block-number-of-would-be-block ++ RAND(t)).

So there you have it! With this formula, life as a miner is spookily similar to the real proof-of-work case. You "buy a mining rig" - you burn coins, and that hits ''you'' in exactly the way sending off money to a chip supplier would have hit you, even though over the whole economy, no real resources have been expended - and you then hope that, by submitting lucky hashes to the network in the form of blocks, you can make more back in fees over time than you spent initially. If you don't keep connected to the network, you won't know what transactions are eligible for including in your next would-be block, and your next lucky hash will run to waste. Meanwhile, other people are "buying mining rigs" (burning coins) too, either freshly or to make up for the "wearing out" of their existing ones; and the network is adjusting its target hash value [reciprocal difficulty] to regulate the rate all this mining effort is producing blocks at, to some preferred average rate. All spookily normal, in other words!

Now, I'm being a little bit disingenuous to say that ''everything'' is normal. We need protection against certain things (use of a lucky hash on two or more competing chains; timestamp-falsification abuse) which either do not exist at all under true proof-of-work - the former - or exist but with the consequences and mitigation strategy being different in detail - the latter. I believe I have a way of standing up to the various forms of malice we need to worry about of those kinds. More to follow soon hopefully!

=== Economic implications ===

The key insight is that verifiably, publicly burning some coins of a known-total-stock-issued currency is the same as "remurrage" (opposite of "demurrage" - it may not be a correct word, but it's a nice back-formation) on the remainder. That is, if there are verifiably 21 million issued-and-not-burned coins, and then you go to sleep and wake up later and there are now only 20 million issued-and-not-burned coins, that's the same as if some magic genie multiplied all wake-up-time nominal bitcoin figures by 21/20. Another way to see the identity of real effect would be to redefine "burning n bitcoins" to mean, not "sending n to an unspendable address", but rather "scattering" the n bitcoins, i.e. sending them to '''every existing''' [non-zero-balance] address, in proportion to the balance [sum of unspent txouts] already stored in each. This would be a horribly gigantic transaction to actually do explicitly, but the point is, burning can be thought of "as if" done that way. (Slogan: Quantity-deflation is remurrage in disguise, in exactly the same way that quantity-inflation is demurrage in disguise.)

So, what ''that'' means is, if while you're sleeping you (a non-miner) hold 1 bitcoin purely passively, i.e. it just sits undisturbed on the blockchain, well, when you wake up, it's as if you've received a "dividend" (of 5% in the particular numeric example above) on top of the general economy-tracking price we expect of a constant-quantity currency. In a world with actual, visibly performed remurrage, this is made explicit - your balance is now 21/20, with the nominal circulation [issued-and-not-burned, and remurraged for good measure] constant at 21 million. You can go and spend the 1/20 "dividend" on some treat, and still have the same fraction (1 out of 21 million) of the money stock as when you went to sleep.

In a world ''without'' any attempt at explicit remurrage, the real facts of the situation are (of course!) the same, but their nominal expression is not perhaps so instantly obvious. Your nominal holding is unchanged at 1; but this is now 1 part in 20 million of the whole money stock, not the 1 part in 21 million it was before. So, you can go and spend 1/21 of it on some treat, taking your nominal balance down to 20/21, and ''that'' nominal balance is the same (1 out of 21 million) fraction of the money stock as when you went to sleep.

So, basically, if you're holding bitcoins and trying to hold an "economy-tracking amount", no more and no less, you find you can go out into the market and use the fraction of your holdings that counts as "dividend above and beyond economy-tracking" on some treat or other. (Indeed, "you can go out..." should read "you ''must'' go out...", if you're really determined to pursue precisely that tracking strategy.)

Who's selling you the real resources embodied in the "treat"? And what's ''their'' motive? Well, transaction fee payers presumably like to re-stock their bitcoin real balances to roughly the same [economy-tracking] level as before, on average - they're paying for the transaction processing as a service. These fees are then burned by miners. (Well, not literally the fees themselves - the fees themselves are ''collected'' by miners, but the way they achieve this is to burn an approximately equal amount, as explained earlier.) So, ordinary Bitcoin users, to achieve their desired re-stocking, have to either produce slightly more, or consume slightly less, or a proper or improper mixture thereof, than they would have needed to in a hypothetical (presumably impracticable) alternative world where they pay no fees for their everyday transactions (and some magic mining-god just altruistically and reliably creates a blockchain out of all the transactions, without charging anybody anything). [This follows directly from their re-stocking desire, and has nothing to do with proof-of-burn specifically. That is, they have to do this regardless of whether the protocol is proof-of-work, proof-of-stake, proof-of-burn or whatever.] It's that extra gap between production and consumption - "extra" on top of whatever gap people are already choosing as a real saving[/dis-saving] strategy - that goes on to the market, for you and all other bitcoin holders to bid off the market by spending on your "treat".

This whole stable pattern of spending habits is, perhaps surprisingly, the same pattern of real resource allocation as would have happened if Cunicula's proof of stake (with close to 100% stake / 0% work admixture) had been in operation, and all bitcoin holders, large and small, had enthusiastically thrown their bitcoins (that is, their stream of bitcoin days destroyed) into the stake-claiming process. The fraction of fees they'd collect if they did that would be just like the "dividend" as I called it above - it would be like explicit remurrage, except instead of being automatic, it would require each holder's active participation (i.e. they couldn't just go to sleep, unless they left some sort of "trusted bot" running and using their private keys to sign their stream of bitcoin days destroyed). So, if you like, proof-of-burn is like automated, 100%-stakeholder-participation Cunicula-style proof-of-stake!

Incidentally, it's also fascinating to consider what happens if the community does decide a demurraging of [ordinary, unburnt] coins, the revenue being added as a coin-[re-]minting stream to the flow of fees, ''is'' necessary to continue with forever, for the sake of network strength. The amazing answer, as far as I can honestly work out, is that in long-run equilibrium, the burn rate is just such as '''to make hardly any of this demurrage ''real'' demurrage at all!''' [The implicit remurrage of burning almost exactly cancels the explicit demurrage of network-strengthening coin-[re-]minting! (Or if you like, the implicit demurrage of inflationary fresh-coin-minting.) Either way, we ''seem'' to get the possibility of amazing network strength "for free"!] This opens up the shocking possibility of turning up the demurrage/inflation rate to startlingly high levels - 5% of money stock / year, 10% of money stock / year... levels that would bring the whole cryptocurrency into disrepute in the true proof-of-work case, since coin-holders really would suffer that actual amount of explicit or implicit demurrage - and yet '''not''' hitting coin-holders with more than a frictional residual fraction of that ''in real terms'' at all, because of the way burning simulates remurrage! Extraordinary stuff! I plan to say more about this soon - but this quick teaser description should already be food for thought.

=== Coin-burning as a tool for transition between cryptocurrencies ===

Proof of burn may also be of interest as a tool for managing an orderly transition from one cryptocurrency ("oldcoin", let's call it) to another ("newcoin"). If the developers of newcoin are looking for a way of avoiding proof-of-work's real resource consumption '''even in newcoin's initial distribution phase''', they can't use proof of newcoin-burn: newcoins don't exist yet. But they ''can'' use proof of oldcoin-burn! (Assuming their reason for creating newcoin is '''not''' a doubting of oldcoin's security model, anyway. - Or at least, not a doubting severe enough to affect sufficiently deeply buried oldcoins, these being the candidates for burning.)

The newcoin blockchain would thus start with (at least a hash referring to) a complete catalogue of all the [sufficiently deeply buried] unspent txouts of oldcoin. Miners would then exhibit burning events within oldcoin up to a certain date; after which, the protocol would switch to burning of newcoin itself (and the dependency on oldcoin could even be thrown away entirely, if a checkpoint of that transition moment was promulgated and accepted by the newcoin community).

This has the nice consequence that, if people throughout the broader economy are gradually deserting oldcoin (as newcoin catches on), '''''its value need not collapse!''''' Instead, oldcoin gets burnt in the transition process, neatly reducing its nominal supply in just such a way as to roughly keep pace with its declining real demand. Meanwhile, those same acts of burning are minting fresh newcoins, at just the pace required to keep up with newcoin's ''growing'' real demand. (At least, that's the case if miners anticipate the transition speed correctly, and enter / exit the coins' respective mining trades at a pace that competes away supra-normal profits. We also have to assume that the ''total'' real demand for both[/all...] cryptocurrencies is roughly stable in "economy-tracking" terms; or at least, that miners anticipate the time path of the size of total real demand, and of its currency-by-currency composition, correctly, or near enough correctly.)

'''To sum up:''' proof of burn ''could'', just maybe, qualify as a new tool to greatly assist overall (multi-cryptocurrency) economic robustness and stability!

== Earlier work suggesting a role for the burning of coins ==

[https://bitcointalk.org/index.php?topic=131139.msg1404195#msg1404195 Forum member ripper234 points out] an earlier work by forum member [https://bitcointalk.org/index.php?action=profile;u=3313 dacoinminster] suggesting coins could be burnt as one component of a broader protocol. [https://bitcointalk.org/index.php?topic=56901.0 The earlier work] is [http://bitcoin.stackexchange.com/questions/2458/is-dacoinminsters-second-bitcoin-whitepaper-logically-economically-consistent discussed on StackExchange]. It revolves around a centralised "trusted entity" system, and so is not directly comparable to decentralised proof-of-burn mining; but it may be of interest to some readers.

== See also ==
*[[Proof_of_work|Proof of work]]
*[[Proof_of_Stake|Proof of stake]]

[[category:mining]]

Proof of Stake

2014-03-25T06:26:07Z

Eldentyrell: the tradgedy-of-the-commons issue only comes up if block incentives decline over time

Proof of Stake is a proposed alternative to [[Proof of Work]]. Like proof of work, proof of stake provides a mechanism for determining who signs bitcoin transactions (see [https://bitcointalk.org/index.php?topic=68213.0 "main" bitcointalk thread], and a [https://bitcointalk.org/index.php?topic=96854.0 Bounty Thread]).

It was probably first proposed [https://bitcointalk.org/index.php?topic=27787.0 here] by Quantum Mechanic. With Proof of Work, the probability of mining a block depends on the work done by the miner (e.g. CPU/GPU cycles spent checking hashes). With Proof of Stake, the resource that's compared is the amount of Bitcoin a miner holds - someone holding 1% of the Bitcoin can mine 1% of the "Proof of Stake blocks".

Some argue that methods based on Proof of Work alone might lead to a low network security in a cryptocurrency with block incentives that decline over time (like bitcoin) due to [[Tragedy of the Commons]], and Proof of Stake is one way of changing the miner's incentives in favor of higher network security.

= Motivation For Proof of Stake =

* A proof-of-stake system might provide increased protection from a malicious attack on the network. Additional protection comes from two sources:
1) Executing an attack would be much more expensive.
2) Reduced incentives for attack. The attacker would need to own a near majority of all bitcoin. Therefore, the attacker suffer severely from his own attack.

* When block rewards are produced through txn fees, a proof of stake system would result in lower equilibrium txn fees. Lower long-run fees would increase the competitiveness of bitcoin relative to alternative payments systems. Intuitively reduced fees are due to vast reductions in the scale of wastage of resources.
== The Monopoly Problem ==

If a single entity (hereafter a monopolist) took control of the majority of txn verification resources, he could use these resources to impose conditions on the rest of the network. Potentially, the monopolist could choose to do this in malicious ways, such as double spending or denying service. If the monopolist chose a malicious strategy and maintained his control for a long period, confidence in bitcoin would be undermined and bitcoin purchasing power would collapse. Alternatively, the monopolist could choose to act benevolently. A benevolent monopolist would exclude all other txn verifiers from fee collection and currency generation, but would not try to exploit currency holders in any way. In order to maintain a good reputation, he would refrain from double spends and maintain service provision. In this case, confidence in Bitcoin could be maintained under monopoly since all of its basic functionality would not be affected.

Both benevolent and malevolent monopoly are potentially profitable, so there are reasons to suspect that an entrepreneurial miner might attempt to become a monopolist at some point. Due to the [[Tragedy of the Commons]] effect, attempts at monopoly become increasingly likely over time.

== How Proof of Stake Addresses Monopoly Problems ==

Monopoly is still possible under proof-of-stake. However, proof-of-stake would be more secure against malicious attacks for two reasons.

Firstly, proof-of-stake makes establishing a verification monopoly more difficult. At the time of writing, an entrepreneur could achieve monopoly over proof-of-work by investing at most 10 million USD in computing hardware. The actual investment necessary might be less than this because other miners will exit as difficulty increases, but it is difficult to predict exactly how much exit will occur. If price remained constant in the face of extremely large purchases (unlikely), such an entrepreneur would need to invest at least 20 million USD to obtain monopoly under proof-of-stake. Since such a large purchase would dramatically increase bitcoin price, the entrepreneur would likely need to invest several times this amount. Thus, even now proof-of-stake monopoly would be several-fold more costly to achieve than proof-of-work monopoly. Over time the comparison of monopoly costs will become more and more dramatic. The ratio of bitcoin's mining rewards to market value is programmed to decline exponentially. As this happens, proof-of-work monopoly will become easier and easier to obtain, whereas obtaining proof-of-stake monopoly will become progressively more difficult as more of the total money supply is released into circulation.

Secondly, and perhaps more importantly, a proof-of-stake monopolist is more likely to behave benevolently exactly because of his stake in Bitcoin. In a benevolent monopoly, the currency txn continue as usual, but the monopolist earns all txn fees and coin generations. Other txn verifiers are shut out of the system, however. Since mining is not source of demand for bitcoin, bitcoin might retain most of its value in the event of a benevolent attack. Earnings from a benevolent attack are similar regardless of whether the attack occurs under proof-of-stake or proof-of-work. In a malicious attack, the attacker has some outside opportunity which allows profit from bitcoin's destruction (simple double-spends are not a plausible motivation; ownership of a competing payment platform is). At the same time, the attacker faces costs related to losses on bitcoin-specific investments which are necessary for the attack. It can be assumed that a malicious attack causes the purchasing power of bitcoin to fall to zero. Under such an attack, the proof-of-stake monopolist will lose his entire investment. By contrast, a malicious proof-of-work monopolist will be able to recover much of their hardware investment through resale. Recall also, that the necessary proof-of-work investment is much smaller than the proof-of-stake investment. Thus, the costs of a malicious attack are several-fold lower under proof-of-work. The low costs associated with malicious attack make a malicious attack more likely to occur.

== Why Proof of Stake Would Likely Decrease Long-run Txn Fees Considerably ==
In a competitive market equilibrium, the total volume of txn fees must be equal to opportunity cost of all resources used to verify txns. Under proof-of-work mining, opportunity cost can be calculated as the total sum spent on mining electricity, mining equipment depreciation, mining labor, and a market rate of return on mining capital. Electricity costs, returns on mining equipment, and equipment depreciation costs are likely to dominate here. If these costs are not substantial, then it will be exceptionally easy to monopolize the mining network. The fees necessary to prevent monopolization will be onerous, possibly in excess of the 3% fee currently charged for credit card purchases. Under pure proof-of-stake, opportunity cost can be calculated as the total sum spent on mining labor and the market interest rate for risk-free bitcoin lending (hardware-related costs will be negligible). Since bitcoins are designed to appreciate over time due to hard-coded supply limitations, interest rates on risk-free bitcoin-denominated loans are likely to be negligible. Therefore, the total volume of txn fees under pure proof-of-stake will just need to be just sufficient to compensate labor involved in maintaining bandwidth and storage space. The associated txn fees will be exceptionally low. Despite these exceptionally low fees, a proof-of-stake network will be many times more costly to exploit than the proof-of-work network. Approximately, a proof-of-work network can be exploited using expenditure equal to about one years worth of currency generation and txn fees. By contrast, exploitation of a proof-of-stake network requires purchase of a majority or near majority of all extant coins.

= Implementation =
There are currently a few distinct proposals on how to implement PoS

== Cunicula's Implementation of Mixed Proof-of-Work and Proof-of-Stake ==

This suggestion is of a mixed Proof-of-Work / Proof-of-Stake system.

=== Cunicula's Note ===
Check the page history for the older implementation. I am replacing my description with a new system which I believe to be much more secure. The new system is a greatly improved version of Colbee's proof of activity. It provides extremely strong protection against PoW attacks, both double-spends and denials of service. It is not vulnerable even if PoW attackers also have substantial (but non majority) stake. It provides strong incentives to maintain full nodes. The system is supported through taxes on coin owners who fail to maintain full nodes. Tax revenue is redistributed to coin owners who maintain full nodes. The maintenance of full nodes is the key element providing security in the system.

The discussion focuses on long-term maintenance of the system. Initial distribution of coins could occur through PoW mining, an IPO mechanism, or a more complex scheme that allows initial coins to be distributed to both PoW miners and businesses voted for by coin owners. The issue of initial distribution is separate from long-term maintenance and it is confusing to discuss the two together.

=== Glossary ===
Voluntary Signatures - Voluntary signatures result from a random auditing processes. As blocks are mined, keys are selected for auditing based on random selection. The signatures provide public evidence that a public key owner is running a full node. Passing the audit allows a private key to remain active.

Active Keys - By default, public keys that appear in the blockchain are active if they have a balance of at least one full coin. Public keys that provide voluntary signatures when randomly audited remain active. Active public keys are eligible to participate in lotteries to sign PoW blocks and mine PoS blocks. This is remunerative. Public keys that fail to provide signatures become dead private keys.

Dead Keys - Keys that have failed to provide signatures lose lottery eligibility. Keys that have balances of less than 1 coin are considered dead by default. Dead keys can no longer mine PoS blocks. However, these dead keys can still be used to generate txns. Network maintenance is supported primarily through mandatory fees levied on coins sent by dead keys. After coins are sent using a dead key, the key becomes active provided that it retains a balance of at least 1 coin.

Mandatory Signature Sequence - In order for a PoW block to be valid and enter the blockchain, it must be signed by a sequence of 5 randomly selected active keys. The fifth signatory in the sequence mines a PoS block.

PoS block - The fifth signatory of a PoW block must mint his own block without any PoW submission at all. This block is called a PoS block.

Coin-age - Coin age refers to the age of txn inputs. Coin age is equal to the number of coins sent times the average age on these coins. Age is measured in blocks. Age is reset to 1 block whenever a coin is sent AND whenever a coin provides a signature (both mandatory and voluntary signatures count). Coin-age is used to calculate mandatory fees.

Demurrage Fee - Chain Security is supported primarily through a demurrage tax on sent inputs. This tax proportional to average input age as measured in coin-years. I suggest 5% per coin-year as a reasonable fee. Active keys can avoid demurrage fees simply by remaining active. Thus the actual fee generation will be much lower than 5% per year. Dead keys must pay demurrage. The opportunity to evade demurrage motivates activity.

Optional Fee - Fees are used to ration block space. Blocks select prioritize txns with high fees. If demurrage fees alone are insufficient to motivate txn inclusion, the user can add an optional fee to his txn.

Fee Fund - Both optional fees and demurrage fees enter a fund, rather than being distributed directly to miners. Fees are added to the fund immediately, so there is a weak incentive to include high fee txns in blocks. The PoW miner receives a distribution equal to 0.01% of the accumulated fund. The first four mandatory signatories also receive 0.1% each. The PoS block miner receives 0.1% as well, but his takings will differ slightly because the fund is updated based on txns included in his block. Use of a fund reduces volatility in mining reward.

Root Private Key - The root private key has full spending and signing authority. When significant balances are held, this key should be kept as an offline backup to guard against theft.

Stake Signing Key - Private Key can delegate signing and sending authority to one other private key. The delegated key can sign blocks and has limited authority to send coins. Authority to send coins is determined by two positive constants, t and k. The following txn rule limits the stake signing keys' spending authority:

Change Returned to Public Key >= all coins sent to other addresses * {max(k,k*(t/coin-years on public key)}
k=9 and t=1/12 are suggested as possible parameters. These parameters allows the stake signing key to spend up to 10% of the total key balance per month. The max value at risk in event of theft of
this key is 10%. Holders of large balances 'zero-out' their coin-age frequently via mining and face less theft risk. If this occurs once per week, for example, the large balance holder will only
risk be able to spend up to 2.3% of their balance per week and will only lose 2.3% in the event of theft. Once theft is detected, all remaining coins can be moved to a secure computer using the
root private key.

=== Mining Process ===

1) Block meeting work difficulty target is mined. Difficulty target periodically adjusted so that 1 PoW block arrives every 10 minutes.

2) Work submission is hashed 10 times consecutively. Each consecutive hash maps to an individual unspent output in the blockchain. This is essentially a lottery drawing two sets of five winners. The first five hashes map to mandatory signatures, the final five hashses map to voluntary signatures.

3) If the mandatory signatures map to active public keys [see glossary], the block can potentially be valid. Otherwise, the block is invalid and must be discarded.

4) If PoW miner finds a potentially valid block, he transmits the following hash to the network: {work submission;hash(his block, the previous valid block)}

5) If the work submission meets the difficulty target and maps to active signatories, then the block is relayed through the network. Otherwise, the message is dropped as spam.

5) The first five selected signatories sequentially sign this hash and transmit it onwards as {work submission; hash; sig 1; sig 2; sig 3; sig 4; sig 5}

6) After the mandatory signature sequence is complete, the final signatory publishes the PoW block and also his own PoS block.

7) The final five hashes map to voluntary signatures. These voluntary signatures can be inserted into any block within the next 6 blocks as special txns. These txns do not require fees.

9) Go to step 1

Note: This process is simultaneous so that multiple block hashes can circulate in the network attempting to collect five signatures and generate PoW/PoS block pairs. Block pairs that lose this race
are orphaned.

=== Infeasability of standard attack vectors ===

Unless attackers own a large share of stake, all types of PoW attacks are computationally infeasible. I think there are two types of known attacks: 1) Double-Spend 2) Denial of Service
I consider approximations below. The numbers are so favorable that consideration of exact statistics is not particularly interesting.

1) Double Spend.

Double spends rely on secrecy. In order to mine blocks in secret a PoW miner must select his 5 of his own public keys in the lottery. If the PoW miner owns a share 0<s<1 of all coins,
the probability of doing that a block meeting the difficulty target will select the miner's coins is (1/s)^5. For s=0.01, 1 out of 10 billion blocks will satisfy this criteria.
Even for extremely small hash aggregate rates, it is not practical to privately mine at a rate 10 billion times faster than all other miners combined. For s=0.1, 1 out of 100,000 blocks will
satisfy this criteria. (i.e. the attack still requires approximately 99.999% of all hashing power). For s=0.5, the attacker will succeed if he controls 51% of the aggregate hash rate.

2) Denial of Service

An attacker who mines publicly could simply produce empty PoW blocks. However, this would fail to deny service. 50% of all blocks are randomly mined via PoS. The attacker cannot
force the PoS miners to produce empty blocks. Therefore he cannot deny service regardless of how much hash rate he controls.

=== Long-term Chain Evaluation ===
1) Comparison of two long chains is based on a simple sum of block difficulty, just as in bitcoin.

2) A criticism of PoS is that there is no reason not to sign attack chains. However, in a long secret chain, many stakeholders will have dead signatures. These dead stakeholders will not be able to sign the main chain, but not the attack chain. They will have a strong incentive to make sure the main chain wins because the attack chain will impose demurrage fees on them.

=== Incentives to maintain full nodes ===

This system introduces powerful incentives to maintain full nodes. Many people argue that the lack of an incentive to maintain a full node is a problem in the bitcoin system.

1) a steady flow of txns will generate some fees even if all public keys remain active. Active keys must be maintaining full nodes. Otherwise they could not provide the voluntary signatures which prove their activity. Even very weak incentives are sufficient in this case. If almost all keys are associated with active nodes, then it is not necessary to motivate additional participation.

2) Some public keys may decide to become inactive. This is costly for them. They will suffer a loss of 5% of their balance per year for as long as they remain inactive.

3) The active public keys constantly capture revenue from inactive public keys. This means that the incentives to remain increase dramatically as participation falls. Suppose that 50% of public keys maintain full nodes, then this 50% will capture 2.5% of coins per annum. This is equal to an annual of return of 2.0%. The alternative, inactivity, yields an annual return of -5.0% as discussed in point 2. I consider this a reasonable incentive level and participation rate. Suppose that I am wrong, and only 10% of public keys maintain full nodes. Then these 10% will capture 4.5% of all extant coins per annum. This implies an annual return on participation equal to 45% per annum. This is a very strong incentive and is almost certain to be sufficient, even if nodes are quite costly to maintain. If only 1% of coins participate, then 4.95% of all extant coins will be distributed to this 1% each year. This implies a weekly return on participation of 3%, a pirate ponzi scheme level return. If these incentive are inadequate to support a healthy network of full nodes (which seems unlikely to me), then the levy on dead coins could be increased to exceed 5% per annum.

4) Many people will not have enough coins to justify running their own node. Such individuals will likely use an online banking service which could store their limited spend key. The service could return interest to users in exchange for managing their keys.

5) Other individuals may prefer the privacy associated with dropping out of participation. These individuals are still welcome to use the network, but must face a wealth tax of 5% per annum to compensate for the security risk created by their behavior.

=== Storage of Blockchain Metadata ===
To facilitate the system, data should be extracted from the block chain in a readily accessible database that is updated with each block. The database only needs to incorporate
public keys which control at least 1 coin. Keys with balances less than 1 coin are considered dead by default. These low-value public keys
are not allowed to create limited stake public keys. If a public key balance drops below 1 coin, the limited stake public key associated with the root key is invalidated.

The database would look like this:

{| class="wikitable"
|-
! Public Key (ordered list) !! Linked Stake Public key (if any) !! Balance !! Cumulative Balance !! Active? !! Coin-age (in years)
|-
| A || As || 1 || 1 || 1 || 0.03
|-
| B || Bs || 2.5 || 3.5 || 0 || 0.1
|-
| C || Cs || 3 || 6.5 || 1 || 0.2
|-
| ... || ... || ... || ... || ... || ...
|}
The block chain must maintain records of links between public keys and delegated limited stake public keys. These should be put in a simple database for easy access.

Cumulative balance can be used to determine the winners of the lottery. (i.e. the lottery is a uniform draw on the support [0,total issued coins]) This indicates a unique lottery winner,
whose chance of winning is proportional to his ownership share.

Coin-age is updated as follows.
If no send, Coin-age_t = Coin-age_t-1 + 1.
If send, Coin_age_t = 1.
If send and receipt of coins, Coin_age_t = 1.
If receipt of coins but no send, Coin_age_t = [Coin_age_(t-1)*balance_(t-1)+received coins]/balance(t)

Coin-age is necessary to determine mandatory demurrage fees and to calculate spending limits for limited stake public keys.

Active is 1 by default and becomes 0 if a key fails to provide a requested voluntary signature. 0 is an absorbing state.

=== Beneficiaries and Lossers from Txn Fees ===
The total amount of demurrage fees collected annually varies between 0% and 5% of the total money supply.

The most burdensome fee in the system is the fee paid to PoW miners. This fee imposes a demurrage tax of between 0% and 0.1% per annum on all users of the system. In addition to the demurrage tax, PoW miners receive a 2% share of any optional fees paid to access scarce block space. All coin owners are net losers as a result of PoW mining fees. To minimize costs to coin owners, PoW fee payments are kept as low as possible. Since large hash rates play only a tiny role in security, larger fees for PoW miners are unnecessary.

Other demurrage fees are transfers of revenue from one private key to another. Some keys are net beneficiaries of these transfers, while other keys are net losers. Collectively, these fees do not make coin owners better or worse off. Their effects are neutral. However, individually, the fees do create winners and losers. ''Active'' users that spend infrequently gain from the system. An ''active'' user with average spend frequency is likely to gain from the system as well, but only by a small amount. An ''active'' user that spends very frequently will probably lose from the system. ''Dead'' users will certainly lose from the system. This loss serves as a punishment for failure to maintain an ''active'' node.

== Meni's implementation ==
This proposal is for a proof-of-work (PoW) skeleton on which occasional checkpoints set by stakeholders are placed. In one variant, double-spending is prevented by waiting for a transaction to be included in a checkpoint; the variant described here uses cementing to prevent double-spending, and checkpoints to resolve cementing conflicts.

=== Proof of work ===
Miners use their hashrate to find blocks and build the blockchain exactly as with the pure PoW system. They receive any new generated coins from the block; there will be two kinds of transaction fees, one of which is a mining fee given to the miner who finds the block, just like the PoW transaction fees.

=== Signatures ===
One block every 100 blocks (a different number can be used instead) is a signature block. When a signature block is found and confirmed with several subsequent blocks, stakeholders (people who have bitcoins) are expected to sign it by using a private key associated with their address which contains coins to sign the block hash. If there are several blocks of the same height, an address should not sign more than one of them. The signatures are broadcast on the network and included in a future block. For every candidate block, the total weight of all signatures is tallied (the weight of an address is determined mostly by the number of coins in it, as of the last signature block). Stakeholders will be able to collect signature fees when providing a signature, proportionally to their weight.

At the basic level, there are no rules to choosing which of several conflicting blocks to sign, stakeholders should just choose one.

=== Cementing ===
Cementing is a node's reluctance to do a blockchain reorganization. A node will reject any new block found if it contradicts a 6-block deep branch it is already aware of and currently considers valid. That is, once a node receives 6 confirmations for a block, it will not accept a competing block even if it is part of a longer branch.

In a pure PoW system this is problematic to do because a node could be stuck on "the wrong version" - if an attacker isolates the node and feeds him bogus data, it will not embrace the true, longer chain when he learns of it. However, using PoS to have the final say in such situations makes this possible.

=== Branch selection ===
When a node needs to select which of several branches is valid, it chooses one based on the following criteria in increasing importance (each one is overridden by the next):

#Branch length (total difficulty of all blocks), as in a PoW system.
#Cementing - an already cemented block will not be replaced by a longer branch.
#Signatures - even a cemented block will be overridden by a signature block with signature weight more than half the total possible weight by some margin.

If the conflict is so long that it contains more than one spot for a signature block, the conflicting signature blocks will be traversed earliest to latest, each time choosing the branch with the majority vote. After the newest uncontested signature block it proceeds to use cementing and branch length.

A signature block with no clear majority will be considered tied, and will not override the other criteria. Signature fees will not be given out but instead carried over to the next signature spot, to encourage stakeholders to participate then.

=== [[Double-spending]] prevention ===
A good level of security can be achieved by waiting for a block to be cemented. By that time it is safe to assume that the network recognizes this block and will not easily switch to a different block, even if a longer branch is presented.

A more authoritative confirmation is enabled by waiting for a signature block. Once a block achieves a majority (and some more time is allowed for this majority to spread in the network), it is extremely unlikely that the network will ever switch away from this block.

=== Weights ===
The weight of every address starts at 0. When an address provides a signature, its weight increases so that after several signatures, the weight approaches the number of coins in the address as of the last signature block. For example,
New weight = 0.9 * Old weight + 0.1 * Balance
If a signature is not provided by the address in a signature block, its weight decreases:
New weight = 0.9 * Old weight
This way, addresses whose owners do not wish to participate in signing do not hamper the ability to reach a majority.

If an address signs two conflicting blocks, its weight is reset to 0. This is to limit the power of malicious stakeholders.

If coins move to a new address, weight is proportionally taken away from the addressed, but is not transferred to the new address. The new stakeholder will have to build up his weight.

=== Malicious stakeholders ===
The system is resilient against stakeholders who misuse their signature power, even if they have a majority of the bitcoins. Since their only obligation is to not sign conflicting blocks, the only way they could double-spend is if they first sign one block so it achieves a majority, then sign a different one so that it achieves a bigger majority. Generally this will not work. A short while after a majority is achieved, most of the network will be aware of the relevant signatures. If a different signature is broadcast, the conflict will be detected and both signatures will be ignored. This will cause the current majority block to become tied, but the network is already cemented on it and will vote for this branch in the next signature block. The weight of the attacker will by then reduce to 0 so he will be unable to create more disruption.

Another attack is refusing to sign blocks to keep them tied. Since this causes a decay of the weight, they can only stand in the way of a majority for a short time.

=== Denial of service ===
The method as described does not solve a denial of service scenario. A majority miner could create only blocks with no transactions (or with many transactions missing) and reject all other blocks.

This may be solvable by adding some measure of the transaction in a block to the selection criteria, such as Bitcoin days destroyed.

Also, proposals to replace the block chain with a directed acyclic graph have been made, and could be used to make it easier to include transactions.

== Key difference between the two proposals ==
In Cunicula's system, voting power is determined by combining (multiplicatively) your hashrate and stake. This would be problematic if small players could not compete effectively with large players. Though we are waiting on a formal mathematical proof, evidence to date suggests that small and large players would have an equal competitive footing. Simulations described in this thread [https://bitcointalk.org/index.php?topic=68213.msg801253#msg801253] indicate that small players are competitive with large players because the multiplicative combination of hashrate and stake exhibits constant returns. Evidence in the thread suggests that these simulation results are accepted by both Cunicula and Meni.)

In Meni's, there's a skeleton based purely on hashrate, and superimposed on it are occasional checkpoints set by stakeholders. You can contribute PoW without having stake, and you can contribute PoS without having work, and in both cases your voting power and reward is linearly proportional to the resources you have.

== PPCoin ==
[http://ppcoin.org PPCoin] is the first known implementation of a combined PoS/PoW system (released August 19 2012).

== See also ==
*[[Proof_of_work|Proof of work]]
*[[Proof_of_burn|Proof of burn]]

[[category:mining]]

Proof of burn

2014-03-25T06:23:25Z

Eldentyrell: wording

Proof of burn

2014-03-25T06:22:43Z

Eldentyrell: proof of burn requires a proof-of-work chain to bootstrap; it is not a true alternative.

'''Proof of burn''' is method for bootstrapping one cryptocurrency off of another. The idea is that miners should show proof that they ''burned'' some coins - that is, sent them to a verifiably unspendable address. This is expensive from their individual point of view, just like proof of work; but it consumes no resources from a whole economy perspective except for the underlying burned asset. To date, all proof of burn cryptocurrencies work by burning proof-of-work-mined cryptocurrencies, so the ultimate source of scarcity remains the proof-of-work-mined "fuel".

There are likely many possible variants of proof of burn. This page currently describes [[User:Ids|Iain Stewart]]'s version. Other people can add variant versions that still belong to the broad proof of burn idea.

== Iain Stewart's version of proof of burn ==

=== Introduction and motivation ===

The key idea of proof-of-burn (this would also apply to proof-of-stake, by the way) is that when choosing the thing which is to qualify as a "difficulty", i.e. to require miners to exhibit proof that they've "done something that's tough to do", all that matters is that ''an individual miner'' finds the task expensive. (Well... it also matters that everyone else should find it cheap to verify that it has been done.) It doesn't need to be the case that real resources are consumed in the real economy.

With proof-of-work, it so happens that real resources are indeed consumed - mining rigs are produced, with human labour and materials as input, electricity is used, and all these things have to be bid away from their real-economy best alternative uses. (Or, if they're produced ''in addition'' to what would have been produced, the total of leisure time is less than it could have been. Something real is grabbed as input.) And while a cryptocurrency is being set up (i.e. [the fast early phase of] its initial distribution) - or, more precisely, while ''the first'' cryptocurrency is being set up; more on this distinction later! - no good alternative has been proposed. (And I'm not proposing one.) But once a cryptocurrency is up and running, with its initial distribution close to completed, new possibilities arise, for tasks to "feel expensive" to a miner but not actually "be expensive" from a god-like whole-economy perspective.

Proof-of-stake (of the "Cunicula variety", I mean) is in fact arguably already an example of such a task. It feels awfully expensive, to a miner, to save up a lot of bitcoins and become a big stakeholder; but from a whole-economy viewpoint, this is a swapping of assets' ownership labels around, it's not a burning of electricity or the like. However, I thought it would be interesting to invent a task that is absolutely, nakedly, unambiguously an example of the contrast between the two viewpoints. And yes, there is one: burning the currency!

By "burning" a tranche of bitcoins I just mean sending them to an address which is unspendable. The precise technical details of this will vary from cryptocurrency to cryptocurrency. With Bitcoin, any address which is [the RIPEMD160/SHA256 hash of] a script that evaluates to false will do. So, the script should do a "deliberately silly" thing - instead of things like "check such-and-such signature, and put the validity result on the stack", it should do something like "add 2 and 2, and now check if what's on top of the stack is equal to 5". (Or just "push 4, and check if it's equal to 5". Anything of that sort.) There are thus an unbounded number of such scripts, with entropy saturating RIPEMD160 since you can choose big numbers to taste. So, bitcoins sent to such a txout can never be redeemed on a future txin. (Barring the cracking of RIPEMD160 and the finding of an alternative matching script, that is. If ''that'' happens, the cryptocurrency is in big trouble anyway!)

With this definition of burning, it's not obvious to blockchain-watchers that some bitcoins ''have'' been burnt, at the time of burning. They've been sent to an address which doesn't stand out from any other. It's only later, when a miner who burned them earlier now wants to exhibit proof that "yes, these coins are burnt", that blockchain-watchers get their proof. (Which basically consists of exhibiting the script that manifestly always evaluates to false, and hashes to the address.) If it's thought desirable that the act of burning should be obvious right away, rather than later, then this can be achieved: burning merely needs to be defined as sending to some ''fixed'' unspendable address, with no variation - e.g. we could settle on the hash of "push 4, and check if it's equal to 5".

So, miners are creating candidate winning blocks by saying to the listening world, not "Look! I've done this many trillion hashes! [or struck lucky with fewer: you, the listening world, wouldn't know the difference... but this doesn't matter...]", but rather "Look! Two months ago I burned this many bitcoins!". In both cases, "this many" means an adjustable difficulty parameter, which the network adjusts from time to time (fortnightly, in today's Bitcoin) to squeeze out marginal miners (and keep more-efficient-than-marginal ones in profit) to just the extent needed to regulate block creation to a preferred pace (one per 10 minutes, in today's Bitcoin).

Why that phrase "Two months ago"? The broad principle is as follows. A miner mustn't be able to just burn some bitcoins ''right now'' and say "OK, I've burned them! Now let me have all those latest juicy transaction fees that have arrived in the past few minutes! Thanks!" That extremely recent act of burning could be undone in a block chain reorganisation; and then the same miner would be able to "re-burn" those same coins in an attempt to grab a block afresh, post-reorganisation. That would constitute a breakdown in the analogy of burning with proof-of-work hashing. A trillion proof-of-work hashes on a pre-reorg block are of no value on the post-reorg chain. A proof-of-work miner must simply shrug and say "Oh well, that's those expenses [electricity, mining rig rental / imputed rental,...] lost and gone... time to try again!" And that's the way things should be, for security - it '''should not''' be as cheap to extend the height of two or more competing chains as it is to focus on one. (And having decided to focus on one, a miner ''should'' incur a risk of lost expense if their choice turns out to be "the wrong one" in network consensus terms.)

The above point makes it clear why the act of burning should be a decent interval earlier than the act of exhibiting proof. Two months may be overdoing it, but the protocol should require it to be sufficiently far back that there's no practical possibility of it being undone. There are in fact some further issues, to do with making sure it's not cheap for a miner to ''re-exhibit'' their proof (of having performed a suitably substantial burn a suitably long time ago) on multiple competing chains. Details to follow.

Now then! How much burning will actually happen, under this protocol? The answer is straightforward enough, though its implications are quite broad and in some ways surprising. Miners will burn bitcoins at an average rate '''very close to''' the average rate that ordinary users are sending them fees (and any coin-minting still going on too of course), minus the miners' true real-resource costs (i.e. the hardware and electricity and the like for handling transactions and blocks and burn proofs - these costs will be far lower than the hashing costs incurred under proof-of-work, but of course still non-zero). This follows by the same sort of "approach to equilibrium" reasoning that tells us that miners will ''expend real resources on proof-of-work'' to roughly that extent - if they didn't, mining would be supra-normally profitable, and new entrants would be attracted into the trade. If burning coins, rather than buying a lot of kit from a mining rig supplier, is the expense incurred by a miner to compete for the revenue stream, the same economic principles apply.

=== Technical sketch of proof of burn: "Burnt coins are mining rigs!" ===

''Iain Stewart writes:'' In this subsection I give a provisional technical sketch of the operational details of the proof-of-burn protocol I've currently settled on. It can be summed up in the following pithy slogan:

'''''"Burnt coins are mining rigs!"'''''

What that slogan means will become clear as I go on. Basically, proof-of-work is so elegant, in so many different ways, excepting its high real-resource cost, that I decided my attempt at an alternative to it, avoiding its real-resource cost, should mimic it as faithfully as possible in every other aspect. Well, only readers can judge whether I've succeeded!

The key is to use a '''stream of true randomness''' - see below for where ''that'' comes from! - to simulate the generating of random hashes that a real proof-of-work mining rig would produce. Now, obviously we don't want to "simulate" every actual hash! A "simulation" of proof-of-work at ''that'' level of detail would just ''be'' proof-of-work! Rather, we want to mimic the statistical properties of a mining rig's stream of hashes, to just the level of detail required to give the same sort of pattern of meeting / not meeting a moving difficulty target, and all the rest of it, that we get with the real thing.

So: first of all, what exactly is my "stream of true randomness"? Chop up time into units considerably shorter than the intended inter-block time, but with no need to go much finer than general network latency. (Seconds will do, I think.) For each second, t, we need a uniform random number between 0 and 1 assigned to it, RAND(t). This sounds as if we need some awful dependency on a fragile central source - some high-powered laser at NASA pouring out quantum noise every second, or something - with all the trust and failure issues that would imply. Fortunately, for simulating mining rigs, we don't need anything like that. All that matters is that, to someone "buying a simulated mining rig" (burning some bitcoins, that is!) at time t, they can't predict the value of RAND(any t' 2 months or more to the future of t). [Where "2 months" means the dead time a burnt coin must wait before it becomes a simulated active mining rig. See introductory motivating section above. It's basically just a generous waiting period to make sure a burnt coin is truly definitely burnt, and won't have any chance of being "unburnt" in a chain reorg, by the time it comes into use in mining.] We do '''not''' need fresh statistical independence of RAND(t) w.r.t. all of RAND(t-1), RAND(t-2), RAND(t-3), etc. (And we don't mind if the stream is known a "short" time into the future - e.g. a week or two; at any rate a small portion of the waiting period.)

Such a lesser goal can, I believe, be achieved with just a few tens of bits of true randomness per week. Quality is what matters, not quantity! I suggest tapping into the world's most highly-audited source of low-bit-rate true randomness: lotteries. These (the big reputable ones anyway) are already subject to elaborate inspection of the machinery that tosses the balls around and draws some of them out. And the results are publicised so widely, in so many newspapers, TV channels, websites etc, as to make it impossible for anyone to lie about them.

Roughly weekly, a config-file (lottery-results.dat or whatever) should get "the latest lottery results" appended to it. There is no hurry about this, it doesn't need to be exactly every week, or even the same lottery every time, it just needs several tens of bits of fresh lottery data added roughly weekly. I believe there would be no trouble propagating this to all nodes, by out-of-band means if necessary. The format should be utterly simple and transparent, a 1-line plain text description of the results and the timestamp (t in RAND(t)) from which they are to be paid attention to, onwards. Like this:

.
.
.
for use from 2013-06-24 00:00:00 onwards: UK national lottery 2013-06-12: 4 9 20 22 37 42, bonus ball 19
for use from 2013-07-01 00:00:00 onwards: UK national lottery 2013-06-19: 7 12 14 19 33 41, bonus ball 28

(Obviously the meta-level words "for use from... onwards" aren't really needed - I just put them in for clarity.) Each line is added in a leisurely, unhurried fashion, at some time (it doesn't matter when) between the draw and the intended start-paying-attention-to-it date. (Some time between 2013-06-19 and 2013-07-01 00:00:00, in the case of the example last line above.) This gives plenty of time for people to add it themselves, from their favourite news source, and check by out-of-band means that they've added what everybody else has added, right down to spelling and punctuation. (Which in practice probably means copying it from somewhere. The point is, the "somewhere" doesn't need to be trusted - a lie, or an unexpected variation in format or spelling or punctuation, would be called out well within the leisurely timescale.)

RAND(t) is then HASH(config-file [excluding any lines that are "for use from ''time later than t'' onwards" of course], plus t itself [in some standard format, e.g. 2013-07-02 23:14:05, or just the Unix numeric time] as a final line). - Or if you like, HASH(HASH(config-file) ++ t), for efficiency. (Where "++" means "append together in some standard fashion".) "HASH()" is your favourite hash function, e.g. SHA256(SHA256()). Thus RAND(t) is a 256-bit integer, which we regard conceptually as a real number between 0 and 1 by putting a binary point in front.

(I'm aware that people on the forums are coming up with randomness protocols for proof-of-stake, proof-of-activity and the like which ''don't'' involve external true randomness like lotteries - they just hash the last hundred blocks' hashes together, or something like that. I don't think this is good enough. [For their application or for mine!] Someone producing the latest block, given the previous 99, can privately produce billions of cheap variations on it, by varying the order the transactions are listed etc, until they find, and publish, the one that "games" the randomness in their favour. However, if I'm wrong about this, and hashing the last hundred blocks is in fact fine, then good! We can drop the lottery rigmarole! Anyway, for the rest of this description, I'll simply assume that RAND(t) becomes available for all t, but remains unknown until a week or two before t, and in particular, RAND(2 months or more from now) is "massively unknown" right now - unknown with many tens to hundreds of bits of unknowable future entropy. That's all that matters for turning burnt coins into simulated mining rigs.)

Right then! What do we do with this RAND(t) stream? We simulate the capricious behaviour of a true proof-of-work mining rig! Let us assume that, in the real proof-of-work world, you can buy an h hashes/second mining rig for b=c*h BTC. (c varies with technical progress, BTC price fluctuations, etc; but in the simulated world it can just be left constant.) Or, inverting this, if you spend b BTC, you acquire a mining rig of h=b/c hashes/s power. Now, what does it actually mean for your rig to perform h hashes during 1 second? It means you're producing h uniform random numbers between 0 and 1. (That binary point again!) But you don't really care what they all are individually - how well you did during that 1 second is defined as "what was the '''lowest''' hash value you produced during that 1 second?". This is then inspected for whether it beats [is lower than] the network's current target; or, perhaps, whether it beats the lesser [i.e. numerically greater] target of a pooled mining operation. If it's good enough, that precious lowest hash is published to the network (or mining pool), and the others are just thrown away (not published). If it's not good enough, even the [not-so-]precious lowest hash isn't published - and certainly not the others. So, in the simulation, we only need to produce, for each second, a simulated "lowest hash for that 1 second". The "others" don't have to exist at all!

For reproducing (statistically) the pattern of hits and misses w.r.t. targets tough enough to not be achieving several hits within 1 second, and for h>>1, we can take the simulated lowest hash for time t to be (1/h) * HASH(signatures-of-the-act-of-burning-the-b-BTC ++ RAND(t)). [In fact this even works for h<1, despite the rather surreal appearance of "lowest hashes" >1 every so often in that case - i.e. values outside the range that ''real'' lowest (or any other!) hashes can ever actually be: it turns out this surreal behaviour is just what's needed to degrade the probability of beating the target by just the right amount. Values >1 in effect represent "I didn't generate any hashes at all during this particular 1-second window".]

Two further subtleties. First of all, it turns out to be desirable to include the block number (chain height @ 1 per block) in the formula - just to keep the owners of simulated mining rigs "on their toes" and not be able to tell a week or so in advance when they'll be lucky. (This encourages them to run a continuous full node. Maybe that's not in fact that important.) So we take simulated-lowest-hash = (1/h) * HASH(signatures-of-the-act-of-burning-the-b-BTC ++ block-number-of-would-be-block ++ RAND(t)). (We should '''not''' include finer details of the block, to avoid "gaming" a la the hundred blocks business I mentioned earlier. - Or if I'm wrong about that, then OK, by all means mix in finer details of the block!)

Secondly, it turns out that to keep the burning process going forever, rather than a pulse of initial burning that no-one ever again wants to contribute further burning to, we should simulate one more property of real-world mining rigs: they break down! That is, we should demurrage away the strength of a simulated mining rig. (A plea to the reader: Don't be alarmed by the word "demurrage". This is '''burnt''' coins I'm talking about - they ''should'' be treated "harshly", in whatever style mimics real-world mining rigs to the required fidelity. Ordinary unburnt coins are not being demurraged! [Unless that's independently desirable as a policy matter, e.g. if it's felt that network strength can only be achieved via more revenue for miners than fees alone will ever provide.]) A real mining rig likely works at full tilt for a few years and then conks out. We ''could'' demurrage each burnt coin in that style - it abruptly expires E years after its creation - but I think a smooth exponential demurrage is nicer, i.e. its burnt value after y years is b'=b*exp(-y/E). Thus h = b'/c = (b/c)*exp(-y/E). [And 1/h = c/b' = (c/b)*exp(y/E).]

Taking these two further subtleties into account, we get the following formula:

simulated-lowest-hash(t) = (c/b)*exp([t - t_burning]/E) * HASH(signatures-of-the-act-of-burning-the-b-BTC ++ block-number-of-would-be-block ++ RAND(t)).

So there you have it! With this formula, life as a miner is spookily similar to the real proof-of-work case. You "buy a mining rig" - you burn coins, and that hits ''you'' in exactly the way sending off money to a chip supplier would have hit you, even though over the whole economy, no real resources have been expended - and you then hope that, by submitting lucky hashes to the network in the form of blocks, you can make more back in fees over time than you spent initially. If you don't keep connected to the network, you won't know what transactions are eligible for including in your next would-be block, and your next lucky hash will run to waste. Meanwhile, other people are "buying mining rigs" (burning coins) too, either freshly or to make up for the "wearing out" of their existing ones; and the network is adjusting its target hash value [reciprocal difficulty] to regulate the rate all this mining effort is producing blocks at, to some preferred average rate. All spookily normal, in other words!

Now, I'm being a little bit disingenuous to say that ''everything'' is normal. We need protection against certain things (use of a lucky hash on two or more competing chains; timestamp-falsification abuse) which either do not exist at all under true proof-of-work - the former - or exist but with the consequences and mitigation strategy being different in detail - the latter. I believe I have a way of standing up to the various forms of malice we need to worry about of those kinds. More to follow soon hopefully!

=== Economic implications ===

The key insight is that verifiably, publicly burning some coins of a known-total-stock-issued currency is the same as "remurrage" (opposite of "demurrage" - it may not be a correct word, but it's a nice back-formation) on the remainder. That is, if there are verifiably 21 million issued-and-not-burned coins, and then you go to sleep and wake up later and there are now only 20 million issued-and-not-burned coins, that's the same as if some magic genie multiplied all wake-up-time nominal bitcoin figures by 21/20. Another way to see the identity of real effect would be to redefine "burning n bitcoins" to mean, not "sending n to an unspendable address", but rather "scattering" the n bitcoins, i.e. sending them to '''every existing''' [non-zero-balance] address, in proportion to the balance [sum of unspent txouts] already stored in each. This would be a horribly gigantic transaction to actually do explicitly, but the point is, burning can be thought of "as if" done that way. (Slogan: Quantity-deflation is remurrage in disguise, in exactly the same way that quantity-inflation is demurrage in disguise.)

So, what ''that'' means is, if while you're sleeping you (a non-miner) hold 1 bitcoin purely passively, i.e. it just sits undisturbed on the blockchain, well, when you wake up, it's as if you've received a "dividend" (of 5% in the particular numeric example above) on top of the general economy-tracking price we expect of a constant-quantity currency. In a world with actual, visibly performed remurrage, this is made explicit - your balance is now 21/20, with the nominal circulation [issued-and-not-burned, and remurraged for good measure] constant at 21 million. You can go and spend the 1/20 "dividend" on some treat, and still have the same fraction (1 out of 21 million) of the money stock as when you went to sleep.

In a world ''without'' any attempt at explicit remurrage, the real facts of the situation are (of course!) the same, but their nominal expression is not perhaps so instantly obvious. Your nominal holding is unchanged at 1; but this is now 1 part in 20 million of the whole money stock, not the 1 part in 21 million it was before. So, you can go and spend 1/21 of it on some treat, taking your nominal balance down to 20/21, and ''that'' nominal balance is the same (1 out of 21 million) fraction of the money stock as when you went to sleep.

So, basically, if you're holding bitcoins and trying to hold an "economy-tracking amount", no more and no less, you find you can go out into the market and use the fraction of your holdings that counts as "dividend above and beyond economy-tracking" on some treat or other. (Indeed, "you can go out..." should read "you ''must'' go out...", if you're really determined to pursue precisely that tracking strategy.)

Who's selling you the real resources embodied in the "treat"? And what's ''their'' motive? Well, transaction fee payers presumably like to re-stock their bitcoin real balances to roughly the same [economy-tracking] level as before, on average - they're paying for the transaction processing as a service. These fees are then burned by miners. (Well, not literally the fees themselves - the fees themselves are ''collected'' by miners, but the way they achieve this is to burn an approximately equal amount, as explained earlier.) So, ordinary Bitcoin users, to achieve their desired re-stocking, have to either produce slightly more, or consume slightly less, or a proper or improper mixture thereof, than they would have needed to in a hypothetical (presumably impracticable) alternative world where they pay no fees for their everyday transactions (and some magic mining-god just altruistically and reliably creates a blockchain out of all the transactions, without charging anybody anything). [This follows directly from their re-stocking desire, and has nothing to do with proof-of-burn specifically. That is, they have to do this regardless of whether the protocol is proof-of-work, proof-of-stake, proof-of-burn or whatever.] It's that extra gap between production and consumption - "extra" on top of whatever gap people are already choosing as a real saving[/dis-saving] strategy - that goes on to the market, for you and all other bitcoin holders to bid off the market by spending on your "treat".

This whole stable pattern of spending habits is, perhaps surprisingly, the same pattern of real resource allocation as would have happened if Cunicula's proof of stake (with close to 100% stake / 0% work admixture) had been in operation, and all bitcoin holders, large and small, had enthusiastically thrown their bitcoins (that is, their stream of bitcoin days destroyed) into the stake-claiming process. The fraction of fees they'd collect if they did that would be just like the "dividend" as I called it above - it would be like explicit remurrage, except instead of being automatic, it would require each holder's active participation (i.e. they couldn't just go to sleep, unless they left some sort of "trusted bot" running and using their private keys to sign their stream of bitcoin days destroyed). So, if you like, proof-of-burn is like automated, 100%-stakeholder-participation Cunicula-style proof-of-stake!

Incidentally, it's also fascinating to consider what happens if the community does decide a demurraging of [ordinary, unburnt] coins, the revenue being added as a coin-[re-]minting stream to the flow of fees, ''is'' necessary to continue with forever, for the sake of network strength. The amazing answer, as far as I can honestly work out, is that in long-run equilibrium, the burn rate is just such as '''to make hardly any of this demurrage ''real'' demurrage at all!''' [The implicit remurrage of burning almost exactly cancels the explicit demurrage of network-strengthening coin-[re-]minting! (Or if you like, the implicit demurrage of inflationary fresh-coin-minting.) Either way, we ''seem'' to get the possibility of amazing network strength "for free"!] This opens up the shocking possibility of turning up the demurrage/inflation rate to startlingly high levels - 5% of money stock / year, 10% of money stock / year... levels that would bring the whole cryptocurrency into disrepute in the true proof-of-work case, since coin-holders really would suffer that actual amount of explicit or implicit demurrage - and yet '''not''' hitting coin-holders with more than a frictional residual fraction of that ''in real terms'' at all, because of the way burning simulates remurrage! Extraordinary stuff! I plan to say more about this soon - but this quick teaser description should already be food for thought.

=== Coin-burning as a tool for transition between cryptocurrencies ===

Proof of burn may also be of interest as a tool for managing an orderly transition from one cryptocurrency ("oldcoin", let's call it) to another ("newcoin"). If the developers of newcoin are looking for a way of avoiding proof-of-work's real resource consumption '''even in newcoin's initial distribution phase''', they can't use proof of newcoin-burn: newcoins don't exist yet. But they ''can'' use proof of oldcoin-burn! (Assuming their reason for creating newcoin is '''not''' a doubting of oldcoin's security model, anyway. - Or at least, not a doubting severe enough to affect sufficiently deeply buried oldcoins, these being the candidates for burning.)

The newcoin blockchain would thus start with (at least a hash referring to) a complete catalogue of all the [sufficiently deeply buried] unspent txouts of oldcoin. Miners would then exhibit burning events within oldcoin up to a certain date; after which, the protocol would switch to burning of newcoin itself (and the dependency on oldcoin could even be thrown away entirely, if a checkpoint of that transition moment was promulgated and accepted by the newcoin community).

This has the nice consequence that, if people throughout the broader economy are gradually deserting oldcoin (as newcoin catches on), '''''its value need not collapse!''''' Instead, oldcoin gets burnt in the transition process, neatly reducing its nominal supply in just such a way as to roughly keep pace with its declining real demand. Meanwhile, those same acts of burning are minting fresh newcoins, at just the pace required to keep up with newcoin's ''growing'' real demand. (At least, that's the case if miners anticipate the transition speed correctly, and enter / exit the coins' respective mining trades at a pace that competes away supra-normal profits. We also have to assume that the ''total'' real demand for both[/all...] cryptocurrencies is roughly stable in "economy-tracking" terms; or at least, that miners anticipate the time path of the size of total real demand, and of its currency-by-currency composition, correctly, or near enough correctly.)

'''To sum up:''' proof of burn ''could'', just maybe, qualify as a new tool to greatly assist overall (multi-cryptocurrency) economic robustness and stability!

== Earlier work suggesting a role for the burning of coins ==

[https://bitcointalk.org/index.php?topic=131139.msg1404195#msg1404195 Forum member ripper234 points out] an earlier work by forum member [https://bitcointalk.org/index.php?action=profile;u=3313 dacoinminster] suggesting coins could be burnt as one component of a broader protocol. [https://bitcointalk.org/index.php?topic=56901.0 The earlier work] is [http://bitcoin.stackexchange.com/questions/2458/is-dacoinminsters-second-bitcoin-whitepaper-logically-economically-consistent discussed on StackExchange]. It revolves around a centralised "trusted entity" system, and so is not directly comparable to decentralised proof-of-burn mining; but it may be of interest to some readers.

== See also ==
*[[Proof_of_work|Proof of work]]
*[[Proof_of_Stake|Proof of stake]]

[[category:mining]]

Hardfork

2014-03-22T17:54:43Z

Eldentyrell:

A Hardfork is a change to the bitcoin protocol that requires all users upgrade.

Any alteration to bitcoin which changes the block structure (including block hash), difficulty rules, or increases the set of valid transactions is a hardfork. However, some of these changes can be implemented by having the new transaction appear to older clients as a pay-to-anybody transaction (of a special form), and getting the miners to agree to reject blocks including the pay-to-anybody transaction unless the transaction validates under the new rules. This is how [[P2SH]] was added to Bitcoin.

See also: [[Softfork]]

Softfork wishlist

2014-03-22T17:53:06Z

Eldentyrell: move softfork-implementable changes from Hardfork_wishlist

The '''Softfork Wishlist''' is to record changes to Bitcoin that might be desirable, but that will require a [[Softfork|"soft" block-chain split]] (consensus of the miners). These changes are implemented by convincing a majority of the miners to reject or [[Discouraged_block|discourage]] blocks that were previously considered valid. This is often combined with a special form of pay-to-anybody transaction, which is declared to have a new meaning. Old clients will see the new transaction types as a pay-to-anybody, but attempts to "steal" these pay-to-anybody outputs without using the new transaction type will be refused by the miners and all upgraded clients.

This page is ''not'' for changes that require a [[Hardfork|"hard" block-chain split]] (everybody must upgrade, old software will not accept blocks/transactions created with the new [[Protocol rules|rules]], considering them to be [[Invalid block|invalid blocks]]). See [[Softfork_wishlist]].

== Block format ==
* Require a [https://en.bitcoin.it/wiki/Thin_Client_Security#Unused_Output_Tree_in_the_Blockchain_.28UOT.29 UTXO tree] in every block

== New Transaction Types ==
* Pay-to-[http://eprint.iacr.org/2013/507.pdf SNARK] (aka [https://bitcointalk.org/index.php?topic=277389.0 CoinWitness]). This allows payment to a user who can produce cryptographic evidence that they ran a certain (time-bounded) program on a certain input argument. The size of the cryptographic evidence is linear in the input argument but constant with respect to the size and running time of the program, so bounding the size of the input argument bounds the size of the data that needs to be put into the blockchain. Unfortunately the time+space constant factors are, with current algorithms, rather large.

== Cryptographic changes==
* Pervasive ECC public key-recovery to reduce transaction sizes (can be done partially without breaking compatibility completely)
* [http://ed25519.cr.yp.to/ Ed25519] (variant*) for much faster validation operations. (variant because the normal way Ed25519 is specified is not key recovery compatible)
* Support for more than one public-key cryptosystem (ECDSA-k1) and key size (256bits) as a hedge against future cryptanalysis or designed-in flaws in any one algorithm. Every node must support validation of signatures with every cryptosystem, but a small number of very-cryptograpically-diverse options is still better than just one. Additional signature types could be kludged into the existing system with script extensions but would be better supported natively.
* Support for a [http://en.wikipedia.org/wiki/Post-quantum_cryptography post-quantum] signature scheme. [http://en.wikipedia.org/wiki/Lamport_signature Lamport signatures] have nice intuitive security properties, but it has extreme space requirements that would require structural changes to the blockchain to accommodate, (e.g. flip-chain+paytoscripthash+extensive pruning). However other post-quantum schemes like [http://en.wikipedia.org/wiki/NTRU IEEE1363.1] (patent expires in 2016) do not. See the [http://pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf introductory chapter of DJB's book] and the [http://pqcrypto.org PQCrypto conference webpage] for full details.

Hardfork Wishlist

2014-03-22T17:51:09Z

Eldentyrell: move softfork-implementable changes to Softfork_wishlist

Softfork wishlist

2014-03-22T17:48:30Z

Eldentyrell:

The '''Softfork Wishlist''' is to record changes to Bitcoin that might be desirable, but that will require a [[Softfork|"soft" block-chain split]] (consensus of the miners).

This page is ''not'' for changes that require a [[Hardfork|"hard" block-chain split]] (everybody must upgrade, old software will not accept blocks/transactions created with the new [[Protocol rules|rules]], considering them to be [[Invalid block|invalid blocks]]). See [[Softfork_wishlist]].

Softfork wishlist

2014-03-22T17:47:52Z

Eldentyrell: Created page with "The '''Softfork Wishlist''' is to record changes to Bitcoin that might be desirable, but that will require a "soft" block-chain split (consensus of the miners)...."

The '''Softfork Wishlist''' is to record changes to Bitcoin that might be desirable, but that will require a [[Softfork|"soft" block-chain split]] (consensus of the miners).

This page is ''not'' for changes that require a [[Hardfork|"hard" block-chain split]] (everybody must upgrade, old software will not accept blocks/transactions created with the new [[Protocol rules|rules]], considering them to be [[Invalid block|invalid blocks]]).

Hardfork Wishlist

2014-03-22T17:46:57Z

Eldentyrell: Add link to Softfork_wishlist

The '''Hardfork Wishlist''' is to record changes to Bitcoin that might be desirable, but that will require a [[Hardfork|"hard" block-chain split]] (everybody must upgrade, old software will not accept blocks/transactions created with the new [[Protocol rules|rules]], considering them to be [[Invalid block|invalid blocks]]).

This page is ''not'' for changes that can be accomplished in way that is compatible with old software (for example, by making transactions [[Nonstandard block|nonstandard]] or by [[Discouraged block|discouraging blocks]]).

This page is also not for changes that can be accomplished by a [[Softfork]]. See [[Softfork_wishlist]].

== Changes to hard-coded limits ==
* Replace hard-coded maximum block size (1,000,000 bytes) and maximum number of signature operations per block (20,000) with ???.

== Major structural changes ==
* "Flip the chain", instead of committing to new transactions, commit to the summaries of open transactions: [https://bitcointalk.org/index.php?topic=505.0] [https://bitcointalk.org/index.php?topic=21995.0] [https://en.bitcoin.it/wiki/User:DiThi/MTUT#PROPOSAL:_Merkle_tree_of_unspent_transactions_.28MTUT.29.2C_for_serverless_thin_clients_and_self-verifiable_prunned_blockchain.] [https://bitcointalk.org/index.php?topic=88208.0]
* Increased efficiency for merged mining: restructure the primary header to make the bitcoin specific data non-mandatory. (e.g. the block chain specific stuff would go into second header connected by a header tree), making the primary headers pure timestamps and nonces.
* Switch to block hashing algorithm secure against block withholding attacks.
* Require a [https://en.bitcoin.it/wiki/Thin_Client_Security#Unused_Output_Tree_in_the_Blockchain_.28UOT.29 UTXO tree] in every block

== Transaction behavior changes==
* Improved signature types to allow for partial malleability of outputs. (e.g. make it easier to add a fee onto someone else's transaction, or to take fees from a transaction without outputs set aside for that purpose)
* Elimination of output scripts: all transactions pay-to-scripthash, probably with a single byte indicating the scripthash type. Other than reducing effective output script secrecy (which is not possible without OP_EVAL anyways) this is believed to be costless, and the secrecy can be recovered with recursive OP_EVAL. The motivation here is that data in outputs is far more expensive than inputs because some outputs may be never prunable, and pay-to-scripthash minimizes output size without harming total size.
* Allow soft-spending of generation outputs without confirmations (outputs of these transactions might also appear as generation themselves)
* Allow additional inputs to generation transactions
* Add new signature hashtype to include value of TxOut being spent, in the hash to be signed. Doing this would remove the requirement that offline signing devices be sent all supporting transactions with the transaction-to-be-signed, just to confirm the transaction fee.
* Pay-to-[http://eprint.iacr.org/2013/507.pdf SNARK] (aka [https://bitcointalk.org/index.php?topic=277389.0 CoinWitness]). This allows payment to a user who can produce cryptographic evidence that they ran a certain (time-bounded) program on a certain input argument. The size of the cryptographic evidence is linear in the input argument but constant with respect to the size and running time of the program, so bounding the size of the input argument bounds the size of the data that needs to be put into the blockchain. Unfortunately the time+space constant factors are, with current algorithms, rather large.

== Cryptographic changes==
* Pervasive ECC public key-recovery to reduce transaction sizes (can be done partially without breaking compatibility completely)
* [http://ed25519.cr.yp.to/ Ed25519] (variant*) for much faster validation operations. (variant because the normal way Ed25519 is specified is not key recovery compatible)
* Support for more than one public-key cryptosystem (ECDSA-k1) and key size (256bits) as a hedge against future cryptanalysis or designed-in flaws in any one algorithm. Every node must support validation of signatures with every cryptosystem, but a small number of very-cryptograpically-diverse options is still better than just one. Additional signature types could be kludged into the existing system with script extensions but would be better supported natively.
* Support for a [http://en.wikipedia.org/wiki/Post-quantum_cryptography post-quantum] signature scheme. [http://en.wikipedia.org/wiki/Lamport_signature Lamport signatures] have nice intuitive security properties, but it has extreme space requirements that would require structural changes to the blockchain to accommodate, (e.g. flip-chain+paytoscripthash+extensive pruning). However other post-quantum schemes like [http://en.wikipedia.org/wiki/NTRU IEEE1363.1] (patent expires in 2016) do not. See the [http://pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf introductory chapter of DJB's book] and the [http://pqcrypto.org PQCrypto conference webpage] for full details.

== Privacy ==
* Better privacy using [http://en.wikipedia.org/wiki/Non-interactive_zero-knowledge_proof NIZKP]s, as proposed in [http://zerocoin.org Zerocoin] or similar.

== Currency changes==
''Please don't list anything here which would significantly change the committed overall economics of the system, it's safe to assume anything with significant economic impact will _never_ be changed in Bitcoin<ref>[http://bitcointalk.org/index.php?topic=45468.msg542375#msg542375 Suggested MAJOR change to Bitcoin]</ref>, because such changes would undermine the trust people have in the system, though they may form the basis of an interesting [[alternative chain]].
* Increase currency divisibility.

== Navel gazing / Protocol housekeeping==
* Byte order consistency (big endian)
* Eliminate redundancies in the variable length integer encodings, possibly switch to a standard.
* Avoiding hashes covering malleable fields

== Bug fixes ==
* CHECKMULTISIG popping one-too-many items off the stack
* Difficulty adjustment periods should overlap (prevent potential 'timejacking') Note: An ideal adjustment algorithm would ensure there is no easy dispute on "next target" for any block. Eg, it should not be possible for MinerX to set his block time 2 hours in the future to achieve a slightly higher difficulty and win any same-block-height race by default.
* Difficulty adjustment should adapt to sudden hashrate loss. Note: many altchains which have attempted this have created significant security vulnerabilities in the process, but experimentation continues.
* Scripts should be fully enabled after a careful audit.
* Miners/relays should not be able to inject extra arbitrary data into transactions?
* Use the previous block hash as an explicit or implicit prev_in in coinbases when hashing them to make it ~impossible to get a duplicate coinbase, thus removing the need for a pruning node to remember coinbase hashes to prevent duplicates consistently with the rest of the network. Note that this problem has already been solved with a softfork in [https://bitcointalk.org/index.php?topic=92558.0 BIP34].
* coinbases must be parseable.
This changes would involve converting old blocks:
* uint64_t for timestamp field in blocks.

==See Also==
*[[Prohibited changes]]

==References==
<references />

[[Category:Technical]]
[[Category:Developer]]

Softfork

2014-03-22T17:45:37Z

Eldentyrell: Created page with "A Softfork is a change to the bitcoin protocol that requires only a majority of the miners upgrade. New transaction types can often be added as softforks, requiring only that..."

A Softfork is a change to the bitcoin protocol that requires only a majority of the miners upgrade.

New transaction types can often be added as softforks, requiring only that the sender and the miners understand the new transaction type. This is done by having the new transaction appear to older clients as a pay-to-anybody transaction (of a special form), and getting the miners to agree to reject blocks including the pay-to-anybody transaction unless the transaction validates under the new rules. This is how [[P2SH]] was added to Bitcoin.

See also: [[Hardfork]]

Hardfork

2014-03-22T17:44:00Z

Eldentyrell: Created page with "A Hardfork is a change to the bitcoin protocol that requires all users upgrade. Any alteration to bitcoin which increases the set of valid transactions is a hardfork. Howeve..."

A Hardfork is a change to the bitcoin protocol that requires all users upgrade.

Any alteration to bitcoin which increases the set of valid transactions is a hardfork. However, some of these changes can be implemented by having the new transaction appear to older clients as a pay-to-anybody transaction (of a special form), and getting the miners to agree to reject blocks including the pay-to-anybody transaction unless the transaction validates under the new rules. This is how [[P2SH]] was added to Bitcoin.

See also: [[Softfork]]

Hardfork Wishlist

2014-03-22T17:41:17Z

Eldentyrell:

The '''Hardfork Wishlist''' is to record changes to Bitcoin that might be desirable, but that will require a [[Hardfork|"hard" block-chain split]] (everybody must upgrade, old software will not accept blocks/transactions created with the new [[Protocol rules|rules]], considering them to be [[Invalid block|invalid blocks]]).

This page is ''not'' for changes that can be accomplished in way that is compatible with old software (for example, by making transactions [[Nonstandard block|nonstandard]] or by [[Discouraged block|discouraging blocks]]).

== Changes to hard-coded limits ==
* Replace hard-coded maximum block size (1,000,000 bytes) and maximum number of signature operations per block (20,000) with ???.

== Major structural changes ==
* "Flip the chain", instead of committing to new transactions, commit to the summaries of open transactions: [https://bitcointalk.org/index.php?topic=505.0] [https://bitcointalk.org/index.php?topic=21995.0] [https://en.bitcoin.it/wiki/User:DiThi/MTUT#PROPOSAL:_Merkle_tree_of_unspent_transactions_.28MTUT.29.2C_for_serverless_thin_clients_and_self-verifiable_prunned_blockchain.] [https://bitcointalk.org/index.php?topic=88208.0]
* Increased efficiency for merged mining: restructure the primary header to make the bitcoin specific data non-mandatory. (e.g. the block chain specific stuff would go into second header connected by a header tree), making the primary headers pure timestamps and nonces.
* Switch to block hashing algorithm secure against block withholding attacks.
* Require a [https://en.bitcoin.it/wiki/Thin_Client_Security#Unused_Output_Tree_in_the_Blockchain_.28UOT.29 UTXO tree] in every block

== Transaction behavior changes==
* Improved signature types to allow for partial malleability of outputs. (e.g. make it easier to add a fee onto someone else's transaction, or to take fees from a transaction without outputs set aside for that purpose)
* Elimination of output scripts: all transactions pay-to-scripthash, probably with a single byte indicating the scripthash type. Other than reducing effective output script secrecy (which is not possible without OP_EVAL anyways) this is believed to be costless, and the secrecy can be recovered with recursive OP_EVAL. The motivation here is that data in outputs is far more expensive than inputs because some outputs may be never prunable, and pay-to-scripthash minimizes output size without harming total size.
* Allow soft-spending of generation outputs without confirmations (outputs of these transactions might also appear as generation themselves)
* Allow additional inputs to generation transactions
* Add new signature hashtype to include value of TxOut being spent, in the hash to be signed. Doing this would remove the requirement that offline signing devices be sent all supporting transactions with the transaction-to-be-signed, just to confirm the transaction fee.
* Pay-to-[http://eprint.iacr.org/2013/507.pdf SNARK] (aka [https://bitcointalk.org/index.php?topic=277389.0 CoinWitness]). This allows payment to a user who can produce cryptographic evidence that they ran a certain (time-bounded) program on a certain input argument. The size of the cryptographic evidence is linear in the input argument but constant with respect to the size and running time of the program, so bounding the size of the input argument bounds the size of the data that needs to be put into the blockchain. Unfortunately the time+space constant factors are, with current algorithms, rather large.

== Cryptographic changes==
* Pervasive ECC public key-recovery to reduce transaction sizes (can be done partially without breaking compatibility completely)
* [http://ed25519.cr.yp.to/ Ed25519] (variant*) for much faster validation operations. (variant because the normal way Ed25519 is specified is not key recovery compatible)
* Support for more than one public-key cryptosystem (ECDSA-k1) and key size (256bits) as a hedge against future cryptanalysis or designed-in flaws in any one algorithm. Every node must support validation of signatures with every cryptosystem, but a small number of very-cryptograpically-diverse options is still better than just one. Additional signature types could be kludged into the existing system with script extensions but would be better supported natively.
* Support for a [http://en.wikipedia.org/wiki/Post-quantum_cryptography post-quantum] signature scheme. [http://en.wikipedia.org/wiki/Lamport_signature Lamport signatures] have nice intuitive security properties, but it has extreme space requirements that would require structural changes to the blockchain to accommodate, (e.g. flip-chain+paytoscripthash+extensive pruning). However other post-quantum schemes like [http://en.wikipedia.org/wiki/NTRU IEEE1363.1] (patent expires in 2016) do not. See the [http://pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf introductory chapter of DJB's book] and the [http://pqcrypto.org PQCrypto conference webpage] for full details.

== Privacy ==
* Better privacy using [http://en.wikipedia.org/wiki/Non-interactive_zero-knowledge_proof NIZKP]s, as proposed in [http://zerocoin.org Zerocoin] or similar.

== Currency changes==
''Please don't list anything here which would significantly change the committed overall economics of the system, it's safe to assume anything with significant economic impact will _never_ be changed in Bitcoin<ref>[http://bitcointalk.org/index.php?topic=45468.msg542375#msg542375 Suggested MAJOR change to Bitcoin]</ref>, because such changes would undermine the trust people have in the system, though they may form the basis of an interesting [[alternative chain]].
* Increase currency divisibility.

== Navel gazing / Protocol housekeeping==
* Byte order consistency (big endian)
* Eliminate redundancies in the variable length integer encodings, possibly switch to a standard.
* Avoiding hashes covering malleable fields

== Bug fixes ==
* CHECKMULTISIG popping one-too-many items off the stack
* Difficulty adjustment periods should overlap (prevent potential 'timejacking') Note: An ideal adjustment algorithm would ensure there is no easy dispute on "next target" for any block. Eg, it should not be possible for MinerX to set his block time 2 hours in the future to achieve a slightly higher difficulty and win any same-block-height race by default.
* Difficulty adjustment should adapt to sudden hashrate loss. Note: many altchains which have attempted this have created significant security vulnerabilities in the process, but experimentation continues.
* Scripts should be fully enabled after a careful audit.
* Miners/relays should not be able to inject extra arbitrary data into transactions?
* Use the previous block hash as an explicit or implicit prev_in in coinbases when hashing them to make it ~impossible to get a duplicate coinbase, thus removing the need for a pruning node to remember coinbase hashes to prevent duplicates consistently with the rest of the network. Note that this problem has already been solved with a softfork in [https://bitcointalk.org/index.php?topic=92558.0 BIP34].
* coinbases must be parseable.
This changes would involve converting old blocks:
* uint64_t for timestamp field in blocks.

==See Also==
*[[Prohibited changes]]

==References==
<references />

[[Category:Technical]]
[[Category:Developer]]

Hardfork Wishlist

2014-03-22T17:41:05Z

Eldentyrell:

The '''Hardfork Wishlist''' is to record changes to Bitcoin that might be desirable, but that will require a [Hardfork|"hard" block-chain split] (everybody must upgrade, old software will not accept blocks/transactions created with the new [[Protocol rules|rules]], considering them to be [[Invalid block|invalid blocks]]).

This page is ''not'' for changes that can be accomplished in way that is compatible with old software (for example, by making transactions [[Nonstandard block|nonstandard]] or by [[Discouraged block|discouraging blocks]]).

== Changes to hard-coded limits ==
* Replace hard-coded maximum block size (1,000,000 bytes) and maximum number of signature operations per block (20,000) with ???.

== Major structural changes ==
* "Flip the chain", instead of committing to new transactions, commit to the summaries of open transactions: [https://bitcointalk.org/index.php?topic=505.0] [https://bitcointalk.org/index.php?topic=21995.0] [https://en.bitcoin.it/wiki/User:DiThi/MTUT#PROPOSAL:_Merkle_tree_of_unspent_transactions_.28MTUT.29.2C_for_serverless_thin_clients_and_self-verifiable_prunned_blockchain.] [https://bitcointalk.org/index.php?topic=88208.0]
* Increased efficiency for merged mining: restructure the primary header to make the bitcoin specific data non-mandatory. (e.g. the block chain specific stuff would go into second header connected by a header tree), making the primary headers pure timestamps and nonces.
* Switch to block hashing algorithm secure against block withholding attacks.
* Require a [https://en.bitcoin.it/wiki/Thin_Client_Security#Unused_Output_Tree_in_the_Blockchain_.28UOT.29 UTXO tree] in every block

== Transaction behavior changes==
* Improved signature types to allow for partial malleability of outputs. (e.g. make it easier to add a fee onto someone else's transaction, or to take fees from a transaction without outputs set aside for that purpose)
* Elimination of output scripts: all transactions pay-to-scripthash, probably with a single byte indicating the scripthash type. Other than reducing effective output script secrecy (which is not possible without OP_EVAL anyways) this is believed to be costless, and the secrecy can be recovered with recursive OP_EVAL. The motivation here is that data in outputs is far more expensive than inputs because some outputs may be never prunable, and pay-to-scripthash minimizes output size without harming total size.
* Allow soft-spending of generation outputs without confirmations (outputs of these transactions might also appear as generation themselves)
* Allow additional inputs to generation transactions
* Add new signature hashtype to include value of TxOut being spent, in the hash to be signed. Doing this would remove the requirement that offline signing devices be sent all supporting transactions with the transaction-to-be-signed, just to confirm the transaction fee.
* Pay-to-[http://eprint.iacr.org/2013/507.pdf SNARK] (aka [https://bitcointalk.org/index.php?topic=277389.0 CoinWitness]). This allows payment to a user who can produce cryptographic evidence that they ran a certain (time-bounded) program on a certain input argument. The size of the cryptographic evidence is linear in the input argument but constant with respect to the size and running time of the program, so bounding the size of the input argument bounds the size of the data that needs to be put into the blockchain. Unfortunately the time+space constant factors are, with current algorithms, rather large.

== Cryptographic changes==
* Pervasive ECC public key-recovery to reduce transaction sizes (can be done partially without breaking compatibility completely)
* [http://ed25519.cr.yp.to/ Ed25519] (variant*) for much faster validation operations. (variant because the normal way Ed25519 is specified is not key recovery compatible)
* Support for more than one public-key cryptosystem (ECDSA-k1) and key size (256bits) as a hedge against future cryptanalysis or designed-in flaws in any one algorithm. Every node must support validation of signatures with every cryptosystem, but a small number of very-cryptograpically-diverse options is still better than just one. Additional signature types could be kludged into the existing system with script extensions but would be better supported natively.
* Support for a [http://en.wikipedia.org/wiki/Post-quantum_cryptography post-quantum] signature scheme. [http://en.wikipedia.org/wiki/Lamport_signature Lamport signatures] have nice intuitive security properties, but it has extreme space requirements that would require structural changes to the blockchain to accommodate, (e.g. flip-chain+paytoscripthash+extensive pruning). However other post-quantum schemes like [http://en.wikipedia.org/wiki/NTRU IEEE1363.1] (patent expires in 2016) do not. See the [http://pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf introductory chapter of DJB's book] and the [http://pqcrypto.org PQCrypto conference webpage] for full details.

== Privacy ==
* Better privacy using [http://en.wikipedia.org/wiki/Non-interactive_zero-knowledge_proof NIZKP]s, as proposed in [http://zerocoin.org Zerocoin] or similar.

== Currency changes==
''Please don't list anything here which would significantly change the committed overall economics of the system, it's safe to assume anything with significant economic impact will _never_ be changed in Bitcoin<ref>[http://bitcointalk.org/index.php?topic=45468.msg542375#msg542375 Suggested MAJOR change to Bitcoin]</ref>, because such changes would undermine the trust people have in the system, though they may form the basis of an interesting [[alternative chain]].
* Increase currency divisibility.

== Navel gazing / Protocol housekeeping==
* Byte order consistency (big endian)
* Eliminate redundancies in the variable length integer encodings, possibly switch to a standard.
* Avoiding hashes covering malleable fields

== Bug fixes ==
* CHECKMULTISIG popping one-too-many items off the stack
* Difficulty adjustment periods should overlap (prevent potential 'timejacking') Note: An ideal adjustment algorithm would ensure there is no easy dispute on "next target" for any block. Eg, it should not be possible for MinerX to set his block time 2 hours in the future to achieve a slightly higher difficulty and win any same-block-height race by default.
* Difficulty adjustment should adapt to sudden hashrate loss. Note: many altchains which have attempted this have created significant security vulnerabilities in the process, but experimentation continues.
* Scripts should be fully enabled after a careful audit.
* Miners/relays should not be able to inject extra arbitrary data into transactions?
* Use the previous block hash as an explicit or implicit prev_in in coinbases when hashing them to make it ~impossible to get a duplicate coinbase, thus removing the need for a pruning node to remember coinbase hashes to prevent duplicates consistently with the rest of the network. Note that this problem has already been solved with a softfork in [https://bitcointalk.org/index.php?topic=92558.0 BIP34].
* coinbases must be parseable.
This changes would involve converting old blocks:
* uint64_t for timestamp field in blocks.

==See Also==
*[[Prohibited changes]]

==References==
<references />

[[Category:Technical]]
[[Category:Developer]]

Hardfork Wishlist

2014-03-22T17:40:21Z

Eldentyrell: /* Transaction behavior changes */

The '''Hardfork Wishlist''' is to record changes to Bitcoin that might be desirable, but that will require a "hard" block-chain split (everybody must upgrade, old software will not accept blocks/transactions created with the new [[Protocol rules|rules]], considering them to be [[Invalid block|invalid blocks]]).

This page is ''not'' for changes that can be accomplished in way that is compatible with old software (for example, by making transactions [[Nonstandard block|nonstandard]] or by [[Discouraged block|discouraging blocks]]).

== Changes to hard-coded limits ==
* Replace hard-coded maximum block size (1,000,000 bytes) and maximum number of signature operations per block (20,000) with ???.

== Major structural changes ==
* "Flip the chain", instead of committing to new transactions, commit to the summaries of open transactions: [https://bitcointalk.org/index.php?topic=505.0] [https://bitcointalk.org/index.php?topic=21995.0] [https://en.bitcoin.it/wiki/User:DiThi/MTUT#PROPOSAL:_Merkle_tree_of_unspent_transactions_.28MTUT.29.2C_for_serverless_thin_clients_and_self-verifiable_prunned_blockchain.] [https://bitcointalk.org/index.php?topic=88208.0]
* Increased efficiency for merged mining: restructure the primary header to make the bitcoin specific data non-mandatory. (e.g. the block chain specific stuff would go into second header connected by a header tree), making the primary headers pure timestamps and nonces.
* Switch to block hashing algorithm secure against block withholding attacks.
* Require a [https://en.bitcoin.it/wiki/Thin_Client_Security#Unused_Output_Tree_in_the_Blockchain_.28UOT.29 UTXO tree] in every block

== Transaction behavior changes==
* Improved signature types to allow for partial malleability of outputs. (e.g. make it easier to add a fee onto someone else's transaction, or to take fees from a transaction without outputs set aside for that purpose)
* Elimination of output scripts: all transactions pay-to-scripthash, probably with a single byte indicating the scripthash type. Other than reducing effective output script secrecy (which is not possible without OP_EVAL anyways) this is believed to be costless, and the secrecy can be recovered with recursive OP_EVAL. The motivation here is that data in outputs is far more expensive than inputs because some outputs may be never prunable, and pay-to-scripthash minimizes output size without harming total size.
* Allow soft-spending of generation outputs without confirmations (outputs of these transactions might also appear as generation themselves)
* Allow additional inputs to generation transactions
* Add new signature hashtype to include value of TxOut being spent, in the hash to be signed. Doing this would remove the requirement that offline signing devices be sent all supporting transactions with the transaction-to-be-signed, just to confirm the transaction fee.
* Pay-to-[http://eprint.iacr.org/2013/507.pdf SNARK] (aka [https://bitcointalk.org/index.php?topic=277389.0 CoinWitness]). This allows payment to a user who can produce cryptographic evidence that they ran a certain (time-bounded) program on a certain input argument. The size of the cryptographic evidence is linear in the input argument but constant with respect to the size and running time of the program, so bounding the size of the input argument bounds the size of the data that needs to be put into the blockchain. Unfortunately the time+space constant factors are, with current algorithms, rather large.

== Cryptographic changes==
* Pervasive ECC public key-recovery to reduce transaction sizes (can be done partially without breaking compatibility completely)
* [http://ed25519.cr.yp.to/ Ed25519] (variant*) for much faster validation operations. (variant because the normal way Ed25519 is specified is not key recovery compatible)
* Support for more than one public-key cryptosystem (ECDSA-k1) and key size (256bits) as a hedge against future cryptanalysis or designed-in flaws in any one algorithm. Every node must support validation of signatures with every cryptosystem, but a small number of very-cryptograpically-diverse options is still better than just one. Additional signature types could be kludged into the existing system with script extensions but would be better supported natively.
* Support for a [http://en.wikipedia.org/wiki/Post-quantum_cryptography post-quantum] signature scheme. [http://en.wikipedia.org/wiki/Lamport_signature Lamport signatures] have nice intuitive security properties, but it has extreme space requirements that would require structural changes to the blockchain to accommodate, (e.g. flip-chain+paytoscripthash+extensive pruning). However other post-quantum schemes like [http://en.wikipedia.org/wiki/NTRU IEEE1363.1] (patent expires in 2016) do not. See the [http://pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf introductory chapter of DJB's book] and the [http://pqcrypto.org PQCrypto conference webpage] for full details.

== Privacy ==
* Better privacy using [http://en.wikipedia.org/wiki/Non-interactive_zero-knowledge_proof NIZKP]s, as proposed in [http://zerocoin.org Zerocoin] or similar.

== Currency changes==
''Please don't list anything here which would significantly change the committed overall economics of the system, it's safe to assume anything with significant economic impact will _never_ be changed in Bitcoin<ref>[http://bitcointalk.org/index.php?topic=45468.msg542375#msg542375 Suggested MAJOR change to Bitcoin]</ref>, because such changes would undermine the trust people have in the system, though they may form the basis of an interesting [[alternative chain]].
* Increase currency divisibility.

== Navel gazing / Protocol housekeeping==
* Byte order consistency (big endian)
* Eliminate redundancies in the variable length integer encodings, possibly switch to a standard.
* Avoiding hashes covering malleable fields

== Bug fixes ==
* CHECKMULTISIG popping one-too-many items off the stack
* Difficulty adjustment periods should overlap (prevent potential 'timejacking') Note: An ideal adjustment algorithm would ensure there is no easy dispute on "next target" for any block. Eg, it should not be possible for MinerX to set his block time 2 hours in the future to achieve a slightly higher difficulty and win any same-block-height race by default.
* Difficulty adjustment should adapt to sudden hashrate loss. Note: many altchains which have attempted this have created significant security vulnerabilities in the process, but experimentation continues.
* Scripts should be fully enabled after a careful audit.
* Miners/relays should not be able to inject extra arbitrary data into transactions?
* Use the previous block hash as an explicit or implicit prev_in in coinbases when hashing them to make it ~impossible to get a duplicate coinbase, thus removing the need for a pruning node to remember coinbase hashes to prevent duplicates consistently with the rest of the network. Note that this problem has already been solved with a softfork in [https://bitcointalk.org/index.php?topic=92558.0 BIP34].
* coinbases must be parseable.
This changes would involve converting old blocks:
* uint64_t for timestamp field in blocks.

==See Also==
*[[Prohibited changes]]

==References==
<references />

[[Category:Technical]]
[[Category:Developer]]

Hardfork Wishlist

2014-03-22T17:03:52Z

Eldentyrell: mention that altchain experimentation with difficulty adjustments continues; it's not hopeless, but it's definitely not solved yet either.

The '''Hardfork Wishlist''' is to record changes to Bitcoin that might be desirable, but that will require a "hard" block-chain split (everybody must upgrade, old software will not accept blocks/transactions created with the new [[Protocol rules|rules]], considering them to be [[Invalid block|invalid blocks]]).

This page is ''not'' for changes that can be accomplished in way that is compatible with old software (for example, by making transactions [[Nonstandard block|nonstandard]] or by [[Discouraged block|discouraging blocks]]).

== Changes to hard-coded limits ==
* Replace hard-coded maximum block size (1,000,000 bytes) and maximum number of signature operations per block (20,000) with ???.

== Major structural changes ==
* "Flip the chain", instead of committing to new transactions, commit to the summaries of open transactions: [https://bitcointalk.org/index.php?topic=505.0] [https://bitcointalk.org/index.php?topic=21995.0] [https://en.bitcoin.it/wiki/User:DiThi/MTUT#PROPOSAL:_Merkle_tree_of_unspent_transactions_.28MTUT.29.2C_for_serverless_thin_clients_and_self-verifiable_prunned_blockchain.] [https://bitcointalk.org/index.php?topic=88208.0]
* Increased efficiency for merged mining: restructure the primary header to make the bitcoin specific data non-mandatory. (e.g. the block chain specific stuff would go into second header connected by a header tree), making the primary headers pure timestamps and nonces.
* Switch to block hashing algorithm secure against block withholding attacks.
* Require a [https://en.bitcoin.it/wiki/Thin_Client_Security#Unused_Output_Tree_in_the_Blockchain_.28UOT.29 UTXO tree] in every block

== Transaction behavior changes==
* Improved signature types to allow for partial malleability of outputs. (e.g. make it easier to add a fee onto someone else's transaction, or to take fees from a transaction without outputs set aside for that purpose)
* Elimination of output scripts: all transactions pay-to-scripthash, probably with a single byte indicating the scripthash type. Other than reducing effective output script secrecy (which is not possible without OP_EVAL anyways) this is believed to be costless, and the secrecy can be recovered with recursive OP_EVAL. The motivation here is that data in outputs is far more expensive than inputs because some outputs may be never prunable, and pay-to-scripthash minimizes output size without harming total size.
* Allow soft-spending of generation outputs without confirmations (outputs of these transactions might also appear as generation themselves)
* Allow additional inputs to generation transactions
* Add new signature hashtype to include value of TxOut being spent, in the hash to be signed. Doing this would remove the requirement that offline signing devices be sent all supporting transactions with the transaction-to-be-signed, just to confirm the transaction fee.

== Cryptographic changes==
* Pervasive ECC public key-recovery to reduce transaction sizes (can be done partially without breaking compatibility completely)
* [http://ed25519.cr.yp.to/ Ed25519] (variant*) for much faster validation operations. (variant because the normal way Ed25519 is specified is not key recovery compatible)
* Support for more than one public-key cryptosystem (ECDSA-k1) and key size (256bits) as a hedge against future cryptanalysis or designed-in flaws in any one algorithm. Every node must support validation of signatures with every cryptosystem, but a small number of very-cryptograpically-diverse options is still better than just one. Additional signature types could be kludged into the existing system with script extensions but would be better supported natively.
* Support for a [http://en.wikipedia.org/wiki/Post-quantum_cryptography post-quantum] signature scheme. [http://en.wikipedia.org/wiki/Lamport_signature Lamport signatures] have nice intuitive security properties, but it has extreme space requirements that would require structural changes to the blockchain to accommodate, (e.g. flip-chain+paytoscripthash+extensive pruning). However other post-quantum schemes like [http://en.wikipedia.org/wiki/NTRU IEEE1363.1] (patent expires in 2016) do not. See the [http://pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf introductory chapter of DJB's book] and the [http://pqcrypto.org PQCrypto conference webpage] for full details.

== Privacy ==
* Better privacy using [http://en.wikipedia.org/wiki/Non-interactive_zero-knowledge_proof NIZKP]s, as proposed in [http://zerocoin.org Zerocoin] or similar.

== Currency changes==
''Please don't list anything here which would significantly change the committed overall economics of the system, it's safe to assume anything with significant economic impact will _never_ be changed in Bitcoin<ref>[http://bitcointalk.org/index.php?topic=45468.msg542375#msg542375 Suggested MAJOR change to Bitcoin]</ref>, because such changes would undermine the trust people have in the system, though they may form the basis of an interesting [[alternative chain]].
* Increase currency divisibility.

== Navel gazing / Protocol housekeeping==
* Byte order consistency (big endian)
* Eliminate redundancies in the variable length integer encodings, possibly switch to a standard.
* Avoiding hashes covering malleable fields

== Bug fixes ==
* CHECKMULTISIG popping one-too-many items off the stack
* Difficulty adjustment periods should overlap (prevent potential 'timejacking') Note: An ideal adjustment algorithm would ensure there is no easy dispute on "next target" for any block. Eg, it should not be possible for MinerX to set his block time 2 hours in the future to achieve a slightly higher difficulty and win any same-block-height race by default.
* Difficulty adjustment should adapt to sudden hashrate loss. Note: many altchains which have attempted this have created significant security vulnerabilities in the process, but experimentation continues.
* Scripts should be fully enabled after a careful audit.
* Miners/relays should not be able to inject extra arbitrary data into transactions?
* Use the previous block hash as an explicit or implicit prev_in in coinbases when hashing them to make it ~impossible to get a duplicate coinbase, thus removing the need for a pruning node to remember coinbase hashes to prevent duplicates consistently with the rest of the network. Note that this problem has already been solved with a softfork in [https://bitcointalk.org/index.php?topic=92558.0 BIP34].
* coinbases must be parseable.
This changes would involve converting old blocks:
* uint64_t for timestamp field in blocks.

==See Also==
*[[Prohibited changes]]

==References==
<references />

[[Category:Technical]]
[[Category:Developer]]

Hardfork Wishlist

2014-03-22T17:02:59Z

Eldentyrell: Delete comment about "interested parties…"; the incentive structure there does not work (tragedy of the commons)

The '''Hardfork Wishlist''' is to record changes to Bitcoin that might be desirable, but that will require a "hard" block-chain split (everybody must upgrade, old software will not accept blocks/transactions created with the new [[Protocol rules|rules]], considering them to be [[Invalid block|invalid blocks]]).

This page is ''not'' for changes that can be accomplished in way that is compatible with old software (for example, by making transactions [[Nonstandard block|nonstandard]] or by [[Discouraged block|discouraging blocks]]).

== Changes to hard-coded limits ==
* Replace hard-coded maximum block size (1,000,000 bytes) and maximum number of signature operations per block (20,000) with ???.

== Major structural changes ==
* "Flip the chain", instead of committing to new transactions, commit to the summaries of open transactions: [https://bitcointalk.org/index.php?topic=505.0] [https://bitcointalk.org/index.php?topic=21995.0] [https://en.bitcoin.it/wiki/User:DiThi/MTUT#PROPOSAL:_Merkle_tree_of_unspent_transactions_.28MTUT.29.2C_for_serverless_thin_clients_and_self-verifiable_prunned_blockchain.] [https://bitcointalk.org/index.php?topic=88208.0]
* Increased efficiency for merged mining: restructure the primary header to make the bitcoin specific data non-mandatory. (e.g. the block chain specific stuff would go into second header connected by a header tree), making the primary headers pure timestamps and nonces.
* Switch to block hashing algorithm secure against block withholding attacks.
* Require a [https://en.bitcoin.it/wiki/Thin_Client_Security#Unused_Output_Tree_in_the_Blockchain_.28UOT.29 UTXO tree] in every block

== Transaction behavior changes==
* Improved signature types to allow for partial malleability of outputs. (e.g. make it easier to add a fee onto someone else's transaction, or to take fees from a transaction without outputs set aside for that purpose)
* Elimination of output scripts: all transactions pay-to-scripthash, probably with a single byte indicating the scripthash type. Other than reducing effective output script secrecy (which is not possible without OP_EVAL anyways) this is believed to be costless, and the secrecy can be recovered with recursive OP_EVAL. The motivation here is that data in outputs is far more expensive than inputs because some outputs may be never prunable, and pay-to-scripthash minimizes output size without harming total size.
* Allow soft-spending of generation outputs without confirmations (outputs of these transactions might also appear as generation themselves)
* Allow additional inputs to generation transactions
* Add new signature hashtype to include value of TxOut being spent, in the hash to be signed. Doing this would remove the requirement that offline signing devices be sent all supporting transactions with the transaction-to-be-signed, just to confirm the transaction fee.

== Cryptographic changes==
* Pervasive ECC public key-recovery to reduce transaction sizes (can be done partially without breaking compatibility completely)
* [http://ed25519.cr.yp.to/ Ed25519] (variant*) for much faster validation operations. (variant because the normal way Ed25519 is specified is not key recovery compatible)
* Support for more than one public-key cryptosystem (ECDSA-k1) and key size (256bits) as a hedge against future cryptanalysis or designed-in flaws in any one algorithm. Every node must support validation of signatures with every cryptosystem, but a small number of very-cryptograpically-diverse options is still better than just one. Additional signature types could be kludged into the existing system with script extensions but would be better supported natively.
* Support for a [http://en.wikipedia.org/wiki/Post-quantum_cryptography post-quantum] signature scheme. [http://en.wikipedia.org/wiki/Lamport_signature Lamport signatures] have nice intuitive security properties, but it has extreme space requirements that would require structural changes to the blockchain to accommodate, (e.g. flip-chain+paytoscripthash+extensive pruning). However other post-quantum schemes like [http://en.wikipedia.org/wiki/NTRU IEEE1363.1] (patent expires in 2016) do not. See the [http://pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf introductory chapter of DJB's book] and the [http://pqcrypto.org PQCrypto conference webpage] for full details.

== Privacy ==
* Better privacy using [http://en.wikipedia.org/wiki/Non-interactive_zero-knowledge_proof NIZKP]s, as proposed in [http://zerocoin.org Zerocoin] or similar.

== Currency changes==
''Please don't list anything here which would significantly change the committed overall economics of the system, it's safe to assume anything with significant economic impact will _never_ be changed in Bitcoin<ref>[http://bitcointalk.org/index.php?topic=45468.msg542375#msg542375 Suggested MAJOR change to Bitcoin]</ref>, because such changes would undermine the trust people have in the system, though they may form the basis of an interesting [[alternative chain]].
* Increase currency divisibility.

== Navel gazing / Protocol housekeeping==
* Byte order consistency (big endian)
* Eliminate redundancies in the variable length integer encodings, possibly switch to a standard.
* Avoiding hashes covering malleable fields

== Bug fixes ==
* CHECKMULTISIG popping one-too-many items off the stack
* Difficulty adjustment periods should overlap (prevent potential 'timejacking') Note: An ideal adjustment algorithm would ensure there is no easy dispute on "next target" for any block. Eg, it should not be possible for MinerX to set his block time 2 hours in the future to achieve a slightly higher difficulty and win any same-block-height race by default.
* Difficulty adjustment should adapt to sudden hashrate loss. Note: all altchains which have attempted this have created significant security vulnerabilities in the process.
* Scripts should be fully enabled after a careful audit.
* Miners/relays should not be able to inject extra arbitrary data into transactions?
* Use the previous block hash as an explicit or implicit prev_in in coinbases when hashing them to make it ~impossible to get a duplicate coinbase, thus removing the need for a pruning node to remember coinbase hashes to prevent duplicates consistently with the rest of the network. Note that this problem has already been solved with a softfork in [https://bitcointalk.org/index.php?topic=92558.0 BIP34].
* coinbases must be parseable.
This changes would involve converting old blocks:
* uint64_t for timestamp field in blocks.

==See Also==
*[[Prohibited changes]]

==References==
<references />

[[Category:Technical]]
[[Category:Developer]]

Hardfork Wishlist

2014-03-22T17:01:33Z

Eldentyrell: Mention BIP34

The '''Hardfork Wishlist''' is to record changes to Bitcoin that might be desirable, but that will require a "hard" block-chain split (everybody must upgrade, old software will not accept blocks/transactions created with the new [[Protocol rules|rules]], considering them to be [[Invalid block|invalid blocks]]).

This page is ''not'' for changes that can be accomplished in way that is compatible with old software (for example, by making transactions [[Nonstandard block|nonstandard]] or by [[Discouraged block|discouraging blocks]]).

== Changes to hard-coded limits ==
* Replace hard-coded maximum block size (1,000,000 bytes) and maximum number of signature operations per block (20,000) with ???.

== Major structural changes ==
* "Flip the chain", instead of committing to new transactions, commit to the summaries of open transactions: [https://bitcointalk.org/index.php?topic=505.0] [https://bitcointalk.org/index.php?topic=21995.0] [https://en.bitcoin.it/wiki/User:DiThi/MTUT#PROPOSAL:_Merkle_tree_of_unspent_transactions_.28MTUT.29.2C_for_serverless_thin_clients_and_self-verifiable_prunned_blockchain.] [https://bitcointalk.org/index.php?topic=88208.0]
* Increased efficiency for merged mining: restructure the primary header to make the bitcoin specific data non-mandatory. (e.g. the block chain specific stuff would go into second header connected by a header tree), making the primary headers pure timestamps and nonces.
* Switch to block hashing algorithm secure against block withholding attacks.
* Require a [https://en.bitcoin.it/wiki/Thin_Client_Security#Unused_Output_Tree_in_the_Blockchain_.28UOT.29 UTXO tree] in every block

== Transaction behavior changes==
* Improved signature types to allow for partial malleability of outputs. (e.g. make it easier to add a fee onto someone else's transaction, or to take fees from a transaction without outputs set aside for that purpose)
* Elimination of output scripts: all transactions pay-to-scripthash, probably with a single byte indicating the scripthash type. Other than reducing effective output script secrecy (which is not possible without OP_EVAL anyways) this is believed to be costless, and the secrecy can be recovered with recursive OP_EVAL. The motivation here is that data in outputs is far more expensive than inputs because some outputs may be never prunable, and pay-to-scripthash minimizes output size without harming total size.
* Allow soft-spending of generation outputs without confirmations (outputs of these transactions might also appear as generation themselves)
* Allow additional inputs to generation transactions
* Add new signature hashtype to include value of TxOut being spent, in the hash to be signed. Doing this would remove the requirement that offline signing devices be sent all supporting transactions with the transaction-to-be-signed, just to confirm the transaction fee.

== Cryptographic changes==
* Pervasive ECC public key-recovery to reduce transaction sizes (can be done partially without breaking compatibility completely)
* [http://ed25519.cr.yp.to/ Ed25519] (variant*) for much faster validation operations. (variant because the normal way Ed25519 is specified is not key recovery compatible)
* Support for more than one public-key cryptosystem (ECDSA-k1) and key size (256bits) as a hedge against future cryptanalysis or designed-in flaws in any one algorithm. Every node must support validation of signatures with every cryptosystem, but a small number of very-cryptograpically-diverse options is still better than just one. Additional signature types could be kludged into the existing system with script extensions but would be better supported natively.
* Support for a [http://en.wikipedia.org/wiki/Post-quantum_cryptography post-quantum] signature scheme. [http://en.wikipedia.org/wiki/Lamport_signature Lamport signatures] have nice intuitive security properties, but it has extreme space requirements that would require structural changes to the blockchain to accommodate, (e.g. flip-chain+paytoscripthash+extensive pruning). However other post-quantum schemes like [http://en.wikipedia.org/wiki/NTRU IEEE1363.1] (patent expires in 2016) do not. See the [http://pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf introductory chapter of DJB's book] and the [http://pqcrypto.org PQCrypto conference webpage] for full details.

== Privacy ==
* Better privacy using [http://en.wikipedia.org/wiki/Non-interactive_zero-knowledge_proof NIZKP]s, as proposed in [http://zerocoin.org Zerocoin] or similar.

== Currency changes==
''Please don't list anything here which would significantly change the committed overall economics of the system, it's safe to assume anything with significant economic impact will _never_ be changed in Bitcoin<ref>[http://bitcointalk.org/index.php?topic=45468.msg542375#msg542375 Suggested MAJOR change to Bitcoin]</ref>, because such changes would undermine the trust people have in the system, though they may form the basis of an interesting [[alternative chain]].
* Increase currency divisibility.

== Navel gazing / Protocol housekeeping==
* Byte order consistency (big endian)
* Eliminate redundancies in the variable length integer encodings, possibly switch to a standard.
* Avoiding hashes covering malleable fields

== Bug fixes ==
* CHECKMULTISIG popping one-too-many items off the stack
* Difficulty adjustment periods should overlap (prevent potential 'timejacking') Note: An ideal adjustment algorithm would ensure there is no easy dispute on "next target" for any block. Eg, it should not be possible for MinerX to set his block time 2 hours in the future to achieve a slightly higher difficulty and win any same-block-height race by default.
* Difficulty adjustment should adapt to sudden hashrate loss. Note: all altchains which have attempted this have created significant security vulnerabilities in the process. Also interested parties could encourage mining by including high fee transactions in every block so avoiding need for this change.
* Scripts should be fully enabled after a careful audit.
* Miners/relays should not be able to inject extra arbitrary data into transactions?
* Use the previous block hash as an explicit or implicit prev_in in coinbases when hashing them to make it ~impossible to get a duplicate coinbase, thus removing the need for a pruning node to remember coinbase hashes to prevent duplicates consistently with the rest of the network. Note that this problem has already been solved with a softfork in [https://bitcointalk.org/index.php?topic=92558.0 BIP34].
* coinbases must be parseable.
This changes would involve converting old blocks:
* uint64_t for timestamp field in blocks.

==See Also==
*[[Prohibited changes]]

==References==
<references />

[[Category:Technical]]
[[Category:Developer]]

Hardfork Wishlist

2014-03-22T16:59:33Z

Eldentyrell: Add privacy section with NIZKPs

The '''Hardfork Wishlist''' is to record changes to Bitcoin that might be desirable, but that will require a "hard" block-chain split (everybody must upgrade, old software will not accept blocks/transactions created with the new [[Protocol rules|rules]], considering them to be [[Invalid block|invalid blocks]]).

This page is ''not'' for changes that can be accomplished in way that is compatible with old software (for example, by making transactions [[Nonstandard block|nonstandard]] or by [[Discouraged block|discouraging blocks]]).

== Changes to hard-coded limits ==
* Replace hard-coded maximum block size (1,000,000 bytes) and maximum number of signature operations per block (20,000) with ???.

== Major structural changes ==
* "Flip the chain", instead of committing to new transactions, commit to the summaries of open transactions: [https://bitcointalk.org/index.php?topic=505.0] [https://bitcointalk.org/index.php?topic=21995.0] [https://en.bitcoin.it/wiki/User:DiThi/MTUT#PROPOSAL:_Merkle_tree_of_unspent_transactions_.28MTUT.29.2C_for_serverless_thin_clients_and_self-verifiable_prunned_blockchain.] [https://bitcointalk.org/index.php?topic=88208.0]
* Increased efficiency for merged mining: restructure the primary header to make the bitcoin specific data non-mandatory. (e.g. the block chain specific stuff would go into second header connected by a header tree), making the primary headers pure timestamps and nonces.
* Switch to block hashing algorithm secure against block withholding attacks.
* Require a [https://en.bitcoin.it/wiki/Thin_Client_Security#Unused_Output_Tree_in_the_Blockchain_.28UOT.29 UTXO tree] in every block

== Transaction behavior changes==
* Improved signature types to allow for partial malleability of outputs. (e.g. make it easier to add a fee onto someone else's transaction, or to take fees from a transaction without outputs set aside for that purpose)
* Elimination of output scripts: all transactions pay-to-scripthash, probably with a single byte indicating the scripthash type. Other than reducing effective output script secrecy (which is not possible without OP_EVAL anyways) this is believed to be costless, and the secrecy can be recovered with recursive OP_EVAL. The motivation here is that data in outputs is far more expensive than inputs because some outputs may be never prunable, and pay-to-scripthash minimizes output size without harming total size.
* Allow soft-spending of generation outputs without confirmations (outputs of these transactions might also appear as generation themselves)
* Allow additional inputs to generation transactions
* Add new signature hashtype to include value of TxOut being spent, in the hash to be signed. Doing this would remove the requirement that offline signing devices be sent all supporting transactions with the transaction-to-be-signed, just to confirm the transaction fee.

== Cryptographic changes==
* Pervasive ECC public key-recovery to reduce transaction sizes (can be done partially without breaking compatibility completely)
* [http://ed25519.cr.yp.to/ Ed25519] (variant*) for much faster validation operations. (variant because the normal way Ed25519 is specified is not key recovery compatible)
* Support for more than one public-key cryptosystem (ECDSA-k1) and key size (256bits) as a hedge against future cryptanalysis or designed-in flaws in any one algorithm. Every node must support validation of signatures with every cryptosystem, but a small number of very-cryptograpically-diverse options is still better than just one. Additional signature types could be kludged into the existing system with script extensions but would be better supported natively.
* Support for a [http://en.wikipedia.org/wiki/Post-quantum_cryptography post-quantum] signature scheme. [http://en.wikipedia.org/wiki/Lamport_signature Lamport signatures] have nice intuitive security properties, but it has extreme space requirements that would require structural changes to the blockchain to accommodate, (e.g. flip-chain+paytoscripthash+extensive pruning). However other post-quantum schemes like [http://en.wikipedia.org/wiki/NTRU IEEE1363.1] (patent expires in 2016) do not. See the [http://pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf introductory chapter of DJB's book] and the [http://pqcrypto.org PQCrypto conference webpage] for full details.

== Privacy ==
* Better privacy using [http://en.wikipedia.org/wiki/Non-interactive_zero-knowledge_proof NIZKP]s, as proposed in [http://zerocoin.org Zerocoin] or similar.

== Currency changes==
''Please don't list anything here which would significantly change the committed overall economics of the system, it's safe to assume anything with significant economic impact will _never_ be changed in Bitcoin<ref>[http://bitcointalk.org/index.php?topic=45468.msg542375#msg542375 Suggested MAJOR change to Bitcoin]</ref>, because such changes would undermine the trust people have in the system, though they may form the basis of an interesting [[alternative chain]].
* Increase currency divisibility.

== Navel gazing / Protocol housekeeping==
* Byte order consistency (big endian)
* Eliminate redundancies in the variable length integer encodings, possibly switch to a standard.
* Avoiding hashes covering malleable fields

== Bug fixes ==
* CHECKMULTISIG popping one-too-many items off the stack
* Difficulty adjustment periods should overlap (prevent potential 'timejacking') Note: An ideal adjustment algorithm would ensure there is no easy dispute on "next target" for any block. Eg, it should not be possible for MinerX to set his block time 2 hours in the future to achieve a slightly higher difficulty and win any same-block-height race by default.
* Difficulty adjustment should adapt to sudden hashrate loss. Note: all altchains which have attempted this have created significant security vulnerabilities in the process. Also interested parties could encourage mining by including high fee transactions in every block so avoiding need for this change.
* Scripts should be fully enabled after a careful audit.
* Miners/relays should not be able to inject extra arbitrary data into transactions?
* Use the previous block hash as an explicit or implicit prev_in in coinbases when hashing them to make it ~impossible to get a duplicate coinbase, thus removing the need for a pruning node to remember coinbase hashes to prevent duplicates consistently with the rest of the network
* coinbases must be parseable.
This changes would involve converting old blocks:
* uint64_t for timestamp field in blocks.

==See Also==
*[[Prohibited changes]]

==References==
<references />

[[Category:Technical]]
[[Category:Developer]]

Prohibited changes

2014-03-22T16:54:11Z

Eldentyrell: add Demurrage, if only because namecoin is already doing it.

These changes are considered to be against the spirit of Bitcoin. Even if ''all'' Bitcoin users decide to adopt any of these changes, the resulting cryptocurrency can no longer be considered "Bitcoin" because it has diverged too much from the original design.

=== Require unanimous consent ===

These changes require the consent of every bitcoin-holder:
* Increasing the total number of issued bitcoins beyond 21 million. Precision may be increased, but proportions must be unchanged.
* Any rule that adds required, explicit centralization. For example, a change requiring that all blocks be signed by some central organization.
* [http://en.wikipedia.org/wiki/Demurrage_(currency) Demurrage] (deletion or reassignment of coins judged to be "lost" or "unused"). This is highly controversial in the context of currency units; on the other hand it is absolutely essential for namespace entries like [Namecoin] (which implements Demurrage for namespace entries but not for currency units).

=== Require miner consensus ===
* Changing the bitcoin distribution algorithm such that the subsidy at any given time period is decreased without miner consensus and 3 years notice, or increased beyond improved precision of halving (lossy beginning with block 1,890,000).

=== Disputed ===
* Adding alternatives to [[Proof of Work]] such as [[Proof of Stake]]. This could change core bitcoin too much, but with widespread agreement of some sort might be possible.

== See Also ==
[[Hardfork Wishlist]] for hard forks that might happen and still be called "Bitcoin".

Hardfork Wishlist

2014-03-22T16:51:52Z

Eldentyrell: /* Major structural changes */

The '''Hardfork Wishlist''' is to record changes to Bitcoin that might be desirable, but that will require a "hard" block-chain split (everybody must upgrade, old software will not accept blocks/transactions created with the new [[Protocol rules|rules]], considering them to be [[Invalid block|invalid blocks]]).

This page is ''not'' for changes that can be accomplished in way that is compatible with old software (for example, by making transactions [[Nonstandard block|nonstandard]] or by [[Discouraged block|discouraging blocks]]).

== Changes to hard-coded limits ==
* Replace hard-coded maximum block size (1,000,000 bytes) and maximum number of signature operations per block (20,000) with ???.

== Major structural changes ==
* "Flip the chain", instead of committing to new transactions, commit to the summaries of open transactions: [https://bitcointalk.org/index.php?topic=505.0] [https://bitcointalk.org/index.php?topic=21995.0] [https://en.bitcoin.it/wiki/User:DiThi/MTUT#PROPOSAL:_Merkle_tree_of_unspent_transactions_.28MTUT.29.2C_for_serverless_thin_clients_and_self-verifiable_prunned_blockchain.] [https://bitcointalk.org/index.php?topic=88208.0]
* Increased efficiency for merged mining: restructure the primary header to make the bitcoin specific data non-mandatory. (e.g. the block chain specific stuff would go into second header connected by a header tree), making the primary headers pure timestamps and nonces.
* Switch to block hashing algorithm secure against block withholding attacks.
* Require a [https://en.bitcoin.it/wiki/Thin_Client_Security#Unused_Output_Tree_in_the_Blockchain_.28UOT.29 UTXO tree] in every block

== Transaction behavior changes==
* Improved signature types to allow for partial malleability of outputs. (e.g. make it easier to add a fee onto someone else's transaction, or to take fees from a transaction without outputs set aside for that purpose)
* Elimination of output scripts: all transactions pay-to-scripthash, probably with a single byte indicating the scripthash type. Other than reducing effective output script secrecy (which is not possible without OP_EVAL anyways) this is believed to be costless, and the secrecy can be recovered with recursive OP_EVAL. The motivation here is that data in outputs is far more expensive than inputs because some outputs may be never prunable, and pay-to-scripthash minimizes output size without harming total size.
* Allow soft-spending of generation outputs without confirmations (outputs of these transactions might also appear as generation themselves)
* Allow additional inputs to generation transactions
* Add new signature hashtype to include value of TxOut being spent, in the hash to be signed. Doing this would remove the requirement that offline signing devices be sent all supporting transactions with the transaction-to-be-signed, just to confirm the transaction fee.

== Cryptographic changes==
* Pervasive ECC public key-recovery to reduce transaction sizes (can be done partially without breaking compatibility completely)
* [http://ed25519.cr.yp.to/ Ed25519] (variant*) for much faster validation operations. (variant because the normal way Ed25519 is specified is not key recovery compatible)
* Support for more than one public-key cryptosystem (ECDSA-k1) and key size (256bits) as a hedge against future cryptanalysis or designed-in flaws in any one algorithm. Every node must support validation of signatures with every cryptosystem, but a small number of very-cryptograpically-diverse options is still better than just one. Additional signature types could be kludged into the existing system with script extensions but would be better supported natively.
* Support for a [http://en.wikipedia.org/wiki/Post-quantum_cryptography post-quantum] signature scheme. [http://en.wikipedia.org/wiki/Lamport_signature Lamport signatures] have nice intuitive security properties, but it has extreme space requirements that would require structural changes to the blockchain to accommodate, (e.g. flip-chain+paytoscripthash+extensive pruning). However other post-quantum schemes like [http://en.wikipedia.org/wiki/NTRU IEEE1363.1] (patent expires in 2016) do not. See the [http://pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf introductory chapter of DJB's book] and the [http://pqcrypto.org PQCrypto conference webpage] for full details.

== Currency changes==
''Please don't list anything here which would significantly change the committed overall economics of the system, it's safe to assume anything with significant economic impact will _never_ be changed in Bitcoin<ref>[http://bitcointalk.org/index.php?topic=45468.msg542375#msg542375 Suggested MAJOR change to Bitcoin]</ref>, because such changes would undermine the trust people have in the system, though they may form the basis of an interesting [[alternative chain]].
* Increase currency divisibility.

== Navel gazing / Protocol housekeeping==
* Byte order consistency (big endian)
* Eliminate redundancies in the variable length integer encodings, possibly switch to a standard.
* Avoiding hashes covering malleable fields

== Bug fixes ==
* CHECKMULTISIG popping one-too-many items off the stack
* Difficulty adjustment periods should overlap (prevent potential 'timejacking') Note: An ideal adjustment algorithm would ensure there is no easy dispute on "next target" for any block. Eg, it should not be possible for MinerX to set his block time 2 hours in the future to achieve a slightly higher difficulty and win any same-block-height race by default.
* Difficulty adjustment should adapt to sudden hashrate loss. Note: all altchains which have attempted this have created significant security vulnerabilities in the process. Also interested parties could encourage mining by including high fee transactions in every block so avoiding need for this change.
* Scripts should be fully enabled after a careful audit.
* Miners/relays should not be able to inject extra arbitrary data into transactions?
* Use the previous block hash as an explicit or implicit prev_in in coinbases when hashing them to make it ~impossible to get a duplicate coinbase, thus removing the need for a pruning node to remember coinbase hashes to prevent duplicates consistently with the rest of the network
* coinbases must be parseable.
This changes would involve converting old blocks:
* uint64_t for timestamp field in blocks.

==See Also==
*[[Prohibited changes]]

==References==
<references />

[[Category:Technical]]
[[Category:Developer]]

Hardfork Wishlist

2014-03-22T16:47:50Z

Eldentyrell: /* Cryptographic changes */

The '''Hardfork Wishlist''' is to record changes to Bitcoin that might be desirable, but that will require a "hard" block-chain split (everybody must upgrade, old software will not accept blocks/transactions created with the new [[Protocol rules|rules]], considering them to be [[Invalid block|invalid blocks]]).

This page is ''not'' for changes that can be accomplished in way that is compatible with old software (for example, by making transactions [[Nonstandard block|nonstandard]] or by [[Discouraged block|discouraging blocks]]).

== Changes to hard-coded limits ==
* Replace hard-coded maximum block size (1,000,000 bytes) and maximum number of signature operations per block (20,000) with ???.

== Major structural changes ==
* "Flip the chain", instead of committing to new transactions, commit to the summaries of open transactions: [https://bitcointalk.org/index.php?topic=505.0] [https://bitcointalk.org/index.php?topic=21995.0] [https://en.bitcoin.it/wiki/User:DiThi/MTUT#PROPOSAL:_Merkle_tree_of_unspent_transactions_.28MTUT.29.2C_for_serverless_thin_clients_and_self-verifiable_prunned_blockchain.] [https://bitcointalk.org/index.php?topic=88208.0]
* Increased efficiency for merged mining: restructure the primary header to make the bitcoin specific data non-mandatory. (e.g. the block chain specific stuff would go into second header connected by a header tree), making the primary headers pure timestamps and nonces.
* Switch to block hashing algorithm secure against block withholding attacks.

== Transaction behavior changes==
* Improved signature types to allow for partial malleability of outputs. (e.g. make it easier to add a fee onto someone else's transaction, or to take fees from a transaction without outputs set aside for that purpose)
* Elimination of output scripts: all transactions pay-to-scripthash, probably with a single byte indicating the scripthash type. Other than reducing effective output script secrecy (which is not possible without OP_EVAL anyways) this is believed to be costless, and the secrecy can be recovered with recursive OP_EVAL. The motivation here is that data in outputs is far more expensive than inputs because some outputs may be never prunable, and pay-to-scripthash minimizes output size without harming total size.
* Allow soft-spending of generation outputs without confirmations (outputs of these transactions might also appear as generation themselves)
* Allow additional inputs to generation transactions
* Add new signature hashtype to include value of TxOut being spent, in the hash to be signed. Doing this would remove the requirement that offline signing devices be sent all supporting transactions with the transaction-to-be-signed, just to confirm the transaction fee.

== Cryptographic changes==
* Pervasive ECC public key-recovery to reduce transaction sizes (can be done partially without breaking compatibility completely)
* [http://ed25519.cr.yp.to/ Ed25519] (variant*) for much faster validation operations. (variant because the normal way Ed25519 is specified is not key recovery compatible)
* Support for more than one public-key cryptosystem (ECDSA-k1) and key size (256bits) as a hedge against future cryptanalysis or designed-in flaws in any one algorithm. Every node must support validation of signatures with every cryptosystem, but a small number of very-cryptograpically-diverse options is still better than just one. Additional signature types could be kludged into the existing system with script extensions but would be better supported natively.
* Support for a [http://en.wikipedia.org/wiki/Post-quantum_cryptography post-quantum] signature scheme. [http://en.wikipedia.org/wiki/Lamport_signature Lamport signatures] have nice intuitive security properties, but it has extreme space requirements that would require structural changes to the blockchain to accommodate, (e.g. flip-chain+paytoscripthash+extensive pruning). However other post-quantum schemes like [http://en.wikipedia.org/wiki/NTRU IEEE1363.1] (patent expires in 2016) do not. See the [http://pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf introductory chapter of DJB's book] and the [http://pqcrypto.org PQCrypto conference webpage] for full details.

== Currency changes==
''Please don't list anything here which would significantly change the committed overall economics of the system, it's safe to assume anything with significant economic impact will _never_ be changed in Bitcoin<ref>[http://bitcointalk.org/index.php?topic=45468.msg542375#msg542375 Suggested MAJOR change to Bitcoin]</ref>, because such changes would undermine the trust people have in the system, though they may form the basis of an interesting [[alternative chain]].
* Increase currency divisibility.

== Navel gazing / Protocol housekeeping==
* Byte order consistency (big endian)
* Eliminate redundancies in the variable length integer encodings, possibly switch to a standard.
* Avoiding hashes covering malleable fields

== Bug fixes ==
* CHECKMULTISIG popping one-too-many items off the stack
* Difficulty adjustment periods should overlap (prevent potential 'timejacking') Note: An ideal adjustment algorithm would ensure there is no easy dispute on "next target" for any block. Eg, it should not be possible for MinerX to set his block time 2 hours in the future to achieve a slightly higher difficulty and win any same-block-height race by default.
* Difficulty adjustment should adapt to sudden hashrate loss. Note: all altchains which have attempted this have created significant security vulnerabilities in the process. Also interested parties could encourage mining by including high fee transactions in every block so avoiding need for this change.
* Scripts should be fully enabled after a careful audit.
* Miners/relays should not be able to inject extra arbitrary data into transactions?
* Use the previous block hash as an explicit or implicit prev_in in coinbases when hashing them to make it ~impossible to get a duplicate coinbase, thus removing the need for a pruning node to remember coinbase hashes to prevent duplicates consistently with the rest of the network
* coinbases must be parseable.
This changes would involve converting old blocks:
* uint64_t for timestamp field in blocks.

==See Also==
*[[Prohibited changes]]

==References==
<references />

[[Category:Technical]]
[[Category:Developer]]

Hardfork Wishlist

2014-03-22T16:47:37Z

Eldentyrell: /* Cryptographic changes */

The '''Hardfork Wishlist''' is to record changes to Bitcoin that might be desirable, but that will require a "hard" block-chain split (everybody must upgrade, old software will not accept blocks/transactions created with the new [[Protocol rules|rules]], considering them to be [[Invalid block|invalid blocks]]).

This page is ''not'' for changes that can be accomplished in way that is compatible with old software (for example, by making transactions [[Nonstandard block|nonstandard]] or by [[Discouraged block|discouraging blocks]]).

== Changes to hard-coded limits ==
* Replace hard-coded maximum block size (1,000,000 bytes) and maximum number of signature operations per block (20,000) with ???.

== Major structural changes ==
* "Flip the chain", instead of committing to new transactions, commit to the summaries of open transactions: [https://bitcointalk.org/index.php?topic=505.0] [https://bitcointalk.org/index.php?topic=21995.0] [https://en.bitcoin.it/wiki/User:DiThi/MTUT#PROPOSAL:_Merkle_tree_of_unspent_transactions_.28MTUT.29.2C_for_serverless_thin_clients_and_self-verifiable_prunned_blockchain.] [https://bitcointalk.org/index.php?topic=88208.0]
* Increased efficiency for merged mining: restructure the primary header to make the bitcoin specific data non-mandatory. (e.g. the block chain specific stuff would go into second header connected by a header tree), making the primary headers pure timestamps and nonces.
* Switch to block hashing algorithm secure against block withholding attacks.

== Transaction behavior changes==
* Improved signature types to allow for partial malleability of outputs. (e.g. make it easier to add a fee onto someone else's transaction, or to take fees from a transaction without outputs set aside for that purpose)
* Elimination of output scripts: all transactions pay-to-scripthash, probably with a single byte indicating the scripthash type. Other than reducing effective output script secrecy (which is not possible without OP_EVAL anyways) this is believed to be costless, and the secrecy can be recovered with recursive OP_EVAL. The motivation here is that data in outputs is far more expensive than inputs because some outputs may be never prunable, and pay-to-scripthash minimizes output size without harming total size.
* Allow soft-spending of generation outputs without confirmations (outputs of these transactions might also appear as generation themselves)
* Allow additional inputs to generation transactions
* Add new signature hashtype to include value of TxOut being spent, in the hash to be signed. Doing this would remove the requirement that offline signing devices be sent all supporting transactions with the transaction-to-be-signed, just to confirm the transaction fee.

== Cryptographic changes==
* Pervasive ECC public key-recovery to reduce transaction sizes (can be done partially without breaking compatibility completely)
* [http://ed25519.cr.yp.to/ Ed25519] (variant*) for much faster validation operations. (variant because the normal way Ed25519 is specified is not key recovery compatible)
* Support for more than one public-key cryptosystem (ECDSA-k1) and key size (256bits) as a hedge against future cryptanalysis or designed-in flaws in any one algorithm. Every node must support validation of signatures with every cryptosystem, but a small number of very-cryptograpically-diverse options is still better than just one. Additional signature types could be kludged into the existing system with script extensions but would be better supported natively.
* Support for a [http://en.wikipedia.org/wiki/Post-quantum_cryptography post-quantum] signature scheme. [http://en.wikipedia.org/wiki/Lamport_signature Lamport signatures] have nice intuitive security properties, but it has extreme space requirements that would require structural changes to the blockchain to accommodate, (e.g. flip-chain+paytoscripthash+extensive pruning). However other post-quantum schemes like [[http://en.wikipedia.org/wiki/NTRU IEEE1363.1]] (patent expires in 2016) do not. See the [http://pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf introductory chapter of DJB's book] and the [http://pqcrypto.org PQCrypto conference webpage] for full details.

== Currency changes==
''Please don't list anything here which would significantly change the committed overall economics of the system, it's safe to assume anything with significant economic impact will _never_ be changed in Bitcoin<ref>[http://bitcointalk.org/index.php?topic=45468.msg542375#msg542375 Suggested MAJOR change to Bitcoin]</ref>, because such changes would undermine the trust people have in the system, though they may form the basis of an interesting [[alternative chain]].
* Increase currency divisibility.

== Navel gazing / Protocol housekeeping==
* Byte order consistency (big endian)
* Eliminate redundancies in the variable length integer encodings, possibly switch to a standard.
* Avoiding hashes covering malleable fields

== Bug fixes ==
* CHECKMULTISIG popping one-too-many items off the stack
* Difficulty adjustment periods should overlap (prevent potential 'timejacking') Note: An ideal adjustment algorithm would ensure there is no easy dispute on "next target" for any block. Eg, it should not be possible for MinerX to set his block time 2 hours in the future to achieve a slightly higher difficulty and win any same-block-height race by default.
* Difficulty adjustment should adapt to sudden hashrate loss. Note: all altchains which have attempted this have created significant security vulnerabilities in the process. Also interested parties could encourage mining by including high fee transactions in every block so avoiding need for this change.
* Scripts should be fully enabled after a careful audit.
* Miners/relays should not be able to inject extra arbitrary data into transactions?
* Use the previous block hash as an explicit or implicit prev_in in coinbases when hashing them to make it ~impossible to get a duplicate coinbase, thus removing the need for a pruning node to remember coinbase hashes to prevent duplicates consistently with the rest of the network
* coinbases must be parseable.
This changes would involve converting old blocks:
* uint64_t for timestamp field in blocks.

==See Also==
*[[Prohibited changes]]

==References==
<references />

[[Category:Technical]]
[[Category:Developer]]

Hardfork Wishlist

2014-03-22T16:47:16Z

Eldentyrell: /* Cryptographic changes */

The '''Hardfork Wishlist''' is to record changes to Bitcoin that might be desirable, but that will require a "hard" block-chain split (everybody must upgrade, old software will not accept blocks/transactions created with the new [[Protocol rules|rules]], considering them to be [[Invalid block|invalid blocks]]).

This page is ''not'' for changes that can be accomplished in way that is compatible with old software (for example, by making transactions [[Nonstandard block|nonstandard]] or by [[Discouraged block|discouraging blocks]]).

== Changes to hard-coded limits ==
* Replace hard-coded maximum block size (1,000,000 bytes) and maximum number of signature operations per block (20,000) with ???.

== Major structural changes ==
* "Flip the chain", instead of committing to new transactions, commit to the summaries of open transactions: [https://bitcointalk.org/index.php?topic=505.0] [https://bitcointalk.org/index.php?topic=21995.0] [https://en.bitcoin.it/wiki/User:DiThi/MTUT#PROPOSAL:_Merkle_tree_of_unspent_transactions_.28MTUT.29.2C_for_serverless_thin_clients_and_self-verifiable_prunned_blockchain.] [https://bitcointalk.org/index.php?topic=88208.0]
* Increased efficiency for merged mining: restructure the primary header to make the bitcoin specific data non-mandatory. (e.g. the block chain specific stuff would go into second header connected by a header tree), making the primary headers pure timestamps and nonces.
* Switch to block hashing algorithm secure against block withholding attacks.

== Transaction behavior changes==
* Improved signature types to allow for partial malleability of outputs. (e.g. make it easier to add a fee onto someone else's transaction, or to take fees from a transaction without outputs set aside for that purpose)
* Elimination of output scripts: all transactions pay-to-scripthash, probably with a single byte indicating the scripthash type. Other than reducing effective output script secrecy (which is not possible without OP_EVAL anyways) this is believed to be costless, and the secrecy can be recovered with recursive OP_EVAL. The motivation here is that data in outputs is far more expensive than inputs because some outputs may be never prunable, and pay-to-scripthash minimizes output size without harming total size.
* Allow soft-spending of generation outputs without confirmations (outputs of these transactions might also appear as generation themselves)
* Allow additional inputs to generation transactions
* Add new signature hashtype to include value of TxOut being spent, in the hash to be signed. Doing this would remove the requirement that offline signing devices be sent all supporting transactions with the transaction-to-be-signed, just to confirm the transaction fee.

== Cryptographic changes==
* Pervasive ECC public key-recovery to reduce transaction sizes (can be done partially without breaking compatibility completely)
* [http://ed25519.cr.yp.to/ Ed25519] (variant*) for much faster validation operations. (variant because the normal way Ed25519 is specified is not key recovery compatible)
* Support for more than one public-key cryptosystem (ECDSA-k1) and key size (256bits) as a hedge against future cryptanalysis or designed-in flaws in any one algorithm. Every node must support validation of signatures with every cryptosystem, but a small number of very-cryptograpically-diverse options is still better than just one. Additional signature types could be kludged into the existing system with script extensions but would be better supported natively.
* Support for a [http://en.wikipedia.org/wiki/Post-quantum_cryptography post-quantum] signature scheme. [http://en.wikipedia.org/wiki/Lamport_signature Lamport signatures] have nice intuitive security properties, but it has extreme space requirements that would require structural changes to the blockchain to accommodate, (e.g. flip-chain+paytoscripthash+extensive pruning). However other post-quantum schemes like [[http://en.wikipedia.org/wiki/NTRU|IEEE1363.1]] do not. See the [http://pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf introductory chapter of DJB's book] and the [http://pqcrypto.org PQCrypto conference webpage] for full details.

== Currency changes==
''Please don't list anything here which would significantly change the committed overall economics of the system, it's safe to assume anything with significant economic impact will _never_ be changed in Bitcoin<ref>[http://bitcointalk.org/index.php?topic=45468.msg542375#msg542375 Suggested MAJOR change to Bitcoin]</ref>, because such changes would undermine the trust people have in the system, though they may form the basis of an interesting [[alternative chain]].
* Increase currency divisibility.

== Navel gazing / Protocol housekeeping==
* Byte order consistency (big endian)
* Eliminate redundancies in the variable length integer encodings, possibly switch to a standard.
* Avoiding hashes covering malleable fields

== Bug fixes ==
* CHECKMULTISIG popping one-too-many items off the stack
* Difficulty adjustment periods should overlap (prevent potential 'timejacking') Note: An ideal adjustment algorithm would ensure there is no easy dispute on "next target" for any block. Eg, it should not be possible for MinerX to set his block time 2 hours in the future to achieve a slightly higher difficulty and win any same-block-height race by default.
* Difficulty adjustment should adapt to sudden hashrate loss. Note: all altchains which have attempted this have created significant security vulnerabilities in the process. Also interested parties could encourage mining by including high fee transactions in every block so avoiding need for this change.
* Scripts should be fully enabled after a careful audit.
* Miners/relays should not be able to inject extra arbitrary data into transactions?
* Use the previous block hash as an explicit or implicit prev_in in coinbases when hashing them to make it ~impossible to get a duplicate coinbase, thus removing the need for a pruning node to remember coinbase hashes to prevent duplicates consistently with the rest of the network
* coinbases must be parseable.
This changes would involve converting old blocks:
* uint64_t for timestamp field in blocks.

==See Also==
*[[Prohibited changes]]

==References==
<references />

[[Category:Technical]]
[[Category:Developer]]

Hardfork Wishlist

2014-03-22T16:46:58Z

Eldentyrell: /* Cryptographic changes */

The '''Hardfork Wishlist''' is to record changes to Bitcoin that might be desirable, but that will require a "hard" block-chain split (everybody must upgrade, old software will not accept blocks/transactions created with the new [[Protocol rules|rules]], considering them to be [[Invalid block|invalid blocks]]).

This page is ''not'' for changes that can be accomplished in way that is compatible with old software (for example, by making transactions [[Nonstandard block|nonstandard]] or by [[Discouraged block|discouraging blocks]]).

== Changes to hard-coded limits ==
* Replace hard-coded maximum block size (1,000,000 bytes) and maximum number of signature operations per block (20,000) with ???.

== Major structural changes ==
* "Flip the chain", instead of committing to new transactions, commit to the summaries of open transactions: [https://bitcointalk.org/index.php?topic=505.0] [https://bitcointalk.org/index.php?topic=21995.0] [https://en.bitcoin.it/wiki/User:DiThi/MTUT#PROPOSAL:_Merkle_tree_of_unspent_transactions_.28MTUT.29.2C_for_serverless_thin_clients_and_self-verifiable_prunned_blockchain.] [https://bitcointalk.org/index.php?topic=88208.0]
* Increased efficiency for merged mining: restructure the primary header to make the bitcoin specific data non-mandatory. (e.g. the block chain specific stuff would go into second header connected by a header tree), making the primary headers pure timestamps and nonces.
* Switch to block hashing algorithm secure against block withholding attacks.

== Transaction behavior changes==
* Improved signature types to allow for partial malleability of outputs. (e.g. make it easier to add a fee onto someone else's transaction, or to take fees from a transaction without outputs set aside for that purpose)
* Elimination of output scripts: all transactions pay-to-scripthash, probably with a single byte indicating the scripthash type. Other than reducing effective output script secrecy (which is not possible without OP_EVAL anyways) this is believed to be costless, and the secrecy can be recovered with recursive OP_EVAL. The motivation here is that data in outputs is far more expensive than inputs because some outputs may be never prunable, and pay-to-scripthash minimizes output size without harming total size.
* Allow soft-spending of generation outputs without confirmations (outputs of these transactions might also appear as generation themselves)
* Allow additional inputs to generation transactions
* Add new signature hashtype to include value of TxOut being spent, in the hash to be signed. Doing this would remove the requirement that offline signing devices be sent all supporting transactions with the transaction-to-be-signed, just to confirm the transaction fee.

== Cryptographic changes==
* Pervasive ECC public key-recovery to reduce transaction sizes (can be done partially without breaking compatibility completely)
* [http://ed25519.cr.yp.to/ Ed25519] (variant*) for much faster validation operations. (variant because the normal way Ed25519 is specified is not key recovery compatible)
* Support for more than one public-key cryptosystem (ECDSA-k1) and key size (256bits) as a hedge against future cryptanalysis or designed-in flaws in any one algorithm. Every node must support validation of signatures with every cryptosystem, but a small number of very-cryptograpically-diverse options is still better than just one. Additional signature types could be kludged into the existing system with script extensions but would be better supported natively.
* Support for a [http://en.wikipedia.org/wiki/Post-quantum_cryptography post-quantum] signature scheme. [http://en.wikipedia.org/wiki/Lamport_signature Lamport signatures] have nice intuitive security properties, but it has extreme space requirements that would require structural changes to the blockchain to accommodate, (e.g. flip-chain+paytoscripthash+extensive pruning). However other post-quantum schemes like [http://en.wikipedia.org/wiki/NTRU|IEEE1363.1] do not. See the [http://pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf introductory chapter of DJB's book] and the [http://pqcrypto.org PQCrypto conference webpage] for full details.

== Currency changes==
''Please don't list anything here which would significantly change the committed overall economics of the system, it's safe to assume anything with significant economic impact will _never_ be changed in Bitcoin<ref>[http://bitcointalk.org/index.php?topic=45468.msg542375#msg542375 Suggested MAJOR change to Bitcoin]</ref>, because such changes would undermine the trust people have in the system, though they may form the basis of an interesting [[alternative chain]].
* Increase currency divisibility.

== Navel gazing / Protocol housekeeping==
* Byte order consistency (big endian)
* Eliminate redundancies in the variable length integer encodings, possibly switch to a standard.
* Avoiding hashes covering malleable fields

== Bug fixes ==
* CHECKMULTISIG popping one-too-many items off the stack
* Difficulty adjustment periods should overlap (prevent potential 'timejacking') Note: An ideal adjustment algorithm would ensure there is no easy dispute on "next target" for any block. Eg, it should not be possible for MinerX to set his block time 2 hours in the future to achieve a slightly higher difficulty and win any same-block-height race by default.
* Difficulty adjustment should adapt to sudden hashrate loss. Note: all altchains which have attempted this have created significant security vulnerabilities in the process. Also interested parties could encourage mining by including high fee transactions in every block so avoiding need for this change.
* Scripts should be fully enabled after a careful audit.
* Miners/relays should not be able to inject extra arbitrary data into transactions?
* Use the previous block hash as an explicit or implicit prev_in in coinbases when hashing them to make it ~impossible to get a duplicate coinbase, thus removing the need for a pruning node to remember coinbase hashes to prevent duplicates consistently with the rest of the network
* coinbases must be parseable.
This changes would involve converting old blocks:
* uint64_t for timestamp field in blocks.

==See Also==
*[[Prohibited changes]]

==References==
<references />

[[Category:Technical]]
[[Category:Developer]]

Hardfork Wishlist

2014-03-22T16:46:44Z

Eldentyrell: /* Cryptographic changes */

The '''Hardfork Wishlist''' is to record changes to Bitcoin that might be desirable, but that will require a "hard" block-chain split (everybody must upgrade, old software will not accept blocks/transactions created with the new [[Protocol rules|rules]], considering them to be [[Invalid block|invalid blocks]]).

This page is ''not'' for changes that can be accomplished in way that is compatible with old software (for example, by making transactions [[Nonstandard block|nonstandard]] or by [[Discouraged block|discouraging blocks]]).

== Changes to hard-coded limits ==
* Replace hard-coded maximum block size (1,000,000 bytes) and maximum number of signature operations per block (20,000) with ???.

== Major structural changes ==
* "Flip the chain", instead of committing to new transactions, commit to the summaries of open transactions: [https://bitcointalk.org/index.php?topic=505.0] [https://bitcointalk.org/index.php?topic=21995.0] [https://en.bitcoin.it/wiki/User:DiThi/MTUT#PROPOSAL:_Merkle_tree_of_unspent_transactions_.28MTUT.29.2C_for_serverless_thin_clients_and_self-verifiable_prunned_blockchain.] [https://bitcointalk.org/index.php?topic=88208.0]
* Increased efficiency for merged mining: restructure the primary header to make the bitcoin specific data non-mandatory. (e.g. the block chain specific stuff would go into second header connected by a header tree), making the primary headers pure timestamps and nonces.
* Switch to block hashing algorithm secure against block withholding attacks.

== Transaction behavior changes==
* Improved signature types to allow for partial malleability of outputs. (e.g. make it easier to add a fee onto someone else's transaction, or to take fees from a transaction without outputs set aside for that purpose)
* Elimination of output scripts: all transactions pay-to-scripthash, probably with a single byte indicating the scripthash type. Other than reducing effective output script secrecy (which is not possible without OP_EVAL anyways) this is believed to be costless, and the secrecy can be recovered with recursive OP_EVAL. The motivation here is that data in outputs is far more expensive than inputs because some outputs may be never prunable, and pay-to-scripthash minimizes output size without harming total size.
* Allow soft-spending of generation outputs without confirmations (outputs of these transactions might also appear as generation themselves)
* Allow additional inputs to generation transactions
* Add new signature hashtype to include value of TxOut being spent, in the hash to be signed. Doing this would remove the requirement that offline signing devices be sent all supporting transactions with the transaction-to-be-signed, just to confirm the transaction fee.

== Cryptographic changes==
* Pervasive ECC public key-recovery to reduce transaction sizes (can be done partially without breaking compatibility completely)
* [http://ed25519.cr.yp.to/ Ed25519] (variant*) for much faster validation operations. (variant because the normal way Ed25519 is specified is not key recovery compatible)
* Support for more than one public-key cryptosystem (ECDSA-k1) and key size (256bits) as a hedge against future cryptanalysis or designed-in flaws in any one algorithm. Every node must support validation of signatures with every cryptosystem, but a small number of very-cryptograpically-diverse options is still better than just one. Additional signature types could be kludged into the existing system with script extensions but would be better supported natively.
* Support for a [http://en.wikipedia.org/wiki/Post-quantum_cryptography post-quantum] signature scheme. [http://en.wikipedia.org/wiki/Lamport_signature Lamport signatures] have nice intuitive security properties, but it has extreme space requirements that would require structural changes to the blockchain to accommodate, (e.g. flip-chain+paytoscripthash+extensive pruning). However other post-quantum schemes like [http://en.wikipedia.org/wiki/NTRU|IEEE 1363.1] do not. See the [http://pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf introductory chapter of DJB's book] and the [http://pqcrypto.org PQCrypto conference webpage] for full details.

== Currency changes==
''Please don't list anything here which would significantly change the committed overall economics of the system, it's safe to assume anything with significant economic impact will _never_ be changed in Bitcoin<ref>[http://bitcointalk.org/index.php?topic=45468.msg542375#msg542375 Suggested MAJOR change to Bitcoin]</ref>, because such changes would undermine the trust people have in the system, though they may form the basis of an interesting [[alternative chain]].
* Increase currency divisibility.

== Navel gazing / Protocol housekeeping==
* Byte order consistency (big endian)
* Eliminate redundancies in the variable length integer encodings, possibly switch to a standard.
* Avoiding hashes covering malleable fields

== Bug fixes ==
* CHECKMULTISIG popping one-too-many items off the stack
* Difficulty adjustment periods should overlap (prevent potential 'timejacking') Note: An ideal adjustment algorithm would ensure there is no easy dispute on "next target" for any block. Eg, it should not be possible for MinerX to set his block time 2 hours in the future to achieve a slightly higher difficulty and win any same-block-height race by default.
* Difficulty adjustment should adapt to sudden hashrate loss. Note: all altchains which have attempted this have created significant security vulnerabilities in the process. Also interested parties could encourage mining by including high fee transactions in every block so avoiding need for this change.
* Scripts should be fully enabled after a careful audit.
* Miners/relays should not be able to inject extra arbitrary data into transactions?
* Use the previous block hash as an explicit or implicit prev_in in coinbases when hashing them to make it ~impossible to get a duplicate coinbase, thus removing the need for a pruning node to remember coinbase hashes to prevent duplicates consistently with the rest of the network
* coinbases must be parseable.
This changes would involve converting old blocks:
* uint64_t for timestamp field in blocks.

==See Also==
*[[Prohibited changes]]

==References==
<references />

[[Category:Technical]]
[[Category:Developer]]

Hardfork Wishlist

2014-03-22T16:45:43Z

Eldentyrell: not all post-quantum crypto has the same disadvantages as lamport sigs

The '''Hardfork Wishlist''' is to record changes to Bitcoin that might be desirable, but that will require a "hard" block-chain split (everybody must upgrade, old software will not accept blocks/transactions created with the new [[Protocol rules|rules]], considering them to be [[Invalid block|invalid blocks]]).

This page is ''not'' for changes that can be accomplished in way that is compatible with old software (for example, by making transactions [[Nonstandard block|nonstandard]] or by [[Discouraged block|discouraging blocks]]).

== Changes to hard-coded limits ==
* Replace hard-coded maximum block size (1,000,000 bytes) and maximum number of signature operations per block (20,000) with ???.

== Major structural changes ==
* "Flip the chain", instead of committing to new transactions, commit to the summaries of open transactions: [https://bitcointalk.org/index.php?topic=505.0] [https://bitcointalk.org/index.php?topic=21995.0] [https://en.bitcoin.it/wiki/User:DiThi/MTUT#PROPOSAL:_Merkle_tree_of_unspent_transactions_.28MTUT.29.2C_for_serverless_thin_clients_and_self-verifiable_prunned_blockchain.] [https://bitcointalk.org/index.php?topic=88208.0]
* Increased efficiency for merged mining: restructure the primary header to make the bitcoin specific data non-mandatory. (e.g. the block chain specific stuff would go into second header connected by a header tree), making the primary headers pure timestamps and nonces.
* Switch to block hashing algorithm secure against block withholding attacks.

== Transaction behavior changes==
* Improved signature types to allow for partial malleability of outputs. (e.g. make it easier to add a fee onto someone else's transaction, or to take fees from a transaction without outputs set aside for that purpose)
* Elimination of output scripts: all transactions pay-to-scripthash, probably with a single byte indicating the scripthash type. Other than reducing effective output script secrecy (which is not possible without OP_EVAL anyways) this is believed to be costless, and the secrecy can be recovered with recursive OP_EVAL. The motivation here is that data in outputs is far more expensive than inputs because some outputs may be never prunable, and pay-to-scripthash minimizes output size without harming total size.
* Allow soft-spending of generation outputs without confirmations (outputs of these transactions might also appear as generation themselves)
* Allow additional inputs to generation transactions
* Add new signature hashtype to include value of TxOut being spent, in the hash to be signed. Doing this would remove the requirement that offline signing devices be sent all supporting transactions with the transaction-to-be-signed, just to confirm the transaction fee.

== Cryptographic changes==
* Pervasive ECC public key-recovery to reduce transaction sizes (can be done partially without breaking compatibility completely)
* [http://ed25519.cr.yp.to/ Ed25519] (variant*) for much faster validation operations. (variant because the normal way Ed25519 is specified is not key recovery compatible)
* Support for more than one public-key cryptosystem (ECDSA-k1) and key size (256bits) as a hedge against future cryptanalysis or designed-in flaws in any one algorithm. Every node must support validation of signatures with every cryptosystem, but a small number of very-cryptograpically-diverse options is still better than just one. Additional signature types could be kludged into the existing system with script extensions but would be better supported natively.
* Support for a [http://en.wikipedia.org/wiki/Post-quantum_cryptography post-quantum] signature scheme. [http://en.wikipedia.org/wiki/Lamport_signature Lamport signatures] have nice intuitive security properties, but it has extreme space requirements that would require structural changes to the blockchain to accommodate, (e.g. flip-chain+paytoscripthash+extensive pruning), but other post-quantum schemes like [http://en.wikipedia.org/wiki/NTRU|IEEE 1363.1] do not. See the [http://pqcrypto.org PQCrypto conference webpage] for details.

== Currency changes==
''Please don't list anything here which would significantly change the committed overall economics of the system, it's safe to assume anything with significant economic impact will _never_ be changed in Bitcoin<ref>[http://bitcointalk.org/index.php?topic=45468.msg542375#msg542375 Suggested MAJOR change to Bitcoin]</ref>, because such changes would undermine the trust people have in the system, though they may form the basis of an interesting [[alternative chain]].
* Increase currency divisibility.

== Navel gazing / Protocol housekeeping==
* Byte order consistency (big endian)
* Eliminate redundancies in the variable length integer encodings, possibly switch to a standard.
* Avoiding hashes covering malleable fields

== Bug fixes ==
* CHECKMULTISIG popping one-too-many items off the stack
* Difficulty adjustment periods should overlap (prevent potential 'timejacking') Note: An ideal adjustment algorithm would ensure there is no easy dispute on "next target" for any block. Eg, it should not be possible for MinerX to set his block time 2 hours in the future to achieve a slightly higher difficulty and win any same-block-height race by default.
* Difficulty adjustment should adapt to sudden hashrate loss. Note: all altchains which have attempted this have created significant security vulnerabilities in the process. Also interested parties could encourage mining by including high fee transactions in every block so avoiding need for this change.
* Scripts should be fully enabled after a careful audit.
* Miners/relays should not be able to inject extra arbitrary data into transactions?
* Use the previous block hash as an explicit or implicit prev_in in coinbases when hashing them to make it ~impossible to get a duplicate coinbase, thus removing the need for a pruning node to remember coinbase hashes to prevent duplicates consistently with the rest of the network
* coinbases must be parseable.
This changes would involve converting old blocks:
* uint64_t for timestamp field in blocks.

==See Also==
*[[Prohibited changes]]

==References==
<references />

[[Category:Technical]]
[[Category:Developer]]

Hardfork Wishlist

2014-03-22T16:43:43Z

Eldentyrell: make "post-quantum cryptosystem" and "multiple cryptosystems as a hedge" separate items

The '''Hardfork Wishlist''' is to record changes to Bitcoin that might be desirable, but that will require a "hard" block-chain split (everybody must upgrade, old software will not accept blocks/transactions created with the new [[Protocol rules|rules]], considering them to be [[Invalid block|invalid blocks]]).

This page is ''not'' for changes that can be accomplished in way that is compatible with old software (for example, by making transactions [[Nonstandard block|nonstandard]] or by [[Discouraged block|discouraging blocks]]).

== Changes to hard-coded limits ==
* Replace hard-coded maximum block size (1,000,000 bytes) and maximum number of signature operations per block (20,000) with ???.

== Major structural changes ==
* "Flip the chain", instead of committing to new transactions, commit to the summaries of open transactions: [https://bitcointalk.org/index.php?topic=505.0] [https://bitcointalk.org/index.php?topic=21995.0] [https://en.bitcoin.it/wiki/User:DiThi/MTUT#PROPOSAL:_Merkle_tree_of_unspent_transactions_.28MTUT.29.2C_for_serverless_thin_clients_and_self-verifiable_prunned_blockchain.] [https://bitcointalk.org/index.php?topic=88208.0]
* Increased efficiency for merged mining: restructure the primary header to make the bitcoin specific data non-mandatory. (e.g. the block chain specific stuff would go into second header connected by a header tree), making the primary headers pure timestamps and nonces.
* Switch to block hashing algorithm secure against block withholding attacks.

== Transaction behavior changes==
* Improved signature types to allow for partial malleability of outputs. (e.g. make it easier to add a fee onto someone else's transaction, or to take fees from a transaction without outputs set aside for that purpose)
* Elimination of output scripts: all transactions pay-to-scripthash, probably with a single byte indicating the scripthash type. Other than reducing effective output script secrecy (which is not possible without OP_EVAL anyways) this is believed to be costless, and the secrecy can be recovered with recursive OP_EVAL. The motivation here is that data in outputs is far more expensive than inputs because some outputs may be never prunable, and pay-to-scripthash minimizes output size without harming total size.
* Allow soft-spending of generation outputs without confirmations (outputs of these transactions might also appear as generation themselves)
* Allow additional inputs to generation transactions
* Add new signature hashtype to include value of TxOut being spent, in the hash to be signed. Doing this would remove the requirement that offline signing devices be sent all supporting transactions with the transaction-to-be-signed, just to confirm the transaction fee.

== Cryptographic changes==
* Pervasive ECC public key-recovery to reduce transaction sizes (can be done partially without breaking compatibility completely)
* [http://ed25519.cr.yp.to/ Ed25519] (variant*) for much faster validation operations. (variant because the normal way Ed25519 is specified is not key recovery compatible)
* Support for more than one public-key cryptosystem (ECDSA-k1) and key size (256bits) as a hedge against future cryptanalysis or designed-in flaws in any one algorithm. Every node must support validation of signatures with every cryptosystem, but a small number of very-cryptograpically-diverse options is still better than just one. Additional signature types could be kludged into the existing system with script extensions but would be better supported natively.
* Support for a [http://en.wikipedia.org/wiki/Post-quantum_cryptography post-quantum] signature scheme. [http://en.wikipedia.org/wiki/Lamport_signature Lamport signatures] have nice intuitive security properties, but it and all other similar schemes have extreme space requirements that would require structural changes to the blockchain to accommodate, (e.g. flip-chain+paytoscripthash+extensive pruning).

== Currency changes==
''Please don't list anything here which would significantly change the committed overall economics of the system, it's safe to assume anything with significant economic impact will _never_ be changed in Bitcoin<ref>[http://bitcointalk.org/index.php?topic=45468.msg542375#msg542375 Suggested MAJOR change to Bitcoin]</ref>, because such changes would undermine the trust people have in the system, though they may form the basis of an interesting [[alternative chain]].
* Increase currency divisibility.

== Navel gazing / Protocol housekeeping==
* Byte order consistency (big endian)
* Eliminate redundancies in the variable length integer encodings, possibly switch to a standard.
* Avoiding hashes covering malleable fields

== Bug fixes ==
* CHECKMULTISIG popping one-too-many items off the stack
* Difficulty adjustment periods should overlap (prevent potential 'timejacking') Note: An ideal adjustment algorithm would ensure there is no easy dispute on "next target" for any block. Eg, it should not be possible for MinerX to set his block time 2 hours in the future to achieve a slightly higher difficulty and win any same-block-height race by default.
* Difficulty adjustment should adapt to sudden hashrate loss. Note: all altchains which have attempted this have created significant security vulnerabilities in the process. Also interested parties could encourage mining by including high fee transactions in every block so avoiding need for this change.
* Scripts should be fully enabled after a careful audit.
* Miners/relays should not be able to inject extra arbitrary data into transactions?
* Use the previous block hash as an explicit or implicit prev_in in coinbases when hashing them to make it ~impossible to get a duplicate coinbase, thus removing the need for a pruning node to remember coinbase hashes to prevent duplicates consistently with the rest of the network
* coinbases must be parseable.
This changes would involve converting old blocks:
* uint64_t for timestamp field in blocks.

==See Also==
*[[Prohibited changes]]

==References==
<references />

[[Category:Technical]]
[[Category:Developer]]

Hardfork Wishlist

2014-03-22T16:42:31Z

Eldentyrell: gah, I hate wikimedia markup

The '''Hardfork Wishlist''' is to record changes to Bitcoin that might be desirable, but that will require a "hard" block-chain split (everybody must upgrade, old software will not accept blocks/transactions created with the new [[Protocol rules|rules]], considering them to be [[Invalid block|invalid blocks]]).

This page is ''not'' for changes that can be accomplished in way that is compatible with old software (for example, by making transactions [[Nonstandard block|nonstandard]] or by [[Discouraged block|discouraging blocks]]).

== Changes to hard-coded limits ==
* Replace hard-coded maximum block size (1,000,000 bytes) and maximum number of signature operations per block (20,000) with ???.

== Major structural changes ==
* "Flip the chain", instead of committing to new transactions, commit to the summaries of open transactions: [https://bitcointalk.org/index.php?topic=505.0] [https://bitcointalk.org/index.php?topic=21995.0] [https://en.bitcoin.it/wiki/User:DiThi/MTUT#PROPOSAL:_Merkle_tree_of_unspent_transactions_.28MTUT.29.2C_for_serverless_thin_clients_and_self-verifiable_prunned_blockchain.] [https://bitcointalk.org/index.php?topic=88208.0]
* Increased efficiency for merged mining: restructure the primary header to make the bitcoin specific data non-mandatory. (e.g. the block chain specific stuff would go into second header connected by a header tree), making the primary headers pure timestamps and nonces.
* Switch to block hashing algorithm secure against block withholding attacks.

== Transaction behavior changes==
* Improved signature types to allow for partial malleability of outputs. (e.g. make it easier to add a fee onto someone else's transaction, or to take fees from a transaction without outputs set aside for that purpose)
* Elimination of output scripts: all transactions pay-to-scripthash, probably with a single byte indicating the scripthash type. Other than reducing effective output script secrecy (which is not possible without OP_EVAL anyways) this is believed to be costless, and the secrecy can be recovered with recursive OP_EVAL. The motivation here is that data in outputs is far more expensive than inputs because some outputs may be never prunable, and pay-to-scripthash minimizes output size without harming total size.
* Allow soft-spending of generation outputs without confirmations (outputs of these transactions might also appear as generation themselves)
* Allow additional inputs to generation transactions
* Add new signature hashtype to include value of TxOut being spent, in the hash to be signed. Doing this would remove the requirement that offline signing devices be sent all supporting transactions with the transaction-to-be-signed, just to confirm the transaction fee.

== Cryptographic changes==
* Pervasive ECC public key-recovery to reduce transaction sizes (can be done partially without breaking compatibility completely)
* [http://ed25519.cr.yp.to/ Ed25519] (variant*) for much faster validation operations. (variant because the normal way Ed25519 is specified is not key recovery compatible)
* Support for a [http://en.wikipedia.org/wiki/Post-quantum_cryptography post-quantum] signature scheme. [http://en.wikipedia.org/wiki/Lamport_signature Lamport signatures] have nice intuitive security properties, but it and all other similar schemes have extreme space requirements that would require structural changes to the blockchain to accommodate, (e.g. flip-chain+paytoscripthash+extensive pruning). Additional signature types could be kludged into the existing system with script extensions but would be better supported natively.

== Currency changes==
''Please don't list anything here which would significantly change the committed overall economics of the system, it's safe to assume anything with significant economic impact will _never_ be changed in Bitcoin<ref>[http://bitcointalk.org/index.php?topic=45468.msg542375#msg542375 Suggested MAJOR change to Bitcoin]</ref>, because such changes would undermine the trust people have in the system, though they may form the basis of an interesting [[alternative chain]].
* Increase currency divisibility.

== Navel gazing / Protocol housekeeping==
* Byte order consistency (big endian)
* Eliminate redundancies in the variable length integer encodings, possibly switch to a standard.
* Avoiding hashes covering malleable fields

== Bug fixes ==
* CHECKMULTISIG popping one-too-many items off the stack
* Difficulty adjustment periods should overlap (prevent potential 'timejacking') Note: An ideal adjustment algorithm would ensure there is no easy dispute on "next target" for any block. Eg, it should not be possible for MinerX to set his block time 2 hours in the future to achieve a slightly higher difficulty and win any same-block-height race by default.
* Difficulty adjustment should adapt to sudden hashrate loss. Note: all altchains which have attempted this have created significant security vulnerabilities in the process. Also interested parties could encourage mining by including high fee transactions in every block so avoiding need for this change.
* Scripts should be fully enabled after a careful audit.
* Miners/relays should not be able to inject extra arbitrary data into transactions?
* Use the previous block hash as an explicit or implicit prev_in in coinbases when hashing them to make it ~impossible to get a duplicate coinbase, thus removing the need for a pruning node to remember coinbase hashes to prevent duplicates consistently with the rest of the network
* coinbases must be parseable.
This changes would involve converting old blocks:
* uint64_t for timestamp field in blocks.

==See Also==
*[[Prohibited changes]]

==References==
<references />

[[Category:Technical]]
[[Category:Developer]]

Hardfork Wishlist

2014-03-22T16:41:57Z

Eldentyrell: add link to post-quantum

The '''Hardfork Wishlist''' is to record changes to Bitcoin that might be desirable, but that will require a "hard" block-chain split (everybody must upgrade, old software will not accept blocks/transactions created with the new [[Protocol rules|rules]], considering them to be [[Invalid block|invalid blocks]]).

This page is ''not'' for changes that can be accomplished in way that is compatible with old software (for example, by making transactions [[Nonstandard block|nonstandard]] or by [[Discouraged block|discouraging blocks]]).

== Changes to hard-coded limits ==
* Replace hard-coded maximum block size (1,000,000 bytes) and maximum number of signature operations per block (20,000) with ???.

== Major structural changes ==
* "Flip the chain", instead of committing to new transactions, commit to the summaries of open transactions: [https://bitcointalk.org/index.php?topic=505.0] [https://bitcointalk.org/index.php?topic=21995.0] [https://en.bitcoin.it/wiki/User:DiThi/MTUT#PROPOSAL:_Merkle_tree_of_unspent_transactions_.28MTUT.29.2C_for_serverless_thin_clients_and_self-verifiable_prunned_blockchain.] [https://bitcointalk.org/index.php?topic=88208.0]
* Increased efficiency for merged mining: restructure the primary header to make the bitcoin specific data non-mandatory. (e.g. the block chain specific stuff would go into second header connected by a header tree), making the primary headers pure timestamps and nonces.
* Switch to block hashing algorithm secure against block withholding attacks.

== Transaction behavior changes==
* Improved signature types to allow for partial malleability of outputs. (e.g. make it easier to add a fee onto someone else's transaction, or to take fees from a transaction without outputs set aside for that purpose)
* Elimination of output scripts: all transactions pay-to-scripthash, probably with a single byte indicating the scripthash type. Other than reducing effective output script secrecy (which is not possible without OP_EVAL anyways) this is believed to be costless, and the secrecy can be recovered with recursive OP_EVAL. The motivation here is that data in outputs is far more expensive than inputs because some outputs may be never prunable, and pay-to-scripthash minimizes output size without harming total size.
* Allow soft-spending of generation outputs without confirmations (outputs of these transactions might also appear as generation themselves)
* Allow additional inputs to generation transactions
* Add new signature hashtype to include value of TxOut being spent, in the hash to be signed. Doing this would remove the requirement that offline signing devices be sent all supporting transactions with the transaction-to-be-signed, just to confirm the transaction fee.

== Cryptographic changes==
* Pervasive ECC public key-recovery to reduce transaction sizes (can be done partially without breaking compatibility completely)
* [http://ed25519.cr.yp.to/ Ed25519] (variant*) for much faster validation operations. (variant because the normal way Ed25519 is specified is not key recovery compatible)
* Support for a [[http://en.wikipedia.org/wiki/Post-quantum_cryptography|post-quantum]] signature scheme. [http://en.wikipedia.org/wiki/Lamport_signature Lamport signatures] have nice intuitive security properties, but it and all other similar schemes have extreme space requirements that would require structural changes to the blockchain to accommodate, (e.g. flip-chain+paytoscripthash+extensive pruning). Additional signature types could be kludged into the existing system with script extensions but would be better supported natively.

== Currency changes==
''Please don't list anything here which would significantly change the committed overall economics of the system, it's safe to assume anything with significant economic impact will _never_ be changed in Bitcoin<ref>[http://bitcointalk.org/index.php?topic=45468.msg542375#msg542375 Suggested MAJOR change to Bitcoin]</ref>, because such changes would undermine the trust people have in the system, though they may form the basis of an interesting [[alternative chain]].
* Increase currency divisibility.

== Navel gazing / Protocol housekeeping==
* Byte order consistency (big endian)
* Eliminate redundancies in the variable length integer encodings, possibly switch to a standard.
* Avoiding hashes covering malleable fields

== Bug fixes ==
* CHECKMULTISIG popping one-too-many items off the stack
* Difficulty adjustment periods should overlap (prevent potential 'timejacking') Note: An ideal adjustment algorithm would ensure there is no easy dispute on "next target" for any block. Eg, it should not be possible for MinerX to set his block time 2 hours in the future to achieve a slightly higher difficulty and win any same-block-height race by default.
* Difficulty adjustment should adapt to sudden hashrate loss. Note: all altchains which have attempted this have created significant security vulnerabilities in the process. Also interested parties could encourage mining by including high fee transactions in every block so avoiding need for this change.
* Scripts should be fully enabled after a careful audit.
* Miners/relays should not be able to inject extra arbitrary data into transactions?
* Use the previous block hash as an explicit or implicit prev_in in coinbases when hashing them to make it ~impossible to get a duplicate coinbase, thus removing the need for a pruning node to remember coinbase hashes to prevent duplicates consistently with the rest of the network
* coinbases must be parseable.
This changes would involve converting old blocks:
* uint64_t for timestamp field in blocks.

==See Also==
*[[Prohibited changes]]

==References==
<references />

[[Category:Technical]]
[[Category:Developer]]

Thin Client Security

2014-03-08T13:54:31Z

Eldentyrell: fix naming

Recently there have been a number of proposals for bitcoin clients which do not store a complete copy of every block in the entire block chain. This page will refer to all such clients as "thin clients". This page is meant to be a place to try to make sense of the security and trust implications of the various schemes.

== Block Height vs. Depth ==

It is important to distinguish between block height verification and block depth verification.

A client verifies the height H of a block by checking that there are H block '''before''' it, all of which are well-formed and obey the maximum-difficulty-adjustment-rate rule. Currently only the Satoshi client, libbitcoin, and btcd do block height verification. Block height is the fundamental anchor of trustless security in the Bitcoin system.

A client verifies the depth D of a block by checking that there are D blocks '''after''' it (also called "confirmations"), all of which are well-formed. SPV clients substitute block depth for block height as a transaction validity check. All clients use block depth as a measure of the liklihood of a [[Chain_Reorganization|blockchain reorganization]] producing a new longer fork which excludes the transaction (i.e. [[Orphan_Block|orphaning]] its block).

See also [https://bitcointalk.org/index.php?topic=88208.msg987429#msg987429 some comments on probabilistic verification of block height].

== Full-Chain Clients ==

The "thick" bitcoin client downloads a copy of the entire chain, including all transactions (not just headers). It will be used as the reference point for security comparisions below.

=== Block '''Height''' as a Transaction Validity Check ===

A full-chain client trusts the difficultywise-longest [https://en.bitcoin.it/wiki/Protocol_rules#Blocks well-formed] blockchain it can find. Any transaction on the difficultywise-longest well-formed chain is considered valid. Therefore, the validity of a transaction is determined by its height -- i.e. how many blocks come ''before'' it. A transaction's ''depth'' (the number of blocks ''after'' it) is used to determine the likelihood of the transaction being invalidated due to the emergence of a longer fork.

==== [[bitcoind|bitcoin-qt]] ====

==== [https://github.com/conformal/btcd btcd] ====

== Header-Only Clients ==

These client downloads a complete copy of the headers for all blocks in the entire blockchain. This means that the download and storage requirements scale linearly with the amount of time since bitcoin was invented; it would be preferable to have the scaling be logarithmic or even constant.

=== Simplified Payment Verification (SPV) ===

This scheme is described in section 8 of the [http://bitcoin.org/bitcoin.pdf original bitcoin whitepaper].

==== Block '''Depth''' as a Transaction Validity Check ====

As Satoshi writes, "[the thin client] can't check the transaction for himself, but by linking it to a place in the chain, he can see that a network node has accepted it, and blocks added after it further confirm the network has accepted it." If we take "X" to be the "number of blocks added after it", then SPV essentially trusts that a transaction X blocks deep in the chain does not have inputs which were already spent further back in the chain. Therefore, the validity of a transaction is determined by its depth -- i.e. how many blocks come ''after'' it. Other thin client protocols also include this assumption.

This is very different from the trust model in the "thick" client: the thick client verifies that a transaction's inputs are unspent by actually checking the whole chain up to that point -- there is no "X blocks deep" involved here. The thick client uses "X blocks deep" (aka "confirmations") only once it has already decided that a transaction is valid (i.e. no [[Double-spending|double-spends]]). At that point it uses "X blocks deep" to decide how likely it is that a longer fork in the chain will emerge which excludes that transaction.

It is very important to understand how the same property ("X blocks deep") is used to verify two different properties in the thick client and SPV cases. '''The thick client never uses block depth as a measure of transaction validity; the SPV client does'''.

This is a concern in a situation where an SPV client is subjected to a double-spend attack by somebody who controls its network connection. For example, suppose you are at a wi-fi cafe and are paying for something using your smartphone -- the cafe owner controls your network connection. Satoshi acknowledges this implicitly when he writes that "the verification is reliable as long as honest nodes control the network" -- to be completely pedantic, this means that the verification is reliable as long as honest nodes control '''the part of the network that the SPV client is able to communicate with'''. In an attack-by-ISP scenario this may not be a sufficiently strong security property. The attacker would not need to overpower "the rest of the network" because the client is unable to communicate with it.

==== [[BitCoinJ|bitcoinj]] ====

Simplified Payment Verification is the verification mechanism used in [[BitCoinJ|bitcoinj]].

A security analysis of some of the issues in bitcoinj can be found [http://code.google.com/p/bitcoinj/wiki/SecurityModel here]; however:

* The claim that "picking 10 nodes and requiring all of them to be consistent needs much less trust" overlooks the problem of [https://en.bitcoin.it/wiki/Weaknesses#Cancer_nodes "cancer nodes"] and [http://en.wikipedia.org/wiki/Sybil_attack Sybil attacks].
* Many of the security claims are qualified by some form of "if you don't think an attacker controls your internet connection"; see the previous section for a discussion of why this is problematic.

==== [https://bitcointalk.org/index.php?topic=128055.0 picocoin] ====

Simplified Payment Verification is the verification mechanism used in picocoin.

The library (libccoin) that picocoin is based on includes code for validating scripts and blocks; this could potentially be used to implement a full-chain client.

==== [[Electrum]] ====

ThomasV [https://en.bitcoin.it/w/index.php?title=Thin_Client_Security&action=historysubmit&diff=42844&oldid=36519 claims] that "Electrum, it is doing SPV since 2012".

=== Unused Output Tree in the Blockchain (UOT) ===

There have been several proposals (the first appears to be [https://bitcointalk.org/index.php?topic=21995.0 this one] by gmaxwell, who called it an "open transaction tree", although the term "open" is now taken to mean "not yet mined into the blockchain" rather than "unspent") to form a tree of unused transaction outputs at each block in the chain, hash it as a Merkle tree, and encode the root hash in the block chain (probably as part of the coinbase input). This will be called an Unused Output Tree (UOT). The first detailed proposal so far appears to be [https://en.bitcoin.it/wiki/User:DiThi/MTUT Alberto Torres' proposal]; etotheipi's [https://bitcointalk.org/index.php?topic=88208.0 ultimate blockchain compression] is a variant of this.

If such UOT hashes were included in the blockchain, a client which shipped with a [https://en.bitcoin.it/wiki/Vocabulary checkpoint] block that had a UOT would only need to download blocks after the checkpoint. Moreover, once the client had downloaded those blocks and confirmed their UOTs, it could discard all but the most recent block containing a UOT.

This would also let a thin client reduce the question of "is this output unspent" to the question of "is this block super-well-formed" where "well-formed" means "well-formed according to the normal blockchain rules and additionally has an Unused Output Tree which is accurate and truthful". This is still a long way from the low level of trust involved in the thick client, but it is a major improvement over all existing proposals.

It is unlikely that bitcoin would ever arrive at a state where every single block had a UOT, since this would require upgrading 100% of the miners on the network, or else convincing enough miners to reject blocks which do not contain a UOT. The latter strategy risks creating blockchain forks, which can be expensive (in reward terms) to miners. Therefore, any UOT strategy would need to cope with the fact that not every block contains a UOT.

Hostile miners may insert blocks into the chain which have what claims to be a UOT, but which is actually invalid. It is unlikely that such blocks could be kept out of the chain because, again, this would require adding a new block well-formedness criterion, and miners implementing this new criterion would risk "mining on the wrong side" of a fork, which could cost them a lot of money. Therefore, any UOT strategy would need to cope with the fact that not every block containing a UOT entry can be trusted.

Note that at the present moment no standard format for such Unused Output Tree hashes has been agreed upon, nor do any of the blocks in the chain contain them. The [https://bitcointalk.org/index.php?topic=91954 ultraprune] feature added to bitcoind-0.8 maintains a similar data structure on the client's disk. It does not put this data structure or its hash anywhere in the blockchain.

== Server-Trusting Clients ==

These clients involve some (usually low) level of trust in the server they rely upon. Mechanisms for authenticating the server, and for confirming that the server has not been compromised, are usually not explained.

All thin clients listed below currently connect to a single server, and are vulnerable to an attack similar to a double-spend. The attack can be run by that single server - the server can just lie to them that they received a Bitcoin transaction, and they, assuming the server does not lie, perform some service, transfer funds or send goods without actually receiving any Bitcoin in exchange. Therefore, they are implicitly trusting it.

Future enhancements have been suggested that will have the client talk to multiple servers and broadcast transactions and query all of them. Unfortunately it is well known to security researchers that this does not actually increase security; it simply makes the exploits more complicated and difficult to find. Security researchers have a name for this phenomenon: it is called a "Sybil attack"<ref>http://en.wikipedia.org/wiki/Sybil_attack</ref>. [https://bitcointalk.org/index.php?topic=88208.msg975201#msg975201 This post] on bitcointalk explains how some governments (notably Iran and China) already perform these sorts of attacks on their own citizens, with the coerced assistance of SSL certificate authorities.

Clients with a checkpoint (even a very old one) that download and validate the headers for the whole blockchain are [http://bitcoinmedia.com/the-irc-bootstrap-method-is-flawed/#comment-4243 not vulnerable] to Sybil attacks in the following sense: they can always ensure that an attack would cost more than the amount being stolen.

=== [[BCCAPI]] ===

== Other ==

* A [http://sourceforge.net/mailarchive/message.php?msg_id=28633866 thread] on bitcoin-dev
* A [http://bitcoin.stackexchange.com/questions/2584/is-reclaiming-disk-space-already-implemented-how-effective-will-it-be/2589 question] on bitcoin.stackexchange.com
* The [https://en.bitcoin.it/wiki/Weaknesses#Cancer_nodes "cancer nodes"] paragraph explains some of the issues with thin clients that base security on trusting whatever "a majority of the IP addresses I can see" say.
* [http://bitcoin.stackexchange.com/questions/2613/how-secure-are-various-models-of-bitcoin-clients related discussion on Stack Exchange]
* A hypothesized [https://bitcointalk.org/index.php?topic=134318.msg1441171#msg1441171 intermediate security class] between SPV and full-chain validation.

<references>

[[Category:Technical]]
[[category:Clients]]
[[Category:Security]]

Thin Client Security

2013-12-04T01:39:35Z

Eldentyrell: restore Electrum

Recently there have been a number of proposals for bitcoin clients which do not store a complete copy of every block in the entire block chain. This page will refer to all such clients as "thin clients". This page is meant to be a place to try to make sense of the security and trust implications of the various schemes.

== Block Height vs. Depth ==

It is important to distinguish between block height verification and block depth verification.

A client verifies the height H of a block by checking that there are H block '''before''' it, all of which are well-formed and obey the maximum-difficulty-adjustment-rate rule. Currently only the Satoshi client and libbitcoin do block height verification. Block height is the fundamental anchor of trustless security in the Bitcoin system.

A client verifies the depth D of a block by checking that there are D blocks '''after''' it (also called "confirmations"), all of which are well-formed. SPV clients substitute block depth for block height as a transaction validity check. All clients use block depth as a measure of the liklihood of a [[Chain_Reorganization|blockchain reorganization]] producing a new longer fork which excludes the transaction (i.e. [[Orphan_Block|orphaning]] its block).

See also [https://bitcointalk.org/index.php?topic=88208.msg987429#msg987429 some comments on probabilistic verification of block height].

== Full-Chain Clients ==

The "thick" bitcoin client downloads a copy of the entire chain, including all transactions (not just headers). It will be used as the reference point for security comparisions below.

=== Block '''Height''' as a Transaction Validity Check ===

A full-chain client trusts the difficultywise-longest [https://en.bitcoin.it/wiki/Protocol_rules#Blocks well-formed] blockchain it can find. Any transaction on the difficultywise-longest well-formed chain is considered valid. Therefore, the validity of a transaction is determined by its height -- i.e. how many blocks come ''before'' it. A transaction's ''depth'' (the number of blocks ''after'' it) is used to determine the likelihood of the transaction being invalidated due to the emergence of a longer fork.

== Header-Only Clients ==

These client downloads a complete copy of the headers for all blocks in the entire blockchain. This means that the download and storage requirements scale linearly with the amount of time since bitcoin was invented; it would be preferable to have the scaling be logarithmic or even constant.

=== Simplified Payment Verification (SPV) ===

This scheme is described in section 8 of the [http://bitcoin.org/bitcoin.pdf original bitcoin whitepaper].

==== Block '''Depth''' as a Transaction Validity Check ====

As Satoshi writes, "[the thin client] can't check the transaction for himself, but by linking it to a place in the chain, he can see that a network node has accepted it, and blocks added after it further confirm the network has accepted it." If we take "X" to be the "number of blocks added after it", then SPV essentially trusts that a transaction X blocks deep in the chain does not have inputs which were already spent further back in the chain. Therefore, the validity of a transaction is determined by its depth -- i.e. how many blocks come ''after'' it. Other thin client protocols also include this assumption.

This is very different from the trust model in the "thick" client: the thick client verifies that a transaction's inputs are unspent by actually checking the whole chain up to that point -- there is no "X blocks deep" involved here. The thick client uses "X blocks deep" (aka "confirmations") only once it has already decided that a transaction is valid (i.e. no [[Double-spending|double-spends]]). At that point it uses "X blocks deep" to decide how likely it is that a longer fork in the chain will emerge which excludes that transaction.

It is very important to understand how the same property ("X blocks deep") is used to verify two different properties in the thick client and SPV cases. '''The thick client never uses block depth as a measure of transaction validity; the SPV client does'''.

This is a concern in a situation where an SPV client is subjected to a double-spend attack by somebody who controls its network connection. For example, suppose you are at a wi-fi cafe and are paying for something using your smartphone -- the cafe owner controls your network connection. Satoshi acknowledges this implicitly when he writes that "the verification is reliable as long as honest nodes control the network" -- to be completely pedantic, this means that the verification is reliable as long as honest nodes control '''the part of the network that the SPV client is able to communicate with'''. In an attack-by-ISP scenario this may not be a sufficiently strong security property. The attacker would not need to overpower "the rest of the network" because the client is unable to communicate with it.

==== [[BitCoinJ|bitcoinj]] ====

Simplified Payment Verification is the verification mechanism used in [[BitCoinJ|bitcoinj]].

A security analysis of some of the issues in bitcoinj can be found [http://code.google.com/p/bitcoinj/wiki/SecurityModel here]; however:

* The claim that "picking 10 nodes and requiring all of them to be consistent needs much less trust" overlooks the problem of [https://en.bitcoin.it/wiki/Weaknesses#Cancer_nodes "cancer nodes"] and [http://en.wikipedia.org/wiki/Sybil_attack Sybil attacks].
* Many of the security claims are qualified by some form of "if you don't think an attacker controls your internet connection"; see the previous section for a discussion of why this is problematic.

==== [https://bitcointalk.org/index.php?topic=128055.0 picocoin] ====

Simplified Payment Verification is the verification mechanism used in picocoin.

The library (libccoin) that picocoin is based on includes code for validating scripts and blocks; this could potentially be used to implement a full-chain client.

==== [[Electrum]] ====

ThomasV [https://en.bitcoin.it/w/index.php?title=Thin_Client_Security&action=historysubmit&diff=42844&oldid=36519 claims] that "Electrum, it is doing SPV since 2012".

=== Unused Output Tree in the Blockchain (UOT) ===

There have been several proposals (the first appears to be [https://bitcointalk.org/index.php?topic=21995.0 this one] by gmaxwell, who called it an "open transaction tree", although the term "open" is now taken to mean "not yet mined into the blockchain" rather than "unspent") to form a tree of unused transaction outputs at each block in the chain, hash it as a Merkle tree, and encode the root hash in the block chain (probably as part of the coinbase input). This will be called an Unused Output Tree (UOT). The first detailed proposal so far appears to be [https://en.bitcoin.it/wiki/User:DiThi/MTUT Alberto Torres' proposal]; etotheipi's [https://bitcointalk.org/index.php?topic=88208.0 ultimate blockchain compression] is a variant of this.

If such UOT hashes were included in the blockchain, a client which shipped with a [https://en.bitcoin.it/wiki/Vocabulary checkpoint] block that had a UOT would only need to download blocks after the checkpoint. Moreover, once the client had downloaded those blocks and confirmed their UOTs, it could discard all but the most recent block containing a UOT.

This would also let a thin client reduce the question of "is this output unspent" to the question of "is this block super-well-formed" where "well-formed" means "well-formed according to the normal blockchain rules and additionally has an Unused Output Tree which is accurate and truthful". This is still a long way from the low level of trust involved in the thick client, but it is a major improvement over all existing proposals.

It is unlikely that bitcoin would ever arrive at a state where every single block had a UOT, since this would require upgrading 100% of the miners on the network, or else convincing enough miners to reject blocks which do not contain a UOT. The latter strategy risks creating blockchain forks, which can be expensive (in reward terms) to miners. Therefore, any UOT strategy would need to cope with the fact that not every block contains a UOT.

Hostile miners may insert blocks into the chain which have what claims to be a UOT, but which is actually invalid. It is unlikely that such blocks could be kept out of the chain because, again, this would require adding a new block well-formedness criterion, and miners implementing this new criterion would risk "mining on the wrong side" of a fork, which could cost them a lot of money. Therefore, any UOT strategy would need to cope with the fact that not every block containing a UOT entry can be trusted.

Note that at the present moment no standard format for such Unused Output Tree hashes has been agreed upon, nor do any of the blocks in the chain contain them. The [https://bitcointalk.org/index.php?topic=91954 ultraprune] feature added to bitcoind-0.8 maintains a similar data structure on the client's disk. It does not put this data structure or its hash anywhere in the blockchain.

== Server-Trusting Clients ==

These clients involve some (usually low) level of trust in the server they rely upon. Mechanisms for authenticating the server, and for confirming that the server has not been compromised, are usually not explained.

All thin clients listed below currently connect to a single server, and are vulnerable to an attack similar to a double-spend. The attack can be run by that single server - the server can just lie to them that they received a Bitcoin transaction, and they, assuming the server does not lie, perform some service, transfer funds or send goods without actually receiving any Bitcoin in exchange. Therefore, they are implicitly trusting it.

Future enhancements have been suggested that will have the client talk to multiple servers and broadcast transactions and query all of them. Unfortunately it is well known to security researchers that this does not actually increase security; it simply makes the exploits more complicated and difficult to find. Security researchers have a name for this phenomenon: it is called a "Sybil attack"<ref>http://en.wikipedia.org/wiki/Sybil_attack</ref>. [https://bitcointalk.org/index.php?topic=88208.msg975201#msg975201 This post] on bitcointalk explains how some governments (notably Iran and China) already perform these sorts of attacks on their own citizens, with the coerced assistance of SSL certificate authorities.

Clients with a checkpoint (even a very old one) that download and validate the headers for the whole blockchain are [http://bitcoinmedia.com/the-irc-bootstrap-method-is-flawed/#comment-4243 not vulnerable] to Sybil attacks in the following sense: they can always ensure that an attack would cost more than the amount being stolen.

=== [[BCCAPI]] ===

== Other ==

* A [http://sourceforge.net/mailarchive/message.php?msg_id=28633866 thread] on bitcoin-dev
* A [http://bitcoin.stackexchange.com/questions/2584/is-reclaiming-disk-space-already-implemented-how-effective-will-it-be/2589 question] on bitcoin.stackexchange.com
* The [https://en.bitcoin.it/wiki/Weaknesses#Cancer_nodes "cancer nodes"] paragraph explains some of the issues with thin clients that base security on trusting whatever "a majority of the IP addresses I can see" say.
* [http://bitcoin.stackexchange.com/questions/2613/how-secure-are-various-models-of-bitcoin-clients related discussion on Stack Exchange]
* A hypothesized [https://bitcointalk.org/index.php?topic=134318.msg1441171#msg1441171 intermediate security class] between SPV and full-chain validation.

<references>

[[Category:Technical]]
[[category:Clients]]
[[Category:Security]]