# clock-bigint

**Deterministic constant-time big integers for blockchain consensus engines.**

[![Documentation](https://docs.rs/clock-bigint/badge.svg)](https://docs.rs/clock-bigint)
[![License](https://img.shields.io/badge/license-MIT%2FApache--2.0-blue.svg)](LICENSE)

## Overview

`clock-bigint` is a production-ready big integer crate that implements the complete ClockinChain Big Integer 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

## Features

- ✅ **No_std compatible**: Works in embedded and WASM environments (default)
- ✅ **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
- ✅ **ZK support**: Constraint-emitting backend for zero-knowledge proofs (feature-gated)

## Quick Start

```rust
use clock_bigint::{U256, BigInt, add, mul};

// Fixed-length BigInt (256-bit) - works in no_std
let a = U256::from_u64(10);
let b = U256::from_u64(20);

// Dynamic-length BigInt - requires alloc feature
let mut x = BigInt::from_u64(42, 512); // max 512 limbs
let y = BigInt::from_u64(100, 512);

// Arithmetic operations
let sum = add(&x, &y).unwrap();
let product = mul(&x, &y).unwrap();
```

## Montgomery Arithmetic

```rust
use clock_bigint::{MontgomeryContext, to_mont, from_mont, mont_mul, mod_pow};

// Create Montgomery context for modulus - requires alloc feature
let modulus = BigInt::from_u64(97, 10); // Must be odd
let ctx = MontgomeryContext::new(modulus).unwrap();

// Convert to Montgomery form
let a = BigInt::from_u64(5, 10);
let a_mont = to_mont(&ctx, &a).unwrap();

// Montgomery multiplication
let b = BigInt::from_u64(7, 10);
let b_mont = to_mont(&ctx, &b).unwrap();
let c_mont = mont_mul(&ctx, &a_mont, &b_mont).unwrap();

// Convert back
let c = from_mont(&ctx, &c_mont).unwrap();
// c = (5 * 7) mod 97 = 35

// Modular exponentiation
let exponent = BigInt::from_u64(3, 10);
let result = mod_pow(&ctx, &a, &exponent).unwrap();
// result = 5^3 mod 97 = 125 mod 97 = 28
```

## Canonical Encoding

```rust
use clock_bigint::{encode, decode, BigInt};

let value = BigInt::from_u64(42, 10);

// Encode to canonical binary format - requires alloc feature
let encoded = encode(&value);
// Format: [sign: u8][limb_count: u32 LE][limbs: u64[] LE]

// Decode with validation
let decoded = decode(&encoded).unwrap();
assert_eq!(decoded.limbs()[0], 42);
```

## Gas Metering

```rust
use clock_bigint::gas;

// Calculate gas cost for operations
let n = 4; // 256-bit (4 limbs)
let add_cost = gas::cost_add(n);
let mul_cost = gas::cost_mul(n);
let modexp_cost = gas::cost_modexp(n, 256); // 256-bit exponent

// All costs are deterministic and precomputable
```

## Type Aliases

```rust
use clock_bigint::{U256, U512, U1024, U2048};

// Fixed-width types for common sizes
let x: U256 = U256::from_u64(42);
let y: U512 = U512::from_u64(100);
```

## Features

- `alloc` - Dynamic BigInt support with heap allocation (default)
- `zk` - Enable ZK constraint backend
- `serde` - Serialization support
- `std` - Alias for `alloc` (compatibility)
- `bench` - Benchmarking infrastructure
- `fuzz` - Fuzzing targets

### Feature Overview

| Feature    | Fixed-size BigInts | Dynamic BigInts | Montgomery | Encoding | Timeboxed |
|------------|-------------------|-----------------|------------|----------|-----------|
| **default** | ✅                | ✅              | ✅         | ✅       | ✅        |
| **no-alloc**| ✅                | ❌              | ❌         | ❌       | ❌        |

**Default (no_std + alloc)**: Full functionality with optional heap allocation
**No-alloc**: Only fixed-size operations for constrained environments

## Specifications

This crate implements the following normative specifications:

1. **ClockinChain Big Integer Representation Specification v1.0**
   - Fixed 64-bit limbs in little-endian order
   - Canonical form enforcement
   - Zero representation rules

2. **Arithmetic Algorithm Specification v1.0**
   - Constant-time addition (adc algorithm)
   - Constant-time subtraction (sbb algorithm)
   - Comba/Karatsuba multiplication
   - Knuth D division

3. **Montgomery & Modular Exponentiation Specification v1.0**
   - Montgomery reduction
   - Montgomery multiplication
   - Montgomery ladder exponentiation

4. **Gas Schedule Specification v1.0**
   - Deterministic cost functions
   - Precomputable gas metering
   - DoS protection (MAX_LIMBS = 512)

## No-Std Usage

For embedded systems, WASM, or other constrained environments:

```rust
// In Cargo.toml
[dependencies]
clock-bigint = { version = "1.0", default-features = false }

// In your code
use clock_bigint::{U256, BigIntCore};

// Only fixed-size BigInts available (no heap allocation)
let a: U256 = U256::from_u64(42);
let b: U256 = U256::from_u64(100);

// Arithmetic through BigIntCore trait
assert_eq!(a.limb_count(), 4);
assert_eq!(b.limb_count(), 4);
```

To enable dynamic BigInts and cryptographic operations:

```toml
[dependencies]
clock-bigint = { version = "1.0", features = ["alloc"] }
```

## Performance Targets

- 256-bit add: ~8 cycles
- 256-bit mul: ~40 cycles
- 2048-bit modexp: within 10% of GMP
- Deterministic across platforms: Guaranteed

## Safety

This crate is designed for cryptographic and consensus-critical applications:

- **No_std compatible**: Works in embedded and WASM environments
- **Constant-time**: No secret-dependent branches or memory accesses
- **Deterministic**: Identical results across all platforms
- **Canonical**: Unique encoding prevents consensus malleability
- **Audited**: Designed for security review

## License

Licensed under either of:

- Apache License, Version 2.0 ([LICENSE-APACHE](LICENSE-APACHE) or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license ([LICENSE-MIT](LICENSE-MIT) or http://opensource.org/licenses/MIT)

at your option.

## Contribution

Contributions are welcome! Please see [CONTRIBUTING.md](CONTRIBUTING.md) for guidelines.

## References

- [ClockinChain Big Integer Representation Specification v1.0](spec/representation.md)
- [Arithmetic Algorithm Specification v1.0](spec/arithmetic.md)
- [Montgomery & Modular Exponentiation Specification v1.0](spec/montgomery.md)
- [Gas Schedule Specification v1.0](spec/gas.md)
