Skip to content

Latest commit

 

History

History
355 lines (199 loc) · 50 KB

rationale.md

File metadata and controls

355 lines (199 loc) · 50 KB

Rationale

This section documents design decisions made in this specification.

Table of Contents

Use of Explicitly-Defined Density Limits

This proposal defines explicit limits on the overall density of computation required to validate both transactions and blocks, particularly of arithmetic, hashing, and signature checking computations. These explicit limits predictably cap the worst-case cost of validating transactions and blocks across all possible contract constructions and transaction-packing schemes (see Rationale: Use of Input Length-Based Densities for details).

Alternatively, this proposal could continue to indirectly limit the worst-case validation costs of transactions and blocks by specifying a system of one or more constant limits applied at various stages of VM evaluation. At best, such statically-defined, per-input limit schemes obfuscate the true limits: determining the real-world, worst-case validation performance of such schemes requires exhaustive enumeration of optimally-packed attack cases. Worse, the precise construction of worst-case attacks becomes significant to real world node performance requirements; any contract construction discovery or network upgrade which reduces contract lengths can magnify an unpredictable set of worst case attacks: e.g. more abusive transactions may be packed into abusive blocks, more abusive inputs may be packed into abusive transactions, fewer abusive transactions are required to exhaust a node's compute capacity, etc.

Finally, because statically-defined, per-input limit schemes fundamentally apply the same limits to 41-byte inputs as they apply to 10,000-byte inputs, the baseline variability of compute requirements ranges from 1 to 243.90 times the worst-case validation (again, determinable only via exhaustive enumeration)1. In practice, this means that some non-malicious contracts (real users) will be limited – ostensibly to protect the network from abusive use of computation during transaction validation – after using less than 1% of the net computation afforded to intentionally-malicious contracts2.

Notes
  1. 10000 / 41 = 243.902439...
  2. 1 / (10000 / 41) = 0.41%

Exclusion of "Gas System" Behaviors

This proposal preserves the Bitcoin Cash network's highly-scalable, stateless validation architecture. Bitcoin Cash contract validation remains stateless and cacheable:

  1. Contracts can be verified using only data derived from spent UTXOs and the transaction itself,
  2. A successful contract validation result can be cached without later re-validation, and
  3. All invalid transactions can be quickly rejected/discarded, with minimal computation requirements for network nodes.

Global-State Validation Architectures

The global-state transaction validation architecture of other, similarly-capable virtual machines – like the Ethereum Virtual Machine (EVM) – architecturally-prevent those systems from achieving the scalability of Bitcoin Cash:

  1. Contracts can reference data derived from unrelated network state,
  2. Contract evaluations cannot be safely cached – all global transactions must be re-validated in the precise order selected by each new block's miner/validator, and
  3. Invalid transactions – both intentionally-abusive and unintentionally-invalid transactions (e.g. honest users underestimating "gas" fees) – exact an orders-of-magnitude greater computation cost on all network node operators than the equivalent cost on Bitcoin Cash network node operators.

In these less efficient validation architectures, maintaining acceptable transaction throughput performance requires both significant development effort and user-facing structural changes, like EVM's pay-per-compute, "gas" regime. With such gas systems, all structurally-valid transactions (even transactions which fail validation by unintentionally exceeding the allotted virtual-compute time purchased by the "gas" fee paid) are at least partially validated and included in the next block – regardless of whether or not the end user intended for their transaction to fail. This leads to:

  1. Poor user experiences – users are forced to accept real-world financial losses for the unpredictability of gas fee markets and/or the technical failures of the network, nodes, contracts, and/or wallet systems.
  2. Financial limitation of contract capabilities – because the per-computation impact of contracts on all network nodes is thousands of times higher than on scalable architectures like Bitcoin Cash, global-state systems are forced to charge a meaningful price for each additional computation. In many cases, this regime is so inefficient that it guides contract development away from algorithms which are more correct or provide better user experiences, and toward algorithms which are inexpensive to execute in the networks' virtual-compute pricing ("gas") system. Notably, the connection between virtual-compute pricing and real world performance is tenuous, with the real-world performance differences between various computations sometimes deviating from their charged "gas" prices by greater than an order of magnitude. The dominance of constant-product market makers (CPMMs) are an observable result of this phenomenon, despite other known constructions being superior for certain use cases (e.g. logarithmic market scoring rules).

Stateless Validation Architecture

In contrast, this proposal preserves the superior user experience and scalability of Bitcoin Cash:

  1. Reliable user experience – users never pay for un-mined, "failed" transactions, user transactions cannot be re-ordered by miners without user consent (via deliberate participation in reorder-able contract schemes), and unconfirmed transactions can be chained such that earlier transactions are guaranteed to be mined if a later transaction in the chain is mined (enabling additional miner-abuse resistance and censorship-resistance strategies).
  2. No-fee contract deployment and superior real-world privacy – User wallets both “deploy” and “destroy” contracts incrementally as part of their usage, rather than calling monolithic, expensive-to-deploy, "global" contracts – improving both overall network throughput and real-world privacy.
  3. Reliably-low fees, even for complex contracts – The per-computation contract validation costs for Bitcoin Cash node operators are thousands of times lower than such costs for node operators in global-state architectures (like Ethereum); existing limits already offer significantly more computation to most Bitcoin Cash contracts than are available to contracts on global-state systems.

Minimal Impact of Compute on Node Operation Costs

In practice, computation costs of node operators are typically bounded for a given capacity, and actual utilization of computation has a relatively smaller impact on overall costs (e.g. electricity usage for a single system moving from 5% to 25% utilization). On the other hand, bandwidth and storage more commonly incur direct usage-based costs, with bandwidth commonly cited as the leading infrastructure cost of operation, followed by storage costs of increasing blockchain sizes (e.g. for archival nodes, indexers, and other Bitcoin Cash businesses and infrastructure operators).

Beyond preventing abusive contract constructions from creating denial-of-service risks to node operators by using orders of magnitude more computation than plausibly non-malicious contracts (see Selection of Hashing Limit and Risk Assessment: Denial of Service Risks) – Bitcoin Cash has no pressing need to measure computation in order to charge differing fees based on computation.

By design, this proposal reduces the overall worst-case computation costs of node operation, while significantly extending the universe of relatively inexpensive-to-validate contract constructions available to Bitcoin Cash contract developers. Further changes which might increase worst-case validation costs – like pay-for-compute schemes – are considered out-of-scope for this proposal (see Use of Input Length-Based Densities for details).

Non-Impact on "Data Storage" Costs and Incentives

This proposal intentionally avoids impacting the costs and incentives surrounding usage of transactions for storage of arbitrary (often non-financial) data with respect to 1) standard validation rules regarding OP_RETURN data carrier outputs, 2) standard validation rules regarding all other data-carrying transactions, and 3) computation-related "data storage" incentives indirectly resulting from all other transaction validation limits.

OP_RETURN Data Carrier Outputs

Following CHIP-2021-03-12 Multiple OP_RETURNs, data carrier outputs are currently limited to 223 cumulative bytes (including encoding overhead), with a maximum content of 220 bytes. While this constant appears to have been selected by mistake, it remains the primary limit to accessible, on-chain data storage with multiple existing indexers and other well-supported infrastructure. As increasing this limit could increase indexing and maintenance costs across a variety of ecosystem software and infrastructure, this proposal considers such increases to be out of scope.

Data-Carrying Transactions

Beyond the easily-accessible, well-indexed storage available via OP_RETURN data carrier outputs, the next meaningful limit on (less-accessible) data storage is the limit on maximum standard transaction length (A.K.A. MAX_STANDARD_TX_SIZE), currently 100,000 bytes. Up to this length, a variety of custom data storage protocols can be designed to pack data into transactions using a variety of constructions, with limits on individual inputs or push sizes exerting a minimal impact (generally less than 1%) on overall storage efficiency. Beyond 100,000 bytes, real-world costs discourage usage of on-chain storage for most kinds of applications. (Note also that Bitcoin Cash's existing practical limits to data-carrying transactions are either equivalent or more conservative than most other networks resulting from bitcoin splits, i.e. BTC, BSV, and XEC.)

This proposal has no impact on the potential usage or efficiency of data-carrying transactions. In practice, most applications would remain best served by storing data off-chain and committing only the hash of such data into on-chain transactions (particularly in common, infrastructure-supported OP_RETURN Data Carrier Outputs).

Indirect, Transaction "Padding" Incentives

This proposal reduces indirect incentives for existing contracts to increase overall blockchain storage usage.

Because the existing statically-defined limits create arbitrary (i.e. inconsistent with respect to performance requirements) partitions in evaluation of existing contracts – requiring computations to be split across multiple inputs – the net effect of this proposal on all existing contract usage is to eliminate overhead (e.g. additional transactions and/or per-input encoding overhead) which is currently required to work around the existing, per-contract evaluation limits. For all currently-possible contracts, this maintains or reduces resulting transaction sizes and overall blockchain data usage.

However, while this proposal's re-targeted limits allow sufficient room for most contract developers to work without any consideration for VM limits, a subset of currently-possible-but-impractical contracts warrants further review:

  • Within the existing limits, evaluations requiring high-density and/or high-precision arithmetic – e.g. emulation of post-quantum cryptography, zero-knowledge proofs, homomorphic encryption, etc. – must be split into multiple inputs, with intermediate results passed across evaluations to allow computation to continue (working around the existing limits). In practice, the excessive cost of contract development and security review limits production deployment of such multi-input systems. Worse, transactions resulting from such systems would require significant per-input and per-output overhead, reducing their efficiency and increasing their overall impact on blockchain storage usage.

  • It could be argued that this proposal (coupled with CHIP-2024-07-BigInt) creates an incentive for these currently-theoretical, arithmetic-dense contracts to "pad" their density control lengths with otherwise-unnecessary data in order to increase the maximum operation cost allocated to the input's evaluation. However, this argument reverses causation; in fact, these proposals so significantly reduce the overhead of arithmetic-dense contracts that many such contracts become efficient enough for realistic production development and deployment. (Note also that these are "economic use cases" related to securing or transacting BCH and/or CashTokens.1) In practice, these proposals produce an unequivocal improvement in the status quo with respect to overall blockchain storage efficiency, and they produce no meaningful change in the incentives surrounding "wasted" data usage. While further improvements are possible (see Rationale: Use of Input Length-Based Densities), this proposal considers further optimizations to be out of scope.

Notes

  1. Even presuming a value judgement that "economic use cases" ought to be prioritized above equally-fee-paying "data storage use cases" (a statement on which this proposal remains neutral), the contracts in question can only reasonably be considered "economic use cases":

    • The purpose of the Bitcoin Cash VM is to adjudicate asset transfer rights without a central authority (for both BCH and CashTokens).

    • In this context, "data storage use cases" might be defined as any use cases in which this adjudication is not used. I.e. instead of relying on the VM for rights adjudication (and by extension, on-chain control of assets), off-chain systems simply use the network as a censorship-resistant messaging layer. Though data storage use cases can technically use the VM in purely-ceremonial ways (e.g. pretending to perform the same on-chain computations as have taken place in the off-chain system), if a system's consensus is reliant on an off-chain protocol, there remains little difference between committing inputs-plus-computation or fully-computed results to the chain (primarily transaction fee efficiency, where committing computed results will be less expensive than committing inputs and ceremonially re-performing the computation on-chain).

    • In contrast, any use case which does require VM evaluation for adjudication of on-chain asset transfer rights (BCH and/or CashTokens), can only reasonably be described as an "economic use case", e.g. single-signature addresses, multi-party vaults, decentralized application treasuries, zero-knowledge proof covenants, sidechain bridges, etc. Within reasonable limits defined to protect network bandwidth, storage, or computation from abusive usage, further distinction between the qualifications of various VM-evaluated contracts as "economic" vs. "non-economic" becomes subjective/arbitrary.

Retention of Control Stack Limit

This proposal avoids modifying the existing practical limit on control stack depth by introducing a specific Control Stack Limit in place of the current effective limit1.

While it is possible to implement an O(1) Control Stack such that deeply nested conditionals have no impact on transaction validation performance, requiring this optimization in all performance-critical VM implementations may have significant consequences for future protocol complexity, particular if future upgrades extend the VM's control flow capabilities. (E.g. bounded loops, switch or match expressions, word/function definition, etc.)

The existing control stack depth of 100 is already far in excess of all known usage. Additionally, given both the availability of the alternate stack and this proposal's replacement of the operation limit, it is possible to emulate practically any algorithm requiring excessive control stack depth with an equivalent, less-deeply nested implementation. As such, an increase in the existing limit on control stack depth is considered out of this proposal's scope.

Notes
  1. The existing 201 operation limit prevents any currently-valid contract from requiring a control stack of depth greater than 100, e.g. <1> OP_IF <1> OP_IF <1> OP_IF ... OP_ENDIF OP_ENDIF OP_ENDIF.

Use of Input Length-Based Densities

This proposal limits both hashing and operation cost to maximum densities based on the approximate byte length of the input under evaluation (see Rationale: Selection of Input Length Formula).

As is currently required within the existing system of limits, contract systems requiring additional computation following activation of this proposal may continue to rearrange or break up expensive computations into multiple inputs. As this proposal attempts to avoid any impact to worst-case validation time – and future upgrades can deploy increases in operation cost limits – additional solutions for increasing per-input operation cost limits are considered out of this proposal's scope.

Alternative: Transaction Length-Based Densities

Alternatively, this proposal could measure densities relative to the byte length of the full containing transaction, sharing a budget across all of the transaction's inputs. Such a transaction-based approach would provide contracts with the most generous possible computation limits given the transaction fees paid, allowing computationally-expensive inputs to also claim the computing resources purchased via the bytes of transaction overhead, outputs, and of other inputs. Additionally, if a future upgrade were to relax output standardness, transaction-based budgets would also offer non-P2SH (Pay to Script Hash) contracts a greater portion of the computing resources purchased via the transaction's other bytes, particularly for contracts which rely mainly on introspection for validation and include little or no unlocking bytecode (e.g. the "Merge Threads" script in Jedex).

However, this proposal's input-based approach is superior in that it: 1) allows contract authors to reliably predict a contract's available limits regardless of the size and other contents of the spending transaction, 2) ensures that contract evaluations which do not exceed VM limits can be composed together in multi-input transactions without further regard for VM limits, 3) preserves the simplicity of parallelizing input validation without cross-thread communication, 4) more conservatively limits the worst-case validation performance of maliciously-invalid transactions (by failing the malicious transaction earlier), and 5) could be expanded into a transaction-based approach by a future upgrade if necessary.

Alternative: UTXO-Length Increased Densities

Another alternative to offer greater limits to non-P2SH contracts would be to base densities on the byte length of both locking and unlocking bytecode, i.e. including the Unspent Transaction Output (UTXO) in the input's budget. However, this alternative approach would increase the volatility of worst-case transaction validation performance: the price of the UTXO's past bandwidth is paid by the previous transaction's mining fee, while the price of the UTXO's storage is paid only by the time-value of associated dust; if compute resources aren't strictly tied to costs in the present (like the current transaction's mining fee), the instantaneous computation requirements of transaction validation are also not bounded by limits in the present (e.g. slow-to-validate UTXOs may be stored up and evaluated in a smaller number of attack transactions). Finally, depending on the precise economics of particular attacks, limits enhanced by UTXO length may incentivize would-be attackers to inflate the UTXO set in advance of an attempted denial-of-service attack, increasing its cost-effectiveness. Instead, this proposal bases computation limits only on costs paid in the present, with the 41-byte minimum input length providing a reasonable minimum computation budget.

Alternative: Transaction Fee-Increased Densities

Finally, this proposal could also increase the operation cost limit proportionally to the per-byte mining fee paid or based on the declaration of "virtual" bytes, e.g. for fee rates of 2 satoshis-per-real-byte, the VM could allow a per-byte budget of 2000 (a 2.5 multiple, incentivizing contracts to pay the higher fee rate rather than simply padding the unlocking bytecode length). However, any allowed increase in per-real-byte operation cost also equivalently changes the variability of per-byte worst-case transaction validation time; such flexibility would need to be conservatively capped and/or interact with the block size limit to ensure predictability of transaction and block validation requirements. Additionally, future research based on real-world usage may support simpler alternatives, e.g. a one-time increase in the per-byte operation cost budget.

Selection of Input Length Formula

The Density Control Length used by the Hashing and Operation Cost limits in this proposal approximates the encoded length of inputs by adding the length of the unlocking bytecode (A.K.A. scriptSig) to the constant 41: the minimum possible per-input overhead of version 1 and 2 transactions1. This approach both simplifies implementations – by avoiding the need to either check the length of the serialized input or compute its expected length – and simplifies some contract development and deployment concerns by avoiding the 2-byte change in available budget as contract length increases from 252 bytes (encoded as 0xfc) to 253 bytes (encoded as 0xfdfd00).

Additionally, by avoiding direct use of encoded input length in limit calculations, the selected formula avoids directly tying the application of VM limits to the encoding format of the containing transaction. This ensures that contracts designed for use in version 1 and 2 transactions may retain equivalent limits even if evaluated within future transaction version(s) that more efficiently encode transaction inputs.

Notes
  1. Outpoint Transaction Hash (32 bytes), Outpoint Index (4 bytes), Unlocking Bytecode Length (minimum 1 byte), Unlocking Bytecode, and Sequence Number (4 bytes): 32 + 4 + 1 + 4 = 41.

Hashing Limit by Digest Iterations

One possible alternative to the proposed Hashing Limit design is to limit evaluations to a fixed count of "bytes hashed" (rather than digest iterations). While this seems simpler, it performs poorly in an adversarial environment: an attacker can choose message sizes to minimize bytes hashed while maximizing digest iterations required (e.g. 1-byte messages).

In practice, because the performance cost of hashing a 55-byte message is equivalent to the performance cost of hashing a single-byte message, any hashing limit which fails to account for the internal block-digest behavior of the Merkle–Damgård hashing algorithm will be vulnerable to a 55x magnification in worst-case validation costs (see Digest Iteration Count).

By directly measuring digest iterations, non-malicious contracts can be allowed to evaluate a higher density of hashing operations without increasing the worst-case validation requirements of the VM as it existed prior to this proposal.

Selection of Hashing Limit

This proposal sets the standard (transaction relay policy) hashing density limit at 0.5 digest iterations per spending input byte. This value is the asymptotic maximum density of hashing operations in plausibly non-malicious, standard transactions within the current VM limits and instruction set: assuming no transaction encoding overhead and that all hashed material is maximally-padded (1-byte segments), the most efficient methods for reducing hashed material into a single result (without any further processing) requires 1 additional operation (e.g. OP_CAT) per hashing operation1.

Note that this standard limit is also well in excess of the highest density found in any standard transaction maximizing hashing within signature checking operations: 0.30 digest iterations per byte2.

For block validation, this proposal sets the consensus limit (A.K.A. "nonstandard") hashing density at 3.5 digest iterations per spending input byte. This limit exceeds the highest-known density of any currently standard transaction of 3.44 digest iterations per byte3. Ideally, a separate nonstandard limit could be avoided, but because currently-standard transactions can be designed to exceed the 0.5 limit, a higher nonstandard limit is necessary to avoid immediately invaliding any currently-standard transactions4. Future proposals could schedule an upgrade to consolidate these limits.

Alternatively, this proposal could set a consensus hashing limit without a lower standardness limit. However, hashing cannot be reliably deferred like signature validation; because the current practical limit is nearly an order of magnitude higher then theoretically useful, limiting the density allowed in standard validation significantly improves worst-case validation performance.

Notes
  1. The two-round hashing operations (OP_HASH160 and OP_HASH256) would be wasteful in this idealized scenario, as 1-byte inputs already require padding in the first round of hashing, so the idealized maximum density is 1 digest iteration per 2 opcodes. Note that while a future upgrade could increase this density by compressing the evaluating code (e.g. with bounded loops) or allowing significant lengths of hashed material to be provided via UTXO bytecode (e.g. by relaxing output standardness), this example still 1) excludes the minimum 41 bytes of input overhead (allowing up to 1271 bytes hashed in 20 hash digest iterations), 2) significantly overestimates hashing density by assuming exclusively 1-byte input lengths rather than more common lengths (e.g. 20 or 32), and 3) excludes overhead from the non-hashing operations performed in realistic contracts.
  2. See benchmark xfszef.
  3. See benchmark lcennk.
  4. This proposal follows the long-established process of restraining abusive usage by invalidating currently-standard malicious behavior via relay policy (A.K.A. "standardness"), and then only restricting the behavior from block validation (A.K.A. "consensus") after it has remained restricted for a significant period of time (e.g. NULLDUMMY, NULLFAIL, MINIMALDATA, etc.).

Stateless Costing of Signing Serialization Hashing

This proposal accounts for the cost of hashing all signing serializations by incrementing the spending transaction input's cumulative hash digest iteration count prior to incrementing the signature check count (A.K.A. SigChecks), regardless of whether a previous signature check used the same signing serialization. This avoids creating a requirement for all implementations to track previously-used signing serializations across signature checks; while some implementations may cache and reuse signing serialization digests, other implementations may reasonably re-hash all signing serializations.

Exclusion of Signing Serialization Components from Hashing Limit

This proposal includes the cost of hashing all signing serializations in the proposed Hashing Limit, but it excludes the cost of any hashing required to produce the internal components of signing serializations (i.e. hashPrevouts, hashUtxos, hashSequence, and hashOutputs). This configuration reduces protocol complexity while correctly accounting for the real-world hashing cost of coveredBytecode (A.K.A. scriptCode), particularly in preventing abuse of OP_CODESEPARATOR, future increases to maximum standard unlocking bytecode length (A.K.A. MAX_TX_IN_SCRIPT_SIG_SIZE – 1,650 bytes), and/or increases to consensus-maximum VM bytecode length (A.K.A. MAX_SCRIPT_SIZE – 10,000 bytes).

Alternatively, this proposal could also require internally accounting for the cost of hashing within signing serialization components. However, because components can be cached across signature checks – and for hashPrevouts, hashUtxos, hashSequence, across the entire transaction validation – such costs would need to be amortized across all of a transaction's signature checks to approximate their fixed, real-world cost. As signature checking is already sufficiently limited by SigChecks and operation cost, omitting hash digest iteration counting of signing serialization components reduces unnecessary protocol complexity.

Ongoing Value of OP_CODESEPARATOR Operation

The OP_CODESEPARATOR operation modifies the signing serialization (A.K.A. "SIGHASH" preimage) used in later-executed signature operations by truncating the coveredBytecode component at the index of the last executed OP_CODESEPARATOR operation.

The OP_CODESEPARATOR behavior is useful for designing contracts in which a single key may provide signatures for use in multiple contract code paths. Without OP_CODESEPARATOR, a valid signature by the key could be re-used by an attacker in a manipulated version of the input's unlocking bytecode to unlock the contract following a different code path; if OP_CODESEPARATOR is executed at some point before any later signature checking operation, a valid signature for the intended code path will fail validation if the unlocking bytecode is manipulated to follow another code path.

Notably, the behavior of OP_CODESEPARATOR can be achieved more directly with OP_CHECKDATASIG: for each code path, the locking bytecode must simply require a different message to be signed by the data signature, preventing signatures from being reused across code paths. However, OP_CODESEPARATOR can be more byte-efficient in that it requires only one additional byte (the OP_CODESEPARATOR instruction) to differentiate the two signature preimages, while OP_CHECKDATASIG may require additional instructions or encoded data to differentiate each possible message.

While past proposals (for both Bitcoin Cash and similar networks) have called for deprecating or disabling OP_CODESEPARATOR, this proposal retains the feature while preventing excessive resource consumption, as OP_CODESEPARATOR is already available in the Bitcoin Cash instruction set, may have active users, and remains useful in some scenarios.

Increased Usability of Multisig Stack Clearing

Prior to this proposal, the multisig operations (OP_CHECKMULTISIG and OP_CHECKMULTISIGVERIFY) were limited in part via incrementing the operation count by the number of stack items provided as public keys. However, because public keys are only validated prior to their use in a signature check, it is also possible to use these operations to more efficiently drop items from the stack than via repeated calls to OP_DROP, OP_2DROP, or OP_NIP.

While this eccentric behavior was likely unintentional, it has been available to contract authors since Bitcoin Cash's 2009 launch, and it is generally the most byte-efficient method of dropping between 9 and 20 stack items (reducing transaction sizes for some contracts). Because this existing stack-clearing behavior is a useful feature and does not meaningfully impact transaction validation costs, this proposal treats zero-signature multisig operations equivalently to all other constant and linear time operations.

Limitation of Pushed Bytes

This proposal limits the density of both memory usage and computation by limiting bytes pushed to the stack to approximately 700 per spending input byte (the per-byte budget of 800 minus the base instruction cost of 100).

Because stack-pushed bytes become inputs to other operations, limiting the overall density of pushed bytes is the most comprehensive method of limiting all sub-linear and linear-time operations (bitwise operations, VM number decoding, OP_DUP, OP_EQUAL, OP_REVERSEBYTES, etc.); this approach increases safety by reducing the risk that any unexpected source of linear time complexity (e.g. due to a defect in a particular VM implementation) might create practically-exploitable performance issues (providing defense in depth) and reduces protocol complexity by avoiding special accounting for all but the most expensive operations (arithmetic, hashing, and signature checking).

Additionally, this proposal’s density-based limit caps the maximum memory and memory bandwidth requirements of validating a large stream of transactions, regardless of the number of parallel validations being performed1.

Alternatively, this proposal could limit memory usage by continuously tracking total stack usage and enforcing some maximum limit. In addition to increasing implementation complexity (e.g. performant implementations would require a usage-tracking stack), this approach would 1) implicitly limit memory bandwidth usage and 2) require additional limitations on linear-time operations.

Notes
  1. While the 10KB stack item length limit and 1000 item stack depth limit effectively limit maximum memory to 10MB plus overhead per validating thread, without additional limits on writing, memory bandwidth can become a bottleneck. This is particularly critical if future upgrades allow for increased contract or stack item lengths, bounded loops, word/function definition, and/or other features that reduce transaction sizes by increasing their operation density.

Unification of Limits into Operation Cost

While this proposal maintains independent limits for both signature checking and hashing (via SigChecks and hash digest iterations, respectively), the measurements used to enforce each limit also contribute to the unified Operation Cost Limit. This configuration prevents maliciously designed transactions from maximizing validation cost across multiple disparate limits, reducing the potential disparity in worst case performance between honest and malicious usage.

Selection of Operation Cost Limit

This proposal sets the operation cost density at 800 per spending input byte. Given a base instruction cost of 100, this density ensures a net budget of 700 per spending input byte, a constant rounded up from the maximum effective limit prior to this proposal1.

Notes
  1. Benchmark d0kxwp (99966 bytes) pushes 62757175 bytes, approximately 627.79 bytes per spending input byte.

Selection of Base Instruction Cost

To retain a conservative limit on contract operation density, this proposal sets a base operation cost of 100 per evaluated instruction, including unexecuted and push operations.

Given the operation cost density limit of 800, a base instruction cost of 100 ensures that the maximum operation density within spending inputs (8 per byte) remains within an order of magnitude of the current effective limit (approximately 1 per byte) resulting from the 201 operation limit.

Because base instruction cost can be reduced - but not increased - in future upgrades without invalidating contracts1, a base cost of 100 is more conservative than lower values (like 10, 1, or 0). Additionally, a relatively-high base instruction cost leaves room for future upgrades to differentiate the costs of existing low and fixed-cost instructions, if necessary.

Alternatively, this proposal could omit any base instruction cost, limiting the cost of all instructions to their impact on the stack. However, instruction evaluation is not costless – a nonzero base cost properly accounts for the real world overhead of evaluating an instruction and verifying non-violation of applicable limits.

Finally, setting an explicit base instruction cost reduces the VM’s implicit reliance on bytecode length for limiting worst case validation performance. By explicitly limiting maximum operation density, future upgrades which increase the maximum allowable contract length or reduce transaction sizes by compressing contract code (e.g. bounded loops or word/function definition) can be supported without incurring technical debt and/or producing de facto limit increases.

Notes
  1. Note that pre-signed transactions, contract systems, and protocols can be specifically designed to operate on any observable characteristic of the VM, including limits. See Notice of Possible Future Expansion.

Inclusion of Numeric Encoding in Operation Costs

The VM number format is designed to allow efficient manipulation of arbitrary-precision integers (Satoshi's initial VM implementation used the OpenSSL library's Multiple-Precision Integer format and operations), so sufficiently-optimized VM implementations can theoretically avoid the overhead of decoding and (re)encoding VM numbers. However, if this proposal were to assume zero operation cost for encoding/decoding, this optimization would be required of all performance-critical VM implementations to avoid divergence of real performance from measured operation cost.

Instead, this proposal increments the operation cost of all operations dealing with potentially-large numbers (greater than 2**32) by the byte length of their numeric output (in effect, doubling the cost of pushing the output). This approach accounts for the cost of re-encoding numerical results from another internal representation as VM numbers – regardless of the underlying arithmetic implementation. (Note that the cost of decoding VM number inputs is already accounted for (in advance) by the comprehensive limiting of pushed bytes. See Rationale: Limitation of Pushed Bytes.)

Because operation cost can be reduced - but not increased - in future upgrades without invalidating contracts1, this proposal's approach is considered more conservative than omitting a cost for re-encoding.

Notes
  1. Note that pre-signed transactions, contract systems, and protocols can be specifically designed to operate on any observable characteristic of the VM, including limits. See Notice of Possible Future Expansion.

Selection of Signature Verification Operation Cost

In addition to the operation cost of hash digest iterations performed within signature checking operations, this proposal sets the operation cost of signature verification to 26000 per check. This constant is rounded down from the per-check budget available within current limits1.

By deriving this limit to be practically equivalent - but slightly more generous - than the existing SigChecks limit, this proposal ensures that all currently-standard transactions remain valid, while avoiding any significant increase in worst case validation performance vs. current limits.

Note that because Schnorr signatures can be batch validated, this proposal could reasonably have set another, lower cost for such signatures. However, as signature validation is generally the bottleneck in worst case validation performance of currently-standard transactions, it may be prudent to avoid extending higher limits for Schnorr signatures and to instead allow any such performance gains to simply improve average validation performance.

Additionally, for contracts to take advantage of any such operation cost discount for Schnorr signatures, the separate SigChecks limits would likely also need to be loosened for Schnorr signatures, and in both cases, a differentiated limit would essentially required all VM implementations to implement the batch verification optimization to avoid negatively impacting worst case performance.

Given these trade-offs, this proposal takes the more conservative approach of applying a fixed operation cost per signature check based only on the existing, worst case scenario.

Notes
  1. Given the SigChecks standardness limit of 1 check per 33.5 bytes and a per-byte operation budget of 800, the current implied cost of a signature check is 26800 (33.5 * 800 = 26800). Benchmark l0fhm3 (Within BCH_2023_05 standard limits, packed 1-of-3 bare multisig inputs, 1 output (all ECDSA signatures, first slot)) demonstrates transaction validation performance similar to a worst-case scenario for this metric – it contains 2619 signature checks in 99988 bytes (262-byte signing serializations; 5 hash digest iterations per signature check), with a standard cost of 3867390 before accounting for signature checks and a remaining budget of approximately 28105 per signature check (((99988 * 800) - 3867390 - (2619 * 5 * 192)) / 2619 ~= 28105.68).

Continued Availability of Deferred Signature Validation

By using the existing SigCheck metric in computing operation cost, this proposal retains the ability to defer signature validation (as described in the 2020-05 SigChecks specification) until the rest of a contract has been evaluated. Notably, enforcement of the proposed hashing limit within signature checking operations can also be deferred until immediately prior to signature validation, though because other hashing operations must be evaluated during program execution, deferring either hashing or digest iteration estimation will not improve worst-case validation performance.

Selection of Hash Digest Iteration Cost

For block validation (consensus), this proposal sets the operation cost of hash digest iterations to 64 (the hashing algorithm block size); for transaction relay (standardness policy) this proposal sets the operation cost of hash digest iterations to 192 (64*3=192). These values ensure that all possible standard transactions remain valid by consensus while accounting for the cost of hashing during standard validation.

Each VM-supported hashing algorithm – RIPEMD-160, SHA-1, and SHA-256 – uses a Merkle–Damgård construction with a block size of 512 bits (64 bytes); operation cost is essentially a count of bytes processed by any VM operation, so the hashing algorithm block size (64) is the most appropriate multiple upon which to base hashing operation cost calculations.

Under the existing limits, the highest possible hashing density of a standard transaction is 3.44 hash digest iterations per spending input byte1. Given a budget of 800 per byte, it is not possible to set a higher multiple of 64 for the consensus operation cost of hash digest iterations (e.g. 128) without invalidating currently-standard transactions2. As such, this proposal sets the consensus operation cost of hash digest iterations to 64.

To determine the standard operation cost of hash digest iterations, the results of multiple representative benchmarks can be compared across multiple independent VM implementations; in a variety of cases, given a signature checking cost of 26000, the closest multiple of 64 to real-world performance cost is 1923.

Notes
  1. Benchmark lcennk.
  2. For example, benchmark lcennk (99966 bytes) with a hash digest iteration cost of 128 results in a cumulative operation cost of 87910420, or 879.40 per byte.
  3. On one representative system, Bitcoin Cash Node (BCHN), performs the baseline benchmark (trxhzt) at 11759.3 Hz (2 sigchecks and 12 iterations) and a hashing-heavy benchmark (lcennk) at 10.6 Hz (0 sigchecks and 344162 iterations). Given 11759.3 (2s + 12h) = 10.6 (344162h), each signature check costs about 149 hash digest iterations; calibrating for a signature check cost of 26000, 26000 / 149.12 ~= 174, the measured cost per digest iteration is approximately 174. Likewise, Libauth, an unrelated JavaScript implementation using WebAssembly-based, software-only implementations of the relevant cryptographic algorithms, performs trxhzt at 2966.08 Hz and lcennk at 2.56 Hz. Given 2966.08 (2s + 12h) = 2.56 (344162h), each signature check costs about 142 hash digest iterations; calibrating for a signature check cost of 26000, 26000 / 142.52 ~= 182, the measured cost per digest iteration is approximately 182.

Inclusion of "Notice of Possible Future Expansion"

This proposal includes a Notice of Possible Future Expansion to clarify established precedent in Bitcoin (Cash) protocol development: pre-signed transactions, contract systems, and protocols which rely on the non-existence of VM features must be interpreted as intentional. This precedent was established by Satoshi Nakamoto in reverted makefile.unix wx-config -- version 0.3.6 (July 29, 2010) with the addition of new opcodes OP_NOP1 to OP_NOP10, and the precedent was reaffirmed by numerous upgrades to Bitcoin (Cash), e.g. OP_CHECKLOCKTIMEVERIFY, Relative locktime, OP_CHECKSEQUENCEVERIFY, the 2018 opcode restoration, CHIP-2021-03: Bigger Script Integers, and other upgrades.