## Preamble

```
CAP: 0074
Title: Host functions for BN254
Working Group:
    Owner: Siddharth Suresh <@sisuresh>
    Authors: Siddharth Suresh <@sisuresh>, Jay Geng <@jayz22>, Matteo Lisotto
    Consulted: Jay Geng <@jayz22>, Anup Pani <@anupsdf>
Status: Final
Created: 2025-09-25
Discussion: https://github.com/orgs/stellar/discussions/1772
Protocol version: 25
```

## Simple Summary
BN254 is a pairing-friendly elliptic curve that has wide support in the ecosystem, and CAP proposes a set of new host functions to provide native support for this curve.

## Working Group

As described in the preamble section.

## Motivation
While Stellar has native support for BLS12-381, many existing applications still rely on BN254 because it's the only pairing friendly elliptic curve with native support in the EVM. Adding BN254 support will allow those applications to add support for Soroban without the need to use a different curve.

### Goals Alignment
This CAP is aligned with the following Stellar Network Goals:

  - The Stellar Network should make it easy for developers of Stellar projects
    to create highly usable products

## Abstract
Three new host functions are proposed for performing curve operations on BN254.

## Specification

### New host functions
```
{
    "export": "m",
    "name": "bn254_g1_add",
    "args": [
        {
            "name": "point1",
            "type": "BytesObject"
        },
        {
            "name": "point2",
            "type": "BytesObject"
        }
    ],
    "return": "BytesObject",
    "docs": "Adds two BN254 G1 points given in bytes format and returns the resulting G1 point in bytes format. G1 serialization format: `concat(be_bytes(X), be_bytes(Y))`. This function does NOT perform subgroup check on the inputs.",
    "min_supported_protocol": 25
},
{
    "export": "n",
    "name": "bn254_g1_mul",
    "args": [
        {
            "name": "point",
            "type": "BytesObject"
        },
        {
            "name": "scalar",
            "type": "U256Val"
        }
    ],
    "return": "BytesObject",
    "docs": "Multiplies a BN254 G1 point by a scalar (Fr), and returns the resulting G1 point in bytes format.",
    "min_supported_protocol": 25
},
{
    "export": "o",
    "name": "bn254_multi_pairing_check",
    "args": [
        {
            "name": "vp1",
            "type": "VecObject"
        },
        {
            "name": "vp2",
            "type": "VecObject"
        }
    ],
    "return": "Bool",
    "docs": "performs pairing operation on a vector of `G1` (`Vec<BytesObject>`)  and a vector of `G2` points (`Vec<BytesObject>`) , return true if the result equals `1_fp12`",
    "min_supported_protocol": 25
}
```

### XDR changes
```
diff --git a/Stellar-contract-config-setting.x b/Stellar-contract-config-setting.x
index b075c6b4f..36abfeb7c 100644
--- a/Stellar-contract-config-setting.x
+++ b/Stellar-contract-config-setting.x
@@ -260,7 +260,30 @@ enum ContractCostType {
     // Cost of performing BLS12-381 scalar element exponentiation
     Bls12381FrPow = 68,
     // Cost of performing BLS12-381 scalar element inversion
-    Bls12381FrInv = 69
+    Bls12381FrInv = 69,
+
+    // Cost of encoding a BN254 Fp (base field element)
+    Bn254EncodeFp = 70,
+    // Cost of decoding a BN254 Fp (base field element)
+    Bn254DecodeFp = 71,
+    // Cost of checking a G1 point lies on the curve
+    Bn254G1CheckPointOnCurve = 72,
+    // Cost of checking a G2 point lies on the curve
+    Bn254G2CheckPointOnCurve = 73,
+    // Cost of checking a G2 point belongs to the correct subgroup
+    Bn254G2CheckPointInSubgroup = 74,
+    // Cost of converting a BN254 G1 point from projective to affine coordinates
+    Bn254G1ProjectiveToAffine = 75,
+    // Cost of performing BN254 G1 point addition
+    Bn254G1Add = 76,
+    // Cost of performing BN254 G1 scalar multiplication
+    Bn254G1Mul = 77,
+    // Cost of performing BN254 pairing operation
+    Bn254Pairing = 78,
+    // Cost of converting a BN254 scalar element from U256
+    Bn254FrFromU256 = 79
 };
 
 struct ContractCostParamEntry {
```

### Semantics

#### Field and groups

`fp` - field element in the base field. Encoding rule: big-endian encoding of the underlying unsigned 32-byte integer. `fp` cannot be larger than the field modulus `0x30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd47`.

`fp2`- field element in the quadratic extension of the base prime field. Encoding rule: concatenation of the two encoded-components `c1` and `c0` i.e. `be_encode(c1) || be_encode(c0)`

`fp12` - field element in the 12-degree prime extension field. This is the output from the pairing operation. `fp12` is only used as the intermediary and encoding is not needed.

`fr` - scalar. A scalar has maximum length of 32 bytes. `fr` is represented with an `U256Val`, and it can be any number between `0` and `2^{256}-1`.

`G1` - group containing points over the base prime field that satisfy the curve equation, plus point at infinity. Encoding rule: concatenation of the two encoded-coordinates (uncompressed form), each being an `fp`, i.e. `be_encode(X) || be_encode(Y)`. The point at infinity is encoded as `(0,0)`. No flag bits are reserved, i.e. the highest two bits in the first byte (`0x80` and `0x40`) must be unset.

`G2` - group containing points over the quadratic extension of the base prime field that satisfy the curve equation, plus the point at infinity. Encoding rule: concatenation of the two encoded-coordinates (uncompressed form), each following `fp2` encoding rule, i.e. `be_encode(X_c1) || be_encode(X_c0) || be_encode(Y_c1) || be_encode(Y_c0)`. The point at infinity is encoded as `(0,0)`. No flag bits are reserved, i.e. the highest two bits in the first byte (`0x80` and `0x40`) must be unset.

#### New host functions introduced

##### `bn254_g1_add`

**Description**: perform point addition in G1. 

**Cost**: covers the cost of decoding (`Bn254DecodeFp`) and on curve check (`Bn254G1CheckPointOnCurve`) of G1 points, point addition (`Bn254G1Add`), conversion of from projective to affine space (`Bn254G1ProjectiveToAffine`), and encoding the result to bytes `Bn254EncodeFp`. 

**Error condition**: if the input bytes contained in each `BytesObject` do not decode into valid G1 points or do not conform the specified encoding standard.
- Bytes length is not equal to 64
- The point is compressed.
- Either input point does not belong on the G1 curve.

##### `bn254_g1_mul`
**Description** perform scalar multiplication in G1. 

**Cost**: includes decoding G1 point, converting `fr` from `U256` (`Bn254FrFromU256`), point multiplication `Bn254G1Mul`, converting the point from project to affine and encoding the result into bytes.

**Error condition**: if the input `BytesObject` does not decode into a valid G1 points or does not conform the specified encoding standard.
- Bytes length is not equal to 64.
- The point is compressed.
- The input point does not belong on the G1 curve.

##### `bn254_multi_pairing_check`
**Description**: performs pairing operation on a vector of `G1` and a vector of `G2` points, returns `true` if the result equals `1_fp12`, otherwise returns `false`. 

**Cost**: includes deserialization of the point vectors (in G1 and G2 respectively), cost of performing the pairing operation `Bn254Pairing`.

**Error conditions**: 
1. two input vectors have different length
2. either input vector has zero length
3. any element in the G1 vector does not decode into a valid G1 point or does not conform the specified encoding standard.
- Bytes length is not equal to 64
- The point is compressed.
- Either input point does not belong on the G1 curve.
4. any element in the G2 vector does not decode into a valid G2 point or does not conform the specified encoding standard.
- Bytes length is not equal to 128
- The point is compressed.
- Either input point does not belong on the G2 curve.
- Either input point does not belong to the correct subgroup.

#### New metering `CostType`s introduced
- `Bn254EncodeFp` - Cost of encoding a BN254 Fp (base field element). Encoding includes the necessary conversion from the internal representation into integer form, and serialization into bytes. Type: constant.
- `Bn254DecodeFp` - Cost of decoding a BN254 Fp (base field element). Decoding includes deserialization from bytes into integer, and the necessary conversion from the integer form to the internal representation. Type: constant.
- `Bn254G1CheckPointOnCurve` - Cost of validating that a G1 point lies on the curve. Type: constant.
- `Bn254G2CheckPointOnCurve` - Cost of validating that a G2 point lies on the curve. Type: constant.
- `Bn254G2CheckPointInSubgroup` - Cost of validating that a G2 point belongs to the correct subgroup. Type: constant.
- `Bn254G1ProjectiveToAffine` - Cost of converting a BN254 G1 point from projective to affine coordinates. Type: constant.
- `Bn254G1Add` - Cost of performing BN254 G1 point addition. Type: constant.
- `Bn254G1Mul` - Cost of performing BN254 G1 scalar multiplication. Type: constant.
- `Bn254Pairing` - Cost of performing BN254 pairing operation. Type: linear w.r.t to the length of the input vectors.
- `Bn254FrFromU256` - Cost of converting a BN254 scalar element from U256. This includes necessary conversion from the integer form to the internal representation. Type: constant.

## Design Rationale

### Function list choice
The list of host functions give Stellar parity with Ethereum. Specifically, we're adding support for the precompiles specified in [EIP-196](https://eips.ethereum.org/EIPS/eip-196) and [EIP-197](https://eips.ethereum.org/EIPS/eip-197).

#### `U256Val` for scalar
All field and group elements mentioned in the host functions are represented as `BytesObject`, with encoding rule specified in [fields and groups](#field-and-groups), except for the scalar element. Since the scalar can be up to 32-bytes, with the same semantics as an unsigned integer, using `U256Val` is the natural choice. Extracting bytes in the correct format can be tricky and error prone, depending on the underlying implementation. Using `U256Val` also takes advantage of the internal small value optimization which reduces storage space for small numbers, see [value type repertoire](cap-0046-01.md/#rationale-for-value-and-object-type-repertoires).

#### Encode/Decode
The only two cost types representing encoding/decoding are of the base field element `Bn254EncodeFp` and `Bn254DecodeFp`, since all field and group elements can be composed of the base elements. (En)Decoding `G1` is (en)decoding two `fp` separately, same for `fp2`. `G2` contains two `fp2`, that are (en)decoded separately.

#### No G1 subgroup check
If the point is on the G1 curve, then it also belongs to the G1 subgroup (https://hackmd.io/@jpw/bn254#Subgroup-check-for-mathbb-G_1), so there's no need for a G1 subgroup check. You can also see that the 
[arkworks](https://github.com/arkworks-rs/algebra/blob/c6f9284c17df00c50d954a5fe1c72dd4a5698103/curves/bn254/src/curves/g1.rs#L61) library always returns true for the subgroup check.

## Protocol Upgrade Transition
The proposed host functions will become available protocol 25, i.e. with `"min_supported_protocol": 25` in the interface definition. For `protocol_version <= 24`, attempting to import any of these function definitions in the WASM will lead to a linking error during Vm instantiation time. 

### Backwards Incompatibilities
This CAP does not introduce any backward incompatibilities.

### Resource Utilization
The performance impact of the new host functions have been captured by the new `CostType` described above. The cpu and memory consumption need to be calibrated carefully on each new `CostType` to ensure that the cost of running BN host functions are metered properly and subject to the network limits. Final calibration numbers are TBD.

## Security Concerns
The main security concerns include
- Logic correctness. The proposed set of functions cover a wide range of cryptographic operations, which rely on correctness of 3rd party implementations. Incorrect implementation or failure to cover certain corner case potentially be exploitable vulnerabilities. 
- Denial of service. Since the proposed operations are computationally intensive, failure to properly calibrate any part, or to properly account for an extra-expensive path, could lead to the actual computation time significantly exceeding the metered costs, thus potentially lead to denial of service.
- Curve security - the curve no longer offers 128-bit security.

## Test Cases
1. Added tests from the ethereum-go repo [here](https://github.com/stellar/rs-soroban-env/blob/cf58d535ab05d02802a5e804a95524650f8c62c7/soroban-env-host/src/test/bn254.rs#L993).
2. Added test from the evm precompile docs [here](https://github.com/stellar/rs-soroban-env/blob/cf58d535ab05d02802a5e804a95524650f8c62c7/soroban-env-host/src/test/bn254.rs#L772C1-L772C42).

## Implementation

TODO