1 package mempool
2 3 import (
4 "fmt"
5 "github.com/p9c/p9/pkg/amt"
6 "time"
7 8 "github.com/p9c/p9/pkg/blockchain"
9 "github.com/p9c/p9/pkg/txscript"
10 "github.com/p9c/p9/pkg/util"
11 "github.com/p9c/p9/pkg/wire"
12 )
13 14 const (
15 // maxStandardP2SHSigOps is the maximum number of signature operations that are
16 // considered standard in a pay-to-script-hash script.
17 maxStandardP2SHSigOps = 15
18 // maxStandardTxCost is the max weight permitted by any transaction according to
19 // the current default policy.
20 maxStandardTxWeight = 400000
21 // maxStandardSigScriptSize is the maximum size allowed for a transaction input
22 // signature script to be considered standard. This value allows for a 15-of-15
23 // CHECKMULTISIG pay-to-script-hash with compressed keys. The form of the
24 // overall script is:
25 //
26 // OP_0 <15 signatures> OP_PUSHDATA2 <2 bytes len> [OP_15 <15 pubkeys> OP_15 OP_CHECKMULTISIG]
27 //
28 // For the p2sh script portion, each of the 15 compressed pubkeys are 33 bytes (
29 // plus one for the OP_DATA_33 opcode), and the thus it totals to ( 15*34)+3 =
30 // 513 bytes.
31 //
32 // Next each of the 15 signatures is a max of 73 bytes (plus one for the
33 // OP_DATA_73 opcode). Also there is one extra byte for the initial extra OP_0
34 // push and 3 bytes for the OP_PUSHDATA2 needed to specify the 513 bytes for the
35 // script push.
36 //
37 // That brings the total to 1+(15*74)+3+513 = 1627. This value also adds a few
38 // extra bytes to provide a little buffer. ( 1 + 15*74 + 3) + (15*34 + 3) + 23 =
39 // 1650
40 maxStandardSigScriptSize = 1650
41 // maxStandardMultiSigKeys is the maximum number of public keys allowed in a
42 // multi-signature transaction output script for it to be considered standard.
43 maxStandardMultiSigKeys = 3
44 )
45 46 // calcMinRequiredTxRelayFee returns the minimum transaction fee required for a
47 // transaction with the passed serialized size to be accepted into the memory
48 // pool and relayed.
49 func calcMinRequiredTxRelayFee(serializedSize int64, minRelayTxFee amt.Amount) int64 {
50 // Calculate the minimum fee for a transaction to be allowed into the mempool
51 // and relayed by scaling the base fee ( which is the minimum free transaction
52 // relay fee). minTxRelayFee is in Satoshi/kB so multiply by serializedSize (
53 // which is in bytes) and divide by 1000 to get minimum Satoshis.
54 minFee := (serializedSize * int64(minRelayTxFee)) / 1000
55 56 if minFee == 0 && minRelayTxFee > 0 {
57 minFee = int64(minRelayTxFee)
58 }
59 // Set the minimum fee to the maximum possible value if the calculated fee is
60 // not in the valid range for monetary amounts.
61 if minFee < 0 || minFee > int64(amt.MaxSatoshi) {
62 minFee = int64(amt.MaxSatoshi)
63 }
64 return minFee
65 }
66 67 // checkInputsStandard performs a series of checks on a transaction's inputs to
68 // ensure they are "standard". A standard transaction input within the context
69 // of this function is one whose referenced public key script is of a standard
70 // form and for pay-to -script-hash, does not have more than
71 // maxStandardP2SHSigOps signature operations. However it should also be noted
72 // that standard inputs also are those which have a clean stack after execution
73 // and only contain pushed data in their signature scripts. This function does
74 // not perform those checks because the script engine already does this more
75 // accurately and concisely via the txscript. ScriptVerifyCleanStack and
76 // txscript.ScriptVerifySigPushOnly flags.
77 func checkInputsStandard(tx *util.Tx, utxoView *blockchain.UtxoViewpoint) (e error) {
78 // NOTE: The reference implementation also does a coinbase check here, but
79 // coinbases have already been rejected prior to calling this function so no
80 // need to recheck.
81 for i, txIn := range tx.MsgTx().TxIn {
82 // It is safe to elide existence and index checks here since they have already
83 // been checked prior to calling this function.
84 entry := utxoView.LookupEntry(txIn.PreviousOutPoint)
85 originPkScript := entry.PkScript()
86 switch txscript.GetScriptClass(originPkScript) {
87 case txscript.ScriptHashTy:
88 numSigOps := txscript.GetPreciseSigOpCount(
89 txIn.SignatureScript, originPkScript, true,
90 )
91 if numSigOps > maxStandardP2SHSigOps {
92 str := fmt.Sprintf(
93 "transaction input #%d has %d signature"+
94 " operations which is more than the allowed max amount of %d",
95 i, numSigOps, maxStandardP2SHSigOps,
96 )
97 return txRuleError(wire.RejectNonstandard, str)
98 }
99 case txscript.NonStandardTy:
100 str := fmt.Sprintf(
101 "transaction input #%d has a non-standard"+
102 " script form", i,
103 )
104 return txRuleError(wire.RejectNonstandard, str)
105 }
106 }
107 return nil
108 }
109 110 // checkPkScriptStandard performs a series of checks on a transaction output
111 // script (public key script) to ensure it is a "standard" public key script. A
112 // standard public key script is one that is a recognized form, and for
113 // multi-signature scripts only contains from 1 to maxStandardMultiSigKeys
114 // public keys.
115 func checkPkScriptStandard(pkScript []byte, scriptClass txscript.ScriptClass) (e error) {
116 switch scriptClass {
117 case txscript.MultiSigTy:
118 numPubKeys, numSigs, e := txscript.CalcMultiSigStats(pkScript)
119 if e != nil {
120 str := fmt.Sprintf(
121 "multi-signature script parse failure: %v", e,
122 )
123 return txRuleError(wire.RejectNonstandard, str)
124 }
125 // A standard multi-signature public key script must contain from 1 to
126 // maxStandardMultiSigKeys public keys.
127 if numPubKeys < 1 {
128 str := "multi-signature script with no pubkeys"
129 return txRuleError(wire.RejectNonstandard, str)
130 }
131 if numPubKeys > maxStandardMultiSigKeys {
132 str := fmt.Sprintf(
133 "multi-signature script with %d public keys"+
134 " which is more than the allowed max of %d", numPubKeys,
135 maxStandardMultiSigKeys,
136 )
137 return txRuleError(wire.RejectNonstandard, str)
138 }
139 // A standard multi-signature public key script must have at least 1 signature
140 // and no more signatures than available public keys.
141 if numSigs < 1 {
142 return txRuleError(
143 wire.RejectNonstandard,
144 "multi-signature script with no signatures",
145 )
146 }
147 if numSigs > numPubKeys {
148 str := fmt.Sprintf(
149 "multi-signature script with %d signatures"+
150 " which is more than the available %d public keys", numSigs,
151 numPubKeys,
152 )
153 return txRuleError(wire.RejectNonstandard, str)
154 }
155 case txscript.NonStandardTy:
156 return txRuleError(wire.RejectNonstandard, "non-standard script form")
157 }
158 return nil
159 }
160 161 // isDust returns whether or not the passed transaction output amount is
162 // considered dust or not based on the passed minimum transaction relay fee.
163 // Dust is defined in terms of the minimum transaction relay fee. In particular,
164 // if the cost to the network to spend coins is more than 1/3 of the minimum
165 // transaction relay fee, it is considered dust.
166 func isDust(txOut *wire.TxOut, minRelayTxFee amt.Amount) bool {
167 // Unspendable outputs are considered dust.
168 if txscript.IsUnspendable(txOut.PkScript) {
169 return true
170 }
171 // The total serialized size consists of the output and the associated input
172 // script to redeem it. Since there is no input script to redeem it yet, use the
173 // minimum size of a typical input script. Pay-to-pubkey-hash bytes breakdown:
174 //
175 // Output to hash (34 bytes):
176 // 8 value, 1 script len, 25 script [1 OP_DUP, 1 OP_HASH_160,
177 // 1 OP_DATA_20, 20 hash, 1 OP_EQUALVERIFY, 1 OP_CHECKSIG]
178 //
179 // Input with compressed pubkey (148 bytes):
180 // 36 prev outpoint, 1 script len, 107 script [1 OP_DATA_72, 72 sig,
181 // 1 OP_DATA_33, 33 compressed pubkey], 4 sequence
182 // Input with uncompressed pubkey (180 bytes):
183 //
184 // 36 prev outpoint, 1 script len, 139 script [1 OP_DATA_72, 72 sig,
185 // 1 OP_DATA_65, 65 compressed pubkey], 4 sequence
186 //
187 // Pay-to-pubkey bytes breakdown:
188 //
189 // Output to compressed pubkey (44 bytes):
190 // 8 value, 1 script len, 35 script [1 OP_DATA_33,
191 // 33 compressed pubkey, 1 OP_CHECKSIG]
192 //
193 // Output to uncompressed pubkey (76 bytes):
194 // 8 value, 1 script len, 67 script [1 OP_DATA_65, 65 pubkey,
195 // 1 OP_CHECKSIG]
196 //
197 // Input (114 bytes):
198 // 36 prev outpoint, 1 script len, 73 script [1 OP_DATA_72,
199 // 72 sig], 4 sequence
200 //
201 // Pay-to-witness-pubkey-hash bytes breakdown:
202 //
203 // Output to witness key hash (31 bytes);
204 // 8 value, 1 script len, 22 script [1 OP_0, 1 OP_DATA_20,
205 // 20 bytes hash160]
206 //
207 // Input (67 bytes as the 107 witness stack is discounted):
208 // 36 prev outpoint, 1 script len, 0 script (not sigScript), 107
209 // witness stack bytes [1 element length, 33 compressed pubkey,
210 // element length 72 sig], 4 sequence
211 //
212 // Theoretically this could examine the script type of the output script and use
213 // a different size for the typical input script size for pay-to-pubkey vs
214 // pay-to-pubkey-hash inputs per the above breakdowns, but the only combination
215 // which is less than the value chosen is a pay-to-pubkey script with a
216 // compressed pubkey, which is not very common.
217 //
218 // The most common scripts are pay-to-pubkey-hash, and as per the above
219 // breakdown, the minimum size of a p2pkh input script is 148 bytes. So that
220 // figure is used. If the output being spent is a witness program, then we apply
221 // the witness discount to the size of the signature.
222 //
223 // The segwit analogue to p2pkh is a p2wkh output. This is the smallest output
224 // possible using the new segwit features. The 107 bytes of witness data is
225 // discounted by a factor of 4, leading to a computed value of 67 bytes of
226 // witness data.
227 //
228 // Both cases share a 41 byte preamble required to reference the input being
229 // spent and the sequence number of the input.
230 totalSize := txOut.SerializeSize() + 41
231 if txscript.IsWitnessProgram(txOut.PkScript) {
232 totalSize += 107
233 } else {
234 totalSize += 107
235 }
236 // The output is considered dust if the cost to the network to spend the coins
237 // is more than 1/3 of the minimum free transaction relay fee. minFreeTxRelayFee
238 // is in Satoshi/KB so multiply by 1000 to convert to bytes.
239 //
240 // Using the typical values for a pay-to-pubkey-hash transaction from the
241 // breakdown above and the default minimum free transaction relay fee of 1000,
242 // this equates to values less than 546 satoshi being considered dust.
243 //
244 // The following is equivalent to (value/totalSize) * (1/3) * 1000 without
245 // needing to do floating point math.
246 return txOut.Value*1000/(3*int64(totalSize)) < int64(minRelayTxFee)
247 }
248 249 // checkTransactionStandard performs a series of checks on a transaction to
250 // ensure it is a "standard" transaction.
251 //
252 // A standard transaction is one that conforms to several additional limiting
253 // cases over what is considered a "sane" transaction such as having a version
254 // in the supported range, being finalized, conforming to more stringent size
255 // constraints, having scripts of recognized forms, and not containing "dust"
256 // outputs (those that are so small it costs more to process them than they are
257 // worth).
258 func checkTransactionStandard(
259 tx *util.Tx, height int32,
260 medianTimePast time.Time, minRelayTxFee amt.Amount,
261 maxTxVersion int32,
262 ) (e error) {
263 // The transaction must be a currently supported version.
264 msgTx := tx.MsgTx()
265 if msgTx.Version > maxTxVersion || msgTx.Version < 1 {
266 str := fmt.Sprintf(
267 "transaction version %d is not in the "+
268 "valid range of %d-%d", msgTx.Version, 1,
269 maxTxVersion,
270 )
271 return txRuleError(wire.RejectNonstandard, str)
272 }
273 // The transaction must be finalized to be standard and therefore considered for
274 // inclusion in a block.
275 if !blockchain.IsFinalizedTransaction(tx, height, medianTimePast) {
276 return txRuleError(
277 wire.RejectNonstandard,
278 "transaction is not finalized",
279 )
280 }
281 // Since extremely large transactions with a lot of inputs can cost almost as
282 // much to process as the sender fees, limit the maximum size of a transaction.
283 // This also helps mitigate CPU exhaustion attacks.
284 txWeight := blockchain.GetTransactionWeight(tx)
285 if txWeight > maxStandardTxWeight {
286 str := fmt.Sprintf(
287 "weight of transaction %v is larger than max "+
288 "allowed weight of %v", txWeight, maxStandardTxWeight,
289 )
290 return txRuleError(wire.RejectNonstandard, str)
291 }
292 for i, txIn := range msgTx.TxIn {
293 // Each transaction input signature script must not exceed the maximum size
294 // allowed for a standard transaction. See the comment on
295 // maxStandardSigScriptSize for more details.
296 sigScriptLen := len(txIn.SignatureScript)
297 if sigScriptLen > maxStandardSigScriptSize {
298 str := fmt.Sprintf(
299 "transaction input %d: signature "+
300 "script size of %d bytes is large than max "+
301 "allowed size of %d bytes", i, sigScriptLen,
302 maxStandardSigScriptSize,
303 )
304 return txRuleError(wire.RejectNonstandard, str)
305 }
306 // Each transaction input signature script must only contain opcodes which push
307 // data onto the stack.
308 if !txscript.IsPushOnlyScript(txIn.SignatureScript) {
309 str := fmt.Sprintf(
310 "transaction input %d: signature "+
311 "script is not push only", i,
312 )
313 return txRuleError(wire.RejectNonstandard, str)
314 }
315 }
316 // None of the output public key scripts can be a non-standard script or be
317 // "dust" (except when the script is a null data script).
318 numNullDataOutputs := 0
319 for i, txOut := range msgTx.TxOut {
320 scriptClass := txscript.GetScriptClass(txOut.PkScript)
321 e := checkPkScriptStandard(txOut.PkScript, scriptClass)
322 if e != nil {
323 // Attempt to extract a reject code from the error so it can be retained. When
324 // not possible, fall back to a non standard error.
325 rejectCode := wire.RejectNonstandard
326 if rejCode, found := extractRejectCode(e); found {
327 rejectCode = rejCode
328 }
329 str := fmt.Sprintf("transaction output %d: %v", i, e)
330 return txRuleError(rejectCode, str)
331 }
332 // Accumulate the number of outputs which only carry data. For all other script
333 // types, ensure the output value is not "dust".
334 if scriptClass == txscript.NullDataTy {
335 numNullDataOutputs++
336 } else if isDust(txOut, minRelayTxFee) {
337 str := fmt.Sprintf(
338 "transaction output %d: payment of %d is dust"+
339 "", i, txOut.Value,
340 )
341 return txRuleError(wire.RejectDust, str)
342 }
343 }
344 // A standard transaction must not have more than one output script that only
345 // carries data.
346 if numNullDataOutputs > 1 {
347 str := "more than one transaction output in a nulldata script"
348 return txRuleError(wire.RejectNonstandard, str)
349 }
350 return nil
351 }
352 353 // GetTxVirtualSize computes the virtual size of a given transaction.
354 // A transaction's virtual size is based off its weight,
355 // creating a discount for any witness data it contains,
356 // proportional to the current blockchain.WitnessScaleFactor value.
357 func GetTxVirtualSize(tx *util.Tx) int64 {
358 // vSize := (weight(tx) + 3) / 4
359 // := (((baseSize * 3) + totalSize) + 3) / 4
360 // We add 3 here as a way to compute the ceiling of the prior arithmetic
361 // to 4. The division by 4 creates a discount for wit witness data.
362 return (blockchain.GetTransactionWeight(tx) + (blockchain.WitnessScaleFactor - 1)) /
363 blockchain.WitnessScaleFactor
364 }
365