added alt_bn syscalls

[ananas-block]

Compatibility

This is an updated version of previous pull request (https://github.com/solana-labs/solana/pull/26629) for Solana v1.11.x Credit for the previous pull request is due to @ai-trepalin. Problem

It is very expensive to compute elliptic curve operations over the bn256(bn254/bn128) curve on Solana. The following curve operations enable for example efficient verification of zero-knowledge proofs within one transaction.

Additionally, contracts written in the Solidity language cannot work in Solana if they contain calls to the following precompiled contracts:

bn256Add — Performs addition on the elliptic curve operations. bn256ScalarMult — Performs scalar multiplication on the elliptic curve operations. bn256Pairing — Elliptic curve pairing operations to perform zkSNARKs verification within the block gas limit.

https://github.com/ethereum/EIPs/blob/master/EIPS/eip-196.md https://github.com/ethereum/EIPs/blob/master/EIPS/eip-197.md

The Neon EVM requires the implementation of system calls in Solana for these contracts. Also, Light Protocol requires the implementation of these syscalls in Solana for more efficient zero-knowledge proof verification. Solution

In order for the precompiled contracts to be used in Solana, it is proposed to implement sys-calls inside the Solana core. That is, to perform an implementation similar to the erc-recover implementation. Summary of Changes

This merge request adds implementation of bn256 (alt_bn128) precompiles. About compute budget costs

Add and ScalarMult are implemented in constant time. Execution time for the pairing implementation follows a linear equation: pairingCU = firstPairingExecutionTime + (numberOfPairings - 1) * otherPairingsExecutionTime

This equation computes the compute units charged (implementation).

The equation results from the arkwork products of pairings implementation which executes a miller loop for every pairing and only one final exponentiation.

In Ethereum gas costs for the pairing operation are calculated similarly.

Possible pricing based on 33ns execution time per CU:

Addition: 334 CU Multiplication: 3,840 CU Pairing: 36,364 CU + (numberOfPairings - 1) * 12,121 CU

Comput units for one G1 multiplication: 126.71 * 1000 / 33 = 3,840 CU Compute units for the first pairing: 1.2ms * 1_000_000 / 33 (ns per CU) = 36,364 CU Compute units for one additional pairing: 0.4ms * 1_000_000 / 33 (ns per CU) = 12,121 CU (Both 1.2ms and 0.4ms have been selected as upper bounds with buffer based on the bench results below.)

Bench Results: Benchmarks were conducted on an aws c6a.2xlarge instance, see detailed bench results and bench implementation.

Summary: G1 addition time:: [4.1247 us 4.1553 us 4.1903 us] Found 6 outliers among 100 measurements (6.00%) 1 (1.00%) low severe 2 (2.00%) high mild 3 (3.00%) high severe

G1 mul time:: [126.64 us 126.68 us 126.71 us] Found 8 outliers among 100 measurements (8.00%) 1 (1.00%) low severe 3 (3.00%) low mild 3 (3.00%) high mild 1 (1.00%) high severe

2 pairings time: [1.3630 ms 1.3718 ms 1.3839 ms] Found 6 outliers among 100 measurements (6.00%) 2 (2.00%) high mild 4 (4.00%) high severe

3 pairings time: [1.6807 ms 1.6819 ms 1.6835 ms] Found 6 outliers among 100 measurements (6.00%) 1 (1.00%) high mild 5 (5.00%) high severe

4 pairings time: [1.9977 ms 1.9980 ms 1.9983 ms] Found 3 outliers among 100 measurements (3.00%) 3 (3.00%) high mild

5 pairings time: [2.3224 ms 2.3227 ms 2.3230 ms] Found 3 outliers among 100 measurements (3.00%) 3 (3.00%) high mild

Fixes #