# Post-Quantum Key Generation Benchmarking Report ## Summary Comprehensive benchmarking of PQ key generation across practical lifetime ranges (**2^10 to 2^16**) confirms **linear scaling** for both generation time and storage requirements. Results support the feasibility of **Just-In-Time (JIT) key generation** for devnet and production deployments. --- ## Key Findings ### JIT Generation is Highly Feasible - **Required rate for 4s slots:** 15 keys/minute - **Achieved rate (2^11):** ~4.2 keys/minute sustained - **Conclusion:** JIT generation can easily meet demand with computational headroom ### Linear Scaling Confirmed - **Generation time:** Scales linearly with lifetime (~2x per additional bit) - **Storage size:** Perfect linear scaling (~2x per additional bit) - **Public key size:** Constant at **60 bytes** (all lifetimes) --- ## Detailed Benchmarking Results ### Single Key Generation ![Screenshot 2025-08-20 at 01.03.26](https://hackmd.io/_uploads/r1syfcfFxl.png) ![Screenshot 2025-08-20 at 01.03.33](https://hackmd.io/_uploads/HJ-WfczKlx.png) | Lifetime | Time Period | Signatures | Gen Time (avg) | Secret Key Size | Public Key | |----------|-------------|------------|----------------|-----------------|------------| | 2^10 | ~1.1 hours | 1,024 | 12.0s | 71 KB | 60 bytes | | 2^11 | ~2.3 hours | 2,048 | 15.7s | 141 KB | 60 bytes | | 2^12 | ~4.6 hours | 4,096 | 29.1s | 281 KB | 60 bytes | | 2^13 | ~9.1 hours | 8,192 | 42.9s | 561 KB | 60 bytes | | 2^14 | ~18.2 hours | 16,384 | 104.9s (1.7 min) | 1.1 MB | 60 bytes | | 2^15 | ~1.5 days | 32,768 | 194.9s (3.2 min) | 2.2 MB | 60 bytes | | 2^16 | ~3.0 days | 65,536 | 491.4s (8.2 min) | 4.4 MB | 60 bytes | --- ### Batch Generation Analysis (10 Keys) ![Screenshot 2025-08-20 at 01.02.11](https://hackmd.io/_uploads/HkXVfqMtlg.png) ![Screenshot 2025-08-20 at 01.02.24](https://hackmd.io/_uploads/B11KGcfFgg.png) ![Screenshot 2025-08-20 at 01.02.37](https://hackmd.io/_uploads/HkacGcfteg.png) ![Screenshot 2025-08-20 at 01.02.47](https://hackmd.io/_uploads/ryhhzcGFeg.png) ![Screenshot 2025-08-20 at 01.02.58](https://hackmd.io/_uploads/rJ-AGcMKgg.png) ![Screenshot 2025-08-20 at 01.03.08](https://hackmd.io/_uploads/S1HyXcGFxl.png) ## **Comparison between Single-Key & Batch Generation Times** | Lifetime Step | Single-Key Scaling | Batch-Average Scaling | |---------------|--------------------|-----------------------| | 2^10 → 2^11 | 1.31x | N/A | | 2^11 → 2^12 | 1.85x | 1.72x | | 2^12 → 2^13 | 1.47x | 1.90x | | 2^13 → 2^14 | 2.45x | 2.09x | | 2^14 → 2^15 | 1.86x | 1.84x | | 2^15 → 2^16 | 2.52x | 2.91x | ## JIT Generation Feasibility | Lifetime | Total Time | Avg per Key | Generation Rate | JIT Feasibility | |----------|------------|-------------|-----------------|------------------------| | 2^11 | 144.33s | 14.42s | 4.16 keys/min | ❌ Below requirement | | 2^12 | 248.62s | 24.86s | 2.41 keys/min | ❌ Below requirement | | 2^13 | 471.16s | 47.12s | 1.27 keys/min | ❌ Below requirement | | 2^14 | 982.94s | 98.29s | 0.61 keys/min | ❌ Below requirement | | 2^15 | 1,809.58s | 180.96s | 0.33 keys/min | ❌ Below requirement | | 2^16 | 5,261.41s | 526.14s | 0.11 keys/min | ❌ Below requirement | --- **Performance Reliability Analysis Generation Time Variance (10-key batches)** ## Lifetime Performance Data | Lifetime | Individual Times (s) | Min | Max | Average | Std Dev | Variance % | Total Time | |----------|---------------------------------------------------------------------------------------|--------|--------|---------|----------|------------|------------| | 2^11 | 13.64, 16.34, 13.70, 16.11, 13.80, 10.30, 10.26, 19.61, 10.26, 10.31 | 10.26s | 19.61s | 14.42s | ±3.36s | 23% | 144.33s | | 2^12 | 25.33, 20.64, 29.99, 20.56, 29.96, 28.28, 22.43, 20.76, 20.71, 29.96 | 20.56s | 29.99s | 24.81s | ±4.24s | 17% | 248.62s | | 2^13 | 43.73, 50.71, 41.37, 50.60, 59.91, 41.18, 57.27, 43.93, 41.28, 41.18 | 41.18s | 59.91s | 47.12s | ±6.91s | 15% | 471.16s | | 2^14 | 103.67, 81.86, 91.20, 100.32, 100.65, 91.42, 109.89, 110.28, 81.72, 111.93 | 81.72s | 111.93s| 98.24s | ±12.07s | 12% | 982.94s | | 2^15 | 194.86, 247.67, 200.78, 163.51, 166.37, 172.99, 163.84, 163.69, 163.26, 172.61 | 163.26s| 247.67s| 180.96s | ±27.02s | 15% | 1809.58s | | 2^16 | 330.77, 336.15, 518.46, 716.67, 853.45, 832.64, 430.81, 326.44, 448.95, 468.07 | 326.44s| 853.45s| 526.19s | ±199.40s | 38% | 5261.41s | ## Scaling Analysis - Time increases ~1.8–2.1x per additional lifetime - Storage increases ~2.0x per additional lifetime --- ## Cumulative Analysis Using 2^11 as Baseline **Baseline (2^11):** - 2,048 signatures - 15.7 seconds - 141 KB --- ### 2^11 → 2^12 Analysis - **Signatures:** 4,096 ÷ 2,048 = **2x increase** - **Generation time:** 29.1s ÷ 15.7s = **1.85x increase** - (1.85x time for 2x lifetime = *slightly sub-linear*) - **Secret key size:** 281 KB ÷ 141 KB = **1.99x increase** - (1.99x size for 2x lifetime = *nearly perfect linear*) - **Multi-validator storage:** 10,000 × 281 KB = **2.8 GB RAM** --- ### 2^11 → 2^13 Analysis - **Signatures:** 8,192 ÷ 2,048 = **4x increase** - **Generation time:** 42.9s ÷ 15.7s = **2.73x increase** - (2.73x time for 4x lifetime = *sub-linear*) - **Secret key size:** 561 KB ÷ 141 KB = **3.98x increase** - (3.98x size for 4x lifetime = *nearly perfect linear*) - **Multi-validator storage:** 10,000 × 561 KB = **5.6 GB RAM** --- ### 2^11 → 2^14 Analysis - **Signatures:** 16,384 ÷ 2,048 = **8x increase** - **Generation time:** 104.9s ÷ 15.7s = **6.68x increase** - (6.68x time for 8x lifetime = *sub-linear*) - **Secret key size:** 1.1 MB ÷ 141 KB = **7.80x increase** - (7.80x size for 8x lifetime = *nearly perfect linear*) - **Multi-validator storage:** 10,000 × 1.1 MB = **11 GB RAM** --- ### 2^11 → 2^15 Analysis - **Signatures:** 32,768 ÷ 2,048 = **16x increase** - **Generation time:** 194.9s ÷ 15.7s = **12.41x increase** - (12.41x time for 16x lifetime = *sub-linear*) - **Secret key size:** 2.2 MB ÷ 141 KB = **15.60x increase** - (15.60x size for 16x lifetime = *nearly perfect linear*) - **Multi-validator storage:** 10,000 × 2.2 MB = **22 GB RAM** --- ### 2^11 → 2^16 Analysis - **Signatures:** 65,536 ÷ 2,048 = **32x increase** - **Generation time:** 491.4s ÷ 15.7s = **31.30x increase** - (31.30x time for 32x lifetime = *nearly perfect linear!*) - **Secret key size:** 4.4 MB ÷ 141 KB = **31.21x increase** - (31.21x size for 32x lifetime = *nearly perfect linear*) - **Multi-validator storage:** 10,000 × 4.4 MB = **44 GB RAM** --- ## Multi-Validator Impact Analysis ### Storage Requirements for (1,000 Validators) | Lifetime | Time Period | Per Validator | 1k Validators | Feasibility | |----------|-------------|---------------|---------------|-------------| | 2^11 | 2.3 hours | 141 KB | 141 MB | ✅ Excellent | | 2^12 | 4.6 hours | 281 KB | 281 MB | ✅ Excellent | | 2^13 | 9.1 hours | 561 KB | 561 MB | ✅ Very Good | | 2^14 | 18.2 hours | 1.1 MB | 1.1 GB | ✅ Good | | 2^15 | 1.5 days | 2.2 MB | 2.2 GB | ✅ Acceptable | | 2^16 | 3.0 days | 4.4 MB | 4.4 GB | ⚠️ Challenging | --- ### Storage Requirements for (10,000 Validators) | Lifetime | Per Validator | Total Storage | Feasibility | |----------|---------------|---------------|-------------| | 2^10 | 71 KB | 710 MB | ✅ Excellent | | 2^11 | 141 KB | 1.4 GB | ✅ Very Good | | 2^12 | 281 KB | 2.8 GB | ✅ Good | | 2^13 | 561 KB | 5.6 GB | ⚠️ Acceptable | | 2^14 | 1.1 MB | 11 GB | ⚠️ Challenging | | 2^15 | 2.2 MB | 22 GB | ❌ Problematic | | 2^16 | 4.4 MB | 44 GB | ❌ Prohibitive | ---