Improve utility of script calculations - larger numbers + op_mul

Consensus
#1

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

7 Likes
2021 BCH upgrade items brainstorm
#2

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

6 Likes
#3

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.

1 Like
#4

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.

1 Like
#5

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.

#6

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.
1 Like
#7

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?

#8

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.

#9

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.

#10

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.

3 Likes
#11

Do any fleshed-out proposals exist for this smaller upgrade to 64-bit numbers?

#12

Has anyone written any full explorations of whether or not upgrades to the number range should keep the current overflow behavior (overflows are accurate, but further math operations will fail) vs. a new behavior to fail the script immediately on overflows?

Scripts can be badly-designed to rely on either mechanic such that an upgrade would ā€œbreakā€ their contract. (Of course, Iā€™d prefer these possibly-non-existent scripts be broken than for BCH to take on permanent technical debt to avoid breaking them, I just think itā€™s important that we publicly note the decision.)

2 Likes
#13

No one has done it. I also think this is a relatively low-hanging fruit of investigation. Find all transactions since some reasonable point in the past, say the CDS upgrade, and do a regression test on actual rules vs. drop-in 64 bit numbers. If some outcomes are different due to dependence on overflow behavior, it will give insight into actual risk. If no outcomes are different then :man_shrugging:.

Just as a guess, using the script testing system that @rosco developed using Libauth seems reasonable if Libauth could provide an engine with a signed 64-bit drop-in replacement. Hmmā€¦ but then data sizes may have knock-on effects. What do you think of the possibility?

#14

Cool, I might try to do that on-chain analysis in the next few months. Of course, whether or not they already exist, if several implementations start working on a solid proposal, I expect someone will broadcast transactions which are broken by it before deployment (griefing). So maybe we should also clarify in the spec that ā€œcontracts designed to break after script number range upgrades will require migrationā€.

if Libauth could provide an engine with a signed 64-bit drop-in replacement [ā€¦]

Sure, that should be fairly easy. When instantiating a VM instance, you can modify the instruction set to replace each arithmetic operation with a version that supports signed 64-bit inputs and results, e.g. transaction introspection alternative VM.

1 Like