kyn-vdf

A pure Rust, WebAssembly-native Wesolowski Verifiable Delay Function (VDF) verifier over Imaginary Quadratic Class Groups.

Overview

Verifiable Delay Functions (VDFs) require a prover to spend non-parallelizable sequential time evaluating a mathematical function, while allowing anyone to verify the output in exponentially faster time $\mathcal{O}(\log T)$.

Until now, the open-source ecosystem lacked a pure Rust, zero-FFI implementation capable of verifying Chia-compatible Wesolowski VDF proofs. Reference implementations relied on C++ binaries and libgmp, preventing execution in:

• WebAssembly (WASM) & In-Browser Light Clients
• Native Mobile Apps (iOS & Android) without complex C++ NDK cross-compilation
• Smart Contracts (CosmWasm, Substrate, Solana, NEAR)
• Embedded & Pure Rust Environments

kyn-vdf provides an independent, clean-room, 100% pure Rust implementation of binary quadratic class group arithmetic and Wesolowski verification, running seamlessly in any environment.

Key Features

• Pure Rust / Zero FFI: Built on safe, arbitrary-precision arithmetic (num-bigint). Zero C/C++, GMP, or OS dependencies.
• WASM Native: Compiles out-of-the-box to wasm32-unknown-unknown for web browsers and mobile wallets.
• Shanks' NUCOMP & NUDUPL: Implements sub-quadratic binary quadratic form composition and squaring with partial Euclidean reduction.
• Asymptotic Verification ($\mathcal{O}(\log T)$): Verification takes constant logarithmic time ($\sim 100\text{ ms}$), even when proofs took minutes or hours to generate.
• Chia-Compatible: 100% test-vector compatible with Chia Network's reference 1024-bit class group VDF specification.
• Fuzzing & Property Tested: Hardened with proptest and cargo-fuzz against malformed inputs and boundary conditions.

Benchmarks

All numbers below are real measurements from cargo bench and the chiavdf C++ reference prover running on the same machine. Reproduce them yourself:

# Pure Rust verification
cargo bench

# C++ prove times (requires kinetic-vdf with chiavdf)
cargo run --release --bin prove_timing -p kinetic-vdf

Test Machine

• CPU: 11th Gen Intel Core i5-11400H @ 2.70GHz (6 Cores, 12 Threads)
• RAM: 16 GB DDR4
• OS / Target: Linux 6.x / x86_64-unknown-linux-gnu
• Discriminant: 1024-bit fundamental negative prime discriminant $D = -p$

Class Group Arithmetic (per operation)

Prove vs. Verify — Full Comparison

Reading the table honestly:

• The C++ chiavdf verifier (~14–19 ms) is faster than kyn-vdf (~82–93 ms) — it uses libgmp, an optimized C++ big-integer library. That's the cost of zero FFI and WASM compatibility.
• Despite being ~5× slower than C++ verify, kyn-vdf still verifies 43× faster than C++ can prove at T=500,000.
• Once $T \geq 1{,}000$, kyn-vdf verification is flat at ~82–93 ms regardless of how large $T$ grows — confirming the $\mathcal{O}(\log T)$ guarantee.
• At T=100, pure Rust is actually faster than C++ verify (12.70 ms vs 14.80 ms) because $2^{100} < B$, making $r$ a smaller number.

Installation

Add kyn-vdf to your Cargo.toml:

[dependencies]
kyn-vdf = "0.1"

Quick Start

1. One-Step Verification

Verify a 1024-bit Chia-compatible proof in one function call:

use kyn_vdf::verify_chia_vdf;

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let challenge = [0x42u8; 32];
    let proof_bytes: Vec<u8> = get_proof_from_network(); // 200 bytes: y || π
    let iterations = 500_000u64;

    let is_valid = verify_chia_vdf(&challenge, &proof_bytes, iterations, 1024)?;
    if is_valid {
        println!("✅ VDF Proof mathematically verified!");
    } else {
        println!("❌ Invalid proof rejected.");
    }

    Ok(())
}

2. Low-Level Class Group Arithmetic

Directly manipulate binary quadratic forms $(a, b, c)$ with Shanks' NUCOMP/NUDUPL:

use kyn_vdf::math::Form;
use kyn_vdf::chia::create_discriminant;
use num_bigint::BigInt;

fn main() {
    let seed = b"kyn-vdf-seed";
    let discriminant = create_discriminant(seed, 1024);

    // Canonical generator element (2, 1, c)
    let g = Form::generator(&discriminant).expect("valid generator");

    // Fast squaring via Shanks' NUDUPL + Gauss reduction
    let g2 = g.square(&discriminant);

    // Fast composition via Shanks' NUCOMP
    let g3 = g.compose(&g2, &discriminant);

    assert!(g3.is_reduced());
}

WebAssembly Support

kyn-vdf has zero native dependencies and compiles cleanly to WebAssembly:

cargo build --target wasm32-unknown-unknown --release

Security & Formal Testing

• Property Testing: tests/proptest_math.rs validates group axioms (identity, associativity, inverse, and exponentiation) using proptest.
• Differential Fuzzing: fuzz/fuzz_targets/fuzz_vdf.rs continuously fuzzes deserialization and verification against malformed/arbitrary byte streams:

  cargo +nightly fuzz run fuzz_vdf
  

• Negative Testing: Strict validation ensures zero false positives on flipped bits, incorrect iteration counts, or non-reduced forms.

Academic References

1. Benjamin Wesolowski (2018): "Efficient Verifiable Delay Functions". ePrint 2018/623.
2. Daniel Shanks (1989): "On Gauss and Composition I, II". Algorithmic NUCOMP and NUDUPL for quadratic forms.
3. Henri Cohen (1993): "A Course in Computational Algebraic Number Theory", Springer-Verlag GTM 138 (Algorithms for Binary Quadratic Forms).
4. Chia Network: Reference C++ implementation (chiavdf).

License

Dual-licensed under your choice of:

• MIT License (LICENSE-MIT)
• Apache License, Version 2.0 (LICENSE-APACHE)

This is the standard dual-licensing approach used by the majority of the Rust ecosystem.