128-bit integer proposal by Tobias Ruck

gistfile1.txt

---
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.
* Input and output sums of SLP values for a transaction are arbitrary precision integers.
* The locktime of a transaction is a 32-bit *unsigned* integer.
* The sequence number of an input of a transaction is a 32-bit *unsigned* integer.

It would be quite reasonable to expect Script developers to want to perform calculations and put numeric constraints on any of the abovely mentioned amounts.

# Motivation
Bitcoin Script being limited to 32-bit integers has been quite the engineering expense for smart contract developers since developing these kinds of contracts has gained traction, especially for smart contracts involving financial calculations. This either resulted in some smart contracts either being outright impossible, very difficult to implement or severely limited in range and/or precision of the involved values.

To mitigate those issues, this document proposes to allow 128-bit integers to become usable in Script, in a way that is compatible with existing contracts.

## Current State
There are a number of ways to work around the 32-bit integer limit, which in practice turns out to be a 31-bit integer limit, all of which have their own kinds of drawbacks:

### Limiting all amounts to 31-bit unsigned integers
A contract would simply fail for any amounts larger than 0x7fff'ffff.

For contracts involving addition and subtraction, like special wallets, dead-man switches or recurrent payment contracts, this limits the maximum possible BCH amount anywhere in the chain of computation to exactly 21.47483647 BCH, which at the time of writing is around $6000.

For uses in day-to-day commerce, this is acceptable, for any uses that require higher values, like a last will, gambling or finance, however, this number is unacceptably low.

However, a lot of financial contracts deal with multiplication and division instead, which limits most contracts involving oracles, prices, conversions etc. to values in the order of magnitude of $10.

In the SLP world, this becomes an even bigger problem. At the time of writing, the GoCrypto token has a valuation of $0.036 per token, with 8 decimal places. This means the maximum representable amount in dollar terms is $0.77. Similar numbers are the case for e.g. ACD Coin, or SPICE, where for the latter, Script would only be able to represent a maximum value of $0.03.

### Truncation arithmetic
A contract would calculate with numbers with some digits removed and then append the necessary zeros at the end again after the calculation.

This solves a lot of the issues of the previous approach, but has other problems:
- Calculations are fundamentally imprecise.
- The resulting math is very complicated and requires a lot of attention to avoid loss of funds.
- Error ranges for this kind of math is hard to establish.
- People involved in finance aren‘t used to these kinds of error ranges occuring.

### Long addtion, subtraction & division 
A contract would perform higher-bit arithmetic using smaller bit arithmetic.

This solves some of the issues of the previous approach, but to the author‘s knowledge there hasn‘t been any implementation of this approach, mostly because the math involved is even more complicated and for many applications, the number of required opcodes would likely exceed the maximum allowed number of opcodes.

## Limitation to P2SH only
As 128-bit arithmetic can be quite costly to execute, 128-bit integers are only be allowed in Pay-To-Script-Hash inputs, which mitigates a (currently relatively benign) DOS vector, which is described in the section Prototype & benchmark, DOS viability.

## Why 128-bit?
Instead of 128-bit integers, one could instead go for 64-bit integers first and add support for 128-bit integers later.

However, there are a number of advantages of going directly for 128-bit integers:
- Most programming languages support checked 128-bit integer arithmetic. C++ has some native support (e.g. __int128), but the Boost library (which is already part of the Bitcoin ABC code) has boost::multiprecision::checked_int128_t, which can detect overflows quite easily.
- The hard part of this proposal is not number of bits but in the activation logic, ensuring the math is correct and writing a large set of tests. Those will remain largely the same for either 64 or 128 bit integers.
- 64-bit integers will not be able to represent every valid SLP token amount. The maximum valid SLP amount is `0xffff'ffff'ffff'ffff`, however, the maximum valid 64-bit integer in Script would be `0x7fff'ffff'ffff'ffff`. Technically, the same is true for Bitcoin UTXO values, however, those are limited to `0x0007'75f0'5a07'4000` due to the 21'000'000 BCH supply limit.
- Many financial applications require high intermediate precision. For example, say a contract enforces a certain USD amount. This USD amount will then be divided by the USD/BCH price, to result in a value that should be a 64-bit integer. For this result to have a high level of precision, more bits than 64 are required.
- Eventually, Bitcoin Cash will move towards fractional satoshis, which probably will be represented with 128-bit integers. Already supporting 128-bit integers before that would ease this transition.

# Specification
The encoding of integers remains the same; and all integers have to be minimally encoded and will be minimally encoded after execution.
The semantics of the opcodes, however, will change:

## Existing arithmetic opcodes
- `x OP_1ADD -> r`
- `x OP_1SUB -> r`
- `x OP_NEGATE -> r`
- `x OP_ABS -> r`
- `x OP_0NOTEQUAL -> r`
- `x y OP_ADD -> r`
- `x y OP_SUB -> r`
- `x y OP_DIV -> r`
- `x y OP_MOD -> r`
- `x y OP_MIN -> r`
- `x y OP_MAX -> r`
- `x y OP_NUMEQUAL -> r`
- `x y OP_NUMNOTEQUAL -> r`
- `x y OP_LESSTHAN -> r`
- `x y OP_GREATERTHAN -> r`
- `x y OP_LESSTHANOREQUAL -> r`
- `x y OP_GREATERTHANOREQUAL -> r`
- `x y z OP_WITHIN -> r`
- `x y OP_NUMEQUALVERIFY`

Before the activation date, the following rules apply:
- `x`, `y` and `z` must all be within `-0x7fff'ffff` and `0x7fff'ffff`. Otherwise, fail the execution.
- `r` will be the result of the corresponding operation, as arbitrary precision integer.

After the activation date, the following rules apply instead:
- `x`, `y`, `z` and `r` must all be within `-0x7fff'ffff'ffff'ffff'ffff'ffff'ffff'ffff` and `0x7fff'ffff'ffff'ffff'ffff'ffff'ffff'ffff`.
- `r` will be the result of the corresponding operation, as checked 128-bit integer. If the operation overflows or exceeds the bounds, the execution fails.

## Existing conversion opcodes
- `x y OP_NUM2BIN -> b`
- `b OP_BIN2NUM -> r`

Before the activation date, the following rules apply:
- `x` and `r` must all be within `-0x7fff'ffff` and `0x7fff'ffff`. Otherwise, fail the execution.
- `y` must be between 0 and 520.

After the activation date, the following rules apply instead:
- `x` and `r` must all be within `-0x7fff'ffff'ffff'ffff'ffff'ffff'ffff'ffff` and `0x7fff'ffff'ffff'ffff'ffff'ffff'ffff'ffff`. Otherwise, fail the execution.
- `y` must be between 0 and 520.

## New opcode
- `x y OP_MUL -> r`
After the activation date, the following rules apply for `OP_MUL`:
- `x`, `y` and `r` must all be within `-0x7fff'ffff'ffff'ffff'ffff'ffff'ffff'ffff` and `0x7fff'ffff'ffff'ffff'ffff'ffff'ffff'ffff`.
- `r` will be the result of a signed multiplication of `x` and `y`, as checked 128-bit integer. If the operation overflows or otherwise exceeds the bounds, the execution fails.

# Notes
None of the existing contracts will become unspendable by this change, as it only loosens the rules of Script. While the results of all arithmetic operations (except `OP_BIN2NUM`) can be of arbitrary precision, due to the limits on the inputs, none of them can exceed the range of 128-bit integers.

The biggest possible result is from `0x7fff'ffff 0x7fff'ffff OP_ADD -> 0xffff'fffe`. `0xffff'fffe` easily fits in a 128-bit integer (note: this would be encoded as `"\x00\xfe\xff\xff\xff"` on the stack, a 5-byte string).

# Prototype & benchmark, DOS viability
A benchmarkable prototype has been implemented here: https://github.com/EyeOfPython/bitcoin-abc-benchin 

This prototype implementation doesn‘t add unittests and doesn‘t cover all cases (e.g. `-0x8000'...'0000` is a possible but invalid result). However, it allows us to evaluate if a naive implementation would allow any kind of DOS attack. For this the following script has been benchmarked with different opcode limits:

```
0x7fff'ffff'ffff'ffff'ffff'ffff'ffff'ffff
0x1234'5678'abcd'ef12
0x7'07ff'fff9'6880'62fa
OP_3DUP OP_MUL OP_DIV OP_MUL { repeated 50 times }
OP_2DROP
```

Another benchmarked script is the following:

```
0x7fff'ffff'ffff'ffff'ffff'ffff'ffff'ffff
0x1234'5678'abcd'ef12
0x7'07ff'fff9'6880'62fa
OP_3DUP OP_MUL OP_DIV OP_DIV { repeated 50 times }
OP_2DROP
```

The following benchmarks are performed on a MacBook from 2015 and should be taken with a grain of salt. Please perform your own benchmarks.

Note that a sigcheck on the same machine takes 70µs, thus a block performing 320'000 sigchecks would take 22.4s to verify. This should be seen as a soft upper bound for the verification time of a block. The benchmark can be seen as a check of whether this limit is upheld.

Results can be found here: https://github.com/EyeOfPython/bitcoin-abc-benchin/blob/master/benchmark.ipynb

- `df_size` is the script size for different opcode limits.
- `df_block_exec` is the number of seconds required to verify the scripts of a 32MB block filled with a type of script.
- `df` is the script execution time in µs.

Noteworthy are the last 4 columns in `df_block_exec`. It appears that OP_DIV and OP_MUL have both the same execution cost.

Three observations:

- A block filled with the known [2] OP_IF quadratic attack takes 00:02:45 to verify, which grows sub-linearly with the opcode limit.
- A block filled with the script being spent as non-P2SH input takes 00:02:00 to verify, and seems to grow linearly with the opcode limit.
- A block filled with the script being spent as P2SH input always takes between 17s and 23s to verify, only very slightly correlated with the opcode limit.

The OP_IF quadratic attack is already being fixed by Pieter Wuille on the Bitcoin Core implementation [3] and can soon be backported. There might still be other expensive scripts, especially those utilizing OP_HASH256.

Keeping the network busy for 00:02:00 would be a viable DOS attack, if the same hardware as a MacBook from 2015 were to be used. It therefore seems to be dangerous to enable 128-bit integers for non-P2SH. However, if 128-bit integers are only usable in P2SH, the DOS attack is mitigated, as it has the same validation cost 320'000 sig checks.

# References

[1]: https://www.boost.org/doc/libs/1_62_0/libs/multiprecision/doc/html/boost_multiprecision/tut/ints/cpp_int.html
[2]: https://bitslog.com/2017/04/17/new-quadratic-delays-in-bitcoin-scripts/
[3]: https://github.com/bitcoin/bitcoin/pull/16902