hotshot_types/data/
ns_table.rs

1// Copyright (c) 2021-2024 Espresso Systems (espressosys.com)
2// This file is part of the HotShot repository.
3
4// You should have received a copy of the MIT License
5// along with the HotShot repository. If not, see <https://mit-license.org/>.
6
7//! This module provides helpers for namespace table.
8
9use std::ops::Range;
10
11/// Byte lengths for the different items that could appear in a namespace table.
12const NUM_NSS_BYTE_LEN: usize = 4;
13const NS_OFFSET_BYTE_LEN: usize = 4;
14const NS_ID_BYTE_LEN: usize = 4;
15
16/// Helper function for AvidM scheme to parse a namespace table.
17/// If the namespace table is invalid, it returns a default single entry namespace table.
18/// For details, please refer to `block/full_payload/ns_table.rs` in the `sequencer` crate.
19#[allow(clippy::single_range_in_vec_init)]
20pub fn parse_ns_table(payload_byte_len: usize, bytes: &[u8]) -> Vec<Range<usize>> {
21    let Some(offsets) = ns_table_offsets(bytes) else {
22        return single_ns_table(payload_byte_len);
23    };
24    // Early breaks for empty payload and namespace table
25    if offsets.is_empty() && payload_byte_len == 0 {
26        return vec![(0..0)];
27    }
28    if offsets.last() != Some(&payload_byte_len) {
29        return single_ns_table(payload_byte_len);
30    }
31    let mut start = 0;
32    offsets
33        .into_iter()
34        .map(|end| {
35            let range = start..end;
36            start = end;
37            range
38        })
39        .collect()
40}
41
42/// The payload length `bytes` claims to be the namespace table of: its final
43/// offset, or zero for a table with no entries. `None` if `bytes` is not a
44/// namespace table at all.
45///
46/// [`parse_ns_table`] substitutes one namespace spanning the payload both for
47/// bytes that are no table and for a table sized for another payload. A
48/// verifier that learned the payload's length from the payload itself must
49/// tell the two apart: for a one-namespace payload the substitute is the
50/// honest table, so a table claiming a different length would otherwise pass.
51pub fn ns_table_payload_byte_len(bytes: &[u8]) -> Option<usize> {
52    ns_table_offsets(bytes).map(|offsets| offsets.last().copied().unwrap_or(0))
53}
54
55/// The namespace end offsets `bytes` encodes, in order. `None` if `bytes` is
56/// not a namespace table: too short, an entry count that disagrees with its
57/// length, or offsets that decrease.
58fn ns_table_offsets(bytes: &[u8]) -> Option<Vec<usize>> {
59    const ENTRY_BYTE_LEN: usize = NS_ID_BYTE_LEN + NS_OFFSET_BYTE_LEN;
60    if bytes.len() < NUM_NSS_BYTE_LEN
61        || !(bytes.len() - NUM_NSS_BYTE_LEN).is_multiple_of(ENTRY_BYTE_LEN)
62    {
63        return None;
64    }
65    let num_entries = u32::from_le_bytes(bytes[..NUM_NSS_BYTE_LEN].try_into().unwrap()) as usize;
66    if num_entries != (bytes.len() - NUM_NSS_BYTE_LEN) / ENTRY_BYTE_LEN {
67        return None;
68    }
69    let mut offsets = Vec::with_capacity(num_entries);
70    let mut last = 0;
71    for i in 0..num_entries {
72        let offset = NUM_NSS_BYTE_LEN + i * ENTRY_BYTE_LEN + NS_ID_BYTE_LEN;
73        let end = u32::from_le_bytes(
74            bytes[offset..offset + NS_OFFSET_BYTE_LEN]
75                .try_into()
76                .unwrap(),
77        ) as usize;
78        if end < last {
79            return None;
80        }
81        offsets.push(end);
82        last = end;
83    }
84    Some(offsets)
85}
86
87#[allow(clippy::single_range_in_vec_init)]
88fn single_ns_table(payload_byte_len: usize) -> Vec<Range<usize>> {
89    tracing::debug!(
90        "Failed to parse the metadata as namespace table. Use a single namespace table instead."
91    );
92    vec![(0..payload_byte_len)]
93}
94
95#[cfg(test)]
96mod tests {
97    use super::*;
98
99    /// Encode a namespace table whose namespaces end at `offsets`.
100    fn ns_table(offsets: &[u32]) -> Vec<u8> {
101        let mut bytes = (offsets.len() as u32).to_le_bytes().to_vec();
102        for (id, offset) in offsets.iter().enumerate() {
103            bytes.extend_from_slice(&(id as u32).to_le_bytes());
104            bytes.extend_from_slice(&offset.to_le_bytes());
105        }
106        bytes
107    }
108
109    /// A table whose entry count disagrees with its length.
110    fn miscounted() -> Vec<u8> {
111        let mut bytes = ns_table(&[30, 100]);
112        bytes[..NUM_NSS_BYTE_LEN].copy_from_slice(&1u32.to_le_bytes());
113        bytes
114    }
115
116    #[test]
117    fn parse_ns_table_slices_a_table_sized_for_the_payload() {
118        assert_eq!(
119            parse_ns_table(100, &ns_table(&[30, 100])),
120            vec![0..30, 30..100]
121        );
122        assert_eq!(
123            parse_ns_table(100, &ns_table(&[0, 100])),
124            vec![0..0, 0..100]
125        );
126        assert_eq!(parse_ns_table(100, &ns_table(&[100])), vec![0..100]);
127        assert_eq!(parse_ns_table(0, &ns_table(&[])), vec![0..0]);
128    }
129
130    #[test]
131    fn parse_ns_table_falls_back_to_one_namespace() {
132        // Not a table.
133        assert_eq!(parse_ns_table(100, &[]), vec![0..100]);
134        assert_eq!(
135            parse_ns_table(100, &ns_table(&[30, 100])[..9]),
136            vec![0..100]
137        );
138        assert_eq!(parse_ns_table(100, &miscounted()), vec![0..100]);
139        assert_eq!(parse_ns_table(100, &ns_table(&[50, 30])), vec![0..100]);
140        // A table, but sized for another payload.
141        assert_eq!(parse_ns_table(100, &ns_table(&[30, 90])), vec![0..100]);
142        assert_eq!(parse_ns_table(100, &ns_table(&[30, 110])), vec![0..100]);
143        assert_eq!(parse_ns_table(100, &ns_table(&[])), vec![0..100]);
144    }
145
146    #[test]
147    fn ns_table_payload_byte_len_is_the_final_offset_of_a_table() {
148        assert_eq!(ns_table_payload_byte_len(&ns_table(&[30, 90])), Some(90));
149        assert_eq!(ns_table_payload_byte_len(&ns_table(&[100])), Some(100));
150        assert_eq!(ns_table_payload_byte_len(&ns_table(&[])), Some(0));
151        assert_eq!(ns_table_payload_byte_len(&[]), None);
152        assert_eq!(ns_table_payload_byte_len(&ns_table(&[30, 100])[..9]), None);
153        assert_eq!(ns_table_payload_byte_len(&miscounted()), None);
154        assert_eq!(ns_table_payload_byte_len(&ns_table(&[50, 30])), None);
155    }
156}
hotshot_types/data/ns_table.rs

hotshot_types/data/
ns_table.rs
