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