Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_o3db_sync/src/oam/threshold.rs

3.7 KiB, 40 runs

created by r1870400018:11372, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! The 256-bit placement threshold.
2//!
3//! A [`Threshold`] encodes the right-hand side of OAM's placement inequality
4//!
5//! $ "XOR"("peer_id", H("record")) < T $
6//!
7//! where `T = floor(2^256 * n / N)`. The threshold is computed once from the
8//! configuration and then applied to many records, so peer-side placement
9//! decisions reduce to a single 32-byte bytewise comparison.
10//!
11//! Three cases are represented explicitly so the saturation boundary is
12//! unambiguous:
13//!
14//! - [`Threshold::None`] -- `n = 0`. No peer is a holder.
15//! - [`Threshold::Bounded`] -- `0 < n < N`. The placement inequality uses the
16//! stored 256-bit value.
17//! - [`Threshold::All`] -- `n >= N` (or degenerate `N = 0`). Every peer is a
18//! holder, independent of the XOR distance. Treated as "threshold equals
19//! `2^256`", which would not fit in a 256-bit word, so it is held as a
20//! sentinel instead.
21//!
22//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
23//! Anthropic Claude
24
25use oxedyne_fe2o3_core::prelude::*;
26use crate::kademlia::id::{
27 Distance,
28 ID_LEN,
29 NodeId,
30};
31
32
33// 64-bit limbs of the 256-bit threshold during computation. Big-endian, so
34// limb index 0 is the most significant.
35const LIMBS: usize = 4;
36
37
38/// A 256-bit placement threshold with an explicit saturation boundary.
39///
40/// Comparison is strict less-than in the `Bounded` case, mirroring the
41/// inequality in the Ozone chapter of the Hematite specification.
42#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
43pub enum Threshold {
44 None, // n = 0, so no peer holds any record
45 Bounded([u8; ID_LEN]), // 0 < n < N, and the XOR distance must be under it
46 All, // n >= N, or N = 0, so every peer holds every record
47}
48
49impl Threshold {
50 /// `T = floor(2^256 * n / network_size)` for the standard case
51 /// `0 < n < network_size`; the two boundary cases saturate to
52 /// [`Threshold::None`] and [`Threshold::All`].
53 pub fn from_params(n: u64, network_size: u64) -> Self {
54 if n == 0 {
55 return Self::None;
56 }
57 if network_size == 0 || n >= network_size {
58 return Self::All;
59 }
60 // Long division of the dividend `n * 2^256` by `network_size`.
61 //
62 // Dividend, big-endian u64 limbs: [n, 0, 0, 0, 0]. Five limbs because
63 // `n * 2^256` occupies bits 256..(256 + 64); zero-padding the
64 // low 256 bits yields the 5-limb representation.
65 //
66 // For `n < network_size` the top quotient limb is zero, so the
67 // bottom four limbs fit in a 256-bit threshold without truncation.
68 let dividend: [u64; LIMBS + 1] = [n, 0, 0, 0, 0];
69 let divisor = network_size as u128;
70 let mut quotient = [0u64; LIMBS + 1];
71 let mut rem: u128 = 0;
72 for i in 0..=LIMBS {
73 let combined = (rem << 64) | (dividend[i] as u128);
74 quotient[i] = (combined / divisor) as u64;
75 rem = combined % divisor;
76 }
77 // `quotient[0]` must be zero because `n < network_size`. The
78 // meaningful quotient is the lower four limbs. Assemble them
79 // big-endian into the 32-byte representation.
80 let mut out = [0u8; ID_LEN];
81 for i in 0..LIMBS {
82 let start = i * 8;
83 out[start..start + 8].copy_from_slice(&quotient[i + 1].to_be_bytes());
84 }
85 Self::Bounded(out)
86 }
87
88 /// Is a peer at this XOR distance from the record hash a holder?
89 pub fn contains(&self, distance: &Distance) -> bool {
90 match self {
91 Self::None => false,
92 Self::All => true,
93 Self::Bounded(t) => distance.0.as_slice() < t.as_slice(),
94 }
95 }
96
97 /// `None` at the saturation boundaries, which have no finite 256-bit
98 /// representation.
99 pub fn as_bytes(&self) -> Option<&[u8; ID_LEN]> {
100 match self {
101 Self::Bounded(t) => Some(t),
102 _ => None,
103 }
104 }
105
106 /// For a caller driving iterator comparisons against XOR distances without
107 /// rewrapping the bytes.
108 pub fn as_node_id(&self) -> Option<NodeId> {
109 self.as_bytes().map(|b| NodeId::from_bytes(*b))
110 }
111}