CHIP 2024-07 BigInt: High-Precision Arithmetic for Bitcoin Cash

CHIPs Standards Track
#21

Welcome to Bitcoin Cash Research!

2 Likes
#22

Just for reference, I found nice documentation on big integer algorithms (from bc documentation, it is an arbitrary precision numeric processing language, and interpreter binary ships with most Linux distros):

Could be useful if later we want to add ops like OP_EXP

1 Like
#23

The chip says bigint libraries are available, but considering the new unlimited design, it is worth mentioning the standard upper limits on big integer size in major languages. The reasons are:

  1. 258 bytes… ok probably any arbitrary int library can handle that. maybe. But you have a little doubt unless you have actually checked the spec of a given language / library.
  2. 10k bytes… ok definitely getting into “probably but really not sure” territory.
  3. future 10k+ bytes… :man_shrugging:

I have looked into the answers to these to convince myself, but authoritative sources / examples should be cited in the CHIP. I’m not sure what the right sources would be. For example I found the limit in the v8 spec for bigint, but that’s not exactly the js spec.

1 Like
#24

In addition to this, it needs to be confirmed that those libraries perform 1:1 operations compared to the intent of VM math ops. Especially in negative numbers, handling of integer math diverges in various systems.

Already from this simple example below, you can see that AT LEAST either python or javascript will need special handling for exactly spec integer behavior. This is a problem that exists already, but I haven’t seen it spelled out anywhere. Minimally:

  • What are the exact boundaries and edge conditions on arbitrary size VM integers?
  • What is the exact behavior for negative numbers?
// javascript:
-10n / 3n
// result: -3n

# python:
-10 // 3
# result: -4

To pre-empt, this is not a shitting contest for languages you don’t like. It’s a practical issue that the CHIP should cover or at least mention.

1 Like
#25

That’s why I added examples here: https://github.com/bitjson/bch-bigint/pull/4/files#diff-5a831ea67cf5cf8703b0de46901ab25bd191f56b320053be9332d9a3b0d01d15R175

should add some text saying “floors towards zero (truncation)”

2 Likes
#26

GP has proposed this PR which would work in replacement of PR 4 and in combination with PRs 2 and 3. We think these changes are required in some form and not optional before our endorsement can be considered for 2025 activation.

1 Like
#27

Great, thanks to General Protocols for the review! I’ll work on incorporating the feedback on both CHIPs. :pray:

3 Likes
#28

Heads up, I’m working with Calin on creating an extensive suite of property tests for arithmetic opcodes, draft/WIP here: https://github.com/bitjson/bch-bigint/pull/7/files

Example, we know that a + b == b + a must hold no matter what, so we run this script: <a> <b> OP_2DUP OP_ADD OP_SWAP OP_ROT OP_ADD OP_EQUAL and we test it for many random values of a and b (such that a + b <= MAX_INT), and the script must always evaluate to true.

So far so good, all the test so far implemented pass as expected, giving us more confidence in BCHN’s BigInt implementation.

2 Likes