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        // A visitor, not <&str>::deserialize: `serde_json::from_value`
145        // (the edge's store RPC) cannot lend borrowed strings — the
146        // borrowed-only form worked everywhere until the first consumer
147        // that couldn't borrow.
148        struct TokenVisitor;
149        impl de::Visitor<'_> for TokenVisitor {
150            type Value = Token;
151            fn expecting(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
152                f.write_str("a waggle token string")
153            }
154            fn visit_str<E: de::Error>(self, s: &str) -> Result<Token, E> {
155                Token::parse(s).map_err(de::Error::custom)
156            }
157        }
158        deserializer.deserialize_str(TokenVisitor)
159    }
160}
161
162#[cfg(test)]
163mod tests {
164    use super::*;
165
166    fn counting_entropy() -> impl FnMut(&mut [u8]) -> Result<(), crate::EntropyError> {
167        let mut state = 0u8;
168        move |buf: &mut [u8]| {
169            for b in buf.iter_mut() {
170                state = state.wrapping_add(37);
171                *b = state;
172            }
173            Ok(())
174        }
175    }
176
177    fn assert_copy<T: Copy>() {}
178
179    #[test]
180    fn size_is_inline_and_copy() {
181        assert_eq!(core::mem::size_of::<Token>(), 24);
182        assert_copy::<Token>();
183    }
184
185    #[test]
186    fn generate_parse_roundtrip() {
187        let mut entropy = counting_entropy();
188        let token = Token::generate(8, &mut entropy).unwrap();
189        assert_eq!(token.as_str().len(), 8);
190        let reparsed = Token::parse(token.as_str()).unwrap();
191        assert_eq!(reparsed, token);
192    }
193
194    #[test]
195    fn parse_rejects_bad_lengths_and_alphabet() {
196        assert_eq!(Token::parse(""), Err(TokenError::Length(0)));
197        assert_eq!(
198            Token::parse("aaaaaaaaaaaaaaaaaaaaaaaa"), // 24 chars
199            Err(TokenError::Length(24))
200        );
201        assert_eq!(Token::parse("abc0def"), Err(TokenError::Alphabet)); // '0' excluded
202        assert_eq!(Token::parse("abcOdef"), Err(TokenError::Alphabet)); // 'O' excluded
203        assert_eq!(Token::parse("abc def"), Err(TokenError::Alphabet));
204    }
205
206    #[test]
207    fn generate_bounds_are_enforced() {
208        let mut entropy = counting_entropy();
209        assert_eq!(Token::generate(0, &mut entropy), Err(TokenError::Length(0)));
210        assert_eq!(
211            Token::generate(24, &mut entropy),
212            Err(TokenError::Length(24))
213        );
214        assert!(Token::generate(MAX_LEN, &mut entropy).is_ok());
215    }
216
217    #[test]
218    fn rejection_sampling_skips_biased_bytes() {
219        // A source that emits one over-bound byte (would alias symbol 0 if
220        // folded) then a valid byte: the token must use only the valid one.
221        let mut phase = 0usize;
222        let mut entropy = move |buf: &mut [u8]| {
223            for b in buf.iter_mut() {
224                *b = if phase % 2 == 0 { 250 } else { 1 };
225                phase += 1;
226            }
227            Ok(())
228        };
229        let token = Token::generate(4, &mut entropy).unwrap();
230        // byte value 1 -> alphabet index 1 -> '2'
231        assert_eq!(token.as_str(), "2222");
232    }
233
234    #[test]
235    fn uniform_distribution_smoke() {
236        // Not a statistical proof (that's a CP-1 property test) — a tripwire
237        // that every alphabet bucket is hit under a spread-out source.
238        // xorshift32: deterministic, but covers the byte range evenly —
239        // unlike the fixed-stride counter, whose consumed positions cycle.
240        let mut state = 0x2026_0707_u32;
241        let mut entropy = move |buf: &mut [u8]| {
242            for b in buf.iter_mut() {
243                state ^= state << 13;
244                state ^= state >> 17;
245                state ^= state << 5;
246                *b = (state & 0xFF) as u8;
247            }
248            Ok(())
249        };
250        let mut seen = [0u32; 58];
251        for _ in 0..2_000 {
252            let t = Token::generate(8, &mut entropy).unwrap();
253            for b in t.as_str().bytes() {
254                let idx = TOKEN_ALPHABET.iter().position(|&a| a == b).unwrap();
255                seen[idx] += 1;
256            }
257        }
258        assert!(seen.iter().all(|&c| c > 0), "alphabet bucket never hit");
259    }
260
261    #[test]
262    fn entropy_failure_surfaces() {
263        let mut broken = |_: &mut [u8]| Err(crate::EntropyError("dead".into()));
264        let err = Token::generate(8, &mut broken).unwrap_err();
265        assert!(matches!(err, TokenError::Entropy(_)));
266    }
267
268    #[test]
269    fn serde_roundtrip_and_validation() {
270        let mut entropy = counting_entropy();
271        let token = Token::generate(8, &mut entropy).unwrap();
272        let json = serde_json::to_string(&token).unwrap();
273        let back: Token = serde_json::from_str(&json).unwrap();
274        assert_eq!(back, token);
275        assert!(serde_json::from_str::<Token>("\"bad token!\"").is_err());
276    }
277}
waggle_core/token.rs

waggle_core/
token.rs
