Transaction Signature Verification for Version 0 Witness Program

  BIP: 143
  Layer: Consensus (soft fork)
  Title: Transaction Signature Verification for Version 0 Witness Program
  Authors: Johnson Lau 
           Pieter Wuille 
  Status: Deployed
  Type: Specification
  Assigned: 2016-01-03
  License: PD

Abstract

This proposal defines a new transaction digest algorithm for signature verification in version 0 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.

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.

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.

Specification

A new transaction digest algorithm is defined, but only applicable to sigops in version 0 witness program: Double SHA256 of the serialization of: 1. nVersion of the transaction (4-byte little endian) 2. hashPrevouts (32-byte hash) 3. hashSequence (32-byte hash) 4. outpoint (32-byte hash + 4-byte little endian) 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)

Semantics of the original sighash types remain unchanged, except the following: # The way of serialization is changed; # All sighash types commit to the amount being spent by the signed input; # FindAndDelete of the signature is not applied to the scriptCode; # OP_CODESEPARATOR(s) after the last executed OP_CODESEPARATOR are not removed from the scriptCode (the last executed OP_CODESEPARATOR and any script before it are always removed); # SINGLE does not commit to the input index. When ANYONECANPAY is not set, the semantics are unchanged since hashPrevouts and outpoint together implicitly commit to the input index. When SINGLE is used with ANYONECANPAY, 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.

The item 5: *For P2WPKH witness program, the scriptCode is 0x1976a914{20-byte-pubkey-hash}88ac. *For P2WSH witness program, **if the witnessScript does not contain any OP_CODESEPARATOR, the scriptCode is the witnessScript serialized as scripts inside CTxOut. **if the witnessScript contains any OP_CODESEPARATOR, the scriptCode is the witnessScript but removing everything up to and including the last executed OP_CODESEPARATOR before the signature checking opcode being executed, serialized as scripts inside CTxOut. (The exact semantics is demonstrated in the examples below)

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 input outpoints; *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 amount (8-byte little endian) with scriptPubKey (serialized as scripts inside CTxOuts); *If sighash type is SINGLE and the input index is smaller than the number of outputs, hashOutputs is the double SHA256 of the output amount with scriptPubKey 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²) to O(n).

Refer to the reference implementation, reproduced below, for the precise algorithm:

  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 contained in hashSequence.
  ss << txTo.vin[nIn].prevout;
  ss << static_cast(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();

Restrictions on public key type

As a default policy, only compressed public keys are accepted in P2WPKH and P2WSH. Each public key passed to a sigop inside version 0 witness program must be a compressed key: the first byte MUST be either 0x02 or 0x03, and the size MUST be 33 bytes. Transactions that break this rule will not be relayed or mined by default.

Since this policy is preparation for a future softfork proposal, to avoid potential future funds loss, users MUST NOT use uncompressed keys in version 0 witness programs.

Example

To ensure consistency in consensus-critical behaviour, developers should test their implementations against all the tests below. More tests related to this proposal could be found under https://github.com/bitcoin/bitcoin/tree/master/src/test/data .

Native P2WPKH

The following is an unsigned transaction: 0100000002fff7f7881a8099afa6940d42d1e7f6362bec38171ea3edf433541db4e4ad969f0000000000eeffffffef51e1b804cc89d182d279655c3aa89e815b1b309fe287d9b2b55d57b90ec68a0100000000ffffffff02202cb206000000001976a9148280b37df378db99f66f85c95a783a76ac7a6d5988ac9093510d000000001976a9143bde42dbee7e4dbe6a21b2d50ce2f0167faa815988ac11000000

nVersion: 01000000 txin: 02 fff7f7881a8099afa6940d42d1e7f6362bec38171ea3edf433541db4e4ad969f 00000000 00 eeffffff ef51e1b804cc89d182d279655c3aa89e815b1b309fe287d9b2b55d57b90ec68a 01000000 00 ffffffff txout: 02 202cb20600000000 1976a9148280b37df378db99f66f85c95a783a76ac7a6d5988ac 9093510d00000000 1976a9143bde42dbee7e4dbe6a21b2d50ce2f0167faa815988ac nLockTime: 11000000

The first input comes from an ordinary P2PK: scriptPubKey : 2103c9f4836b9a4f77fc0d81f7bcb01b7f1b35916864b9476c241ce9fc198bd25432ac value: 6.25 private key : bbc27228ddcb9209d7fd6f36b02f7dfa6252af40bb2f1cbc7a557da8027ff866

The second input comes from a P2WPKH witness program: scriptPubKey : 00141d0f172a0ecb48aee1be1f2687d2963ae33f71a1, value: 6 private key : 619c335025c7f4012e556c2a58b2506e30b8511b53ade95ea316fd8c3286feb9 public key : 025476c2e83188368da1ff3e292e7acafcdb3566bb0ad253f62fc70f07aeee6357

To sign it with a nHashType of 1 (SIGHASH_ALL):

hashPrevouts: dSHA256(fff7f7881a8099afa6940d42d1e7f6362bec38171ea3edf433541db4e4ad969f00000000ef51e1b804cc89d182d279655c3aa89e815b1b309fe287d9b2b55d57b90ec68a01000000) = 96b827c8483d4e9b96712b6713a7b68d6e8003a781feba36c31143470b4efd37

hashSequence: dSHA256(eeffffffffffffff) = 52b0a642eea2fb7ae638c36f6252b6750293dbe574a806984b8e4d8548339a3b

hashOutputs: dSHA256(202cb206000000001976a9148280b37df378db99f66f85c95a783a76ac7a6d5988ac9093510d000000001976a9143bde42dbee7e4dbe6a21b2d50ce2f0167faa815988ac) = 863ef3e1a92afbfdb97f31ad0fc7683ee943e9abcf2501590ff8f6551f47e5e5

hash preimage: 0100000096b827c8483d4e9b96712b6713a7b68d6e8003a781feba36c31143470b4efd3752b0a642eea2fb7ae638c36f6252b6750293dbe574a806984b8e4d8548339a3bef51e1b804cc89d182d279655c3aa89e815b1b309fe287d9b2b55d57b90ec68a010000001976a9141d0f172a0ecb48aee1be1f2687d2963ae33f71a188ac0046c32300000000ffffffff863ef3e1a92afbfdb97f31ad0fc7683ee943e9abcf2501590ff8f6551f47e5e51100000001000000

nVersion: 01000000 hashPrevouts: 96b827c8483d4e9b96712b6713a7b68d6e8003a781feba36c31143470b4efd37 hashSequence: 52b0a642eea2fb7ae638c36f6252b6750293dbe574a806984b8e4d8548339a3b outpoint: ef51e1b804cc89d182d279655c3aa89e815b1b309fe287d9b2b55d57b90ec68a01000000 scriptCode: 1976a9141d0f172a0ecb48aee1be1f2687d2963ae33f71a188ac amount: 0046c32300000000 nSequence: ffffffff hashOutputs: 863ef3e1a92afbfdb97f31ad0fc7683ee943e9abcf2501590ff8f6551f47e5e5 nLockTime: 11000000 nHashType: 01000000

sigHash: c37af31116d1b27caf68aae9e3ac82f1477929014d5b917657d0eb49478cb670 signature: 304402203609e17b84f6a7d30c80bfa610b5b4542f32a8a0d5447a12fb1366d7f01cc44a0220573a954c4518331561406f90300e8f3358f51928d43c212a8caed02de67eebee01

The serialized signed transaction is: 01000000000102fff7f7881a8099afa6940d42d1e7f6362bec38171ea3edf433541db4e4ad969f00000000494830450221008b9d1dc26ba6a9cb62127b02742fa9d754cd3bebf337f7a55d114c8e5cdd30be022040529b194ba3f9281a99f2b1c0a19c0489bc22ede944ccf4ecbab4cc618ef3ed01eeffffffef51e1b804cc89d182d279655c3aa89e815b1b309fe287d9b2b55d57b90ec68a0100000000ffffffff02202cb206000000001976a9148280b37df378db99f66f85c95a783a76ac7a6d5988ac9093510d000000001976a9143bde42dbee7e4dbe6a21b2d50ce2f0167faa815988ac000247304402203609e17b84f6a7d30c80bfa610b5b4542f32a8a0d5447a12fb1366d7f01cc44a0220573a954c4518331561406f90300e8f3358f51928d43c212a8caed02de67eebee0121025476c2e83188368da1ff3e292e7acafcdb3566bb0ad253f62fc70f07aeee635711000000

nVersion: 01000000 marker: 00 flag: 01 txin: 02 fff7f7881a8099afa6940d42d1e7f6362bec38171ea3edf433541db4e4ad969f 00000000 494830450221008b9d1dc26ba6a9cb62127b02742fa9d754cd3bebf337f7a55d114c8e5cdd30be022040529b194ba3f9281a99f2b1c0a19c0489bc