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: Math Composition (Stage 3)

Reading Time: 35 minutes Depends On: kyn-vdf/src/form.rs, kyn-vdf/src/xgcd.rs

What Is This?

This file contains the optimized mathematical foundation for multiplying and squaring elements within an imaginary quadratic class group. It fundamentally implements the exact algebraic rules required to advance the Verifiable Delay Function (VDF) state securely. Specifically, it provides Shanks’ NUDUPL algorithm for efficiently squaring a single form in the class group space. It also provides Shanks’ NUCOMP algorithm for efficiently composing two different forms together . Finally, it includes a fast binary exponentiation method to raise a given form to an arbitrary, integer power. These complex algorithms take one or two quadratic forms as inputs to begin the computational process. They perform structured polynomial transformations on these specific input variables. They then securely return a canonical reduced product form representing the final outcome. The internal logic heavily leverages the extended Euclidean algorithm to prevent intermediate numbers from growing too large. This careful, deliberate bounding of coefficient sizes ensures that memory allocations remain small and predictable throughout execution. Ultimately, this specific file serves as the absolute core cryptographic engine that guarantees the un-forgeable delay. This un-forgeable delay is what the entire Kinetic network consensus relies upon to function properly. Without this precise implementation, the network would collapse due to forged timestamps. It acts as the strict timekeeper for a globally distributed, trustless environment. Every line of code here represents a carefully considered tradeoff between mathematical purity and bare-metal performance.

Why Kinetic Needs This

Kinetic relies entirely on a Verifiable Delay Function to cryptographically prove that real-world time has elapsed between blocks. This cryptographic proof is actively generated by sequentially computing an immense number of repeated squarings. These sequential squarings happen inside a specialized mathematical structure called an unknown-order group. In our unique architecture, this unknown-order group is defined as an imaginary quadratic class group. This class group uses a carefully selected, cryptographically secure large prime discriminant. The standard, academically pure way to multiply two class group forms is widely known as naive Gaussian composition. However, naive Gaussian composition presents an insurmountable performance challenge for a high-throughput network like Kinetic. During naive Gaussian composition, the intermediate coefficients (a, b, c) balloon to large, unmanageable sizes. These sizes naturally occur immediately before the final standard reduction step is finally permitted to clean them up. Specifically, they can rapidly grow up to the exact mathematical square of the absolute size of the underlying network discriminant. If Kinetic uses a standard, secure 2048-bit discriminant, naive composition would routinely generate intermediate numbers exceeding 4096 bits. Performing raw mathematical arithmetic on 4096-bit numbers is more computationally expensive than operating on 2048-bit numbers. It is also significantly more memory-intensive across the entire hardware execution pipeline. It demands vastly more CPU cycles per individual multiplication, addition, or division instruction. It also forces the underlying system allocator to handle , unpredictable heap allocations continuously. Since generating a VDF proof fundamentally requires many millions of sequential squarings, this performance overhead compounds . Even a microscopic microsecond slowdown per single squaring operation destroys the absolute reliability of the global delay guarantee. This cascading failure breaks the core consensus timing assumptions entirely. Furthermore, it would slow down all other honest nodes on the broader network. These honest nodes must verify the block accurately before safely accepting it into their local decentralized chain. To resolve this critical computational bottleneck, Kinetic mandates the exclusive use of Shanks’ algorithms. Specifically, it enforces the NUDUPL and NUCOMP algorithms for all class group operations without exception. These specialized algorithms intercept the intermediate components before they are ever allowed to explode in memory size. They apply a partial extended greatest common divisor (XGCD) routine directly mid-calculation. This mid-calculation intervention actively reduces the internal values dynamically and predictably. This specific methodology guarantees that the intermediate BigInt structures stay bounded. They generally remain very close to the exact original bit-size of the discriminant itself throughout the entire execution lifetime. bounded sizes logically mean that dynamic memory allocations remain entirely predictable. They are remarkably cache-friendly and significantly faster to process directly at the hardware CPU level. By relying on these specific, tuned optimizations, Kinetic levels the computational playing field. This creates a fundamentally fair network for all disparate participants regardless of hardware budgets. If the operation were intentionally memory-hard instead of purely sequential, attackers could easily utilize specialized memory architectures. This would allow them to calculate the VDF faster and maliciously manipulate the network timestamp mechanism. Hardware advantages like parallel ALUs or expensive custom FPGAs become bottlenecked. They are constrained by the inherently sequential, step-by-step nature of this exact bounded arithmetic design. Without math.rs and its tuned, memory management, Kinetic’s consensus mechanism would be slow and insecure. It would be instantly vulnerable to well-funded participants leveraging superior, specialized computing hardware. Therefore, the density and performance of this single file arguably define the security perimeter of the entire Kinetic ecosystem.

How It Works

The overarching execution flow within this file is an absolute masterclass in managing arbitrary-precision BigInt memory allocations. It manages these allocations safely while performing dense, cryptography over complex algebraic structures. The entire mathematical processing pipeline is divided into three primary algorithms. Each of these algorithms serves a distinct, irreplaceable, and designed role in the full VDF lifecycle. The overall engineering objective here is to ensure that no single operation causes an unexpected garbage collection pause. It is equally critical that no operation forces the host CPU to catastrophically stall on predictable cache misses.

1. Shanks’ NUDUPL (Squaring)

-> See: kyn-vdf/src/math.rs — Lines 227 to 310 NUDUPL is unequivocally the absolute core of the prover’s execution loop. It easily ranks as the most frequently executed single function anywhere in the entire Kinetic network stack. It is a specialized variant of Shanks’ composition and exclusively tailored for squaring a single mathematical form. When a cryptographic form is composed with itself, many algebraic terms gracefully cancel each other out. This symmetric cancellation and permanently reduces the initial processing overhead. This is heavily contrasted with the much slower process of composing two entirely different forms together. The algorithm starts execution by cleanly extracting the a, b, and c coefficients directly from the input form’s state. It carefully avoids unnecessary copying during this initial coefficient extraction phase. It then immediately triggers the optimized partial extended Euclidean algorithm. This trigger occurs via a strict, direct call to the dedicated xgcd_partial function module. Instead of running naively until a full, final zero remainder is predictably reached, xgcd_partial is instructed to stop early. It deliberately halts its internal iterative loop exactly when the computed remainders cross a specific mathematical threshold. This strict threshold is precisely the fourth root of the absolute mathematical value of the network discriminant. This deliberate premature termination yields a specialized 2x2 mathematical transition matrix. This matrix is composed of remarkably small, easily manageable integer coefficients. The algorithm carefully takes this small transition matrix and cross-multiplies it iteratively with the original form components. This specific matrix cross-multiplication yields a brand new set of mathematical coefficients . Crucially, these newly minted coefficients are naturally, already partially reduced by design. By performing this precise matrix multiplication sequence, NUDUPL skips the dangerous computational phase entirely. This skipped phase is exactly where naive coefficients would have normally, disastrously doubled in bit length. This section heavily and intentionally utilizes Rust’s powerful num_integer::Integer trait to execute precise division semantics. Specifically, it relies on div_floor and mod_floor rather than using the basic native operators built into the Rust language. In strict cryptographic mathematics over class groups, taking a modulo of any negative number must universally wrap around. It must always wrap directly to a positive remainder to maintain structural integrity. Rust’s standard % operator simply truncates the division lazily toward zero. This default truncation yields destructive negative remainders for all negative inputs. Using % here would instantaneously corrupt the deep structural validity of the class group form permanently. This would result in invalid VDF proofs being broadcast to the network. After the transition matrix is successfully and safely applied, NUDUPL always triggers a standard, final reduction step. This final reduction logically guarantees that the newly squared form is canonical, unique, and minimal. Memory management dynamically here requires meticulous, manual oversight to ensure high performance without memory leaks. Because BigInt structures reside exclusively on the heap by design, they naturally drop their memory when fully consumed by an operator. The codebase heavily utilizes cleanly borrowed references (e.g., &a + &b) to securely execute arithmetic. It does this without erroneously taking permanent ownership of the transient variables. It manually triggers an explicit clone() only when a specific intermediate value must be preserved. This preservation only happens across volatile mutable boundaries for a subsequent, necessary calculation step.

2. Shanks’ NUCOMP (General Composition)

-> See: kyn-vdf/src/math.rs — Lines 312 to 420 NUCOMP brilliantly generalizes the fast composition logic to handle two different mathematical forms safely. Because the raw inputs are inherently distinct and asymmetric, the algorithm simply cannot rely on the symmetric mathematical cancellations. It cannot use the elegant shortcuts that NUDUPL heavily exploits for raw speed. Instead, it must painstakingly compute the full, unadulterated greatest common divisor . It computes this GCD specifically between the respective a coefficients of both individual input forms. This heavy initial phase involves safely calculating specific intermediate structural values correctly. These values are consistently referred to as s and m in deep academic cryptographic literature. Once these foundational values are cleanly found, the algorithm proceeds carefully to solve a series of strict linear congruences. The ultimate, necessary objective of these complex, interconnected congruences is to discover a single unified structural variable. This critical variable is typically denoted simply as V in the codebase. This specific variable V must uniquely and simultaneously satisfy two rigid, independent modular constraints. These precise constraints actively involve the original, unmodified b coefficients of the parent forms. V essentially acts as the critical mathematical bridge required to merge the independent states. It merges the states of the two distinct input forms into a single cohesive mathematical entity. If the protocol naively combined the forms directly using V right away, disaster would strike. The resulting leading A coefficient would instantaneously explode in size directly to the product of a1 * a2. NUCOMP elegantly and robustly prevents this impending, memory explosion . It does this by immediately feeding the discovered V and the original coefficients cleanly into xgcd_partial. Exactly like the NUDUPL implementation, it reliably retrieves a specialized transition matrix directly based exclusively on early-stopping GCD remainders. The various mathematical components of the two parent forms are then carefully cross-multiplied with this specific transition matrix. This cross-multiplication produces the final, safely bounded coefficients representing the merged state. This complex phase necessarily involves an high volume of temporary, volatile BigInt allocations in memory. These allocations are immediately, ruthlessly dropped from local scope immediately after their singular use. Managing these precise lifetimes safely during these dense, chaotic matrix multiplications is critical. It is the only reliable way to avoid devastating, compilation-halting borrow-checker errors in Rust. Finally, a standard, rigorous reduction pass is reliably applied to definitively yield the canonical product. This ensures the final representation of the two composed forms is minimal and unique. Because of the heavy initial GCD computations and complex, demanding congruence solving, NUCOMP is naturally much slower than NUDUPL. Therefore, the Kinetic network protocol and ensures it never, ever uses NUCOMP for the intensive sequential squaring loop. Instead, it is , unapologetically reserved exclusively for the verifier protocol execution phase. The verifier uses it sparingly but crucially to conclusively validate the final mathematical structure of the incoming proof.

3. Fast Exponentiation (fast_pow)

-> See: kyn-vdf/src/math.rs — Lines 422 to 502 This robust function implements a efficient, tightly controlled algorithmic loop. It precisely computes f^n for an arbitrarily large integer n with remarkable efficiency. It fundamentally and heavily utilizes the classic left-to-right binary exponentiation technique universally known in cryptography. This elegant technique is often colloquially called the square-and-multiply algorithm by cryptographic engineers. The strict algorithm carefully evaluates the absolute binary bit representation of the exponent n. It securely evaluates this representation sequentially, starting securely from the absolute most significant bit down to the absolute least. It first carefully initializes a mutable accumulator variable securely in memory. This accumulator typically, reliably starts directly as the mathematical identity form of the defined class group. For every single, distinct bit successfully evaluated in the binary string, a specific action occurs unconditionally. The accumulator form is unconditionally, reliably, and forcefully squared using the fastest available method. This critical, repetitive squaring operation is executed directly using the optimized nudupl function described extensively above. If the current binary bit being evaluated currently happens to be exactly a binary 1, an additional operational step occurs. This asymmetric, additional step is and securely triggered by the internal logic branch. The running accumulator is multiplied cleanly by the exact original base form f. It executes this multiplication using the versatile, generalized nucomp function for distinct forms. This deliberate, mathematical strategy dramatically reduces the required total operations required to finish safely. It drops the complexity from a purely, disastrously linear O(n) to an fast, manageable logarithmic O(log n). A , critical performance optimization nested deeply inside this hot loop is opportunistic reduction. During continuous, heavy mathematical composition, small, subtle inefficiencies can gradually, inevitably compound. This compounding causes the underlying form coefficients to slowly, consistently creep upward in raw size over time. The carefully designed algorithm actively intercepts this subtle, growing threat proactively. It does this by continuously, checking the absolute bit length securely of the accumulator’s internal a coefficient. If this specific, critical bit length unexpectedly exceeds exactly half the total bit width of the network discriminant, action is taken. The smart algorithm instantly, forcefully intervenes directly in the execution flow. It forces a rigid, standard reduction pass safely on the accumulator form. It successfully executes this reduction before allowing the loop to proceed cleanly to the next exponent bit. This brilliant, preemptive safeguard eliminates the , very real risk of a performance cliff. It prevents this cliff from occurring dangerously near the very end of very large, long-running exponentiations. The hot loop constantly, safely overwrites the main accumulator with newly generated forms continuously. This constant overwriting ensures old memory is cleanly, freed by the Rust garbage collector .

Key Pieces

The following structural components represent the most critical moving parts of the mathematical engine safely:

fn nudupl(f: &Form, d: &BigInt) -> Form

#![allow(unused)]
fn main() {
fn nudupl(f: &Form, d: &BigInt) -> Form
}

-> See: kyn-vdf/src/math.rs — Lines 227-310 This is undoubtedly the single, absolute most critical mathematical function for the overall performance of the entire VDF prover. It directly, consistently provides the high-speed squaring capability that fundamentally drives the entire verifiable delay sequence securely. Its raw, unadulterated performance characteristics directly, fundamentally dictate the exact real-world delay duration. This duration is inherently, required to maintain Kinetic’s target block intervals accurately. It prudently, intelligently receives the target form immutably to actively prevent unnecessary, expensive heap cloning. It then heavily internally manages its own transient, temporary memory allocations with absolute precision. Any regressions internally in this function directly, immediately weaken the economic security of the entire Kinetic network architecture significantly.

fn nucomp(f1: &Form, f2: &Form, d: &BigInt) -> Form

#![allow(unused)]
fn main() {
fn nucomp(f1: &Form, f2: &Form, d: &BigInt) -> Form
}

-> See: kyn-vdf/src/math.rs — Lines 312-420 This crucial function exclusively provides the generalized, robust composition logic for safely handling distinct, non-identical forms. It is an absolute, unavoidable requirement for the Wesolowski verification process executed securely by all honest network nodes. The network verifier must reliably, accurately multiply a standard cryptographic base form directly against a proof form safely. This proof form is raised to a dynamic, unpredictable challenge power derived from network state safely. It safely navigates complex linear congruences continuously without risking disastrous integer overflows . It does this while also avoiding precision loss or fatal division panics during runtime.

fn fast_pow(base: &Form, exp: &BigInt, d: &BigInt) -> Form

#![allow(unused)]
fn main() {
fn fast_pow(base: &Form, exp: &BigInt, d: &BigInt) -> Form
}

-> See: kyn-vdf/src/math.rs — Lines 422-502 This is the absolute primary orchestrator designated for safely raising any given mathematical form to an arbitrary BigInt power. It relies fundamentally, heavily on intelligently alternating sequenced calls to both nudupl and nucomp safely. It bases these specific calls entirely on strict, sequential binary bit evaluation securely. It matters intensely for rapid proof generation, where the prover must cleanly, accurately compute a quotient power dynamically. It effectively, permanently guarantees that even large, complex exponentiations reliably complete rapidly. They complete consistently in a tiny fraction of a single second rather than dangerously hanging indefinitely and stalling consensus.

BigInt Re-borrowing Patterns (&(&a + &b)) The Rust BigInt type definitely does not magically implement the standard Copy trait effortlessly. This is exactly because it relies heavily, consistently on dynamic, variable-length heap allocations exclusively. Consequently, utilizing any standard mathematical operators natively like + or * actively consumes the underlying values permanently by default. To prevent the strict Rust compiler from , prematurely destroying variables that are needed later, you must borrow them securely. You achieve this safely using the explicit & operator cleanly. Understanding exactly when to properly use &a, when to let the compiler safely consume a directly, and when to intentionally call a.clone() is . This careful, deliberate juggling of transient reference lifetimes is exactly what allows the cryptographic math to safely run at blazing speeds. It does this continuously without allocating endlessly and predictably crashing the entire host node gracefully. It is arguably the absolute most difficult aspect of writing -performant, memory-safe cryptography in pure Rust securely.

Caution

num_integer::Integer methods (mod_floor, div_floor) This sensitive module and universally requires correct Euclidean division rules when handling any negative numbers safely. Native arithmetic operators trivially like % in standard Rust simply, dangerously truncate toward zero continuously. This actively produces results that actively, break the underlying cryptographic structures securely. You must , use mod_floor consistently to ensure any negative dividends always wrap cleanly into positive remainders reliably. Failing to do so accurately will silently, dangerously yield invalid mathematical forms safely. This will permanently, irrevocably ruin the entire consensus proof validity .

How This Connects to the Rest of Kinetic

FORWARD DEPENDENCY: kyn-vdf/src/prover.rs The prover entirely, depends on nudupl to reliably, predictably execute the many millions of sequential squarings required. These squarings are required for the fundamental delay phase safely. Its core architectural execution loop is fundamentally, beautifully just a very tight, optimized continuous sequence . It is a sequence of continuous nudupl invocations executing flawlessly. Without optimized nudupl, the prover simply cannot logically securely generate a valid proof of elapsed time reliably.

FORWARD DEPENDENCY: kyn-vdf/src/verifier.rs The verifier relies structurally, on nucomp and fast_pow to independently securely validate proofs. It validates the pure mathematical integrity of all incoming proofs efficiently. It safely ensures that the block producer actually spent the exact required computational time reliably. It ensures they did not attempt to artificially forge the delay securely. This prevents malicious, aggressive nodes from endlessly spamming the secure network with instantly generated blocks safely.

CROSS-CRATE: kinetic-consensus/src/engine.rs The global, authoritative consensus engine actively, intelligently monitors the exact real-world time required . It monitors the time to successfully securely execute these specific mathematical functions reliably. It intelligently, dynamically uses this historical benchmarking data constantly to dynamically adjust . It cleanly adjusts the required VDF target iterations accurately for future upcoming network epochs safely. The pure algorithmic efficiency internally of math.rs is intrinsically, deeply, and directly permanently tied purely securely. It is tied to the absolute stability of the global, decentralized block interval reliably across all global continents safely.

Quick Reference

  • Need to sequentially square a form? Always reliably use nudupl(f, D) directly.
  • Why avoid nucomp for squaring? Do not use nucomp for simple squaring safely as it is computationally slower securely.
  • Need to securely combine two distinct, separate cryptographic forms? Always securely confidently use nucomp(f1, f2, D) reliably.
  • Need to securely precisely raise a specific base form smoothly to a very large power? Invoke fast_pow(f, exponent, D) reliably for lightning-fast explicit binary exponentiation securely.
  • Doing complex group math safely with potential negative BigInts? Never, ever reliably use % natively. Always heavily rely on mod_floor securely from the trusted Integer trait .
  • Compiler complaining about erroneously moved values abruptly? Check your mathematical expressions very carefully structurally.
  • How to fix moved values securely? Ensure all critical mathematical operands are properly safely borrowed with & reliably.
  • Why is exponentiation safely inexplicably slowing down over time? You likely mistakenly removed the opportunistic check.
  • What got removed? You probably accidentally fully disabled the critical opportunistic standard reduction check deeply buried safely in fast_pow .

Open Questions / Things to Revisit

Warning

Timing Side-Channels in Exponentiation The fast_pow function branches its execution path based on the individual bits of the given exponent. It uses a strict square-and-multiply branching logic that is predictable. While VDF exponents are inherently public data in the Kinetic protocol, we must be careful. We must deeply analyze if this predictable branching exposes any subtle hardware vulnerabilities. We must investigate if it makes the network susceptible to CPU cache timing attacks. If a malicious node can optimize execution based on timing data, it ruins the delay proof.

Memory Allocation Overheads During Composition Both nucomp and nudupl rapidly allocate and cleanly deallocate dozens of temporary BigInt structures. They do this during every single mathematical execution loop. Running this continuously for millions of consecutive iterations places unrelenting stress on the system allocator. The default Rust allocator struggles to keep up with the continuous heap fragmentation. We should investigate implementing a custom slab allocator. Alternatively, we could build a pre-allocated BigInt memory pool specifically for this math module. This could reduce garbage collection pauses and speed up proof generation.

Important

WebAssembly Stack Limits for Light Clients If Kinetic nodes are ever compiled down to WASM for browser-based light clients, we face risks. The internal xgcd_partial routine must be thoroughly and audited. If it relies heavily on deep recursive function calls, it will fail. Recursive calls easily and reliably blow up the limited WASM call stack in browsers. An iterative rewrite might be necessary for broader, stable client compatibility. We must test this logic in a WASM sandbox before deploying light nodes.

Discriminant Pointer Indirection Overhead We are currently actively passing the discriminant D directly by reference. We pass it into every single mathematical function repeatedly across the entire codebase. This causes constant, unnecessary pointer indirection and cache misses. We should investigate encapsulating D securely inside a persistent ClassGroupContext struct. This would immediately eliminate this constant pointer passing natively. It would also and permanently clean up the external API surface.