av_receipts/
jcs.rs

1//! RFC 8785 — JSON Canonicalization Scheme (JCS).
2//!
3//! Rules implemented (and tested against the RFC's own vectors):
4//! - object keys sorted by **UTF-16 code units** (surrogate order, not byte
5//!   order — they differ for supplementary-plane characters);
6//! - numbers serialized with ECMAScript `ToString(Number)` semantics
7//!   (shortest round-trip digits; decimal notation for exponents in
8//!   (-7, 21); `e+`/`e-` exponential outside; `-0` → `0`);
9//! - strings minimally escaped (`\"`, `\\`, `\b`, `\f`, `\n`, `\r`, `\t`,
10//!   `\u00XX` for other controls; everything else literal UTF-8);
11//! - no insignificant whitespace.
12//!
13//! Integers beyond ±2^53 are **rejected** (not silently rounded): JCS numbers
14//! are IEEE-754 doubles and precision loss would corrupt canonical hashes
15//! (silent-error class D13.4).
16
17use serde_json::Value;
18use std::fmt::Write as _;
19
20/// Canonicalization failures.
21#[derive(Debug, thiserror::Error, PartialEq, Eq)]
22#[non_exhaustive]
23pub enum JcsError {
24    /// Integer outside the exactly-representable double range.
25    #[error("integer {0} outside ±2^53; JCS would lose precision")]
26    UnsafeInteger(String),
27    /// Non-finite number (unreachable via `serde_json::Value`, kept for defense).
28    #[error("non-finite number cannot be canonicalized")]
29    NonFinite,
30    /// Value nesting exceeds `MAX_NESTED_DEPTH`.
31    ///
32    /// Current call sites all feed `canonicalize` a `Value` that was
33    /// parsed by `serde_json::from_slice` (default recursion limit
34    /// 128), or serialized from a typed struct with bounded depth,
35    /// so this cap is transitively already enforced. The cap here is
36    /// defense-in-depth against a future caller that pipes an
37    /// unbounded-parsed `Value` (e.g. `serde_json::Deserializer::
38    /// disable_recursion_limit`) or a merged deep tree — without
39    /// this bound, `write_value` would recurse until the OS stack
40    /// overflows.
41    #[error("value nesting exceeds {0}; JCS refuses to recurse further")]
42    TooDeep(usize),
43}
44
45/// Matches `av_receipts::receipt::MAX_NESTED_DEPTH`
46/// (128), which is also the serde_json default parser recursion
47/// limit — anything a legit strict-load receipt could carry.
48const MAX_NESTED_DEPTH: usize = 128;
49
50/// Canonicalize a JSON value per RFC 8785. Returns the canonical UTF-8 string.
51pub fn canonicalize(value: &Value) -> Result<String, JcsError> {
52    // Typical receipt canonicalizes to a few hundred bytes; pre-allocate to
53    // avoid the growth-doubling churn on the first few pushes.
54    let mut out = String::with_capacity(512);
55    write_value(value, &mut out, 0)?;
56    Ok(out)
57}
58
59fn write_value(value: &Value, out: &mut String, depth: usize) -> Result<(), JcsError> {
60    if depth > MAX_NESTED_DEPTH {
61        return Err(JcsError::TooDeep(MAX_NESTED_DEPTH));
62    }
63    match value {
64        Value::Null => out.push_str("null"),
65        Value::Bool(true) => out.push_str("true"),
66        Value::Bool(false) => out.push_str("false"),
67        Value::Number(n) => write_number(n, out)?,
68        Value::String(s) => write_string(s, out),
69        Value::Array(items) => {
70            out.push('[');
71            for (i, item) in items.iter().enumerate() {
72                if i > 0 {
73                    out.push(',');
74                }
75                write_value(item, out, depth + 1)?;
76            }
77            out.push(']');
78        }
79        Value::Object(map) => {
80            // Sort keys by UTF-16 code-unit sequence.
81            let mut keys: Vec<&String> = map.keys().collect();
82            keys.sort_by(|a, b| utf16_cmp(a, b));
83            out.push('{');
84            for (i, key) in keys.iter().enumerate() {
85                if i > 0 {
86                    out.push(',');
87                }
88                write_string(key, out);
89                out.push(':');
90                if let Some(v) = map.get(*key) {
91                    write_value(v, out, depth + 1)?;
92                }
93            }
94            out.push('}');
95        }
96    }
97    Ok(())
98}
99
100/// Compare two strings by their UTF-16 code-unit sequences (RFC 8785 §3.2.3).
101fn utf16_cmp(a: &str, b: &str) -> std::cmp::Ordering {
102    a.encode_utf16().cmp(b.encode_utf16())
103}
104
105fn write_string(s: &str, out: &mut String) {
106    out.push('"');
107    for ch in s.chars() {
108        match ch {
109            '"' => out.push_str("\\\""),
110            '\\' => out.push_str("\\\\"),
111            '\u{0008}' => out.push_str("\\b"),
112            '\u{000C}' => out.push_str("\\f"),
113            '\n' => out.push_str("\\n"),
114            '\r' => out.push_str("\\r"),
115            '\t' => out.push_str("\\t"),
116            c if (c as u32) < 0x20 => {
117                let _ = write!(out, "\\u{:04x}", c as u32);
118            }
119            c => out.push(c),
120        }
121    }
122    out.push('"');
123}
124
125use av_core::error::JCS_SAFE_MAX;
126
127fn write_number(n: &serde_json::Number, out: &mut String) -> Result<(), JcsError> {
128    if let Some(u) = n.as_u64() {
129        if u > JCS_SAFE_MAX {
130            return Err(JcsError::UnsafeInteger(u.to_string()));
131        }
132        let _ = write!(out, "{u}");
133        return Ok(());
134    }
135    if let Some(i) = n.as_i64() {
136        if i < -(JCS_SAFE_MAX as i64) {
137            return Err(JcsError::UnsafeInteger(i.to_string()));
138        }
139        let _ = write!(out, "{i}");
140        return Ok(());
141    }
142    let f = n.as_f64().ok_or(JcsError::NonFinite)?;
143    if !f.is_finite() {
144        return Err(JcsError::NonFinite);
145    }
146    // Round-trip guard, symmetric with the integer paths above: every
147    // double with magnitude in (2^53, 10^21) is integer-valued (the
148    // IEEE-754 spacing is ≥ 1 past 2^53) and ECMAScript rendering emits
149    // it as pure integer digits. Re-parsing that canonical text yields an
150    // integer above the ±2^53 cap, which the integer path refuses — so a
151    // document signed over such a value could never re-canonicalize for
152    // verification from its parsed form (silent-error class D13.4, via
153    // the float back door). At or below 2^53 the value is exact; at or
154    // above 10^21 the rendering is exponential and re-parses as a double.
155    #[allow(clippy::cast_precision_loss)] // 2^53 is exactly representable
156    if f.abs() > JCS_SAFE_MAX as f64 && f.abs() < 1e21 {
157        return Err(JcsError::UnsafeInteger(ecma_number(f)));
158    }
159    out.push_str(&ecma_number(f));
160    Ok(())
161}
162
163/// ECMAScript `ToString(Number)` (ECMA-262 §6.1.6.1.20) for finite doubles.
164///
165/// Digits come from ryu (shortest **correctly-rounded** representation —
166/// Rust's `{:e}`/Grisu is shortest but not always correctly rounded, which the
167/// RFC 8785 Appendix vectors catch); the ECMAScript layout rules are then
168/// applied to (digits, k).
169fn ecma_number(f: f64) -> String {
170    if f == 0.0 {
171        return "0".to_owned(); // covers -0.0 per ES semantics
172    }
173    if f < 0.0 {
174        let mut s = String::with_capacity(24);
175        s.push('-');
176        s.push_str(&ecma_number(-f));
177        return s;
178    }
179    let mut buf = ryu::Buffer::new();
180    let printed = buf.format_finite(f);
181    let (digits, k) = digits_and_k(printed);
182    let digits = digits.as_str();
183    let n = digits.len() as i64;
184
185    if (1..=21).contains(&k) && n <= k {
186        // Integer: digits followed by k-n zeros.
187        let mut s = String::from(digits);
188        for _ in 0..(k - n) {
189            s.push('0');
190        }
191        s
192    } else if (1..=21).contains(&k) {
193        // Decimal point inside the digits; 1 <= k < n here so the split is in-bounds.
194        #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
195        let (int_part, frac_part) = digits.split_at(k as usize);
196        format!("{int_part}.{frac_part}")
197    } else if (-5..=0).contains(&k) {
198        // 0.000ddd… (ECMA-262: −6 < k ≤ 0)
199        let mut s = String::from("0.");
200        for _ in 0..(-k) {
201            s.push('0');
202        }
203        s.push_str(digits);
204        s
205    } else {
206        // Exponential: d[.ddd]e±(k-1)
207        let exp_val = k - 1;
208        let sign = if exp_val >= 0 { "+" } else { "-" };
209        let (first, rest) = digits.split_at(1);
210        if rest.is_empty() {
211            format!("{first}e{sign}{}", exp_val.abs())
212        } else {
213            format!("{first}.{rest}e{sign}{}", exp_val.abs())
214        }
215    }
216}
217
218/// Decompose a ryu-printed positive finite float (`"123.45"`, `"1.5e-7"`,
219/// `"12.0"`) into shortest digit string and ECMAScript `k` (value =
220/// 0.digits × 10^k).
221fn digits_and_k(printed: &str) -> (String, i64) {
222    let (mantissa, e) = match printed.split_once(['e', 'E']) {
223        Some((m, exp)) => (m, exp.parse::<i64>().unwrap_or(0)),
224        None => (printed, 0),
225    };
226    let (int_part, frac_part) = match mantissa.split_once('.') {
227        Some((i, f)) => (i, f),
228        None => (mantissa, ""),
229    };
230    let int_stripped = int_part.trim_start_matches('0');
231    let (raw, k) = if int_stripped.is_empty() {
232        let lead_zeros = frac_part.len() - frac_part.trim_start_matches('0').len();
233        (
234            frac_part.trim_start_matches('0').to_owned(),
235            e - lead_zeros as i64,
236        )
237    } else {
238        (
239            format!("{int_stripped}{frac_part}"),
240            int_stripped.len() as i64 + e,
241        )
242    };
243    let digits = raw.trim_end_matches('0');
244    if digits.is_empty() {
245        ("0".to_owned(), k)
246    } else {
247        (digits.to_owned(), k)
248    }
249}
250
251#[cfg(test)]
252mod tests {
253    #![allow(clippy::unwrap_used, clippy::expect_used, clippy::panic)]
254
255    use super::*;
256    use serde_json::json;
257
258    /// RFC 8785 Appendix B number vectors (IEEE-754 bit patterns → canonical text).
259    #[test]
260    fn rfc8785_appendix_b_numbers() {
261        let vectors: &[(u64, &str)] = &[
262            (0x0000000000000000, "0"),
263            (0x8000000000000000, "0"), // -0 → 0
264            (0x0000000000000001, "5e-324"),
265            (0x8000000000000001, "-5e-324"),
266            (0x7fefffffffffffff, "1.7976931348623157e+308"),
267            (0xffefffffffffffff, "-1.7976931348623157e+308"),
268            (0x4340000000000000, "9007199254740992"),
269            (0xc340000000000000, "-9007199254740992"),
270            (0x444b1ae4d6e2ef50, "1e+21"),
271            (0x3eb0c6f7a0b5ed8d, "0.000001"),
272            (0x3e7ad7f29abcaf48, "1e-7"),
273            (0x41b3de4355555553, "333333333.3333332"),
274            (0x41b3de4355555554, "333333333.33333325"),
275            (0x41b3de4355555555, "333333333.3333333"),
276            (0x41b3de4355555556, "333333333.3333334"),
277            (0x41b3de4355555557, "333333333.33333343"),
278            (0xbecbf647612f3696, "-0.0000033333333333333333"),
279            (0x43143ff3c1cb0959, "1424953923781206.2"),
280        ];
281        for (bits, expected) in vectors {
282            let f = f64::from_bits(*bits);
283            assert_eq!(&ecma_number(f), expected, "bits {bits:#018x}");
284        }
285    }
286
287    #[test]
288    fn integer_forms() {
289        assert_eq!(ecma_number(1.0), "1");
290        assert_eq!(ecma_number(42.0), "42");
291        assert_eq!(ecma_number(100000.0), "100000");
292        assert_eq!(ecma_number(1e20), "100000000000000000000");
293        assert_eq!(ecma_number(1e21), "1e+21");
294        assert_eq!(ecma_number(-1e21), "-1e+21");
295    }
296
297    /// A double in (2^53, 10^21) renders as pure integer digits whose
298    /// re-parse is an integer above the ±2^53 cap — the canonical text of
299    /// a signed document would fail re-canonicalization at verify time.
300    /// Refused at write time, symmetric with the integer path; the
301    /// boundaries stay accepted and idempotent.
302    #[test]
303    fn integer_form_doubles_beyond_2_53_are_refused() {
304        let refused = [2.993466907830268e18, 9007199254740994.0, -9.999e20];
305        for f in refused {
306            let value = json!([f]);
307            assert!(
308                matches!(canonicalize(&value), Err(JcsError::UnsafeInteger(_))),
309                "expected UnsafeInteger for {f}"
310            );
311        }
312        // Boundary and beyond-range values stay accepted and roundtrip.
313        for f in [9007199254740992.0f64, -9007199254740992.0, 1e21, 1e300, -5e-324] {
314            let first = canonicalize(&json!([f])).unwrap();
315            let reparsed: Value = serde_json::from_str(&first).unwrap();
316            assert_eq!(
317                canonicalize(&reparsed).unwrap(),
318                first,
319                "canonical form of {f} must re-canonicalize identically"
320            );
321        }
322    }
323
324    #[test]
325    fn fraction_forms() {
326        assert_eq!(ecma_number(0.5), "0.5");
327        assert_eq!(ecma_number(0.000001), "0.000001");
328        assert_eq!(ecma_number(0.0000001), "1e-7");
329        assert_eq!(ecma_number(1.5), "1.5");
330        assert_eq!(ecma_number(1.2345678901234567), "1.2345678901234567");
331    }
332
333    /// RFC 8785 §3.2.3 key-sorting example (UTF-16 order incl. supplementary chars).
334    #[test]
335    fn rfc8785_key_sorting() {
336        // Keys via JSON escapes (editor normalization must not corrupt the vector):
337        // \u20AC €, \uD83D\uDE02 😂 (U+1F602), \uFB33 דּ (precomposed).
338        // UTF-16 code-unit order: 20AC < D83D < FB33 — differs from code-point
339        // order, where 1F602 would sort last.
340        let v: Value = serde_json::from_str(r#"{"\uFB33": 3, "\uD83D\uDE02": 2, "\u20AC": 1}"#).unwrap();
341        let c = canonicalize(&v).unwrap();
342        assert_eq!(c, "{\"\u{20ac}\":1,\"\u{1f602}\":2,\"\u{fb33}\":3}");
343    }
344
345    /// RFC 8785 Appendix A weird-input vector.
346    #[test]
347    fn rfc8785_structure_vector() {
348        let input = r#"{
349          "numbers": [333333333.33333329, 1E30, 4.50, 2e-3, 0.000000000000000000000000001],
350          "string": "\u20ac$\u000F\u000aA'\u0042\u0022\u005c\\\"\/",
351          "literals": [null, true, false]
352        }"#;
353        let v: Value = serde_json::from_str(input).unwrap();
354        let c = canonicalize(&v).unwrap();
355        let expected = "{\"literals\":[null,true,false],\"numbers\":[333333333.3333333,1e+30,4.5,0.002,1e-27],\"string\":\"€$\\u000f\\nA'B\\\"\\\\\\\\\\\"/\"}";
356        assert_eq!(c, expected);
357    }
358
359    #[test]
360    fn string_escapes() {
361        let v = json!({"a": "line\nbreak\ttab\u{0001}ctl\"quote\\back"});
362        let c = canonicalize(&v).unwrap();
363        assert_eq!(c, "{\"a\":\"line\\nbreak\\ttab\\u0001ctl\\\"quote\\\\back\"}");
364    }
365
366    #[test]
367    fn unsafe_integers_rejected() {
368        let over = serde_json::Number::from((1u64 << 53) + 1);
369        let v = Value::Number(over);
370        assert_eq!(
371            canonicalize(&v),
372            Err(JcsError::UnsafeInteger(((1u64 << 53) + 1).to_string()))
373        );
374        let under = serde_json::Number::from(-(1i64 << 53) - 1);
375        assert!(canonicalize(&Value::Number(under)).is_err());
376        // Exactly ±2^53 is fine.
377        assert!(canonicalize(&json!(1u64 << 53)).is_ok());
378        assert!(canonicalize(&json!(-(1i64 << 53))).is_ok());
379    }
380
381    #[test]
382    fn insertion_order_does_not_matter() {
383        // serde_json preserve_order keeps insertion order, so these two Values
384        // have different internal order — canonical output must be identical.
385        let a: Value = serde_json::from_str(r#"{"z":1,"a":2,"m":{"y":1,"b":2}}"#).unwrap();
386        let b: Value = serde_json::from_str(r#"{"a":2,"m":{"b":2,"y":1},"z":1}"#).unwrap();
387        assert_eq!(canonicalize(&a).unwrap(), canonicalize(&b).unwrap());
388    }
389
390    #[test]
391    fn canonicalization_is_idempotent() {
392        let v = json!({"b": [1.5, "x", {"k": 1e21}], "a": null});
393        let once = canonicalize(&v).unwrap();
394        let reparsed: Value = serde_json::from_str(&once).unwrap();
395        let twice = canonicalize(&reparsed).unwrap();
396        assert_eq!(once, twice);
397    }
398
399    #[test]
400    fn empty_containers() {
401        assert_eq!(canonicalize(&json!({})).unwrap(), "{}");
402        assert_eq!(canonicalize(&json!([])).unwrap(), "[]");
403        assert_eq!(canonicalize(&json!("")).unwrap(), "\"\"");
404    }
405
406    #[test]
407    fn space_at_boundary_u0020_is_not_escaped() {
408        // The escape guard is `< 0x20`: space (U+0020) sits at the boundary
409        // and must stay literal, not become "\u0020". This detects the
410        // <-vs-<= off-by-one silently corrupting canonical output.
411        let v = json!({"a": "a b"});
412        assert_eq!(canonicalize(&v).unwrap(), "{\"a\":\"a b\"}");
413        // And U+001F just below the boundary DOES get escaped.
414        let v2 = json!({"a": "a\u{001f}b"});
415        assert_eq!(canonicalize(&v2).unwrap(), "{\"a\":\"a\\u001fb\"}");
416    }
417
418    #[test]
419    fn positive_zero_never_prints_with_a_minus_sign() {
420        // ES semantics: both zeros print "0". The `f == 0.0` early return
421        // covers -0.0 too (IEEE: -0.0 == 0.0), and it must stay ahead of the
422        // sign-handling branch — dropping or reordering it would send -0.0
423        // through ryu and emit "-0".
424        assert_eq!(ecma_number(0.0), "0");
425        assert_eq!(ecma_number(-0.0), "0");
426    }
427
428    /// Recursion is capped at `MAX_NESTED_DEPTH`. All
429    /// current call sites feed `canonicalize` a `Value` parsed by
430    /// serde_json (default limit 128) so this cap is transitively
431    /// redundant today, but a future caller that pipes a
432    /// disable_recursion_limit-parsed Value would otherwise
433    /// stack-overflow. Build a nested array manually (bypassing
434    /// serde_json's parser cap) and assert `TooDeep` is returned
435    /// cleanly rather than the process crashing.
436    /// The array test above leaves the
437    /// `write_value(v, out, depth + 1)` recursion in the *object* arm
438    /// unpinned — a mutant that stops incrementing depth there would
439    /// canonicalize unbounded object nesting and stack-overflow on
440    /// hostile input. Same construction, maps instead of arrays.
441    #[test]
442    fn canonicalize_refuses_pathologically_nested_objects() {
443        let mut v = Value::Null;
444        for _ in 0..MAX_NESTED_DEPTH + 10 {
445            let mut map = serde_json::Map::new();
446            map.insert("k".to_owned(), v);
447            v = Value::Object(map);
448        }
449        assert_eq!(canonicalize(&v), Err(JcsError::TooDeep(MAX_NESTED_DEPTH)));
450    }
451
452    #[test]
453    fn canonicalize_refuses_pathologically_nested_arrays() {
454        let mut v = Value::Array(vec![Value::Null]);
455        for _ in 0..MAX_NESTED_DEPTH + 10 {
456            v = Value::Array(vec![v]);
457        }
458        assert_eq!(canonicalize(&v), Err(JcsError::TooDeep(MAX_NESTED_DEPTH)));
459    }
460
461    #[test]
462    fn canonicalize_accepts_depths_up_to_the_cap() {
463        // Build a nested tree at exactly MAX_NESTED_DEPTH to lock
464        // in the boundary behaviour. `MAX_NESTED_DEPTH + 1` is the
465        // cutoff; MAX itself must still succeed.
466        let mut v = Value::Null;
467        for _ in 0..MAX_NESTED_DEPTH {
468            v = Value::Array(vec![v]);
469        }
470        assert!(canonicalize(&v).is_ok());
471    }
472}
av_receipts/jcs.rs

av_receipts/
jcs.rs
