BIP 0016: Difference between revisions

From Bitcoin Wiki
Jump to navigation Jump to search
2112 (talk | contribs)
initial raw copy from the bitcointalk.org
 
934 (talk | contribs)
Update BIP text with latest version from https://github.com/bitcoin/bips/blob/4c6389f8431f6778/bip-0016.mediawiki
 
(26 intermediate revisions by 11 users not shown)
Line 1: Line 1:
Bitcoin Improvement Proposal 0016
{{bip}}
{{BipMoved|bip-0016.mediawiki}}


Author: 2112
<pre>
  BIP: 16
  Layer: Consensus (soft fork)
  Title: Pay to Script Hash
  Author: Gavin Andresen <gavinandresen@gmail.com>
  Comments-Summary: No comments yet.
  Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0016
  Status: Final
  Type: Standards Track
  Created: 2012-01-03
</pre>


Copyright: Public domain
==Abstract==


Status: Draft -> Deferred
This BIP describes a new "standard" transaction type for the Bitcoin scripting system, and defines additional validation rules that apply only to the new transactions.


Type: Informational
==Motivation==


The purpose of pay-to-script-hash is to move the responsibility for supplying the conditions to redeem a transaction from the sender of the funds to the redeemer.


The purpose of this document is purely informative and not normative. It aims to spread to the wider cryptographic community the various improvements to the well-known Bitcoin design that would address some limitations of the existing implementation that prevent its wider adoption. The proposed changes are far-reaching and as such are not suitable for immediate implementation. They are so extensive that it is certain that a complete reimplementation will be required. No matter what is the immediate fate of this proposal, I’m remaining hopeful that the ideas explained will remain public domain knowledge and will serve as a prior-art counterclaim in any future patent litigation.
The benefit is allowing a sender to fund any arbitrary transaction, no matter how complicated, using a fixed-length 20-byte hash that is short enough to scan from a QR code or easily copied and pasted.


The centerpiece of this proposal is the idea of “digital prospectus”: a program whose main functionality is to do perform a verification of the submitted blocks and transactions. This program will be cryptographically hashed and will become a “root prospectus hash” in this proposal and an equivalent of the newspaper headline in the present Bitcoin genesis block. In addition the “root prospectus hash” will become the identifier for the “digital financial security” in the transactional transport protocols. As such it will replace 4-byte integer 1 in the current Bitcoin protocol.
==Specification==


The choice of the programming language for the “digital prospectus” needs to be made early. The primary requirement is that the language needs to have very strong theoretical underpinnings: it must be able to efficiently express its own interpreter and there must be existing programs that are capable of proving simple theorems expressed in this language. It seems to me that some dialect of LISP would be suitable choice. LISP s-expressions maintain very close relationship between the human-readable text of the program (which will be hashed to form the digital prospectus) and the internal data structures that represent the program and which will be interpreted and verified many times during its lifetime. The runtime efficiency is pretty much immaterial; the properties that are tremendously important are (1) well-defined semantics; (2) the ability of the program to analyze and transform its own text; (3) possibility of secure implementations that are resistant to the cryptographic side-channel attacks like “differential fault analysis”, “differential power analysis”, “timing attack”, etc.
A new standard transaction type that is relayed and included in mined blocks is defined:


The exact content of the “digital prospectus” would depend on the type of the “digital financial security” that it describes. For the security like Bitcoin it would define the rules for the validity of the block and the transaction. It would exactly specify the fees that need to be paid for the inclusion of the transactions in the block and who is allowed to specify checkpoints for the longest chain of blocks. In the current Bitcoin implementation fees are pretty much left unspecified (with the exception of “dust spam defense”) and two block-chain checkpoints were signed by “fabianhjr”, who is pretty much unknown in the community.
    OP_HASH160 [20-byte-hash-value] OP_EQUAL


It isn’t assumed that the “digital prospectus” remains constant throughout the whole lifetime of the “digital financial security”. The “root prospectus” will be included in the root signature block. The implementation will provide a means of recording the “digital prospectus amendments” which in effect will patch the original prospectus. Throughout the lifetime of the “digital financial security” there will be many forks and joins in the DAG (directed acyclic graph) of the prospectuses. The acceptance of forks and joins will be left for the approval of the end user. In case of the competing forks it will be up to the end user to decide whom to trust. The choice needs to be made only when transacting, the peer can participate in multiple simultaneous versions of the amended security. There will be an obvious overhead of the storage and network bandwidth, but the user will not have to make any either-or choices unless actually transacting.
[20-byte-hash-value] shall be the push-20-bytes-onto-the-stack opcode (0x14) followed by exactly 20 bytes.


On the network transport layer the peers will locate each other using a DHT (distributed hash table) using both “root prospectus hash” as well as an ordered pair of the “root and amended prospectus hashes”. I don’t envision that the peers in the proposed protocol would need to shun any other peers. The peer-to-peer network will resemble more of Bittorrent peer-to-peer network: all peers share the DHT and make direct connections only when interested in the sharing of the particular torrent.
This new transaction type is redeemed by a standard scriptSig:
The “digital prospectus” moves the Bitcoin from the equivalent of the “oral contract” to the equivalent of the “written contract”. In the current implementation of Bitcoin there exist an implicit trust in the “core developer team”, their “Satoshi client C++ implementation” and the “consensus of the majority of the miners”. The proposed implementation would spell the requirements exactly and would allow continuing trading of the instruments among those who do not want to trust the consensus of the majority and any future amended prospectuses.


In other words it would change the Bitcoin government from the democracy to the republic.
    ...signatures... {serialized script}
The last but not least change allowed by the existence of the “digital prospectus” will be the change in scripting engine. Currently Bitcoin uses a simple postfix script language implemented as an automaton with a stack but without loops. The “no loop” requirement was to avoid possibly of attacks by infinite loop. I propose that the same programming language that is used to represent the digital prospectus is used to represent the scripts. If the prospectus writer decides to allow general scripting with looping she can include in the prospectus a relatively simple theorem prover: given the script and N inputs does the script return true or false in at most K*N steps, where K is arbitrary constant chosen by the prospectus writer. This is not a general undecidable stopping problem because the theorem prover can return “undecided within C*L steps”, where L is the length of the script and C another arbitrary constant in the prospectus. The strong syntax and semantic checker for scripts also has obvious benefits for software testing.


Another benefit of using LISP (or any similar language) for scripting lies in its transformability. There exist a body of research of ultra-reliable computing that used “SIMD-like” and/or “Hamming distance 3 or higher” coding for error detection and correction. Ultimately no LISP computers were used in the deep space probes because of overall power requirements. For the terrestrial finance transactions the absolute power used by the computer is not really limiting, but the invulnerability to the various side-channel attacks like differential fault analysis becomes a tremendous benefit. Those fault-hardening and SIMD-like transformations could be applied mechanically to the scripts so long as they are represented appropriately.
Transactions that redeem these pay-to-script outpoints are only considered standard if the ''serialized script'' - also referred to as the ''redeemScript'' - is, itself, one of the other standard transaction types.


Obviously Bitcoin stack automaton scripts can be automatically translated to the prefix s-expression notation and undergo the same transformations as above. But I don’t see the benefit it requiring this additional step aside from backward compatibility.
The rules for validating these outpoints when relaying transactions or considering them for inclusion in a new block are as follows:


Overall the program implementing the current proposal could be compatible with Bitcoin and all currently existing alternative block-chain currencies, including Litecoin, IxCoin, I0Coin, Tenebrix, and Fairbrix. It would be up to the Bitcoin core development team to commit to the precise rules regarding fees and checkpoints. It could even transact Solidcoin version 2 and would conceivably prevent any closed-source modifications that plague that clone of Bitcoin. The network transport protocols are currently incompatible, but the network adaptation layer would be very simple.
# Validation fails if there are any operations other than "push data" operations in the scriptSig.
# Normal validation is done: an initial stack is created from the signatures and {serialized script}, and the hash of the script is computed and validation fails immediately if it does not match the hash in the outpoint.
# {serialized script} is popped off the initial stack, and the transaction is validated again using the popped stack and the deserialized script as the scriptPubKey.


In summary this proposal encompasses three main changes: (1) explicit cryptographically signed and software-executable contract included in the root block, (2) cooperative DHT-based networking protocol that does away with IRC, dedicated ports and 4-byte identifiers, (3) general prefix script notation backed by strong syntax and semantic checkers.
These new rules should only be applied when validating transactions in blocks with timestamps >= 1333238400 (Apr 1 2012) <ref>[https://github.com/bitcoin/bitcoin/commit/8f188ece3c82c4cf5d52a3363e7643c23169c0ff Remove -bip16 and -paytoscripthashtime command-line arguments]</ref>. There are transactions earlier than 1333238400 in the block chain that fail these new validation rules. <ref>[https://web.archive.org/web/20141122040355/http://blockexplorer.com/tx/6a26d2ecb67f27d1fa5524763b49029d7106e91e3cc05743073461a719776192 Transaction 6a26d2ecb67f27d1fa5524763b49029d7106e91e3cc05743073461a719776192]</ref>. Older transactions must be validated under the old rules. (see the Backwards Compatibility section for details).
Because of this proposal is very far-reaching I suggest that it will be immediately placed in the dormant state. Initially we can work on clarifying its wording, but the full implementation will require a lot of discussion and research. Hopefully the information included here will stay in public domain and will spread amongst the cryptography research community.
 
For example, the scriptPubKey and corresponding scriptSig for a one-signature-required transaction is:
 
    scriptSig: [signature] {[pubkey] OP_CHECKSIG}
    scriptPubKey: OP_HASH160 [20-byte-hash of {[pubkey] OP_CHECKSIG} ] OP_EQUAL
 
Signature operations in the {serialized script} shall contribute to the maximum number allowed per block (20,000) as follows:
 
# OP_CHECKSIG and OP_CHECKSIGVERIFY count as 1 signature operation, whether or not they are evaluated.
# OP_CHECKMULTISIG and OP_CHECKMULTISIGVERIFY immediately preceded by OP_1 through OP_16 are counted as 1 to 16 signature operation, whether or not they are evaluated.
# All other OP_CHECKMULTISIG and OP_CHECKMULTISIGVERIFY are counted as 20 signature operations.
 
Examples:
 
+3 signature operations:
    {2 [pubkey1] [pubkey2] [pubkey3] 3 OP_CHECKMULTISIG}
 
+22 signature operations
    {OP_CHECKSIG OP_IF OP_CHECKSIGVERIFY OP_ELSE OP_CHECKMULTISIGVERIFY OP_ENDIF}
 
==Rationale==
 
This BIP replaces BIP 12, which proposed a new Script opcode ("OP_EVAL") to accomplish everything in this BIP and more.
 
The Motivation for this BIP (and BIP 13, the pay-to-script-hash address type) is somewhat controversial; several people feel that it is unnecessary, and complex/multisignature transaction types should be supported by simply giving the sender the complete {serialized script}. The author believes that this BIP will minimize the changes needed to all of the supporting infrastructure that has already been created to send funds to a base58-encoded-20-byte bitcoin addresses, allowing merchants and exchanges and other software to start supporting multisignature transactions sooner.
 
Recognizing one 'special' form of scriptPubKey and performing extra validation when it is detected is ugly. However, the consensus is that the alternatives are either uglier, are more complex to implement, and/or expand the power of the expression language in dangerous ways.
 
The signature operation counting rules are intended to be easy and quick to implement by statically scanning the {serialized script}. Bitcoin imposes a maximum-number-of-signature-operations per block to prevent denial-of-service attacks on miners. If there was no limit, a rogue miner might broadcast a block that required hundreds of thousands of ECDSA signature operations to validate, and it might be able to get a head start computing the next block while the rest of the network worked to validate the current one.
 
There is a 1-confirmation attack on old implementations, but it is expensive and difficult in practice. The attack is:
 
# Attacker creates a pay-to-script-hash transaction that is valid as seen by old software, but invalid for new implementation, and sends themselves some coins using it.
# Attacker also creates a standard transaction that spends the pay-to-script transaction, and pays the victim who is running old software.
# Attacker mines a block that contains both transactions.
 
If the victim accepts the 1-confirmation payment, then the attacker wins because both transactions will be invalidated when the rest of the network overwrites the attacker's invalid block.
 
The attack is expensive because it requires the attacker create a block that they know will be invalidated by the rest of the network. It is difficult because creating blocks is difficult and users should not accept 1-confirmation transactions for higher-value transactions.
 
==Backwards Compatibility==
 
These transactions are non-standard to old implementations, which will (typically) not relay them or include them in blocks.
 
Old implementations will validate that the {serialize script}'s hash value matches when they validate blocks created by software that fully support this BIP, but will do no other validation.
 
Avoiding a block-chain split by malicious pay-to-script transactions requires careful handling of one case:
 
* A pay-to-script-hash transaction that is invalid for new clients/miners but valid for old clients/miners.
 
To gracefully upgrade and ensure no long-lasting block-chain split occurs, more than 50% of miners must support full validation of the new transaction type and must switch from the old validation rules to the new rules at the same time.
 
To judge whether or not more than 50% of hashing power supports this BIP, miners are asked to upgrade their software and put the string "/P2SH/" in the input of the coinbase transaction for blocks that they create.
 
On February 1, 2012, the block-chain will be examined to determine the number of blocks supporting pay-to-script-hash for the previous 7 days. If 550 or more contain "/P2SH/" in their coinbase, then all blocks with timestamps after 15 Feb 2012, 00:00:00 GMT shall have their pay-to-script-hash transactions fully validated. Approximately 1,000 blocks are created in a week; 550 should, therefore, be approximately 55% of the network supporting the new feature.
 
If a majority of hashing power does not support the new validation rules, then rollout will be postponed (or rejected if it becomes clear that a majority will never be achieved).
 
===520-byte limitation on serialized script size===
 
As a consequence of the requirement for backwards compatibility the serialized script is itself subject to the same rules as any other PUSHDATA operation, including the rule that no data greater than 520 bytes may be pushed to the stack. Thus it is not possible to spend a P2SH output if the redemption script it refers to is >520 bytes in length. For instance while the OP_CHECKMULTISIG opcode can itself accept up to 20 pubkeys, with 33-byte compressed pubkeys it is only possible to spend a P2SH output requiring a maximum of 15 pubkeys to redeem: 3 bytes + 15 pubkeys * 34 bytes/pubkey = 513 bytes.
 
 
==Reference Implementation==
 
https://gist.github.com/gavinandresen/3966071
 
==See Also==
 
* https://bitcointalk.org/index.php?topic=46538
* The [[bip-0013.mediawiki|Address format for Pay to Script Hash BIP]]
* M-of-N Multisignature Transactions [[bip-0011.mediawiki|BIP 11]]
* [[bip-0016/qa.mediawiki|Quality Assurance test checklist]]
 
== References ==
<references>

Latest revision as of 13:15, 26 December 2021

This page describes a BIP (Bitcoin Improvement Proposal).
Please see BIP 2 for more information about BIPs and creating them. Please do not just create a wiki page.

Please do not modify this page. This is a mirror of the BIP from the source Git repository here.

  BIP: 16
  Layer: Consensus (soft fork)
  Title: Pay to Script Hash
  Author: Gavin Andresen <gavinandresen@gmail.com>
  Comments-Summary: No comments yet.
  Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0016
  Status: Final
  Type: Standards Track
  Created: 2012-01-03

Abstract

This BIP describes a new "standard" transaction type for the Bitcoin scripting system, and defines additional validation rules that apply only to the new transactions.

Motivation

The purpose of pay-to-script-hash is to move the responsibility for supplying the conditions to redeem a transaction from the sender of the funds to the redeemer.

The benefit is allowing a sender to fund any arbitrary transaction, no matter how complicated, using a fixed-length 20-byte hash that is short enough to scan from a QR code or easily copied and pasted.

Specification

A new standard transaction type that is relayed and included in mined blocks is defined:

   OP_HASH160 [20-byte-hash-value] OP_EQUAL

[20-byte-hash-value] shall be the push-20-bytes-onto-the-stack opcode (0x14) followed by exactly 20 bytes.

This new transaction type is redeemed by a standard scriptSig:

   ...signatures... {serialized script}

Transactions that redeem these pay-to-script outpoints are only considered standard if the serialized script - also referred to as the redeemScript - is, itself, one of the other standard transaction types.

The rules for validating these outpoints when relaying transactions or considering them for inclusion in a new block are as follows:

  1. Validation fails if there are any operations other than "push data" operations in the scriptSig.
  2. Normal validation is done: an initial stack is created from the signatures and {serialized script}, and the hash of the script is computed and validation fails immediately if it does not match the hash in the outpoint.
  3. {serialized script} is popped off the initial stack, and the transaction is validated again using the popped stack and the deserialized script as the scriptPubKey.

These new rules should only be applied when validating transactions in blocks with timestamps >= 1333238400 (Apr 1 2012) [1]. There are transactions earlier than 1333238400 in the block chain that fail these new validation rules. [2]. Older transactions must be validated under the old rules. (see the Backwards Compatibility section for details).

For example, the scriptPubKey and corresponding scriptSig for a one-signature-required transaction is:

   scriptSig: [signature] {[pubkey] OP_CHECKSIG}
   scriptPubKey: OP_HASH160 [20-byte-hash of {[pubkey] OP_CHECKSIG} ] OP_EQUAL

Signature operations in the {serialized script} shall contribute to the maximum number allowed per block (20,000) as follows:

  1. OP_CHECKSIG and OP_CHECKSIGVERIFY count as 1 signature operation, whether or not they are evaluated.
  2. OP_CHECKMULTISIG and OP_CHECKMULTISIGVERIFY immediately preceded by OP_1 through OP_16 are counted as 1 to 16 signature operation, whether or not they are evaluated.
  3. All other OP_CHECKMULTISIG and OP_CHECKMULTISIGVERIFY are counted as 20 signature operations.

Examples:

+3 signature operations:

   {2 [pubkey1] [pubkey2] [pubkey3] 3 OP_CHECKMULTISIG}

+22 signature operations

   {OP_CHECKSIG OP_IF OP_CHECKSIGVERIFY OP_ELSE OP_CHECKMULTISIGVERIFY OP_ENDIF}

Rationale

This BIP replaces BIP 12, which proposed a new Script opcode ("OP_EVAL") to accomplish everything in this BIP and more.

The Motivation for this BIP (and BIP 13, the pay-to-script-hash address type) is somewhat controversial; several people feel that it is unnecessary, and complex/multisignature transaction types should be supported by simply giving the sender the complete {serialized script}. The author believes that this BIP will minimize the changes needed to all of the supporting infrastructure that has already been created to send funds to a base58-encoded-20-byte bitcoin addresses, allowing merchants and exchanges and other software to start supporting multisignature transactions sooner.

Recognizing one 'special' form of scriptPubKey and performing extra validation when it is detected is ugly. However, the consensus is that the alternatives are either uglier, are more complex to implement, and/or expand the power of the expression language in dangerous ways.

The signature operation counting rules are intended to be easy and quick to implement by statically scanning the {serialized script}. Bitcoin imposes a maximum-number-of-signature-operations per block to prevent denial-of-service attacks on miners. If there was no limit, a rogue miner might broadcast a block that required hundreds of thousands of ECDSA signature operations to validate, and it might be able to get a head start computing the next block while the rest of the network worked to validate the current one.

There is a 1-confirmation attack on old implementations, but it is expensive and difficult in practice. The attack is:

  1. Attacker creates a pay-to-script-hash transaction that is valid as seen by old software, but invalid for new implementation, and sends themselves some coins using it.
  2. Attacker also creates a standard transaction that spends the pay-to-script transaction, and pays the victim who is running old software.
  3. Attacker mines a block that contains both transactions.

If the victim accepts the 1-confirmation payment, then the attacker wins because both transactions will be invalidated when the rest of the network overwrites the attacker's invalid block.

The attack is expensive because it requires the attacker create a block that they know will be invalidated by the rest of the network. It is difficult because creating blocks is difficult and users should not accept 1-confirmation transactions for higher-value transactions.

Backwards Compatibility

These transactions are non-standard to old implementations, which will (typically) not relay them or include them in blocks.

Old implementations will validate that the {serialize script}'s hash value matches when they validate blocks created by software that fully support this BIP, but will do no other validation.

Avoiding a block-chain split by malicious pay-to-script transactions requires careful handling of one case:

  • A pay-to-script-hash transaction that is invalid for new clients/miners but valid for old clients/miners.

To gracefully upgrade and ensure no long-lasting block-chain split occurs, more than 50% of miners must support full validation of the new transaction type and must switch from the old validation rules to the new rules at the same time.

To judge whether or not more than 50% of hashing power supports this BIP, miners are asked to upgrade their software and put the string "/P2SH/" in the input of the coinbase transaction for blocks that they create.

On February 1, 2012, the block-chain will be examined to determine the number of blocks supporting pay-to-script-hash for the previous 7 days. If 550 or more contain "/P2SH/" in their coinbase, then all blocks with timestamps after 15 Feb 2012, 00:00:00 GMT shall have their pay-to-script-hash transactions fully validated. Approximately 1,000 blocks are created in a week; 550 should, therefore, be approximately 55% of the network supporting the new feature.

If a majority of hashing power does not support the new validation rules, then rollout will be postponed (or rejected if it becomes clear that a majority will never be achieved).

520-byte limitation on serialized script size

As a consequence of the requirement for backwards compatibility the serialized script is itself subject to the same rules as any other PUSHDATA operation, including the rule that no data greater than 520 bytes may be pushed to the stack. Thus it is not possible to spend a P2SH output if the redemption script it refers to is >520 bytes in length. For instance while the OP_CHECKMULTISIG opcode can itself accept up to 20 pubkeys, with 33-byte compressed pubkeys it is only possible to spend a P2SH output requiring a maximum of 15 pubkeys to redeem: 3 bytes + 15 pubkeys * 34 bytes/pubkey = 513 bytes.


Reference Implementation

https://gist.github.com/gavinandresen/3966071

See Also

References

<references>