# 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
```rust
// 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
```rust
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
```rust
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
```rust
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
```rust
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
```rust
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
```rust
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
```rust
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
```rust
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
```rust
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
| 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