Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

kyn-vdf: Imaginary Quadratic Class Groups Math Core

Crate: kyn-vdf Stage: 2 Reading Time: 40 minutes Depends On: 01_vdf_overview.md (Conceptual overview of VDFs)

What Is This?

This document breaks down the mathematical foundation of the Verifiable Delay Function (VDF) implementation in the Kinetic network. Specifically, it provides an explanation of the mathematical operations over Imaginary Quadratic Class Groups. These class groups provide the non-parallelizable, deterministic time-delay necessary for our network’s consensus mechanism to function safely. This file specifically documents the core operations found in kyn-vdf/src/math.rs (lines 1-226). It acts as the strict foundational bedrock for the entire cryptographic pipeline. It defines binary quadratic forms, encompassing arbitrary precision arithmetic, Shanks NUCOMP threshold calculations, partial Euclidean steps, and Gauss reduction algorithms. All of this is implemented in purely deterministic Rust code to ensure cross-network consensus stability and bit-for-bit accuracy. Without the precise mathematics in this file, Kinetic would not be able to securely elect block producers. It would also fail to verify elapsed time in a decentralized manner, which is the entire premise of the Kinetic network. This math forms the strict computational wall that prevents attackers from rushing or manipulating the network’s internal clock. It is the heart of the Kinetic VDF and the absolute source of truth for the entire sequence of squarings. Understanding this file is for anyone working on the consensus layer. It marries advanced algebraic number theory with low-level systems engineering.

Why Kinetic Needs This

At the very heart of Kinetic’s network security model is the Verifiable Delay Function (VDF). A VDF is a cryptographic primitive that guarantees that a certain amount of sequential computational time has unequivocally elapsed. This verifiable proof of elapsed time is crucial for preventing malicious actors from rushing the consensus process. In a proof-of-stake system like Kinetic, unpredictable randomness is required to elect leaders safely and fairly. If the randomness generation is instant, attackers can simulate thousands of forks and pick the one where they win the election. A VDF acts as an “randomness beacon” for the entire network. It prevents attackers from predicting or manipulating future block producers by forcing a , unavoidable time delay on the randomness generation.

To achieve this sequential delay, we need a mathematical structure known as a “group of unknown order”. In a group of known order, an attacker can use shortcut calculations (like Euler’s theorem) to compute the final result instantly. By bypassing the sequential delay entirely, the VDF loses its primary property and the network becomes vulnerable to immediate takeover. While standard RSA groups are indeed of unknown order, they come with a fatal flaw: they require a trusted setup.

Warning

A trusted setup means a trusted party must generate the prime factors and then securely destroy them. This represents a centralization risk and a single point of failure that Kinetic refuses to accept.

Imaginary Quadratic Class Groups offer a elegant, trustless alternative to RSA. We can generate a class group of unknown order simply by using a large negative prime number. This number is called a fundamental discriminant, commonly denoted as $D$. Because $D$ is just a prime number (which can be deterministically derived from a block hash), this entirely eliminates the need for a trusted setup phase. This preserves the true, permissionless decentralization of the Kinetic network from the genesis block onwards.

However, this mathematical elegance comes with heavy, engineering requirements. First, we must deal with integers to maintain robust cryptographic security against modern hardware and ASICs. For a standard 128-bit cryptographic security level, our discriminant $D$ needs to be a negative prime number that is thousands of bits long. Typically, in the Kinetic protocol, this means a 1024-bit or 2048-bit negative prime integer. Standard Rust primitive types like u64 or u128 simply cannot hold values of this enormous magnitude. This is exactly why we depend on the num-bigint crate to handle all values as heap-allocated BigInt objects. Without BigInt, we would not be able to store our parameters, let alone perform multi-million iteration squarings on them. These objects dynamically allocate memory to store as many bits as required for the calculation.

Second, the system demands absolute, bit-perfect determinism across the entire global network. Kinetic is a decentralized network running on heterogeneous hardware, from cloud servers to desktop PCs. When a node computes a VDF proof, every other node in the network must be able to verify it independently. They must arrive at the exact same mathematical conclusion down to the final bit, without exception. This means we cannot rely on floating-point arithmetic for any part of the calculation. Standard operations like f64::sqrt() are forbidden in our consensus-critical code. Floating-point precision, rounding behavior, and NaN handling can vary subtly between different CPU architectures (such as x86 vs ARM). Furthermore, different compiler optimizations can alter the order of operations, changing the final result of floating-point math. If nodes disagree on the result of a math operation by even a single bit, the network would instantly fork and fail to reach consensus. Therefore, every single calculation in math.rs must be , integer-based.

Finally, we need extreme, performance. VDFs are evaluated continuously by nodes, requiring billions of sequential squaring operations to prove elapsed time. If our BigInt math is inefficient, the baseline delay becomes artificially inflated. The sequential delay would be caused by memory allocations and garbage collection rather than actual cryptographic operations. This is why you will see a heavy reliance on passing variables by reference (e.g., &BigInt) rather than taking ownership. Taking ownership causes cloning, which means allocating new space on the heap, copying bytes, and eventually dropping the memory. Minimizing these costly heap allocations during the billions of additions and multiplications is a top architectural priority for kyn-vdf. Every single microsecond saved in the math core translates directly to a faster, more secure network. By passing immutable and mutable references , we allow the compiler to reuse memory allocations.

How It Works

The entire mathematical mechanism of the class group operates on structures known as “Binary Quadratic Forms”. A binary quadratic form is a homogeneous polynomial of degree two in two variables. Specifically, it takes the form $f(x, y) = ax^2 + bxy + cy^2$. In our codebase, we typically represent this polynomial simply as a tuple of its coefficients: (a, b, c). For a given negative discriminant $D$, these forms operate as the group elements of our cryptographic class group. The equivalence classes of these forms under modular transformations form a finite abelian group. This mathematical group provides the exact algebraic structure needed to chain squaring operations for the VDF.

In kyn-vdf/src/math.rs, the code is structured into a tight pipeline that supports two main operations. The first operation is composing two forms together (or squaring a form with itself). The second operation is reducing a form back to its canonical, minimal representation. Because the coefficients grow fast when composing forms, we use a sophisticated algorithm. This algorithm is called Shanks NUCOMP, and it keeps the coefficients as small as possible throughout the intermediate steps of the computation. Let’s walk through the exact flow of the code from lines 1 to 226 in extensive detail to understand this pipeline.

1. Calculating the NUCOMP Threshold

-> See: kyn-vdf/src/math.rs — Lines 10 to 45

When we compose two quadratic forms , the resulting coefficients can grow exceptionally large. Without optimization, they can easily grow to the size of $D^2$, which ruins cache locality and dramatically reduces performance. Shanks NUCOMP is a algorithmic optimization that performs a partial reduction during the composition step itself, rather than waiting until the end. By reducing early, it prevents the intermediate numbers from ever getting that large in memory, speeding up the overall calculation.

To know exactly when to stop this partial reduction, the NUCOMP algorithm requires a specific threshold value, usually denoted as $L$. This threshold is defined as the fourth root of the absolute value of the discriminant: $L = |D|^{1/4}$. In lines 10-45, we implement the isqrt_fourth(n) function to calculate this critical threshold. Because we are forbidden from using floating point math for consensus, this function computes the integer square root twice in succession. Applying the integer square root twice yields the integer fourth root exactly. It uses a purely deterministic Newton-Raphson method adapted for integer arithmetic. The algorithm starts with an initial, conservative guess and iteratively refines it using integer division and averaging. By staying entirely in integer space, we guarantee perfect consistency across all platforms. We ensure that every single Kinetic node calculates the exact same threshold $L$, down to the last bit. This is true regardless of whether the node is running on a high-end Intel server or a low-power ARM device. The function is written carefully to manage memory by reusing local mutable variables during the Newton-Raphson loop, avoiding excess allocations. It ensures that the fourth root calculation, while slightly slower than a hardware floating point equivalent, is 100% deterministic. This function is a great example of rewriting standard math primitives exclusively for cryptographic contexts.

2. The Partial Extended Euclidean Algorithm

-> See: kyn-vdf/src/math.rs — Lines 47 to 95

The standard Extended Euclidean Algorithm (XGCD) is a foundational algorithm in computational number theory. It finds the greatest common divisor of two integers and simultaneously computes the coefficients of Bézout’s identity. However, for the Shanks NUCOMP optimization, we do not want to run the XGCD all the way to completion. Instead, we run a specialized, modified version known as a “Partial” XGCD.

In the xgcd_partial function, we pass in two BigInt values and the specific threshold $L$. This threshold $L$ is exactly the value we just computed using the isqrt_fourth function. The loop inside this function executes the standard Euclidean division steps: dividing, finding the remainder, and shifting variables. But crucially, it includes a strict early-exit condition that defines the “partial” nature of the algorithm. It halts the moment the remainder drops below the threshold $L$.

Notice how heavily this specific section of code relies on Rust references and borrowing syntax. Mathematical operations like a = &b - &q * &r are written with explicit borrows on every single operand. If we were to blindly clone these 1024-bit integers on every single iteration of the Euclidean algorithm loop, performance would tank immediately. The memory allocator would thrash, and the VDF would become far too slow to run on consumer-grade hardware. By using references, the num-bigint crate can perform the arithmetic using the existing backing vectors. This minimizes the stress on the global system allocator and keeps the CPU cache piping hot for maximum instruction throughput. This pattern of utilizing references for num-bigint arithmetic is a hallmark of Kinetic’s cryptographic optimizations. Understanding lifetime scopes and borrow checking is critical to making sense of these dense mathematical loops.

3. Representing the Quadratic Form

-> See: kyn-vdf/src/math.rs — Lines 97 to 120

In this section, we define the central data structure of the entire crate: the Form struct. It is defined simply as a struct holding exactly three BigInt fields, named a, b, and c. These three fields map directly to the coefficients of our binary quadratic form $ax^2 + bxy + cy^2$. The quadratic form has deep connections to ideals in quadratic fields, making it the perfect algebraic structure for our group operations. There is a fundamental, mathematical invariant that this struct must always maintain at rest. The discriminant of the form must always equal the network’s globally chosen $D$. In equation terms, this means that the relation $b^2 - 4ac = D$ must always hold true for any valid form. This relation directly mirrors the standard quadratic formula discriminant, and it ties the specific form back to the global class group. If a form ever violates this invariant, it is invalid, cryptographically useless, and represents a critical consensus failure.

The struct provides various initialization methods to safely construct forms, ensuring the invariant holds upon creation. It carefully initializes the identity element of the class group, which is required to start the VDF sequence. More importantly, it provides the target receiver for our next, and most crucial, operation: reduction. The Form struct also implements traits like Clone and PartialEq. However, you must be careful: equality checking is only meaningful if both forms are in their reduced state. Comparing two unreduced forms directly via PartialEq is a logical error, as they may represent the exact same mathematical element in the class group but have wildly different coefficients. The system relies on strict reduced-form comparisons during the verification step to ensure consensus agreement. To avoid bugs, equality comparisons should always be preceded by a call to reduce().

4. Gauss Reduction Algorithm

-> See: kyn-vdf/src/math.rs — Lines 122 to 226

When operations like composition or squaring are performed on forms, they naturally become “unreduced”. An unreduced form represents the exact same mathematical equivalence class as a properly reduced form. However, its coefficients $a$, $b$, and $c$ are unnecessarily large and non-canonical. In order to deterministically compare forms (which the verifier must do to check the VDF proof), they must be standardized. They must be converted back into a unique, canonical state known as the “reduced” state. The reduce() method implements the classical Gauss reduction algorithm for this exact standardization purpose.

Gauss reduction is conceptually similar to the Euclidean algorithm, but it operates on two-dimensional quadratic forms instead of one-dimensional integers. A binary quadratic form is considered properly, reduced if and only if two strict conditions are met. First, the coefficients must satisfy the primary inequality: $-a < b <= a < c$. Second, if $a$ happens to exactly equal $c$, then $b$ must be greater than or equal to $0$. The reduce() function uses a mutable while loop that repeatedly applies two core normalization steps until these precise conditions are met.

The first step is logically called “Normalize B”. It shifts the value of the $b$ coefficient so that it falls precisely into the mathematical range $(-a, a]$. This step involves calculating a shift factor $q$ via a careful integer division. It then updates both the $b$ and $c$ coefficients accordingly using this calculated shift factor, preserving the overall discriminant invariant throughout the transformation. The preservation of the discriminant invariant is verified via robust unit testing, but logically it is guaranteed by the algebraic shifts applied. This step acts as a sliding window that bounds the size of $b$.

The second step is logically called “Minimize A”. If the coefficient $a$ is greater than $c$, the form is fundamentally unbalanced and clearly violates the reduction condition. To fix this imbalance, the algorithm dynamically swaps the values of $a$ and $c$, and simultaneously negates the value of the $b$ coefficient. This elegant mathematical swap immediately makes the new $a$ coefficient smaller than the new $c$ coefficient. This step acts as the primary driver of reduction, constantly pushing the maximum values downwards with every loop iteration.

The main loop in lines 122-226 alternates continuously between these two critical normalizations. Because the coefficient $a$ decreases every single time a swap operation occurs, the algorithm is guaranteed to eventually terminate. The heavy use of BigInt mutable references in this section is perhaps the single most performance-critical code in the entire repository. Gauss reduction runs iteratively after every single composition step in the main VDF prover loop. If this specific reduction loop is slow, the entire network’s baseline VDF delay increases, harming network throughput. Any future optimizations to Kinetic’s underlying math library will undoubtedly start right here in reduce().

Key Pieces

This section breaks down the critical components you need to understand in this file.

isqrt_fourth(n: &BigInt) -> BigInt

#![allow(unused)]
fn main() {
isqrt_fourth(n: &BigInt) -> BigInt
}
  • What it does: Computes the deterministic integer fourth root of a number $n$.
  • File:Line: kyn-vdf/src/math.rs — Lines 10-45.
  • Why it matters: It calculates the foundational $L$ threshold required by the Shanks NUCOMP optimization.

Important

If this value is computed incorrectly by even a single bit, the partial XGCD will stop at the wrong time. Stopping at the wrong time corrupts the intermediate state and invalidates the entire VDF output, rendering the proof useless. The strict integer-only implementation is the bedrock that guarantees network-wide consensus determinism.

xgcd_partial(a: &BigInt, b: &BigInt, limit: &BigInt) -> (BigInt, BigInt, BigInt)

#![allow(unused)]
fn main() {
xgcd_partial(a: &BigInt, b: &BigInt, limit: &BigInt) -> (BigInt, BigInt, BigInt)
}
  • What it does: Runs the Extended Euclidean Algorithm but forces a strict early stop when the remainder is less than or equal to the limit.
  • File:Line: kyn-vdf/src/math.rs — Lines 47-95.
  • Why it matters: It is the true computational engine of the Shanks NUCOMP optimization strategy. By strategically stopping the Euclidean algorithm early, we extract the exact intermediate Bézout coefficients needed for composition. These precise coefficients allow us to compose two forms without letting their intermediate values explode in system memory. This partial step is the crux of how Kinetic maintains memory-efficient group operations at scale.

struct Form

#![allow(unused)]
fn main() {
struct Form
}
  • What it does: Represents the abstract mathematical object $ax^2 + bxy + cy^2$ using three arbitrary-precision BigInt fields.
  • File:Line: kyn-vdf/src/math.rs — Lines 97-120.
  • Why it matters: This simple struct is the atomic unit of the entire VDF architecture. The entire VDF computation is functionally just a long, sequential chain of squaring Form objects millions of times. It securely holds the cryptographic state that is ultimately passed between the prover and the verifier over the network. Without a tight, efficient Form abstraction, the code would be a sprawling mess of loose variables.

Form::reduce(&mut self)

#![allow(unused)]
fn main() {
Form::reduce(&mut self)
}
  • What it does: Canonicalizes a quadratic form in-place so its internal coefficients satisfy the strict Gauss reduction inequality conditions.
  • File:Line: kyn-vdf/src/math.rs — Lines 122-226.
  • Why it matters: Without this mandatory reduction step, the coefficients $a$, $b$, and $c$ would grow with every single squaring operation. They would quickly consume gigabytes of memory and exhaust all available RAM on the node, fatally crashing the system. Reduction guarantees that the coefficients stay tightly bounded safely by the size of the discriminant $D$. It also ensures that every single node arrives at the exact same canonical representation for final verification. Verification hinges entirely on forms matching identically after reduction.

How This Connects to the Rest of Kinetic

This mathematical foundation is not an isolated academic exercise. It is deeply, inextricably wired into the cryptographic layers of the network and directly drives the consensus engine.

  • FORWARD DEPENDENCY: kyn-vdf/src/prover.rs The prover module takes a starting Form and squares it $T$ times consecutively to generate the delay. To achieve this sequential squaring, it continuously and repeatedly calls both xgcd_partial and Form::reduce in a tight loop. The execution efficiency of the code in math.rs directly dictates how fast the prover can physically run on given hardware. This hardware speed, in turn, structurally defines the network’s minimum possible block delay.

  • FORWARD DEPENDENCY: kyn-vdf/src/verifier.rs The verifier module uses the exact same mathematical operations defined here. It uses them to check the Wesolowski proof provided by the remote prover node. The verifier requires absolute, exact deterministic agreement on the reduce() outputs to accept a proof as valid and safe. Any discrepancy in math.rs means the verifier will falsely reject a valid proof.

  • CROSS-CRATE: kinetic-core The core consensus mechanism in the kinetic-core crate relies heavily on the VDF as an , trustless clock. It treats the finalized, reduced Form output as a secure source of pseudo-randomness for electing the next block producer. If the underlying math in this file is flawed, the random seed generation for leader election breaks down, stalling the chain. kinetic-core trusts math.rs to provide the randomness needed for Proof of Stake.

Quick Reference

Here are the essential mathematical facts you need to memorize about this module.

  • Primary Group Operation: Composition and Squaring of Binary Quadratic Forms.
  • Discriminant ($D$) Size: Typically 1024 to 2048 bits (must be a negative prime number).
  • Shanks NUCOMP Threshold ($L$): Defined as the fourth root of the absolute value of $D$ ($|D|^{1/4}$).
  • Gauss Reduction Condition 1: The coefficients must satisfy $-a < b <= a < c$.
  • Gauss Reduction Condition 2: Alternatively, if $a = c$, then $b >= 0$.
  • Data Types: All heavy computation exclusively relies on num-bigint::BigInt for arbitrary precision.

Caution

  • Determinism Constraint: NO FLOATING POINT math is allowed under any circumstances, ever, to prevent consensus forks.
  • Memory Strategy: Aggressive use of references (&BigInt) and mutable in-place operations (&mut self) to avoid expensive heap allocations.
  • Fundamental Invariant: The equation $b^2 - 4ac$ must always equal $D$ at all resting states.

Open Questions / Things to Revisit

There are several rough edges, architectural questions, and areas for future optimization in this file.

  • Memory Allocations in reduce: Even with careful use of references, num-bigint occasionally reallocates internal backing vectors during division and modulo operations. We need to profile the reduce() function under heavy, sustained load to identify these hidden allocations. We should investigate if we can pre-allocate scratch space buffers to eliminate the remaining heap allocations and stabilize the garbage collector. This could provide a speedup for the prover.

  • Alternative Math Backends: Currently, we use the num-bigint crate because it provides pure Rust compatibility, safety, and ease of auditing. However, GMP (GNU Multiple Precision Arithmetic Library) is widely known to be significantly faster for numbers of this specific 1024-bit size. Should we seriously consider a C-FFI wrapper to GMP for high-performance nodes that want to run optimized provers? If we do make this architectural shift, we must prove that determinism is preserved across the FFI boundary, which is risky.

  • Constant Time Execution Considerations: Classical Gauss reduction is fundamentally a variable-time algorithm by its mathematical nature. Its actual execution time depends heavily on the specific coefficients being reduced during the loop. In the context of a VDF prover, this is generally acceptable because we actually want the prover to run as fast as natively possible. Furthermore, VDF proofs are inherently evaluated on public data, meaning secrecy is not the primary concern. However, we need a thorough, professional security audit to ensure this doesn’t open up any obscure timing side-channel attacks on the verifier side of the protocol.

  • NUCOMP vs Standard Composition Crossover: For very small discriminants, the computational overhead of calculating xgcd_partial might actually be worse than just doing standard Arndt composition and then a full reduction. We should establish comprehensive benchmarks to find the exact performance crossover point where NUCOMP becomes superior to standard composition. This might allow us to switch algorithms dynamically based on the discriminant size for optimal performance.

  • WebAssembly Compatibility: If we eventually want light clients or browser wallets to verify VDFs natively in the browser, this math must compile cleanly and efficiently to Wasm.

Important

We need to verify that our aggressive use of num-bigint does not introduce any Wasm-incompatible instructions or performance regressions when compiled to WebAssembly targets.

  • Parallel Reduction Exploration: While the VDF itself is sequential by cryptographic design, could micro-parts of the reduction algorithm be parallelized safely using SIMD instructions? We need to deeply investigate if modern CPU vector extensions (like AVX-512) can accelerate the normalization steps without breaking the strict bit-level determinism requirement.