Enhancement proposal for tx size / network fee estimation

[bc1p-dectector]

Hey @nothing0012 , this is tech partner of Ordyssey.com,

The 2-dummy algorithm proposed by msigner library effectively protects the interests of sellers, buyers and platforms. This has laid a good foundation for the industry's tx security.

But there is an issue for msigner's implementation in the fee estimation part, at present, msigner library uses a method similar to the following to estimate the tx size:

function msigner_txsize_calculate(inputCount, outputCount) {
    return 10 + 180 * inputCount + 34 * outputCount;
}

This method makes a rough estimate of the tx size. We hope to propose a more accurate estimation method that traverses the input and output of PSBT, and estimate the tx size according to the input and output types.

We wrote the following TxSizeCalculator class in Ordyssey signer code base (which also based on 2-dummy algorithm). We hope that the TxSizeCalculator can be trans-compiled and moved to msigner library (may do that with a new pull request) to make a more accurate estimate for tx size and network/miner fee paid by buyer.

const OPCODE_BYTES = 1;
const ECDSA_PUBLIC_KEY_BYTES = 33;
const ECDSA_SIGNATURE_BYTES = 72;
const SCHNORR_PUBLIC_KEY_BYTES = 32;
const SCHNORR_SIGNATURE_BYTES = 64;
const PUBLIC_KEY_HASH_BYTES = 20;
const P2SH_SCRIPT_HASH_BYTES = 20;
const P2WSH_SCRIPT_HASH_BYTES = 32;

class TxSizeCalculator {
    static scriptTypes = [ "p2pkh", "p2sh", "p2wpkh", "p2wsh", "p2tr" ]

    constructor() {
        this.inputCount = 0;
        this.outputCount = 0;
        this.hasWitness = false;
        this.totalInputVBytes = 0;
        this.totalOutputVBytes = 0;
    }

    addInputType(scriptType, count = 1, multisigPolicy = undefined) {
        if (!this.hasWitness) {
            this.hasWitness = (
                (scriptType !== "p2pkh" && scriptType !== "p2sh")
                || (scriptType === "p2sh" && multisigPolicy === undefined)
            );
        }
        this.inputCount += count;
        const vbytes = TxSizeCalculator.getInputVBytes(scriptType, count, multisigPolicy);
        this.totalInputVBytes += vbytes;
        return vbytes;
    }

    addOutputType(scriptType, count = 1) {
        this.outputCount += count;
        const vbytes = TxSizeCalculator.getOutputVBytes(scriptType, count);
        this.totalOutputVBytes += vbytes;
        return vbytes;
    }

    calculate() {
        const overheadVBytes = TxSizeCalculator.getOverheadVBytes(
            this.inputCount,
            this.outputCount,
            this.hasWitness
        );
        return this.totalInputVBytes + this.totalOutputVBytes + overheadVBytes;
    }

    static getOverheadVBytes(inputCount, outputCount, hasWitness) {
        let vbytes = (
            4       // nVersion
            + TxSizeCalculator._varintBytes(inputCount)    // number of inputs
            + TxSizeCalculator._varintBytes(outputCount)   // number of outputs
            + 4     // nLockTime
        );

        if (hasWitness) {
            vbytes += (
                0.5                     // segwit marker & segwit flag
                + inputCount * 0.25     // witness item count
            );
        }
        return vbytes;
    }

    static getInputVBytes(scriptType, count = 1, multisigPolicy = undefined) {
        if (multisigPolicy !== undefined) {
            scriptType = `${scriptType}-multisig`;
        }

        let scriptSigBytes = 0
        let witnessBytes = 0;
        switch(scriptType) {
            case "p2pkh":
                // scriptSig: OP_PUSH72 <ecdsa_signature> OP_PUSH33 <ecdsa_public_key>
                scriptSigBytes = (
                    OPCODE_BYTES
                    + ECDSA_SIGNATURE_BYTES
                    + OPCODE_BYTES
                    + ECDSA_PUBLIC_KEY_BYTES
                );
                break;

            case "p2wpkh":
                // witness: OP_PUSH72 <ecdsa_signature> OP_PUSH33 <ecdsa_public_key>
                witnessBytes =(
                    OPCODE_BYTES
                    + ECDSA_SIGNATURE_BYTES
                    + OPCODE_BYTES
                    + ECDSA_PUBLIC_KEY_BYTES
                );
                break;

            case "p2tr":
                // witness: OP_PUSH64 <schnorr_signature>
                witnessBytes = (
                    OPCODE_BYTES
                    + SCHNORR_SIGNATURE_BYTES
                );
                break;

            case "p2sh":
                // p2sh-p2wpkh
                // scriptSig: OP_PUSH22 <redeemScript>
                // redeemScript: OP_0 OP_PUSH20 <public_key_hash>
                // witness: OP_PUSH72 <ecdsa_signature> OP_PUSH33 <ecdsa_public_key>
                scriptSigBytes = (
                    OPCODE_BYTES
                    + OPCODE_BYTES
                    + OPCODE_BYTES
                    + PUBLIC_KEY_HASH_BYTES
                );
                witnessBytes = (
                    OPCODE_BYTES
                    + ECDSA_SIGNATURE_BYTES
                    + OPCODE_BYTES
                    + ECDSA_PUBLIC_KEY_BYTES
                );
                break;

            case "p2sh-multisig":
            case "p2wsh-multisig":
                // scriptSig(p2sh 2-of-3 multisig):
                //   OP_0
                //   OP_PUSH72 <ecdsa_signature>
                //   OP_PUSH72 <ecdsa_signature>
                //   OP_PUSHDATA1 105
                //   <redeemScript>
                // redeemScript:
                //   OP_2
                //   OP_PUSH33 <ecdsa_public_key>
                //   OP_PUSH33 <ecdsa_public_key>
                //   OP_PUSH33 <ecdsa_public_key>
                //   OP_3
                //   OP_CHECKMULTISIG
                const [ M, N ] = multisigPolicy.map((number) => parseInt(number));
                const redeemScriptBytes = (
                    OPCODE_BYTES    // OP_2
                    + N * (OPCODE_BYTES + ECDSA_PUBLIC_KEY_BYTES)   // OP_PUSH33 <pubkey>
                    + OPCODE_BYTES  // OP_3
                    + OPCODE_BYTES  // OP_CHECKMULTISIG
                );
                scriptSigBytes = (
                    OPCODE_BYTES    // OP_0
                    + M * (OPCODE_BYTES + ECDSA_SIGNATURE_BYTES)   // OP_PUSH72 <ecdsa_signature>
                    + TxSizeCalculator._scriptNumberBytes(redeemScriptBytes)    // OP_PUSHDATA1 105
                    + redeemScriptBytes
                );
                if (scriptType === "p2wsh-multisig") {
                    witnessBytes = scriptSigBytes;
                    scriptSigBytes = 0;
                }
                break;

            default:
                throw new Error(`invalid script type: ${scriptType}`);
        }

        return count * (
            36      // outpoint
            + TxSizeCalculator._varintBytes(scriptSigBytes)
            + scriptSigBytes
            + 4     // nSequence
            + (witnessBytes/4)
        );
    }

    static getOutputVBytes(scriptType, count = 1) {
        let scriptPubKeyBytes = 0;
        switch (scriptType) {
            case "p2pkh":
                // OP_DUP OP_HASH160 OP_PUSH20 <public_key_hash> OP_EQUALVERIFY OP_CHECKSIG
                scriptPubKeyBytes = 5 * OPCODE_BYTES + PUBLIC_KEY_HASH_BYTES;
                break;

            case "p2sh":
                // OP_HASH160 OP_PUSH20 <script_hash> OP_EQUAL
                scriptPubKeyBytes = 3 * OPCODE_BYTES + P2SH_SCRIPT_HASH_BYTES
                break;

            case "p2wpkh":
                // OP_0 OP_PUSH20 <public_key_hash>
                scriptPubKeyBytes = 2 * OPCODE_BYTES + PUBLIC_KEY_HASH_BYTES;
                break;

            case "p2wsh":
                // OP_0 OP_PUSH32 <script_hash>
                scriptPubKeyBytes = 2 * OPCODE_BYTES + P2WSH_SCRIPT_HASH_BYTES;
                break;

            case "p2tr":
                // OP_1 OP_PUSH32 <schnorr_public_key>
                scriptPubKeyBytes = 2 * OPCODE_BYTES + SCHNORR_PUBLIC_KEY_BYTES;
                break;

            default:
                throw new Error(`invalid script type: ${scriptPubKeyType}`);
        }

        return count * (
            8       // nValue
            + 1     // scriptPubKey length
            + scriptPubKeyBytes
        );
    }

    static _varintBytes(n) {
        if (n <= 252) {
            return 1;
        } else if (n <= 0xffff) {
            return 3;
        } else if (n <= 0xffffffff) {
            return 5;
        } else if (n <= 0xffffffffffffffffn) {
            return 9;
        } else {
            throw new Error("invalid var int");
        }
    }

    static _scriptNumberBytes(n) {
        if (n < 75) {
            return 1;
        } else if (n <= 255) {
            return 2;
        } else if (n <= 65535) {
            return 3;
        } else if (n <= 4294967295) {
            return 5;
        } else {
            throw new Error("script element too large");
        }
    }
}

We compared them. In a typical inscription transaction, the estimated value by msigner will be more than 400vB larger than the actual value. If calculated by 20sat/vB, the user's gas fee will be more spend 8000 sats. This is an example:

const { api, TxSizeCalculator } = require("../src/index.js");
const AddressTypes = [ "p2pkh", "p2sh", "p2wpkh", "p2wsh", "p2tr" ];

function getAddressType(addressOrOutputScript, network = "mainnet") {
    invariant(addressOrOutputScript !== undefined, "addressOrOutputScript");

    let payment = undefined;
    for (const addressType of AddressTypes) {
        params = (addressOrOutputScript instanceof Buffer)
            ? { output: addressOrOutputScript, network: bitcoin.getNetwork(network) }
            : { address: addressOrOutputScript, network: bitcoin.getNetwork(network) };

        try {
            payment = bitcoin[addressType](params);
        } catch (e) {
            // ignore
        }
    }

    if (payment) {
        return payment.name;
    } else {
        throw new Error("no matching address type");
    }
}
function msigner_txsize_calculate(inputCount, outputCount) {
    return 10 + 180 * inputCount + 34 * outputCount;
}

async function main () {
    const txid = "e01927af29de6dfebae93667867bc530f3db252c742bddbecbb0bdd81e60c838";
    const tx = await api.fetchTx(txid);
    console.log(`exact tx virtual bytes: ${tx.virtualSize()}vB`);

    const txSizeCalculator = new TxSizeCalculator();
    for (const [i, txInput] of tx.ins.entries()) {
        const prev_txid = txInput.hash.reverse().toString("hex");
        const prev_tx = await api.fetchTx(prev_txid);
        const prev_output = prev_tx.outs[txInput.index];
        const scriptType = getAddressType(prev_output.script);
        txSizeCalculator.addInputType(scriptType);
        console.log(`input #${i} type: ${scriptType}`);
    }

    for (const [i, txOutput] of tx.outs.entries()) {
        const scriptType = getAddressType(txOutput.script);
        txSizeCalculator.addOutputType(scriptType);
        console.log(`output type #${i}: ${scriptType}`);
    }

    const size1 = txSizeCalculator.calculate();
    console.log(`TxSizeCalculator: ${size1}vB`);

    const size2 = msigner_txsize_calculate(tx.ins.length, tx.outs.length);
    console.log(`msigner: ${size2}vB`);
}

main()
    .then(() => process.exit(0))
    .catch((e) => {
        console.error(e);
        process.exit(1);
    });

Welcome any discussion on this topic. Thanks again to @nothing0012 for creation of two-dummy algorithm. Learnt a lot!