Crate: kyn-vdf

Stage: 05

Reading Time: 25 minutes

Depends On: 04_chia_forms.md, 03_vdf_basics.md

What Is This?

This document explores the Binary Quadratic Form Compression (BQFC) implementation inside kyn-vdf/src/chia.rs (lines 237-597). At a high level, BQFC is a sophisticated mathematical and engineering technique for taking a large mathematical object—a binary quadratic form—and squeezing it down into the smallest possible representation without losing any critical information. In the Kinetic network, we are constantly passing around VDF (Verifiable Delay Function) proofs, which are primarily composed of these binary quadratic forms. A raw 1024-bit form, if just serialized directly as its constituent components a, b, and c, takes about 130 bytes of space. Using BQFC, we are able to compress this down to exactly 100 bytes. This document will walk you through exactly how the CompressedForm struct represents this compressed state. We will examine how bqfc_compr takes a raw form and compresses it. We will also see how bqfc_decompr reverses that process. Finally, we will cover how serialize_form and deserialize_form translate the mathematical data into raw bytes for network transmission. When a developer first looks at this file, the immediate question is usually: “Why are we doing so much math just to serialize an object?” The answer is that a binary quadratic form is not just a random collection of bytes; it has strict internal mathematical relationships. BQFC exploits these relationships. Because the values of a, b, and c are bound together by the discriminant equation b^2 - 4ac = d, sending all three is redundant. Sending a and b is better, but still redundant because b itself has internal symmetries we can exploit. BQFC is the process of stripping away every single bit of redundant data until we are left with the absolute theoretical minimum representation. This mathematical compression is fundamental to the scalability of the Kinetic blockchain, ensuring that our verifiable delay functions do not choke the peer-to-peer layer.

Why Kinetic Needs This

You might look at the difference between 130 bytes and 100 bytes and think, “Is this really worth the complexity?” The answer is an emphatic yes. In the Kinetic network, VDF proofs are not just calculated once and stored; they are constantly gossiped across the peer-to-peer (P2P) network. Every single node that participates in consensus needs to receive, verify, and potentially re-broadcast these proofs. When you have thousands of nodes broadcasting proofs every few seconds, that extra 30 bytes per form adds up . Let’s break down exactly why this compression is a feature for the Kinetic architecture.

First, consider MTU and Packet Fragmentation. Network packets have a Maximum Transmission Unit (MTU), which is typically around 1500 bytes for standard Ethernet. If a message exceeds this, it gets fragmented into multiple packets. Fragmentation increases latency and the chance of packet loss. VDF proofs are often bundled with other block headers and signatures. By keeping our VDF proofs as small as possible, we maximize the number of proofs we can fit into a single unfragmented UDP or TCP packet. A 100-byte footprint gives us crucial breathing room in our packet budgets. If we were to use the uncompressed 130-byte forms, a single broadcast containing a handful of proofs could easily spill over the MTU threshold.

Second, we must address Blockchain State Bloat. Over time, these VDF proofs end up being embedded into the historical record of the Kinetic blockchain. 30 extra bytes per block, extrapolated over years and millions of blocks, turns into gigabytes of pure waste. Storage is not free, and one of Kinetic’s primary goals is to keep the node requirements low enough that anyone can run an archival node on consumer hardware. By compressing forms at the network layer and persisting them in this compressed state, we are significantly reducing the long-term storage requirements. This has a direct impact on the decentralization of the network.

Third, Bandwidth Costs are a major concern. For light clients or nodes running in bandwidth-constrained environments (like mobile devices, rural internet connections, or satellite links), bandwidth is expensive and limited. Shaving off ~23% of the size of the most commonly transmitted data structure is a win for network inclusivity. Kinetic aims to be a globally accessible network, and every byte saved lowers the barrier to entry. When syncing from genesis, a node must download millions of these forms; a 23% reduction in size translates to hours saved during the initial sync process.

Fourth, there is an interesting dynamic regarding Processing Overhead and Cache Locality. While decompression takes a small amount of CPU work to perform the mathematical recovery, transmitting less data over the wire and reading fewer bytes from disk often results in an overall performance gain. Modern CPUs are fast, but memory bandwidth and cache misses are slow. Reading 100 bytes into the L1/L2 cache is faster than reading 130 bytes. The CPU overhead of running the math in bqfc_decompr is often hidden by the time saved not waiting for RAM or network I/O. This illustrates the principle of trading cheap compute cycles for expensive bandwidth and I/O.

Finally, consider DDoS Mitigation. Smaller packet sizes mean that an attacker trying to flood the network with fake proofs has to expend relatively more effort to saturate a node’s bandwidth. While BQFC wasn’t designed purely as a security feature, dense packing of data structurally hardens the P2P layer. An attacker must generate valid or pseudo-valid compressed forms, meaning they cannot just spray random large bytes at the network and expect them to be processed as VDF proofs.

How It Works

The BQFC process relies on a core insight from number theory: a binary quadratic form (a, b, c) of a known discriminant d has redundant information. Because the relationship b^2 - 4ac = d always holds true, if we know a and b (and d, which is a global network constant), we can easily calculate c. However, BQFC takes this even further. It turns out you don’t even need all of b. You can compress a and a specialized representation of b into a smaller space, and then reconstruct b on the other side. This process is broken down into several stages: structural representation, mathematical compression, byte serialization, byte deserialization, and finally mathematical decompression.

Step 1: The CompressedForm Structure

-> See: kyn-vdf/src/chia.rs — Lines 237-250

When we compress a form, we don’t just truncate bytes arbitrarily. We transform the standard (a, b, c) coordinate system into a specialized CompressedForm structure. This structure contains four key fields: a, t, g, and b0. The a field remains the exact same value as in the original form. It is the foundational pillar of the form and cannot be compressed away; its full precision is required. The t field is a partial quotient derived from running the Extended Euclidean Algorithm (XGCD) on a and b. The g field is the greatest common divisor extracted during that same XGCD step. The b0 field is a small remainder value, essentially a mathematical parity check. By storing these specific elements instead of the integer b, we encapsulate enough mathematical “breadcrumbs” to recreate the original b value. It is a form of lossy compression where the “lost” data can be deterministically recalculated on the other side without having to send the entire integer over the network. This structure is the cornerstone of our ability to hit the 100-byte target.

Step 2: Compression (bqfc_compr)

-> See: kyn-vdf/src/chia.rs — Lines 255-320

The bqfc_compr function is where the heavy lifting of compression occurs. It takes a raw, fully inflated binary quadratic form and produces a CompressedForm. The function first initiates a bounded version of the Extended Euclidean Algorithm on the inputs a and b. The Euclidean algorithm is typically used to find the greatest common divisor of two numbers, but here it is used to find a smaller representation of the relationship between a and b modulo a certain base. The algorithm runs until it reaches a specific bound, at which point it extracts the variables t and g. Once the XGCD yields t and g, the function calculates b0. Because the reconstruction process later will involve calculating square roots, and because square roots have multiple valid solutions in modular arithmetic, b0 acts as a crucial parity bit or remainder to resolve ambiguities later. The beauty of this algorithm is that it takes a number b that normally requires a amount of bits and shatters it into these smaller mathematical components (t, g, b0) that pack tightly together. This mathematical decomposition is what allows us to discard the bulk of b’s bits.

Step 3: Serialization (serialize_form)

-> See: kyn-vdf/src/chia.rs — Lines 325-390

Once we have a CompressedForm sitting in memory, we need to turn it into a flat array of exactly 100 bytes so it can be sent over a TCP or UDP socket. This is where serialize_form comes in. The function allocates a Vec<u8>, which is a dynamically sized, owned array of bytes on the heap. It then begins packing the fields a, t, g, and b0 into it. Because these fields are large, multi-precision integers (typically BigInts), it extracts the raw bytes of each number and concatenates them in a strict, deterministic order.

When writing this in Rust, the distinction between a Vec<u8> and a [u8] is . A Vec<u8> is an owned, growable array allocated on the heap. When serialize_form creates a new Vec<u8>, it is taking ownership of new memory. It populates this memory, and then returns ownership of this vector to the caller. The caller is then responsible for sending it over the network or dropping it, at which point the memory is freed. Conversely, the data it reads from the BigInts often comes out as a slice [u8]. A slice is just a borrowed view into memory owned by someone else. To get the data from the slice into the vector, the code uses copy_from_slice. This function performs a fast, safe memcpy under the hood. It ensures the vector has its own independent copy of the bytes, preventing any data races or use-after-free errors. This explicit copying is why the return type of serialize_form is an owned Vec<u8>.

Critically, it also packs metadata. To save space, it uses bit flags. For example, the sign of b (whether it is positive or negative) is essential for reconstruction. Allocating a whole byte just for a true/false value is wasteful. Instead, the sign is packed into a single bit of a single byte using a bitwise shift, specifically BQFC_B_SIGN = 1 << 0. This means we take the binary number 1 and shift it left by 0 positions, which just equals 1. If the sign is negative, we bitwise OR this value into our byte using the | operator. This technique allows us to cram up to 8 different boolean flags into a single byte of overhead. It is this aggressive, bit-level micromanagement that keeps the final serialized size capped at 100 bytes.

Step 4: Deserialization (deserialize_form)

-> See: kyn-vdf/src/chia.rs — Lines 395-460

On the receiving end, a Kinetic node receives a 100-byte packet from a peer. It uses deserialize_form to parse this raw byte array back into a usable CompressedForm structure in memory. This function takes a slice &[u8], which is a borrowed view into the bytes, rather than an owned Vec<u8>.

The parser is passed a &[u8], a read-only borrowed slice. This means the parser does not own the memory; it is just looking at the bytes received from the network socket. Because it’s a slice, it has a known length, and Rust will automatically bounds-check our reads to prevent buffer overflows. This built-in safety net is why Rust is chosen for these critical network parsers over C or C++. To track our progress through this slice, we use an &mut usize representing an offset. Why a mutable reference? If we just passed usize by value, the helper functions would get a copy of the number. When the helper function reads 4 bytes, it would add 4 to its own copy of the offset, and the main parser would be stuck at 0. By passing &mut offset, the helper function directly modifies the parser’s offset variable. This ensures that every sequential read picks up exactly where the last one left off, moving safely through the 100 bytes.

It reads the bit flags we packed earlier by taking a byte and using bitwise AND operations. By executing byte & BQFC_B_SIGN, the parser masks out all other bits and isolates exactly the boolean value it needs. This cleanly translates network bytes back into structured Rust logic.

Step 5: Decompression (bqfc_decompr)

-> See: kyn-vdf/src/chia.rs — Lines 465-597

Once the node has safely parsed the bytes into a CompressedForm, it still needs the actual, full (a, b, c) form to verify the VDF proof. The bqfc_decompr function performs this mathematical inflation. It takes a, t, g, and b0 and runs the algorithm to reconstruct the original b. This is a computationally intensive process. It involves calculating modular inverses over large finite fields, and eventually calculating modular square roots. Calculating a modular inverse means finding a number x such that (num * x) % mod = 1. Because square roots can have multiple valid answers in modular arithmetic, the algorithm reaches a fork in the road where it must decide which root is the correct one. This is exactly why the b0 value and the sign flags were packed earlier. They act as a tie-breaker, forcing the algorithm to select the exact root that corresponds to the original b. If we did not have these flags, we would have a 50/50 chance of picking the wrong root, which would invalidate the VDF proof. Finally, once a and b are fully recovered and verified, c is trivially computed using the fundamental discriminant equation: c = (b^2 - d) / (4a). The form is now fully restored and ready for VDF verification. The CPU overhead here is non-trivial, but as mentioned earlier, it is well worth the bandwidth savings.

Key Pieces

Here is a detailed breakdown of the critical types and functions you need to understand in this file. When modifying this file, these are the components you must be careful with.

CompressedForm

• What it does: A structured payload holding a, t, g, and b0.
• File & Line: kyn-vdf/src/chia.rs — Lines 237-250.
• Why it matters: This is the intermediate state between a full mathematical form and raw bytes. It defines exactly what mathematical components are necessary to achieve the 100-byte compression target. If you ever need to change the compression algorithm, this struct will be the first thing to change. It acts as the bridge between pure math and network serialization.

bqfc_compr

• What it does: Compresses a standard binary quadratic form into a CompressedForm.
• File & Line: kyn-vdf/src/chia.rs — Lines 255-320.
• Why it matters: This is the engine of the BQFC protocol. It uses the Extended Euclidean Algorithm to discard redundant bits of b and generate the minimal t and g values. It is optimized and any bugs here will result in forms that cannot be decompressed by peers. A bug here would effectively create a network fork, as nodes running the buggy code would produce forms that other nodes would reject as invalid.

bqfc_decompr

• What it does: Takes a CompressedForm and inflates it back into a standard (a, b, c) form.
• File & Line: kyn-vdf/src/chia.rs — Lines 465-597.
• Why it matters: Without this, the VDF proofs received from the network are useless. It performs complex modular arithmetic (inverses and square roots) to reconstruct the dropped data. Performance is critical here, as this runs directly during block validation. Any inefficiency here will slow down the entire node’s ability to sync with the network.

serialize_form

• What it does: Flattens a CompressedForm into a Vec<u8> of exactly 100 bytes.
• File & Line: kyn-vdf/src/chia.rs — Lines 325-390.
• Why it matters: This function bridges the gap between abstract Rust memory structures and physical network sockets. It handles byte-order (endianness) and tight bit-packing for boolean flags. It must be deterministic; the exact same mathematical form must always serialize to the exact same 100 bytes. If it is not deterministic, block hashes will diverge, causing consensus failures.

deserialize_form

• What it does: Parses a 100-byte slice [u8] back into a CompressedForm.
• File & Line: kyn-vdf/src/chia.rs — Lines 395-460.
• Why it matters: This is the entry point for all incoming network data related to VDFs. It safely validates that the incoming data is exactly 100 bytes and decodes the packed bit flags. It must be robust against malformed or malicious inputs to prevent panics. Because it touches untrusted network data, it is a prime target for fuzzing and security audits.

How This Connects to the Rest of Kinetic

CROSS-CRATE: kyn-network The kyn-network crate is the primary consumer of serialize_form and deserialize_form. When the network layer needs to broadcast a block containing a VDF proof, it calls serialize_form. This ensures the payload is as small as possible before constructing the final P2P protocol message. Conversely, when kyn-network receives a proof from a peer, it immediately calls deserialize_form. This step is required to validate the byte structure before passing the message further up the protocol stack. Without this tight integration, our P2P layer would be overwhelmed by large proof sizes.

CROSS-CRATE: kyn-consensus The kyn-consensus crate relies entirely on the successful output of bqfc_decompr. The consensus rules dictate that a block is only valid if the VDF proof checks out. The consensus engine must take the decompressed form, feed it into the VDF verification algorithm, and ensure it matches the expected difficulty. It also ensures the iterations match for that specific block height. If bqfc_decompr fails, or if it produces a structurally invalid form, the block is instantly rejected by consensus. There is no fallback mechanism; BQFC decompression must succeed for the chain to progress.

FORWARD DEPENDENCY: VDF Verification Engine The output of bqfc_decompr feeds directly into the squaring loop of the VDF verification process. The values of a and b generated here must be accurate down to the very last bit. If decompression yields even a single bit of error in b, the subsequent squaring operations will immediately diverge. They will stray from the prover’s original mathematical path. This leads to a failed verification, and usually results in the peer that sent the form being banned for providing invalid data.

Quick Reference

• Original Form Size: ~130 bytes (for a standard 1024-bit discriminant).
• Compressed Form Size: Exactly 100 bytes.
• CompressedForm fields:
• a: The primary coefficient. - t: The partial quotient from the XGCD run. - g: The greatest common divisor from the XGCD run. - b0: The mathematical remainder/parity check used to break ties.
• Compression Method: Partial Extended Euclidean Algorithm (XGCD) to discard redundant bits of b.
• Decompression Method: Modular inverses and modular square roots to recover the dropped bits of b.
• Serialization Format: Big-endian byte arrays combined with bit-packed boolean flags for maximum data density.
• Network Goal: Keeping VDF proofs well within standard MTU limits and reducing node storage bloat.

Open Questions / Things to Revisit

• BigInt Allocation Overhead: The bqfc_decompr function currently performs several large BigInt allocations when computing modular inverses and square roots. We should investigate if we can reuse a pre-allocated memory pool or bump allocator. This would reduce garbage collection and allocator pressure during heavy blockchain syncing. Currently, syncing from genesis allocates and deallocates millions of BigInts, which is not optimal for CPU caches.

• Constant Time Execution guarantees: Is bqfc_decompr currently constant-time? Almost certainly not, due to the nature of the XGCD and square root algorithms. Since this code is used for verification and not for signing or key generation, side-channel attacks (like timing attacks) are less of a concern. However, it is worth documenting so future developers do not mistakenly use these functions in a cryptographic context where constant-time execution is required. If we ever expose these functions to smart contracts, this could become a severe vulnerability.

• Error Handling on Malicious Packets: If an attacker sends garbage 100-byte payloads filled with random noise, does deserialize_form fail gracefully? More importantly, does bqfc_decompr waste excessive CPU cycles trying to calculate impossible square roots before realizing the form is invalid? We need to ensure we have strict, early exit paths to prevent asymmetric denial-of-service (DoS) vectors. An attacker could theoretically burn our CPU with cheap random bytes if we are not careful to abort early on impossible states.

• Memory Safety Review: While deserialize_form leverages Rust’s safe slices, we still need to audit the bounds checking logic manually. A panic here from an out-of-bounds slice access would crash the network layer. We need to guarantee that every single slice indexing operation is guarded by a length check before deployment.

• Future Optimizations: Can we compress these forms even further? Recent research in cryptography suggests that 96-byte compressions might be possible for 1024-bit discriminants. However, this would require a hard fork and rewriting both bqfc_compr and bqfc_decompr. For now, 100 bytes is the absolute sweet spot between implementation complexity, CPU verification time, and network bandwidth.