waggle_core/
token.rs

1//! The token: a short, non-enumerable name for one act of distribution.
2//!
3//! Design commitments (docs `02 §2`, `03 §4`): inline storage (24 bytes,
4//! `Copy`, zero heap — two tokens fit a cache line in maps), the Bitcoin
5//! base58 alphabet (no `0OIl` ambiguity — tokens get read aloud and typed),
6//! and **rejection-sampled** generation so no alphabet position is favored
7//! (modulo bias is how "non-enumerable" quietly stops being true).
8
9use core::fmt;
10use serde::{de, Deserialize, Deserializer, Serialize, Serializer};
11use thiserror::Error;
12
13use crate::entropy::Entropy;
14
15/// The Bitcoin base58 alphabet: 58 symbols, no `0`, `O`, `I`, or `l`.
16pub const TOKEN_ALPHABET: &[u8; 58] = b"123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
17
18/// Largest byte value usable without modulo bias: `232 = 58 * 4`.
19const REJECTION_BOUND: u8 = 232;
20
21const MAX_LEN: usize = 23;
22const DEFAULT_ALLOC: usize = 64;
23
24/// Why a token could not be parsed or generated.
25#[derive(Debug, Error, PartialEq, Eq)]
26pub enum TokenError {
27    /// Length outside `1..=23` characters.
28    #[error("token length {0} outside 1..=23")]
29    Length(usize),
30    /// A character outside the base58 alphabet.
31    #[error("token contains a character outside the base58 alphabet")]
32    Alphabet,
33    /// The entropy source failed while generating.
34    #[error("entropy source failed while generating a token: {0}")]
35    Entropy(String),
36}
37
38/// A waggle token: inline, `Copy`, 24 bytes total.
39///
40/// Tokens are *names*, not data — comparison, hashing, and display are the
41/// whole interface. Construction is either [`Token::parse`] (validated) or
42/// [`Token::generate`] (rejection-sampled from an [`Entropy`] source).
43#[derive(Clone, Copy, PartialEq, Eq, Hash)]
44pub struct Token {
45    len: u8,
46    buf: [u8; MAX_LEN],
47}
48
49impl Token {
50    /// Parse and validate an existing token string.
51    pub fn parse(s: &str) -> Result<Self, TokenError> {
52        let bytes = s.as_bytes();
53        if bytes.is_empty() || bytes.len() > MAX_LEN {
54            return Err(TokenError::Length(bytes.len()));
55        }
56        if !bytes.iter().all(|b| TOKEN_ALPHABET.contains(b)) {
57            return Err(TokenError::Alphabet);
58        }
59        let mut buf = [0u8; MAX_LEN];
60        buf[..bytes.len()].copy_from_slice(bytes);
61        #[allow(clippy::cast_possible_truncation)] // bytes.len() <= 23
62        Ok(Self {
63            len: bytes.len() as u8,
64            buf,
65        })
66    }
67
68    /// Generate a fresh token of `len` characters from `entropy`.
69    ///
70    /// Rejection sampling: bytes ≥ 232 are discarded rather than folded,
71    /// so every alphabet symbol is exactly equally likely.
72    pub fn generate(len: usize, entropy: &mut impl Entropy) -> Result<Self, TokenError> {
73        if len == 0 || len > MAX_LEN {
74            return Err(TokenError::Length(len));
75        }
76        let mut buf = [0u8; MAX_LEN];
77        let mut filled = 0usize;
78        let mut pool = [0u8; DEFAULT_ALLOC];
79        while filled < len {
80            entropy
81                .fill(&mut pool)
82                .map_err(|e| TokenError::Entropy(e.to_string()))?;
83            for &b in &pool {
84                if b < REJECTION_BOUND {
85                    buf[filled] = TOKEN_ALPHABET[(b % 58) as usize];
86                    filled += 1;
87                    if filled == len {
88                        break;
89                    }
90                }
91            }
92        }
93        #[allow(clippy::cast_possible_truncation)] // len <= 23
94        Ok(Self {
95            len: len as u8,
96            buf,
97        })
98    }
99
100    /// The token as a string slice.
101    #[must_use]
102    pub fn as_str(&self) -> &str {
103        // Invariant: buf[..len] came from TOKEN_ALPHABET (pure ASCII), so
104        // this cannot fail; unsafe from_utf8_unchecked is not worth the
105        // audit burden for a cold path.
106        core::str::from_utf8(&self.buf[..self.len as usize]).unwrap_or("")
107    }
108}
109
110impl PartialOrd for Token {
111    fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
112        Some(self.cmp(other))
113    }
114}
115
116impl Ord for Token {
117    /// Lexicographic by string form — deterministic map ordering is what
118    /// R-1's byte-identical serialization rests on.
119    fn cmp(&self, other: &Self) -> core::cmp::Ordering {
120        self.as_str().cmp(other.as_str())
121    }
122}
123
124impl fmt::Display for Token {
125    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
126        f.write_str(self.as_str())
127    }
128}
129
130impl fmt::Debug for Token {
131    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
132        write!(f, "Token({})", self.as_str())
133    }
134}
135
136impl Serialize for Token {
137    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
138        serializer.serialize_str(self.as_str())
139    }
140}
141
142impl<'de> Deserialize<'de> for Token {
143    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
144        let s = <&str>::deserialize(deserializer)?;
145        Self::parse(s).map_err(de::Error::custom)
146    }
147}
148
149#[cfg(test)]
150mod tests {
151    use super::*;
152
153    fn counting_entropy() -> impl FnMut(&mut [u8]) -> Result<(), crate::EntropyError> {
154        let mut state = 0u8;
155        move |buf: &mut [u8]| {
156            for b in buf.iter_mut() {
157                state = state.wrapping_add(37);
158                *b = state;
159            }
160            Ok(())
161        }
162    }
163
164    fn assert_copy<T: Copy>() {}
165
166    #[test]
167    fn size_is_inline_and_copy() {
168        assert_eq!(core::mem::size_of::<Token>(), 24);
169        assert_copy::<Token>();
170    }
171
172    #[test]
173    fn generate_parse_roundtrip() {
174        let mut entropy = counting_entropy();
175        let token = Token::generate(8, &mut entropy).unwrap();
176        assert_eq!(token.as_str().len(), 8);
177        let reparsed = Token::parse(token.as_str()).unwrap();
178        assert_eq!(reparsed, token);
179    }
180
181    #[test]
182    fn parse_rejects_bad_lengths_and_alphabet() {
183        assert_eq!(Token::parse(""), Err(TokenError::Length(0)));
184        assert_eq!(
185            Token::parse("aaaaaaaaaaaaaaaaaaaaaaaa"), // 24 chars
186            Err(TokenError::Length(24))
187        );
188        assert_eq!(Token::parse("abc0def"), Err(TokenError::Alphabet)); // '0' excluded
189        assert_eq!(Token::parse("abcOdef"), Err(TokenError::Alphabet)); // 'O' excluded
190        assert_eq!(Token::parse("abc def"), Err(TokenError::Alphabet));
191    }
192
193    #[test]
194    fn generate_bounds_are_enforced() {
195        let mut entropy = counting_entropy();
196        assert_eq!(Token::generate(0, &mut entropy), Err(TokenError::Length(0)));
197        assert_eq!(
198            Token::generate(24, &mut entropy),
199            Err(TokenError::Length(24))
200        );
201        assert!(Token::generate(MAX_LEN, &mut entropy).is_ok());
202    }
203
204    #[test]
205    fn rejection_sampling_skips_biased_bytes() {
206        // A source that emits one over-bound byte (would alias symbol 0 if
207        // folded) then a valid byte: the token must use only the valid one.
208        let mut phase = 0usize;
209        let mut entropy = move |buf: &mut [u8]| {
210            for b in buf.iter_mut() {
211                *b = if phase % 2 == 0 { 250 } else { 1 };
212                phase += 1;
213            }
214            Ok(())
215        };
216        let token = Token::generate(4, &mut entropy).unwrap();
217        // byte value 1 -> alphabet index 1 -> '2'
218        assert_eq!(token.as_str(), "2222");
219    }
220
221    #[test]
222    fn uniform_distribution_smoke() {
223        // Not a statistical proof (that's a CP-1 property test) — a tripwire
224        // that every alphabet bucket is hit under a spread-out source.
225        // xorshift32: deterministic, but covers the byte range evenly —
226        // unlike the fixed-stride counter, whose consumed positions cycle.
227        let mut state = 0x2026_0707_u32;
228        let mut entropy = move |buf: &mut [u8]| {
229            for b in buf.iter_mut() {
230                state ^= state << 13;
231                state ^= state >> 17;
232                state ^= state << 5;
233                *b = (state & 0xFF) as u8;
234            }
235            Ok(())
236        };
237        let mut seen = [0u32; 58];
238        for _ in 0..2_000 {
239            let t = Token::generate(8, &mut entropy).unwrap();
240            for b in t.as_str().bytes() {
241                let idx = TOKEN_ALPHABET.iter().position(|&a| a == b).unwrap();
242                seen[idx] += 1;
243            }
244        }
245        assert!(seen.iter().all(|&c| c > 0), "alphabet bucket never hit");
246    }
247
248    #[test]
249    fn entropy_failure_surfaces() {
250        let mut broken = |_: &mut [u8]| Err(crate::EntropyError("dead".into()));
251        let err = Token::generate(8, &mut broken).unwrap_err();
252        assert!(matches!(err, TokenError::Entropy(_)));
253    }
254
255    #[test]
256    fn serde_roundtrip_and_validation() {
257        let mut entropy = counting_entropy();
258        let token = Token::generate(8, &mut entropy).unwrap();
259        let json = serde_json::to_string(&token).unwrap();
260        let back: Token = serde_json::from_str(&json).unwrap();
261        assert_eq!(back, token);
262        assert!(serde_json::from_str::<Token>("\"bad token!\"").is_err());
263    }
264}
waggle_core/token.rs

waggle_core/
token.rs
