System/standard library for bignumbers

[axic]

EVM supports 256-bit operations "natively". While that precision is not needed in a lot of cases it does come as very useful for certain operations, such as handling token balances, in Ethereum.

With wasm one would need to include a bignumber library to do that, potentially in a lot of contracts. This suggests a good opportunity to define a standard bignumber library, which can be used by contracts, but it is not mandatory to be used.

Due to the design of "host" functions in wasm (having a separation of namespaces) it is possible to design this in a forward compatible manner, but implement it right now in the clients, such as Hera.

Lets define a new namespace stdbn (jk, bignum or stdbignum) with the following

• mul256(a: i32ptr, b: i32ptr, out: i32ptr)
• mulmod256(a: i32ptr, b: i32ptr, mod: i32ptr, out: i32ptr)
• others TBD

All of the arguments are 32-bit pointers to a memory location containing a 256-bit little endian number. The pointers can overlap or be the same.

In the future this could also be implemented as a (system) library: #17.

The main benefit of a "system library" is the predefined address it lives at and the client's ability to make a decision whether it uses a wasm blob or implements it natively.

[chfast]

I'm not sure the std prefix makes any difference here.

The name mul256 is fine because it's the same for signed and unsigned number. But the second one should be rather umulmod256.

The naming conventions are not very consistent everywhere, but I believe there are 3 options:

• assembly like: no prefix - signed or sign neutral, u prefix - unsigned.
• EVM like: no prefix - unsigned or sign neutral, s prefix - signed.
• pedantic like: no prefix - sign neutral, u prefix - unsigned, s prefix - signed.

[axic]

I like the pedantic option.

[axic]

I think we should add all 256-bit methods to the host interface: add, sub, mul, div, mulmod, cmp. Also need to consider support for signed numbers.

We could argue that some of them are fast enough if implemented in Wasm, but the secondary goal here is to reduce code duplication and it helps in that.

Any comments?

[jakelang]

Personally I feel like it would complicate the design for the bignum library to only contain the arithmetic methods that are not fast enough in wasm.

Reducing code duplication is definitely another big benefit of having a "complete" bignum lib. As long as we can minimize host function overhead, this is great for reducing contract bloat.

[axic]

Potentially we could make use of the references proposal for Wasm. Let assume the following example is for fixed 256-bit long bignums:

bignum.load(memOffset: i32) -> anyref
bignum.store(memOffset: i32, v: anyref)
bignum.mul(a: anyref, b: anyref)
bignum.add(a: anyref, b: anyref)
...

This assumes that opaque references (what anyref is) would be efficiently passed around in interpreters.

[axic]

Let's agree on this first basic API, which isn't using a bignum stack:

• addu256(a: i32ptr, b: i32ptr, c: i32ptr) where c = a + b
• subu256(a, b, c) where c = a - b
• mulu256(a, b, c) where c = a * b
• divu256(a, b, c) where c = a / b
• mulmodu256(a, b, c, d) where d = (a * b) % c
• cmpu256(a: i32ptr, b: i32ptr) -> i32 where the returned value is less than zero if a < b, zero if a == b or larger than zero if a > b

@chfast @s1na what do you think?

[poemm]

How about the first argument is the output. so output position is consistent for different numbers of arguments, for example binary_op(output,input1,input2) and unary_op(output, input)?

[axic]

I thought about having output as the first operand, but wasn't sure of the merit. Some POSIX functions do that, but find some of them confusing.

What would be the benefit we gain? Note, I expect this to change during the upcoming months. We also need to make a decision whether to replace (or add) a stack based version.

[poemm]

What would be the benefit we gain?

Convention. Gnu Multiple Precision and lots of crypto pass output first. But it doesn't matter.

We also need to make a decision whether to replace (or add) a stack based version.

Not sure which algorithms benefit from the stack based version, other than pathological benchmarks. But it may be simple enough to implement -- bin_op256_stack() can just call bin_op256(stack_ptr-32, stack_ptr-32, stack_ptr) and update the stack pointer.

[jakelang]

I agree with @axic here.
Although it's somewhat common in POSIX and other legacy conventions to use op(dst, src),
It is far more linguistically intuitive writing op(src, dst) when lacking the muscle memory for the former.