Gas Schedule v1.0 - ClockinChain Big Integer Specifications
Description: Normative specifications for ClockinChain big integer arithmetic

# Gas Schedule Specification v1.0

## Overview

This specification defines the normative gas cost constants for all BigInt arithmetic operations, ensuring deterministic, precomputable metering for the ClockinChain VM.

## 1. Design Principles

### 1.1 Gas Cost Properties

1. Public parameters only: Gas cost depends only on public limb length
2. No secret dependency: Never depends on operand values
3. Linear/quadratic scaling: Simple mathematical formulas
4. Constant-time compatible: Compatible with constant-time execution
5. Precomputable: VM can compute costs before execution
6. DoS protection: Prevents arithmetic-based denial-of-service

### 1.2 Base Definitions

    #![allow(unused)]
    fn main() {
    const G_BASE: Gas = 10;  // Baseline dispatch cost unit
    let n: usize = limb_count;
    let k: usize = exponent_bit_length;
    }

All costs below are added to `G_BASE`.

## 2. Core Arithmetic Costs

### 2.1 Addition and Subtraction

Operation | Formula | Notes
--- | --- | ---
Addition | `G_add(n) = 3n` | Carry chain propagation
Subtraction | `G_sub(n) = 3n` | Borrow chain propagation
Negation | `G_neg(n) = 2n` | Two's complement
Comparison | `G_cmp(n) = 2n` | Full limb comparison

### 2.2 Bitwise Operations

Operation | Formula | Notes
--- | --- | ---
Bit shift | `G_shift(n) = 2n` | Barrel shift implementation

## 3. Multiplication Costs

### 3.1 Multiplication Variants

Operation | Formula | Notes
--- | --- | ---
Multiply | `G_mul(n) = 2n²` | Comba/Karatsuba
Square | `G_sqr(n) = 1.6n²` | Optimized for squaring
Multiply-Accumulate | `G_mac(n) = 2n²` | Internal operation

### 3.2 Algorithm Selection

- Comba method for small operands (n ≤ 16)
- Karatsuba method for large operands (n > 16)
- Cost formula covers both algorithms

## 4. Division and Modulo

### 4.1 Division Operations

Operation | Formula | Notes
--- | --- | ---
Division | `G_div(n) = 4n²` | Knuth long division
Modulo | `G_mod(n) = 4n²` | Same cost as division
DivMod | `G_divmod(n) = 4n²` | Shared computation

### 4.2 Division Algorithm

- Knuth Algorithm D with constant-time corrections
- Quadratic complexity due to digit-by-digit approach
- Includes normalization and denormalization steps

## 5. Montgomery Domain Operations

### 5.1 Montgomery Arithmetic

Operation | Formula | Notes
--- | --- | ---
MontReduce | `G_mred(n) = n²` | Reduction loop
MontMul | `G_mmul(n) = 2n²` | Mul + Reduce
MontAdd/Sub | `G_madd(n) = 3n` | + conditional reduction
ToMont | `G_tomont(n) = 2n²` | Using R²
FromMont | `G_frommont(n) = n²` | Reduction only

### 5.2 Modular Exponentiation

Ladder Cost Formula:

    G_modexp(n, k) = k × (G_mmul(n) + G_mmul(n)) + G_setup
                   = k × 4n² + 20n²

Where:

- `k` = exponent bit length
- Ladder performs 2 multiplications per bit
- Setup cost covers Montgomery context creation

## 6. Modular Inverse

### 6.1 Inverse Methods

Method | Cost | Notes
--- | --- | ---
Binary GCD | `G_inv_gcd(n) = 6n²` | Constant-time bounds
Via ModExp | `G_modexp(n, n)` | For prime moduli

### 6.2 Binary GCD Algorithm

- Extended Euclidean algorithm
- Fixed iteration bounds based on limb count
- Constant-time implementation

## 7. Encoding and Serialization

### 7.1 Encoding Operations

Operation | Formula | Notes
--- | --- | ---
Canonicalize | `G_canon(n) = n` | Remove leading zeros
Encode | `G_enc(n) = n` | Serialize to bytes
Decode | `G_dec(n) = n` | Deserialize from bytes

### 7.2 Encoding Format

Binary format: `[sign: u8][limb_count: u32 LE][limbs: u64[] LE]`

## 8. Global Limits

### 8.1 Maximum Size Limits

    #![allow(unused)]
    fn main() {
    const MAX_LIMBS: usize = 512;  // 32768-bit integers
    }

- Prevents denial-of-service attacks
- Operations exceeding this MUST trap before execution

### 8.2 Overflow Handling

- Fixed-length BigInt: Trap on overflow
- Dynamic BigInt: Error on exceeding capacity

## 9. Example Costs

### 9.1 Common Sizes

Operation | 256-bit (n=4) | 2048-bit (n=32)
--- | --- | ---
Add | 12 | 96
Mul | 32 | 2048
MontMul | 32 | 2048
Div | 64 | 4096
ModExp (256-bit exp) | ~32768 | ~8.3M
ModExp (2048-bit exp) | ~131072 | ~33.5M

### 9.2 Gas Budget Considerations

For typical blockchain operations:

- Simple transfers: ~50 gas
- ECDSA signature verification: ~100K gas
- Modular exponentiation (2048-bit): ~10M gas

## 10. Governance and Updates

### 10.1 Gas Schedule Adjustments

- Gas constants may be adjusted by chain governance
- Must maintain linear/quadratic form constraints
- Updates require consensus approval

### 10.2 Backward Compatibility

- Gas costs can only increase (never decrease)
- New operations can be added with appropriate costs
- Existing operations maintain cost formulas

## 11. Implementation Requirements

### 11.1 Gas Calculation

    #![allow(unused)]
    fn main() {
    fn gas_cost_add(n: usize) -> Gas {
        G_BASE + 3 * n
    }

    fn gas_cost_mul(n: usize) -> Gas {
        G_BASE + 2 * n * n
    }

    fn gas_cost_modexp(n: usize, k: usize) -> Gas {
        G_BASE + k * 4 * n * n + 20 * n * n
    }
    }

### 11.2 Precomputation

VM MUST be able to compute gas costs before execution using only:

- Operation type
- Limb count (n)
- Exponent bit length (k)

### 11.3 Error Handling

- Insufficient gas: Transaction rejected
- Gas overflow: Implementation-defined behavior
- Invalid operations: Trap with error

## 12. Security Considerations

### 12.1 DoS Prevention

- Quadratic costs prevent large integer attacks
- Maximum limb limits prevent memory exhaustion
- Gas metering prevents computational DoS

### 12.2 Constant-Time Compatibility

- Gas costs never depend on secret values
- Precomputation doesn't leak timing information
- Compatible with constant-time arithmetic

## 13. Testing and Validation

### 13.1 Gas Cost Verification

    #![allow(unused)]
    fn main() {
    #[test]
    fn test_gas_costs_positive() {
        for n in 1..=MAX_LIMBS {
            assert!(gas_cost_add(n) > 0);
            assert!(gas_cost_mul(n) > 0);
        }
    }

    #[test]
    fn test_gas_costs_increase_with_size() {
        for n in 1..100 {
            assert!(gas_cost_add(n+1) > gas_cost_add(n));
            assert!(gas_cost_mul(n+1) > gas_cost_mul(n));
        }
    }
    }

### 13.2 Performance Correlation

- Gas costs SHOULD correlate with actual CPU cycles
- Benchmark results validate cost model accuracy
- Performance regressions trigger gas schedule review

## 14. Future Extensions

### 14.1 Advanced Operations

Future specifications may add:

- Batch operations with discounted costs
- Hardware-accelerated operations
- Specialized cryptographic primitives

### 14.2 Dynamic Gas Pricing

- Gas costs could become dynamic based on:
  - Network congestion
  - Hardware performance
  - Economic factors

### 14.3 Multi-Precision Extensions

- Support for 32-bit limbs on constrained platforms
- Variable limb sizes for different use cases