diff options
| -rw-r--r-- | README.mediawiki | 20 | ||||
| -rw-r--r-- | bip-0002.mediawiki | 2 | ||||
| -rw-r--r-- | bip-0047.mediawiki | 87 | ||||
| -rw-r--r-- | bip-0068.mediawiki | 12 | ||||
| -rw-r--r-- | bip-0070/extensions.mediawiki | 2 | ||||
| -rw-r--r-- | bip-0075.mediawiki | 12 | ||||
| -rw-r--r-- | bip-0112.mediawiki | 9 | ||||
| -rw-r--r-- | bip-0113.mediawiki | 12 | ||||
| -rw-r--r-- | bip-0114.mediawiki | 230 | ||||
| -rw-r--r-- | bip-0141.mediawiki | 95 | ||||
| -rw-r--r-- | bip-0143.mediawiki | 34 | ||||
| -rw-r--r-- | bip-0144.mediawiki | 7 | ||||
| -rw-r--r-- | bip-0144/witnesstx.png | bin | 18923 -> 21335 bytes |
13 files changed, 433 insertions, 89 deletions
diff --git a/README.mediawiki b/README.mediawiki index 970cf93..974870e 100644 --- a/README.mediawiki +++ b/README.mediawiki @@ -23,7 +23,7 @@ Those proposing changes should consider that ultimately consent may rest with th | BIP Status and Comments | Luke Dashjr | Process -| Draft +| Deferred |- | [[bip-0009.mediawiki|9]] | Version bits with timeout and delay @@ -314,6 +314,12 @@ Those proposing changes should consider that ultimately consent may rest with th | Standard | Draft |- +| [[bip-0075.mediawiki|75]] +| Out of Band Address Exchange using Payment Protocol Encryption +| Justin Newton, Matt David, Aaron Voisine, James MacWhyte +| Standard +| Draft +|- | [[bip-0080.mediawiki|80]] | Hierarchy for Non-Colored Voting Pool Deterministic Multisig Wallets | Justus Ranvier, Jimmy Song @@ -332,12 +338,6 @@ Those proposing changes should consider that ultimately consent may rest with th | Standard | Draft |- -| [[bip-0075.mediawiki|75]] -| Out of Band Address Exchange using Payment Protocol Encryption -| Justin Newton, Matt David, Aaron Voisine and James MacWhyte -| Standard -| Draft -|- | [[bip-0099.mediawiki|99]] | Motivation and deployment of consensus rule changes ([soft/hard]forks) | Jorge Timón @@ -404,6 +404,12 @@ Those proposing changes should consider that ultimately consent may rest with th | Standard | Draft |- +| [[bip-0114.mediawiki|114]] +| Merkelized Abstract Syntax Tree +| Johnson Lau +| Standard +| Draft +|- | [[bip-0120.mediawiki|120]] | Proof of Payment | Kalle Rosenbaum diff --git a/bip-0002.mediawiki b/bip-0002.mediawiki index a667026..9d59405 100644 --- a/bip-0002.mediawiki +++ b/bip-0002.mediawiki @@ -2,7 +2,7 @@ BIP: 2 Title: BIP Status and Comments Author: Luke Dashjr <luke+bip@dashjr.org> - Status: Draft + Status: Deferred Type: Process Created: 2016-02-03 </pre> diff --git a/bip-0047.mediawiki b/bip-0047.mediawiki index bdac681..b1145b3 100644 --- a/bip-0047.mediawiki +++ b/bip-0047.mediawiki @@ -1,7 +1,7 @@ RECENT CHANGES: +* (19 Apr 2016) Define version 2 payment codes +* (17 Apr 2016) Clarify usage of outpoints in notification transactions * (18 Dec 2015) Update explanations to resolve FAQs -* (12 Oct 2015) Revise blinding method for notification transactions -* (21 Sep 2015) Correct base58check version byte <pre> BIP: 47 @@ -84,7 +84,27 @@ 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)== +==Versions== + +Payment codes contain a version byte which identifies a specific set of behavior. + +Unless otherwise specified, payment codes of different versions are interoperable. If Alice uses a version x payment code, and Bob uses a version y payment code, they can still send and receive transactions between each other. + +Currently specified versions: + +* Version 1 +** Address type: P2PKH +** Notification type: address +* Version 2 +** Address type: P2PKH +** Notification type: bloom-multisig + +===Recommended Versions=== + +* Wallets which have bloom filtering capabilities SHOULD create version 2 payment codes instead of version 1 payment codes. +* Version 1 payment codes are only recommended for wallets which lack access to bloom filtering capability. + +==Version 1== ===Representation=== @@ -119,20 +139,25 @@ It is assumed that Alice can easily obtain Bob's payment code via a suitable met * 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 +* Designated input: the first input in the notification transaction which exposes an secp256k1 pubkey in either its signature script, or in the redeem script or pubkey script of the output being spent +* Designated pubkey: the first secp256k1 pubkey pushed to the stack during script execution for the designated input +* Outpoint: the specific output of a previous transaction which is being spent. See the Reference section for the binary serialization ====Notification Transaction==== Prior to the first time Alice initiates a transaction to Bob, Alice MUST inform Bob of her payment code via the following procedure: +Note: this procedure is used if Bob uses a version 1 payment code (regardless of the the version of Alice's payment code). If Bob's payment code is not version 1, see the appropriate section in this specification. + # Alice constructs a transaction which sends a small quantity of bitcoins to Bob's notification address (notification transaction) ## The inputs selected for this transaction MUST NOT be easily associated with Alice's notification address # Alice derives a unique shared secret using ECDH: -## Alice selects the private key corresponding to the first exposed public key, of the first pubkey-exposing input, of the transaction: <pre>a</pre> +## Alice selects the private key corresponding to the designated pubkey: <pre>a</pre> ## Alice selects the public key associated with Bob's notification address: <pre>B, where B = bG</pre> ## Alice calculates a secret point: <pre>S = aB</pre> ## Alice calculates a 64 byte blinding factor: <pre>s = HMAC-SHA512(x, o)</pre> ### "x" is the x value of the secret point -### "o" is the outpoint being spent by the first pubkey-exposing input of the transaction. +### "o" is the outpoint being spent by the designated input # Alice serializes her payment code in binary form. # Alice renders her payment code (P) unreadable to anyone except Bob: ## Replace the x value with x': <pre>x' = x XOR (first 32 bytes of s)</pre> @@ -143,12 +168,12 @@ Prior to the first time Alice initiates a transaction to Bob, Alice MUST inform # Bob watches for any transactions which create an output at his notification address. # When a transaction is received, the client examines it to determine if it contains a standard OP_RETURN output with an 80 byte payload (notification transactions). # If the first byte of the payload in a notification transaction is 0x01: -## Bob selects the first exposed public key, of the first pubkey-exposing input, of the transaction: <pre>A, where A = aG</pre> +## Bob selects the designated pubkey: <pre>A, where A = aG</pre> ## Bob selects the private key associated with his notification address: <pre>b</pre> ## Bob calculates a secret point: <pre>S = bA</pre> ## Bob calculates the binding factor: <pre>s = HMAC-SHA512(x, o)</pre> ### "x" is the x value of the secret point -### "o" is the outpoint being spent by the first pubkey-exposing input of the transaction. +### "o" is the outpoint being spent by the designated input. ## Bob interprets the 80 byte payload as a payment code, except: ### Replace the x value with x': <pre>x' = x XOR (first 32 bytes of s)</pre> ### Replace the chain code with c': <pre>c' = c XOR (last 32 bytes of s)</pre> @@ -177,6 +202,17 @@ Alice SHOULD use an input script in one of the following standard forms to expos 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. +=====Post-Notification Privacy Considerations===== + +Incautious handling of change outputs from notification transactions may cause unintended loss of privacy. + +The recipient of a transaction which spends a change output from a prior notification transaction will learn about the potential connection between the sender and the recipient of the notification transaction. + +The following actions are recommended to reduce this risk: + +* Wallets which support mixing SHOULD mix change outputs from notification transactions prior to spending them +* Wallets which do not support mixing MAY simulate mixing by creating a transaction which spends the change output to the next external BIP44 address + ====Sending==== # Each time Alice wants to initiate a transaction to Bob, Alice derives a unique P2PKH address for the transaction using ECDH follows: @@ -291,6 +327,41 @@ The sender transmits their payment code in base58 form to the calculated Bitmess In order to use Bitmessage notification, the recipient must have a Bitmessage client which listens at the address which the senders will derive and is capable of relaying received payment codes to the Bitcoin wallet. +==Version 2== + +Version 2 payment codes behave identifically to version 1 payment codes, except as modified below. + +===Representation=== + +====Binary Serialization==== + +* Byte 0: version. required value: 0x02 + +===Protocol=== + +====Definitions==== + +* Notification change output: the change output from a notification transaction which which resides in the sender's wallet, but can be automatically located by the intended recipient +* Payment code identifier: a 33 byte representation of a payment code constructed by prepending 0x02 to the SHA256 hash of the binary serialization of the payment code + +====Notification Transaction==== + +Note: this procedure is used if Bob uses a version 2 payment code (regardless of the the version of Alice's payment code). If Bob's payment code is not version 2, see the appropriate section in this specification. + +# Construct a notification transaction as per the version 1 instructions, except do not create the output to Bob's notification address +# Create a notification change address as follows: +## Obtain the pubkey corresponding to the next change address +## Construct a multisig output in the form: +<pre>OP_1 <Bob's payment code identifier> <change address pubkey> OP_2 OP_CHECKMULTISIG</pre> + +The relative ordering of the payment code identifier and change address pubkey in the above script MAY be randomized + +Bob detects notification transactions by adding his payment code identifier to his bloom filter. + +# When the filter returns a notification transaction, the sender's payment code is unblinded using the same procedure as for version 1 notification transactions. + +Alice's wallet should spend the notification change output at the next appropriate opportunity. + ==Test Vectors== * [[https://gist.github.com/SamouraiDev/6aad669604c5930864bd|BIP47 Reusable Payment Codes Test Vectors]] @@ -300,7 +371,7 @@ In order to use Bitmessage notification, the recipient must have a Bitmessage cl * [[bip-0032.mediawiki|BIP32 - Hierarchical Deterministic Wallets]] * [[bip-0043.mediawiki|BIP43 - Purpose Field for Deterministic Wallets]] * [[bip-0044.mediawiki|BIP44 - Multi-Account Hierarchy for Deterministic Wallets]] -* [[https://bitcoin.org/en/glossary/outpoint|Outpoint]] +* [[https://bitcoin.org/en/developer-reference#outpoint|Outpoint]] * [[https://github.com/petertodd/dust-b-gone|dust-b-gone]] * [[https://en.bitcoin.it/wiki/Base58Check_encoding|Base58Check encoding]] * [[https://bitmessage.org/bitmessage.pdf|Bitmessage]] diff --git a/bip-0068.mediawiki b/bip-0068.mediawiki index 8c566b0..0082db3 100644 --- a/bip-0068.mediawiki +++ b/bip-0068.mediawiki @@ -43,7 +43,7 @@ This specification only interprets 16 bits of the sequence number as relative lo 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 mining date of the output is equal 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. @@ -218,9 +218,13 @@ This BIP was edited by BtcDrak, Nicolas Dorier and kinoshitajona. ==Deployment== -This BIP is to be deployed by either version-bits BIP9 or by isSuperMajority(). Exact details TDB. +This BIP is to be deployed by "versionbits" BIP9 using bit 0. -It is recommended to deploy BIP112 and BIP113 at the same time. +For Bitcoin '''mainnet''', the BIP9 '''starttime''' will be midnight 1st May 2016 UTC (Epoch timestamp 1462060800) and BIP9 '''timeout''' will be midnight 1st May 2017 UTC (Epoch timestamp 1493596800). + +For Bitcoin '''testnet''', the BIP9 '''starttime''' will be midnight 1st March 2016 UTC (Epoch timestamp 1456790400) and BIP9 '''timeout''' will be midnight 1st May 2017 UTC (Epoch timestamp 1493596800). + +This BIP must be deployed simultaneously with BIP112 and BIP113 using the same deployment mechanism. ==Compatibility== @@ -246,6 +250,8 @@ The most efficient way to calculate sequence number from relative lock-time is w Bitcoin mailing list discussion: https://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg07864.html +BIP9: https://github.com/bitcoin/bips/blob/master/bip-0009.mediawiki + BIP112: https://github.com/bitcoin/bips/blob/master/bip-0112.mediawiki BIP113: https://github.com/bitcoin/bips/blob/master/bip-0113.mediawiki diff --git a/bip-0070/extensions.mediawiki b/bip-0070/extensions.mediawiki index b572b1d..51400d8 100644 --- a/bip-0070/extensions.mediawiki +++ b/bip-0070/extensions.mediawiki @@ -6,4 +6,4 @@ Add your extension below using tags starting at 1000 and submit a pull-req. | Field Number || Extension Name || Field Name || Description |- | 1000 || [[https://example.com|(unassigned)]] || (unassigned) || (unassigned) -|}
\ No newline at end of file +|} diff --git a/bip-0075.mediawiki b/bip-0075.mediawiki index f9d28d0..b62c753 100644 --- a/bip-0075.mediawiki +++ b/bip-0075.mediawiki @@ -34,15 +34,15 @@ The motivation for defining this extension to the [[bip-0070.mediawiki|BIP70]] P The motivation for this extension to [[bip-0070.mediawiki|BIP70]] is threefold: -# Ensure that the payment details can only be seen by the participants in the transaction, and not by any third party. +# Ensure that the payment details can only be seen by the participants in the transaction, and not by any third party. # Enhance the Payment Protocol to allow for store and forward servers in order to allow, for example, mobile wallets to sign and serve Payment Requests. # Allow a sender of funds the option of sharing their identity with the receiver. This information could then be used to: -#* Make Bitcoin logs more human readable -#* Give the user the ability to decide who to release payment details to -#* Allow an entity such as a political campaign to ensure donors match regulatory and legal requirements +#* Make Bitcoin logs more human readable +#* Give the user the ability to decide who to release payment details to +#* Allow an entity such as a political campaign to ensure donors match regulatory and legal requirements #* Allow for an open standards based way for regulated financial entities to meet regulatory requirements #* Automate the active exchange of payment addresses, so static addresses and BIP32 X-Pubs can be avoided to maintain privacy and convenience @@ -346,11 +346,11 @@ Clients SHOULD keep in mind Receivers can broadcast a transaction without return * All ECC signatures included in any message defined in this BIP MUST use the SHA-256 hashing algorithm and MUST be DER [ITU.X690.1994] encoded. ==Implementation== -A reference implementation for a Store & Forward server supporting this proposal can be found here: +A reference implementation for a Store & Forward server supporting this proposal can be found here: [https://github.com/netkicorp/addressimo Addressimo] -A reference client implementation can be found in the InvoiceRequest functional testing for Addressimo here: +A reference client implementation can be found in the InvoiceRequest functional testing for Addressimo here: [https://github.com/netkicorp/addressimo/blob/master/functest/functest_bip75.py BIP75 Client Reference Implementation] diff --git a/bip-0112.mediawiki b/bip-0112.mediawiki index 336f9fc..9d8228c 100644 --- a/bip-0112.mediawiki +++ b/bip-0112.mediawiki @@ -342,10 +342,13 @@ https://github.com/bitcoin/bitcoin/pull/7524 ==Deployment== -This BIP is to be deployed by either version-bits BIP9 or by IsSuperMajority(). Exact details TDB. +This BIP is to be deployed by "versionbits" BIP9 using bit 0. -It is recommended to deploy BIP68 and BIP113 at the same time as this BIP. +For Bitcoin '''mainnet''', the BIP9 '''starttime''' will be midnight 1st May 2016 UTC (Epoch timestamp 1462060800) and BIP9 '''timeout''' will be midnight 1st May 2017 UTC (Epoch timestamp 1493596800). +For Bitcoin '''testnet''', the BIP9 '''starttime''' will be midnight 1st March 2016 UTC (Epoch timestamp 1456790400) and BIP9 '''timeout''' will be midnight 1st May 2017 UTC (Epoch timestamp 1493596800). + +This BIP must be deployed simultaneously with BIP68 and BIP113 using the same deployment mechanism. ==Credits== @@ -363,6 +366,8 @@ Thanks to Eric Lombrozo and Anthony Towns for contributing example use cases. ==References== +[https://github.com/bitcoin/bips/blob/master/bip-0009.mediawiki BIP 9] Versionbits + [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 diff --git a/bip-0113.mediawiki b/bip-0113.mediawiki index d21054b..7497f50 100644 --- a/bip-0113.mediawiki +++ b/bip-0113.mediawiki @@ -72,10 +72,13 @@ https://github.com/bitcoin/bitcoin/pull/6566 ==Deployment== -This BIP is to be deployed by either version-bits BIP9 or by isSuperMajority(). -Exact details TBD. +This BIP is to be deployed by "versionbits" BIP9 using bit 0. -It is recommended to deploy BIP68 and BIP112 at the same time as this BIP. +For Bitcoin '''mainnet''', the BIP9 '''starttime''' will be midnight 1st May 2016 UTC (Epoch timestamp 1462060800) and BIP9 '''timeout''' will be midnight 1st May 2017 UTC (Epoch timestamp 1493596800). + +For Bitcoin '''testnet''', the BIP9 '''starttime''' will be midnight 1st March 2016 UTC (Epoch timestamp 1456790400) and BIP9 '''timeout''' will be midnight 1st May 2017 UTC (Epoch timestamp 1493596800). + +This BIP must be deployed simultaneously with BIP68 and BIP112 using the same deployment mechanism. ==Acknowledgements== @@ -98,6 +101,9 @@ concerns with existing protocols. ==References== + +[https://github.com/bitcoin/bips/blob/master/bip-0009.mediawiki BIP9: Versionbits] + [https://github.com/bitcoin/bips/blob/master/bip-0065.mediawiki BIP65: OP_CHECKLOCKTIMEVERIFY] [https://github.com/bitcoin/bips/blob/master/bip-0068.mediawiki BIP68: Consensus-enforced transaction replacement signaled via sequence numbers] diff --git a/bip-0114.mediawiki b/bip-0114.mediawiki new file mode 100644 index 0000000..2d16084 --- /dev/null +++ b/bip-0114.mediawiki @@ -0,0 +1,230 @@ +<pre> + BIP: 114 + Title: Merkelized Abstract Syntax Tree + Author: Johnson Lau <jl2012@xbt.hk> + Status: Draft + Type: Standards Track + Created: 2016-04-02 +</pre> + +==Abstract== +This BIP defines a new witness program type that uses a Merkle tree to encode mutually exclusive branches in a script. This enables complicated redemption conditions that are currently not possible, improves privacy by hiding unexecuted scripts, and allows inclusion of non-consensus enforced data with very low or no additional cost. + +==Motivation== +===Evolution of Bitcoin script system=== +Bitcoin uses a script system to specify the conditions for redemption of transaction outputs. In its original design, the conditions for redemption are directly recorded in the scriptPubKey by the sender of the funds. This model has several drawbacks, particularly for complicated scripts: +# It could be difficult for the receiver to specify the conditions; +# Large scripts take up more UTXO space; +# The sender will pay for the additional block space; +# To prevent DoS attack, scripts are limited to 10,000 bytes and 201 op codes; +# Any unexecuted branches and non-consensus enforced data in the script are visible to the public, consuming block space while damaging privacy. + +The [[bip-0016.mediawiki|BIP16]] (Pay-to-script-hash, "P2SH") fixes the first 3 problems by using a fixed-length 20-byte script hash in the scriptPubKey, and moving the responsibility for supplying the script to the redeemer. However, due to the data push size limit in script, a P2SH script may not be bigger than 520 bytes. Also, P2SH still requires the redeemer to publish all unexecuted branches of the script. + +The [[bip-0141.mediawiki|BIP141]] defines 2 new types of scripts that support segregated witness. The pay-to-witness-script-hash (P2WSH) is similar to P2SH is many ways. By supplying the script in witness, P2WSH restores the original 10,000 byte script limit. However, it still requires publishing of unexecuted branches. + +===Merkelized Abstract Syntax Tree=== +The idea of Merkelized Abstract Syntax Tree (MAST) is to use a Merkle tree to encode mutually exclusive branches in a script. When spending, the redeemer may provide only the branch they are executing, and hashes that connect the branch to the fixed size Merkel root. This reduces the size of redemption stack from O(n) to O(log n) (n as the number of mutually exclusive branches). This enables complicated redemption conditions that is currently not possible due to the script size and op code limit, improves privacy by hiding unexecuted branches, and allows inclusion of non-consensus enforced data with very low or no additional cost. + +==Specification== +In [[bip-0141.mediawiki|BIP141]], witness programs with a version byte of 1 or larger are considered to be anyone-can-spend scripts. The following new validation rules are applied if the witness program version byte is 1 and the program size is 32 bytes. The witness program is the <code>MAST Root</code>. + +To redeem an output of this kind, the witness must consist of an input stack to feed to the script, followed by a <code>Postion</code> value, a serialized Merkle path (<code>Path</code>), and a serialized script (<code>MAST Script</code>). + +The <code>Position</code>, <code>Path</code>, and <code>MAST Script</code> are popped off the initial witness stack. + +The double-SHA256 of the MAST Script (≤ TBD bytes) must be correctly connected to the <code>MAST Root</code> with the <code>ComputeMerkleRootFromBranch</code> function, with the specified <code>Path</code> and <code>Position</code>. + +<code>Path</code> is the serialized Merkle path for the <code>MAST Script</code>. Size of <code>Path</code> must be a multiple of 32 bytes, and not more than 1024 bytes (which allows 32 levels). Each 32 byte word is a double-SHA256 merkle node in the merkle branch connecting to the <code> MAST Root</code>. If the size of <code>Path</code> is zero, the double-SHA256 of the <code>MAST Script</code> must match the <code>MAST Root</code>. + +<code>Position</code> indicates the location of the <code>MAST Script</code> in the Merkle tree, with zero indicating the leftmost position. It is an unsigned little-endian integer with not more than 4 bytes. It must be encoded in the most parsimonious way possible, with no leading zero and not larger than the maximum number of items allowed by the depth of the tree (as implied by the size of <code>Path</code>). + +The <code>MAST Script</code> is then deserialized, and executed after normal script evaluation with the remaining witness stack (≤ TBD bytes for each stack item). The script must not fail, and result in exactly a single TRUE on the stack. + +Sigops in MAST program are counted to the block sigop limit in the same way as the version 0 witness program (see BIP141). + +If the version byte is 1, but the witness program is not 32 bytes, the script must fail. + +== Examples == +=== Calculation of MAST Root === +To calculate the MAST Root for 4 branches, the double-SHA256 of each branch is first calculated: + <1> EQUAL (0x5187), HASH256=3b647cb856a965fa6feffb4621eb2a4f4c2453693b2f64e021383ccbd80a1abb + <2> EQUAL (0x5287), HASH256=37772654bdce9b3d59e1169ea16ddbaa8a2ae8ee265db64863d0b76f02c882fa + <3> EQUAL (0x5387), HASH256=2e972642436151cd96e4b0868077b6362ffb5eb30b420a6f1c5e1c6fff02bc33 + <4> EQUAL (0x5487), HASH256=4c954fc1e635ce8417341465f85b59d700806f6e57bb96b2a25bec5ca3f9f154 + +Serialize the hashes of the first pair and calculate the hash. Same for the other pair: + HASH256(HASH256(5187)|HASH256(5287)) = 64fbdfc0a82ecc3b33434bfea63440e9a5275fa5e533200d2eaf18281e8b28b6 + HASH256(HASH256(5387)|HASH256(5487)) = aeadea837d5e640a1444208f7aca3be63bc8ab3c6b28a19878a00cc9c631ac31 + +Serialize the 2 hashes from the previous step and calculate the hash, which is the <code>MAST Root</code>: + MAST Root = 6746003b5c9d342b2c210d406802c351e7eb5943412dcfc4718be625a8a59c0e + +The scriptPubKey with native witness program is: + <1> <0x6746003b5c9d342b2c210d406802c351e7eb5943412dcfc4718be625a8a59c0e> + (0x51206746003b5c9d342b2c210d406802c351e7eb5943412dcfc4718be625a8a59c0e) + +To redeem with the <code><4> EQUAL</code> branch, the witness is + 04 (Stack for evaluation) + 03 (Position) + 2e972642436151cd96e4b0868077b6362ffb5eb30b420a6f1c5e1c6fff02bc3364fbdfc0a82ecc3b33434bfea63440e9a5275fa5e533200d2eaf18281e8b28b6 (Path) + 5487 (MAST Script) + +=== Imbalance MAST === +When constructing a MAST, if the user believes that some of the branches are more likely to be executed, they may put them closer to the <code>MAST Root</code>. It will save some witness space when the preferred branches are actually executed. + +=== Escrow with Timeout === +The following is the "Escrow with Timeout" example in [[bip-0112.mediawiki|BIP112]]: + IF + 2 <Alice's pubkey> <Bob's pubkey> <Escrow's pubkey> 3 CHECKMULTISIGVERIFY + ELSE + "30d" CHECKSEQUENCEVERIFY DROP + <Alice's pubkey> CHECKSIGVERIFY + ENDIF + +Using compressed public key, the size of this script is 150 bytes. + +With MAST, this script could be broken down into 2 mutually exclusive branches: + 2 <Alice's pubkey> <Bob's pubkey> <Escrow's pubkey> 3 CHECKMULTISIGVERIFY (105 bytes) + "30d" CHECKSEQUENCEVERIFY DROP <Alice's pubkey> CHECKSIGVERIFY (42 bytes) + +With 2 branches, the <code>Path</code> will be 32 bytes (as the hash of the unexecuted branch), and the <code>Position</code> will be 1 byte as either 0 or 1. Since only one branch will be published, it is more difficult for a blockchain analyst to determine the details of the escrow. + +=== Hashed Time-Lock Contract === +The following is the "Hashed TIme-Lock Contract" example in [[bip-0112.mediawiki|BIP112]]: + HASH160 DUP <R-HASH> EQUAL + IF + "24h" CHECKSEQUENCEVERIFY + 2DROP + <Alice key hash> + ELSE + <Commit-Revocation-Hash> EQUAL + NOTIF + "Timestamp" CHECKLOCKTIMEVERIFY DROP + ENDIF + <Bob key hash> + ENDIF + CHECKSIG + +To create a MAST Root, it is flattened to 3 mutually exclusive branches: + HASH160 <R-HASH> EQUALVERIFY "24h" CHECKSEQUENCEVERIFY DROP <Alice key hash> CHECKSIG + HASH160 <Commit-Revocation-Hash> EQUALVERIFY <Bob key hash> CHECKSIG + "Timestamp" CHECKLOCKTIMEVERIFY DROP <Bob key hash> CHECKSIG + +which significantly improves readability and reduces the witness size when it is redeemed. + +=== Large multi-signature constructs === +The current CHECKMULTISIG supports up to 20 public keys. Although it is possible to extend it beyond 20 keys by using multiple CHECKSIGs and IF/ELSE conditions, the construction could be very complicated and soon use up the 10,000 bytes and 201 op codes limit. + +With MAST, large and complex multi-signature constructs could be flattened to many simple CHECKMULTISIG conditions. For example, a 3-of-2000 multi-signature scheme could be expressed as 1,331,334,000 3-of-3 CHECKMULTISIGs, which forms a 31-level MAST. The scriptPubKey still maintains a fixed size of 34 bytes, and the redemption witness will be very compact, with less than 1,500 bytes. + +=== Commitment of non-consensus enforced data === +Currently, committing non-consensus enforced data in the scriptPubKey requires the use of OP_RETURN which occupies additional block space. With MAST, users may commit such data as a branch. Depends on the number of executable branches, inclusion of such a commitment may incur no extra witness space, or 32 bytes at most. + +An useful case would be specifying "message-signing keys", which are not valid for spending, but allow users to sign any message without touching the cold storage "funding key". + +== Backward compatibility == +As a soft fork, older software will continue to operate without modification. Non-upgraded nodes, however, will consider MAST programs as anyone-can-spend scripts. Wallets should always be wary of anyone-can-spend scripts and treat them with suspicion. + +== Deployment == +This BIP depends on [[bip-0141.mediawiki|BIP141]] and will be deployed by version-bits [[bip-0009.mediawiki|BIP9]] after BIP141 is enforced. Exact details TBD. + +== Credits == +The idea of MAST originates from Russell O’Connor, Pieter Wuille, and [https://bitcointalk.org/index.php?topic=255145.msg2757327#msg2757327 Peter Todd]. + +== Reference Implementation == +https://github.com/jl2012/bitcoin/tree/segwit_mast + +<source lang="cpp"> +//New rules apply if version byte is 1 and witness program size is 32 bytes +if (witversion == 1) { + if (program.size() == 32) { + + //Witness stack must have at least 3 items + if (witness.stack.size() < 3) + return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_MISMATCH); + + //Script is the last witness stack item + scriptPubKey = CScript(witness.stack.back().begin(), witness.stack.back().end()); + uint256 hashScriptPubKey; + CHash256().Write(&scriptPubKey[0], scriptPubKey.size()).Finalize(hashScriptPubKey.begin()); + + //Path is the second last witness stack item + std::vector<unsigned char> pathdata = witness.stack.at(witness.stack.size() - 2); + + // Size of Path must be a multiple of 32 bytes (0 byte is allowed) + if (pathdata.size() & 0x1F) + return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_MISMATCH); + + // Depth of the tree is size of Path divided by 32 + unsigned int depth = pathdata.size() >> 5; + + // Maximum allowed depth is 32 + if (depth > 32) + return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_MISMATCH); + std::vector<uint256> path; + path.resize(depth); + for (unsigned int i = 0; i < depth; i++) + memcpy(path[i].begin(), &pathdata[32 * i], 32); + + //Position is the third last witness stack item + std::vector<unsigned char> positiondata = witness.stack.at(witness.stack.size() - 3); + + //Position may have 4 bytes at most + if (positiondata.size() > 4) + return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_MISMATCH); + + uint32_t position = 0; + + //Position is an unsigned little-endian integer with no leading zero byte + if (positiondata.size() > 0) { + if (positiondata.back() == 0x00) + return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_MISMATCH); + for (size_t i = 0; i != positiondata.size(); ++i) + position |= static_cast<uint32_t>(positiondata[i]) << 8 * i; + } + + //Position must not be larger than the maximum number of items allowed by the depth of tree + if (depth < 32) { + if (position >= (1U << depth)) + return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_MISMATCH); + } + + //Calculate the Merkle Root and compare with the witness program + uint256 root = ComputeMerkleRootFromBranch(hashScriptPubKey, path, position); + if (memcmp(root.begin(), &program[0], 32)) + return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_MISMATCH); + + //Remaining stack items used for evaluation + stack = std::vector<std::vector<unsigned char> >(witness.stack.begin(), witness.stack.end() - 3); + } + + else { + //Invalid if version byte is 1 but witness program size is not 32 bytes + return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_WRONG_LENGTH); + } +} +</source> + +Copying from <code>src/consensus/merkle.cpp</code>: +<source lang="cpp"> +uint256 ComputeMerkleRootFromBranch(const uint256& leaf, const std::vector<uint256>& vMerkleBranch, uint32_t nIndex) { + uint256 hash = leaf; + for (std::vector<uint256>::const_iterator it = vMerkleBranch.begin(); it != vMerkleBranch.end(); ++it) { + if (nIndex & 1) { + hash = Hash(BEGIN(*it), END(*it), BEGIN(hash), END(hash)); + } else { + hash = Hash(BEGIN(hash), END(hash), BEGIN(*it), END(*it)); + } + nIndex >>= 1; + } + return hash; +} +</source> + + +== References == +*[[bip-0141.mediawiki|BIP141 Segregated Witness (Consensus layer)]] + +== Copyright == +This document is placed in the public domain. diff --git a/bip-0141.mediawiki b/bip-0141.mediawiki index a73cf35..07e6a7f 100644 --- a/bip-0141.mediawiki +++ b/bip-0141.mediawiki @@ -60,28 +60,30 @@ A non-witness program (defined hereinafter) txin MUST be associated with an empt A new block rule is added which requires a commitment to the <code>wtxid</code>. The <code>wtxid</code> of coinbase transaction is assumed to be <code>0x0000....0000</code>. -A witness root hash is calculated with all those <code>wtxid</code> as leaves, in a way similar to the hashMerkleRoot in the block header. +A <code>witness root hash</code> is calculated with all those <code>wtxid</code> as leaves, in a way similar to the <code>hashMerkleRoot</code> in the block header. -The commitment is recorded in a scriptPubKey of the coinbase transaction. It must be at least 38 bytes, with the first 6-byte of <code>0x6a24aa21a9ed</code>, that is: +The commitment is recorded in a <code>scriptPubKey</code> of the coinbase transaction. It must be at least 38 bytes, with the first 6-byte of <code>0x6a24aa21a9ed</code>, that is: 1-byte - OP_RETURN (0x6a) 1-byte - Push the following 36 bytes (0x24) 4-byte - Commitment header (0xaa21a9ed) - 32-byte - Commitment hash: Double-SHA256(witness root hash|witness nonce) + 32-byte - Commitment hash: Double-SHA256(witness root hash|witness reserved value) 39th byte onwards: Optional data with no consensus meaning -and the coinbase's input's witness must consist of a single 32-byte array for the witness nonce. +and the coinbase's input's witness must consist of a single 32-byte array for the <code>witness reserved value</code>. -If there are more than one scriptPubKey matching the pattern, the one with highest output index is assumed to be the commitment. +If there are more than one <code>scriptPubKey</code> matching the pattern, the one with highest output index is assumed to be the commitment. + +If all transactions in a block do not have witness data, the commitment is optional. === 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". +A <code>scriptPubKey</code> (or <code>redeemScript</code> 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". There are two cases in which witness validation logic are triggered. Each case determines the location of the witness version byte and program, as well as the form of the scriptSig: -# Triggered by a scriptPubKey that is exactly a push of a version byte, plus a push of a witness program. The scriptSig must be exactly empty. -# Triggered when a scriptPubKey is a P2SH script, and the BIP16 redeemScript pushed in the scriptSig is exactly a push of a version byte plus a push of a witness program. The scriptSig must be exactly a push of the BIP16 redeemScript. +# Triggered by a <code>scriptPubKey</code> that is exactly a push of a version byte, plus a push of a witness program. The scriptSig must be exactly empty or validation fails. +# Triggered when a <code>scriptPubKey</code> is a P2SH script, and the BIP16 <code>redeemScript</code> pushed in the <code>scriptSig</code> is exactly a push of a version byte plus a push of a witness program. The <code>scriptSig</code> must be exactly a push of the BIP16 <code>redeemScript</code> or validation fails. If the version byte is 0, and the witness program is 20 bytes: * It is interpreted as a pay-to-witness-public-key-hash (P2WPKH) program. @@ -91,9 +93,9 @@ If the version byte is 0, and the witness program is 20 bytes: If the version byte is 0, and the witness program is 32 bytes: * It is interpreted as a pay-to-witness-script-hash (P2WSH) program. -* The witness must consist of an input stack to feed to the script, followed by a serialized script ("witnessScript"). -* The witnessScript (≤ 10,000 bytes) is popped off the initial witness stack. SHA256 of the witnessScript must match the 32-byte witness program. -* The witnessScript is deserialized, and executed after normal script evaluation with the remaining witness stack (≤ 520 bytes for each stack item). +* The witness must consist of an input stack to feed to the script, followed by a serialized script (<code>witnessScript</code>). +* The <code>witnessScript</code> (≤ 10,000 bytes) is popped off the initial witness stack. SHA256 of the <code>witnessScript</code> must match the 32-byte witness program. +* The <code>witnessScript</code> is deserialized, and executed after normal script evaluation with the remaining witness stack (≤ 520 bytes for each stack item). * The script must not fail, and result in exactly a single TRUE on the stack. If the version byte is 0, but the witness program is neither 20 nor 32 bytes, the script must fail. @@ -106,9 +108,13 @@ If the version byte is 1 to 16, no further interpretation of the witness program Blocks are currently limited to 1,000,000 bytes (1MB) total size. We change this restriction as follows: -''Block cost'' is defined. The cost of each byte in the existing header and transactions is 4, while the cost of each byte in witness data is 1. +''Block cost'' is defined as ''Base size'' * 3 + ''Total size''. (rationale<ref>Rationale of using a single composite constraint, instead of two separate limits such as 1MB base data and 3MB witness data: Using two separate limits would make mining and fee estimation nearly impossible. Miners would need to solve a complex non-linear optimization problem to find the set of transactions that maximize fees given both constraints, and wallets would not be able to know what to pay as it depends on which of the two conditions is most constrained by the time miners try to produce blocks with their transactions in. Another problem with such an approach is freeloading. Once a set of transactions hit the base data 1MB constraint, up to 3MB extra data could be added to the witness by just minimally increasing the fee. The marginal cost for extra witness space effectively becomes zero in that case.</ref>) + +''Base size'' is the block size in bytes with the original transaction serialization without any witness-related data, as seen by a non-upgraded node. -The new rule is total ''block cost'' ≤ 4,000,000. +''Total size'' is the block size in bytes with transactions serialized as described in [[bip-0144.mediawiki|BIP144]], including base data and witness data. + +The new rule is ''block cost'' ≤ 4,000,000. ==== Sigops ==== @@ -126,8 +132,8 @@ The following example is a version 0 pay-to-witness-public-key-hash (P2WPKH) wit witness: <signature> <pubkey> scriptSig: (empty) - scriptPubKey: 0 <20-byte-hash> - (0x0014{20-byte-hash}) + scriptPubKey: 0 <20-byte-key-hash> + (0x0014{20-byte-key-hash}) The '0' in scriptPubKey indicates the following push is a version 0 witness program. The length of the witness program indicates that it is a P2WPKH type. The witness must consist of exactly 2 items. The HASH160 of the pubkey in witness must match the witness program. @@ -137,6 +143,24 @@ The signature is verified as Comparing with a traditional P2PKH output, the P2WPKH equivalent occupies 3 less bytes in the scriptPubKey, and moves the signature and public key from scriptSig to witness. +=== P2WPKH nested in BIP16 P2SH === + +The following example is the same P2WPKH witness program, but nested in a BIP16 P2SH output. + + witness: <signature> <pubkey> + scriptSig: <0 <20-byte-key-hash>> + (0x160014{20-byte-key-hash}) + scriptPubKey: HASH160 <20-byte-script-hash> EQUAL + (0xA914{20-byte-script-hash}87) + +The only item in scriptSig is hashed with HASH160, compared against the 20-byte-script-hash in scriptPubKey, and interpreted as: + + 0 <20-byte-key-hash> + +The P2WPKH witness program is then executed as described in the previous example. + +Comparing with the previous example, the scriptPubKey is 1 byte bigger and the scriptSig is 23 bytes bigger. Although a nested witness program is less efficient, its payment address is fully transparent and backward compatible for all Bitcoin reference client since version 0.6.0. + === P2WSH witness program === The following example is an 1-of-2 multi-signature version 0 pay-to-witness-script-hash (P2WSH) witness program. @@ -158,13 +182,13 @@ A P2WSH witness program allows arbitrarily large script as the 520-byte push lim The scriptPubKey occupies 34 bytes, as opposed to 23 bytes of BIP16 P2SH. The increased size improves security against possible collision attacks, as 2<sup>80</sup> work is not infeasible anymore (By the end of 2015, 2<sup>84</sup> hashes have been calculated in Bitcoin mining since the creation of Bitcoin). The spending script is same as the one for an equivalent BIP16 P2SH output but is moved to witness. -=== Witness program nested in BIP16 P2SH === +=== P2WSH nested in BIP16 P2SH === The following example is the same 1-of-2 multi-signature P2WSH witness program, but nested in a BIP16 P2SH output. witness: 0 <signature1> <1 <pubkey1> <pubkey2> 2 CHECKMULTISIG> scriptSig: <0 <32-byte-hash>> - (0x0020{32-byte-hash}) + (0x220020{32-byte-hash}) scriptPubKey: HASH160 <20-byte-hash> EQUAL (0xA914{20-byte-hash}87) @@ -174,18 +198,17 @@ The only item in scriptSig is hashed with HASH160, compared against the 20-byte- The P2WSH witness program is then executed as described in the previous example. -Comparing with the previous 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. +Comparing with the previous example, the scriptPubKey is 11 bytes smaller (with reduced security) while witness is the same. However, it also requires 35 bytes in scriptSig. === Extensible commitment structure === -The new commitment in coinbase transaction is a hash of the witness root hash and a witness nonce. The nonce currently has no consensus meaning, but in the future allows new commitment values for future softforks. For example, if a new consensus-critical commitment is required in the future, the commitment in -coinbase becomes: +The new commitment in coinbase transaction is a hash of the <code>witness root hash</code> and a <code>witness reserved value</code>. The <code>witness reserved value</code> currently has no consensus meaning, but in the future allows new commitment values for future softforks. For example, if a new consensus-critical commitment is required in the future, the commitment in coinbase becomes: - Double-SHA256(Witness root hash|Hash(new commitment|witness nonce)) + Double-SHA256(Witness root hash|Hash(new commitment|witness reserved value)) -For backward compatibility, the Hash(new commitment|witness nonce) will go to the coinbase witness, and the witness nonce will be recorded in another location specified by the future softfork. Any number of new commitment could be added in this way. +For backward compatibility, the <code>Hash(new commitment|witness reserved value)</code> will go to the coinbase witness, and the <code>witness reserved value</code> will be recorded in another location specified by the future softfork. Any number of new commitment could be added in this way. -Any commitments that are not consensus-critical to Bitcoin, such as merge-mining, MUST NOT use the witness nonce to preserve the ability to do upgrades of the Bitcoin consensus protocol. +Any commitments that are not consensus-critical to Bitcoin, such as merge-mining, MUST NOT use the <code>witness reserved value</code> to preserve the ability to do upgrades of the Bitcoin consensus protocol. The optional data space following the commitment also leaves room for metadata of future softforks, and MUST NOT be used for other purpose. @@ -249,33 +272,23 @@ As a soft fork, older software will continue to operate without modification. N == 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. +This BIP will be deployed by "version bits" BIP9 using bit 1. -(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.) +For Bitcoin mainnet, the BIP9 starttime will be midnight TBD UTC (Epoch timestamp TBD) and BIP9 timeout will be midnight TBD UTC (Epoch timestamp TBD). -=== 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. +For Bitcoin testnet, the BIP9 starttime will be midnight 1 May 2016 UTC (Epoch timestamp 1462060800) and BIP9 timeout will be midnight 1 May 2017 UTC (Epoch timestamp 1493596800). == 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. +== Footnotes == + +<references /> + == Reference Implementation == -https://github.com/sipa/bitcoin/commits/segwit +https://github.com/bitcoin/bitcoin/pull/7910 == References == diff --git a/bip-0143.mediawiki b/bip-0143.mediawiki index 72ef22d..bf56594 100644 --- a/bip-0143.mediawiki +++ b/bip-0143.mediawiki @@ -1,4 +1,4 @@ -<pre> +<pre> BIP: 143 Title: Transaction Signature Verification for Version 0 Witness Program Author: Johnson Lau <jl2012@xbt.hk> @@ -14,7 +14,7 @@ This proposal defines a new transaction digest algorithm for signature verificat == 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: +Unfortunately, there are at least 2 weaknesses in the original SignatureHash 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> @@ -28,37 +28,41 @@ A new transaction digest algorithm is defined, but only applicable to sigops in 2. hashPrevouts (32-byte hash) 3. hashSequence (32-byte hash) 4. outpoint (32-byte hash + 4-byte little endian) - 5. scriptCode of the input (varInt for the length + script) + 5. scriptCode of the input (serialized as scripts inside CTxOuts) 6. value of the output spent by this input (8-byte little endian) 7. nSequence of the input (4-byte little endian) 8. hashOutputs (32-byte hash) 9. nLocktime of the transaction (4-byte little endian) 10. sighash type of the signature (4-byte little endian) -All components in the original algorithm, including the behavior <code>OP_CODESEPERATOR</code>, remains unchanged. The only difference is the way of serialization and the inclusion of amount being spent. +Semantics of the original sighash types remain unchanged, except the followings: +# The way of serialization is changed; +# All sighash types commit to the amount being spent by the signed input; +# <code>FindAndDelete</code> of the signature is not applied to the <code>scriptCode</code>; +# <code>SINGLE</code> does not commit to the input index. When <code>ANYONECANPAY</code> is not set, the semantics are unchanged since <code>hashPrevouts</code> and <code>outpoint</code> together implictly commit to the input index. When <code>SINGLE</code> is used with <code>ANYONECANPAY</code>, omission of the index commitment allows permutation of the input-output pairs, as long as each pair is located at an equivalent index. The items 1, 4, 7, 9, 10 have the same meaning as the original algorithm. <ref name=wiki></ref> The item 5: *For P2WPKH witness program, the scriptCode is <code>0x1976a914{20-byte-pubkey-hash}88ac</code>. *For P2WSH witness program, -**if the <code>witnessScript</code> does not contain any <code>OP_CODESEPERATOR</code>, the <code>scriptCode</code> is a <code>varInt</code> for the length of the <code>witnessScript</code>, followed by the <code>witnessScript</code>. -**if the <code>witnessScript</code> contains any <code>OP_CODESEPERATOR</code>, the <code>scriptCode</code> is the evaluated script, with all <code>OP_CODESEPARATOR</code> and everything up to the last <code>OP_CODESEPARATOR</code> before the signature checking opcode being executed removed, and prepended by a <code>varInt</code> for the length of the truncated script. +**if the <code>witnessScript</code> does not contain any <code>OP_CODESEPERATOR</code>, the <code>scriptCode</code> is the <code>witnessScript</code> serialized as scripts inside CTxOuts. +**if the <code>witnessScript</code> contains any <code>OP_CODESEPERATOR</code>, the <code>scriptCode</code> is the evaluated script, with all <code>OP_CODESEPARATOR</code> and everything up to the last <code>OP_CODESEPARATOR</code> before the signature checking opcode being executed removed, serialized as scripts inside CTxOuts. The item 6 is a 8-byte value of the amount of bitcoin spent in this input. <code>hashPrevouts</code>: -*If the ANYONECANPAY flag is not set, hashPrevouts is the double SHA256 of the serialization of all input outpoints; +*If the <code>ANYONECANPAY</code> flag is not set, <code>hashPrevouts</code> is the double SHA256 of the serialization of all input outpoints; *Otherwise, <code>hashPrevouts</code> is a <code>uint256</code> of <code>0x0000......0000</code>. <code>hashSequence</code>: -*If none of the ANYONECANPAY, SINGLE, NONE sighash type is set, hashSequence is the double SHA256 of the serialization of nSequence of all inputs; +*If none of the <code>ANYONECANPAY</code>, <code>SINGLE</code>, <code>NONE</code> sighash type is set, <code>hashSequence</code> is the double SHA256 of the serialization of <code>nSequence</code> of all inputs; *Otherwise, <code>hashSequence</code> is a <code>uint256</code> of <code>0x0000......0000</code>. <code>hashOutputs</code>: -*If the sighash type is neither SINGLE nor NONE, hashOutputs is the double SHA256 of the serialization of all output value (8-byte little endian) with scriptPubKey (<code>varInt</code> for the length + script); -*If sighash type is SINGLE and the input index is not greater than the number of outputs, <code>hashOutputs</code> is the double SHA256 of the output value with <code>scriptPubKey</code> of the same index as the input; -*Otherwise, <code>hashOutputs</code> is a <code>uint256</code> of <code>0x0000......0000</code>. +*If the sighash type is neither <code>SINGLE</code> nor <code>NONE</code>, <code>hashOutputs</code> is the double SHA256 of the serialization of all output value (8-byte little endian) with <code>scriptPubKey</code> (serialized as scripts inside CTxOuts); +*If sighash type is <code>SINGLE</code> and the input index is not greater than the number of outputs, <code>hashOutputs</code> is the double SHA256 of the output value with <code>scriptPubKey</code> of the same index as the input; +*Otherwise, <code>hashOutputs</code> is a <code>uint256</code> of <code>0x0000......0000</code>.<ref>In the original algorithm, a <code>uint256</code> of <code>0x0000......0001</code> is commited if the input index for a <code>SINGLE</code> signature is greater than the number of outputs. In this BIP a <code>0x0000......0000</code> is commited, without changing the semantics.</ref> The <code>hashPrevouts</code>, <code>hashSequence</code>, and <code>hashOutputs</code> 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). @@ -137,7 +141,9 @@ Refer to the reference implementation, reproduced below, for the precise algorit scriptPubKey: 2103c9f4836b9a4f77fc0d81f7bcb01b7f1b35916864b9476c241ce9fc198bd25432ac value: 6.25 The second input comes from a P2WPKH witness program: - scriptPubKey: 00141d0f172a0ecb48aee1be1f2687d2963ae33f71a1, value: 6 + scriptPubKey : 00141d0f172a0ecb48aee1be1f2687d2963ae33f71a1, value: 6 + private key : 619c335025c7f4012e556c2a58b2506e30b8511b53ade95ea316fd8c3286feb9 + public key : 025476c2e83188368da1ff3e292e7acafcdb3566bb0ad253f62fc70f07aeee6357 To sign it with a nHashType of 1 (SIGHASH_ALL): @@ -189,11 +195,11 @@ This proposal is deployed with Segregated Witness softfork (BIP 141) == 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. +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, including the redefined sigops, as anyone-can-spend scripts. == Reference Implementation == -https://github.com/sipa/bitcoin/commits/segwit +https://github.com/bitcoin/bitcoin/pull/7910 == References == diff --git a/bip-0144.mediawiki b/bip-0144.mediawiki index 2da222c..f2c8857 100644 --- a/bip-0144.mediawiki +++ b/bip-0144.mediawiki @@ -86,9 +86,10 @@ Currently, the only witness objects type supported are script witnesses which co * '''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) +A node will signal that it can provide witnesses using the following service bit + + NODE_WITNESS = (1 << 3) + === Hashes === Transaction hashes used in the transaction merkle tree and txin outpoints are always computed using the old non-witness diff --git a/bip-0144/witnesstx.png b/bip-0144/witnesstx.png Binary files differindex 5fd8afc..cb02a63 100644 --- a/bip-0144/witnesstx.png +++ b/bip-0144/witnesstx.png |
