# 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":

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

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

```rust
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<Limb>
- 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