secp256k1 Inline

High-performance secp256k1 elliptic curve operations and ECDSA verification for Jolt zkVM

Overview

The secp256k1 inline provides optimized elliptic curve operations for the secp256k1 curve (used in Bitcoin and Ethereum). It includes field arithmetic, point operations, and ECDSA signature verification.

API Reference

Secp256k1Fq

Base field element (coordinates).

pub struct Secp256k1Fq {
    e: [u64; 4],  // 256-bit value in standard (non-Montgomery) form
}

Methods

pub fn from_u64_arr(arr: &[u64; 4]) -> Result<Self, Secp256k1Error>;
pub fn from_u64_arr_unchecked(arr: &[u64; 4]) -> Self;
pub fn e(&self) -> [u64; 4];
pub fn zero() -> Self;
pub fn seven() -> Self;
pub fn is_zero(&self) -> bool;
pub fn neg(&self) -> Self;
pub fn add(&self, other: &Secp256k1Fq) -> Self;
pub fn sub(&self, other: &Secp256k1Fq) -> Self;
pub fn dbl(&self) -> Self;
pub fn tpl(&self) -> Self;
pub fn mul(&self, other: &Secp256k1Fq) -> Self;  // Uses inline
pub fn square(&self) -> Self;                      // Uses inline
pub fn div(&self, other: &Secp256k1Fq) -> Self;   // Uses inline

Secp256k1Fr

Scalar field element (private keys, signatures).

pub struct Secp256k1Fr {
    e: [u64; 4],  // 256-bit value in standard form
}

Methods

pub fn from_u64_arr(arr: &[u64; 4]) -> Result<Self, Secp256k1Error>;
pub fn from_u64_arr_unchecked(arr: &[u64; 4]) -> Self;
pub fn e(&self) -> [u64; 4];
pub fn as_u128_pair(&self) -> (u128, u128);
pub fn zero() -> Self;
pub fn is_zero(&self) -> bool;
pub fn neg(&self) -> Self;
pub fn add(&self, other: &Secp256k1Fr) -> Self;
pub fn sub(&self, other: &Secp256k1Fr) -> Self;
pub fn dbl(&self) -> Self;
pub fn mul(&self, other: &Secp256k1Fr) -> Self;   // Uses inline
pub fn square(&self) -> Self;                       // Uses inline
pub fn div(&self, other: &Secp256k1Fr) -> Self;    // Uses inline

Secp256k1Point

Affine point on the secp256k1 curve.

pub struct Secp256k1Point {
    x: Secp256k1Fq,
    y: Secp256k1Fq,
}

Methods

pub fn new(x: Secp256k1Fq, y: Secp256k1Fq) -> Result<Self, Secp256k1Error>;
pub fn new_unchecked(x: Secp256k1Fq, y: Secp256k1Fq) -> Self;
pub fn from_u64_arr(arr: &[u64; 8]) -> Result<Self, Secp256k1Error>;
pub fn from_u64_arr_unchecked(arr: &[u64; 8]) -> Self;
pub fn to_u64_arr(&self) -> [u64; 8];
pub fn x(&self) -> Secp256k1Fq;
pub fn y(&self) -> Secp256k1Fq;
pub fn generator() -> Self;
pub fn infinity() -> Self;
pub fn is_infinity(&self) -> bool;
pub fn is_on_curve(&self) -> bool;
pub fn neg(&self) -> Self;
pub fn double(&self) -> Self;
pub fn add(&self, other: &Secp256k1Point) -> Self;
pub fn double_and_add(&self, other: &Secp256k1Point) -> Self;
pub fn endomorphism(&self) -> Self;
pub fn decompose_scalar(k: &Secp256k1Fr) -> [(bool, u128); 2];  // GLV

ecdsa_verify()

Verifies an ECDSA signature.

pub fn ecdsa_verify(
    z: Secp256k1Fr,  // Message hash
    r: Secp256k1Fr,  // Signature component
    s: Secp256k1Fr,  // Signature component
    q: Secp256k1Point  // Public key
) -> Result<(), Secp256k1Error>

Error Handling

pub trait UnwrapOrSpoilProof<T> {
    fn unwrap_or_spoil_proof(self) -> T;
}

impl<T> UnwrapOrSpoilProof<T> for Result<T, Secp256k1Error> { /* ... */ }

Use .unwrap_or_spoil_proof() to make proofs unsatisfiable on error (e.g., invalid signature).

Usage Examples

ECDSA Signature Verification

use secp256k1_inline::{ecdsa_verify, Secp256k1Fr, Secp256k1Point, UnwrapOrSpoilProof};

#[jolt::provable]
fn verify_signature(
    message_hash: [u64; 4],
    signature_r: [u64; 4],
    signature_s: [u64; 4],
    public_key: [u64; 8],
) -> bool {
    let z = Secp256k1Fr::from_u64_arr(&message_hash).unwrap();
    let r = Secp256k1Fr::from_u64_arr(&signature_r).unwrap();
    let s = Secp256k1Fr::from_u64_arr(&signature_s).unwrap();
    let q = Secp256k1Point::from_u64_arr(&public_key).unwrap();
    
    // Returns Ok(()) if valid, Err(_) if invalid
    ecdsa_verify(z, r, s, q).is_ok()
}

Proving Valid Signature (Spoil Proof on Invalid)

use secp256k1_inline::{ecdsa_verify, UnwrapOrSpoilProof};

#[jolt::provable]
fn prove_valid_signature(
    z: Secp256k1Fr,
    r: Secp256k1Fr,
    s: Secp256k1Fr,
    q: Secp256k1Point,
) {
    // If signature is invalid, no valid proof can exist
    ecdsa_verify(z, r, s, q).unwrap_or_spoil_proof();
}

Point Addition

use secp256k1_inline::Secp256k1Point;

#[jolt::provable]
fn add_public_keys(pk1: [u64; 8], pk2: [u64; 8]) -> [u64; 8] {
    let p1 = Secp256k1Point::from_u64_arr(&pk1).unwrap();
    let p2 = Secp256k1Point::from_u64_arr(&pk2).unwrap();
    p1.add(&p2).to_u64_arr()
}

Field Arithmetic

use secp256k1_inline::Secp256k1Fq;

#[jolt::provable]
fn field_multiply(a: [u64; 4], b: [u64; 4]) -> [u64; 4] {
    let x = Secp256k1Fq::from_u64_arr(&a).unwrap();
    let y = Secp256k1Fq::from_u64_arr(&b).unwrap();
    x.mul(&y).e()
}

Implementation Details

Custom Instructions

The secp256k1 inline provides seven custom instructions:

Base Field (Fq) Operations

1. SECP256K1_MULQ (funct3=0x00): Multiply two Fq elements
2. SECP256K1_SQUAREQ (funct3=0x01): Square an Fq element
3. SECP256K1_DIVQ (funct3=0x02): Divide Fq elements (computes a/b mod q)

Scalar Field (Fr) Operations

4. SECP256K1_MULR (funct3=0x04): Multiply two Fr elements
5. SECP256K1_SQUARER (funct3=0x05): Square an Fr element
6. SECP256K1_DIVR (funct3=0x06): Divide Fr elements (computes a/b mod r)

Advice (Non-deterministic)

7. SECP256K1_GLVR_ADV (funct3=0x07): GLV scalar decomposition (pure advice, verified in constraints)

Curve Equation

secp256k1: y² = x³ + 7 over the prime field:

p = 2²⁵⁶ - 2³² - 2⁹ - 2⁸ - 2⁷ - 2⁶ - 2⁴ - 1
  = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F

Scalar field (order of generator):

n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

GLV Endomorphism

The implementation uses the GLV method to accelerate scalar multiplication:

• Decompose scalar k into k = k₁ + k₂·λ where |k₁|, |k₂| ≤ 2¹²⁸
• Compute k·G = k₁·G + k₂·(λ·G) using 4-dimensional windowed multiplication
• λ = 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72

This reduces scalar multiplication from 256 doublings to ~128 combined operations.

ECDSA Verification Algorithm

1. Check q ≠ ∞, r ≠ 0, s ≠ 0
2. Compute u₁ = z/s (mod n), u₂ = r/s (mod n)
3. Compute R = u₁·G + u₂·Q using GLV
4. Verify R.x ≡ r (mod n)

Point Representation

Points use affine coordinates with infinity represented as (0, 0) (not on curve).

Non-Montgomery Form

Unlike arkworks, this implementation stores field elements in standard (non-Montgomery) form to match inline semantics. Addition/subtraction still use arkworks (same in both forms), but multiplication/division use custom inlines.

Error Types

pub enum Secp256k1Error {
    InvalidFqElement,  // Value ≥ p
    InvalidFrElement,  // Value ≥ n
    NotOnCurve,        // Point not on y² = x³ + 7
    QAtInfinity,       // Public key is infinity
    ROrSZero,          // Invalid signature (r=0 or s=0)
    RxMismatch,        // Signature verification failed
}

Constants

pub const INLINE_OPCODE: u32 = 0x0B;
pub const SECP256K1_FUNCT7: u32 = 0x05;

// Base field operations
pub const SECP256K1_MULQ_FUNCT3: u32 = 0x00;
pub const SECP256K1_SQUAREQ_FUNCT3: u32 = 0x01;
pub const SECP256K1_DIVQ_FUNCT3: u32 = 0x02;

// Scalar field operations  
pub const SECP256K1_MULR_FUNCT3: u32 = 0x04;
pub const SECP256K1_SQUARER_FUNCT3: u32 = 0x05;
pub const SECP256K1_DIVR_FUNCT3: u32 = 0x06;

// Advice operations
pub const SECP256K1_GLVR_ADV_FUNCT3: u32 = 0x07;

Performance Characteristics

• Field multiplication: ~10-20x faster than pure Rust
• ECDSA verification: ~50-100x faster end-to-end
• Scalar multiplication: GLV optimization provides 2x speedup

Feature Flags

• host: Enables reference implementation for host-side execution
  • Guest code: Compile WITHOUT this feature
  • Prover code: Compile WITH this feature

Source Code Location

jolt-inlines/secp256k1/
├── src/
│   ├── lib.rs          # Module definitions and constants
│   ├── sdk.rs          # Public API (1114 lines)
│   ├── sequence_builder.rs  # Instruction sequences
│   └── host.rs         # Host-side registration
└── Cargo.toml

See Also

• Grumpkin - Cycle curve for BN254
• BigInt - Used internally for field operations
• Inlines Overview - General information about cryptographic inlines