New commitment structure, sigop limits, etc

1 files changed, 99 insertions, 99 deletions

diff --git a/bip-0141.mediawiki b/bip-0141.mediawiki
index ac44d87..7a5c28c 100644
--- a/bip-0141.mediawiki
+++ b/bip-0141.mediawiki
@@ -21,7 +21,7 @@ The entirety of the transaction's effects are determined by output consumption (
 
 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):
+# '''Nonintentional malleability becomes impossible'''. Since signature data is no longer part of the transaction hash, changes to how the transaction was signed are no longer relevant to transaction identification. As a solution of transaction malleability, this is superior to the canonical signature approach ([https://github.com/bitcoin/bips/edit/master/bip-0062.mediawiki 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
@@ -30,106 +30,67 @@ By removing this data from the transaction structure committed to the transactio
 # '''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. 
+#* New script system could be introduced without any limitation from the existing script semantic. For example, a new transaction digest algorithm for transaction signature verification is described in [https://github.com/bitcoin/bips/blob/master/bip-0143.mediawiki BIP143]
 
 ==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 new block rule is added which requires a commitment to the witness hashes, the double SHA256 of a transaction including witnesses. The witness hash of coinbase transaction 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:
+The commitment is recorded in a scriptPubKey of the coinbase transaction. It must be at least 38 bytes, with the first 6-byte of 0x6a24aa21a9ed, 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)
+  
+  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.
 
-<pre>SHA256('WitnessV1\x00\x00\x00\x00\x00\x00\x00' || nonce)</pre>
+If there are more than one scriptPubKey matching the pattern, the one with highest output index is assumed to be the commitment.
 
-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.
+=== Witness program ===
 
-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.
+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".
 
-=== Block size limit ===
-Blocks are currently limited to 1 MB total size. We change this restriction as follows:
+New rules for scriptSig:
+* 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.
 
-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.
+If the version byte is 0, the witness program 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 must result in exactly a single TRUE on the stack.
 
-The new rule is s<sub>v</sub> <= 1 MB.
+If the version byte is 1, the witness program 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. SHA256 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 witness program is between 2 and 31 bytes, the script must fail.
 
-=== Witness program ===
+If the version byte is 2 to 16, no further interpretation of the witness program or witness happens.
 
-* 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.
+=== Other consensus critical limits ===
 
-** 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.
+==== Block size ====
 
-=== Other consensus critical constraints ===
+Blocks are currently limited to 1,000,000 bytes (1MB) total size. We change this restriction as follows:
 
-== Block size analysis ==
-WORK IN PROGRESS
+''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.
 
-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>
+The new rule is total ''block cost'' ≤ 4,000,000.
 
-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.
+==== Sigops ====
 
-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%.
+Sigops per block is currently limited to 20,000. We change this restriction as follows:
 
+''Sigop cost'' is defined. The cost of a sigop in traditoinal script is 4, while the cost of a sigop in witness program is 1.
 
+The new rule is total ''sigop cost'' ≤ 80,000.
 
 == Examples ==
 
@@ -139,15 +100,16 @@ The following example is a version 0 witness program, equivalent to the existing
 
     witness:      <signature> <pubkey>
     scriptSig:    (empty)
-    scriptPubKey: OP_0 <0x76A914{20-byte-hash-value}88AC>
+    scriptPubKey: 0 <DUP HASH160 <20-byte-hash> EQUALVERIFY CHECKSIG>
+                  (0x001976A914{20-byte-hash}88AC)
 
-The OP_0 indicates the following push is a version 0 witness program. The witness program is deserialized and becomes:
+The '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
+    DUP HASH160 <20-byte-hash> EQUALVERIFY CHECKSIG
 
 The script is executed with the data from witness
 
-    <signature> <pubkey> DUP HASH160 <20byte-hash-value> EQUALVERIFY CHECKSIG
+    <signature> <pubkey> DUP HASH160 <20-byte-hash> 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.
 
@@ -155,39 +117,57 @@ Comparing with a P2PKH output, the witness program equivalent occupies 2 more by
 
 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>
+    witness:      0 <signature1> <1 <pubkey1> <pubkey2> 2 CHECKMULTISIG>
     scriptSig:    (empty)
-    scriptPubKey: OP_1 <0x{32-byte-hash-value}>
+    scriptPubKey: 1 <32-byte-hash>
+                  (0x5120{32-byte-hash})
 
-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:
+The '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 in scriptPubKey, and deserialized:
 
-    1 <33-byte-pubkey1> <33-byte-pubkey2> 2 CHECKMULTISIG
+    1 <pubkey1> <pubkey2> 2 CHECKMULTISIG
 
 The script is executed with the remaining data from witness:
 
-    0 <signature1> 1 <33-byte-pubkey1> <33-byte-pubkey2> 2 CHECKMULTISIG
+    0 <signature1> 1 <pubkey1> <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.
+The scriptPubKey occupies 34 bytes, as opposed to 23 bytes of 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 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
+    witness:      0 <signature1> <1 <pubkey1> <pubkey2> 2 CHECKMULTISIG>
+    scriptSig:    <1 <32-byte-hash>>
+                  (5120{32-byte-hash})
+    scriptPubKey: HASH160 <20-byte-hash> EQUAL
+                  (0x76A914{20-byte-hash}88AC)
 
-The only item in scriptSig is hashed with HASH160, compared against the 20-byte-hash-value in scriptPubKey, and interpreted as:
+The only item in scriptSig is hashed with HASH160, compared against the 20-byte-hash in scriptPubKey, and interpreted as:
 
-    OP_1 <0x{32-byte-hash-value}>
+    1 <32-byte-hash>
 
 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.
 
+=== Extensible commitment structure ===
+
+The new commitment in coinbase transaction is a hash of the witness root hash and a witness nonce. The nonce which currently has no consensus meaning, serves two purposes:
+
+* It 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))
+
+:: 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.
+
+* Any commitments that are not consensus-critical to Bitcoin, such as merge-mining, may utilize this witness nonce. However, they must not be committed directly as the nonce, or the external system may be forced to hardfork when Bitcoin introduces more consensus-critical commitments. Instead, they should use the nonce as the root of an extensible commitment tree, and should not make any assumption about the location and depth of their commitments in the tree. For example, in the external system, it may use a flag to indicate the actual location of the commitments with the Merkle paths provided.
+
+The optional data space following the commitment also leaves room for metadata of future softforks.
+
 === 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.
@@ -197,7 +177,9 @@ Such setups is not possible with BIP62 as the malleability fix, since the spendi
 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:
@@ -206,9 +188,15 @@ In the current Bitcoin protocol, it is possible to generate compact fraud proof
 # 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.
+Extra witness data can be committed that allows short proofs of block invalidity that SPV nodes can quickly verify:
+
+# Sum trees for transaction fee can be committed making it possible to construct short proofs that the miner does not add excessive fees to the coinbase transaction. Similar for the block size and sigop count limit.
+# 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.
+
+These commitments could be included in the extensible commitment structure 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.
@@ -216,23 +204,26 @@ Examples of new script system include Schnorr signatures which reduce the size o
 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).
+Currently there is only one nLockTime field in a transaction and all inputs must share the same value. [https://github.com/bitcoin/bips/edit/master/bip-0068.mediawiki 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 [https://github.com/bitcoin/bips/edit/master/bip-0065.mediawiki BIP65] and [https://github.com/bitcoin/bips/edit/master/bip-0112.mediawiki 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)
+* Sending bitcoin to upgraded wallets using a P2SH address (less efficient)
+* Sending bitcoin to upgraded wallets using a native witness program (more efficient) through [https://github.com/bitcoin/bips/blob/master/bip-0070.mediawiki BIP70] payment protocol
 
 '''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)
+* Sending bitcoin to upgraded wallets using a native witness program if BIP70 is not supported
 
 == Deployment ==
 
@@ -248,7 +239,6 @@ invalid, and all further blocks enforce the new rules.
 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,
@@ -258,10 +248,20 @@ 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
+
+https://github.com/sipa/bitcoin/commits/segwit2
+
+== References ==
+
+*[https://github.com/bitcoin/bips/blob/master/bip-0016.mediawiki BIP16 Pay to Script Hash]
+*[https://github.com/bitcoin/bips/blob/master/bip-0142.mediawiki BIP142 Address Formats for Witness Program]
+*[https://github.com/bitcoin/bips/blob/master/bip-0143.mediawiki BIP143 Transaction signature verification for version 0 and version 1 witness program]
+*[https://github.com/bitcoin/bips/blob/master/bip-0144.mediawiki BIP144 Segregated Witness (Peer Services)]
 
 == Copyright ==
+
 This document is placed in the public domain.