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