BigNum Modulo Divisor
login
{ "title": "BigNum Modulo Divisor" }

BigNum modulo divisor (BMD)

Every BigNum script operation is followed by a truncated division (that is, a sign-preserving modulo operation) to ensure that the resulting BigNum fits within script machine memory size limits. Given a BMD of size S bits, every BigNum must therefore be no larger than S+1 bits, because an additional bit is needed to denote the number’s sign.

OP_EXECed subscripts inherit the caller’s BMD, but the caller is not affected by any BMD changes a subscript makes.

Defaults

Every script MUST begin with the BMD set to 2**64 or 0x10000000000000000.

Limits

The BMD MUST be no larger than 2**4096.
The BMD MUST not be 0.

Design Considerations

BMD verses stateless solutions

The BMD introduces an additional piece of state into the script machine. Implicit state can cause script bugs as script authors assume incorrect implicit state.

Yet, we cannot change the arithmetic opcode parameter counts to include a modulo for BigNum operations only without introducing a significant bug vector, where the number of parameters for arithmetic operations would differ based on the types of some of those parameters. And the stack manipulations require to supply this modulo parameter for every operation would be painful and grow the script.

If a constant modulo is chosen, future expansion of capacity would require a completely new “BiggerBigNum” type.

If overflow and underflow script errors are raised (failing the script), the useful size of the BigNum becomes half the maximum bit length because multiplying 2 N bit numbers may result in a 2N bit number. Additionally, script authors may rely on this behavior to fail the script, which would break these scripts if the overflow/underflow limit is later raised. Therefore, like a constant modulo, the overflow/underflow option will require a new type to increase capacity.

Finally, this solution opens the possibility of more script-size-efficient implementations of cryptographic operations that occur over modular groups. Such groups almost always require prime order (modulus) so that repeating the group operation on any element generates the entire group with the cycle time == group order. This prime number differs for different groups so must be configurable.

BMD default

The relatively small default BMD was chosen so that scripts begin with efficient numerical calculations, with the expectation that scripts that use BigNums in a cryptographic context shall set the BMD explicitly.