From 9821aabf0b50d2487b07502d3d2cd89e7d62bdbe Mon Sep 17 00:00:00 2001 From: murilo ijanc Date: Tue, 24 Mar 2026 15:04:03 -0300 Subject: Initial commit NAT-aware Kademlia DHT library for peer-to-peer networks. Features: - Distributed key-value storage (iterative FIND_NODE, FIND_VALUE, STORE) - NAT traversal via DTUN hole-punching and proxy relay - Reliable Datagram Protocol (RDP) with 7-state connection machine - Datagram transport with automatic fragmentation/reassembly - Ed25519 packet authentication - 256-bit node IDs (Ed25519 public keys) - Rate limiting, ban list, and eclipse attack mitigation - Persistence and metrics - OpenBSD and Linux support --- src/id.rs | 238 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 238 insertions(+) create mode 100644 src/id.rs (limited to 'src/id.rs') diff --git a/src/id.rs b/src/id.rs new file mode 100644 index 0000000..b2e37eb --- /dev/null +++ b/src/id.rs @@ -0,0 +1,238 @@ +//! 256-bit node identity for Kademlia. +//! +//! NodeId is 32 bytes — the same size as an Ed25519 +//! public key. For node IDs, `NodeId = public_key` +//! directly. For DHT key hashing, SHA-256 maps +//! arbitrary data into the 256-bit ID space. + +use crate::sys; +use std::fmt; + +/// Length of a node ID in bytes (32 = Ed25519 pubkey). +pub const ID_LEN: usize = 32; + +/// Number of bits in a node ID. +pub const ID_BITS: usize = ID_LEN * 8; // 256 + +/// A 256-bit node identifier. +/// +/// Provides XOR distance and lexicographic ordering as +/// required by Kademlia routing. +#[derive(Clone, Copy, PartialEq, Eq, Hash)] +pub struct NodeId([u8; ID_LEN]); + +impl NodeId { + /// Generate a random node ID. + pub fn random() -> Self { + let mut buf = [0u8; ID_LEN]; + sys::random_bytes(&mut buf); + Self(buf) + } + + /// Create a node ID from raw bytes. + pub fn from_bytes(b: [u8; ID_LEN]) -> Self { + Self(b) + } + + /// Create a node ID by SHA-256 hashing arbitrary + /// data. + /// + /// Used by `put`/`get` to map keys into the 256-bit + /// Kademlia ID space. + pub fn from_key(data: &[u8]) -> Self { + use sha2::{Digest, Sha256}; + let hash = Sha256::digest(data); + let mut buf = [0u8; ID_LEN]; + buf.copy_from_slice(&hash); + Self(buf) + } + + /// Return the raw bytes. + pub fn as_bytes(&self) -> &[u8; ID_LEN] { + &self.0 + } + + /// XOR distance between two node IDs. + pub fn distance(&self, other: &NodeId) -> NodeId { + let mut out = [0u8; ID_LEN]; + for (i, byte) in out.iter_mut().enumerate() { + *byte = self.0[i] ^ other.0[i]; + } + NodeId(out) + } + + /// Number of leading zero bits in this ID. + /// + /// Used to determine the k-bucket index. + pub fn leading_zeros(&self) -> u32 { + for (i, &byte) in self.0.iter().enumerate() { + if byte != 0 { + return (i as u32) * 8 + byte.leading_zeros(); + } + } + (ID_LEN as u32) * 8 + } + + /// Check if all bytes are zero. + pub fn is_zero(&self) -> bool { + self.0.iter().all(|&b| b == 0) + } + + /// Parse from a hexadecimal string (64 chars). + pub fn from_hex(s: &str) -> Option { + if s.len() != ID_LEN * 2 { + return None; + } + let mut buf = [0u8; ID_LEN]; + for i in 0..ID_LEN { + buf[i] = u8::from_str_radix(&s[i * 2..i * 2 + 2], 16).ok()?; + } + Some(Self(buf)) + } + + /// Format as a hexadecimal string (64 chars). + pub fn to_hex(&self) -> String { + self.0.iter().map(|b| format!("{b:02x}")).collect() + } + + /// Serialize to a byte slice. + /// + /// # Panics + /// Panics if `buf.len() < ID_LEN` (32). + pub fn write_to(&self, buf: &mut [u8]) { + debug_assert!( + buf.len() >= ID_LEN, + "NodeId::write_to: buf too small ({} < {ID_LEN})", + buf.len() + ); + buf[..ID_LEN].copy_from_slice(&self.0); + } + + /// Deserialize from a byte slice. + /// + /// # Panics + /// Panics if `buf.len() < ID_LEN` (32). + pub fn read_from(buf: &[u8]) -> Self { + debug_assert!( + buf.len() >= ID_LEN, + "NodeId::read_from: buf too small ({} < {ID_LEN})", + buf.len() + ); + let mut id = [0u8; ID_LEN]; + id.copy_from_slice(&buf[..ID_LEN]); + Self(id) + } +} + +impl Ord for NodeId { + fn cmp(&self, other: &Self) -> std::cmp::Ordering { + self.0.cmp(&other.0) + } +} + +impl PartialOrd for NodeId { + fn partial_cmp(&self, other: &Self) -> Option { + Some(self.cmp(other)) + } +} + +impl fmt::Debug for NodeId { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "NodeId({})", &self.to_hex()[..8]) + } +} + +impl fmt::Display for NodeId { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "{}", self.to_hex()) + } +} + +impl AsRef<[u8]> for NodeId { + fn as_ref(&self) -> &[u8] { + &self.0 + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn zero_distance() { + let id = NodeId::from_bytes([0xAB; ID_LEN]); + let d = id.distance(&id); + assert!(d.is_zero()); + } + + #[test] + fn xor_symmetric() { + let a = NodeId::from_bytes([0x01; ID_LEN]); + let b = NodeId::from_bytes([0xFF; ID_LEN]); + assert_eq!(a.distance(&b), b.distance(&a)); + } + + #[test] + fn leading_zeros_all_zero() { + let z = NodeId::from_bytes([0; ID_LEN]); + assert_eq!(z.leading_zeros(), 256); + } + + #[test] + fn leading_zeros_first_bit() { + let mut buf = [0u8; ID_LEN]; + buf[0] = 0x80; + let id = NodeId::from_bytes(buf); + assert_eq!(id.leading_zeros(), 0); + } + + #[test] + fn leading_zeros_ninth_bit() { + let mut buf = [0u8; ID_LEN]; + buf[1] = 0x80; + let id = NodeId::from_bytes(buf); + assert_eq!(id.leading_zeros(), 8); + } + + #[test] + fn hex_roundtrip() { + let id = NodeId::from_bytes([ + 0xDE, 0xAD, 0xBE, 0xEF, 0x01, 0x23, 0x45, 0x67, 0x89, 0xAB, 0xCD, + 0xEF, 0xFE, 0xDC, 0xBA, 0x98, 0x76, 0x54, 0x32, 0x10, 0xDE, 0xAD, + 0xBE, 0xEF, 0x01, 0x23, 0x45, 0x67, 0x89, 0xAB, 0xCD, 0xEF, + ]); + let hex = id.to_hex(); + assert_eq!(hex.len(), 64); + assert_eq!(NodeId::from_hex(&hex), Some(id)); + } + + #[test] + fn from_key_deterministic() { + let a = NodeId::from_key(b"hello"); + let b = NodeId::from_key(b"hello"); + assert_eq!(a, b); + } + + #[test] + fn from_key_different_inputs() { + let a = NodeId::from_key(b"hello"); + let b = NodeId::from_key(b"world"); + assert_ne!(a, b); + } + + #[test] + fn ordering_is_lexicographic() { + let a = NodeId::from_bytes([0x00; ID_LEN]); + let b = NodeId::from_bytes([0xFF; ID_LEN]); + assert!(a < b); + } + + #[test] + fn write_read_roundtrip() { + let id = NodeId::from_bytes([0x42; ID_LEN]); + let mut buf = [0u8; ID_LEN]; + id.write_to(&mut buf); + let id2 = NodeId::read_from(&buf); + assert_eq!(id, id2); + } +} -- cgit v1.2.3