[Proposal] [Leo RFC] Fine-grained integer types

[acoglio]

💥 Proposal - Leo RFC

Summary

Instead of just having 5 sizes of unsigned and signed integer types, allow all sizes, in order to minimize the number of bits, which are costly in the R1CS computation model (vs. the more traditional computation model).

Motivation

A user may need a variable to store a number from 0 to 10, for which 4 bits suffice, but the smallest available type is u8, which has 4 extra bits.

While supplying a few "standard" sizes is appropriate for traditional programming languages that ultimately run on an x86 or similar kind of processor, the R1CS computation model is different, and every bit has a cost there.

Design

Instead of just the types u8 u16 u32 u64 u128 and i8 i16 i32 i64 i128, support any type u<n> and i<n> where <n> is a positive (non-zero) integer.

For the example above (a number from 0 to 10), one could use a variable of type u4.

Based on avoiding user surprise/error, the arithmetic operations should error (statically or dynamically, as feasible) when the result of two integer operands with the same type do not fit in the type. In this case, it should be easy for the user to use a slightly larger type (e.g. one more bit for an addition).

Based on the same motivation of avoiding user surprise/error, casts that may change value should be explicit, while casts that never do could be implicit, but we may decide to make all of them explicit instead (cf. discussion in #600).

As a point of comparison, the Circom language (https://docs.circom.io) has no integer types as such, but supports the creation of arrays of boolean signals, and operations on them, that are essentially unsigned and signed integers of any sizes.

Drawbacks

The Leo language and compiler become a bit more complicated, but things should not change much structurally. Instead of handling 5 possible fixed sizes of integers, we would have to handle any size. (We may put an upper limit to <n>, although we should not have to.)

Users have to be more cognizant of the number of bits of things, but for assurance and correctness I would say that this is actually an advantage, not a drawback. (Still, users may find it a burden, which is why I mention it as a "drawback".)

Effect on Ecosystem

None?

Alternatives

Stick to the current 5 sizes.