Improve utility of script calculations - larger numbers + op_mul

emergent_reasons · May 18, 2020, 1:34pm

Having larger numbers in script will simplify scripts[1] involving arbitrary satoshi amounts and other calculations. Perhaps even more importantly, it will make those scripts safer where the scripts are currently required to use additional artificial calculation techniques[2]. It is possible that it will increase the number of use cases as well, for example where artificial calculation techniques may not cover all needs or may be impossible to fit in script size limits.

Making op_mul available will have similar benefits by allowing multiplication instead of workarounds involving division or artificial calculation techniques.

The combination of larger integers and op_mul can be seen as a set that completes the basic calculation capability of Bitcoin Cash script. If they should be separated, I will remove op_mul from this topic.

I think this topic deserves discussion and evidence around:

Benefits and risks of different sizes (64, 128, 256, 512, …, bignum, other?) from a scripting safety and complexity perspective.
Benefits and risks of different sizes from an implementation perspective.
Desired behavior with respect to overflow.
Desired behavior of op_mul.
Should everything be done in one step, or should it be more than one to get to the end result?

[1] Two specific examples of use cases that would benefit from increased simplicity and safety:

Mecenas, etc. scripts created by @Licho (predicting username here) and others are limited to about 20 BCH in the best case.
The majority of complexity in AnyHedge contract is truncation math to get around the 31-bit positive integer limitation and retain precision. An alternative 60-bit math technique created by @Tobias_Ruck would solve the precision better, but still the vast majority of complexity would be a workaround for the 31-bit positive integer limitation.

[2] Artificial calculation techniques

As linked above, 60-bit math technique created by @Tobias_Ruck
Also as linked above, truncation math and precision recovery

Tobias_Ruck · May 20, 2020, 3:30pm

Relevant here is the proposal I made for 128-bit integers:

github.com

EyeOfPython/bitcoincash.org/blob/int128/spec/int128.md

---
layout: specification
title: 2020-NOV-15 128-bit integer specification
date: 2020-01-14
activation: 2020-NOV-15
version: 1.0
author: Tobias Ruck
---

# Summary
All arithmetic operations in Script (see below for an exhaustive list) will be able to work with 128-bit signed integers for Pay-To-Script-Hash inputs, ranging from `-0x7fff'ffff'ffff'ffff'ffff'ffff'ffff'ffff` to `0x7fff'ffff'ffff'ffff'ffff'ffff'ffff'ffff`. Any input or output outside of this boundary will cause the execution of the script to fail.

Further, the opcode `OP_MUL` will be re-enabled.

# Background
Currently, Bitcoin Script on the Bitcoin Cash blockchain limits integers to 32-bit signed integers, with values ranging from `-0x7fff'ffff` to `0x7fff'ffff`.

This is severely limiting, if we consider the following facts:
* Values locked in UTXOs are 64-bit unsigned integers.
* SLP values are 64-bit unsigned integers.

This file has been truncated. show original

markblundeberg · August 9, 2020, 8:53am

Thanks for starting this topic, and thanks Tobias for the excellent work writing a spec and running benchmarks. I am surprised that the 128 bit math is that slow. This seems to give an argument for only going to 64-bit at first, since C++ implementations have access to e.g. __builtin_smulll_overflow that on x86-64 does two opcodes – multiply and branch. The idea of limiting to P2SH is very interesting, though I feel like a generalized ‘cost-accounting’ approach (possibly merging sigchecks & other CPU-consuming metrics) would serve better in the long run.

tom · August 9, 2020, 11:16am

I think most people don’t realize that todays Script operators are hardcoded to use 4-byte math (i.e. 32 bit). Which is really quite small. I only was told this a couple of days ago as I never really paid attention to script before.

64 bits is used to encode the ‘amount’ fields (in satoshi) for instance.

This little detail was missing from this thread so far and in my opinion is a good problem statement that makes it easy to convince almost all devs.

emergent_reasons · August 9, 2020, 2:54pm

Thanks for focusing on this specific issue. Just for reference, it’s even slightly worse than it sounds for general satoshi calculations since it’s 32 bit signed. We are writing up some details about specific use cases that are broken or enabled by larger integers and multiplication.

markblundeberg · August 16, 2020, 11:13pm

So, one interesting plan would be as follows:

Update to 1+63 bit math and OP_MUL. Change all overflow handling to reject overflow on output. This way, implementations can use fast 64-bit checked math that is native to current CPUs.
In future, expand to larger numbers (1+255 or 1+256 bit?) and regulate big-number arithmetic operations by counting them as partial SigChecks. We would probably want to rename and rescale the sigchecks. I’m not sure what calibration values would be desired, but I expect any reasonable values would be far from causing any reasonable smart contracts from running into a sigchecks limit.

emergent_reasons · August 17, 2020, 2:25am

If that does not reduce the chances of a future better upgrade, that would be nice. If 128 is effectively as easy as 64 as a first step, then that would be much better for contracts like AnyHedge.

Regarding the cost, rather than overloading sigchecks, do you think it might be a good time to consider a script accounting mechanism that would create the ground work for more rational fee setting?

markblundeberg · August 17, 2020, 4:01am

As far as I can tell, checked 64 bit is in a class of its own as low hanging fruit and we don’t need to worry about DoS workarounds (Actually I’m not 100% sure about that! Integer division, even CPU-native division, can be quite slow. Needs analysis.). Of course it should be coded in a way that makes it possible to expand in future.

It seems that going beyond 64 is in another category – 80, 128, 129, 256, 257, 512, whatever. (I don’t understand why 128 is chosen btw, that seems to be focussed on some particular applications? 1+256 seems like the next natural step given how bitcoin is all about 256-bit nonnegative numbers. E.g. maybe someone wants to sha256 something and take a modulo for some clever idea.) Anyway once we figure out the DoS workarounds these are all fair game.

emergent_reasons · August 17, 2020, 5:49am

The reason of 128 is that Tobias seemed convinced that it is the boundary for doing things efficiently and without needing boost / additional dependencies in other languages. Also he thought it was important for fractional sats which I personally don’t put weight on for a near-term update.

andrewstone · August 20, 2020, 4:32pm

I think that we need to focus on the medium to long term when deciding to change the scripting language. And also an evolutionary approach is slower. Some 3rd world countries have better cell coverage than places in the USA because they didn’t bother to put down all the copper first – they leap-frogged the technology.

If we define a large bignum, then any interpreter can optimize cases that fit into a machine word. A large bignum prepares BCH script for the future, and provides key niche advantages today. Specifically, it should be very clear to developers that many of the tasks of BCH script will consist of cryptographic operations so there will be a need. And for proof, you can look at ETH: there are a variety of “bignum-out-of-256int” libraries that implement bignums there. We can “leapfrog” ETH by providing native, high performance bignums.

Worry about bignum support for various languages is putting too much focus on detail verses the broad picture of creating the most useful scripting language. All major languages have ways to import C libraries. Sure doing so may not be super convenient – but it is not correct to assume that the C++ impls get an “unfair advantage”. Arguably, C++, being an older and more complex language, assesses a continuous penalty on C++ full nodes. If the C++ implementations gain a small advantage here, how can we assess this advantage verses disadvantage?

I have created a bignum implementation over libgmp (gnu multiprecision library, LGPL licensed - that is the: LIBRARY GPL, not the standard GPL – so not viral and therefore compatible with MIT and commercial use). A quick search showed me that libgmp already contains bindings for all the major languages we are interested in.

See www.nextchain.cash for detailed specifications.