Proof of Work (S/Kademlia Sybil Protection)

Crate: kinetic-network Stage: 8 Reading time: 15 Depends on: 01_overview.md

What Is This?

This module implements the identity generation and validation mechanism for the Kinetic network, specifically using a concept inspired by S/Kademlia. In plain terms, before a node is allowed to participate in the network, it must prove that it expended a significant amount of computational effort to generate its cryptographic identity (PeerId). It does this by repeatedly generating keypairs until it finds one whose public key hashes to a value with a specific number of leading zero bits.

This proof of work (PoW) is not for consensus, block generation, or cryptocurrency mining. It is an anti-spam and anti-Sybil defense mechanism for the networking layer. To ensure identities cannot be mined once, hoarded, and reused forever, the proof of work is bound to a specific timeframe called an “epoch.” An epoch is derived directly from the network’s Drand-based clock (the “kyn”). When the epoch passes, the identity becomes invalid, and the node must mine a new one to remain in the network.

Why Kinetic Needs This

Kademlia is a efficient distributed hash table (DHT) used for peer-to-peer routing. It allows nodes to find each other quickly across a decentralized network. However, vanilla Kademlia is notoriously vulnerable to Sybil attacks and Eclipse attacks because identities are essentially free to create.

Because distance in Kademlia is calculated using the XOR metric between two PeerIds, an attacker could theoretically generate millions of random keypairs in a matter of seconds. If they generate enough keypairs, they will eventually find PeerIds that are “close” to a specific target node in the network. Once they have these strategically placed identities, they can flood the target node’s routing table. The target node, believing these are legitimate close peers, will drop honest peers in favor of the attacker’s peers, effectively isolating the target node from the honest network. This is known as an Eclipse attack, as the attacker surrounds the victim’s view of the network.

By enforcing a Proof of Work requirement on identity creation, Kinetic makes this attack computationally unfeasible and economically unviable. If an attacker wants to generate 1,000 identities near a specific node, and each identity takes 5 minutes of high-memory Argon2 computation to find, the cost of the attack becomes astronomical.

Furthermore, Kinetic introduces the concept of rolling epochs. An identity is only valid for a specific window of time (e.g., 12 hours). This forces the attacker to continuously spend massive hardware resources to maintain their malicious presence across multiple epochs, effectively destroying the financial incentive of a long-term Eclipse attack. If this pow.rs module did not exist, the network’s routing layer could be compromised by a single bad actor with a standard laptop, a simple python script, and ten minutes of spare time.

How It Works

The Proof of Work mechanism in Kinetic is built around the Argon2id hashing algorithm. This is a critical architectural choice that differentiates Kinetic from early blockchain networks. Unlike SHA-256 (used in Bitcoin), which can be easily accelerated using specialized ASICs or parallelized on GPUs, Argon2id is intentionally designed to be memory-hard. It requires significant memory bandwidth and sequential memory access patterns, making it resistant to specialized mining hardware. This keeps the playing field level for standard consumer CPUs and ensures that attackers cannot gain an asymmetric computational advantage by renting cheap, older ASICs.

The Choice of Argon2id

Argon2id is the winner of the Password Hashing Competition (PHC) and is the current industry standard for memory-hard hashing. Kinetic chooses Argon2id over Argon2i or Argon2d for identity mining:

• Argon2d is faster and resistant to GPU cracking, but it is vulnerable to side-channel timing attacks.
• Argon2i is safe from side-channel attacks but less resistant to GPU cracking.
• Argon2id is a hybrid. It uses Argon2i for the first half of the first iteration (preventing side-channel attacks) and Argon2d for the rest (maximizing GPU resistance).

The specific parameters hardcoded into pow.rs are Params::new(16384, 1, 1, None):

• Memory Cost (16384): This dictates that every single hash attempt requires exactly 16 Megabytes of RAM. If an attacker tries to run 1,000 parallel hash attempts to speed up their mining, they immediately need 16 Gigabytes of high-speed memory just for the hashing process.
• Time Cost (1): A single iteration over the memory. This keeps the CPU time reasonable while enforcing the memory bandwidth bottleneck.
• Parallelism (1): A single lane. This ensures the hashing is single-threaded, forcing attackers to scale horizontally (more machines) rather than vertically (wider GPUs).

1. The Staggered Epoch Mechanism

-> See: crates/kinetic-network/src/pow.rs — Lines 35 to 46

In a naive implementation, if an epoch lasts 12 hours, every single node in the network would find its identity invalidated at the exact same moment when the epoch clock clicks over. This would cause a massive, synchronized network collapse as every peer simultaneously drops offline to mine a new identity. To prevent this, Kinetic uses a “staggered” epoch approach.

#![allow(unused)]
fn main() {
// Illustration of the staggering math let offset = u64::from_be_bytes(offset_bytes) % EPOCH_KYNS; let current_epoch = (kyn + offset) / EPOCH_KYNS;
}

The get_staggered_epoch function calculates the current epoch differently for each individual peer. It takes the last 8 bytes of the peer’s PeerId, converts them into an integer, and uses it as an offset modulo the epoch length. This means every peer has their own personal 12-hour window, offset from the global kyn clock by a random amount determined by their public key. Because the offset is deterministic but evenly distributed, node churn becomes a smooth, continuous background process across the network rather than a synchronized event.

Example Scenario:

• Node A has an offset of 0. For Node A, Epoch 1 starts at kyn 1440, Epoch 2 starts at kyn 2880.
• Node B has an offset of 720. For Node B, Epoch 1 starts at kyn 720, Epoch 2 starts at kyn 2160.
• The network is desynchronized in its identity turnover. At any given kyn, only a tiny fraction (1/1440th) of the network is forced to roll over their identities.

2. Mining an Identity (The Grinding Loop)

-> See: crates/kinetic-network/src/pow.rs — Lines 85 to 127

When a Kinetic node starts up, if its current identity has expired (or if it is a fresh node that doesn’t have one), it must mine a new one. The mine_sybil_keypair function runs a continuous, CPU-bound loop. Inside the loop, it performs the following steps:

1. Generates a fresh Ed25519 keypair using random entropy.
2. Extracts the public key and converts it into a PeerId.
3. Calculates the staggered epoch for this specific PeerId using the current network kyn.
4. Computes the Argon2id hash of the PeerId bytes combined with the epoch bytes.

#![allow(unused)]
fn main() {
// The PeerId bytes act as the password input // The epoch bytes act as the mandatory salt argon2.hash_password_into(peer_bytes, &epoch.to_be_bytes(), &mut output)
}

5. Checks the number of leading zero bits in the resulting hash using the leading_zeros helper.

If the hash has enough leading zeros to match the network’s required difficulty, the loop exits successfully, and the keypair is saved as the node’s new identity. If it does not have enough leading zeros, the keypair is immediately discarded, and the loop repeats. Because Argon2id is intentionally slow, this loop blocks the thread for a significant amount of time, proving the node’s computational commitment.

3. Validating Incoming Peers & Epoch Overlap Handover

-> See: crates/kinetic-network/src/pow.rs — Lines 48 to 80

Validating a peer is not a simple boolean check of a single hash. It involves a critical overlap window. When is_valid_sybil_pow runs, it executes the following logic path:

1. Calculate Target Epoch: Determine the peer’s personal staggered epoch for the current network kyn.
2. Current Epoch Check: Run Argon2id on (PeerId, Current_Epoch). If the hash meets the difficulty, return true. The peer is up to date.
3. Previous Epoch Check: If the current epoch check fails, the function checks if current_epoch > 0. If so, it runs Argon2id again on (PeerId, Current_Epoch - 1).
4. Grace Period Approval: If the previous epoch’s hash meets the difficulty, the peer is still approved and true is returned.

Why check both? If the network only accepted the current epoch, then at the exact kyn a node’s epoch transitions from N to N+1, all of its network neighbors would immediately drop its connection. The node would be isolated from the network while it mines its identity for N+1. By checking both N and N-1, the network allows a node to use its N-1 identity for a full additional epoch (12 hours). The node will continue communicating with its neighbors using its N-1 identity while its background threads silently grind out the PoW for epoch N. Once the N identity is found, the node seamlessly swaps its identity without dropping a single connection.

Key Pieces

• EPOCH_KYNS -> See: crates/kinetic-network/src/pow.rs — Line 8 A constant defining the length of an epoch in terms of Drand kyns. Currently set to 1440, which corresponds exactly to 12 hours assuming a standard 30-second kyn interval.

• get_staggered_epoch -> See: crates/kinetic-network/src/pow.rs — Lines 35 to 46 The crucial function that converts the global kyn counter into a peer-specific epoch number. It extracts the last 8 bytes of the PeerId. If the PeerId is shorter than 8 bytes, it right-aligns the bytes into the buffer to prevent massive, unintended value shifts. It then calculates the modulo against EPOCH_KYNS to stagger identity expiration evenly and predictably across the entire network.

• compute_pow_hash -> See: crates/kinetic-network/src/pow.rs — Lines 25 to 32 A helper function that orchestrates the Argon2id hashing process. It enforces the requirement that the PeerId bytes act as the password and the epoch bytes act as the minimum 8-byte salt required by the Argon2 specification.

• leading_zeros -> See: crates/kinetic-network/src/pow.rs — Lines 11 to 22 Iterates over the output hash bytes to count the number of consecutive zero bits at the beginning of the array. It checks full bytes (adding 8 for every 0 byte) and then uses the built-in integer leading_zeros for the first non-zero byte. This bit-level precision is how the network dynamically measures the “difficulty” of a given hash.

• is_valid_sybil_pow -> See: crates/kinetic-network/src/pow.rs — Lines 48 to 80 The validation gatekeeper. Every incoming peer must pass this function, or their connection will be immediately dropped. It uses strict, predefined Argon2 parameters (16MB memory, 1 iteration) to ensure validation is fast enough not to bottleneck the network, while keeping the overall mining process adequately slow.

• mine_sybil_keypair -> See: crates/kinetic-network/src/pow.rs — Lines 85 to 127 The CPU-intensive grinding function that discovers a valid identity. It sets up the Argon2id parameters, captures a start timer using web_time::Instant::now(), and enters an infinite loop. Inside, it generates keys and hashes them until the condition is met. It includes safety checks to panic if called against kyn 0 outside of development mode, ensuring the node does not waste hours mining an identity bound to an uninitialized clock.

How This Connects to the Rest of Kinetic

This module acts as the strict cryptographic bouncer for the entire networking layer. It integrates deeply with libp2p’s connection handling and routing behaviors. Before a peer is allowed to be added to the DHT routing table, its Proof of Work is verified here.

CROSS-CRATE: Drand Kyns — defined and explained in the kinetic-core crate documentation. The current_kyn passed into these functions is derived from the verified Drand randomness beacon.

FORWARD DEPENDENCY: The kinetic-daemon crate (Stage 9) relies on mine_sybil_keypair during its startup sequence. It typically wraps this function in an asynchronous background task so that the node can start its HTTP server and answer health checks while its cryptographic identity is still being mined.

Quick Reference

• PoW Algorithm: Argon2id (memory-hard, ASIC-resistant).
• Validation Memory Cost: 16 MB (16384 KB).
• Epoch Length: 12 hours (1440 kyns).
• Grace Period: 1 previous epoch (an additional 12 hours).
• Difficulty Metric: Contiguous leading zero bits in the resulting hash.
• Dev Mode Bypass: If kinetic_core::config::is_dev_mode() returns true, all Proof of Work checks and mining operations are skipped, allowing for instantaneous local testing.

Open Questions / Things to Revisit

• CPU Blocking Risk: The mine_sybil_keypair function is purely synchronous and CPU-bound. As noted by the inline WARNING comment, if this is called directly inside a tokio async context without utilizing spawn_blocking, it will starve the async executor and cause the node to lock up completely.
• Fixed Argon Parameters: The Argon2id parameters (16MB memory, 1 iteration, 1 parallelism) are currently hardcoded directly into the functions. As hardware naturally improves over the years, these parameters may need to become dynamic or configurable via network consensus to maintain the intended computational difficulty threshold.
• Background Mining Handover: Currently, if an identity expires, the node has to mine a new one. It is crucial that higher-level daemon logic anticipates this expiration and starts mining the next epoch’s keypair in the background before the current one expires, ensuring zero downtime for the node’s network presence.