[Proposal] alt_bn128 curve math

[snjax]

Proposal

To implement a set of zkSNAKs verifiers (like Groth16 or PLONK) I suggest to add alt_bn128 math functions into VM:
To learn more about alt_bn128 and subgroups G1 and G2 see EIP-196 and EIP-197.

Functions

All formulas below are defined in additive notation. If data is wrong serialized, the function returns Error.

• alt_bn128_g1_multiexp(items:&[G1, Fr]) -> Result<G1>

Compute with Pippenger's algorithm, where are Fr scalars and are G1 group elements.

Bad data: If a is more or equal then Fr order or is not in G1 group, function returns Error.

Complexity: . I propose to use regularization for .

Gas formula:

fn log2floor(x:u64) -> u64 {
    let mut t = x;
    let mut r = 0;
    for offset in [32, 16, 8, 4, 2, 1].iter() {
        if t >> offset != 0 {
            t >>= offset;
            r += offset;
        }
    }
    r
}

let n = (n_bytes+item_size-1)/item_size;
let gas_consumed = A+B*n+C * if n > 1 {n / log2floor(n)} else {n};

B is linear component, corresponding to deserialization complexity.

• alt_bn128_g1_sum(items:&[G1, bool]) -> Result<G1>

Compute .

Bad data: If a is not one or zero or is not in G1 group, function returns Error.

Complexity: linear

Gas formula:

let n = (n_bytes+item_size-1)/item_size;
let gas_consumed = A+B*n;

• alt_bn128_pairing_check(items:&[G1,G2]) -> Result<bool>

Compute

Bad data: If is not in G1 group or is not in G2 subgroup, function returns Error.

Complexity: linear

Gas formula:

let n = (n_bytes+item_size-1)/item_size;
let gas_consumed = A+B*n;

Data encoding

G1 is serialized as two U256 (x and y) in LE.
G2 is serialized as four U256 (re(x), im(x), re(y), im(y)) in LE.
bool is serialized as one byte.
Tuple is serialized as concatenated chunks of serialized elements.
Slice is serialized as concatenated chunks of serialized elements.

Implementation

alt_bn128 functions implemented as fork of parity-bn with minor updates:

• serialization, deserialization
• pippenger multiexp
• API, described above

The crate should be published and moved to nearprotocol.

[MaksymZavershynskyi]

@akhi3030 Is this implemented and can be closed?

[akhi3030]

@nearmax: in near/nearcore#6824, we stabalised alt_bn128_g1_multiexp, alt_bn128_g1_sum, alt_bn128_pairing_check.
However, I do not see any NEPs or spec for these function in this repo. Maybe a NEP is not strictly necessary as the bulk of the work was done before the NEP process was standardised. However, we should probably add something to the spec. We can probably create a separate issue to track the remaining work and close this issue.

[frol]

@akhi3030 Yes, please, create a new issue and close this one. Could you take ownership of getting the spec updated? 🙏

[akhi3030]

@akhi3030 Yes, please, create a new issue and close this one. Could you take ownership of getting the spec updated? 🙏

Happy to do so!

[akhi3030]

The remaining work is now tracked in #426. Please prefer continuing discussions on that issue.