123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399 |
- // Copyright (c) 2013-2016 The btcsuite developers
- // Use of this source code is governed by an ISC
- // license that can be found in the LICENSE file.
- package mempool
- import (
- "fmt"
- "math/big"
- "time"
- "github.com/pkt-cash/pktd/btcutil/er"
- "github.com/pkt-cash/pktd/blockchain"
- "github.com/pkt-cash/pktd/btcutil"
- "github.com/pkt-cash/pktd/txscript"
- "github.com/pkt-cash/pktd/wire"
- )
- const (
- // maxStandardP2SHSigOps is the maximum number of signature operations
- // that are considered standard in a pay-to-script-hash script.
- maxStandardP2SHSigOps = 15
- // maxStandardTxCost is the max weight permitted by any transaction
- // according to the current default policy.
- maxStandardTxWeight = 400000
- // maxStandardSigScriptSize is the maximum size allowed for a
- // transaction input signature script to be considered standard. This
- // value allows for a 15-of-15 CHECKMULTISIG pay-to-script-hash with
- // compressed keys.
- //
- // The form of the overall script is: OP_0 <15 signatures> OP_PUSHDATA2
- // <2 bytes len> [OP_15 <15 pubkeys> OP_15 OP_CHECKMULTISIG]
- //
- // For the p2sh script portion, each of the 15 compressed pubkeys are
- // 33 bytes (plus one for the OP_DATA_33 opcode), and the thus it totals
- // to (15*34)+3 = 513 bytes. Next, each of the 15 signatures is a max
- // of 73 bytes (plus one for the OP_DATA_73 opcode). Also, there is one
- // extra byte for the initial extra OP_0 push and 3 bytes for the
- // OP_PUSHDATA2 needed to specify the 513 bytes for the script push.
- // That brings the total to 1+(15*74)+3+513 = 1627. This value also
- // adds a few extra bytes to provide a little buffer.
- // (1 + 15*74 + 3) + (15*34 + 3) + 23 = 1650
- maxStandardSigScriptSize = 1650
- // DefaultMinRelayTxFee is the minimum fee in satoshi that is required
- // for a transaction to be treated as free for relay and mining
- // purposes. It is also used to help determine if a transaction is
- // considered dust and as a base for calculating minimum required fees
- // for larger transactions. This value is in Satoshi/1000 bytes.
- DefaultMinRelayTxFee = btcutil.Amount(1000)
- // maxStandardMultiSigKeys is the maximum number of public keys allowed
- // in a multi-signature transaction output script for it to be
- // considered standard.
- maxStandardMultiSigKeys = 3
- // maxStandardLegacyInputs is the maximum number of transaction inputs
- // which will be allowed before the transaction is considered non-standard.
- // Hashing of the transaction in order to validate legacy (non-segwit)
- // inputs requires O(n**2) time because the transaction must be serialized
- // separately for each input.
- maxStandardLegacyInputs = 500
- )
- // calcMinRequiredTxRelayFee returns the minimum transaction fee required for a
- // transaction with the passed serialized size to be accepted into the memory
- // pool and relayed.
- func calcMinRequiredTxRelayFee(serializedSize int64, minRelayTxFee btcutil.Amount) int64 {
- // Calculate the minimum fee for a transaction to be allowed into the
- // mempool and relayed by scaling the base fee (which is the minimum
- // free transaction relay fee). minTxRelayFee is in Satoshi/kB so
- // multiply by serializedSize (which is in bytes) and divide by 1000 to
- // get minimum Satoshis.
- minFee := (serializedSize * int64(minRelayTxFee)) / 1000
- if minFee == 0 && minRelayTxFee > 0 {
- minFee = int64(minRelayTxFee)
- }
- // Set the minimum fee to the maximum possible value if the calculated
- // fee is not in the valid range for monetary amounts.
- if minFee < 0 || minFee > int64(btcutil.MaxUnits()) {
- minFee = int64(btcutil.MaxUnits())
- }
- return minFee
- }
- // checkInputsStandard performs a series of checks on a transaction's inputs
- // to ensure they are "standard". A standard transaction input within the
- // context of this function is one whose referenced public key script is of a
- // standard form and, for pay-to-script-hash, does not have more than
- // maxStandardP2SHSigOps signature operations. However, it should also be noted
- // that standard inputs also are those which have a clean stack after execution
- // and only contain pushed data in their signature scripts. This function does
- // not perform those checks because the script engine already does this more
- // accurately and concisely via the txscript.ScriptVerifyCleanStack and
- // txscript.ScriptVerifySigPushOnly flags.
- func checkInputsStandard(tx *btcutil.Tx, utxoView *blockchain.UtxoViewpoint) er.R {
- // NOTE: The reference implementation also does a coinbase check here,
- // but coinbases have already been rejected prior to calling this
- // function so no need to recheck.
- for i, txIn := range tx.MsgTx().TxIn {
- // It is safe to elide existence and index checks here since
- // they have already been checked prior to calling this
- // function.
- entry := utxoView.LookupEntry(txIn.PreviousOutPoint)
- originPkScript := entry.PkScript()
- switch txscript.GetScriptClass(originPkScript) {
- case txscript.ScriptHashTy:
- numSigOps := txscript.GetPreciseSigOpCount(
- txIn.SignatureScript, originPkScript, true)
- if numSigOps > maxStandardP2SHSigOps {
- str := fmt.Sprintf("transaction input #%d has "+
- "%d signature operations which is more "+
- "than the allowed max amount of %d",
- i, numSigOps, maxStandardP2SHSigOps)
- return txRuleError(wire.RejectNonstandard, str)
- }
- case txscript.NonStandardTy:
- str := fmt.Sprintf("transaction input #%d has a "+
- "non-standard script form", i)
- return txRuleError(wire.RejectNonstandard, str)
- }
- }
- return nil
- }
- // checkPkScriptStandard performs a series of checks on a transaction output
- // script (public key script) to ensure it is a "standard" public key script.
- // A standard public key script is one that is a recognized form, and for
- // multi-signature scripts, only contains from 1 to maxStandardMultiSigKeys
- // public keys.
- func checkPkScriptStandard(pkScript []byte, scriptClass txscript.ScriptClass) er.R {
- switch scriptClass {
- case txscript.MultiSigTy:
- numPubKeys, numSigs, err := txscript.CalcMultiSigStats(pkScript)
- if err != nil {
- str := fmt.Sprintf("multi-signature script parse "+
- "failure: %v", err)
- return txRuleError(wire.RejectNonstandard, str)
- }
- // A standard multi-signature public key script must contain
- // from 1 to maxStandardMultiSigKeys public keys.
- if numPubKeys < 1 {
- str := "multi-signature script with no pubkeys"
- return txRuleError(wire.RejectNonstandard, str)
- }
- if numPubKeys > maxStandardMultiSigKeys {
- str := fmt.Sprintf("multi-signature script with %d "+
- "public keys which is more than the allowed "+
- "max of %d", numPubKeys, maxStandardMultiSigKeys)
- return txRuleError(wire.RejectNonstandard, str)
- }
- // A standard multi-signature public key script must have at
- // least 1 signature and no more signatures than available
- // public keys.
- if numSigs < 1 {
- return txRuleError(wire.RejectNonstandard,
- "multi-signature script with no signatures")
- }
- if numSigs > numPubKeys {
- str := fmt.Sprintf("multi-signature script with %d "+
- "signatures which is more than the available "+
- "%d public keys", numSigs, numPubKeys)
- return txRuleError(wire.RejectNonstandard, str)
- }
- case txscript.NonStandardTy:
- return txRuleError(wire.RejectNonstandard,
- "non-standard script form")
- }
- return nil
- }
- var bigThousand = big.NewInt(1000)
- // isDust returns whether or not the passed transaction output amount is
- // considered dust or not based on the passed minimum transaction relay fee.
- // Dust is defined in terms of the minimum transaction relay fee. In
- // particular, if the cost to the network to spend coins is more than 1/3 of the
- // minimum transaction relay fee, it is considered dust.
- func isDust(txOut *wire.TxOut, minRelayTxFee btcutil.Amount) bool {
- // Unspendable outputs are considered dust.
- if txscript.IsUnspendable(txOut.PkScript) {
- return true
- }
- // The total serialized size consists of the output and the associated
- // input script to redeem it. Since there is no input script
- // to redeem it yet, use the minimum size of a typical input script.
- //
- // Pay-to-pubkey-hash bytes breakdown:
- //
- // Output to hash (34 bytes):
- // 8 value, 1 script len, 25 script [1 OP_DUP, 1 OP_HASH_160,
- // 1 OP_DATA_20, 20 hash, 1 OP_EQUALVERIFY, 1 OP_CHECKSIG]
- //
- // Input with compressed pubkey (148 bytes):
- // 36 prev outpoint, 1 script len, 107 script [1 OP_DATA_72, 72 sig,
- // 1 OP_DATA_33, 33 compressed pubkey], 4 sequence
- //
- // Input with uncompressed pubkey (180 bytes):
- // 36 prev outpoint, 1 script len, 139 script [1 OP_DATA_72, 72 sig,
- // 1 OP_DATA_65, 65 compressed pubkey], 4 sequence
- //
- // Pay-to-pubkey bytes breakdown:
- //
- // Output to compressed pubkey (44 bytes):
- // 8 value, 1 script len, 35 script [1 OP_DATA_33,
- // 33 compressed pubkey, 1 OP_CHECKSIG]
- //
- // Output to uncompressed pubkey (76 bytes):
- // 8 value, 1 script len, 67 script [1 OP_DATA_65, 65 pubkey,
- // 1 OP_CHECKSIG]
- //
- // Input (114 bytes):
- // 36 prev outpoint, 1 script len, 73 script [1 OP_DATA_72,
- // 72 sig], 4 sequence
- //
- // Pay-to-witness-pubkey-hash bytes breakdown:
- //
- // Output to witness key hash (31 bytes);
- // 8 value, 1 script len, 22 script [1 OP_0, 1 OP_DATA_20,
- // 20 bytes hash160]
- //
- // Input (67 bytes as the 107 witness stack is discounted):
- // 36 prev outpoint, 1 script len, 0 script (not sigScript), 107
- // witness stack bytes [1 element length, 33 compressed pubkey,
- // element length 72 sig], 4 sequence
- //
- //
- // Theoretically this could examine the script type of the output script
- // and use a different size for the typical input script size for
- // pay-to-pubkey vs pay-to-pubkey-hash inputs per the above breakdowns,
- // but the only combination which is less than the value chosen is
- // a pay-to-pubkey script with a compressed pubkey, which is not very
- // common.
- //
- // The most common scripts are pay-to-pubkey-hash, and as per the above
- // breakdown, the minimum size of a p2pkh input script is 148 bytes. So
- // that figure is used. If the output being spent is a witness program,
- // then we apply the witness discount to the size of the signature.
- //
- // The segwit analog to p2pkh is a p2wkh output. This is the smallest
- // output possible using the new segwit features. The 107 bytes of
- // witness data is discounted by a factor of 4, leading to a computed
- // value of 67 bytes of witness data.
- //
- // Both cases share a 41 byte preamble required to reference the input
- // being spent and the sequence number of the input.
- totalSize := txOut.SerializeSize() + 41
- if txscript.IsWitnessProgram(txOut.PkScript) {
- totalSize += (107 / blockchain.WitnessScaleFactor)
- } else {
- totalSize += 107
- }
- // The output is considered dust if the cost to the network to spend the
- // coins is more than 1/3 of the minimum free transaction relay fee.
- // minFreeTxRelayFee is in Satoshi/KB, so multiply by 1000 to
- // convert to bytes.
- //
- // Using the typical values for a pay-to-pubkey-hash transaction from
- // the breakdown above and the default minimum free transaction relay
- // fee of 1000, this equates to values less than 546 satoshi being
- // considered dust.
- //
- // The following is equivalent to (value/totalSize) * (1/3) * 1000
- // without needing to do floating point math.
- v := big.NewInt(txOut.Value)
- v.Mul(v, bigThousand)
- v.Div(v, big.NewInt(3*int64(totalSize)))
- return v.Cmp(big.NewInt(int64(minRelayTxFee))) < 0
- }
- // checkTransactionStandard performs a series of checks on a transaction to
- // ensure it is a "standard" transaction. A standard transaction is one that
- // conforms to several additional limiting cases over what is considered a
- // "sane" transaction such as having a version in the supported range, being
- // finalized, conforming to more stringent size constraints, having scripts
- // of recognized forms, and not containing "dust" outputs (those that are
- // so small it costs more to process them than they are worth).
- func checkTransactionStandard(tx *btcutil.Tx, height int32,
- medianTimePast time.Time, minRelayTxFee btcutil.Amount,
- maxTxVersion int32) er.R {
- // The transaction must be a currently supported version.
- msgTx := tx.MsgTx()
- if msgTx.Version > maxTxVersion || msgTx.Version < 1 {
- str := fmt.Sprintf("transaction version %d is not in the "+
- "valid range of %d-%d", msgTx.Version, 1,
- maxTxVersion)
- return txRuleError(wire.RejectNonstandard, str)
- }
- // The transaction must be finalized to be standard and therefore
- // considered for inclusion in a block.
- if !blockchain.IsFinalizedTransaction(tx, height, medianTimePast) {
- return txRuleError(wire.RejectNonstandard,
- "transaction is not finalized")
- }
- // Since extremely large transactions with a lot of inputs can cost
- // almost as much to process as the sender fees, limit the maximum
- // size of a transaction. This also helps mitigate CPU exhaustion
- // attacks.
- txWeight := blockchain.GetTransactionWeight(tx)
- if txWeight > maxStandardTxWeight {
- str := fmt.Sprintf("weight of transaction %v is larger than max "+
- "allowed weight of %v", txWeight, maxStandardTxWeight)
- return txRuleError(wire.RejectNonstandard, str)
- }
- hasLegacyInputs := false
- for i, txIn := range msgTx.TxIn {
- // Each transaction input signature script must not exceed the
- // maximum size allowed for a standard transaction. See
- // the comment on maxStandardSigScriptSize for more details.
- sigScriptLen := len(txIn.SignatureScript)
- if sigScriptLen > maxStandardSigScriptSize {
- str := fmt.Sprintf("transaction input %d: signature "+
- "script size of %d bytes is large than max "+
- "allowed size of %d bytes", i, sigScriptLen,
- maxStandardSigScriptSize)
- return txRuleError(wire.RejectNonstandard, str)
- }
- // Each transaction input signature script must only contain
- // opcodes which push data onto the stack.
- if !txscript.IsPushOnlyScript(txIn.SignatureScript) {
- str := fmt.Sprintf("transaction input %d: signature "+
- "script is not push only", i)
- return txRuleError(wire.RejectNonstandard, str)
- }
- hasLegacyInputs = hasLegacyInputs || len(txIn.Witness) == 0
- }
- if hasLegacyInputs && len(msgTx.TxIn) > maxStandardLegacyInputs {
- return txRuleError(wire.RejectNonstandard,
- fmt.Sprintf("transaction has legacy inputs and has %d inputs which is "+
- "more than the limit (%d) for transactions with legacy inputs",
- len(msgTx.TxIn), maxStandardLegacyInputs))
- }
- // None of the output public key scripts can be a non-standard script or
- // be "dust" (except when the script is a null data script).
- numNullDataOutputs := 0
- for i, txOut := range msgTx.TxOut {
- scriptClass := txscript.GetScriptClass(txOut.PkScript)
- err := checkPkScriptStandard(txOut.PkScript, scriptClass)
- if err != nil {
- return err
- }
- // Accumulate the number of outputs which only carry data. For
- // all other script types, ensure the output value is not
- // "dust".
- if scriptClass == txscript.NullDataTy {
- numNullDataOutputs++
- } else if isDust(txOut, minRelayTxFee) {
- str := fmt.Sprintf("transaction output %d: payment "+
- "of %d is dust", i, txOut.Value)
- return txRuleError(wire.RejectDust, str)
- }
- }
- // A standard transaction must not have more than one output script that
- // only carries data.
- if numNullDataOutputs > 1 {
- str := "more than one transaction output in a nulldata script"
- return txRuleError(wire.RejectNonstandard, str)
- }
- return nil
- }
- // GetTxVirtualSize computes the virtual size of a given transaction. A
- // transaction's virtual size is based off its weight, creating a discount for
- // any witness data it contains, proportional to the current
- // blockchain.WitnessScaleFactor value.
- func GetTxVirtualSize(tx *btcutil.Tx) int64 {
- // vSize := (weight(tx) + 3) / 4
- // := (((baseSize * 3) + totalSize) + 3) / 4
- // We add 3 here as a way to compute the ceiling of the prior arithmetic
- // to 4. The division by 4 creates a discount for wit witness data.
- return (blockchain.GetTransactionWeight(tx) + (blockchain.WitnessScaleFactor - 1)) /
- blockchain.WitnessScaleFactor
- }
|