BigInt Inline

High-performance 256-bit multiplication for Jolt zkVM

Overview

The BigInt inline provides optimized 256-bit × 256-bit multiplication with 512-bit output. This is essential for cryptographic operations involving large integers, such as elliptic curve arithmetic and RSA operations.

API Reference

bigint256_mul()

Performs 256-bit × 256-bit multiplication.

pub fn bigint256_mul(
    lhs: [u64; 4],
    rhs: [u64; 4]
) -> [u64; 8]

Parameters

• lhs: First 256-bit operand as 4 u64 limbs (little-endian)
• rhs: Second 256-bit operand as 4 u64 limbs (little-endian)

Returns

• [u64; 8]: 512-bit result as 8 u64 limbs (little-endian)

bigint256_mul_inline()

Low-level unsafe interface to the multiplication instruction.

pub unsafe fn bigint256_mul_inline(
    a: *const u64,
    b: *const u64,
    result: *mut u64
)

Safety Requirements

• All pointers must be valid and 8-byte aligned
• a and b must point to at least 32 bytes of readable memory
• result must point to at least 64 bytes of writable memory
• Memory regions may overlap (result can alias a or b)

Usage Examples

Basic Multiplication

use bigint_inline::bigint256_mul;

#[jolt::provable]
fn multiply_big_numbers(a: [u64; 4], b: [u64; 4]) -> [u64; 8] {
    bigint256_mul(a, b)
}

Modular Arithmetic

use bigint_inline::bigint256_mul;

#[jolt::provable]
fn mul_mod(a: [u64; 4], b: [u64; 4], modulus: [u64; 4]) -> [u64; 4] {
    let product = bigint256_mul(a, b);
    // Perform modular reduction
    reduce_mod_256(product, modulus)
}

fn reduce_mod_256(value: [u64; 8], modulus: [u64; 4]) -> [u64; 4] {
    // Implementation depends on specific modulus
    // For prime field arithmetic, use specialized reduction
    todo!()
}

RSA Modular Exponentiation (Component)

use bigint_inline::bigint256_mul;

#[jolt::provable]
fn mod_square(x: [u64; 4], modulus: [u64; 4]) -> [u64; 4] {
    let square = bigint256_mul(x, x);
    reduce_mod_256(square, modulus)
}

Elliptic Curve Point Scalar Multiplication Helper

use bigint_inline::bigint256_mul;

#[jolt::provable]
fn field_mul(a: [u64; 4], b: [u64; 4], field_modulus: [u64; 4]) -> [u64; 4] {
    let product = bigint256_mul(a, b);
    barrett_reduction(product, field_modulus)
}

fn barrett_reduction(value: [u64; 8], modulus: [u64; 4]) -> [u64; 4] {
    // Barrett reduction algorithm
    todo!()
}

Implementation Details

Custom Instruction

• BIGINT256_MUL (funct3=0x00, funct7=0x04): Performs 256×256→512 multiplication

Limb Representation

Numbers are represented in little-endian limb order:

// Value = limbs[0] + limbs[1]·2⁶⁴ + limbs[2]·2¹²⁸ + limbs[3]·2¹⁹²
let value: [u64; 4] = [low, mid_low, mid_high, high];

Multiplication Algorithm

The inline performs schoolbook multiplication:

  a₃ a₂ a₁ a₀
× b₃ b₂ b₁ b₀
─────────────
  (products and carries)
─────────────
r₇ r₆ r₅ r₄ r₃ r₂ r₁ r₀

Each output limb rᵢ includes contributions from all aⱼ × bₖ where j + k = i, plus carries from lower limbs.

Memory Layout

• Input operands: 32 bytes each (4 × 64-bit limbs)
• Output: 64 bytes (8 × 64-bit limbs)
• Alignment: 8-byte (u64) alignment required

Constants

pub const INLINE_OPCODE: u32 = 0x0B;
pub const BIGINT256_MUL_FUNCT3: u32 = 0x00;
pub const BIGINT256_MUL_FUNCT7: u32 = 0x04;
pub const BIGINT256_MUL_NAME: &str = "BIGINT256_MUL_INLINE";

const INPUT_LIMBS: usize = 4;
const OUTPUT_LIMBS: usize = 2 * INPUT_LIMBS;  // 8

Performance Characteristics

• Cycle count: ~10-20x reduction compared to pure Rust implementation
• Proving overhead: Minimal additional constraints
• Throughput: Optimized for single 256×256 multiplication

Integration with Curve Libraries

The BigInt inline is used internally by:

• secp256k1 inline - Field arithmetic operations
• Grumpkin inline - Field arithmetic operations

For most use cases, prefer the high-level curve APIs which handle modular reduction automatically.

Comparison with Software Implementation

Pure Rust 256×256 multiplication typically requires:

• 16 64×64→128 multiplications
• Carry propagation logic
• ~100-200 RISC-V instructions

The inline reduces this to a single custom instruction.

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/bigint/
├── src/
│   ├── lib.rs          # Module definitions and registration
│   └── multiplication/
│       ├── mod.rs      # Constants and module structure
│       ├── sdk.rs      # Public API (bigint256_mul)
│       ├── exec.rs     # Host-side reference implementation
│       └── sequence_builder.rs  # Instruction sequence
└── Cargo.toml

Advanced Usage

Using Raw Pointers

For zero-copy operations:

use bigint_inline::bigint256_mul_inline;

#[jolt::provable]
fn multiply_in_place(a: &[u64; 4], b: &[u64; 4], result: &mut [u64; 8]) {
    unsafe {
        bigint256_mul_inline(
            a.as_ptr(),
            b.as_ptr(),
            result.as_mut_ptr()
        );
    }
}

Overlapping Memory

The inline supports in-place operations:

let mut buffer = [a, b, [0; 4]].concat();  // 12 u64s
unsafe {
    bigint256_mul_inline(
        buffer.as_ptr(),           // Points to 'a'
        buffer.as_ptr().add(4),    // Points to 'b'
        buffer.as_mut_ptr().add(4) // Overwrites 'b' and beyond
    );
}

See Also

• secp256k1 - Uses BigInt for field operations
• Grumpkin - Uses BigInt for field operations
• Inlines Overview - General information about cryptographic inlines