CHIP 2021-05 Bounded Looping Operations

[bitjson]

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.

bitjson/bch-loops

Review and feedback are appreciated!

[proteusguy]

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.

[freetrader]

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.

[tom]

@freetrader

but take a long time to execute and hence pose a new risk if they are not easily spotted ahead of execution time…

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

[freetrader]

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

[proteusguy]

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.

[bitcoincashautist]

Great work! This proposal is well thought out and allows much more utility without significantly increasing node operating costs, and it would be great if it could make it into 2023 or 2024 upgrade window. Clever way to limit the “damage” by essentially interpreting it as a macro, it can’t expand to more than the equivalent “manual” looping 10,000b script. Paired with hash counter of the other CHIP, I think we can unlock a lot of utility at negligible or even 0 expense.

[MathieuG]

I think bounded loops would be a very nice addition to the BCH VM!
Now that Bitcoin Cash scriptability has become much more powerful with CashTokens it would be good to document the practical needs for “Simplifying Repeated Procedures” like merkle proof validation and “Aggregation” like aggregating value of all inputs. This way we can better understand its practical relevancy.

For example the workaround for a person adding multiple UTXOs to a smart contract and the contract aggregating the input values would be a simple consolidation beforehand. We already see this type of “consolidate UTXOs” button used for the Paytaca browser extension. Only In the case where the added inputs are controlled by different parties would this not be possible.

Any practical & pressing needs for merkle validation would also be good to be documented. Merkle root validation was an important part of pmv3 tokenization but luckily that complexity was avoided by the CashTokens CHIP which replaced it.

[MathieuG]

It the research topic “The need for additional Math opcodes” @bitcoincashautist discussed how bounded loops can be used to emulate missing math opcodes like pow & log.

@bitcoincashautist

AFAIK implementation of integer pow/log is just some arithmetic & bit shift ops, inside some bounded loops, shouldn’t stick out as more expensive than some other opcodes.

Further in the topic it was discussed how bounded loops could be used to emulate higher order division together with op_muldiv

@bitcoincashautist

Division part is the big problem, it needs a bounded loop - worst case it would need 63 iterations. With higher limits CHIP the loop could be unrolled, and implementing it with Script would be quite expensive, lots of bytecode just to perform a single muldiv - an operation we can expect will be common.

So although there’s no pressing need for aggregation/merkle root validation, bounded loops enable emulating opcodes like pow & log and enable higher precision math division (uint126)