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

2.2 Bitwise Operations

3. Multiplication Costs

3.1 Multiplication Variants

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

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

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

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

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

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