# 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
```rust
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
| 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
| Bit shift | `G_shift(n) = 2n` | Barrel shift implementation |
## 3. Multiplication Costs
### 3.1 Multiplication Variants
| 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
| 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
| 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
| 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
| 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
```rust
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
| 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
```rust
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
```rust
#[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