bsv_tracker/
compact.rs

1//! The compact byte form of one [`State`](crate::State) (bsv-stack-lean #92).
2//!
3//! Version 1, every field in order:
4//!
5//! | field | encoding |
6//! | --- | --- |
7//! | version | one byte, `1` |
8//! | txid | an id |
9//! | word | a tag byte (`0` unknown, `1` built, `2` announced, `3` seen, `4` mined, `5` stale, `6` rejected and its reason, `7` conflicted and its ids, `8` abandoned) |
10//! | evidence | `0`, or `1` and the checked proof's txid (an id), path, header hash and root (ids), root (an id) and depth (a varint) |
11//! | suspect | `0` or `1` |
12//! | hints | a varint count, then each hint, the newest at the front |
13//! | last hint time | `0`, or `1` and a varint |
14//! | re-ask | `0`, or `1` and a tag byte (`0` reorg, `1` fork, `2` hint, `3` proof failed, `4` recheck, `5` age, `6` spend) and its payload |
15//!
16//! A varint is unsigned LEB128 in its shortest form. A string is a varint
17//! length and its UTF-8 bytes. An id is `0` and 32 raw bytes when the text is
18//! 64 lowercase hex digits, else `1` and a string. A hint is its source (a
19//! string), its status (a tag byte in [`HintStatus`] declaration order and its
20//! payload), its observed time (a varint) and its verdict (`0`, or `1` and the
21//! status, the optional height, the optional reason and the competitor ids).
22//! A path is its block height, a varint count of levels, and per level a
23//! varint count of leaves, each an offset (a varint), a flag byte (`1`
24//! duplicate, `2` txid, `4` a hash follows) and the hash (an id).
25//!
26//! The decoder accepts only the bytes the encoder writes: a non-canonical
27//! varint, an id written as text that has the raw form, a flag outside its set
28//! or trailing bytes are each refused.
29
30use crate::{
31    CheckError, CheckedProof, Header, Height, Hint, HintStatus, Proof, Reask, Timestamp, TxId,
32    Verdict, Word,
33};
34use bsv_rs::transaction::{MerklePath, MerklePathLeaf};
35use std::fmt;
36
37/// The version byte [`State::to_compact`](crate::State::to_compact) writes.
38pub const COMPACT_VERSION: u8 = 1;
39
40/// Bytes [`State::from_compact`](crate::State::from_compact) refuses. A
41/// refusal restores nothing; the host re-tracks the transaction.
42#[derive(Clone, Debug, PartialEq, Eq)]
43pub enum CompactError {
44    /// The version byte is not one this crate reads.
45    UnknownVersion(u8),
46    /// The bytes end inside a field.
47    Truncated,
48    /// Bytes remain after the last field.
49    TrailingBytes,
50    /// A tag, flag, varint, id or string the encoder never writes.
51    Malformed(&'static str),
52    /// The stored proof record does not hold together: its path does not
53    /// reduce, it names another transaction, or its root differs from its
54    /// header's. Nothing here consults the host's headers.
55    Evidence(CheckError),
56}
57impl fmt::Display for CompactError {
58    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
59        write!(f, "{self:?}")
60    }
61}
62impl std::error::Error for CompactError {}
63
64/// The fields of a state, as the codec reads and writes them.
65pub(crate) struct Parts {
66    pub txid: TxId,
67    /// None is the mined word, backed by the evidence field.
68    pub word: Option<Word>,
69    pub evidence: Option<CheckedProof>,
70    pub suspect: bool,
71    pub hints: Vec<Hint>,
72    pub last_hint_at: Option<Timestamp>,
73    pub reask: Option<Reask>,
74}
75
76pub(crate) struct Fields<'a> {
77    pub txid: &'a str,
78    pub word: &'a Word,
79    pub evidence: Option<&'a CheckedProof>,
80    pub suspect: bool,
81    pub hints: &'a [Hint],
82    pub last_hint_at: Option<Timestamp>,
83    pub reask: Option<&'a Reask>,
84}
85
86pub(crate) fn encode(fields: &Fields<'_>) -> Vec<u8> {
87    let mut w = Writer(vec![COMPACT_VERSION]);
88    w.id(fields.txid);
89    w.word(fields.word);
90    match fields.evidence {
91        None => w.byte(0),
92        Some(checked) => {
93            w.byte(1);
94            w.id(checked.proof().txid());
95            w.path(checked.proof().path());
96            w.id(&checked.header().hash);
97            w.id(&checked.header().merkle_root);
98            w.id(checked.root());
99            w.varint(checked.depth());
100        }
101    }
102    w.flag(fields.suspect);
103    w.len(fields.hints.len());
104    for hint in fields.hints {
105        w.hint(hint);
106    }
107    w.option(fields.last_hint_at, Writer::varint);
108    match fields.reask {
109        None => w.byte(0),
110        Some(reask) => {
111            w.byte(1);
112            w.reask(reask);
113        }
114    }
115    w.0
116}
117
118pub(crate) fn decode(bytes: &[u8]) -> Result<Parts, CompactError> {
119    let mut r = Reader(bytes);
120    let version = r.byte()?;
121    if version != COMPACT_VERSION {
122        return Err(CompactError::UnknownVersion(version));
123    }
124    let txid = r.id()?;
125    if txid != txid.to_ascii_lowercase() {
126        return Err(CompactError::Malformed("txid not lowercase"));
127    }
128    let word = r.word()?;
129    let evidence = if r.flag()? {
130        let proof_txid = r.id()?;
131        let path = r.path()?;
132        let header = Header {
133            hash: r.id()?,
134            merkle_root: r.id()?,
135        };
136        let root = r.id()?;
137        let depth = r.varint()?;
138        let proof = Proof::new(proof_txid, path).map_err(CompactError::Evidence)?;
139        if proof.txid() != txid {
140            return Err(CompactError::Evidence(CheckError::TxidMismatch));
141        }
142        Some(CheckedProof::restored(proof, header, root, depth).map_err(CompactError::Evidence)?)
143    } else {
144        None
145    };
146    let suspect = r.flag()?;
147    let count = r.count()?;
148    let mut hints = Vec::with_capacity(count);
149    for _ in 0..count {
150        hints.push(r.hint()?);
151    }
152    let last_hint_at = r.option(Reader::varint)?;
153    let reask = r.option(Reader::reask)?;
154    if !r.0.is_empty() {
155        return Err(CompactError::TrailingBytes);
156    }
157    Ok(Parts {
158        txid,
159        word,
160        evidence,
161        suspect,
162        hints,
163        last_hint_at,
164        reask,
165    })
166}
167
168struct Writer(Vec<u8>);
169impl Writer {
170    fn byte(&mut self, b: u8) {
171        self.0.push(b);
172    }
173    fn flag(&mut self, b: bool) {
174        self.byte(u8::from(b));
175    }
176    fn varint(&mut self, mut n: u64) {
177        loop {
178            // The low seven bits; the mask makes the truncation exact.
179            #[allow(clippy::cast_possible_truncation)]
180            let low = (n & 0x7f) as u8;
181            n >>= 7;
182            if n == 0 {
183                self.byte(low);
184                return;
185            }
186            self.byte(low | 0x80);
187        }
188    }
189    fn len(&mut self, n: usize) {
190        self.varint(n as u64);
191    }
192    fn height(&mut self, h: Height) {
193        self.varint(u64::from(h));
194    }
195    fn string(&mut self, s: &str) {
196        self.len(s.len());
197        self.0.extend_from_slice(s.as_bytes());
198    }
199    fn id(&mut self, s: &str) {
200        if let Some(raw) = raw_id(s) {
201            self.byte(0);
202            self.0.extend_from_slice(&raw);
203        } else {
204            self.byte(1);
205            self.string(s);
206        }
207    }
208    fn ids(&mut self, ids: &[TxId]) {
209        self.len(ids.len());
210        for id in ids {
211            self.id(id);
212        }
213    }
214    fn option<T>(&mut self, value: Option<T>, put: impl FnOnce(&mut Self, T)) {
215        match value {
216            None => self.byte(0),
217            Some(v) => {
218                self.byte(1);
219                put(self, v);
220            }
221        }
222    }
223    fn word(&mut self, word: &Word) {
224        match word {
225            Word::Unknown => self.byte(0),
226            Word::Built => self.byte(1),
227            Word::Announced => self.byte(2),
228            Word::Seen => self.byte(3),
229            // The checked proof is the evidence field; a mined word shares it.
230            Word::Mined(_) => self.byte(4),
231            Word::Stale => self.byte(5),
232            Word::Rejected { reason } => {
233                self.byte(6);
234                self.string(reason);
235            }
236            Word::Conflicted { competitors } => {
237                self.byte(7);
238                self.ids(competitors);
239            }
240            Word::Abandoned => self.byte(8),
241        }
242    }
243    fn path(&mut self, path: &MerklePath) {
244        self.height(path.block_height);
245        self.len(path.path.len());
246        for level in &path.path {
247            self.len(level.len());
248            for leaf in level {
249                self.varint(leaf.offset);
250                let flags = u8::from(leaf.duplicate)
251                    | (u8::from(leaf.txid) << 1)
252                    | (u8::from(leaf.hash.is_some()) << 2);
253                self.byte(flags);
254                if let Some(hash) = &leaf.hash {
255                    self.id(hash);
256                }
257            }
258        }
259    }
260    fn status(&mut self, status: &HintStatus) {
261        match status {
262            HintStatus::Accepted => self.byte(0),
263            HintStatus::Seen => self.byte(1),
264            HintStatus::Mined { height } => {
265                self.byte(2);
266                self.height(*height);
267            }
268            HintStatus::StaleBlock => self.byte(3),
269            HintStatus::Rejected { reason } => {
270                self.byte(4);
271                self.string(reason);
272            }
273            HintStatus::DoubleSpend { competitors } => {
274                self.byte(5);
275                self.ids(competitors);
276            }
277            HintStatus::OrphanMempool => self.byte(6),
278            HintStatus::Unknown => self.byte(7),
279            HintStatus::MempoolPresent { source } => {
280                self.byte(8);
281                self.string(source);
282            }
283        }
284    }
285    fn hint(&mut self, hint: &Hint) {
286        self.string(&hint.source);
287        self.status(&hint.status);
288        self.varint(hint.observed);
289        self.option(hint.verdict.as_ref(), |w, v| {
290            w.string(&v.status);
291            w.option(v.height, Self::height);
292            w.option(v.reason.as_deref(), Self::string);
293            w.ids(&v.competitors);
294        });
295    }
296    fn reask(&mut self, reask: &Reask) {
297        match reask {
298            Reask::Reorg { fork_height } => {
299                self.byte(0);
300                self.height(*fork_height);
301            }
302            Reask::Fork { height } => {
303                self.byte(1);
304                self.height(*height);
305            }
306            Reask::Hint(hint) => {
307                self.byte(2);
308                self.hint(hint);
309            }
310            Reask::ProofFailed { height } => {
311                self.byte(3);
312                self.height(*height);
313            }
314            Reask::Recheck => self.byte(4),
315            Reask::Age => self.byte(5),
316            Reask::Spend => self.byte(6),
317        }
318    }
319}
320
321struct Reader<'a>(&'a [u8]);
322impl Reader<'_> {
323    fn take(&mut self, n: usize) -> Result<&[u8], CompactError> {
324        if n > self.0.len() {
325            return Err(CompactError::Truncated);
326        }
327        let (head, rest) = self.0.split_at(n);
328        self.0 = rest;
329        Ok(head)
330    }
331    fn byte(&mut self) -> Result<u8, CompactError> {
332        let (&b, rest) = self.0.split_first().ok_or(CompactError::Truncated)?;
333        self.0 = rest;
334        Ok(b)
335    }
336    fn flag(&mut self) -> Result<bool, CompactError> {
337        match self.byte()? {
338            0 => Ok(false),
339            1 => Ok(true),
340            _ => Err(CompactError::Malformed("flag")),
341        }
342    }
343    fn varint(&mut self) -> Result<u64, CompactError> {
344        let mut n = 0u64;
345        for shift in (0..64).step_by(7) {
346            let b = self.byte()?;
347            let low = u64::from(b & 0x7f);
348            if shift == 63 && low > 1 {
349                return Err(CompactError::Malformed("varint overflow"));
350            }
351            n |= low << shift;
352            if b & 0x80 == 0 {
353                if b == 0 && shift > 0 {
354                    return Err(CompactError::Malformed("varint not shortest"));
355                }
356                return Ok(n);
357            }
358        }
359        Err(CompactError::Malformed("varint overflow"))
360    }
361    fn height(&mut self) -> Result<Height, CompactError> {
362        Height::try_from(self.varint()?).map_err(|_| CompactError::Malformed("height"))
363    }
364    /// A count of items, each at least one byte, so a count beyond the
365    /// remaining bytes is refused before anything is allocated.
366    fn count(&mut self) -> Result<usize, CompactError> {
367        let n = usize::try_from(self.varint()?).map_err(|_| CompactError::Truncated)?;
368        if n > self.0.len() {
369            return Err(CompactError::Truncated);
370        }
371        Ok(n)
372    }
373    fn string(&mut self) -> Result<String, CompactError> {
374        let n = self.count()?;
375        let bytes = self.take(n)?;
376        String::from_utf8(bytes.to_vec()).map_err(|_| CompactError::Malformed("utf-8"))
377    }
378    fn id(&mut self) -> Result<String, CompactError> {
379        match self.byte()? {
380            0 => {
381                const HEX: &[u8; 16] = b"0123456789abcdef";
382                let mut s = String::with_capacity(64);
383                for b in self.take(32)? {
384                    s.push(char::from(HEX[usize::from(b >> 4)]));
385                    s.push(char::from(HEX[usize::from(b & 0xf)]));
386                }
387                Ok(s)
388            }
389            1 => {
390                let s = self.string()?;
391                if raw_id(&s).is_some() {
392                    return Err(CompactError::Malformed("id not in its raw form"));
393                }
394                Ok(s)
395            }
396            _ => Err(CompactError::Malformed("id tag")),
397        }
398    }
399    fn ids(&mut self) -> Result<Vec<TxId>, CompactError> {
400        let n = self.count()?;
401        (0..n).map(|_| self.id()).collect()
402    }
403    fn option<T>(
404        &mut self,
405        get: impl FnOnce(&mut Self) -> Result<T, CompactError>,
406    ) -> Result<Option<T>, CompactError> {
407        if self.flag()? {
408            get(self).map(Some)
409        } else {
410            Ok(None)
411        }
412    }
413    /// None is the mined word; the state attaches the evidence field's proof.
414    fn word(&mut self) -> Result<Option<Word>, CompactError> {
415        Ok(Some(match self.byte()? {
416            0 => Word::Unknown,
417            1 => Word::Built,
418            2 => Word::Announced,
419            3 => Word::Seen,
420            4 => return Ok(None),
421            5 => Word::Stale,
422            6 => Word::Rejected {
423                reason: self.string()?,
424            },
425            7 => Word::Conflicted {
426                competitors: self.ids()?,
427            },
428            8 => Word::Abandoned,
429            _ => return Err(CompactError::Malformed("word tag")),
430        }))
431    }
432    fn path(&mut self) -> Result<MerklePath, CompactError> {
433        let block_height = self.height()?;
434        let levels = self.count()?;
435        let mut path = Vec::with_capacity(levels);
436        for _ in 0..levels {
437            let n = self.count()?;
438            let mut level = Vec::with_capacity(n);
439            for _ in 0..n {
440                let offset = self.varint()?;
441                let flags = self.byte()?;
442                if flags & !0b111 != 0 {
443                    return Err(CompactError::Malformed("leaf flags"));
444                }
445                let hash = if flags & 4 == 0 {
446                    None
447                } else {
448                    Some(self.id()?)
449                };
450                level.push(MerklePathLeaf {
451                    offset,
452                    hash,
453                    txid: flags & 2 != 0,
454                    duplicate: flags & 1 != 0,
455                });
456            }
457            path.push(level);
458        }
459        Ok(MerklePath { block_height, path })
460    }
461    fn status(&mut self) -> Result<HintStatus, CompactError> {
462        Ok(match self.byte()? {
463            0 => HintStatus::Accepted,
464            1 => HintStatus::Seen,
465            2 => HintStatus::Mined {
466                height: self.height()?,
467            },
468            3 => HintStatus::StaleBlock,
469            4 => HintStatus::Rejected {
470                reason: self.string()?,
471            },
472            5 => HintStatus::DoubleSpend {
473                competitors: self.ids()?,
474            },
475            6 => HintStatus::OrphanMempool,
476            7 => HintStatus::Unknown,
477            8 => HintStatus::MempoolPresent {
478                source: self.string()?,
479            },
480            _ => return Err(CompactError::Malformed("hint status tag")),
481        })
482    }
483    fn hint(&mut self) -> Result<Hint, CompactError> {
484        let source = self.string()?;
485        let status = self.status()?;
486        let observed = self.varint()?;
487        let verdict = self.option(|r| {
488            Ok(Verdict {
489                status: r.string()?,
490                height: r.option(Self::height)?,
491                reason: r.option(Self::string)?,
492                competitors: r.ids()?,
493            })
494        })?;
495        Ok(Hint {
496            source,
497            status,
498            observed,
499            verdict,
500        })
501    }
502    fn reask(&mut self) -> Result<Reask, CompactError> {
503        Ok(match self.byte()? {
504            0 => Reask::Reorg {
505                fork_height: self.height()?,
506            },
507            1 => Reask::Fork {
508                height: self.height()?,
509            },
510            2 => Reask::Hint(self.hint()?),
511            3 => Reask::ProofFailed {
512                height: self.height()?,
513            },
514            4 => Reask::Recheck,
515            5 => Reask::Age,
516            6 => Reask::Spend,
517            _ => return Err(CompactError::Malformed("re-ask tag")),
518        })
519    }
520}
521
522/// The 32 bytes of 64 lowercase hex digits, in text order.
523fn raw_id(s: &str) -> Option<[u8; 32]> {
524    fn nibble(c: u8) -> Option<u8> {
525        match c {
526            b'0'..=b'9' => Some(c - b'0'),
527            b'a'..=b'f' => Some(c - b'a' + 10),
528            _ => None,
529        }
530    }
531    let bytes = s.as_bytes();
532    if bytes.len() != 64 {
533        return None;
534    }
535    let mut raw = [0u8; 32];
536    for (out, pair) in raw.iter_mut().zip(bytes.as_chunks::<2>().0) {
537        *out = (nibble(pair[0])? << 4) | nibble(pair[1])?;
538    }
539    Some(raw)
540}
bsv_tracker/compact.rs

bsv_tracker/
compact.rs
