CHIP 2021-05 Bounded Looping Operations

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

Loops were originally excluded from this design on the mistaken assumption that they risk consuming excessive validation resources. In reality, a small number of VM operations make up the majority of resource usage during transaction validation, and any implementation of bounded loops can be many orders of magnitude faster than the most pathological VM bytecode constructions.

Introducing this basic control flow structure would make BCH contracts significantly more powerful and efficient.


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

The precise implementation 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 these indefinite loops, but indefinite loops could not be emulated with definite loops.

Review and feedback are appreciated!

3 Likes

I support this improvement. Pretty close to what I had argued for when Bitcoin’s forth-like VM was first announced. Bounded non-determinism rather than unlimited Turing completeness. No need for gas. All leaving this out did was create huge transactions for unrolled fixed loops and eliminate any chance for flexible but safe dynamic runtime logic.

1 Like

I see there are some example cases in the CHIP around how this may be used.

What I did not find mentioned (maybe I overlooked something) is mention of looping – possibly with nesting – of some expensive operations like signature verifications, possibly in some degenerate scripts which may be small in terms of script size, run fine (even within the bounds of REPEATED_BYTES) but take a long time to execute and hence pose a new risk if they are not easily spotted ahead of execution time…

At the moment we have a transaction’s size as a proxy for its complexity – sigops which skew this are already subject to separate regulations. This makes is somewhat easier to spot potential “troublemakers”.

I think loops could pose a difficulty for keeping script verification performance well scalable (i.e. open up new DoS vectors) if they are not screened with some care.
Certainly this seems like a juicy CHIP to review in terms of possible pathologies.

Doesn’t this solve the issues you described? SigChecks protection Protocol Upgrade

4 Likes

At first glance, I think it would solve it for signature checks, yes. Thanks Tom.

2 Likes

Yes counting the difference in position between the begin/until against total script size limits (which actually penalizes code within the loop that may perform if branches) is a vastly cheaper method of cost accounting transaction executions than gas. Elegant and simple to implement. This is a really powerful improvement to bitcoinscript that only has upside in terms of expressiveness and physical tx size savings.

4 Likes