Skip to content

Latest commit

 

History

History
244 lines (166 loc) · 11.4 KB

readme.md

File metadata and controls

244 lines (166 loc) · 11.4 KB

CHIP-2021-05-loops: Bounded Looping Operations

    Title: Bounded Looping Operations
    Type: Standards
    Layer: Consensus
    Maintainer: Jason Dreyzehner
    Status: Draft
    Initial Publication Date: 2021-05-28
    Latest Revision Date: 2024-12-18
    Version: 1.2.0

Summary

This proposal adds two new BCH virtual machine (VM) operations, OP_BEGIN and OP_UNTIL, enabling a variety of loop constructions in BCH contracts without increasing the processing or memory requirements of the VM.

Deployment

Deployment of this specification is proposed for the May 2026 upgrade.

  • Activation is proposed for 1763208000 MTP, (2025-11-15T12:00:00.000Z) on chipnet.
  • Activation is proposed for 1778846400 MTP, (2026-05-15T12:00:00.000Z) on the BCH network (mainnet), testnet3, testnet4, and scalenet.

Motivation

The Bitcoin Cash VM is strictly limited to prevent maliciously-designed transactions from requiring excessive resources during transaction validation.

Loops were originally excluded from the VM design as part of an initial, anti-Denial-of-Service approach. However, despite the "no loops" approach being quietly abandoned for explicit limits (reverted makefile.unix wx-config -- version 0.3.6 – July 29, 2010), the Bitcoin Cash VM is still missing this basic control flow structure, creating significant waste in many contracts by requiring duplication of contract bytecode.

This proposal adds the well-established, OP_BEGIN/OP_UNTIL loop construction used by most Forth-like languages, making BCH contracts significantly more powerful and efficient.

Benefits

Looping operations enable many use cases where specifying a precise procedure using OP_IF is impractical or impossible, and they also significantly reduce the bytecode length of many contracts with repeated procedures.

Costs & Risk Mitigation

The following costs and risks have been assessed.

Modification to Transaction Validation

Without adequate limits, looping operations have the potential to increase worst-case transaction validation costs and expose VM implementations to Denial of Service (DOS) attacks.

Following CHIP 2021-05 VM Limits, the Bitcoin Cash VM consistently prevents abuse of all VM operations via density-based limits. Accordingly, new flow control structures cannot magnify worst-case validation performance – all constructions made more concise by this proposal are equivalently limited to a corresponding degree across each of the VM's existing abuse prevention metrics. (Note also that this proposal was specifically reviewed as part of the VM Limits CHIP: Risk Assessment.)

Additionally, this proposal includes new test vectors covering both functional behavior and worst-case validation performance (across both standard and nonstandard validation).

Node Upgrade Costs

This proposal affects consensus – all fully-validating node software must implement these VM changes to remain in consensus.

These VM changes are backwards-compatible: all past and currently-possible transactions remain valid under these new rules.

Ecosystem Upgrade Costs

Because this proposal only affects internals of the VM, standard wallets, block explorers, and other services will not require software modifications for these changes. Only software which offers VM evaluation (e.g. Bitauth IDE) will be required to upgrade.

Wallets and other services may optionally upgrade to add support for new contracts which will become possible after deployment of this proposal.

Technical Specification

Two new VM operations are added: OP_BEGIN (0x65/101) and OP_UNTIL (0x66/102).

Note: these codepoints were previously used by OP_VERIF (0x65) and OP_VERNOTIF (0x66) in early versions of Bitcoin, but those operations were disabled when it was realized that they created a fork-risk between different versions of the Bitcoin software. Both codepoints currently render the transaction invalid (even when found in an unexecuted OP_IF branch), so they are effectively equivalent to any codepoints in the undefined ranges. They are particularly well-suited for this application because they are the only two available, adjacent codepoints within the control-flow range of operations.

To support these operations, the control stack is modified to support integer values.

Control Stack

This proposal modifies the control stack (A.K.A. ExecStack or ConditionStack) to support integer values. When testing for operation execution, integer values must be ignored.

Prior to this proposal, the control stack (A.K.A. ExecStack or ConditionStack) is conceptually an array of boolean values: when a flow control operation (like OP_IF) is encountered, a true is pushed to the stack if the branch is to be executed, and false if not. (OP_ELSE toggles the top value on this stack.) Non-flow control operations are only evaluated if the control stack contains no false values.

OP_BEGIN (0x65/101)

OP_BEGIN pushes the current instruction pointer index to the control stack (A.K.A. ConditionStack).

This operation sets a pointer to which the evaluation will return when the matching OP_UNTIL is encountered. If a matching OP_UNTIL is never encountered, the evaluation returns an error.

OP_UNTIL (0x66/102)

OP_UNTIL pops the top item from the control stack:

  • If this control value is not an integer, error.
  • The top item is popped from the stack, if the value is 0 (the same test as OP_NOTIF) the instruction pointer is set to the OP_BEGIN instruction (otherwise, evaluation continues past the OP_UNTIL).

Rationale

This section documents design decisions made in this specification.

Naming and Semantics

This proposal is influenced by the BEGIN ... UNTIL indefinite loop construction in the Forth programming language (upon which the rest of the Bitcoin Cash VM is based). This particular construction offers maximal flexibility: definite loops can be easily emulated with indefinite loops, but indefinite loops cannot be emulated with definite loops.

Suitability in Covenant Applications

One alternative to the proposed OP_BEGIN ... OP_UNTIL construction could be a single OP_GOTO operation which (with certain limits) jumps to the instruction pointer at the top of the stack.

While such an operation could help to further increase the efficiency and expressiveness of the BCH instruction set, a GOTO instruction also makes modeling execution more difficult. This is particularly limiting for covenant applications – it is notably more difficult for covenants to keep track of expected instruction pointer indexes (to reconstruct contracts with hypothetical OP_GOTO operations) than it is for them to use this proposal's construction.

The higher-level OP_BEGIN ... OP_UNTIL construction also better matches the semantics of the existing VM instruction set (e.g. OP_IF ... OP_ENDIF).

Usage Examples

The following examples demonstrate usage of OP_BEGIN and OP_UNTIL.

Simplifying Repeated Procedures

Bounded loops reduce wasted bytes in repeated procedures like merkle proof validation.

Merkle trees offer a versatile data structure for storing state in BCH contracts. Below is one possible strategy for validating a merkle proof (shown validating the left-most element in a tree of 16 elements):

<sibling_tier_4_hash>
<sibling_tier_3_hash>
<sibling_tier_2_hash>
<sibling_leaf_hash>
<value>
<1> OP_TOALTSTACK
<1> OP_TOALTSTACK
<1> OP_TOALTSTACK
<1> OP_TOALTSTACK

OP_FROMALTSTACK // check if leaf requires swap
OP_IF OP_SWAP OP_ENDIF
OP_CAT OP_HASH256

OP_FROMALTSTACK // check if tier 2 requires swap
OP_IF OP_SWAP OP_ENDIF
OP_CAT OP_HASH256

OP_FROMALTSTACK // check if tier 3 requires swap
OP_IF OP_SWAP OP_ENDIF
OP_CAT OP_HASH256

OP_FROMALTSTACK // check if tier 4 requires swap
OP_IF OP_SWAP OP_ENDIF
OP_CAT OP_HASH256

<root> OP_EQUALVERIFY

With bounded loops, this procedure can be simplified to:

<sibling_tier_4_hash>
<sibling_tier_3_hash>
<sibling_tier_2_hash>
<sibling_leaf_hash>
<value>
<0> OP_TOALTSTACK
<1> OP_TOALTSTACK
<1> OP_TOALTSTACK
<1> OP_TOALTSTACK
<1>

OP_BEGIN
  OP_IF OP_SWAP OP_ENDIF // check if leaf requires swap
  OP_CAT OP_HASH256
  OP_FROMALTSTACK
OP_UNTIL

<root> OP_EQUALVERIFY

Aggregation

Without bounded loops, contracts are forced to emulate aggregation by re-specifying a particular aggregation procedure for each possible set size.

For example, to aggregate the UTXO value of each transaction input without bounded loops (for up to 4 inputs using transaction introspection operations):

<0> // aggregated value
<4> // the count of values to aggregate

// locking bytecode
OP_DUP OP_TXINPUTCOUNT OP_LESSTHANOREQUAL OP_VERIFY // prevent malleability
OP_1SUB OP_DUP <0> OP_GREATERTHANOREQUAL OP_IF
    OP_SWAP
    <0> OP_UTXOVALUE
    OP_ADD
    OP_SWAP
OP_ENDIF
OP_1SUB OP_DUP <0> OP_GREATERTHANOREQUAL OP_IF
    OP_SWAP
    <1> OP_UTXOVALUE
    OP_ADD
    OP_SWAP
OP_ENDIF
OP_1SUB OP_DUP <0> OP_GREATERTHANOREQUAL OP_IF
    OP_SWAP
    <2> OP_UTXOVALUE
    OP_ADD
    OP_SWAP
OP_ENDIF
OP_1SUB OP_DUP <0> OP_GREATERTHANOREQUAL OP_IF
    OP_SWAP
    <3> OP_UTXOVALUE
    OP_ADD
    OP_SWAP
OP_ENDIF
OP_DROP // drop remaining index, leaving aggregated value on top

With bounded loops, this aggregation can be simplified to:

<0> <0>
OP_BEGIN                            // Loop (re)starts with index, value
  OP_OVER OP_UTXOVALUE OP_ADD       // Add UTXO value at index to total
  OP_SWAP OP_1ADD OP_SWAP           // Increment index
  OP_OVER OP_TXINPUTCOUNT OP_EQUAL
OP_UNTIL                            // Loop until index equals the TX input count
OP_NIP                              // Drop index, leaving sum of UTXO values

Implementations

Please see the following implementations for additional examples and test vectors:

Feedback & Reviews

Changelog

This section summarizes the evolution of this document.

  • v1.2.0 (current)
    • Re-propose for 2026
    • Eliminate Repeated Bytes counter (#5)
  • v1.1.0 – 2021-06-10 (d1406b69)
    • Correct OP_UNTIL to complete on truthy values
  • v1.0.0 – 2021-05-27 (d1406b69)
    • Initial publication

Copyright

This document is placed in the public domain.