BigNum Arithmetic

Enables signed integers and integer arithmetic with 4096 + 1 sign bit precision

This work enables large integer arithmetic with a maximum of 4096 bit sign-magnitude precision (so 4097 bits of storage is required). Calculations may temporarily internally require double that size to handle overflow.

Overflow is handled by having every operation be executed modulo a positive value that can be set by the script (OP_SETBMD). Subscripts (OP_EXEC) inherit the setting of the caller, but the caller's setting is not changed if a subscript executes OP_SETBMD. For negative numbers truncated division rules are followed; in other words, the result gets the sign of the dividend: Given: $$ P>0, A mod P = B $$ Then: $$ -A mod P= -B $$

BigNum representation

BigNums cannot be accessed as bit patterns without first converting them via OP_NUM2BIN. This allows BigNums to be internally represented in any format.

OP_BIN2BIGNUM and OP_NUM2BIN convert to and from a binary format, and some opcodes accept either BigNum or binary data.

The binary format is a little-endian sign-magnitude representation. In other words, serialize the absolute value of the number in little-endian format, and then append a byte 0 for positive or 0x80 for negative.

BigNum operations

All implicit conversions proceed exactly as if OP_BIN2BIGNUM was executed. In particular, the implicit modulo is executed after the transformation.

B OP_SETMOD => (nothing)^? Sets the BigNum modulo divisor (BMD) to B. B must be > 0, and may be a BigNum or bignum-format binary data.

N OP_BIN2BIGNUM => B N is interpreted as a little-endian signed-magnitude integer. It is converted to a BigNum modulo BMD and stored on the stack.

B S OP_NUM2BIN => D B written to the stack as a little-endian signed-magnitude integer of length S+1 bytes (S byte number and 1 sign byte of 0 or 0x80).

B OP_IF => (nothing) Evaluates to "True" if B is nonzero, positive or negative.

A B OP_NUMEQUAL => C If either A or B are BigNums, C is a BigNum. 0 == -0

OP_NUMEQUALVERIFY, OP_NUMNOTEQUAL, OP_LESSTHAN, OP_GREATERTHAN, OP_LESSTHANOREQUAL, OP_GREATERTHANOREQUAL, OP_WITHIN,OP_0NOTEQUAL, If any input is a BigNum, all inputs are converted to BigNums before execution, and the output is a BigNum. (OP_IF works as expected with BigNums of value 0 or 1)

OP_MIN, OP_MAX If either input is a BigNum, all inputs are converted to BigNums before execution, and the output is a BigNum.

OP_1ADD, OP_1SUB, OP_NEGATE, OP_ABS, OP_ADD, OP_SUB, OP_MUL, OP_DIV, OP_MOD, OP_LSHIFT, OP_RSHIFT If any input is a BigNum, all inputs are converted to BigNums before execution, and the output is a BigNum.

a b OP_EQUAL => c a b OP_EQUALVERIFY => c Pop 2 args. Push False if the arguments are different types. If the arguments' types match, push True if equal as per that type's equality algorithm. These are byte comparison for byte strings (and therefore scriptnums), or numerical comparison for BigNums. Otherwise push False.

The VERIFY flavor then checks the true/false value on the top of the stack, fails the script if false, and pops if true.

OP_MUL Enabled for BigNums only. If either argument is a BigNum, the other is assumed to be a scriptnum and converted. As in all BigNum opcodes, the result of the operation modulo (truncated division) the BMD is pushed onto the stack.

bn cnt OP_LSHIFT => bnr Enabled for BigNums only. bn must be a BigNum, or the script is failed with SCRIPT_ERR_DISABLED_OPCODE. cnt must be 0 to the maximum bignum bit size (4096), and may be a BigNum or a ScriptNum.

As in all BigNum opcodes, the result of the operation modulo (truncated division) the BMD is pushed onto the stack.

bn cnt OP_RSHIFT => bnr Enabled for BigNums only. bn must be a BigNum, or the script is failed with SCRIPT_ERR_DISABLED_OPCODE. cnt may be a BigNum or a ScriptNum. bn >> cnt is executed.

As in all BigNum opcodes, the result of the operation modulo (truncated division) the BMD is pushed onto the stack. This is NOT a no-op because the BMD might have changed since bn was last used.

Design considerations

Sign magnitude

2's-complement arithmetic is not commonly used for large number arithmetic because its advantages are mitigated by larger sizes and turn into complexities when executing operations on numbers represented by different bit lengths.

No BigNum binary access / Typed stack

It is possible to implement BigNum behavior without adding type information to the stack. However, doing so means that the implementation would have to convert a BigNum to and from its internal representation to a little-endian sign-magnitude byte vector before and after every operation.

By disallowing direct access (i.e. implicit conversion) to the binary BigNum representation, we reflect the cost of this operation in the Bitcoin Script language, and simplify the implementation of the more efficient typed stack.

Maximum integer size

The maximum size of 4096 bits (512 bytes) was picked because the stack currently supports the storage of 520 bytes.

Modulo operator

A design concern is how to allow future expansion of the maximum number size in bits, should the maximum stack width be increased.

If operations were defined at a particular bit size, future expansion would have to create a separate type "ReallyBigNum" and associated load opcode. Otherwise scripts that relied upon the implicit modulo caused by the number's bit size would fail when operations that were modulo 4096 now became modulo 8192. If overflow instead caused script failure, script authors might rely on that behavior, even if a requirements document tells them not to.

Specifying the modulo as a parameter in every operation is incompatible with the existing arithmetic opcode parameter set, and would dramatically increase the size or complexity of the script.

Allowing a modulo to be specified results in efficently-coded scripts that execute cryptographic algorithms since many such algorithms operate in abelian numerical groups of prime order.

Once concern is that the current BMD is a piece of implicit state in the script virtual machine. It would be very "clean" if the entirety of virtual machine state existed on the 2 stacks. However, "this ship has already sailed"; the OP_CODESEPARATOR instruction stores the current program counter for subsequent use by signature checking instructions.

BigNum serialized representation

By matching the current serialized representation, BigNum becomes compatible with the existing 32-bit numerical system "ScriptNum". In particular ScriptNum can be used to execute a calculation, and then the result can be converted to a BigNum via OP_BIN2BIGNUM.

However, due to the fact that ScriptNums are converted to and from minimally-encoded binary representation before and after every operation, in practice it may be more efficient to use BigNums for small values.