Description: Normative specifications for ClockinChain big integer arithmetic

# ClockinChain Big Integer Specifications

This document collection contains the normative specifications for the ClockinChain Big Integer library, a production-ready big integer crate for blockchain consensus engines.

## Specifications

- Representation Specification v1.0 - Canonical encoding and memory layout
- Arithmetic Algorithm Specification v1.0 - Deterministic arithmetic operations
- Montgomery & Modular Exponentiation Specification v1.0 - Cryptographic arithmetic
- Gas Schedule Specification v1.0 - Precomputable gas metering

## Overview

The ClockinChain Big Integer specifications define a complete cryptographic big integer arithmetic library with the following key properties:

- Deterministic: Bit-for-bit identical results across all platforms
- Constant-time: All operations execute in constant time to prevent timing attacks
- Canonical encoding: Unique representation for each integer value
- Gas metering: Precomputable gas costs for VM execution
- Montgomery arithmetic: Full support for cryptographic operations
- Time-sliced operations: Pausable long operations for async VM execution

## Implementation

These specifications are implemented in the clock-bigint Rust crate.

## License

This specification is licensed under the same terms as the clock-bigint crate.

# ClockinChain Big Integer Representation Specification v1.0

## Overview

This specification defines the canonical representation, memory layout, and encoding format for big integers in the ClockinChain ecosystem.

## 1. Memory Layout

### 1.1 Limb Definition

Big integers are represented as arrays of 64-bit unsigned integers called "limbs":

    #![allow(unused)]
    fn main() {
    type Limb = u64;
    const LIMB_BITS: usize = 64;
    }

### 1.2 Endianness

All limb arrays use little-endian ordering:

- `limbs[0]` contains the least significant limb
- `limbs[n-1]` contains the most significant limb

### 1.3 Word Size

The base B = 2^64, so each limb represents a value in the range [0, 2^64 - 1].

## 2. Canonical Form

### 2.1 Zero Representation

Zero MUST be represented as:

- `sign = false`
- `limbs = [0]` (exactly one limb)
- No leading zero limbs allowed

### 2.2 Non-zero Representation

Non-zero integers MUST satisfy:

- No leading zero limbs: `limbs[limbs.len() - 1] != 0`
- Minimal limb count: smallest n such that the above holds
- Sign bit indicates negative values

### 2.3 Negative Zero Prohibition

Negative zero is explicitly forbidden:

- `sign = true` AND `value = 0` is invalid
- All zero values MUST have `sign = false`

## 3. Type System

### 3.1 Dynamic BigInt

    #![allow(unused)]
    fn main() {
    struct BigInt {
        sign: bool,           // false = positive, true = negative
        limbs: Vec<Limb>,     // little-endian limb array
        max_limbs: usize,     // capacity limit
    }
    }

### 3.2 Fixed-Size BigInt

    #![allow(unused)]
    fn main() {
    struct BigIntFixed<const L: usize> {
        limbs: [Limb; L],     // fixed-size array
    }
    }

### 3.3 Type Aliases

Common fixed sizes:

- `U256 = BigIntFixed<4>` (256 bits)
- `U512 = BigIntFixed<8>` (512 bits)
- `U1024 = BigIntFixed<16>` (1024 bits)
- `U2048 = BigIntFixed<32>` (2048 bits)

## 4. Encoding Format

### 4.1 Binary Format

Canonical binary encoding uses the following format:

    [sign: u8][limb_count: u32 LE][limbs: u64[] LE]

Where:

- `sign`: 0 for positive, 1 for negative
- `limb_count`: number of limbs (u32, little-endian)
- `limbs`: limb array in little-endian byte order

### 4.2 Encoding Rules

1. Canonical encoding: Every integer has exactly one valid encoding
2. No leading zeros: Encoded limb arrays must not contain leading zero limbs
3. Minimal length: Use the smallest limb count that satisfies canonical form
4. Deterministic: Same integer always produces identical encoding

### 4.3 Decoding Validation

Decoding MUST reject:

- Invalid sign values (not 0 or 1)
- Leading zero limbs in non-zero values
- Negative zero representations
- Malformed binary data

## 5. Memory Management

### 5.1 Allocation Strategy

- Dynamic BigInt uses heap allocation with Vec
- Fixed BigInt uses stack allocation when L ≤ 8
- Heap allocation for L > 8 or dynamic types

### 5.2 Capacity Limits

- `MAX_LIMBS = 512` (32768 bits maximum)
- Prevents denial-of-service attacks
- Enforced at allocation time

### 5.3 Canonicalization

All BigInt values MUST be canonicalized after operations:

- Remove leading zero limbs
- Enforce zero sign rule
- Maintain minimal representation

## 6. Cross-Platform Compatibility

### 6.1 Endianness

- All encodings use little-endian byte order
- Limb arrays are always little-endian
- Platform endianness is irrelevant

### 6.2 Word Size

- Assumes 64-bit limbs
- No support for 32-bit platforms
- All operations assume 64-bit arithmetic

### 6.3 Determinism

- Identical inputs produce identical outputs
- No platform-specific behavior
- No undefined behavior in arithmetic

## 7. Error Conditions

### 7.1 Invalid Encoding

`InvalidEncoding` error for:

- Malformed binary data
- Non-canonical representations
- Invalid sign values

### 7.2 Capacity Exceeded

`Overflow` error for:

- Operations exceeding max_limbs
- Fixed-size overflow (const generics)

### 7.3 Invalid Operations

`InvalidModulus` error for:

- Even moduli in Montgomery operations
- Zero moduli
- Invalid modulus sizes

## 8. Testing Requirements

### 8.1 Canonical Form Tests

- Zero representation uniqueness
- No leading zeros in encodings
- Sign consistency validation
- Cross-platform determinism

### 8.2 Encoding Tests

- Round-trip encoding/decoding
- Rejection of invalid encodings
- Canonical encoding uniqueness
- Performance benchmarks

### 8.3 Memory Safety Tests

- Bounds checking validation
- Allocation limit enforcement
- Memory leak prevention
- Stack overflow prevention

# Arithmetic Algorithm Specification v1.0

## Overview

This specification defines the normative algorithms for all big integer arithmetic operations in the ClockinChain ecosystem. All algorithms must execute in constant time and produce deterministic results.

## 1. Common Conventions

### 1.1 Limb Operations

    #![allow(unused)]
    fn main() {
    // Basic limb arithmetic with carry/borrow
    fn limb_add_carry(a: Limb, b: Limb, carry: Limb) -> (Limb, Limb) {
        let sum = a as u128 + b as u128 + carry as u128;
        (sum as Limb, (sum >> 64) as Limb)
    }

    fn limb_sub_borrow(a: Limb, b: Limb, borrow: Limb) -> (Limb, Limb) {
        let diff = a as i128 - b as i128 - borrow as i128;
        (diff as Limb, if diff < 0 { 1 } else { 0 })
    }

    fn limb_mul_wide(a: Limb, b: Limb) -> (Limb, Limb) {
        let product = a as u128 * b as u128;
        (product as Limb, (product >> 64) as Limb)
    }
    }

### 1.2 Fixed Loop Rule

All algorithms MUST iterate over full declared limb length:

- Never exit loops early
- Mask carries instead of branching
- Use constant-time condition selection
- Fixed execution paths regardless of input values

### 1.3 Algorithm Selection

Operations choose algorithms based on public parameters only (limb length), never secret values.

## 2. Addition Algorithm

### 2.1 Function Signature

    #![allow(unused)]
    fn main() {
    fn add(a: &BigInt, b: &BigInt) -> Result<BigInt>
    }

### 2.2 Precondition

- `a` and `b` have equal limb length `n`
- If dynamic-length, caller ensures sufficient capacity

### 2.3 Algorithm

    For i = 0 .. n-1:
        (sum_i, carry) = adc(a.limbs[i], b.limbs[i], carry)
        c.limbs[i] = sum_i

    After final limb:
        If carry = 1:
            If dynamic-length → append new limb = 1
            If fixed-length → overflow trap

### 2.4 Constant-Time adc

    #![allow(unused)]
    fn main() {
    sum = x + y + carry
    carry_out = (sum < x) OR ((carry == 1) AND (sum == x))
    }

No branches allowed.

### 2.5 Sign Handling

- Same sign: `sign(c) = sign(a)`
- Different signs: invoke subtraction algorithm

### 2.6 Gas Cost

`G_add(n) = 3n`

## 3. Subtraction Algorithm

### 3.1 Function Signature

    #![allow(unused)]
    fn main() {
    fn sub(a: &BigInt, b: &BigInt) -> Result<BigInt>
    }

### 3.2 Algorithm (Magnitude)

    For i = 0 .. n-1:
        (diff_i, borrow) = sbb(a.limbs[i], b.limbs[i], borrow)
        c.limbs[i] = diff_i

    If final borrow = 1 → result negative:
        Compute two's complement of magnitude
        Flip sign bit

### 3.3 Constant-Time sbb

    #![allow(unused)]
    fn main() {
    diff = x - y - borrow
    borrow_out = (x < y) OR ((borrow == 1) AND (x == y))
    }

No branches.

### 3.4 Sign Rule

`sign(c) = sign(a) XOR sign(b)`

### 3.5 Gas Cost

`G_sub(n) = 3n`

## 4. Multiplication Algorithm

### 4.1 Function Signature

    #![allow(unused)]
    fn main() {
    fn mul(a: &BigInt, b: &BigInt) -> Result<BigInt>
    }

### 4.2 Comba Method (Small Operands)

For operands ≤ 16 limbs:

    Let n = limb count
    Initialize c limbs length = 2n all zero

    for i = 0 .. n-1:
        carry = 0
        for j = 0 .. n-1:
            (lo, hi) = mul64(a[i], b[j])
            (c[i+j], carry) = mac(c[i+j], lo, carry)
            carry += hi
        c[i+n] = carry

### 4.3 Karatsuba Method (Large Operands)

For operands > 16 limbs:

    fn karatsuba_mul(a: &[Limb], b: &[Limb]) -> Vec<Limb> {
        let n = a.len();
        let m = n / 2;

        // Split operands
        let (a0, a1) = a.split_at(m);
        let (b0, b1) = b.split_at(m);

        // Compute z0 = a0*b0
        let z0 = karatsuba_mul(a0, b0);

        // Compute z2 = a1*b1
        let z2 = karatsuba_mul(a1, b1);

        // Compute z1 = (a0+a1)*(b0+b1) - z0 - z2
        let a01 = add_limbs(a0, a1);
        let b01 = add_limbs(b0, b1);
        let z1 = karatsuba_mul(&a01, &b01);
        sub_limbs_inplace(&mut z1, &z0);
        sub_limbs_inplace(&mut z1, &z2);

        // Combine results
        return combine_karatsuba_results(z0, z1, z2, m);
    }

### 4.4 Threshold Selection

- Threshold MUST be fixed constant: `KARATSUBA_THRESHOLD = 16`
- Execution path depends only on public limb length
- Never on operand values

### 4.5 Sign Rule

`sign(c) = sign(a) XOR sign(b)`

### 4.6 Gas Cost

`G_mul(n) = 2n²`

## 5. Division Algorithm

### 5.1 Function Signatures

    #![allow(unused)]
    fn main() {
    fn div_rem(a: &BigInt, b: &BigInt) -> Result<(BigInt, BigInt)>
    fn div(a: &BigInt, b: &BigInt) -> Result<BigInt>
    fn rem(a: &BigInt, b: &BigInt) -> Result<BigInt>
    }

### 5.2 Knuth Algorithm D

1. Normalize divisor: Left-shift so highest bit set
2. Left-shift dividend equally
3. Main loop:

    for i from high_limb downto low_limb:
        // Estimate quotient digit q̂
        q̂ = estimate_quotient_digit(dividend, divisor, i)

        // Multiply and subtract
        (partial_product, borrow) = mul_sub(divisor, q̂, dividend_slice)

        // Correct if overestimated
        while borrow != 0:
            q̂ -= 1
            add_back(divisor, dividend_slice)
            borrow = check_borrow(dividend_slice)

### 5.3 Constant-Time Corrections

- All correction steps use masked subtraction
- No branches based on borrow values
- Fixed iteration count based on limb length

### 5.4 Division by Zero

Must return deterministic `DivisionByZero` error.

### 5.5 Sign Rules

    quotient_sign = sign(a) XOR sign(b)
    remainder_sign = sign(a)

### 5.6 Gas Cost

`G_div(n) = 4n²`

## 6. Squaring Algorithm

### 6.1 Function Signature

    #![allow(unused)]
    fn main() {
    fn sqr(a: &BigInt) -> Result<BigInt>
    }

### 6.2 Specialized Algorithm

Squaring uses optimized algorithm for `a²`:

- Exploits symmetry: `a² = (a0 + a1*B)² = a0² + 2*a0*a1*B + a1²*B²`
- Fewer multiplications than general multiplication
- Same constant-time properties

### 6.3 Gas Cost

`G_sqr(n) = 1.6n²` (cheaper than multiplication)

## 7. Bitwise Operations

### 7.1 Bit Shift

    #![allow(unused)]
    fn main() {
    fn shift_left(a: &BigInt, bits: usize) -> Result<BigInt>
    fn shift_right(a: &BigInt, bits: usize) -> Result<BigInt>
    }

### 7.2 Algorithm

- Convert bit shifts to limb shifts + intra-limb shifts
- Handle carry/borrow across limb boundaries
- Constant-time regardless of shift amount

### 7.3 Gas Cost

`G_shift(n) = 2n`

## 8. Comparison Operations

### 8.1 Comparison Functions

    #![allow(unused)]
    fn main() {
    fn cmp(a: &BigInt, b: &BigInt) -> Ordering
    fn eq(a: &BigInt, b: &BigInt) -> bool
    fn lt(a: &BigInt, b: &BigInt) -> bool
    }

### 8.2 Constant-Time Implementation

- Compare magnitudes first
- Then compare signs if magnitudes equal
- No early exit on first difference

### 8.3 Gas Cost

`G_cmp(n) = 2n`

## 9. Error Conditions

Condition | Result
--- | ---
Overflow (fixed) | VM Trap
Overflow (dynamic beyond max) | Overflow error
Division by zero | Deterministic error
Non-canonical input | Decode rejection

## 10. Determinism Guarantee

Given identical inputs, all implementations MUST:

- Produce identical limb outputs
- Execute identical iteration counts
- Consume identical gas cost
- Never branch on secret data

# Montgomery & Modular Exponentiation Specification v1.0

## Overview

This specification defines the normative cryptographic arithmetic standard for Montgomery operations and modular exponentiation, critical for ChronoSig, ChronoHash, ChronoMerkle, and ZK systems.

## 1. Base Parameters

### 1.1 Definitions

- Limb base: `B = 2^64`
- Limb count: `n`
- Modulus: `m`, where `m` MUST be odd
- `R = B^n mod m`
- `R² = B^(2n) mod m`
- `m' = -m⁻¹ mod B`

### 1.2 Montgomery Representation

A value `x` in normal representation is converted to Montgomery form:

    x̃ = (x × R) mod m

Montgomery domain arithmetic operates on `x̃`.

## 2. Montgomery Reduction

### 2.1 Function Signature

    #![allow(unused)]
    fn main() {
    fn mont_reduce(t: &BigInt, m: &BigInt, m_prime: Limb) -> BigInt
    }

Where `t` is a 2n-limb value.

### 2.2 Algorithm

    For i = 0 .. n-1:
        u_i = (t[i] × m') mod B
        (t[i .. i+n]) += u_i × m[0 .. n]

    After loop:
        t = t[n .. 2n]
        if t ≥ m:
            t -= m

### 2.3 Constant-Time Implementation

The conditional subtraction MUST be implemented via masked subtraction — not branching.

### 2.4 Gas Cost

`G_mont_reduce(n) = n²`

## 3. Montgomery Multiplication

### 3.1 Function Signature

    #![allow(unused)]
    fn main() {
    fn mont_mul(ã: &BigInt, b̃: &BigInt, m: &BigInt, m_prime: Limb) -> BigInt
    }

### 3.2 Definition

    c̃ = mont_reduce(ã × b̃)

Produces: `c̃ = (a × b × R) mod m`

### 3.3 Gas Cost

`G_mont_mul(n) = 2n²`

## 4. Montgomery Addition/Subtraction

Performed normally in Montgomery domain:

    Add: c̃ = (ã + b̃) mod m
    Sub: c̃ = (ã - b̃) mod m

Both followed by conditional reduction (constant-time masked subtraction).

## 5. Conversion Functions

### 5.1 Into Montgomery Form

    #![allow(unused)]
    fn main() {
    fn to_mont(x: &BigInt, m: &BigInt) -> BigInt
    }

Definition:

    to_mont(x) = mont_mul(x, R² mod m)

### 5.2 Out of Montgomery Form

    #![allow(unused)]
    fn main() {
    fn from_mont(x̃: &BigInt, m: &BigInt) -> BigInt
    }

Definition:

    from_mont(x̃) = mont_reduce(x̃)

## 6. Montgomery Context

### 6.1 Structure

    #![allow(unused)]
    fn main() {
    struct MontgomeryContext {
        modulus: BigInt,      // m
        r_mod_m: BigInt,      // R mod m
        r_squared_mod_m: BigInt, // R² mod m
        m_prime: Limb,        // m'
        limb_count: usize,    // n
    }
    }

### 6.2 Creation

    #![allow(unused)]
    fn main() {
    fn new(modulus: BigInt) -> Result<MontgomeryContext>
    }

Requirements:

- `modulus` MUST be odd
- `modulus > 0`
- Precomputes all context values

## 7. Modular Exponentiation

### 7.1 Function Signature

    #![allow(unused)]
    fn main() {
    fn mod_pow(base: &BigInt, exponent: &BigInt, modulus: &BigInt) -> Result<BigInt>
    }

### 7.2 Montgomery Ladder Algorithm

    Input: base in normal form
    Output: base^exponent mod modulus

    1. Precompute:
       R mod m
       R² mod m
       m'

    2. Convert:
       x̃ = to_mont(base)
       R̃ = to_mont(1)

    3. Initialize:
       R0 = R̃
       R1 = x̃

    4. For bit i from MSB(exponent) → LSB:
       bit = exponent[i]

       cswap(bit, R0, R1)
       R1 = mont_mul(R0, R1)
       R0 = mont_mul(R0, R0)
       cswap(bit, R0, R1)

    5. result = from_mont(R0)

### 7.3 Constant-Time Conditional Swap

    #![allow(unused)]
    fn main() {
    mask = -bit  // 0xFFFF... if bit=1, 0x0000... if bit=0
    tmp = mask & (R0 XOR R1)
    R0 ^= tmp
    R1 ^= tmp
    }

No branches allowed.

### 7.4 Gas Cost

`G_modexp(n, k) = k × 4n² + 20n²`

Where k = exponent bit length.

## 8. Modular Inverse

### 8.1 Via Extended GCD

    #![allow(unused)]
    fn main() {
    fn mod_inverse(a: &BigInt, m: &BigInt) -> Result<BigInt>
    }

Uses binary extended GCD with constant-time loop bounds.

### 8.2 Via Fermat's Little Theorem

For prime modulus `p`:

    a⁻¹ mod p = a^(p-2) mod p

### 8.3 Gas Cost

- Via GCD: `G_inv_gcd(n) = 6n²`
- Via exponentiation: same as `G_modexp`

## 9. Error Conditions

Condition | Result
--- | ---
m even | Reject modulus (InvalidModulus error)
modulus = 0 | Reject (InvalidModulus error)
exponent = 0 | Return 1 mod m
base = 0 & exponent = 0 | Return 1 (by convention)

## 10. Security Properties

### 10.1 Constant-Time Guarantee

All Montgomery operations MUST maintain:

- Constant-time execution w.r.t secret data
- No secret-dependent memory access
- Identical instruction count for equal limb sizes
- Safe for signature and ZK usage

### 10.2 Side Channel Resistance

- Montgomery reduction eliminates power analysis patterns
- Ladder exponentiation prevents timing attacks
- No data-dependent branches or memory access

## 11. Test Vector Requirements

### 11.1 Known Answer Tests

Test vectors MUST include:

- RSA modulus operations
- secp256k1 field operations
- Randomized consistency tests:

    #![allow(unused)]
    fn main() {
    // Verify: from_mont(mont_mul(to_mont(a), to_mont(b))) == (a*b mod m)
    assert_eq!(
        from_mont(&mont_mul(&to_mont(a), &to_mont(b))),
        (a * b) % modulus
    );
    }

### 11.2 Edge Cases

- Modulus = 3 (smallest valid odd modulus)
- Base = 0, 1, modulus-1
- Exponent = 0, 1, large values
- Carry propagation in Montgomery reduction

## 12. Performance Targets

Operation | Target
--- | ---
MontMul (256-bit) | ~200 cycles
MontReduce (256-bit) | ~100 cycles
ModExp (2048-bit) | within 10% of GMP

## 13. Implementation Notes

### 13.1 Word Size Assumptions

- Assumes 64-bit limbs
- Montgomery parameters optimized for 64-bit arithmetic
- No support for 32-bit platforms

### 13.2 Memory Layout

- All Montgomery values use canonical BigInt representation
- No special internal formats
- Compatible with all other BigInt operations

### 13.3 Determinism

- Identical results across platforms
- No undefined behavior
- Reproducible for consensus-critical applications

# Gas Schedule Specification v1.0

## Overview

This specification defines the normative gas cost constants for all BigInt arithmetic operations, ensuring deterministic, precomputable metering for the ClockinChain VM.

## 1. Design Principles

### 1.1 Gas Cost Properties

1. Public parameters only: Gas cost depends only on public limb length
2. No secret dependency: Never depends on operand values
3. Linear/quadratic scaling: Simple mathematical formulas
4. Constant-time compatible: Compatible with constant-time execution
5. Precomputable: VM can compute costs before execution
6. DoS protection: Prevents arithmetic-based denial-of-service

### 1.2 Base Definitions

    #![allow(unused)]
    fn main() {
    const G_BASE: Gas = 10;  // Baseline dispatch cost unit
    let n: usize = limb_count;
    let k: usize = exponent_bit_length;
    }

All costs below are added to `G_BASE`.

## 2. Core Arithmetic Costs

### 2.1 Addition and Subtraction

Operation | Formula | Notes
--- | --- | ---
Addition | `G_add(n) = 3n` | Carry chain propagation
Subtraction | `G_sub(n) = 3n` | Borrow chain propagation
Negation | `G_neg(n) = 2n` | Two's complement
Comparison | `G_cmp(n) = 2n` | Full limb comparison

### 2.2 Bitwise Operations

Operation | Formula | Notes
--- | --- | ---
Bit shift | `G_shift(n) = 2n` | Barrel shift implementation

## 3. Multiplication Costs

### 3.1 Multiplication Variants

Operation | Formula | Notes
--- | --- | ---
Multiply | `G_mul(n) = 2n²` | Comba/Karatsuba
Square | `G_sqr(n) = 1.6n²` | Optimized for squaring
Multiply-Accumulate | `G_mac(n) = 2n²` | Internal operation

### 3.2 Algorithm Selection

- Comba method for small operands (n ≤ 16)
- Karatsuba method for large operands (n > 16)
- Cost formula covers both algorithms

## 4. Division and Modulo

### 4.1 Division Operations

Operation | Formula | Notes
--- | --- | ---
Division | `G_div(n) = 4n²` | Knuth long division
Modulo | `G_mod(n) = 4n²` | Same cost as division
DivMod | `G_divmod(n) = 4n²` | Shared computation

### 4.2 Division Algorithm

- Knuth Algorithm D with constant-time corrections
- Quadratic complexity due to digit-by-digit approach
- Includes normalization and denormalization steps

## 5. Montgomery Domain Operations

### 5.1 Montgomery Arithmetic

Operation | Formula | Notes
--- | --- | ---
MontReduce | `G_mred(n) = n²` | Reduction loop
MontMul | `G_mmul(n) = 2n²` | Mul + Reduce
MontAdd/Sub | `G_madd(n) = 3n` | + conditional reduction
ToMont | `G_tomont(n) = 2n²` | Using R²
FromMont | `G_frommont(n) = n²` | Reduction only

### 5.2 Modular Exponentiation

Ladder Cost Formula:

    G_modexp(n, k) = k × (G_mmul(n) + G_mmul(n)) + G_setup
                   = k × 4n² + 20n²

Where:

- `k` = exponent bit length
- Ladder performs 2 multiplications per bit
- Setup cost covers Montgomery context creation

## 6. Modular Inverse

### 6.1 Inverse Methods

Method | Cost | Notes
--- | --- | ---
Binary GCD | `G_inv_gcd(n) = 6n²` | Constant-time bounds
Via ModExp | `G_modexp(n, n)` | For prime moduli

### 6.2 Binary GCD Algorithm

- Extended Euclidean algorithm
- Fixed iteration bounds based on limb count
- Constant-time implementation

## 7. Encoding and Serialization

### 7.1 Encoding Operations

Operation | Formula | Notes
--- | --- | ---
Canonicalize | `G_canon(n) = n` | Remove leading zeros
Encode | `G_enc(n) = n` | Serialize to bytes
Decode | `G_dec(n) = n` | Deserialize from bytes

### 7.2 Encoding Format

Binary format: `[sign: u8][limb_count: u32 LE][limbs: u64[] LE]`

## 8. Global Limits

### 8.1 Maximum Size Limits

    #![allow(unused)]
    fn main() {
    const MAX_LIMBS: usize = 512;  // 32768-bit integers
    }

- Prevents denial-of-service attacks
- Operations exceeding this MUST trap before execution

### 8.2 Overflow Handling

- Fixed-length BigInt: Trap on overflow
- Dynamic BigInt: Error on exceeding capacity

## 9. Example Costs

### 9.1 Common Sizes

Operation | 256-bit (n=4) | 2048-bit (n=32)
--- | --- | ---
Add | 12 | 96
Mul | 32 | 2048
MontMul | 32 | 2048
Div | 64 | 4096
ModExp (256-bit exp) | ~32768 | ~8.3M
ModExp (2048-bit exp) | ~131072 | ~33.5M

### 9.2 Gas Budget Considerations

For typical blockchain operations:

- Simple transfers: ~50 gas
- ECDSA signature verification: ~100K gas
- Modular exponentiation (2048-bit): ~10M gas

## 10. Governance and Updates

### 10.1 Gas Schedule Adjustments

- Gas constants may be adjusted by chain governance
- Must maintain linear/quadratic form constraints
- Updates require consensus approval

### 10.2 Backward Compatibility

- Gas costs can only increase (never decrease)
- New operations can be added with appropriate costs
- Existing operations maintain cost formulas

## 11. Implementation Requirements

### 11.1 Gas Calculation

    #![allow(unused)]
    fn main() {
    fn gas_cost_add(n: usize) -> Gas {
        G_BASE + 3 * n
    }

    fn gas_cost_mul(n: usize) -> Gas {
        G_BASE + 2 * n * n
    }

    fn gas_cost_modexp(n: usize, k: usize) -> Gas {
        G_BASE + k * 4 * n * n + 20 * n * n
    }
    }

### 11.2 Precomputation

VM MUST be able to compute gas costs before execution using only:

- Operation type
- Limb count (n)
- Exponent bit length (k)

### 11.3 Error Handling

- Insufficient gas: Transaction rejected
- Gas overflow: Implementation-defined behavior
- Invalid operations: Trap with error

## 12. Security Considerations

### 12.1 DoS Prevention

- Quadratic costs prevent large integer attacks
- Maximum limb limits prevent memory exhaustion
- Gas metering prevents computational DoS

### 12.2 Constant-Time Compatibility

- Gas costs never depend on secret values
- Precomputation doesn't leak timing information
- Compatible with constant-time arithmetic

## 13. Testing and Validation

### 13.1 Gas Cost Verification

    #![allow(unused)]
    fn main() {
    #[test]
    fn test_gas_costs_positive() {
        for n in 1..=MAX_LIMBS {
            assert!(gas_cost_add(n) > 0);
            assert!(gas_cost_mul(n) > 0);
        }
    }

    #[test]
    fn test_gas_costs_increase_with_size() {
        for n in 1..100 {
            assert!(gas_cost_add(n+1) > gas_cost_add(n));
            assert!(gas_cost_mul(n+1) > gas_cost_mul(n));
        }
    }
    }

### 13.2 Performance Correlation

- Gas costs SHOULD correlate with actual CPU cycles
- Benchmark results validate cost model accuracy
- Performance regressions trigger gas schedule review

## 14. Future Extensions

### 14.1 Advanced Operations

Future specifications may add:

- Batch operations with discounted costs
- Hardware-accelerated operations
- Specialized cryptographic primitives

### 14.2 Dynamic Gas Pricing

- Gas costs could become dynamic based on:
  - Network congestion
  - Hardware performance
  - Economic factors

### 14.3 Multi-Precision Extensions

- Support for 32-bit limbs on constrained platforms
- Variable limb sizes for different use cases