vendor/github.com/btcsuite/btcd/blockchain/merkle.go

   1 // Copyright (c) 2013-2016 The btcsuite developers
   2 // Use of this source code is governed by an ISC
   3 // license that can be found in the LICENSE file.
   4
   5 package blockchain
   6
   7 import (
   8         "bytes"
   9         "fmt"
  10         "math"
  11
  12         "github.com/btcsuite/btcd/chaincfg/chainhash"
  13         "github.com/btcsuite/btcd/txscript"
  14         "github.com/btcsuite/btcutil"
  15 )
  16
  17 const (
  18         // CoinbaseWitnessDataLen is the required length of the only element within
  19         // the coinbase's witness data if the coinbase transaction contains a
  20         // witness commitment.
  21         CoinbaseWitnessDataLen = 32
  22
  23         // CoinbaseWitnessPkScriptLength is the length of the public key script
  24         // containing an OP_RETURN, the WitnessMagicBytes, and the witness
  25         // commitment itself. In order to be a valid candidate for the output
  26         // containing the witness commitment
  27         CoinbaseWitnessPkScriptLength = 38
  28 )
  29
  30 var (
  31         // WitnessMagicBytes is the prefix marker within the public key script
  32         // of a coinbase output to indicate that this output holds the witness
  33         // commitment for a block.
  34         WitnessMagicBytes = []byte{
  35                 txscript.OP_RETURN,
  36                 txscript.OP_DATA_36,
  37                 0xaa,
  38                 0x21,
  39                 0xa9,
  40                 0xed,
  41         }
  42 )
  43
  44 // nextPowerOfTwo returns the next highest power of two from a given number if
  45 // it is not already a power of two.  This is a helper function used during the
  46 // calculation of a merkle tree.
  47 func nextPowerOfTwo(n int) int {
  48         // Return the number if it's already a power of 2.
  49         if n&(n-1) == 0 {
  50                 return n
  51         }
  52
  53         // Figure out and return the next power of two.
  54         exponent := uint(math.Log2(float64(n))) + 1
  55         return 1 << exponent // 2^exponent
  56 }
  57
  58 // HashMerkleBranches takes two hashes, treated as the left and right tree
  59 // nodes, and returns the hash of their concatenation.  This is a helper
  60 // function used to aid in the generation of a merkle tree.
  61 func HashMerkleBranches(left *chainhash.Hash, right *chainhash.Hash) *chainhash.Hash {
  62         // Concatenate the left and right nodes.
  63         var hash [chainhash.HashSize * 2]byte
  64         copy(hash[:chainhash.HashSize], left[:])
  65         copy(hash[chainhash.HashSize:], right[:])
  66
  67         newHash := chainhash.DoubleHashH(hash[:])
  68         return &newHash
  69 }
  70
  71 // BuildMerkleTreeStore creates a merkle tree from a slice of transactions,
  72 // stores it using a linear array, and returns a slice of the backing array.  A
  73 // linear array was chosen as opposed to an actual tree structure since it uses
  74 // about half as much memory.  The following describes a merkle tree and how it
  75 // is stored in a linear array.
  76 //
  77 // A merkle tree is a tree in which every non-leaf node is the hash of its
  78 // children nodes.  A diagram depicting how this works for bitcoin transactions
  79 // where h(x) is a double sha256 follows:
  80 //
  81 //               root = h1234 = h(h12 + h34)
  82 //              /                           \
  83 //        h12 = h(h1 + h2)            h34 = h(h3 + h4)
  84 //         /            \              /            \
  85 //      h1 = h(tx1)  h2 = h(tx2)    h3 = h(tx3)  h4 = h(tx4)
  86 //
  87 // The above stored as a linear array is as follows:
  88 //
  89 //      [h1 h2 h3 h4 h12 h34 root]
  90 //
  91 // As the above shows, the merkle root is always the last element in the array.
  92 //
  93 // The number of inputs is not always a power of two which results in a
  94 // balanced tree structure as above.  In that case, parent nodes with no
  95 // children are also zero and parent nodes with only a single left node
  96 // are calculated by concatenating the left node with itself before hashing.
  97 // Since this function uses nodes that are pointers to the hashes, empty nodes
  98 // will be nil.
  99 //
 100 // The additional bool parameter indicates if we are generating the merkle tree
 101 // using witness transaction id's rather than regular transaction id's. This
 102 // also presents an additional case wherein the wtxid of the coinbase transaction
 103 // is the zeroHash.
 104 func BuildMerkleTreeStore(transactions []*btcutil.Tx, witness bool) []*chainhash.Hash {
 105         // Calculate how many entries are required to hold the binary merkle
 106         // tree as a linear array and create an array of that size.
 107         nextPoT := nextPowerOfTwo(len(transactions))
 108         arraySize := nextPoT*2 - 1
 109         merkles := make([]*chainhash.Hash, arraySize)
 110
 111         // Create the base transaction hashes and populate the array with them.
 112         for i, tx := range transactions {
 113                 // If we're computing a witness merkle root, instead of the
 114                 // regular txid, we use the modified wtxid which includes a
 115                 // transaction's witness data within the digest. Additionally,
 116                 // the coinbase's wtxid is all zeroes.
 117                 switch {
 118                 case witness && i == 0:
 119                         var zeroHash chainhash.Hash
 120                         merkles[i] = &zeroHash
 121                 case witness:
 122                         wSha := tx.MsgTx().WitnessHash()
 123                         merkles[i] = &wSha
 124                 default:
 125                         merkles[i] = tx.Hash()
 126                 }
 127
 128         }
 129
 130         // Start the array offset after the last transaction and adjusted to the
 131         // next power of two.
 132         offset := nextPoT
 133         for i := 0; i < arraySize-1; i += 2 {
 134                 switch {
 135                 // When there is no left child node, the parent is nil too.
 136                 case merkles[i] == nil:
 137                         merkles[offset] = nil
 138
 139                 // When there is no right child, the parent is generated by
 140                 // hashing the concatenation of the left child with itself.
 141                 case merkles[i+1] == nil:
 142                         newHash := HashMerkleBranches(merkles[i], merkles[i])
 143                         merkles[offset] = newHash
 144
 145                 // The normal case sets the parent node to the double sha256
 146                 // of the concatentation of the left and right children.
 147                 default:
 148                         newHash := HashMerkleBranches(merkles[i], merkles[i+1])
 149                         merkles[offset] = newHash
 150                 }
 151                 offset++
 152         }
 153
 154         return merkles
 155 }
 156
 157 // ExtractWitnessCommitment attempts to locate, and return the witness
 158 // commitment for a block. The witness commitment is of the form:
 159 // SHA256(witness root || witness nonce). The function additionally returns a
 160 // boolean indicating if the witness root was located within any of the txOut's
 161 // in the passed transaction. The witness commitment is stored as the data push
 162 // for an OP_RETURN with special magic bytes to aide in location.
 163 func ExtractWitnessCommitment(tx *btcutil.Tx) ([]byte, bool) {
 164         // The witness commitment *must* be located within one of the coinbase
 165         // transaction's outputs.
 166         if !IsCoinBase(tx) {
 167                 return nil, false
 168         }
 169
 170         msgTx := tx.MsgTx()
 171         for i := len(msgTx.TxOut) - 1; i >= 0; i-- {
 172                 // The public key script that contains the witness commitment
 173                 // must shared a prefix with the WitnessMagicBytes, and be at
 174                 // least 38 bytes.
 175                 pkScript := msgTx.TxOut[i].PkScript
 176                 if len(pkScript) >= CoinbaseWitnessPkScriptLength &&
 177                         bytes.HasPrefix(pkScript, WitnessMagicBytes) {
 178
 179                         // The witness commitment itself is a 32-byte hash
 180                         // directly after the WitnessMagicBytes. The remaining
 181                         // bytes beyond the 38th byte currently have no consensus
 182                         // meaning.
 183                         start := len(WitnessMagicBytes)
 184                         end := CoinbaseWitnessPkScriptLength
 185                         return msgTx.TxOut[i].PkScript[start:end], true
 186                 }
 187         }
 188
 189         return nil, false
 190 }
 191
 192 // ValidateWitnessCommitment validates the witness commitment (if any) found
 193 // within the coinbase transaction of the passed block.
 194 func ValidateWitnessCommitment(blk *btcutil.Block) error {
 195         // If the block doesn't have any transactions at all, then we won't be
 196         // able to extract a commitment from the non-existent coinbase
 197         // transaction. So we exit early here.
 198         if len(blk.Transactions()) == 0 {
 199                 str := "cannot validate witness commitment of block without " +
 200                         "transactions"
 201                 return ruleError(ErrNoTransactions, str)
 202         }
 203
 204         coinbaseTx := blk.Transactions()[0]
 205         if len(coinbaseTx.MsgTx().TxIn) == 0 {
 206                 return ruleError(ErrNoTxInputs, "transaction has no inputs")
 207         }
 208
 209         witnessCommitment, witnessFound := ExtractWitnessCommitment(coinbaseTx)
 210
 211         // If we can't find a witness commitment in any of the coinbase's
 212         // outputs, then the block MUST NOT contain any transactions with
 213         // witness data.
 214         if !witnessFound {
 215                 for _, tx := range blk.Transactions() {
 216                         msgTx := tx.MsgTx()
 217                         if msgTx.HasWitness() {
 218                                 str := fmt.Sprintf("block contains transaction with witness" +
 219                                         " data, yet no witness commitment present")
 220                                 return ruleError(ErrUnexpectedWitness, str)
 221                         }
 222                 }
 223                 return nil
 224         }
 225
 226         // At this point the block contains a witness commitment, so the
 227         // coinbase transaction MUST have exactly one witness element within
 228         // its witness data and that element must be exactly
 229         // CoinbaseWitnessDataLen bytes.
 230         coinbaseWitness := coinbaseTx.MsgTx().TxIn[0].Witness
 231         if len(coinbaseWitness) != 1 {
 232                 str := fmt.Sprintf("the coinbase transaction has %d items in "+
 233                         "its witness stack when only one is allowed",
 234                         len(coinbaseWitness))
 235                 return ruleError(ErrInvalidWitnessCommitment, str)
 236         }
 237         witnessNonce := coinbaseWitness[0]
 238         if len(witnessNonce) != CoinbaseWitnessDataLen {
 239                 str := fmt.Sprintf("the coinbase transaction witness nonce "+
 240                         "has %d bytes when it must be %d bytes",
 241                         len(witnessNonce), CoinbaseWitnessDataLen)
 242                 return ruleError(ErrInvalidWitnessCommitment, str)
 243         }
 244
 245         // Finally, with the preliminary checks out of the way, we can check if
 246         // the extracted witnessCommitment is equal to:
 247         // SHA256(witnessMerkleRoot || witnessNonce). Where witnessNonce is the
 248         // coinbase transaction's only witness item.
 249         witnessMerkleTree := BuildMerkleTreeStore(blk.Transactions(), true)
 250         witnessMerkleRoot := witnessMerkleTree[len(witnessMerkleTree)-1]
 251
 252         var witnessPreimage [chainhash.HashSize * 2]byte
 253         copy(witnessPreimage[:], witnessMerkleRoot[:])
 254         copy(witnessPreimage[chainhash.HashSize:], witnessNonce)
 255
 256         computedCommitment := chainhash.DoubleHashB(witnessPreimage[:])
 257         if !bytes.Equal(computedCommitment, witnessCommitment) {
 258                 str := fmt.Sprintf("witness commitment does not match: "+
 259                         "computed %v, coinbase includes %v", computedCommitment,
 260                         witnessCommitment)
 261                 return ruleError(ErrWitnessCommitmentMismatch, str)
 262         }
 263
 264         return nil
 265 }