commit 55e3cad8573abf1fd863bb1f430abc51d8bcfcc7
parent 2369bf40de462316cffdfbd50c183766ec7f5ba6
Author: Joris Hartog <jorishartog@hotmail.com>
Date: Thu, 27 Aug 2026 10:45:07 +0200
perf(vdf): fit large proofs to checkpoint budget
Diffstat:
3 files changed, 64 insertions(+), 5 deletions(-)
diff --git a/docs/protocol.md b/docs/protocol.md
@@ -100,7 +100,7 @@ The anchor burn is not a fairness mechanism. By itself, it would mostly help the
The VDF is there to make block production sequential and time-based. It uses a Chia-compatible Wesolowski proof over a class group of imaginary quadratic forms. The 1024-bit class-group discriminant is derived deterministically from the block VDF seed, so the protocol does not rely on an RSA trusted setup or on anyone destroying hidden factors.
-VDF solutions are encoded with the `classgroup-wesolowski-bqfc-v1` prefix followed by two 100-byte Chia BQFC forms in hexadecimal: the output `y` and the Wesolowski proof `pi`. The implementation is Rust-only and has no GMP, MPIR, or other native runtime dependency. Proof generation uses a Chia-compatible checkpoint-and-bucket time-memory tradeoff, with a bounded-memory constant-space fallback for parameter sets that exceed the local allocation limits. Both paths produce the same proof and do not change verification or the wire format. Older RSA-modulus and GMP class-group VDF outputs are not valid for this protocol version.
+VDF solutions are encoded with the `classgroup-wesolowski-bqfc-v1` prefix followed by two 100-byte Chia BQFC forms in hexadecimal: the output `y` and the Wesolowski proof `pi`. The implementation is Rust-only and has no GMP, MPIR, or other native runtime dependency. Proof generation uses a Chia-compatible checkpoint-and-bucket time-memory tradeoff. For large workloads, the prover increases its internal pass count to keep the checkpoints within a fixed memory budget; a bounded-memory constant-space fallback remains available when no checkpoint configuration fits the allocation limits. These internal strategies produce the same proof and do not change verification or the wire format. Older RSA-modulus and GMP class-group VDF outputs are not valid for this protocol version.
In a local Apple Silicon release benchmark, the Rust-only checkpoint prover completed 100,000 rounds in about `0.9s`. Its lower-memory fallback took about `1.8s`, while the official Python/C++ Chia reference took about `0.67s`. These measurements are only a performance snapshot on one machine; they do not affect consensus or the VDF wire format.
diff --git a/docs/security-review.md b/docs/security-review.md
@@ -192,7 +192,9 @@ see which revision was tested.
plus sparse proof buckets that keep empty buckets implicit instead of cloning
full identity forms or composing identity aggregates, and per-pass incremental
checkpoint bucket selection with a 100,000-round checkpoint parameter floor of
- `k = 10`, release thin-LTO/codegen-unit tuning, and replacement of
+ `k = 10`, adaptive multi-pass fitting that keeps normal large workloads within
+ the fixed checkpoint memory budget instead of selecting the constant-memory
+ fallback, release thin-LTO/codegen-unit tuning, and replacement of
per-checkpoint modular exponentiation with one modular exponentiation plus
fixed modular steps; an official
Python/C++ `chiavdf` reference measurement was about `0.673s`. Phase profiling
diff --git a/src/domain/vdf/prover.rs b/src/domain/vdf/prover.rs
@@ -515,14 +515,29 @@ impl ProofParameters {
if rounds >= 100_000 {
k = k.max(10);
}
- let checkpoint_stride = u64::from(k).saturating_mul(l).max(1);
-
Self {
k,
l,
- checkpoint_count: rounds.div_ceil(checkpoint_stride),
+ checkpoint_count: rounds.div_ceil(u64::from(k).saturating_mul(l).max(1)),
bucket_count: 1_u64.checked_shl(k).unwrap_or(u64::MAX),
}
+ .fit_checkpoint_budget(rounds, MAX_CHECKPOINTS)
+ }
+
+ // k and l only select the checkpoint prover's time-memory tradeoff; they do
+ // not affect the resulting Wesolowski proof. Increasing l lets large, honest
+ // protocol workloads stay on the checkpoint path without raising the memory
+ // cap or falling back to a second round-sized sequential pass.
+ fn fit_checkpoint_budget(mut self, rounds: u64, max_checkpoints: u64) -> Self {
+ if max_checkpoints == 0 || self.checkpoint_count <= max_checkpoints {
+ return self;
+ }
+
+ let checkpoint_budget_stride = u64::from(self.k).saturating_mul(max_checkpoints).max(1);
+ self.l = self.l.max(rounds.div_ceil(checkpoint_budget_stride));
+ let checkpoint_stride = u64::from(self.k).saturating_mul(self.l).max(1);
+ self.checkpoint_count = rounds.div_ceil(checkpoint_stride);
+ self
}
}
@@ -562,6 +577,23 @@ mod tests {
}
#[test]
+ fn network_default_rounds_fit_the_checkpoint_memory_budget() {
+ let rounds = u64::from(crate::app::DEFAULT_VDF_ROUNDS);
+ let parameters = ProofParameters::for_rounds(rounds);
+
+ assert_eq!(
+ parameters,
+ ProofParameters {
+ k: 12,
+ l: 22,
+ checkpoint_count: 253_788,
+ bucket_count: 4_096,
+ }
+ );
+ assert!(parameters.checkpoint_count <= super::MAX_CHECKPOINTS);
+ }
+
+ #[test]
fn checkpoint_proof_matches_constant_memory_proof() {
let discriminant = create_discriminant(b"iuna-vdf-checkpoint-differential", 1024).unwrap();
let generator = Form::generator(&discriminant).unwrap();
@@ -613,6 +645,31 @@ mod tests {
}
#[test]
+ fn memory_fitted_checkpoint_proof_matches_constant_memory_proof() {
+ let rounds = 301_u64;
+ let discriminant = create_discriminant(b"iuna-vdf-checkpoint-memory-fit", 1024).unwrap();
+ let generator = Form::generator(&discriminant).unwrap();
+ let threshold = isqrt_fourth(&discriminant.abs());
+ let group = ClassGroup {
+ discriminant: &discriminant,
+ threshold: &threshold,
+ };
+ let parameters = ProofParameters::for_rounds(rounds).fit_checkpoint_budget(rounds, 20);
+
+ assert_eq!(parameters.k, 3);
+ assert_eq!(parameters.l, 6);
+ assert_eq!(parameters.checkpoint_count, 17);
+
+ let checkpoint =
+ prove_checkpointed(group, &generator, rounds, parameters, |_, _| {}).unwrap();
+ let constant_memory =
+ prove_constant_memory(&discriminant, &generator, &threshold, rounds, |_, _| {})
+ .unwrap();
+
+ assert_eq!(checkpoint, constant_memory);
+ }
+
+ #[test]
#[ignore = "manual VDF prover benchmark"]
fn benchmark_checkpoint_prover_against_constant_memory() {
let rounds = 100_000_u64;