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

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