char/plc-mirror

git clone https://git.t4t.associates/char/plc-mirror

Charlotte Somuse new plox opcodec formatc2f2166

main
branchesmainall refs →
20.3 KiB571 linesraw
1use anyhow::{Context, Result, bail, ensure};
2use base64::{Engine, engine::general_purpose::URL_SAFE_NO_PAD};
3use chrono::{DateTime, SecondsFormat, Utc};
4use cid::multibase::{self, Base};
5use serde_json::{Map, Value, json};
6
7const STRING: u8 = 0;
8const INTERN: u8 = 1;
9const KEY: u8 = 2;
10const SIGNATURE: u8 = 3;
11const CID: u8 = 4;
12const ARRAY: u8 = 5;
13const OBJECT: u8 = 6;
14const BSKY_GENESIS: u8 = 7;
15const TRUMP_GENESIS: u8 = 8;
16const LITERAL_CBOR: u8 = 9;
17const HANDLE: u8 = 10;
18const BSKY_CREATE: u8 = 11;
19
20const MAX_PROGRAM: usize = 1024 * 1024;
21const MAX_DEPTH: usize = 64;
22const MAX_STACK: usize = 16_384;
23const MAX_WORK: usize = 16 * 1024 * 1024;
24
25// These are format constants, not a description of Bluesky's current configuration.
26pub(crate) const BSKY_ROTATIONS: [&str; 2] = [
27    "did:key:zQ3shhCGUqDKjStzuDxPkTxN6ujddP4RkEKJJouJGRRkaLGbg",
28    "did:key:zQ3shpKnbdPx3g3CmPf5cRVTPe1HtSwVn5ish3wSnDPQCbLJK",
29];
30const TRUMP_ALIASES: [&str; 7] = [
31    "at://donald.trump.com",
32    "at://jr.donald.trump.com",
33    "at://eric.trump.com",
34    "at://ivanka.trump.com",
35    "at://tiffany.trump.com",
36    "at://barron.trump.com",
37    "at://melania.trump.com",
38];
39
40fn varint(mut n: u64, out: &mut Vec<u8>) {
41    while n >= 128 {
42        out.push(n as u8 | 128);
43        n >>= 7;
44    }
45    out.push(n as u8);
46}
47
48fn literal(tag: u8, bytes: &[u8], out: &mut Vec<u8>) {
49    out.push(tag);
50    varint(bytes.len() as u64, out);
51    out.extend_from_slice(bytes);
52}
53
54struct Reader<'a>(&'a [u8]);
55
56impl<'a> Reader<'a> {
57    fn take(&mut self, n: usize) -> Result<&'a [u8]> {
58        ensure!(n <= self.0.len(), "truncated operand");
59        let (head, tail) = self.0.split_at(n);
60        self.0 = tail;
61        Ok(head)
62    }
63
64    fn varint(&mut self) -> Result<u64> {
65        let mut n = 0;
66        for shift in (0..70).step_by(7) {
67            let b = self.take(1)?[0];
68            ensure!(shift != 63 || b <= 1, "varint overflow");
69            n |= u64::from(b & 127) << shift;
70            if b < 128 {
71                return Ok(n);
72            }
73        }
74        bail!("varint overflow")
75    }
76
77    fn bytes(&mut self) -> Result<&'a [u8]> {
78        let n = usize::try_from(self.varint()?)?;
79        self.take(n)
80    }
81}
82
83fn genesis(endpoint: Value, aliases: Value, rotations: Value, key: Value, sig: Value) -> Value {
84    json!({
85        "type": "plc_operation",
86        "prev": null,
87        "rotationKeys": rotations,
88        "alsoKnownAs": aliases,
89        "services": {"atproto_pds": {"type": "AtprotoPersonalDataServer", "endpoint": endpoint}},
90        "verificationMethods": {"atproto": key},
91        "sig": sig,
92    })
93}
94
95fn legacy_create(service: Value, handle: Value, key: Value, sig: Value) -> Value {
96    json!({
97        "type": "create",
98        "prev": null,
99        "recoveryKey": BSKY_ROTATIONS[0],
100        "service": service,
101        "handle": handle,
102        "signingKey": key,
103        "sig": sig,
104    })
105}
106
107pub fn encode(value: &Value, intern: impl Fn(&str) -> Option<u64>) -> Result<Vec<u8>> {
108    let depth = value_depth(value);
109    ensure!(depth <= MAX_DEPTH, "operation too deep");
110    // JSON text does not round-trip every f64 with serde_json's default parser.
111    let fallback = serde_ipld_dagcbor::to_vec(value)?;
112    ensure!(fallback.len() <= MAX_PROGRAM - 11, "operation too large");
113    let mut out = Vec::new();
114    // Wide/deep values use a single literal rather than exhausting the VM's work budget.
115    if fallback.len() <= MAX_STACK / 2 && fallback.len() * 6 * (depth + 2) <= MAX_WORK {
116        encode_value(value, &intern, &mut out, 0)?;
117    }
118    if out.is_empty() || out.len() > fallback.len() {
119        out.clear();
120        literal(LITERAL_CBOR, &fallback, &mut out);
121    }
122    Ok(out)
123}
124
125fn encode_value(
126    value: &Value,
127    intern: &impl Fn(&str) -> Option<u64>,
128    out: &mut Vec<u8>,
129    depth: usize,
130) -> Result<()> {
131    ensure!(depth <= MAX_DEPTH, "operation too deep");
132    if value.get("type").and_then(Value::as_str) == Some("create") {
133        let service = &value["service"];
134        let handle = &value["handle"];
135        let key = &value["signingKey"];
136        let sig = &value["sig"];
137        if [service, handle, key, sig].iter().all(|v| v.is_string())
138            && value == &legacy_create(service.clone(), handle.clone(), key.clone(), sig.clone())
139        {
140            for operand in [service, handle, key, sig] {
141                encode_value(operand, intern, out, depth + 1)?;
142            }
143            out.push(BSKY_CREATE);
144            return Ok(());
145        }
146    }
147    if value.get("type").and_then(Value::as_str) == Some("plc_operation") {
148        let endpoint = &value["services"]["atproto_pds"]["endpoint"];
149        let aliases = &value["alsoKnownAs"];
150        let rotations = &value["rotationKeys"];
151        let key = &value["verificationMethods"]["atproto"];
152        let sig = &value["sig"];
153        if endpoint.is_string() && key.is_string() && sig.is_string() {
154            if rotations == &json!(BSKY_ROTATIONS)
155                && aliases
156                    .as_array()
157                    .is_some_and(|a| a.len() == 1 && a[0].is_string())
158                && value
159                    == &genesis(
160                        endpoint.clone(),
161                        aliases.clone(),
162                        rotations.clone(),
163                        key.clone(),
164                        sig.clone(),
165                    )
166            {
167                for operand in [endpoint, &aliases[0], key, sig] {
168                    encode_value(operand, intern, out, depth + 1)?;
169                }
170                out.push(BSKY_GENESIS);
171                return Ok(());
172            }
173            if endpoint == "https://pds.trump.com"
174                && aliases == &json!(TRUMP_ALIASES)
175                && rotations
176                    .as_array()
177                    .is_some_and(|a| a.len() == 4 && a.iter().all(Value::is_string))
178                && value
179                    == &genesis(
180                        endpoint.clone(),
181                        aliases.clone(),
182                        rotations.clone(),
183                        key.clone(),
184                        sig.clone(),
185                    )
186            {
187                for operand in rotations.as_array().unwrap().iter().chain([key, sig]) {
188                    encode_value(operand, intern, out, depth + 1)?;
189                }
190                out.push(TRUMP_GENESIS);
191                return Ok(());
192            }
193        }
194    }
195    match value {
196        Value::String(s) => {
197            if let Some(id) = intern(s) {
198                out.push(INTERN);
199                varint(id, out);
200            } else if let Some(handle) = s
201                .strip_prefix("at://")
202                .and_then(|s| s.strip_suffix(".bsky.social"))
203            {
204                literal(HANDLE, handle.as_bytes(), out);
205            } else if let Some(key) = s.strip_prefix("did:key:z")
206                && key.len() <= 128
207                && let Ok(bytes) = Base::Base58Btc.decode(key)
208                && Base::Base58Btc.encode(&bytes) == key
209            {
210                literal(KEY, &bytes, out);
211            } else if s.len() == 86
212                && let Ok(bytes) = URL_SAFE_NO_PAD.decode(s)
213                && bytes.len() == 64
214                && URL_SAFE_NO_PAD.encode(&bytes) == *s
215            {
216                out.push(SIGNATURE);
217                out.extend_from_slice(&bytes);
218            } else if let Ok(cid) = s.parse::<cid::Cid>()
219                && cid.to_string() == *s
220            {
221                literal(CID, &cid.to_bytes(), out);
222            } else {
223                literal(STRING, s.as_bytes(), out);
224            }
225        }
226        Value::Array(values) => {
227            for value in values {
228                encode_value(value, intern, out, depth + 1)?;
229            }
230            out.push(ARRAY);
231            varint(values.len() as u64, out);
232        }
233        Value::Object(values) => {
234            for (key, value) in values {
235                encode_value(&Value::String(key.clone()), intern, out, depth + 1)?;
236                encode_value(value, intern, out, depth + 1)?;
237            }
238            out.push(OBJECT);
239            varint(values.len() as u64, out);
240        }
241        _ => literal(LITERAL_CBOR, &serde_ipld_dagcbor::to_vec(value)?, out),
242    }
243    Ok(())
244}
245
246pub fn decode<'a>(program: &[u8], intern: impl Fn(usize) -> Option<&'a str>) -> Result<Value> {
247    ensure!(program.len() <= MAX_PROGRAM, "program too large");
248    let mut input = Reader(program);
249    let mut stack: Vec<(Value, usize)> = Vec::new();
250    let mut work = 0usize;
251    while !input.0.is_empty() {
252        let opcode = input.take(1)?[0];
253        let (value, depth) = match opcode {
254            STRING | HANDLE => {
255                let s = std::str::from_utf8(input.bytes()?)?;
256                (
257                    Value::String(if opcode == HANDLE {
258                        format!("at://{s}.bsky.social")
259                    } else {
260                        s.to_owned()
261                    }),
262                    0,
263                )
264            }
265            INTERN => {
266                let id = usize::try_from(input.varint()?)?;
267                let s = intern(id).context("missing interned string")?;
268                ensure!(s.len() <= MAX_PROGRAM, "interned string too large");
269                (Value::String(s.to_owned()), 0)
270            }
271            KEY => {
272                let bytes = input.bytes()?;
273                ensure!(bytes.len() <= 128, "key operand too large");
274                (
275                    Value::String(format!(
276                        "did:key:{}",
277                        multibase::encode(Base::Base58Btc, bytes)
278                    )),
279                    0,
280                )
281            }
282            SIGNATURE => (Value::String(URL_SAFE_NO_PAD.encode(input.take(64)?)), 0),
283            CID => (
284                Value::String(cid::Cid::try_from(input.bytes()?)?.to_string()),
285                0,
286            ),
287            LITERAL_CBOR => {
288                let value: Value = serde_ipld_dagcbor::from_slice(input.bytes()?)?;
289                let depth = value_depth(&value);
290                (value, depth)
291            }
292            ARRAY | OBJECT | BSKY_GENESIS | TRUMP_GENESIS | BSKY_CREATE => {
293                let n = match opcode {
294                    ARRAY => usize::try_from(input.varint()?)?,
295                    OBJECT => usize::try_from(input.varint()?)?
296                        .checked_mul(2)
297                        .context("object size overflow")?,
298                    BSKY_GENESIS | BSKY_CREATE => 4,
299                    _ => 6,
300                };
301                ensure!(n <= stack.len(), "stack underflow");
302                let start = stack.len() - n;
303                let depth = stack[start..].iter().map(|(_, d)| d + 1).max().unwrap_or(1);
304                let mut values = stack.drain(start..).map(|(v, _)| v);
305                let value = match opcode {
306                    ARRAY => Value::Array(values.collect()),
307                    OBJECT => {
308                        let mut object = Map::new();
309                        while let Some(key) = values.next() {
310                            let Value::String(key) = key else {
311                                bail!("object key is not a string")
312                            };
313                            ensure!(
314                                object.insert(key, values.next().unwrap()).is_none(),
315                                "duplicate object key"
316                            );
317                        }
318                        Value::Object(object)
319                    }
320                    BSKY_GENESIS | BSKY_CREATE => {
321                        let args: Vec<_> = values.collect();
322                        ensure!(
323                            args.iter().all(Value::is_string),
324                            "invalid genesis operands"
325                        );
326                        let [endpoint, name, key, sig]: [Value; 4] = args.try_into().unwrap();
327                        if opcode == BSKY_CREATE {
328                            legacy_create(endpoint, name, key, sig)
329                        } else {
330                            genesis(endpoint, json!([name]), json!(BSKY_ROTATIONS), key, sig)
331                        }
332                    }
333                    _ => {
334                        let args: Vec<_> = values.collect();
335                        ensure!(
336                            args.iter().all(Value::is_string),
337                            "invalid genesis operands"
338                        );
339                        let [a, b, c, d, key, sig]: [Value; 6] = args.try_into().unwrap();
340                        genesis(
341                            json!("https://pds.trump.com"),
342                            json!(TRUMP_ALIASES),
343                            json!([a, b, c, d]),
344                            key,
345                            sig,
346                        )
347                    }
348                };
349                (
350                    value,
351                    if opcode == BSKY_GENESIS || opcode == TRUMP_GENESIS {
352                        depth + 2
353                    } else {
354                        depth
355                    },
356                )
357            }
358            _ => bail!("unknown opcode {opcode}"),
359        };
360        ensure!(depth <= MAX_DEPTH, "operation too deep");
361        // Bound cumulative construction work, including dictionary and template expansion.
362        work = work
363            .checked_add(serde_json::to_vec(&value)?.len())
364            .context("expansion overflow")?;
365        ensure!(work <= MAX_WORK, "program expansion limit exceeded");
366        ensure!(stack.len() < MAX_STACK, "stack limit exceeded");
367        stack.push((value, depth));
368    }
369    ensure!(stack.len() == 1, "program must produce exactly one value");
370    Ok(stack.pop().unwrap().0)
371}
372
373fn value_depth(value: &Value) -> usize {
374    match value {
375        Value::Array(a) => 1 + a.iter().map(value_depth).max().unwrap_or(0),
376        Value::Object(o) => 1 + o.values().map(value_depth).max().unwrap_or(0),
377        _ => 0,
378    }
379}
380
381pub fn encode_did(did: &str) -> Vec<u8> {
382    if let Some(suffix) = did.strip_prefix("did:plc:")
383        && let Ok(bytes) = Base::Base32Lower.decode(suffix)
384        && bytes.len() == 15
385        && Base::Base32Lower.encode(&bytes) == suffix
386    {
387        let mut out = vec![1];
388        out.extend(bytes);
389        return out;
390    }
391    let mut out = vec![0];
392    out.extend_from_slice(did.as_bytes());
393    out
394}
395
396pub fn decode_did(bytes: &[u8]) -> Result<String> {
397    match bytes.split_first() {
398        Some((0, text)) => Ok(std::str::from_utf8(text)?.to_owned()),
399        Some((1, bytes)) if bytes.len() == 15 => {
400            Ok(format!("did:plc:{}", Base::Base32Lower.encode(bytes)))
401        }
402        _ => bail!("invalid DID encoding"),
403    }
404}
405
406pub fn encode_timestamp(text: &str) -> Vec<u8> {
407    if let Ok(time) = DateTime::parse_from_rfc3339(text) {
408        let ms = time.timestamp_millis();
409        if let Some(time) = DateTime::<Utc>::from_timestamp_millis(ms)
410            && time.to_rfc3339_opts(SecondsFormat::Millis, true) == text
411        {
412            let mut out = vec![1];
413            varint(((ms as u64) << 1) ^ ((ms >> 63) as u64), &mut out);
414            return out;
415        }
416    }
417    let mut out = vec![0];
418    out.extend_from_slice(text.as_bytes());
419    out
420}
421
422pub fn decode_timestamp(bytes: &[u8]) -> Result<String> {
423    match bytes.split_first() {
424        Some((0, text)) => Ok(std::str::from_utf8(text)?.to_owned()),
425        Some((1, bytes)) => {
426            let mut input = Reader(bytes);
427            let n = input.varint()?;
428            ensure!(input.0.is_empty(), "trailing timestamp bytes");
429            let ms = (n >> 1) as i64 ^ -((n & 1) as i64);
430            let time =
431                DateTime::<Utc>::from_timestamp_millis(ms).context("timestamp out of range")?;
432            Ok(time.to_rfc3339_opts(SecondsFormat::Millis, true))
433        }
434        _ => bail!("invalid timestamp encoding"),
435    }
436}
437
438#[cfg(test)]
439mod tests {
440    use super::*;
441
442    #[test]
443    fn legacy_bluesky_creates_are_compact_and_lossless() -> Result<()> {
444        let original = json!({
445            "handle": "paul.bsky.social",
446            "prev": null,
447            "recoveryKey": "did:key:zQ3shhCGUqDKjStzuDxPkTxN6ujddP4RkEKJJouJGRRkaLGbg",
448            "service": "https://bsky.social",
449            "sig": "DyaPWDItkJnVkN1izINSW-fdjUzP9BkIKlD7SnzD5axfK_870ZZ-1EYcrQLQtP9VkWcp2cdbyIHprjPfeUs8WQ",
450            "signingKey": "did:key:zQ3shP5TBe1sQfSttXty15FAEHV1DZgcxRZNxvEWnPfLFwLxJ",
451            "type": "create",
452        });
453        let strings = ["https://bsky.social"];
454        let program = encode(&original, |s| {
455            strings.iter().position(|v| *v == s).map(|n| n as u64)
456        })?;
457        assert!(program.len() <= 130, "{} bytes", program.len());
458        println!("legacy create: {} bytes", program.len());
459        assert_eq!(decode(&program, |id| strings.get(id).copied())?, original);
460
461        let mut variants = vec![original.clone()];
462        for field in original.as_object().unwrap().keys() {
463            let mut absent = original.clone();
464            absent.as_object_mut().unwrap().remove(field);
465            variants.push(absent);
466            let mut null = original.clone();
467            null[field] = Value::Null;
468            variants.push(null);
469        }
470        let mut custom = original.clone();
471        custom["recoveryKey"] = original["signingKey"].clone();
472        variants.push(custom);
473        let mut extra = original;
474        extra["future"] = json!({"nested": [false, null, 7]});
475        variants.push(extra);
476        for value in variants {
477            let program = encode(&value, |_| None)?;
478            let decoded = decode(&program, |_| None)?;
479            assert_eq!(
480                serde_ipld_dagcbor::to_vec(&decoded)?,
481                serde_ipld_dagcbor::to_vec(&value)?
482            );
483        }
484        Ok(())
485    }
486
487    #[test]
488    fn values_and_canonical_bytes_survive() -> Result<()> {
489        let values = [
490            json!({"type":"create", "prev":null, "extra":[true, false, -7, 1.5, {}, []]}),
491            json!({"type":"plc_tombstone", "prev":"bafyreih553tggj3y22ewyb5mlhrcszkjjles7fr57xixixf3sk52jeqoyy", "sig":"literal"}),
492            json!({"alsoKnownAs":["at://alice.bsky.social", "at://☃.example"], "unknown":{"n":18446744073709551615u64}}),
493            json!(-0.0),
494        ];
495        let strings = ["at://☃.example".to_owned()];
496        for value in values {
497            let program = encode(&value, |s| {
498                strings.iter().position(|v| v == s).map(|n| n as u64)
499            })?;
500            let decoded = decode(&program, |id| strings.get(id).map(String::as_str))?;
501            assert_eq!(decoded, value);
502            assert_eq!(
503                serde_ipld_dagcbor::to_vec(&decoded)?,
504                serde_ipld_dagcbor::to_vec(&value)?
505            );
506        }
507        Ok(())
508    }
509
510    #[test]
511    fn metadata_is_exact() -> Result<()> {
512        for did in [
513            "did:plc:ragtjsm2j2vknwkz3zp4oxrd",
514            "did:web:example.com",
515            "did:plc:RAGT",
516            "",
517        ] {
518            assert_eq!(decode_did(&encode_did(did))?, did);
519        }
520        for time in [
521            "2026-09-12T12:16:35.070Z",
522            "1960-01-01T00:00:00.000Z",
523            "2026-09-12T12:16:35Z",
524            "2026-09-12T12:16:35.070123Z",
525            "2026-09-12T13:16:35.070+01:00",
526            "unknown",
527        ] {
528            assert_eq!(decode_timestamp(&encode_timestamp(time))?, time);
529        }
530        Ok(())
531    }
532
533    #[test]
534    fn malformed_programs_fail() {
535        for bytes in [
536            vec![],
537            vec![255],
538            vec![INTERN, 0],
539            vec![STRING, 3, b'a'],
540            vec![ARRAY, 1],
541            vec![OBJECT, 1],
542            vec![BSKY_GENESIS],
543            vec![BSKY_CREATE],
544            vec![
545                LITERAL_CBOR,
546                1,
547                0xf6,
548                STRING,
549                0,
550                STRING,
551                0,
552                STRING,
553                0,
554                BSKY_CREATE,
555            ],
556            vec![SIGNATURE, 0],
557            vec![CID, 1, 0],
558            vec![STRING, 1, 255],
559            vec![INTERN, 255, 255, 255, 255, 255, 255, 255, 255, 255, 2],
560            vec![STRING, 0, STRING, 0],
561            vec![STRING, 0, STRING, 0, STRING, 0, STRING, 0, OBJECT, 2],
562        ] {
563            assert!(decode(&bytes, |_| None).is_err(), "{bytes:?}");
564        }
565        let mut nested = vec![STRING, 0];
566        for _ in 0..100 {
567            nested.extend([ARRAY, 1]);
568        }
569        assert!(decode(&nested, |_| None).is_err());
570    }
571}