diff options
| -rw-r--r-- | README.mediawiki | 72 | ||||
| -rw-r--r-- | bip-0001.mediawiki | 37 | ||||
| -rw-r--r-- | bip-0016.mediawiki | 2 | ||||
| -rw-r--r-- | bip-0047.mediawiki | 69 | ||||
| -rw-r--r-- | bip-0065.mediawiki | 23 | ||||
| -rw-r--r-- | bip-0068.mediawiki | 245 | ||||
| -rw-r--r-- | bip-0068/encoding.png | bin | 0 -> 6311 bytes | |||
| -rw-r--r-- | bip-0103.mediawiki | 72 | ||||
| -rw-r--r-- | bip-0107.mediawiki | 83 | ||||
| -rw-r--r-- | bip-0112.mediawiki | 186 | ||||
| -rw-r--r-- | bip-0122.mediawiki | 112 | ||||
| -rw-r--r-- | bip-0122/chainid.png | bin | 0 -> 2967 bytes | |||
| -rw-r--r-- | bip-0125.mediawiki | 187 | ||||
| -rw-r--r-- | bip-0140.mediawiki | 113 | ||||
| -rw-r--r-- | bip-0141.mediawiki | 267 | ||||
| -rw-r--r-- | bip-0142.mediawiki | 157 | ||||
| -rw-r--r-- | bip-0143.mediawiki | 133 | ||||
| -rw-r--r-- | bip-0144.mediawiki | 122 | ||||
| -rw-r--r-- | bip-0144/witnesstx.png | bin | 0 -> 18923 bytes |
19 files changed, 1602 insertions, 278 deletions
diff --git a/README.mediawiki b/README.mediawiki index 925910c..8e82118 100644 --- a/README.mediawiki +++ b/README.mediawiki @@ -1,4 +1,4 @@ -People wishing to submit BIPs, first should propose their idea or document to the mailing list. After discussion they should email Greg Maxwell <gmaxwell@gmail.com>. After copy-editing and acceptance, it will be published here. +People wishing to submit BIPs, first should propose their idea or document to the mailing list. After discussion they should email Luke Dashjr <luke_bipeditor@dashjr.org>. After copy-editing and acceptance, it will be published here. We are fairly liberal with approving BIPs, and try not to be too involved in decision making on behalf of the community. The exception is in very rare cases of dispute resolution when a decision is contentious and cannot be agreed upon. In those cases, the conservative option will always be preferred. @@ -16,7 +16,7 @@ Those proposing changes should consider that ultimately consent may rest with th | [[bip-0001.mediawiki|1]] | BIP Purpose and Guidelines | Amir Taaki -| Standard +| Process | Active |- | [[bip-0009.mediawiki|9]] @@ -153,7 +153,7 @@ Those proposing changes should consider that ultimately consent may rest with th |- style="background-color: #cfffcf" | [[bip-0037.mediawiki|37]] | Bloom filtering -| Mike Hearn and Matt Corallo +| Mike Hearn, Matt Corallo | Standard | Accepted |- @@ -267,8 +267,8 @@ Those proposing changes should consider that ultimately consent may rest with th | Draft |- | [[bip-0068.mediawiki|68]] -| Consensus-enforced transaction replacement signalled via sequence numbers -| Mark Friedenbach +| Relative lock-time through consensus-enforced sequence numbers +| Mark Friedenbach, BtcDrak, Nicolas Dorier | Standard | Draft |- @@ -320,6 +320,12 @@ Those proposing changes should consider that ultimately consent may rest with th | Standard | Draft |- +| [[bip-0103.mediawiki|103]] +| Block size following technological growth +| Pieter Wuille +| Standard +| Draft +|- | [[bip-0105.mediawiki|105]] | Consensus based block size retargeting algorithm | BtcDrak @@ -332,21 +338,27 @@ Those proposing changes should consider that ultimately consent may rest with th | Standard | Draft |- +| [[bip-0107.mediawiki|107]] +| Dynamic limit on the block size +| Washington Y. Sanchez +| Standard +| Draft +|- | [[bip-0111.mediawiki|111]] | NODE_BLOOM service bit -| Matt Corallo and Peter Todd +| Matt Corallo, Peter Todd | Standard | Draft |- | [[bip-0112.mediawiki|112]] | CHECKSEQUENCEVERIFY -| BtcDrak and Mark Friedenbach +| BtcDrak, Mark Friedenbach | Standard | Draft |- | [[bip-0113.mediawiki|113]] | Median time-past as endpoint for lock-time calculations -| Thomas Kerin and Mark Friedenbach +| Thomas Kerin, Mark Friedenbach | Standard | Draft |- @@ -362,17 +374,59 @@ Those proposing changes should consider that ultimately consent may rest with th | Standard | Draft |- +| [[bip-0122.mediawiki|122]] +| URI scheme for Blockchain references / exploration +| Marco Pontello +| Standard +| Draft +|- | [[bip-0123.mediawiki|123]] | BIP Classification | Eric Lombrozo | Informational | Draft |- +| [[bip-0125.mediawiki|125]] +| Opt-in Full Replace-by-Fee Signaling +| David Harding, Peter Todd +| Standard +| Draft +|- | [[bip-0130.mediawiki|130]] -| sendheaders message +| sendheaders message | Suhas Daftuar | Standard | Draft +|- +| [[bip-0140.mediawiki|140]] +| Normalized TXID +| Christian Decker +| Standard +| Draft +|- +| [[bip-0141.mediawiki|141]] +| Segregated Witness (Consensus layer) +| Eric Lombrozo, Johnson Lau, Pieter Wuille +| Standard +| Draft +|- +| [[bip-0142.mediawiki|142]] +| Address Formats for Witness Program +| Johnson Lau +| Standard +| Draft +|- +| [[bip-0143.mediawiki|143]] +| Transaction signature verification for version 0 and version 1 witness program +| Johnson Lau, Pieter Wuille +| Standard +| Draft +|- +| [[bip-0144.mediawiki|144]] +| Segregated Witness (Peer Services) +| Eric Lombrozo, Pieter Wuille +| Standard +| Draft |} <!-- IMPORTANT! See the instructions at the top of this page, do NOT JUST add BIPs here! --> diff --git a/bip-0001.mediawiki b/bip-0001.mediawiki index 6901080..e1abadd 100644 --- a/bip-0001.mediawiki +++ b/bip-0001.mediawiki @@ -1,8 +1,8 @@ <pre> BIP: 1 Title: BIP Purpose and Guidelines - Status: Accepted - Type: Standards Track + Status: Active + Type: Process Created: 2011-08-19 </pre> @@ -13,6 +13,7 @@ BIP stands for Bitcoin Improvement Proposal. A BIP is a design document providin We intend BIPs to be the primary mechanisms for proposing new features, for collecting community input on an issue, and for documenting the design decisions that have gone into Bitcoin. The BIP author is responsible for building consensus within the community and documenting dissenting opinions. Because the BIPs are maintained as text files in a versioned repository, their revision history is the historical record of the feature proposal. + ==BIP Types== There are three kinds of BIP: @@ -23,30 +24,26 @@ There are three kinds of BIP: ==BIP Work Flow== -The BIP editors assign BIP numbers and change their status. Please send all BIP-related email to the BIP editor, which is listed under [[#BIP_Editors|BIP Editors]] below. Also see [[#BIP_Editor_Responsibilities__Workflow|BIP Editor Responsibilities & Workflow]]. +The BIP process begins with a new idea for Bitcoin. Each potential BIP must have a champion -- someone who writes the BIP using the style and format described below, shepherds the discussions in the appropriate forums, and attempts to build community consensus around the idea. The BIP champion (a.k.a. Author) should first attempt to ascertain whether the idea is BIP-able. Posting to the [https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev bitcoin-dev@lists.linuxfoundation.org] mailing list (and maybe the [https://bitcointalk.org/index.php?board=6.0 Development & Technical Discussion] forum) is the best way to go about this. -Authors MUST NOT self assign numbers, but should use an alias such as "bip-johndoe-infinitebitcoins" which includes the author's name/nick and the BIP subject. +Vetting an idea publicly before going as far as writing a BIP is meant to save both the potential author and the wider community time. Many ideas have been brought forward for changing Bitcoin that have been rejected for various reasons. Asking the Bitcoin community first if an idea is original helps prevent too much time being spent on something that is guaranteed to be rejected based on prior discussions (searching the internet does not always do the trick). It also helps to make sure the idea is applicable to the entire community and not just the author. Just because an idea sounds good to the author does not mean it will work for most people in most areas where Bitcoin is used. Small enhancements or patches often don't need standardisation between multiple projects; these don't need a BIP and should be injected into the relevant Bitcoin development work flow with a patch submission to the applicable Bitcoin issue tracker. -The BIP process begins with a new idea for Bitcoin. It is highly recommended that a single BIP contain a single key proposal or new idea. Small enhancements or patches often don't need a BIP and can be injected into the Bitcoin development work flow with a patch submission to the Bitcoin issue tracker. The more focused the BIP, the more successful it tends to be. The BIP editor reserves the right to reject BIP proposals if they appear too unfocused or too broad. If in doubt, split your BIP into several well-focused ones. +Once the champion has asked the Bitcoin community as to whether an idea has any chance of acceptance, a draft BIP should be presented to the [https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev bitcoin-dev] mailing list. This gives the author a chance to flesh out the draft BIP to make it properly formatted, of high quality, and to address additional concerns about the proposal. Following a discussion, the proposal should be sent to the bitcoin-dev list and the BIP editor with the draft BIP. This draft must be written in BIP style as described below, else it will be sent back without further regard until proper formatting rules are followed. -Each BIP must have a champion -- someone who writes the BIP using the style and format described below, shepherds the discussions in the appropriate forums, and attempts to build community consensus around the idea. The BIP champion (a.k.a. Author) should first attempt to ascertain whether the idea is BIP-able. Posting to the [https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev bitcoin-dev] mailing list (and maybe the [https://bitcointalk.org/index.php?board=6.0 Development&Technical Discussion] forum) is the best way to go about this. +BIP authors are responsible for collecting community feedback on both the initial idea and the BIP before submitting it for review. However, wherever possible, long open-ended discussions on public mailing lists should be avoided. Strategies to keep the discussions efficient include: setting up a separate SIG mailing list for the topic, having the BIP author accept private comments in the early design phases, setting up a wiki page or git repository, etc. BIP authors should use their discretion here. -Vetting an idea publicly before going as far as writing a BIP is meant to save the potential author time. Many ideas have been brought forward for changing Bitcoin that have been rejected for various reasons. Asking the Bitcoin community first if an idea is original helps prevent too much time being spent on something that is guaranteed to be rejected based on prior discussions (searching the internet does not always do the trick). It also helps to make sure the idea is applicable to the entire community and not just the author. Just because an idea sounds good to the author does not mean it will work for most people in most areas where Bitcoin is used. +It is highly recommended that a single BIP contain a single key proposal or new idea. The more focused the BIP, the more successful it tends to be. If in doubt, split your BIP into several well-focused ones. -Once the champion has asked the Bitcoin community as to whether an idea has any chance of acceptance, a draft BIP should be presented to [https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev bitcoin-dev@lists.linuxfoundation.org]. This gives the author a chance to flesh out the draft BIP to make properly formatted, of high quality, and to address initial concerns about the proposal. +The BIP editors assign BIP numbers and change their status. Please send all BIP-related email to the BIP editor, which is listed under [[#BIP_Editors|BIP Editors]] below. Also see [[#BIP_Editor_Responsibilities__Workflow|BIP Editor Responsibilities & Workflow]]. The BIP editor reserves the right to reject BIP proposals if they appear too unfocused or too broad. -Following a discussion, the proposal should be sent to the Bitcoin-dev list and the BIP editor with the draft BIP. This draft must be written in BIP style as described below, else it will be sent back without further regard until proper formatting rules are followed. +Authors MUST NOT self assign BIP numbers, but should use an alias such as "bip-johndoe-infinitebitcoins" which includes the author's name/nick and the BIP subject. -If the BIP editor approves, he will assign the BIP a number, label it as Standards Track, Informational, or Process, give it status "Draft", and add it to the git repository. The BIP editor will not unreasonably deny a BIP. Reasons for denying BIP status include duplication of effort, being technically unsound, not providing proper motivation or addressing backwards compatibility, or not in keeping with the Bitcoin philosophy. +If the BIP editor approves, he will assign the BIP a number, label it as Standards Track, Informational, or Process, give it status "Draft", and add it to the BIPs git repository. The BIP editor will not unreasonably deny a BIP. Reasons for denying BIP status include duplication of effort, disregard for formatting rules, being too unfocused or too broad, being technically unsound, not providing proper motivation or addressing backwards compatibility, or not in keeping with the Bitcoin philosophy. For a BIP to be accepted it must meet certain minimum criteria. It must be a clear and complete description of the proposed enhancement. The enhancement must represent a net improvement. The proposed implementation, if applicable, must be solid and must not complicate the protocol unduly. The BIP author may update the Draft as necessary in the git repository. Updates to drafts may also be submitted by the author as pull requests. Standards Track BIPs consist of two parts, a design document and a reference implementation. The BIP should be reviewed and accepted before a reference implementation is begun, unless a reference implementation will aid people in studying the BIP. Standards Track BIPs must include an implementation -- in the form of code, a patch, or a URL to same -- before it can be considered Final. -BIP authors are responsible for collecting community feedback on a BIP before submitting it for review. However, wherever possible, long open-ended discussions on public mailing lists should be avoided. Strategies to keep the discussions efficient include: setting up a separate SIG mailing list for the topic, having the BIP author accept private comments in the early design phases, setting up a wiki page or git repository, etc. BIP authors should use their discretion here. - -For a BIP to be accepted it must meet certain minimum criteria. It must be a clear and complete description of the proposed enhancement. The enhancement must represent a net improvement. The proposed implementation, if applicable, must be solid and must not complicate the protocol unduly. - Once a BIP has been accepted, the reference implementation must be completed. When the reference implementation is complete and accepted by the community, the status will be changed to "Final". A BIP can also be assigned status "Deferred". The BIP author or editor can assign the BIP this status when no progress is being made on the BIP. Once a BIP is deferred, the BIP editor can re-assign it to draft status. @@ -143,11 +140,11 @@ If you are interested in assuming ownership of a BIP, send a message asking to t ==BIP Editors== -The current BIP editor is Gregory Maxwell who can be contacted at [[mailto:gmaxwell@gmail.com|gmaxwell@gmail.com]]. +The current BIP editor is Luke Dashjr who can be contacted at [[mailto:luke_bipeditor@dashjr.org|luke_bipeditor@dashjr.org]]. ==BIP Editor Responsibilities & Workflow== -A BIP editor must subscribe to the Bitcoin development mailing list. All BIP-related correspondence should be sent (or CC'd) to gmaxwell@gmail.com. +The BIP editor subscribes to the Bitcoin development mailing list. All BIP-related correspondence should be sent (or CC'd) to luke_bipeditor@dashjr.org. For each new BIP that comes in an editor does the following: @@ -167,11 +164,9 @@ The BIP editor will: * List the BIP in [[README.mediawiki]] -* Send email back to the BIP author with next steps (post to bitcoin mailing list). +* Send email back to the BIP author with next steps (post to bitcoin-dev mailing list). -Many BIPs are written and maintained by developers with write access to the Bitcoin codebase. The BIP editors monitor BIP changes, and correct any structure, grammar, spelling, or markup mistakes we see. - -The editors don't pass judgement on BIPs. We merely do the administrative & editorial part. Except for times like this, there's relatively low volume. +The BIP editors are intended to fulfill administrative and editorial responsibilities. The BIP editors monitor BIP changes, and correct any structure, grammar, spelling, or markup mistakes we see. ==History== @@ -180,3 +175,5 @@ This document was derived heavily from Python's PEP-0001. In many places text wa ==Changelog== 10 Oct 2015 - Added clarifications about sumission process and BIP number assignment. + +01 Jan 2016 - Clarified early stages of BIP idea championing, collecting community feedback, etc. diff --git a/bip-0016.mediawiki b/bip-0016.mediawiki index 4c2a524..25b652d 100644 --- a/bip-0016.mediawiki +++ b/bip-0016.mediawiki @@ -37,7 +37,7 @@ The rules for validating these outpoints when relaying transactions or consideri # 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. -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 transaction earlier than 13333238400 in the block chain that fail these new validation rules. <ref>[http://blockexplorer.com/tx/6a26d2ecb67f27d1fa5524763b49029d7106e91e3cc05743073461a719776192 Transaction 6a26d2ecb67f27d1fa5524763b49029d7106e91e3cc05743073461a719776192]</ref>. Older transactions must be validated under the old rules. (see the Backwards Compatibility section for details). +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 transaction earlier than 1333238400 in the block chain that fail these new validation rules. <ref>[http://blockexplorer.com/tx/6a26d2ecb67f27d1fa5524763b49029d7106e91e3cc05743073461a719776192 Transaction 6a26d2ecb67f27d1fa5524763b49029d7106e91e3cc05743073461a719776192]</ref>. 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: diff --git a/bip-0047.mediawiki b/bip-0047.mediawiki index 8247e00..c3c5058 100644 --- a/bip-0047.mediawiki +++ b/bip-0047.mediawiki @@ -1,8 +1,10 @@ RECENT CHANGES: -* (21 Sep 2015) Correct base58check version byte +* (18 Dec 2015) Update explanations to resolve FAQs + +* (12 Oct 2015) Revise blinding method for notification transactions -* (18 Sep 2015) Clarify decoding of notification transactions +* (21 Sep 2015) Correct base58check version byte <pre> BIP: 47 @@ -29,9 +31,29 @@ Payment codes add identity information to transactions which is useful in a merc We define the following 3 levels in BIP32 path: -<pre> +<code> m / purpose' / coin_type' / identity' -</pre> +</code> + +The child keys derived from an identity are used in different ways: + +<code> +m / purpose' / coin_type' / identity' / 0 +</code> + +The 0th (non-hardened) child is the notification key. + +<code> +m / purpose' / coin_type' / identity' / 0 through 2147483647 +</code> + +These (non-hardened) keypairs are used for ECDH to generate deposit addresses. + +<code> +m / purpose' / coin_type' / identity' / 0' through 2147483647' +</code> + +These (hardened) keypairs are ephemeral payment codes. Apostrophe in the path indicates that BIP32 hardened derivation is used. @@ -49,19 +71,31 @@ Hardened derivation is used at this level. ===Identity=== -Identity is a particular extended public/private key pair. The extended public key is a payment code. +The identity derivation level produces an extended public key and its associated extended private key. -Identities SHOULD have 1:1 correspondence with a BIP44 account, as in each BIP44 account in an HD wallet should be assigned exactly one payment code which shares the same index value. +When the extended public key at this level is combined with the metadata specified in the Representation section below, the resulting entity is called a "payment code." + +This derivation level is equivalent to the Account level in BIP-44. Wallets SHOULD treat payment codes as intrinsically part of the BIP-44 account at the same index and create payment codes and accounts as pairs. + +For example, the payment code created represented by (m / 47' / 0' / 0') is part of the account represented by (m / 44' / 0' / 0'). + +The second account in a wallet consists of the new account/payment code pair created by using an index of 1 in as the account/identity level of both paths. + +Incoming payments received via this specification are equivalent to payments received to BIP-44 addresses, and unspent outputs from both types of addresses can be used as inputs in the same outgoing transaction. Hardened derivation is used at this level. Except where noted, all keys derived from a payment code use the public derivation method. +==Standard Payment Codes (v1)== + +===Representation=== + ====Binary Serialization==== A payment code contains the following elements: -* Byte 0: type. required value: 0x01 +* Byte 0: version. required value: 0x01 * Byte 1: features bit field. All bits must be zero except where specified elsewhere in this specification ** Bit 0: Bitmessage notification ** Bits 1-7: reserved @@ -85,7 +119,7 @@ It is assumed that Alice can easily obtain Bob's payment code via a suitable met ====Definitions==== -* Payment code: an extended public key which is associated with a particular identity +* Payment code: an extended public key and associated metadata which is associated with a particular identity/account * Notification address: the P2PKH address associated with the 0<sup>th</sup> public key derived from a payment code * Notification transaction: a transaction which sends an output to a notification address which includes an embedded payment code @@ -135,6 +169,17 @@ Bitcoins received via notification transactions require special handling in orde # Outputs received to notification addresses MAY be passed through a mixing service before being added to the user's spendable balance. # Outputs received to notification addresses MAY be donated to miners using dust-b-gone or an equivalent procedure. +=====Standard Notification Transaction Scripts===== + +Alice SHOULD use an input script in one of the following standard forms to expose a public key, and compliant applications SHOULD recognize all of these forms. + +* P2PK (pay to pubkey) +* P2PKH (pay to pubkey hash) +* Multisig (bare multisig, without P2SH) +* a script which spends any of the above script forms via P2SH (pay to script hash) + +Compatible wallets MAY provide a method for a user to manually specify the public key associated with a notification transaction in order to recover payment codes sent via non-standard notification transactions. + ====Sending==== # Each time Alice wants to initiate a transaction to Bob, Alice derives a unique P2PKH address for the transaction using ECDH follows: @@ -175,7 +220,7 @@ If Alice does not want her payment to Bob to be associated with her identity, sh ====Cold Storage==== -* Unlike traditional watching-only wallets, those associated with payment codes help in cold storage can not detect incoming payments immediately. +* Unlike traditional watching-only wallets, those associated with payment codes held in cold storage can not detect incoming payments immediately. * When the watching-only wallet detects an incoming notification transaction, it packages the transaction in an implementation-specific format suitable for transfer to the offline device. * The offline device recovers the payment code, then pre-generates a large number of relevant keypairs (example: 10000) in order to minimize the need for air gap round trips. * The offline device then packages the relevant public keys in an implementation-specific format suitable for transfer to the online device. @@ -194,7 +239,9 @@ When querying a public blockchain explorer, wallets SHOULD connect to the explor Previously-spendable funds will generally not be lost or become inaccessible after a recovery from a seed, but all information regarding previous outgoing payments will be lost. -The metadata which a wallet must store regarding the state an identity consists of: +In order to recover received funds from a seed, the wallet must obtain every notification it has ever received to its notification address, including all spent transactions. It then re-establishes its lookahead window for each subchain by scanning every derived address sequentially until it locates a contiguous block of unused addresses of a user-specified length. + +The metadata which a wallet must store to properly process outgoing transactions consists of: # A list of every payment code to which the identity has sent a notification transaction. ## This list is lost if a wallet must be recovered from a seed. @@ -233,7 +280,7 @@ A recipient prefers to receive notifications via Bitmessage indiates this prefer * Setting bit 0 of the features byte to 1 * Setting byte 67 of the serialized payment code to the desired Bitmessage address version -* Setting byte 67 of the serialized payment code to the desired Bitmessage stream number +* Setting byte 68 of the serialized payment code to the desired Bitmessage stream number The sender uses this information to construct a valid notification Bitmessage address: diff --git a/bip-0065.mediawiki b/bip-0065.mediawiki index b48fa75..df995de 100644 --- a/bip-0065.mediawiki +++ b/bip-0065.mediawiki @@ -2,7 +2,7 @@ BIP: 65 Title: OP_CHECKLOCKTIMEVERIFY Author: Peter Todd <pete@petertodd.org> - Status: Draft + Status: Accepted Type: Standards Track Created: 2014-10-01 </pre> @@ -16,11 +16,17 @@ some point in the future. ==Summary== -CHECKLOCKTIMEVERIFY redefines the existing NOP2 opcode. When executed it -compares the top item on the stack to the nLockTime field of the transaction -containing the scriptSig. If that top stack item is greater than the transaction's -nLockTime field the script fails immediately, otherwise script evaluation continues -as though a NOP was executed. +CHECKLOCKTIMEVERIFY redefines the existing NOP2 opcode. When executed, if +any of the following conditions are true, the script interpreter will terminate +with an error: + +* the stack is empty; or +* the top item on the stack is less than 0; or +* the lock-time type (height vs. timestamp) of the top stack item and the nLockTime field are not the same; or +* the top stack item is greater than the transaction's nLockTime field; or +* the nSequence field of the txin is 0xffffffff; + +Otherwise, script execution will continue as if a NOP had been executed. The nLockTime field in a transaction prevents the transaction from being mined until either a certain block height, or block time, has been reached. By @@ -92,7 +98,7 @@ making transaction malleability a non-issue. ====Two-factor wallets==== -Services like GreenAddress store Bitcoins with 2-of-2 multisig scriptPubKey's +Services like GreenAddress store bitcoins with 2-of-2 multisig scriptPubKey's such that one keypair is controlled by the user, and the other keypair is controlled by the service. To spend funds the user uses locally installed wallet software that generates one of the required signatures, and then uses a @@ -195,6 +201,7 @@ transaction output ''can'' be spent. Refer to the reference implementation, reproduced below, for the precise semantics and detailed rationale for those semantics. + case OP_NOP2: { // CHECKLOCKTIMEVERIFY @@ -270,7 +277,7 @@ https://github.com/petertodd/bitcoin/commit/ab0f54f38e08ee1e50ff72f801680ee84d0f ==Deployment== We reuse the double-threshold IsSuperMajority() switchover mechanism used in -BIP 66 with the same thresholds, but for nVersion = 4. The new rules are +BIP66 with the same thresholds, but for nVersion = 4. The new rules are in effect for every block (at height H) with nVersion = 4 and at least 750 out of 1000 blocks preceding it (with heights H-1000..H-1) also have nVersion >= 4. Furthermore, when 950 out of the 1000 blocks diff --git a/bip-0068.mediawiki b/bip-0068.mediawiki index 12b97c7..55905af 100644 --- a/bip-0068.mediawiki +++ b/bip-0068.mediawiki @@ -1,7 +1,10 @@ <pre> BIP: 68 - Title: Consensus-enforced transaction replacement signaled via sequence numbers (relative lock-time) + Title: Relative lock-time using consensus-enforced sequence numbers Author: Mark Friedenbach <mark@friedenbach.org> + BtcDrak <btcdrak@gmail.com> + Nicolas Dorier <nicolas.dorier@gmail.com> + kinoshitajona <kinoshitajona@gmail.com> Status: Draft Type: Standards Track Created: 2015-05-28 @@ -9,19 +12,42 @@ ==Abstract== -This BIP describes a modification to the consensus-enforced semantics of the sequence number field to enable a signed transaction input to remain invalid for a defined period of time after confirmation of its corresponding outpoint, for the purpose of supporting consensus-enforced transaction replacement features. +This BIP introduces relative lock-time (RLT) consensus-enforced semantics of the sequence number field to enable a signed transaction input to remain invalid for a defined period of time after confirmation of its corresponding outpoint. ==Motivation== -Bitcoin has sequence number fields for each input of a transaction. The original idea appears to have been that the highest sequence number should dominate and miners should prefer it over lower sequence numbers. This was never really implemented, and the half-implemented code seemed to be making an assumption that miners would honestly prefer the higher sequence numbers, even if the lower ones were much much more profitable. That turns out to be a dangerous assumption, and so most technical people have assumed that kind of sequence number mediated replacement was useless because there was no way to enforce "honest" behavior, as even a few rational (profit maximizing) miners would break that completely. The change described by this BIP provides the missing piece that makes sequence numbers do something significant with respect to enforcing transaction replacement without assuming anything other than profit-maximizing behavior on the part of miners. +Bitcoin transactions have a sequence number field for each input. The original idea appears to have been that a transaction in the mempool would be replaced by using the same input with a higher sequence value. Although this was not properly implemented, it assumes miners would prefer higher sequence numbers even if the lower ones were more profitable to mine. However, a miner acting on profit motives alone would break that assumption completely. The change described by this BIP repurposes the sequence number for new use cases without breaking existing functionality. It also leaves room for future expansion and other use cases. + +The transaction nLockTime is used to prevent the mining of a transaction until a certain date. nSequence will be repurposed to prevent mining of a transaction until a certain age of the spent output in blocks or timespan. This, among other uses, allows bi-directional payment channels as used in [https://github.com/ElementsProject/lightning/raw/master/doc/deployable-lightning.pdf Hashed Timelock Contracts (HTLCs)] and [https://github.com/bitcoin/bips/blob/master/bip-0112.mediawiki#Bidirectional_Payment_Channels BIP112]. ==Specification== -For transactions with an nVersion of 2 or greater, if the most significant bit (1 << 31) of a sequence number is clear, the remaining 31 bits are interpreted as an encoded relative lock-time. A sequence number with the most significant bit set is given no consensus meaning and can be included in any block, like normal, under all circumstances. +This specification defines the meaning of sequence numbers for transactions with an nVersion greater than or equal to 2 for which the rest of this specification relies on. + +All references to median-time-past (MTP) are as defined by BIP113. + +If bit (1 << 31) of the sequence number is set, then no consensus meaning is applied to the sequence number and can be included in any block under all currently possible circumstances. + +If bit (1 << 31) of the sequence number is not set, then the sequence number is interpreted as an encoded relative lock-time. + +The sequence number encoding is interpreted as follows: + +Bit (1 << 22) determines if the relative lock-time is time-based or block based: If the bit is set, the relative lock-time specifies a timespan in units of 512 seconds granularity. The timespan starts from the median-time-past of the output’s previous block, and ends at the MTP of the previous block. If the bit is not set, the relative lock-time specifies a number of blocks. -If the second most significant bit (1 << 30) is clear, the next 16 bits are interpreted as a minimum block-height constraint over the input's age. The remaining 14 bits have no consensus-enforced meaning. A sequence number of zero indicates a relative lock-time of zero blocks (bits 31 and 30 clear) and can be included in any block. A sequence number of 1 << 14 can be included in the next block after the input it is spending, or any block thereafter, but cannot be included in the same block as its parent. A sequence number of 2 << 14 can't be included until at least two blocks later, and so on. +The flag (1<<22) is the highest order bit in a 3-byte signed integer for use in bitcoin scripts as a 3-byte PUSHDATA with OP_CHECKSEQUENCEVERIFY (BIP 112). -Alternatively, if the second most significant bit (1 << 30) is set, the next 25 bits are interpreted as a minimum block-time constraint over the input's age. The remaining 5 bits have no consensus-enforced meaning. A sequence number with just that second most significant bit set (0x40000000) is interpreted as a relative lock-time of 0, measured in seconds, and can be included in the same block as the output being spent. Advancing that sequence number by 2^5 (0x40000020) constrains the transaction to be included in blocks with an nTime timestamp at least one second greater than the median time stamp of the 11 blocks prior to the block containing the coin being spent. Advancing the sequence number by an additional 2^5 (0x40000040) constrains the spend to be two seconds later, and so on. +This specification only interprets 16 bits of the sequence number as relative lock-time, so a mask of 0x0000ffff MUST be applied to the sequence field to extract the relative lock-time. The 16-bit specification allows for a year of relative lock-time and the remaining bits allow for future expansion. + +<img src=bip-0068/encoding.png></img> + +For time based relative lock-time, 512 second granularity was chosen because bitcoin blocks are generated every 600 seconds. So when using block-based or time-based, the same amount of time can be encoded with the available number of bits. Converting from a sequence number to seconds is performed by multiplying by 512 = 2^9, or equivalently shifting up by 9 bits. + +When the relative lock-time is time-based, it is interpreted as a minimum block-time constraint over the input's age. A relative time-based lock-time of zero indicates an input which can be included in any block. More generally, a relative time-based lock-time n can be included into any block produced 512 * n seconds after the mining date of the output it is spending, or any block thereafter. +The mining date of the output is equals to the median-time-past of the previous block which mined it. + +The block produced time is equal to the median-time-past of its previous block. + +When the relative lock-time is block-based, it is interpreted as a minimum block-height constraint over the input's age. A relative block-based lock-time of zero indicates an input which can be included in any block. More generally, a relative block lock-time n can be included n blocks after the mining date of the output it is spending, or any block thereafter. This is proposed to be accomplished by replacing IsFinalTx() and CheckFinalTx(), existing consensus and non-consensus code functions that return true if a transaction's lock-time constraints are satisfied and false otherwise, with LockTime() and CheckLockTime(), new functions that return a non-zero value if a transaction's lock-time or sequence number constraints are not satisfied and zero otherwise: @@ -33,28 +59,41 @@ This is proposed to be accomplished by replacing IsFinalTx() and CheckFinalTx(), /* Setting nSequence to this value for every input in a transaction * disables nLockTime. */ - const uint32_t CTxIn::SEQUENCE_FINAL = 0xffffffff; - /* Threshold for CTxIn::nSequence: below this value it is interpreted - * as arelative lock-time, otherwise ignored. */ - const uint32_t CTxIn::SEQUENCE_LOCKTIME_THRESHOLD = (1 << 31); - /* Threshold for CTxIn::nSequence when interpreted as a relative - * lock-time: below this value it has units of blocks, otherwise - * seconds. */ - const uint32_t CTxIn::SEQUENCE_UNITS_THRESHOLD = (1 << 30); - /* Number of reserved low-order bits (depending on units used) which - * are shifted out prior to relative lock-time constraint checking. */ - const int CTxIn::SEQUENCE_BLOCKS_OFFSET = 14; - const int CTxIn::SEQUENCE_SECONDS_OFFSET = 5; - - int64_t LockTime(const CTransaction &tx, - int flags, const CCoinsView* pCoinsView, - int nBlockHeight, int64_t nBlockTime) + static const uint32_t SEQUENCE_FINAL = 0xffffffff; + + /* If this flag set, CTxIn::nSequence is NOT interpreted as a + * relative lock-time. Setting the most significant bit of a + * sequence number disabled relative lock-time. */ + static const uint32_t SEQUENCE_LOCKTIME_DISABLE_FLAG = (1 << 31); + + /* If CTxIn::nSequence encodes a relative lock-time and this flag + * is set, the relative lock-time has units of 512 seconds, + * otherwise it specifies blocks with a granularity of 1. */ + static const uint32_t SEQUENCE_LOCKTIME_TYPE_FLAG = (1 << 22); + + /* If CTxIn::nSequence encodes a relative lock-time, this mask is + * applied to extract that lock-time from the sequence field. */ + static const uint32_t SEQUENCE_LOCKTIME_MASK = 0x0000ffff; + + /* In order to use the same number of bits to encode roughly the + * same wall-clock duration, and because blocks are naturally + * limited to occur every 600s on average, the minimum granularity + * for time-based relative lock-time is fixed at 512 seconds. + * Converting from CTxIn::nSequence to seconds is performed by + * multiplying by 512 = 2^9, or equivalently shifting up by + * 9 bits. */ + static const int SEQUENCE_LOCKTIME_GRANULARITY = 9; + + int64_t LockTime(const CTransaction &tx, int flags, const std::vector<int>* prevHeights, const CBlockIndex& block) { - CCoins coins; - + assert(prevHeights == NULL || prevHeights->size() == tx.vin.size()); + int64_t nBlockTime = (flags & LOCKTIME_MEDIAN_TIME_PAST) + ? block.GetAncestor(std::max(block.nHeight-1, 0))->GetMedianTimePast() + : block.GetBlockTime(); + bool fEnforceBIP68 = static_cast<uint32_t>(tx.nVersion) >= 2 && flags & LOCKTIME_VERIFY_SEQUENCE; - + // Will be set to the equivalent height- and time-based nLockTime // values that would be necessary to satisfy all relative lock- // time constraints given our view of block chain history. @@ -63,10 +102,10 @@ This is proposed to be accomplished by replacing IsFinalTx() and CheckFinalTx(), // Will remain equal to true if all inputs are finalized // (CTxIn::SEQUENCE_FINAL). bool fFinalized = true; - - BOOST_FOREACH(const CTxIn& txin, tx.vin) { + for (size_t txinIndex = 0; txinIndex < tx.vin.size(); txinIndex++) { + const CTxIn& txin = tx.vin[txinIndex]; // Set a flag if we witness an input that isn't finalized. - if (CTxIn::SEQUENCE_FINAL == txin.nSequence) + if (txin.nSequence == CTxIn::SEQUENCE_FINAL) continue; else fFinalized = false; @@ -74,70 +113,35 @@ This is proposed to be accomplished by replacing IsFinalTx() and CheckFinalTx(), // Do not enforce sequence numbers as a relative lock time // unless we have been instructed to, and a view has been // provided. - if (!(fEnforceBIP68 && pCoinsView)) + if (!fEnforceBIP68) continue; - // Sequence numbers equal to or above the locktime threshold - // are not treated as relative lock-times, nor are they given - // any consensus-enforced meaning at this point. - if (txin.nSequence >= CTxIn::SEQUENCE_LOCKTIME_THRESHOLD) + // Sequence numbers with the most significant bit set are not + // treated as relative lock-times, nor are they given any + // consensus-enforced meaning at this point. + if (txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_DISABLE_FLAG) continue; - // Fetch the UTXO corresponding to this input. - if (!pCoinsView->GetCoins(txin.prevout.hash, coins)) { - // It is fully expected that coinbases inputs are not - // found in the UTXO set. Proceed to the next intput... - if (txin.prevout.IsNull()) - continue; - // If a non-coinbase input cannot be found, we cannot - // be certain about whether lock-time constraints have - // been satisfied. Note that it should only ever be - // possible for this to happen with wallet transactions - // that have unknown inputs. - else - return std::numeric_limits<int64_t>::max(); - } - - // coins.nHeight is MEMPOOL_HEIGHT (an absurdly high value) - // if the parent transaction was from the mempool. We can't - // know what height it will have once confirmed, but we - // assume it makes it in the same block. - int nCoinHeight = std::min(coins.nHeight, nBlockHeight); - - if (txin.nSequence < CTxIn::SEQUENCE_UNITS_THRESHOLD) { + if (prevHeights == NULL) + continue; + + int nCoinHeight = (*prevHeights)[txinIndex]; + + if (txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG) { + + int64_t nCoinTime = block.GetAncestor(std::max(nCoinHeight-1, 0))->GetMedianTimePast(); + + // Time-based relative lock-times are measured from the + // smallest allowed timestamp of the block containing the + // txout being spent, which is the median time past of the + // block prior. + nMinTime = std::max(nMinTime, nCoinTime + (int64_t)((txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_MASK) << CTxIn::SEQUENCE_LOCKTIME_GRANULARITY) - 1); + } else { // We subtract 1 from relative lock-times because a lock- // time of 0 has the semantics of "same block," so a lock- // time of 1 should mean "next block," but nLockTime has // the semantics of "last invalid block height." - nMinHeight = std::max(nMinHeight, nCoinHeight + (int)( - txin.nSequence >> CTxIn::SEQUENCE_BLOCKS_OFFSET) - 1); - } else { - // In two locations that follow we make reference to - // chainActive.Tip(). To prevent a race condition, we - // store a reference to the current tip. - // - // Note that it is not guaranteed that indexBestBlock will - // be consistent with the passed in view. The proper thing - // to do is to have the view return time information about - // UTXOs. - const CBlockIndex& indexBestBlock = *chainActive.Tip(); - - // The only time the negative branch of this conditional - // is executed is when the prior output was taken from the - // mempool, in which case we assume it makes it into the - // same block (see above). - int64_t nCoinTime = (nCoinHeight <= (indexBestBlock.nHeight+1)) - ? indexBestBlock.GetAncestor(nCoinHeight-1)->GetMedianTimePast() - : nBlockTime; - - // Time-based relative lock-times are measured from the - // smallest allowed timestamp of the block containing the - // txout being spent, which is the median time past of the - // block prior. We subtract one for the same reason as - // above. - nMinTime = std::max(nMinTime, nCoinTime + (int64_t)(( - txin.nSequence - CTxIn::SEQUENCE_UNITS_THRESHOLD) - >> CTxIn::SEQUENCE_SECONDS_OFFSET) - 1); + nMinHeight = std::max(nMinHeight, nCoinHeight + (int)(txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_MASK) - 1); } } @@ -146,62 +150,30 @@ This is proposed to be accomplished by replacing IsFinalTx() and CheckFinalTx(), // are not enforced. if (fFinalized) return 0; - + if ((int64_t)tx.nLockTime < LOCKTIME_THRESHOLD) nMinHeight = std::max(nMinHeight, (int)tx.nLockTime); else nMinTime = std::max(nMinTime, (int64_t)tx.nLockTime); - if (nMinHeight >= nBlockHeight) + if (nMinHeight >= block.nHeight) return nMinHeight; + if (nMinTime >= nBlockTime) return nMinTime; return 0; - } - - int64_t CheckLockTime(const CTransaction &tx, int flags) - { - AssertLockHeld(cs_main); - - // By convention a negative value for flags indicates that the - // current network-enforced consensus rules should be used. - flags = std::max(flags, 0); - - // pcoinsTip contains the UTXO set for chainActive.Tip() - CCoinsViewMemPool viewMemPool(pcoinsTip, mempool); - const CCoinsView *pCoinsView = &viewMemPool; - - // CheckLockTime() uses chainActive.Height()+1 to evaluate - // nLockTime because when LockTime() is called within - // CBlock::AcceptBlock(), the height of the block *being* - // evaluated is what is used. Thus if we want to know if a - // transaction can be part of the *next* block, we need to call - // LockTime() with one more than chainActive.Height(). - const int nBlockHeight = chainActive.Height() + 1; - - // Timestamps on the other hand don't get any special treatment, - // because we can't know what timestamp the next block will have, - // and there aren't timestamp applications where it matters. - const int64_t nBlockTime = GetAdjustedTime(); - - return LockTime(tx, flags, pCoinsView, nBlockHeight, nBlockTime); - } -</pre> + }</pre> Code conditional on the return value of IsFinalTx() / CheckLockTime() has to be updated as well, since the semantics of the return value has been inverted. -==Rationale== - -Using sequence numbers for locking inputs makes sense, since no transaction can be in a block before its parent transactions. This means that a lower sequence number can always be included earlier than a higher one (even if the time the original coins being spent was unknown when the transaction was authored). Because of this, even rational miners should go along with the scheme: Take the lowest sequence number and collect the fees, or skip over it in the hopes that no one else takes a lower number before the next available higher number becomes spendable. And, of course, users are not constrained to make their sequence numbers go up only one at a time. So it's "take the most updated version, now, or gamble that no one in the next dozen blocks takes the most updated and that you manage to include the next to most when it finally becomes mineable." This is similar to how lock-time works. In fact, this scheme is precisely a per-input relative lock-time. - ==Example: Bidirectional payment channel== -A bidirectional payment channel can be established by two parties funding a single output in the following way: Alice funds a 1btc output which is the 2-of-2 multisig of Alice AND Bob, or Alice's key only after a sufficiently long timeout, e.g. 30 days or 4320 blocks. The channel-generating transaction is signed by Alice and broadcast to the network. +A bidirectional payment channel can be established by two parties funding a single output in the following way: Alice funds a 1 BTC output which is the 2-of-2 multisig of Alice AND Bob, or Alice's key only after a sufficiently long timeout, e.g. 30 days or 4320 blocks. The channel-generating transaction is signed by Alice and broadcast to the network. -Alice desires to send Bob a payment of 0.1btc. She does so by constructing a transaction spending the 1btc output and sending 0.1btc to Bob and 0.9btc back to herself. She provides her signature for the 2-of-2 multisig constraint, and sets a relative lock-time using the sequence number field such that the transaction will become valid 24-hours or 144 blocks before the refund timeout. Two more times Alice sends Bob a payment of 0.1btc, each time generating and signing her half of a transaction spending the 1btc output and sending 0.2btc, then 0.3btc to Bob with a relative lock-time of 29 days from creation of the channel. +Alice desires to send Bob a payment of 0.1 BTC. She does so by constructing a transaction spending the 1 BTC output and sending 0.1 BTC to Bob and 0.9 BTC back to herself. She provides her signature for the 2-of-2 multisig constraint, and sets a relative lock-time using the sequence number field such that the transaction will become valid 24-hours or 144 blocks before the refund timeout. Two more times Alice sends Bob a payment of 0.1 BTC, each time generating and signing her half of a transaction spending the 1btc output and sending 0.2 BTC, then 0.3 BTC to Bob with a relative lock-time of 29 days from creation of the channel. -Bob now desires to send Alice a refund of 0.25btc. He does so by constructing a transaction spending the 1btc output and sending 0.95btc (= 0.7btc + 0.25btc) to Alice and 0.05btc to himself. Since Bob will still have in his logs the transaction giving him 0.7btc 29 days after the creation of the channel, Alice demands that this new transaction have a relative lock-time of 28 days so she has a full day to broadcast it before the next transaction matures. +Bob now desires to send Alice a refund of 0.25 BTC. He does so by constructing a transaction spending the 1btc output and sending 0.95 BTC (= 0.7 BTC + 0.25 BTC) to Alice and 0.05 BTC to himself. Since Bob will still have in his logs the transaction giving him 0.7 BTC 29 days after the creation of the channel, Alice demands that this new transaction have a relative lock-time of 28 days so she has a full day to broadcast it before the next transaction matures. Alice and Bob continue to make payments to each other, decrementing the relative lock-time by one day each time the channel switches direction, until the present time is reached or either party desires to close out the channel. A close-out is performed by finalizing the input (nSequence = MAX_INT) and both parties signing. @@ -215,40 +187,41 @@ https://github.com/bitcoin/bitcoin/pull/6312 Credit goes to Gregory Maxwell for providing a succinct and clear description of the behavior of this change, which became the basis of this BIP text. +This BIP was edited by BtcDrak, Nicolas Dorier and kinoshitajona. + ==Deployment== -We reuse the double-threshold switch over mechanism from BIPs 34 and 66, with the same thresholds, but for nVersion = 4. The new rules are in effect for every block (at height H) with nVersion = 4 and at least 750 out of 1000 blocks preceding it (with heights H-1000..H-1) also have nVersion = 4. Furthermore, when 950 out of the 1000 blocks preceding a block do have nVersion = 4, nVersion = 3 blocks become invalid, and all further blocks enforce the new rules. +This BIP is to be deployed by either version-bits BIP9 or by isSuperMajority(). Exact details TDB. -It is recommended that this soft-fork deployment trigger include other related proposals for improving Bitcoin's lock-time capabilities, including [https://github.com/bitcoin/bips/blob/master/bip-0065.mediawiki BIP 65]: OP_CHECKLOCKTIMEVERIFY, [https://github.com/bitcoin/bips/blob/master/bip-0112.mediawiki BIP 112]: CHECKSEQUENCEVERIFY, and [https://github.com/bitcoin/bips/blob/master/bip-0113.mediawiki BIP 113] Median time-past as endpoint for lock-time calculations. +BIP68 MUST be deployed together with BIP113. It is also recommended to deploy BIP112 at the same time. ==Compatibility== The only use of sequence numbers by the Bitcoin Core reference client software is to disable checking the nLockTime constraints in a transaction. The semantics of that application are preserved by this BIP. -There may be other uses for the sequence number field that are not commonplace or yet to be discovered. To allow for other uses of the sequence number field, it is only interpreted as a relative lock-time as described in this BIP if the most significant bit is clear. This allows up to 31 bits of the sequence number field to be used for other purposes in applications which don't simultaneously need a per-input relative lock-time. In addition, the unused low-order bits of the relative lock-time encoding are available for use by future soft-fork extensions. +As can be seen from the specification section, a number of bits are undefined by this BIP to allow for other use cases by setting bit (1 << 31) as the remaining 31 bits have no meaning under this BIP. Additionally, bits (1 << 23) through (1 << 30) inclusive have no meaning at all when bit (1 << 31) is unset. + +Additionally, this BIP specifies only 16 bits to actually encode relative lock-time meaning a further 6 are unused (1 << 16 through 1 << 21 inclusive). This allows the possibility to increase granularity by soft-fork, or for increasing the maximum possible relative lock-time in the future. The most efficient way to calculate sequence number from relative lock-time is with bit masks and shifts: <pre> // 0 <= nHeight < 65,535 blocks (1.25 years) - nSequence = nHeight << 14; - nHeight = nSequence >> 14; + nSequence = nHeight; + nHeight = nSequence & 0x0000ffff; // 0 <= nTime < 33,554,431 seconds (1.06 years) - nSequence = 1<<30 | (nTime << 5); - nTime = (nSequence ^ 1<<30) >> 5; + nSequence = (1 << 22) | (nTime >> 9); + nTime = (nSequence & 0x0000ffff) << 9; </pre> ==References== Bitcoin mailing list discussion: https://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg07864.html -[https://github.com/bitcoin/bips/blob/master/bip-0034.mediawiki BIP 34]: Block v2, Height in Coinbase - -[https://github.com/bitcoin/bips/blob/master/bip-0065.mediawiki BIP 65]: OP_CHECKLOCKTIMEVERIFY +BIP112: https://github.com/bitcoin/bips/blob/master/bip-0112.mediawiki -[https://github.com/bitcoin/bips/blob/master/bip-0066.mediawiki BIP 66]: Strict DER signatures +BIP113: https://github.com/bitcoin/bips/blob/master/bip-0113.mediawiki -[https://github.com/bitcoin/bips/blob/master/bip-0112.mediawiki BIP 112]: CHECKSEQUENCEVERIFY +Hashed Timelock Contrats (HTLCs): https://github.com/ElementsProject/lightning/raw/master/doc/deployable-lightning.pdf -[https://github.com/bitcoin/bips/blob/master/bip-0113.mediawiki BIP 113]: Median time-past as endpoint for lock-time calculations diff --git a/bip-0068/encoding.png b/bip-0068/encoding.png Binary files differnew file mode 100644 index 0000000..cd7649e --- /dev/null +++ b/bip-0068/encoding.png diff --git a/bip-0103.mediawiki b/bip-0103.mediawiki new file mode 100644 index 0000000..39e8a3f --- /dev/null +++ b/bip-0103.mediawiki @@ -0,0 +1,72 @@ +<pre> + BIP: 103 + Title: Block size following technological growth + Author: Pieter Wuille <pieter.wuille@gmail.com> + Status: Draft + Type: Standards Track + Created: 2015-07-21 +</pre> + +==Abstract== + +This BIP proposes a block size growth intended to accommodate for hardware and other technological improvements for the foreseeable future. + +==Motivation== + +Many people want to see Bitcoin scale over time, allowing an increasing number of transactions on the block chain. It would come at an increased cost for the ecosystem (bandwidth, processing, and storage for relay nodes, as well as an impact on propagation speed of blocks on the network), but technology also improves over time. When all technologies depended on have improved as well as their availability on the market, there is no reason why Bitcoin's fundamental transaction rate cannot improve proportionally. + +Currently, there is a consensus rule in place that limits the size of blocks to 1000000 bytes. Changing this requires a hard-forking change: one that will require every full node in the network to implement the new rules. The new chain created by those changed nodes will be rejected by old nodes, so this would effectively be a request to the ecosystem to migrate to a new and incompatible network. Doing this while controversy exists is dangerous to the network and the ecosystem. + +Furthermore, the effective space available is always constrained by a hash rate majority and its ability to process transactions. No hard forking change that relaxes the block size limit can be guaranteed to provide enough space for every possible demand - or even any particular demand - unless strong centralization of the mining ecosystem is expected. Because of that, the development of a fee market and the evolution towards an ecosystem that is able to cope with block space competition should be considered healthy. This does not mean the block size or its limitation needs to be constant forever. However, the purpose of such a change should be evolution with technological growth, and not kicking the can down the road because of a fear of change in economics. + +Bitcoin's advantage over other systems does not lie in scalability. Well-designed centralized systems can trivially compete with Bitcoin's on-chain transactions in terms of cost, speed, reliability, convenience, and scale. Its power lies in transparency, lack of need for trust in network peers, miners, and those who influence or control the system. Wanting to increase the scale of the system is in conflict with all of those. Attempting to buy time with a fast increase is not wanting to face that reality, and treating the system as something whose scale trumps all other concerns. A long term scalability plan should aim on decreasing the need for trust required in off-chain systems, rather than increasing the need for trust in Bitcoin. + +In summary, hard forks are extremely powerful, and we need to use them very responsibly as a community. They have the ability to fundamentally change the technology or economics of the system, and can be used to disadvantage those who expected certain rules to be immutable. They should be restricted to uncontroversial changes, or risk eroding the expectation of low trust needed in the system in the longer term. As the block size debate has been controversial so far - for good or bad reasons - this BIP aims for gradual change and its effects start far enough in the future. + +==Specification== + +The block size limitation is replaced by the function below, applied to the median of the timestamps of the previous 11 blocks, or in code terms: the block size limit for pindexBlock is GetMaxBlockSize(pindexBlock->pprev->GetMedianTimePast()). + +The sigop limit scales proportionally. + +It implements a series of block size steps, one every ~97 days, between January 2017 and July 2063, each increasing the maximum block size by 4.4%. This allows an overall growth of 17.7% per year. + +<pre> +uint32_t GetMaxBlockSize(int64_t nMedianTimePast) { + // The first step is on January 1st 2017. + if (nMedianTimePast < 1483246800) { + return 1000000; + } + // After that, one step happens every 2^23 seconds. + int64_t step = (nMedianTimePast - 1483246800) >> 23; + // Don't do more than 11 doublings for now. + step = std::min<int64_t>(step, 175); + // Every step is a 2^(1/16) factor. + static const uint32_t bases[16] = { + // bases[i] == round(1000000 * pow(2.0, (i + 1) / 16.0)) + 1044274, 1090508, 1138789, 1189207, + 1241858, 1296840, 1354256, 1414214, + 1476826, 1542211, 1610490, 1681793, + 1756252, 1834008, 1915207, 2000000 + }; + return bases[step & 15] << (step / 16); +} +</pre> + +==Rationale== + +Waiting 1.5 years before the hard fork takes place should provide ample time to minimize the risk of a hard fork, if found uncontroversial. + +Because every increase (including the first) is only 4.4%, risk from large market or technological changes is minimized. + +The growth rate of 17.7% growth per year is consistent with the average growth rate of bandwidth the last years, which seems to be the bottleneck. If over time, this growth factor is beyond what the actual technology offers, the intention should be to soft fork a tighter limit. + +Using a time-based check is very simple to implement, needs little context, is efficient, and is trivially reviewable. Using the "median time past" guarantees monotonic behaviour, as this median is required to be increasing, according to Bitcoin's existing consensus rules. Using the "median time past" of the block before means we know in advance what the limit of each block will be, without depending on the actual block's timestamp. + +==Compatibility== + +This is a hard forking change, thus breaks compatbility with old fully-validating node. It should not be deployed without widespread consensus. + +==Acknowledgements== + +Thanks to Gregory Maxwell and Wladimir J. van der Laan for their suggestions. diff --git a/bip-0107.mediawiki b/bip-0107.mediawiki new file mode 100644 index 0000000..88a2c99 --- /dev/null +++ b/bip-0107.mediawiki @@ -0,0 +1,83 @@ +<pre> + BIP: 107 + Title: Dynamic limit on the block size + Author: Dr Washington Y. Sanchez <washington.sanchez@gmail.com> + Status: Draft + Type: Standards Track + Created: 2015-09-11 +</pre> + +==Abstract== + +This BIP proposes a dynamic limit to the block size based on transaction volume. + +==Motivation== + +Over the next few years, large infrastructure investments will be made into: + +# Improving global network connectivity +# Improving block propogation across the Bitcoin network +# Layer 2 services and networks for off-chain transactions +# General efficiency improvements to transactions and the blockchain + +* While there is a consensus between Bitcoin developers, miners, businesses and users that the block size needs to be increased, there is a lingering concern over the potential unintended consequences that may agument the trend towards network and mining centralization (largely driven by mining hardware such as ASICs) and thereby threaten the security of the network. +* In contrast, failing to respond to elevated on-chain transaction volume may lead to a consumer-failure of Bitcoin, where ordinary users - having enjoyed over 6 years of submitting transactions on-chain at relatively low cost - will be priced out of blockchain with the emergence of a prohibitive 'fee market'. +* These two concerns must be delicately balanced so that all users can benefit from a robust, scalable, and neutral network. + +==Specification== + +* Increases in the block size will occur in 2 phases +* '''Phase 1''' +** The block size will be increased similar to [[https://twitter.com/adam3us/status/636410827969421312|Adam Back's proposal]], as a safe runway prior to switching to Phase 2, while network and protocol infrastructure is improved +** The schedule: +*** ''2016-2017:'' 2 MB +*** ''2018-2019:'' 4 MB +*** ''2020:'' 6 MB +* '''Phase 2''' +** In 2020, the maximum block size will be increased dynamically according to sustained increases in transaction volume +** Every 4032 blocks (~4 weeks), a CHECK will be performed to determine if a raise in the maximum block size should occur +*** This calculates to a theoretical maximum of 13 increases per year +** IF of the last >= 3025 blocks were >=60% full, the maximum block size will be increased by 10% +** The maximum block size can only ever be increased, not decreased +* The default <code>limitfreerelay</code> will also be raised in proportion to maximum block size increases +** Transactions without fees can continue to be submitted and relayed on the network as per normal +** <code>limitfreerelay</code> also helps counter attempts to trigger a block size increase by 'penny-flooding' + +For example: +* When the dynamic rules for increasing the block size go live on January 1st 2020, the starting maximum block size wil be 6 MB +* IF >=3025 blocks are >= 3.6 MB, the new maximum block size become 6.6 MB. +* The theoretical maximum block size at the end of 2020 would be ~20.7 MB, assuming all 13 increases are triggered every 4 weeks by the end of the year. + +==Rationale== + +* '''Phase 1''' +** This runway has a schedule for conservative increases to the block size in order to relieve transaction volume pressure while allowing network and protocol infrastructure improvements to be made, as well as layer 2 services to emerge +* '''Phase 2''' +** Why 60% full blocks? +*** IF blocks are 60% full, they count as a ''vote'' towards increasing the block size +*** If this parameter is too low, the trigger sensitivity may be too high and vulnerable to spam attacks or miner collusion +*** Setting the parameter too high may set the trigger sensitivity too low, causing transaction delays that are trying to be avoided in the first place +*** Between September 2013-2015, the standard deviation measured from average block size (n=730 data points from blockchain.info) was ~ 0.13 MB or 13% of the maximum block size +**** If blocks needed to be 90% full before an increase were triggered, normal variance in the average block size would mean some blocks would be full before an increase could be triggered +*** Therefore, we need a ''safe distance'' away from the maximum block size to avoid normal block size variance hitting the limit. The 60% level represents a 3 standard deviation distrance from the limit. +** Why 3025 blocks? +*** The assessment period is 4032 blocks or ~ 4 weeks, with the threshold set as 4032 blocks/0.75 + 1 +*** Increases in the maximum block size should only occur after a sustained trend can be observed in order to: +***# Demonstrate a market-driven secular elevation in the transaction volume +***# Increase the cost to trigger an increase by spam attacks or miner collusion with zero fee transactions +*** In other words, increases to the maximum block size must be conservative but meaningful to relieve transaction volume pressure in response to true market demand +** Why 10% increase in the block size? +*** Increases in the block size are designed to be conservative and in balance with the number of theoretical opportunitites to increase the block size per year +*** Makes any resources spent for spam attacks or miner collusion relatively expensive to achieve a minor increase in the block size. A sustained attack would need to be launched that may be too costly, and ideally detectable by the community + +==Deployment== +''From BIP66:'' +We reuse the double-threshold switchover mechanism from BIP 34, with the same thresholds, but for nVersion = ''n''. The new rules are in effect for every block (at height H) with nVersion = ''n'' and at least 750 out of 1000 blocks preceding it (with heights H-1000..H-1) also have nVersion = ''n''. Furthermore, when 950 out of the 1000 blocks preceding a block do have nVersion = ''n'', nVersion = ''n-1'' blocks become invalid, and all further blocks enforce the new rules. + +==Acknowledgements== + +Thanks to Austin Hill, Brian Hoffman, Angel Leon, Bulukani Mlalazi, Chris Pacia, and Ryan Shea for their comments. + +==Copyright== + +This work is placed in the public domain. diff --git a/bip-0112.mediawiki b/bip-0112.mediawiki index f79fd32..643c617 100644 --- a/bip-0112.mediawiki +++ b/bip-0112.mediawiki @@ -20,24 +20,20 @@ being spent. ==Summary== CHECKSEQUENCEVERIFY redefines the existing NOP3 opcode. -When executed, the script interpreter continues as if a NOP was executed -so long as one of the following conditions is met: +When executed, if any of the following conditions are true, the script interpreter will terminate with an error: - * the transaction's nVersion field is 0 or 1; - * the top item on the stack is a value greater than or equal to (1 << 31); or - * the top item on the stack and the transaction input's sequence number are both relative lock-times of the same units, and the relative lock-time represented by the sequence number is greater than or equal to the relative lock-time represented by the top item on the stack. +* the stack is empty; or +* the top item on the stack is less than 0; or +* the top item on the stack has the disable flag (1 << 31) unset; and +** the transaction version is less than 2; or +** the transaction input sequence number disable flag (1 << 31) is set; or +** the relative lock-time type is not the same; or +** the top stack item is greater than the transaction sequence (when masked according to the BIP68); -Otherwise, script execution terminates with an error. +Otherwise, script execution will continue as if a NOP had been executed. -BIP 68's redefinition of nSequence prevents a non-final transaction -from being selected for inclusion in a block until the corresponding -input has reached the specified age, as measured in block height or -block time. By comparing the argument to CHECKSEQUENCEVERIFY against -the nSequence field, we indirectly verify a desired minimum age of the -the output being spent; until that relative age has been reached any -script execution pathway including the CHECKSEQUENCEVERIFY will fail -to validate, causing the transaction not to be selected for inclusion -in a block. +BIP 68 prevents a non-final transaction from being selected for inclusion in a block until the corresponding input has reached the specified age, as measured in block-height or block-time. By comparing the argument to CHECKSEQUENCEVERIFY against the nSequence field, we indirectly verify a desired minimum age of the +the output being spent; until that relative age has been reached any script execution pathway including the CHECKSEQUENCEVERIFY will fail to validate, causing the transaction not to be selected for inclusion in a block. ==Motivation== @@ -100,7 +96,7 @@ Some more specific applications of this idea: ====Hash Time-Locked Contracts==== -Hash Time-Locked Contracts (HTLCs) provide a general mechanism for offchain contract negotiation. An execution pathway can be made to require knowledge of a secret (a hash preimage) that can be presented within an invalidation time window. By sharing the secret it is possible to guarantee to the counterparty that the transaction will never be broadcast since this would allow the counterparty to claim the output immediately while one would have to wait for the time window to pass. If the secret has not been shared, the counterparty will be unable to use the instant pathway and the delayed pathway must be used instead. +Hash Time-Locked Contracts (HTLCs) provide a general mechanism for off-chain contract negotiation. An execution pathway can be made to require knowledge of a secret (a hash preimage) that can be presented within an invalidation time window. By sharing the secret it is possible to guarantee to the counterparty that the transaction will never be broadcast since this would allow the counterparty to claim the output immediately while one would have to wait for the time window to pass. If the secret has not been shared, the counterparty will be unable to use the instant pathway and the delayed pathway must be used instead. ====Bidirectional Payment Channels==== @@ -142,11 +138,12 @@ A simple output, paying to Alice might then look like: HASH160 <revokehash> EQUAL IF - DUP HASH160 <Bob key hash> CHECKSIGVERIFY + <Bob key hash> ELSE - "24h" CHECKSEQUENCEVERIFY - DUP HASH160 <Alice key hash> CHECKSIGVERIFY + "24h" CHECKSEQUENCEVERIFY DROP + <Alice key hash> ENDIF + CHECKSIG This allows Alice to publish the latest commitment transaction at any time and spend the funds after 24 hours, but also ensures that if Alice @@ -156,17 +153,18 @@ With CHECKLOCKTIMEVERIFY, this would look like: HASH160 <revokehash> EQUAL IF - DUP HASH160 <Bob key hash> CHECKSIGVERIFY + <Bob key hash> ELSE - "2015/12/15" CHECKLOCKTIMEVERIFY - DUP HASH160 <Alice key hash> CHECKSIGVERIFY + "2015/12/15" CHECKLOCKTIMEVERIFY DROP + <Alice key hash> ENDIF + CHECKSIG This form of transaction would mean that if the anchor is unspent on 2015/12/16, Alice can use this commitment even if it has been revoked, simply by spending it immediately, giving no time for Bob to claim it. -Ths means that the channel has a deadline that cannot be pushed +This means that the channel has a deadline that cannot be pushed back without hitting the blockchain; and also that funds may not be available until the deadline is hit. CHECKSEQUENCEVERIFY allows you to avoid making such a tradeoff. @@ -179,35 +177,33 @@ delay, and the entire output can be claimed by the other party if the revocation secret is known. With CHECKSEQUENCEVERIFY, a HTLC payable to Alice might look like the following in Alice's commitment transaction: - HASH160 DUP <revokehash> EQUAL + HASH160 DUP <R-HASH> EQUAL IF - DROP DUP HASH160 <Bob key hash> CHECKSIGVERIFY + "24h" CHECKSEQUENCEVERIFY + 2DROP + <Alice key hash> ELSE - <R hash> EQUAL - IF - "24h" CHECKSEQUENCEVERIFY DROP - DUP HASH160 <Alice key hash> CHECKSIGVERIFY - ELSE - "2015/10/20 10:33" CHECKLOCKTIMEVERIFY DROP - DUP HASH160 <Bob key hash> CHECKSIGVERIFY + <Commit-Revocation-Hash> EQUAL + NOTIF + "24h" CHECKLOCKTIMEVERIFY DROP ENDIF + <Bob key hash> ENDIF + CHECKSIG and correspondingly in Bob's commitment transaction: - HASH160 DUP <revokehash> EQUAL + HASH160 DUP <R-HASH> EQUAL + SWAP <Commit-Revocation-Hash> EQUAL ADD IF - DROP DUP HASH160 <Alice key hash> CHECKSIGVERIFY + <Alice key hash> ELSE - <R hash> EQUAL - IF - DUP HASH160 <Alice key hash> CHECKSIGVERIFY - ELSE - "24h" CHECKSEQUENCEVERIFY DROP - "2015/10/20 10:33" CHECKLOCKTIMEVERIFY DROP - DUP HASH160 <Bob key hash> CHECKSIGVERIFY - ENDIF + "2015/10/20 10:33" CHECKLOCKTIMEVERIFY + "24h" CHECKSEQUENCEVERIFY + 2DROP + <Bob key hash> ENDIF + CHECKSIG Note that both CHECKSEQUENCEVERIFY and CHECKLOCKTIMEVERIFY are used in the final branch of above to ensure Bob cannot spend the output until after both @@ -234,15 +230,19 @@ Refer to the reference implementation, reproduced below, for the precise semantics and detailed rationale for those semantics. - /* Threshold for nSequence: below this value it is interpreted - * as a relative lock-time, otherwise ignored. */ - static const uint32_t SEQUENCE_LOCKTIME_THRESHOLD = (1 << 31); + /* If this flag set, CTxIn::nSequence is NOT interpreted as a + * relative lock-time. */ + static const uint32_t SEQUENCE_LOCKTIME_DISABLE_FLAG = (1 << 31); - /* Threshold for nSequence when interpreted as a relative - * lock-time: below this value it has units of blocks, otherwise - * seconds. */ - static const uint32_t SEQUENCE_UNITS_THRESHOLD = (1 << 30); + /* If CTxIn::nSequence encodes a relative lock-time and this flag + * is set, the relative lock-time has units of 512 seconds, + * otherwise it specifies blocks with a granularity of 1. */ + static const uint32_t SEQUENCE_LOCKTIME_TYPE_FLAG = (1 << 22); + /* If CTxIn::nSequence encodes a relative lock-time, this mask is + * applied to extract that lock-time from the sequence field. */ + static const uint32_t SEQUENCE_LOCKTIME_MASK = 0x0000ffff; + case OP_NOP3: { if (!(flags & SCRIPT_VERIFY_CHECKSEQUENCEVERIFY)) { @@ -252,10 +252,10 @@ semantics and detailed rationale for those semantics. } break; } - + if (stack.size() < 1) return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION); - + // Note that elsewhere numeric opcodes are limited to // operands in the range -2**31+1 to 2**31-1, however it is // legal for opcodes to produce results exceeding that @@ -266,23 +266,23 @@ semantics and detailed rationale for those semantics. // to 5-byte bignums, which are good until 2**39-1, well // beyond the 2**32-1 limit of the nSequence field itself. const CScriptNum nSequence(stacktop(-1), fRequireMinimal, 5); - + // In the rare event that the argument may be < 0 due to // some arithmetic being done first, you can always use // 0 MAX CHECKSEQUENCEVERIFY. if (nSequence < 0) return set_error(serror, SCRIPT_ERR_NEGATIVE_LOCKTIME); - + // To provide for future soft-fork extensibility, if the - // operand is too large to be treated as a relative lock- - // time, CHECKSEQUENCEVERIFY behaves as a NOP. - if (nSequence >= SEQUENCE_LOCKTIME_THRESHOLD) + // operand has the disabled lock-time flag set, + // CHECKSEQUENCEVERIFY behaves as a NOP. + if ((nSequence & CTxIn::SEQUENCE_LOCKTIME_DISABLE_FLAG) != 0) break; - - // Actually compare the specified sequence number with the input. + + // Compare the specified sequence number with the input. if (!checker.CheckSequence(nSequence)) return set_error(serror, SCRIPT_ERR_UNSATISFIED_LOCKTIME); - + break; } @@ -291,38 +291,52 @@ semantics and detailed rationale for those semantics. // Relative lock times are supported by comparing the passed // in operand to the sequence number of the input. const int64_t txToSequence = (int64_t)txTo->vin[nIn].nSequence; - + // Fail if the transaction's version number is not set high // enough to trigger BIP 68 rules. if (static_cast<uint32_t>(txTo->nVersion) < 2) return false; - - // Sequence numbers above SEQUENCE_LOCKTIME_THRESHOLD - // are not consensus constrained. Testing that the transaction's - // sequence number is not above this threshold prevents - // using this property to get around a CHECKSEQUENCEVERIFY - // check. - if (txToSequence >= SEQUENCE_LOCKTIME_THRESHOLD) + + // Sequence numbers with their most significant bit set are not + // defined by BIP68. Testing that the transaction's sequence + // number do not have this bit set prevents using this property + // to get around a CHECKSEQUENCEVERIFY check. + if (txToSequence & CTxIn::SEQUENCE_LOCKTIME_DISABLE_FLAG) return false; + + // Mask off any bits that do not have BIP68 consensus-enforced meaning + // before doing the integer comparisons of ::VerifySequence. + const uint32_t nLockTimeMask = CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG + | CTxIn::SEQUENCE_LOCKTIME_MASK; - // There are two kinds of nSequence: lock-by-blockheight + if (!::VerifySequence(txToSequence & nLockTimeMask, + CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG, + nSequence & nLockTimeMask)) + return false; + + return true; + } + + static bool VerifySequence(int64_t txToSequence, int64_t nThreshold, const CScriptNum& nSequence) + { + // There are two kinds of nLockTime: lock-by-blockheight // and lock-by-blocktime, distinguished by whether - // nSequence < SEQUENCE_UNITS_THRESHOLD. + // nSequence < nThreshold (CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG). // // We want to compare apples to apples, so fail the script // unless the type of nSequence being tested is the same as // the nSequence in the transaction. if (!( - (txToSequence < SEQUENCE_UNITS_THRESHOLD && nSequence < SEQUENCE_UNITS_THRESHOLD) || - (txToSequence >= SEQUENCE_UNITS_THRESHOLD && nSequence >= SEQUENCE_UNITS_THRESHOLD) + (txToSequence < nThreshold && nSequence < nThreshold) || + (txToSequence >= nThreshold && nSequence >= nThreshold) )) return false; - + // Now that we know we're comparing apples-to-apples, the // comparison is a simple numeric one. - if (txTo->vin[nIn].nSequence > txToSequence) + if (nSequence > txToSequence) return false; - + return true; } @@ -336,25 +350,10 @@ https://github.com/bitcoin/bitcoin/pull/6564 ==Deployment== -We reuse the double-threshold switchover mechanism from BIPs 34 and -66, with the same thresholds, but for nVersion = 4. The new rules are -in effect for every block (at height H) with nVersion = 4 and at least -750 out of 1000 blocks preceding it (with heights H-1000..H-1) also -have nVersion = 4. Furthermore, when 950 out of the 1000 blocks -preceding a block do have nVersion = 4, nVersion = 3 blocks become -invalid, and all further blocks enforce the new rules. +This BIP is to be deployed by either version-bits BIP9 or by isSuperMajority(). Exact details TDB. -It is recommended that this soft-fork deployment trigger include other -related proposals for improving Bitcoin's lock-time capabilities, including: +It is recommended to deploy BIP68 and BIP113 at the same time as this BIP. -[https://github.com/bitcoin/bips/blob/master/bip-0065.mediawiki BIP 65]: -OP_CHECKLOCKTIMEVERIFY, - -[https://github.com/bitcoin/bips/blob/master/bip-0068.mediawiki BIP 68]: -Consensus-enforced transaction replacement signalled via sequence numbers, - -and [https://github.com/bitcoin/bips/blob/master/bip-0113.mediawiki BIP 113]: -Median-Past-Time-Lock. ==Credits== @@ -367,12 +366,12 @@ done by Peter Todd for the closely related BIP 65. BtcDrak authored this BIP document. -Thanks to Eric Lombrozo and Anthony Towns for contributing example usecases. +Thanks to Eric Lombrozo and Anthony Towns for contributing example use cases. ==References== -[https://github.com/bitcoin/bips/blob/master/bip-0068.mediawiki BIP 68] Consensus-enforced transaction replacement signalled via sequence numbers +[https://github.com/bitcoin/bips/blob/master/bip-0068.mediawiki BIP 68] Relative lock-time through consensus-enforced sequence numbers [https://github.com/bitcoin/bips/blob/master/bip-0065.mediawiki BIP 65] OP_CHECKLOCKTIMEVERIFY @@ -397,3 +396,4 @@ Thanks to Eric Lombrozo and Anthony Towns for contributing example usecases. This document is placed in the public domain. + diff --git a/bip-0122.mediawiki b/bip-0122.mediawiki new file mode 100644 index 0000000..902aa02 --- /dev/null +++ b/bip-0122.mediawiki @@ -0,0 +1,112 @@ +<pre> + BIP: 122 + Title: URI scheme for Blockchain references / exploration + Author: Marco Pontello <marcopon@gmail.com> + Status: Draft + Type: Standards Track + Created: 29 August 2015 + Post-History: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-August/010712.html +</pre> + +==Abstract== + +This BIP propose an URI scheme for looking up blocks, transactions, addresses on a Blockchain explorer, or in general to make proper Blockchain references + +==Motivation== + +The purpose of this URI scheme is to enable users to handle all the requests for details about blocks, transactions, etc. with their preferred tool (being that a web service or a local application). +Currently a Bitcoin client usually points to an arbitrary blockchain explorer when the user looks for the details of a transaction, or let him choose from a limited list of possible alternatives. +Other times resorting to cut&paste is needed. +The same happens with posts and messages that reference some particular txs or blocks, if they provide links at all. + +==Specification== + +The URI follow this form: + + <nowiki>blockchain:[//chain]</type/hash></nowiki> + +Where: + +{| class="wikitable" +! style="text-align: center;" | Element +! colspan="2" style="text-align: center;" | Description +! +|- +| chain +| colspan="2" | '''chain ID''' (see below) of the desired chain, leading 0s included. If omitted (which would be the usual case), Bitcoin main net is assumed. +| optional +|- +| rowspan="3" | type +| tx +| for transactions. +| rowspan="3" | +|- +| block +| for blocks (supports both hash or height). +|- +| address +| for addresses. +|- +| hash +| colspan="2" | the relevant hash to refer to (leading zeros included), or block height. +| +|} + +---- +===Definition of chain ID=== + +The '''chain ID''' of a chain is the block hash of the corresponding genesis block. For forked chains, it's the block hash of the first block after fork. + +So, for example: +<pre> +Bitcoin main : 000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f +Bitcoin test : 000000000933ea01ad0ee984209779baaec3ced90fa3f408719526f8d77f4943 +Bitcoin regtest: 0f9188f13cb7b2c71f2a335e3a4fc328bf5beb436012afca590b1a11466e2206 +</pre> + +An example of forked chain (Feathercoin, that forked Litecoin): + +<img src=bip-0122/chainid.png></img> + +<pre> +Litecoin : 12a765e31ffd4059bada1e25190f6e98c99d9714d334efa41a195a7e7e04bfe2 +Feathercoin: fdbe99b90c90bae7505796461471d89ae8388ab953997aa06a355bbda8d915cb +</pre> + + +==Examples== + +A transaction on Bitcoin main net: + blockchain:/tx/b462ae6eb8bdae2e060239a2a3ea5d9c3e0f9ef34d9717beb2dcf0ed42cee7da + +A block on Bitcoin main net: + blockchain:/block/00000000000000000119af5bcae2926df54ae262e9071a94a99c913cc217cc72 +or + blockchain:/block/372338 + +An address on Bitcoin main net: + blockchain:/address/16EW6Rv9P9AxFDBrZV816dD4sj1EAYUX3f + +A transaction on Bitcoin test net: + blockchain://000000000933ea01ad0ee984209779baaec3ced90fa3f408719526f8d77f4943/tx/3b95a766d7a99b87188d6875c8484cb2b310b78459b7816d4dfc3f0f7e04281a + +==Rationale== + +From the point of view of a wallet (or other Blockchain related tool) developer that need to show any kind of Blockchain references, using this scheme mean that he can simply make it a blockchain: link and be done with it, without having to worry about any specific Blockchain explorer or provide a means for the user to select one. + +Blockchain explorers in turn will simply offer to handle the blockchain: URI, the first time the user visit their website, or launch/install the application, or even set themselves if there isn't already one. + +Users get the convenience of using always their preferred explorer, which can be especially handy on mobile devices, where juggling with cut&paste is far from ideal. + +== Sample implementation == + +[https://github.com/MarcoPon/blockchain-exploration Demo Blockchain: URI handler on GitHub] + +==Acknowledgements== +Thanks to Btc Drak for suggesting to provide support for different networks. +Thanks to Jorge Timon for the idea of using genesis blocks hashes to identify them. +Thanks to Richard Moore, Matt Whitlock, Andreas Schildbach for suggestions about the structure and hierarchy of the URI scheme. + +==Copyright== + +This document is placed in the public domain.
\ No newline at end of file diff --git a/bip-0122/chainid.png b/bip-0122/chainid.png Binary files differnew file mode 100644 index 0000000..ab6957a --- /dev/null +++ b/bip-0122/chainid.png diff --git a/bip-0125.mediawiki b/bip-0125.mediawiki new file mode 100644 index 0000000..63788e9 --- /dev/null +++ b/bip-0125.mediawiki @@ -0,0 +1,187 @@ +<pre> + BIP: 125 + Title: Opt-in Full Replace-by-Fee Signaling + Author: David A. Harding <dave@dtrt.org>, Peter Todd <pete@petertodd.org> + Status: Draft + Type: Standards Track + Created: 2015-12-04 +</pre> + +==Abstract== + +Many nodes today will not replace any transaction in their mempool with +another transaction that spends the same inputs, making it difficult for +spenders to adjust their previously-sent transactions to deal with +unexpected confirmation delays or to perform other useful replacements. + +The opt-in full Replace-by-Fee (opt-in full-RBF) signaling policy +described here allows spenders to add a signal to a transaction indicating +that they want to be able to replace that transaction in the future. +In response to this signal, + +* Nodes may allow transactions containing this signal to be replaced in their mempools. + +* The recipient or recipients of a transaction containing this signal may choose not to treat it as payment until it has been confirmed, eliminating the risk that the spender will use allowed replacements to defraud them. + +Nodes and recipients may continue to treat transactions without the +signal the same way they treated them before, preserving the existing +status quo. + +==Summary== + +This policy specifies two ways a transaction can signal that it is +replaceable. + +* '''Explicit signaling:''' A transaction is considered to have opted in to allowing replacement of itself if any of its inputs have an nSequence number less than (0xffffffff - 1). + +* '''Inherited signaling:''' Transactions that don't explicitly signal replaceability are replaceable under this policy for as long as any one of their ancestors signals replaceability and remains unconfirmed. + +===Implementation Details=== + +The initial implementation expected in Bitcoin Core 0.12.0 uses the following rules: + +One or more transactions currently in the mempool (original +transactions) will be replaced by a new transaction (replacement +transaction) that spends one or more of the same inputs if, + +# The original transactions signal replaceability explicitly or through inheritance as described in the above Summary section. + +# The replacement transaction pays an absolute higher fee than the sum paid by the original transactions. + +# The replacement transaction does not contain any new unconfirmed inputs that did not previously appear in the mempool. (Unconfirmed inputs are inputs spending outputs from currently unconfirmed transactions.) + +# The replacement transaction must pay for its own bandwidth in addition to the amount paid by the original transactions at or above the rate set by the node's minimum relay fee setting. For example, if the minimum relay fee is 1 satoshi/byte and the replacement transaction is 500 bytes total, then the replacement must pay a fee at least 500 satoshis higher than the sum of the originals. + +# The number of original transactions to be replaced and their descendant transactions which will be evicted from the mempool must not exceed a total of 100 transactions. + +The initial implementation may be seen in +[https://github.com/bitcoin/bitcoin/pull/6871 Bitcoin Core PR#6871] +and specifically the master branch commits from +5891f870d68d90408aa5ce5b597fb574f2d2cbca to +16a2f93629f75d182871f288f0396afe6cdc8504 (inclusive). + +===Receiving wallet policy=== + +Wallets that display unconfirmed transactions to users or that provide +data about unconfirmed transactions to automated systems should consider +doing one of the following: + +# Conveying additional suspicion about opt-in full-RBF transactions to the user or data consumer. + +# Ignoring the opt-in transaction until it has been confirmed. + +Because descendant transactions may also be replaceable under this +policy through inherited signaling, any method used to process opt-in +full-RBF transactions should be inherited by any descendant transactions +for as long as any ancestor opt-in full-RBF transactions remain +unconfirmed. + +===Spending wallet policy=== + +Wallets that don't want to signal replaceability should use either a max +sequence number (0xffffffff) or a sequence number of (0xffffffff-1) when +then also want to use locktime; all known wallets currently do this. +They should also take care not to spend any unconfirmed transaction that +signals replaceability explicitly or through inherited signaling; most wallets also +currently do this by not spending any unconfirmed transactions except +for those they created themselves. + +Wallets that do want to make replacements should use explicit signaling +and meet the criteria described above in the Implementation Details +section. A +[https://en.bitcoin.it/wiki/Transaction_replacement Bitcoin Wiki page] +has been created to help wallet authors track deployed mempool policies +relating to transaction replacement. + +The initial implementation makes use of P2P protocol reject messages for +rejected replacements, allowing P2P clients to determine whether their +replacements were initially accepted by their peers. Standard P2P +lightweight client practice of sending to some peers while listening for +relays from other peers should allow clients to determine whether the +replacement has propagated. + +==Motivation== + +Satoshi Nakamoto's original Bitcoin implementation provided the +nSequence number field in each input to +[https://github.com/trottier/original-bitcoin/blob/master/src/main.cpp#L434 allow replacement] +of transactions containing that input within the +mempool. When receiving replacements, nodes were supposed to replace +transactions whose inputs had lower sequence numbers with transactions +that had higher sequence numbers. + +In that implementation, replacement transactions did not have to pay +additional fees, so there was no direct incentive for miners to +include the replacement and no built-in rate limiting that prevented +overuse of relay node bandwidth. Nakamoto +[https://github.com/bitcoin/bitcoin/commit/05454818dc7ed92f577a1a1ef6798049f17a52e7#diff-118fcbaaba162ba17933c7893247df3aR522 removed replacement] +from Bitcoin version 0.3.12, leaving only the +comment, "Disable replacement feature for now". + +Replacing transactions with higher-fee transactions provided a way for +spenders to align their desires with miners, but by the time a +Replace-by-Fee (RBF) patch was available to re-enable replacement, some +receivers had begun to expect that the first version of a transaction +they saw was highly likely to be the version of the transaction to be +confirmed, and so some users advocated that replacement should be +disallowed. + +To address those concerns, a variation on RBF was created that +required that the replacement transaction pay all of same outputs as +the original transaction in equal or greater amount. This was called +RBF First Seen Safe (RBF-FSS), and the original RBF became known as +full-RBF. Although agreeable to recipients who relied on the +first-seen version of a transaction, each use of RBF-FSS required +adding an extra input to a transaction, resulting in wallets being +unable to use it if they had no spare inputs, a loss of privacy when +inputs from different origins get used in the same transaction, and a +wasteful increase in transaction byte size. + +Opt-in full-RBF uses Nakamoto's original semantics (with a slight +tweak to allow locktime users to opt-out) to signal that replacement +is possible, providing first-seen users with the ability to ignore +those transactions while also allowing for the efficiency benefits +of full-RBF. + +There are no known problematic interactions between opt-in full-RBF and +other uses of nSequence. Specifically, opt-in full-RBF is compatible +with consensus-enforced locktime as provided in the Bitcoin 0.1 +implementation, draft BIP68 (Relative lock-time using consensus-enforced +sequence numbers), and draft BIP112 (CHECKSEQUENCEVERIFY). + +==Deployment== + +Now, and since Bitcoin's first release, 100% of the network hash rate +mines transactions using opt-in full-RBF semantics (sequence less than +(0xffffffff - 1)). + +Opt-in full-RBF as a default mempool replacement policy among nodes +and miners is expected to become widespread as they upgrade to Bitcoin +Core 0.12.0 (release expected Jan/Feb 2016) and similar node software +such as Bitcoin LJR. + +Actual replacement may be unreliable until two conditions have been satisfied: + +# Enough nodes have upgraded to support it, providing a relay path for replacements to go from spending wallets to miners controlling significant amounts of hash rate. + +# Enough hash rate has upgraded to support replacement, allowing for reasonable probability that a replacement can be mined. + +==Client support== + +No known wallet currently creates transactions by default with +nSequence set below (0xffffffff - 1), so no known existing wallet +explicitly signals replaceability by default. No known popular wallet +spends other users' unconfirmed transactions by default, so no known +existing wallets signals inherited replaceability. + +==See also== + +# [https://en.bitcoin.it/wiki/Transaction_replacement Transaction Replaceability on Bitcoin Wiki] targeted at helping wallet authors use RBF + +# Tools for creating opt-in full-RBF transactions: https://github.com/petertodd/replace-by-fee-tools#replace-by-fee-tools + +# [https://www.reddit.com/r/Bitcoin/comments/3urm8o/optin_rbf_is_misunderstood_ask_questions_about_it/ Reddit: Questions about opt-in RBF] targeted at helping community members understand opt-in full-RBF + +==Copyright== + +This document is placed in the public domain. diff --git a/bip-0140.mediawiki b/bip-0140.mediawiki new file mode 100644 index 0000000..b187a49 --- /dev/null +++ b/bip-0140.mediawiki @@ -0,0 +1,113 @@ +<pre> + BIP: 140 + Title: Normalized TXID + Author: Christian Decker <decker.christian@gmail.com> + Status: Draft + Type: Standards Track + Created: 2015-10-14 +</pre> +== Abstract == + +This BIP describes the use of normalized transaction IDs (NTXIDs) in order to eliminate transaction malleability, both in the third-party modification scenario as well as the participant modification scenario. The transaction ID is normalized by removing the signature scripts from transactions before computing its hash. The normalized transaction hashes are then used during the signature creation and signature verification of dependent transactions. + +== Motivation == + +Transaction malleability refers to the fact that transactions can be modified, either by one of the signers by re-signing the transaction or a third-party by modifying the signature representation. This is a problem since any modification to the serialized representation also changes the hash of the transaction, which is used by spending transaction to reference the funds that are being transferred. If a transaction is modified and later confirmed by ending up in the blockchain all transactions that depended on the original transaction are no longer valid, and thus orphaned. + +BIPs 62<ref>[[https://github.com/bitcoin/bips/blob/master/bip-0062.mediawiki|BIP 62 - Dealing with malleability]]</ref> and 66<ref>[[https://github.com/bitcoin/bips/blob/master/bip-0066.mediawiki|BIP 66 - Strict DER signatures]]</ref> alleviate the problem of third-party modification by defining a canonical representation of the signatures. However, checking the canonical representation is complex and may not eliminate all sources of third-party malleability. Furthermore, these BIPs do not address modifications by one of the signers, i.e., re-signing the transaction, because signers can produce any number of signatures due to the random parameter in ECDSA. + +This proposal eliminates malleability by removing the malleable signatures from the hash used to reference the outputs spent by a transaction. The new hash used to reference an output is called the ''normalized transaction ID''. The integrity of all data that is used to reference the output is guaranteed by the signature itself, and any modification that would change the normalized transaction ID would also invalidate the signature itself. + +Besides eliminating transaction malleability as a source of problems it also allows the use of transaction templates. Transaction templates simplify higher level protocols and allows new uses. They allow an unsigned template transaction to be used as a basis for a sequence of transaction and only once the sequence matches the signers' expectations they provide the necessary signatures for the template to become valid, thus opting in to the sequence. + +== Specification == + +The use of normalized transaction IDs is introduced as a softfork. The specification is divided into three parts: + +* Computation of the normalized transaction ID +* Introduction of a new extensible signature verification opcode to enable softfork deployment +* Changes to the UTXO tracking to enable normalized transaction ID lookup + +=== Normalized Transaction ID computation === + +In order to calculate the normalized transaction ID, the signature script is stripped from each input of the transaction of non-coinbase transactions and each input is normalized. Stripping the signature script is achieved by setting the script's length to 0 and removing the <code>uchar[]</code> array from the <code>TxIn</code>.<ref>[[https://en.bitcoin.it/wiki/Protocol_Specification#tx|Protocol Specification: TX]]</ref> +Inputs are then normalized by replacing the hash of each previous transaction with its normalized version if available, i.e., the normalized hash of the previous transaction that created the output being spent in the current transaction. Version 1 transactions do not have a normalized transaction ID hence the non-normalized transaction ID is used for input normalization. + +The normalized transaction ID is then computed as the double <code>SHA 256</code> hash of the normalized transaction matching the existing transaction ID computation. The normalized transaction ID remains unchanged even if the signatures of the transaction are replaced/malleated and describe a class of semantically identical transactions. In the following we use ''transaction instance ID'' to refer to the transaction ID computed on the transaction including signatures. Normalized transaction IDs for coinbase transactions are computed with the signature script in the coinbase input, in order to avoid hash collisions. + +=== OP_CHECKSIGEX === +This BIP introduces a new opcode <code>OP_CHECKSIGEX</code> which replaces <code>OP_NOP4</code>. <code>OP_CHECKSIGEX</code> subsumes <code>OP_CHECKSIGVERIFY</code> and <code>OP_CHECKMULTISIGVERIFY</code>, and extends them by accepting a new <code>VERSION</code> parameter. The version parameter is a single integer pushed onto the stack before invoking <code>OP_CHECKSIGEX</code> and is used to group and evolve future versions of signature checking opcodes. + +When executed <code>OP_CHECKSIGEX</code> pops the version from the stack and then performs the signature check according to the specified version. If the verifying client does not support the specified version, i.e., the version was defined after the release of the client, the client must treat the <code>OP_CHECKSIGEX</code> as an <code>OP_NOP</code>. + +==== Version 1 ==== + +The first version of <code>OP_CHECKSIGEX</code> (<code>VERSION=1</code>) implements normalized transaction IDs and uses Schnorr signatures instead of the current ECDSA signatures. + +Version 1 introduces the following new standard script format: + + m {pubkey}...{pubkey} n v OP_CHECKSIGEX + +with matching scriptSig format: + + {signature}...{signature} + +This is the standard ''m-of-n'' script defined in [https://github.com/bitcoin/bips/blob/master/bip-0011.mediawiki BIP 11] with an additional version parameter <code>v</code> and the new opcode. Singlesig transactions are encoded as ''1-of-1'' transactions. + +The existing <code>OP_CHECKMULTISIG</code> and <code>OP_CHECKMULTISIGVERIFY</code> have a bug<ref>[[https://bitcoin.org/en/developer-guide#multisig|Developer Documentation - Multisig]]</ref> that pops one argument too many from the stack. This bug is not reproduced in the implementation of OP_CHECKSIGEX, so the canonical solution of pushing a dummy value onto the stack is not necessary. + +The normalization is achieved by normalizing the transaction before computing the signaturehash, i.e., the hash that is signed. +The transaction must be normalized by replacing all transaction IDs in the inputs by their normalized variants and stripping the signature scripts. The normalized transction IDs are computed as described in the previous section. This normalization step is performed both when creating the signatures as well as when checking the signatures. + +=== Tracking Normalized Transaction IDs === + +The transaction version is bumped to 2. The new version signals to clients receiving the transaction that they should track the normalized transaction ID along with the transaction instance ID in the unspent transaction output (UTXO) set. Upon receiving a version 2 transaction the client computes the normalized transaction ID, annotates the outputs with it, and adds them into the UTXO set indexed by the transaction instance ID as before. Transactions continue using the transaction instance ID to reference the outputs, but while checking the signature they may get normalized. All network messages continue to use the transaction instance ID to reference the transaction, specifically <code>inv</code>, <code>getdata</code>, <code>tx</code> and <code>block</code> messages still use transaction instance IDs, not the normalized transaction IDs. + +Outputs created by version 1 transactions are not annotated with the normalized transaction ID, and when normalizing the hashes in transaction inputs referencing version 1 outputs are not modified. + +== Rationale == + +=== Normalization === +Normalized transaction IDs are provably non-malleable since no data is included in the signaturehash whose integrity is not also proven in the signature, thus any modification causing the hash to change will also invalidate the signature. +Normalized transactions are secure as they still use cryptographic hashes over all the semantic information of the transaction, i.e., the inputs, outputs and metadata, thus it is still computationally infeasible to cause a hash collision between transactions. + +There are a number of advantages to using normalized transaction IDs: + +* Like BIP 62 and BIP 66 it solves the problem of third-parties picking transactions out of the network, modifying them and reinjecting them. +* ''m-of-n'' multisig outputs are often used in higher level protocols<ref>[[http://www.tik.ee.ethz.ch/file/716b955c130e6c703fac336ea17b1670/duplex-micropayment-channels.pdf|A Fast and Scalable Payment Network with Bitcoin Duplex Micropayment Channels ]]</ref><ref>[[http://lightning.network/lightning-network-paper.pdf|The Bitcoin Lightning Network: +Scalable Off-Chain Instant Payments]]</ref> in which several parties sign a transaction. Without normalized transaction IDs it is trivial for one party to re-sign a transaction, hence changing the transaction hash and invalidating any transaction built on top of its outputs. Normalized transaction IDs force the ID not to change, even if a party replaces its signature. +* Many higher level protocols build structures of transactions on top of multisig outputs that are not completely signed. This is currently not possible without one party holding a fully signed transaction and then calculating the ID. It is desirable to be able to build successive transactions without one party collecting all signatures, and thus possibly lock in funds unilaterally. Normalized transaction IDs allow the use of transaction templates, i.e., completely unsigned transactions upon which further transactions can be built, and only once every party is assured the structure matches its expectations it signs the template, thus validating the template. + +The only occurence in which transactions can still be modified unilaterally is in the case <code>SIGHASH_NONE</code>, <code>SIGHASH_SINGLE</code> or <code>SIGHASH_ANYONECANPAY</code> is used. This however is not problematic since in these cases the creator of the transaction explicitly allows modification. + +In case of a transaction becoming invalid due to one of the inputs being malleated it is necessary to modify the spending transaction to reference the modified transaction ID. However, the signatures, which only use the normalized IDs, remain valid as long as the semantics of the funding transaction remain unchanged. An observer in the network may fix the transaction and reinject a corrected version. + +Using version 2 for transactions is an explicit opt-in to the normalized ID tracking and a simple upgrade for existing clients. It avoids having to reprocess the entire blockchain and computing the normalized transaction IDs for existing outputs in the UTXO. This would be further complicated by having to recursively compute normalized transaction IDs down to the coinbase transactions which created the coins. + +Tracking the normalized transaction IDs in the UTXO requires the storage of an additional hash per transaction whose outputs are not completely spent, which at 7,000,000 transactions with unspent outputs amounts to 224MB additional storage on disk. + +The coinbase transactions have been checked for hash-collisions and no collisions were found except for the coinbase transactions in blocks at heights 91842 and 91880, which are known to be identical<ref>[[https://github.com/bitcoin/bips/blob/master/bip-0030.mediawiki|BIP 30 - Duplicate transactions]]</ref>, and motivated the introduction of BIP 34.<ref>[[https://github.com/bitcoin/bips/blob/master/bip-0034.mediawiki|Block v2, Height in Coinbase]]</ref> Since coinbase transactions are invalid if transmitted outside of a block it is not possible to modify them on the fly and since they only mature after being included for a long time in the blockchain they are considered safe. + +=== OP_CHECKSIGEX === + +The new opcode <code>OP_CHECKSIGEX</code> was introduced in order to allow the use of normalized transaction IDs as a softfork and in order to keep the number of <code>OP_NOP</code>s needed to a bare minimum, while enabling future soft-fork updates to the signing algorithms. + +The additional argument containing the version can be pushed on the stack using a single byte up to version 16 (<code>OP_1</code> - <code>OP_16</code>), resulting in one byte overhead for this script type. Using the standard multisig format also for 1-of-1 transactions add an additional 2 bytes, however it also removes the bug requiring a dummy push, resulting in a single byte overhead. +Furthermore, using Schnorr signatures instead of ECDSA brings a number of improvements that reduce the size of transactions (''m-of-m'' is the same size as ''1-of-1'') and increase verification speed (batch signature validation by summing up keys and signatures). The code is already in bitcoin/secp256k1 and can be merged in. We limited the description of this BIP to re-using BIP 11 style ''m-of-n'' scripts to keep it short, however Schnorr also allows a number of more complex applications which we defer to future BIPs. + +Version 0 was intentionally skipped in order to guarantee that the top-most element before <code>OP_CHECKSIGEX</code> is non-zero. This is necessary to guarantee that non-upgraded clients, which interpret <code>OP_CHECKSIGEX</code> as <code>OP_NOP4</code>, do not end up with a zero value on top of the stack after execution, which would be interpreted as script failure. + +=== Impact === + +This is a softfork which replaces <code>OP_NOP4</code> with the new implementation of <code>OP_CHECKSIGEX</code>, as such the impact on the network is minimal. Wallets that do not implement this opcode will not be able to verify the validity of the scripts, however if transactions using <code>OP_CHECKSIGEX</code> are included in blocks they will accept them and track the inputs correctly. This is guaranteed since the transaction inputs still use the non-normalized transaction ID to reference the outputs to be claimed, hence non-upgraded wallets can still lookup the outputs and mark them as spent. Furthermore, clients that do not implement this BIP are unable to identify outputs using this script as their own, however upgrading and rescanning the blockchain will make them available. + +== See also == + +* [[bip-0062.mediawiki|BIP 62: Dealing with malleability]] +* [[bip-0066.mediawiki|BIP 66: Strict DER Signatures]] + +== References == +<references> + +==Copyright== +This document is placed in the public domain.
\ No newline at end of file diff --git a/bip-0141.mediawiki b/bip-0141.mediawiki new file mode 100644 index 0000000..ac44d87 --- /dev/null +++ b/bip-0141.mediawiki @@ -0,0 +1,267 @@ +<pre> + BIP: 141 + Title: Segregated Witness (Consensus layer) + Author: Eric Lombrozo <elombrozo@gmail.com> + Johnson Lau <jl2012@xbt.hk> + Pieter Wuille <pieter.wuille@gmail.com> + Status: Draft + Type: Standards Track + Created: 2015-12-21 +</pre> + +==Abstract== + +This BIP defines a new structure called a "witness" that is committed to blocks separately from the transaction merkle tree. This structure contains data required to check transaction validity but not required to determine transaction effects. In particular, scripts and signatures are moved into this new structure. + +The witness is committed in a tree that is nested into the block's existing merkle root via the coinbase transaction for the purpose of making this BIP soft fork compatible. A future hard fork can place this tree in its own branch. + +==Motivation== + +The entirety of the transaction's effects are determined by output consumption (spends) and new output creation. Other transaction data, and signatures in particular, are only required to validate the blockchain state, not to determine it. + +By removing this data from the transaction structure committed to the transaction merkle tree, several problems are fixed: + +# '''Nonintentional malleability becomes impossible'''. Since signature data is no longer part of the transaction hash, changes to how the transaction was authorized is no longer relevant to transaction identification. As a solution of transaction malleability, this is superior to the canonical signature approach (BIP62): +#* It prevents involuntary transaction malleability for any type of scripts, as long as all inputs are signed (with at least one CHECKSIG or CHECKMULTISIG operation) +#* In the case of an m-of-n CHECKMULTISIG script, a transaction is malleable only with agreement of m private key holders (as opposed to only 1 private key holder with BIP62) +#* It prevents involuntary transaction malleability due to unknown ECDSA signature malleability +#* It allows creation of unconfirmed transaction dependency chains without counterparty risk, an important feature for offchain protocols such as the Lightning Network +# '''Transmission of signature data becomes optional'''. It is needed only if a peer is trying to validate a transaction instead of just checking its existence. This reduces the size of SPV proofs and potentially improves the privacy of SPV clients as they can download more transactions using the same bandwidth. +# '''Some constraints could be bypassed with a soft fork''' by moving part of the transaction data to a structure unknown to current protocol, for example: +#* Size of witness could be ignored / discounted when calculating the block size, effectively increasing the block size to some extent +#* Hard coded constants, such as maximum data push size (520 bytes) or sigops limit could be reevaluated or removed +#* New script system could be introduced without any limitation from the existing script semantic +# '''Additional data required for fraud proofs can be added to witness'''. Extra data can be committed that allows short proofs of block invalidity that SPV nodes can quickly verify. +#* Backlinks for the outputs spent by the transaction's inputs can be provided. These backlinks consist of a block hash and an offset that thin clients can easily query and check to verify that the outputs exist. +#* Sum trees for transaction inputs and outputs can be committed making it possible to construct short proofs that no new coins are created in any noncoinbase transaction and that the miner does not add excessive fees to the coinbase transaction. + +==Specification== + +=== Commitment structure === + +!!!DRAFT ONLY!!! + +A new block rule is added which requires a commitment to the witness hashes in the coinbase (or an OP_RETURN output of a specific transaction, or somewhere else) + +(Hardfork after x year to move the commitment to block header?) + +Witness hash is the double SHA256 of a transaction including witnesses: http://blockhawk.net/diagrams/witnesstx.png. For the coinbase transaction, its witness hash is assumed to be 0x0000....0000. + +A witness root hash is calculated with all those witness hashes as leaves, in a way similar to the hashMerkleRoot in the block header. + +No witness data is allowed in blocks that don't commit to witness data, as this would otherwise leave room from spam. + +==== Proposal 1: balance tree (the current implementation) ==== +The commitment is a push of exactly 41 bytes: +*The first 4 bytes are commitment header: 0xaa21a9ed +*The next 4 bytes describe a nonce +*The next 1 byte is the "levels bytes", describes the number of levels in a Merkle tree (0 to 32) +*The next 32 bytes is a commitment root hash (not the witness root hash) + +Locator of the witness root hash is defined as: + +<pre>SHA256('WitnessV1\x00\x00\x00\x00\x00\x00\x00' || nonce)</pre> + +The first levels bits of locator, interpreted in little endian, are assumed to be the position in the leaves of the Merkle tree where the witness root hash goes. + +The coinbase's input's witness must consist of a single byte array of 32 * levels bytes, and are assumed to be the Merkle path to connect the witness root hash to the commitment root hash. + +====Proposal 2: imbalance tree==== +The commitment is a push of exactly 40 bytes: +*The first 4 bytes are commitment header: 0xaa21a9ed +*The next 4 bytes describe a nonce +*The next 32 bytes is a commitment root hash (not the witness root hash) + +Locator of the witness root hash is defined as: + +<pre>SHA256('WitnessV1\x00\x00\x00\x00\x00\x00\x00' || nonce)</pre> + +The first levels bits of locator, interpreted in little endian, are assumed to be the position in the leaves of the Merkle tree where the witness root hash goes. + +The coinbase's input's witness must consist of a single byte array, which the size must be a multiple of 32 bytes but not bigger than 32*32 bytes. These are assumed to be the Merkle path to connect the witness root hash to the commitment root hash. Depth of the commitment is determined by the length of the path. If the depth of the tree is 0, the path should be represented by 0x00, and the witness root hash will be same as the commitment root hash. + +=== Block size limit === +Blocks are currently limited to 1 MB total size. We change this restriction as follows: + +We define a base block size s<sub>b</sub> consisting of the existing header and transactions, a witness size s<sub>w</sub> consisting of only the size of the witness data, and a virtual block size s<sub>v</sub> = s<sub>b</sub> + s<sub>w</sub>/4. + +The new rule is s<sub>v</sub> <= 1 MB. + +=== Witness program === + +* A scriptPubKey (or redeemScript as defined in BIP16/P2SH) that consists of a 1-byte push opcode (for 0 to 16) followed by a data push between 2 and 32 bytes gets a new special meaning. The value of the first push is called the "version byte". The following byte vector pushed is called the "witness program". +** In case the scriptPubKey pushes a version byte and witness program directly, the scriptSig must be exactly empty. +** In case the redeemScript pushes a version byte and witness program, the scriptSig must be exactly the single push of the redeemScript. + +** If the version byte is 0, the WP is the actual script. +*** The script is executed after normal script evaluation but with data from the witness rather than the scriptSig. +*** The program must not fail, and result in exactly a single TRUE on the stack. +** If the version byte is 1, the WP must be 32 bytes, as a SHA256 hash of the actual script. +*** The witness must consist of an input stack to feed to the program, followed by the serialized program. +*** The serialized program is popped off the initial witness stack. Hash of the serialized program must match the hash pushed in the witness program. +*** The serialized program is deserialized, and executed after normal script evaluation with the remaining witness stack. +*** The script must not fail, and result in exactly a single TRUE on the stack. +** If the version byte is 2 to 16, no further interpretation of the witness program or witness happens. + +=== Other consensus critical constraints === + +== Block size analysis == +WORK IN PROGRESS + +Definitions: +<pre> + Core block size (CBS): The block size as seen by a non-upgrading full node + Witness size (WS): The total size of witness data in a block + Total block size (TBS): CBS + WS + Witness discount (WD): A discount factor for witness data in VBS calculation (1 = no discount) + Virtual block size (VBS): CBS + (WS * WD) + Witness adoption (WA): Proportion (in size) of new format transactions among all transactions + Prunable ratio (PR): Proportion of signature data size in a transaction +</pre> + +With some transformation it could be shown that: +<pre> + TBS = CBS / (1 - WA * PR) + = VBS / (1 - WA * PR * (1 - WD)) +</pre> + +In order to keep the proposal as a soft fork, the CBS must not have a upper limit higher than 1MB. + +The PR heavily depends on the transaction script type and input-output ratio. For example, the PR of 1-in 2-out P2PKH and 1-in 1-out 2-of-2 multisig P2SH are about 47% and 72% respectively. According to the data presented by Pieter Wuille on 7 December 2015, the current average PR on the blockchain is about 60%. + + + +== Examples == + +=== Version 0 witness program === + +The following example is a version 0 witness program, equivalent to the existing Pay-to-Pubkey-Hash (P2PKH) output. + + witness: <signature> <pubkey> + scriptSig: (empty) + scriptPubKey: OP_0 <0x76A914{20-byte-hash-value}88AC> + +The OP_0 indicates the following push is a version 0 witness program. The witness program is deserialized and becomes: + + DUP HASH160 <20byte-hash-value> EQUALVERIFY CHECKSIG + +The script is executed with the data from witness + + <signature> <pubkey> DUP HASH160 <20byte-hash-value> EQUALVERIFY CHECKSIG + +Comparing with a P2PKH output, the witness program equivalent occupies 2 more bytes in the scriptPubKey, while moving the signature and public key from scriptSig to witness. + +=== Version 1 witness program === + +The following example is an 1-of-2 multi-signature version 1 witness program. + + witness: 0 <signature1> <0x5121{33-byte-pubkey1}21{33-byte-pubkey2}52AE> + scriptSig: (empty) + scriptPubKey: OP_1 <0x{32-byte-hash-value}> + +The OP_1 in scriptPubKey indicates the following push is a version 1 witness program. The last item in the witness is popped off, hashed with SHA256, compared against the 32-byte-hash-value in scriptPubKey, and deserialized: + + 1 <33-byte-pubkey1> <33-byte-pubkey2> 2 CHECKMULTISIG + +The script is executed with the remaining data from witness: + + 0 <signature1> 1 <33-byte-pubkey1> <33-byte-pubkey2> 2 CHECKMULTISIG + +Since the actual program is larger than 32 bytes, it cannot be accommodated in a version 0 witness program. A version 1 witness program allows arbitrarily large script as the 520-byte push limit is bypassed. + +The scriptPubKey occupies 34 bytes, as opposed to 23 bytes of P2SH. The increased size improves security against possible collision attacks, as 2^80 work is not infeasible anymore (By the end of 2015, 2^84 hashes have been calculated in Bitcoin mining since the creation of Bitcoin). The spending script is same as the one for an equivalent P2SH output but is moved to witness. + +=== Witness program nested in Pay-to-Script-Hash === + +The following example is the same 1-of-2 multi-signature version 1 witness program, but nested in a P2SH output. + + witness: 0 <signature1> <0x5121{33-byte-pubkey1}21{33-byte-pubkey2}52AE> + scriptSig: <0x5120{32-byte-hash-value}> + scriptPubKey: HASH160 <20-byte-hash-value> EQUAL + +The only item in scriptSig is hashed with HASH160, compared against the 20-byte-hash-value in scriptPubKey, and interpreted as: + + OP_1 <0x{32-byte-hash-value}> + +The version 1 witness program is then executed as described in the last example + +Comparing with the last example, the scriptPubKey is 11 bytes smaller (with reduced security) while witness is the same. However, it also requires 35 bytes in scriptSig, which is not prunable in transmission. Although a nested witness program is less efficient in many ways, its payment address is fully transparent and backward compatible for all Bitcoin reference client since version 0.6.0. + +=== Trust-free unconfirmed transaction dependency chain === +Segregated witness fixes the problem of transaction malleability fundamentally, which enables the building of unconfirmed transaction dependency chains in a trust-free manner. + +Two parties, Alice and Bob, may agree to send certain amount of Bitcoin to a 2-of-2 multisig output (the "funding transaction"). Without signing the funding transaction, they may create another transaction, time-locked in the future, spending the 2-of-2 multisig output to third account(s) (the "spending transaction"). Alice and Bob will sign the spending transaction and exchange the signatures. After examining the signatures, they will sign and commit the funding transaction to the blockchain. Without further action, the spending transaction will be confirmed after the lock-time and release the funding according to the original contract. It also retains the flexibility of revoking the original contract before the lock-time, by another spending transaction with shorter lock-time, but only with mutual-agreement of both parties. + +Such setups is not possible with BIP62 as the malleability fix, since the spending transaction could not be created without both parties first signing the funding transaction. If Alice reveals the funding transaction signature before Bob does, Bob is able to lock up the funding indefinitely without ever signing the spending transaction. + +Unconfirmed transaction dependency chain is a fundamental building block of more sophisticated payment networks, such as duplex micropayment channel and the Lightning Network, which have the potential to greatly improve the scalability and efficiency of the Bitcoin system. + +== Future extensions == +=== Compact fraud proof for SPV nodes === +Bitcoin right now only has two real security models. A user either runs a full-node which validates every block with all rules in the system, or a SPV (Simple Payment Verification) client which only validates the headers as a proof of publication of some transactions. The Bitcoin whitepaper suggested that SPV nodes may accept alerts from full nodes when they detect an invalid block, prompting the SPV node to download the questioned blocks and transactions for validation. This approach, however, could become a DoS attack vector as there is virtually no cost to generate a false alarm. An alarm must come with a compact, yet deterministic fraud proof. + +In the current Bitcoin protocol, it is possible to generate compact fraud proof for almost all rules except a few: + +# It is not possible to prove a miner has introduced too many Bitcoins in the coinbase transaction outputs without showing the whole block itself and all input transactions. +# It is not possible to prove the violation of any block specific constraints, such as size and sigop limits, without showing the whole block (and all input transactions in the case of sigop limit) +# It is not possible to prove the spending of a non-existing input without showing all transaction IDs in the blockchain way back to the genesis block. + +It is possible to prove the first 2 types of fraud if a block is committed to a Merkle-sum-tree of the fee, size, and sigop count of each transaction. It is also possible to prove the last type of fraud if a block is committed to a Merkle tree with the originating block height and transaction index of all inputs. These commitments could be included in the extensible witness commitment through a soft fork and will be transparent to nodes that do not understand such new rules. + +=== New script system === +Since a version byte is pushed before a witness program, and programs with unknown versions are always considered as anyone-can-spend script, it is possible to introduce any new script system with a soft fork. The witness as a structure is not restricted by any existing script semantics and constraints, the 520-byte push limit in particular, and therefore allows arbitrarily large scripts and signatures. + +Examples of new script system include Schnorr signatures which reduce the size of multisig transactions dramatically, Lamport signature which is quantum computing resistance, and Merklized abstract syntax trees which allow very compact witness for conditional scripts with extreme complexity. + +The 32-byte limitation for witness program could be easily extended through a soft fork in case a stronger hash function is needed in the future. The version byte is also expandable through a softfork. + +=== Per-input lock-time and relative-lock-time === +Currently there is only one nLockTime field in a transaction and all inputs must share the same value. BIP68 enables per-input relative-lock-time using the nSequence field, however, with a limited lock-time period and resolution. + +With a soft fork, it is possible to introduce a separate witness structure to allow per-input lock-time and relative-lock-time, and a new script system that could sign and manipulate the new data (like BIP65 and BIP112). + +== Backward compatibility == +As a soft fork, older software will continue to operate without modification. Non-upgraded nodes, however, will not see nor validate the witness data and will consider all witness programs as anyone-can-spend scripts (except a few edge cases in version 0 witness programs which are provably unspendable with original script semantics). Wallets should always be wary of anyone-can-spend scripts and treat them with suspicion. Non-upgraded nodes are strongly encouraged to upgrade in order to take advantage of the new features. + +'''What a non-upgraded wallet can do''' + +* Receiving bitcoin from non-upgraded and upgraded wallets +* Sending bitcoin to non-upgraded wallets +* Sending bitcoin to upgraded wallets using a P2SH address (a less efficient way to use segregated witness) + +'''What a non-upgraded wallet cannot do''' + +* Validating segregated witness transaction. It assumes such a transaction is always valid +* Sending bitcoin to upgraded wallets using a native witness program (a more efficient way to use segregated witness) + +== Deployment == + +We reuse the double-threshold IsSuperMajority() switchover mechanism used in +BIP65 with the same thresholds, but for nVersion = 5. The new rules are +in effect for every block (at height H) with nVersion = 5 and at least +750 out of 1000 blocks preceding it (with heights H-1000..H-1) also +have nVersion >= 5. Furthermore, when 950 out of the 1000 blocks +preceding a block do have nVersion >= 5, nVersion < 5 blocks become +invalid, and all further blocks enforce the new rules. + +(It should be noted that BIP9 involves permanently setting a high-order bit to +1 which results in nVersion >= all prior IsSuperMajority() soft-forks and thus +no bits in nVersion are permanently lost.) + + +=== SPV Clients === + +While SPV clients are unable to fully validate blocks, +they are able to validate block headers and, thus, can check block version and proof-of-work. +SPV clients should reject nVersion < 5 blocks if 950 out of 1000 preceding blocks have +nVersion >= 5 to prevent false confirmations from the remaining 5% of +non-upgraded miners when the 95% threshold has been reached. + +== Credits == +Special thanks to Gregory Maxwell for originating many of the ideas in this BIP and Luke-Jr for figuring out how to deploy this as a soft fork. + +== Reference Implementation == +https://github.com/sipa/bitcoin/commits/segwit + +== Copyright == +This document is placed in the public domain. diff --git a/bip-0142.mediawiki b/bip-0142.mediawiki new file mode 100644 index 0000000..7efeca7 --- /dev/null +++ b/bip-0142.mediawiki @@ -0,0 +1,157 @@ +<pre> + BIP: 142 + Title: Address Formats for Witness Program + Author: Johnson Lau <jl2012@xbt.hk> + Status: Draft + Type: Standards Track + Created: 2015-12-24 +</pre> + +== Abstract == + +This BIP describes 2 new types of Bitcoin address to support native Segregated Witness (segwit) transactions. The first type resembles the original P2PKH base-58 address. The second type is a z-base-32 representation of a witness program with Damm algorithm checksum, which supports arbitrarily complex transactions, and is forward compatible to new version witness programs in the future. + +== Motivation == + +To define standard payment addresses for native segwit transactions to promote early adoption of the more efficient transaction method. + +== Specification == + +=== P2PKH segwit address === + +The first new Bitcoin address format defined is specific to pay-to-public-key-hash segwit transaction. The scriptPubKey is a single push of version-0 witness program in this form, + <0x0076A914{20-byte-hash-value}88AC> +The new address is encoded exactly in the same way as the original pay-to-public-key-hash address: + base58-encode: [1-byte version][20-byte-hash-value][4-byte checksum] +Version byte is 0x19 for a main-network address, 0x41 for a testnet address. The following 20-byte is the public key hash. And the 4-byte checksum is the first four bytes of the double SHA256 hash of the version and public key hash. + +All addresses generated with this scheme will a constant length of 34 characters, with a "B" prefix for main-network and "T" prefix for testnet. + +=== General segwit address === + +The second new bitcoin address format defined is applicable to witness program of version 0 to 15 with a length of 2 to 32 bytes. + +The z-base-32 character set is used: +{|class="wikitable" style="width:40ex; text-align: center; margin: 0 auto 0 auto;" +!width="12%"|Value +!width="12%"|Symbol +!width="12%"|Value +!width="12%"|Symbol +!width="12%"|Value +!width="12%"|Symbol +!width="12%"|Value +!width="12%"|Symbol +|- +| 0 || y || 8 || e || 16 || o || 24 || a +|- +| 1 || b || 9 || j || 17 || t || 25 || 2 +|- +| 2 || n || 10 || k || 18 || 1 || 26 || 4 +|- +| 3 || d || 11 || m || 19 || u || 27 || 5 +|- +| 4 || r || 12 || c || 20 || w || 28 || h +|- +| 5 || f || 13 || p || 21 || i || 29 || 7 +|- +| 6 || g || 14 || q || 22 || s || 30 || 6 +|- +| 7 || 8 || 15 || x || 23 || z || 31 || 9 +|} + +It is case-insensitive and includes all alphanumeric characters excluding 0, 2, l, v. The order of alphabet is chosen so that less ambiguous alphabet characters will appear more frequently than others. + +An address is a 270-bit string in z-base-32 with the following components: + + 5 address version bits + 5 length bits + 4 witness program version bits + 256 witness program bits + +The address version bits is 00001<sub>b</sub> for the main-network and 11001<sub>b</sub> for the testnet. + +Value of the length bits is the length of the witness program in byte minus 1. + +Witness program version bits indicates version of the witness program (v0 to v15). + +The witness program is padded with leading 0<sub>b</sub> to 256 bits. + +The 270-bit string is transformed to z-base-32 with 54 digits. + +The 54-digit raw address is then divided into 9 equal segments. For each segment, a checksum is calculated with Damm algorithm and appended to the end of the segment. This makes the length increases to 63 digits. + +A second round of checksum is calculated by taking the digits in the same position of the 9 segments, and appended to the end of the address. This is the final address with 69 digits. + + +== Rationale == + +The segregated witness soft fork (BIP x) defines 2 ways of encoding "witness program", a data push of 2 to 32 bytes: + +* A native witness program output is a scriptPubKey with a push of version byte followed by a push of witness program, and nothing else; +* A witness program in P2SH is a P2SH redeemScript with a push of version byte followed by a push of witness program, while the scriptPubKey looks like a normal P2SH output. + +As the P2SH address has been defined in 2012, using witness program in P2SH allows most existing wallets to pay a segwit-compatible wallet without any upgrade. However, this method requires more block space and is less collision-resistance than a native witness program, and is only a short-term solution to make the transition smoother. Eventually, all users are expected to use the more efficient native witness program as the primary payment method. + +The drawbacks of Bitcoin addresses have been extensively discussed in BIP13. Since then, better payment methods have been proposed or deployed, for example: +*BIP47 Reusable Payment Codes for Hierarchical Deterministic Wallets +*BIP63 Stealth Addresses +*BIP70 Payment protocol + +However, none of these are as widely adopted as the suboptimal base-58 scriptPubKey template addresses, which is still a standard for the whole eco-system, from wallets, block explorers, merchants, exchanges, to end users. As P2PKH transactions are still dominating the blockchain, the author believes that the proposed P2PKH segwit addresses is the easiest way for wallets and services to adopt native witness program, which is particularly important in the context of scaling the capacity of the blockchain. + +The P2PKH segwit addresses only allow simple payment to a single public key. For arbitrarily complex segwit transactions, the general segwit address is used. The use of z-base-32 eliminates case-sensitiveness and simplifies transformation to and from hexadecimals. The Damm algorithm checksum allows detection of all single-digit errors and all adjacent transposition errors. With the excellent upgradability of witness program, this proposal is also forward compatible to new version witness programs that is not longer than 32 bytes. + +== Compatibility == + +This proposal is not backward compatible, but it fails gracefully -- if an older implementation is given one of these new Bitcoin addresses, it will report the address as invalid and will refuse to create a transaction. + +This proposal is forward compatible to any new witness program format with version 2 to 15 and length of 2 to 32 bytes. + +== Example == + +=== P2PKH segwit address === + +The following public key, + 0450863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B23522CD470243453A299FA9E77237716103ABC11A1DF38855ED6F2EE187E9C582BA6 +when encoded as a P2PKH template, would become: + DUP HASH160 <010966776006953D5567439E5E39F86A0D273BEE> EQUALVERIFY CHECKSIG +And the corresponding version 1 Bitcoin address is + 16UwLL9Risc3QfPqBUvKofHmBQ7wMtjvM +When the same script is encoded as a version 0 witness program, the scriptPubKey becomes: + OP_0 <0x76A914010966776006953D5567439E5E39F86A0D273BEE88AC> +Using 0x19 as the address version, the equivalent witness program address is: + B4YZZ3nMBETWVF9ZSfotSwTxVnqhdkTi7r + +=== General segwit address === + +With the same 25 bytes version 0 witness program in the last example: + OP_0 <0x76A914010966776006953D5567439E5E39F86A0D273BEE88AC> +The address version bits is 00001<sub>b</sub> + 00001<sub>b</sub> +The lengths bits is 11000<sub>b</sub> (24 = 25 - 1) + 00001-11000<sub>b</sub> +The witness program version bits is 0000 + 00001-11000-0000<sub>b</sub> +Appended by the zero-padded witness program + 00001-11000-0000-0-00000-00000-00000-00000-00000-00000-00000-00000-00000-00000-00000-00000-11101...01100 +The 270-bit string is transformed to z-base-32 with 54 digits and split into 9 equal segments: + bayyyy -yyyyyy -yyq4wt -eyejc3 -5sybwi -8iksqo -h6mah9 -o4oprh -767nfc +Calculate the Damm checksum for each segment: + For example: Damm(bayyyy) = 7 + bayyyy7-yyyyyyy-yyq4wte-eyejc3q-5sybwic-8iksqoo-h6mah9w-o4oprhm-767nfc4 +Calculate the Damm checksum for digits in the same position of different segments: + For example: Damm(byye58ho7) = j + bayyyy7-yyyyyyy-yyq4wte-eyejc3q-5sybwic-8iksqoo-h6mah9w-o4oprhm-767nfc4-jwk86o + +== Implementation == + +From arbitrary witness program to general segwit address: https://gist.github.com/jl2012/760b0f952715b8b6c608 + +== References == + +* [[bip-0013.mediawiki|BIP 13: Address Format for pay-to-script-hash]] +* [[bip-0016.mediawiki|BIP 16: Pay to Script Hash (aka "/P2SH/")]] +* [[bip-xxxx.mediawiki|BIP x: Segregated Witness]] https://github.com/bitcoin/bips/pull/265 + +== Copyright == +This work is placed in the public domain. diff --git a/bip-0143.mediawiki b/bip-0143.mediawiki new file mode 100644 index 0000000..276e2cb --- /dev/null +++ b/bip-0143.mediawiki @@ -0,0 +1,133 @@ +<pre> + BIP: 143 + Title: Transaction signature verification for version 0 and version 1 witness program + Author: Johnson Lau <jl2012@xbt.hk> + Pieter Wuille <pieter.wuille@gmail.com> + Status: Draft + Type: Standards Track + Created: 2016-01-03 +</pre> + +== Abstract == +This proposal defines a new transaction digest algorithm for signature verification in version 0 and version 1 witness program, in order to minimize redundant data hashing in verification, and to cover the input value by the signature. + +== Motivation == +There are 4 ECDSA signature verification codes in the original Bitcoin script system: CHECKSIG, CHECKSIGVERIFY, CHECKMULTISIG, CHECKMULTISIGVERIFY (“sigops”). According to the sighash type (ALL, NONE, SINGLE, ANYONECANPAY), a transaction digest is generated with a double SHA256 of a serialized subset of the transaction, and the signature is verified against this digest with a given public key. The detailed procedure is described in a Bitcoin Wiki article. <ref name=wiki>[https://en.bitcoin.it/wiki/OP_CHECKSIG]</ref> + +Unfortunately, there are at least 2 weaknesses in the original transaction digest algorithm: + +* For the verification of each signature, the amount of data hashing is proportional to the size of the transaction. Therefore, data hashing grows in O(n<sup>2</sup>) as the number of sigops in a transaction increases. While a 1 MB block would normally take 2 seconds to verify with an average computer in 2015, a 1MB transaction with 5569 sigops may take 25 seconds to verify. This could be fixed by optimizing the digest algorithm by introducing some reusable “midstate”, so the time complexity becomes O(n). <ref>[https://web.nvd.nist.gov/view/vuln/detail?vulnId=CVE-2013-2292 CVE-2013-2292]</ref><ref>[https://bitcointalk.org/?topic=140078 New Bitcoin vulnerability: A transaction that takes at least 3 minutes to verify]</ref><ref>[http://rusty.ozlabs.org/?p=522 The Megatransaction: Why Does It Take 25 Seconds?]</ref> +* The algorithm does not involve the amount of Bitcoin being spent by the input. This is usually not a problem for online network nodes as they could request for the specified transaction to acquire the output value. For an offline transaction signing device ("cold wallet"), however, the unknowing of input amount makes it impossible to calculate the exact amount being spent and the transaction fee. To cope with this problem a cold wallet must also acquire the full transaction being spent, which could be a big obstacle in the implementation of lightweight, air-gapped wallet. By including the input value of part of the transaction digest, a cold wallet may safely sign a transaction by learning the value from an untrusted source. In the case that a wrong value is provided and signed, the signature would be invalid and no funding might be lost. <ref>[https://bitcointalk.org/index.php?topic=181734.0 SIGHASH_WITHINPUTVALUE: Super-lightweight HW wallets and offline data]</ref> + +Deploying the aforementioned fixes in the original script system is not a simple task. That would be either a hardfork, or a softfork for new sigops without the ability to remove or insert stack items. However, the introduction of segregated witness softfork offers an opportunity to define a different set of script semantics without disrupting the original system, as the unupgraded nodes would always consider such a transaction output is spendable by arbitrary signature or no signature at all. <ref>[https://github.com/CodeShark/bips/blob/segwit/bip-codeshark-jl2012-segwit.mediawiki BIPx: Segregated Witness (Consensus layer)]</ref> + +== Specification == +A new transaction digest algorithm is defined, but only applicable to sigops in version 0 and version 1 witness program: + Double SHA256 of the serialization of: + 1. nVersion of the transaction + 2. hashPrevouts + 3. hashSequence + 4. transaction id and output index of the output spent by this input + 5. subscript of the input + 6. value of the output spent by this input + 7. nSequence of the input + 8. hashOutputs + 9. nLocktime of the transaction + 10. sighash type of the signature + +The items 1, 4, 5, 7, 9, 10 have the same meaning as the original algorithm. <ref name=wiki></ref> + +The item 6 is a 8-byte value of the amount of bitcoin spent in this input. + +hashPrevouts: +*If the ANYONECANPAY flag is not set, hashPrevouts is the double SHA256 of the serialization of all transaction ids and output indexes involved in this transaction; +*Otherwise, hashPrevouts is a uint256 of 0x0000......0000. + +hashSequence: +*If none of the ANYONECANPAY, SINGLE, NONE sighash type is set, hashSequence is the double SHA256 of the serialization of nSequence of all inputs; +*Otherwise, hashSequence is a uint256 of 0x0000......0000. + +hashOutputs: +*If the sighash type is neither SINGLE nor NONE, hashOutputs is the double SHA256 of the serialization of all output scriptPubKey with value; +*If sighash type is SINGLE and the input index is not greater than the number of outputs, hashOutputs is the double SHA256 of the output scriptPubKey with value of the same index as the input; +*Otherwise, hashOutputs is a uint256 of 0x0000......0000. + +The hashPrevouts, hashSequence, and hashOutputs calculated in an earlier verification may be reused in other inputs of the same transaction, so that the time complexity of the whole hashing process reduces from O(n<sup>2</sup>) to O(n). + +Refer to the reference implementation, reproduced below, for the precise algorithm: + +<source lang="cpp"> + uint256 hashPrevouts; + uint256 hashSequence; + uint256 hashOutputs; + + if (!(nHashType & SIGHASH_ANYONECANPAY)) { + CHashWriter ss(SER_GETHASH, 0); + for (unsigned int n = 0; n < txTo.vin.size(); n++) { + ss << txTo.vin[n].prevout; + } + hashPrevouts = ss.GetHash(); + } + + if (!(nHashType & SIGHASH_ANYONECANPAY) && (nHashType & 0x1f) != SIGHASH_SINGLE && (nHashType & 0x1f) != SIGHASH_NONE) { + CHashWriter ss(SER_GETHASH, 0); + for (unsigned int n = 0; n < txTo.vin.size(); n++) { + ss << txTo.vin[n].nSequence; + } + hashSequence = ss.GetHash(); + } + + if ((nHashType & 0x1f) != SIGHASH_SINGLE && (nHashType & 0x1f) != SIGHASH_NONE) { + CHashWriter ss(SER_GETHASH, 0); + for (unsigned int n = 0; n < txTo.vout.size(); n++) { + ss << txTo.vout[n]; + } + hashOutputs = ss.GetHash(); + } else if ((nHashType & 0x1f) == SIGHASH_SINGLE && nIn < txTo.vout.size()) { + CHashWriter ss(SER_GETHASH, 0); + ss << txTo.vout[nIn]; + hashOutputs = ss.GetHash(); + } + + CHashWriter ss(SER_GETHASH, 0); + // Version + ss << txTo.nVersion; + // Input prevouts/nSequence (none/all, depending on flags) + ss << hashPrevouts; + ss << hashSequence; + // The input being signed (replacing the scriptSig with scriptCode + amount) + // The prevout may already be contained in hashPrevout, and the nSequence + // may already be contain in hashSequence. + ss << txTo.vin[nIn].prevout; + ss << static_cast<const CScriptBase&>(scriptCode); + ss << amount; + ss << txTo.vin[nIn].nSequence; + // Outputs (none/one/all, depending on flags) + ss << hashOutputs; + // Locktime + ss << txTo.nLockTime; + // Sighash type + ss << nHashType; + + return ss.GetHash(); +</source> + +== Deployment == + +This proposal is deployed with Segregated Witness softfork (BIP x) + +== Backward compatibility == + +As a soft fork, older software will continue to operate without modification. Non-upgraded nodes, however, will not see nor validate the witness data and will consider all witness programs, inculding the redefined sigops, as anyone-can-spend scripts. + +== Reference Implementation == + +https://github.com/sipa/bitcoin/commits/segwit + +== References == + +<references> + +== Copyright == + +This document is placed in the public domain. diff --git a/bip-0144.mediawiki b/bip-0144.mediawiki new file mode 100644 index 0000000..ed8cf2b --- /dev/null +++ b/bip-0144.mediawiki @@ -0,0 +1,122 @@ +<pre> + BIP: 144 + Title: Segregated Witness (Peer Services) + Author: Eric Lombrozo <elombrozo@gmail.com> + Pieter Wuille <pieter.wuille@gmail.com> + Status: Draft + Type: Standards Track + Created: 2015-12 +</pre> + +==Abstract== +This BIP defines new messages and serialization formats for propagation of transactions and blocks committing to segregated witness structures. + +==Motivation== +In addition to defining witness structures and requiring commitments in future blocks (BIPxxxx - Consensus segwit BIP), new mechanisms must be defined to allow peers to advertise support for segregated witness and to relay the witness structures and request them from other peers without breaking compatibility with older nodes. + +==Specification== + +=== Serialization === +A new serialization format for tx messages is added to the peer-to-peer protocol. + +The serialization has the following structure: + +{| class="wikitable" style="width: auto; text-align: center; font-size: smaller; table-layout: fixed;" +!Field Size +!Name +!Type +!Description +|- +| 4 +| version +| int32_t +| Transaction data format version +|- +| 1 +| marker +| char +| Must be zero +|- +| 1 +| flag +| char +| Must be nonzero +|- +| 1+ +| txin_count +| var_int +| Number of transaction inputs +|- +| 41+ +| txins +| txin[] +| A list of one or more transaction inputs +|- +| 1+ +| txout_count +| var_int +| Number of transaction outputs +|- +| 9+ +| txouts +| txouts[] +| A list of one or more transaction outputs +|- +| 1+ +| witness +| witness +| The witness structure as a serialized byte array +|- +| 4 +| lock_time +| uint32_t +| The block number or timestamp until which the transaction is locked +|} + +Parsers supporting this BIP will be able to distinguish between the old serialization format (without the witness) and this one. The marker byte is set to zero so that this structure will never parse as a valid transaction in a parser that does not support this BIP. If parsing were to succeeded, such a transaction would contain no inputs and a single output. + +If the witness is empty, the old serialization format should be used. + +Witness objects can be extended to contain other kinds of witness data not yet specified. This BIP is agnostic to the witness data structure, defined in BIPxxxx (Consensus Segwit BIP), and treats it as an arbitrary byte array. + +* '''Rationale for not having an independent message type with its own serialization''': this would require separate "tx" and "block" messages, and all RPC calls operating on raw transactions would need to be duplicated, or need inefficinent or nondeterministic guesswork to know which type is to be used. + +* '''Rationale for not using just a single 0x00 byte as marker''': that would lead to empty transactions (no inputs, no outputs, which are used in some tests) to be interpreted as new serialized data. + +* '''Rationale for the 0x01 flag byte in between''': this will allow us to easily add more extra non-committed data to transactions (like txouts being spent, ...). It can be interpreted as a bitvector. + +=== Handshake === +A new message 'havewitness' is sent after receiving 'verack' to +indicate that a node can provide witness if requested (similar to +'sendheaders') (Note: it might be better to signal this with a services bit in the version message) + +=== Hashes === +Transaction hashes used in the transaction merkle tree and txin outpoints are always computed using the old non-witness +serialization. + +Support for a new hash including the witness data is added that is +computed from the new witness serialization. (Note that transactions +with an empty witness always use the old serialization, +and therefore, they have witness hash equal to normal hash.) + +<img src=bip-0144/witnesstx.png></img> + +=== Relay === +New inv types MSG_WITNESS_TX and MSG_WITNESS_BLOCK are added, only +for use in getdata. Inventory messages themselves still use just MSG_TX and MSG_BLOCK, +similar to MSG_FILTERED_BLOCK. + +* '''Rationale for not advertizing witnessness in invs''': we don't always use invs anymore (with 'sendheaders' BIP 130), plus it's not useful: implicitly, every transaction and block have a witness, old ones just have empty ones. + +MSG_WITNESS_TX getdata requests should use the non-witness serialized hash. The peer shall respond with a tx message, and if the witness structure is nonempty, the witness serialization shall be used. + +MSG_WITNESS_BLOCK requests will return a block message with transactions that have a witness using witness serialization. + +== Credits == +Special thanks to Gregory Maxwell for originating many of the ideas in this BIP and Luke-Jr for figuring out how to deploy this as a soft fork. + +== Reference Implementation == +https://github.com/sipa/bitcoin/commits/segwit + +== Copyright == +This document is placed in the public domain. diff --git a/bip-0144/witnesstx.png b/bip-0144/witnesstx.png Binary files differnew file mode 100644 index 0000000..5fd8afc --- /dev/null +++ b/bip-0144/witnesstx.png |
