extern crate alloc;
use alloc::vec::Vec;
use sha3::{digest::{ExtendableOutput, XofReader}, Digest, Sha3_256, Shake256};
use zeroize::Zeroize;
use crate::identity_error::IdentityError;
const HYPERCUBE_DIM: usize = 5;
const NUM_NODES: usize = 1 << HYPERCUBE_DIM; const THRESHOLD_K: usize = 3; const MODULUS_Q: u64 = 8380417;
const TOTAL_SHARES: usize = 5;
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct NodeAddress(pub u8);
impl NodeAddress {
pub fn neighbor(&self, dim: usize) -> Self {
NodeAddress(self.0 ^ (1 << dim))
}
pub fn hamming_distance(&self, other: &Self) -> usize {
(self.0 ^ other.0).count_ones() as usize
}
}
#[derive(Clone, Debug)]
pub struct ZkProofSegment {
pub share_id: u8,
pub share_val: u64,
pub path_tag: [u8; 32],
}
#[derive(Clone, Debug)]
pub struct HypercubePacket {
pub source: NodeAddress,
pub destination: NodeAddress,
pub current_node: NodeAddress,
pub dimension_route: Vec<usize>,
pub route_index: usize,
pub payload: ZkProofSegment,
}
pub struct SecretSharer;
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct HtssShare {
pub index: u8,
pub value: Vec<u8>,
}
const LIMB_BYTES: usize = 2;
const LIMB_EVAL_BYTES: usize = 4;
impl SecretSharer {
pub fn split_key_material(secret: &[u8], nonce: &[u8]) -> Result<Vec<HtssShare>, IdentityError> {
if secret.is_empty() || secret.len() > u32::MAX as usize {
return Err(IdentityError::InvalidInputLength);
}
let mut payload = Vec::with_capacity(4 + secret.len() + 1);
payload.extend_from_slice(&(secret.len() as u32).to_le_bytes());
payload.extend_from_slice(secret);
while payload.len() % LIMB_BYTES != 0 {
payload.push(0);
}
let limb_count = payload.len() / LIMB_BYTES;
let mut shares: Vec<HtssShare> = (1..=TOTAL_SHARES as u8)
.map(|index| HtssShare {
index,
value: Vec::with_capacity(limb_count * LIMB_EVAL_BYTES),
})
.collect();
for limb_idx in 0..limb_count {
let lo = payload[limb_idx * LIMB_BYTES] as u64;
let hi = payload[limb_idx * LIMB_BYTES + 1] as u64;
let limb_value = lo | (hi << 8);
let mut coefficients = Vec::with_capacity(THRESHOLD_K);
coefficients.push(limb_value % MODULUS_Q);
for coeff_idx in 1..THRESHOLD_K {
coefficients.push(Self::derive_coeff_from_secret(
secret, nonce, limb_idx, coeff_idx,
));
}
for share in shares.iter_mut() {
let mut y = 0u64;
let mut x_pow = 1u64;
for &coeff in &coefficients {
y = (y + coeff * x_pow) % MODULUS_Q;
x_pow = (x_pow * share.index as u64) % MODULUS_Q;
}
share.value.extend_from_slice(&(y as u32).to_le_bytes());
}
coefficients.zeroize();
}
payload.zeroize();
Ok(shares)
}
pub fn reconstruct_key_material(shares: &[HtssShare]) -> Result<Vec<u8>, IdentityError> {
if shares.len() < THRESHOLD_K {
return Err(IdentityError::ThresholdNotMet);
}
let width = shares[0].value.len();
if width == 0 || width % LIMB_EVAL_BYTES != 0 {
return Err(IdentityError::SerializationError);
}
if shares.iter().any(|s| s.value.len() != width || s.index == 0) {
return Err(IdentityError::SerializationError);
}
let limb_count = width / LIMB_EVAL_BYTES;
let mut payload = Vec::with_capacity(limb_count * LIMB_BYTES);
for limb_idx in 0..limb_count {
let points: Vec<(u8, u64)> = shares
.iter()
.map(|s| {
let off = limb_idx * LIMB_EVAL_BYTES;
let mut b = [0u8; LIMB_EVAL_BYTES];
b.copy_from_slice(&s.value[off..off + LIMB_EVAL_BYTES]);
(s.index, u32::from_le_bytes(b) as u64)
})
.collect();
let limb = Self::reconstruct_secret(&points);
payload.push((limb & 0xFF) as u8);
payload.push(((limb >> 8) & 0xFF) as u8);
}
if payload.len() < 4 {
return Err(IdentityError::SerializationError);
}
let mut len_bytes = [0u8; 4];
len_bytes.copy_from_slice(&payload[..4]);
let len = u32::from_le_bytes(len_bytes) as usize;
if len == 0 || 4 + len > payload.len() {
payload.zeroize();
return Err(IdentityError::SerializationError);
}
let secret = payload[4..4 + len].to_vec();
payload.zeroize();
Ok(secret)
}
pub fn split_key_material_bytes(
secret: &[u8],
nonce: &[u8],
) -> Result<Vec<u8>, IdentityError> {
let shares = Self::split_key_material(secret, nonce)?;
let width = shares[0].value.len();
let mut out = Vec::with_capacity(1 + 4 + shares.len() * (1 + width));
out.push(shares.len() as u8);
out.extend_from_slice(&(width as u32).to_le_bytes());
for share in &shares {
out.push(share.index);
out.extend_from_slice(&share.value);
}
Ok(out)
}
pub fn reconstruct_key_material_bytes(bytes: &[u8]) -> Result<Vec<u8>, IdentityError> {
if bytes.len() < 5 {
return Err(IdentityError::SerializationError);
}
let count = bytes[0] as usize;
let mut width_bytes = [0u8; 4];
width_bytes.copy_from_slice(&bytes[1..5]);
let width = u32::from_le_bytes(width_bytes) as usize;
if count == 0 || width == 0 {
return Err(IdentityError::SerializationError);
}
let expected = 5 + count * (1 + width);
if bytes.len() != expected {
return Err(IdentityError::SerializationError);
}
let mut shares = Vec::with_capacity(count);
let mut off = 5;
for _ in 0..count {
let index = bytes[off];
off += 1;
shares.push(HtssShare {
index,
value: bytes[off..off + width].to_vec(),
});
off += width;
}
Self::reconstruct_key_material(&shares)
}
fn derive_coeff_from_secret(
secret: &[u8],
nonce: &[u8],
limb_idx: usize,
coeff_idx: usize,
) -> u64 {
let mut hasher = Shake256::default();
sha3::digest::Update::update(&mut hasher, b"AETHEL_HTSS_COEFF_V1");
sha3::digest::Update::update(&mut hasher, &(secret.len() as u32).to_le_bytes());
sha3::digest::Update::update(&mut hasher, secret);
sha3::digest::Update::update(&mut hasher, &(nonce.len() as u32).to_le_bytes());
sha3::digest::Update::update(&mut hasher, nonce);
sha3::digest::Update::update(&mut hasher, &(limb_idx as u64).to_le_bytes());
sha3::digest::Update::update(&mut hasher, &(coeff_idx as u64).to_le_bytes());
let mut xof = hasher.finalize_xof();
loop {
let mut buf = [0u8; 4];
xof.read(&mut buf);
let candidate = (u32::from_le_bytes(buf) & 0x00FF_FFFF) as u64;
if candidate < MODULUS_Q {
return candidate;
}
}
}
#[deprecated(
since = "0.1.1",
note = "threshold not enforced: coefficients derive non-cryptographically from a \
caller-supplied u64 seed, so one share plus that seed recovers the secret. \
Also truncates any secret above ~2^23. Use split_key_material."
)]
pub fn split_secret(secret: u64, k: usize, n: usize, seed: u64) -> Vec<(u8, u64)> {
let mut coefficients = Vec::with_capacity(k);
coefficients.push(secret % MODULUS_Q);
for i in 1..k {
let coeff = Self::derive_coeff(seed, i as u64) % MODULUS_Q;
coefficients.push(coeff);
}
let mut shares = Vec::with_capacity(n);
for x in 1..=(n as u8) {
let mut y = 0u64;
let mut x_pow = 1u64;
for &coeff in &coefficients {
y = (y + coeff.wrapping_mul(x_pow)) % MODULUS_Q;
x_pow = x_pow.wrapping_mul(x as u64) % MODULUS_Q;
}
shares.push((x, y));
}
coefficients.zeroize();
shares
}
fn derive_coeff(seed: u64, idx: u64) -> u64 {
let mut v = seed.wrapping_add(idx.wrapping_mul(0x9e3779b97f4a7c15));
v ^= v >> 30;
v = v.wrapping_mul(0xbf58476d1ce4e5b9);
v ^= v >> 27;
v = v.wrapping_mul(0x94d049bb133111eb);
v ^= v >> 31;
v
}
pub fn reconstruct_secret_checked(shares: &[(u8, u64)]) -> Result<u64, IdentityError> {
if shares.len() < THRESHOLD_K {
return Err(IdentityError::ThresholdNotMet);
}
Ok(Self::reconstruct_secret(shares))
}
pub fn reconstruct_secret(shares: &[(u8, u64)]) -> u64 {
let q = MODULUS_Q as i64;
let mut secret = 0i64;
for i in 0..shares.len() {
let xi = shares[i].0 as i64;
let yi = shares[i].1 as i64;
let mut num = 1i64;
let mut den = 1i64;
for j in 0..shares.len() {
if i != j {
let xj = shares[j].0 as i64;
num = ((num % q) * ((-xj % q + q) % q)) % q;
den = ((den % q) * ((xi - xj % q + q) % q)) % q;
}
}
let den_inv = Self::mod_inverse(den, q);
let lagrange = (num % q * den_inv % q) % q;
let term = (yi % q * lagrange % q) % q;
secret = (secret + term) % q;
}
((secret % q) + q) as u64 % MODULUS_Q
}
fn mod_inverse(a: i64, m: i64) -> i64 {
let mut t = 0i64; let mut newt = 1i64;
let mut r = m; let mut newr = a % m;
while newr != 0 {
let quotient = r / newr;
let temp_t = t - quotient * newt; t = newt; newt = temp_t;
let temp_r = r - quotient * newr; r = newr; newr = temp_r;
}
if r > 1 { return 0; }
if t < 0 { t += m; }
t
}
}
pub struct HypercubeNetwork {
pub nodes: Vec<NodeAddress>,
}
impl HypercubeNetwork {
pub fn new() -> Self {
let nodes = (0..NUM_NODES).map(|i| NodeAddress(i as u8)).collect();
Self { nodes }
}
pub fn compute_orthogonal_paths(_src: NodeAddress, _dst: NodeAddress) -> Vec<Vec<usize>> {
let mut paths = Vec::with_capacity(HYPERCUBE_DIM);
for d_start in 0..HYPERCUBE_DIM {
let mut dim_order = Vec::with_capacity(HYPERCUBE_DIM);
for i in 0..HYPERCUBE_DIM {
dim_order.push((d_start + i) % HYPERCUBE_DIM);
}
paths.push(dim_order);
}
paths
}
pub fn route_payload_shares(
&self,
src: NodeAddress,
dst: NodeAddress,
shares: &[(u8, u64)],
) -> Vec<HypercubePacket> {
let routes = Self::compute_orthogonal_paths(src, dst);
let mut packets = Vec::new();
for (i, share) in shares.iter().enumerate() {
let route_dim_sequence = routes[i % HYPERCUBE_DIM].clone();
let mut hasher = Sha3_256::new();
hasher.update(src.0.to_le_bytes());
hasher.update(dst.0.to_le_bytes());
hasher.update([share.0]);
let mut path_tag = [0u8; 32];
path_tag.copy_from_slice(&hasher.finalize());
let packet = HypercubePacket {
source: src,
destination: dst,
current_node: src,
dimension_route: route_dim_sequence,
route_index: 0,
payload: ZkProofSegment {
share_id: share.0,
share_val: share.1,
path_tag,
},
};
packets.push(packet);
}
let mut delivered_packets = Vec::new();
for mut pkt in packets {
while pkt.current_node != pkt.destination {
let next_dim = pkt.dimension_route[pkt.route_index];
let next_node = pkt.current_node.neighbor(next_dim);
pkt.current_node = next_node;
pkt.route_index += 1;
}
delivered_packets.push(pkt);
}
delivered_packets
}
}
impl Default for HypercubeNetwork {
fn default() -> Self {
Self::new()
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_htss_split_reconstruct() {
let secret: u64 = 5234123;
let seed: u64 = 0xdeadbeef_cafebabe;
let shares = SecretSharer::split_secret(secret, THRESHOLD_K, HYPERCUBE_DIM, seed);
assert_eq!(shares.len(), HYPERCUBE_DIM);
let reconstructed = SecretSharer::reconstruct_secret(&shares[0..THRESHOLD_K]);
assert_eq!(reconstructed, secret);
}
#[test]
fn test_hypercube_routing() {
let network = HypercubeNetwork::new();
let src = NodeAddress(0b00000);
let dst = NodeAddress(0b11111);
let seed: u64 = 0x1234567890abcdef;
let shares = SecretSharer::split_secret(42u64, THRESHOLD_K, HYPERCUBE_DIM, seed);
let delivered = network.route_payload_shares(src, dst, &shares);
assert_eq!(delivered.len(), HYPERCUBE_DIM);
for pkt in &delivered {
assert_eq!(pkt.current_node, dst);
}
}
}