bitcoin_consensus_encoding/
compact_size.rs

1// SPDX-License-Identifier: CC0-1.0
2
3//! Compact size codec.
4//!
5//! Compact size is a variable-length integer encoding used throughout the Bitcoin
6//! consensus protocol to encode collection lengths. However, there are also some
7//! unique non-length use cases.
8
9use internals::array_vec::ArrayVec;
10
11use crate::decode::Decoder;
12use crate::encode::{Encoder, EncoderStatus, ExactSizeEncoder};
13use crate::error::{
14    CompactSizeDecoderError, CompactSizeDecoderErrorInner, LengthPrefixExceedsMaxError,
15};
16use crate::DecoderStatus;
17
18/// Default maximum size of a decoded object in bytes.
19///
20/// Matches Bitcoin Core's default [serialization limit]. This is
21/// a high level anti-DoS limit which all Bitcoin types should
22/// easily fit within.
23///
24/// [serialization limit]: https://github.com/bitcoin/bitcoin/blob/a7c29df0e5ace05b6186612671d6103c112ec922/src/serialize.h#L32
25const MAX_COMPACT_SIZE: usize = 0x0200_0000;
26
27/// The maximum length of a compact size encoding.
28const SIZE: usize = 9;
29
30/// Compact size prefix byte indicating a 2-byte `u16` payload follows.
31const PREFIX_U16: u8 = 0xFD;
32/// Compact size prefix byte indicating a 4-byte `u32` payload follows.
33const PREFIX_U32: u8 = 0xFE;
34/// Compact size prefix byte indicating an 8-byte `u64` payload follows.
35const PREFIX_U64: u8 = 0xFF;
36
37/// Encoder for a compact size encoded integer.
38#[derive(Debug, Clone)]
39pub struct CompactSizeEncoder {
40    buf: ArrayVec<u8, SIZE>,
41}
42
43impl CompactSizeEncoder {
44    /// Constructs a new `CompactSizeEncoder` for a length prefix.
45    ///
46    /// The `usize` type is the natural Rust type for lengths and collection sizes, which is the
47    /// dominant use case for compact size encoding in the Bitcoin protocol. Prefer this constructor
48    /// whenever you are encoding the length of a collection or a byte slice.
49    ///
50    /// Compact size encodings are defined only over the `u64` range. Hypothetical future platforms
51    /// that have `usize` greater than 64 bits are currently not supported.
52    ///
53    /// If you need to encode an arbitrary `u64` integer that is not a length prefix, use
54    /// [`Self::new_u64`] instead.
55    pub fn new(value: usize) -> Self {
56        const _WE_ONLY_SUPPORT_ARCHITECTURES_WITH_UP_TO_64_BIT_USIZE: () = {
57            assert!(core::mem::size_of::<usize>() <= 8);
58        };
59        Self { buf: Self::encode(value as u64) }
60    }
61
62    /// Constructs a new `CompactSizeEncoder` for an arbitrary `u64` integer.
63    ///
64    /// Prefer [`Self::new`] unless you are encoding a non-length integer.
65    ///
66    /// A small number of fields in the Bitcoin protocol are compact-size-encoded integers that are
67    /// not collection lengths (e.g. service flags). Use this constructor for those cases, where the
68    /// natural type of the value is `u64` rather than `usize`.
69    pub fn new_u64(value: u64) -> Self { Self { buf: Self::encode(value) } }
70
71    /// Returns the number of bytes used to encode this `CompactSize` value.
72    ///
73    /// # Returns
74    ///
75    /// - 1 for 0..=0xFC
76    /// - 3 for 0xFD..=(2^16-1)
77    /// - 5 for 0x10000..=(2^32-1)
78    /// - 9 otherwise.
79    #[inline]
80    pub const fn encoded_size(value: usize) -> usize {
81        match value {
82            0..=0xFC => 1,
83            0xFD..=0xFFFF => 3,
84            0x10000..=0xFFFF_FFFF => 5,
85            _ => 9,
86        }
87    }
88
89    /// Encodes `CompactSize` without allocating.
90    #[inline]
91    fn encode(value: u64) -> ArrayVec<u8, SIZE> {
92        let mut res = ArrayVec::<u8, SIZE>::new();
93        match value {
94            0..=0xFC => {
95                res.push(value as u8); // Cast ok because of match.
96            }
97            0xFD..=0xFFFF => {
98                let v = value as u16; // Cast ok because of match.
99                res.push(PREFIX_U16);
100                res.extend_from_slice(&v.to_le_bytes());
101            }
102            0x10000..=0xFFFF_FFFF => {
103                let v = value as u32; // Cast ok because of match.
104                res.push(PREFIX_U32);
105                res.extend_from_slice(&v.to_le_bytes());
106            }
107            _ => {
108                res.push(PREFIX_U64);
109                res.extend_from_slice(&value.to_le_bytes());
110            }
111        }
112        res
113    }
114}
115
116impl Encoder for CompactSizeEncoder {
117    #[inline]
118    fn current_chunk(&self) -> &[u8] { &self.buf }
119
120    #[inline]
121    fn advance(&mut self) -> EncoderStatus { EncoderStatus::Finished }
122}
123
124impl ExactSizeEncoder for CompactSizeEncoder {
125    #[inline]
126    fn len(&self) -> usize { self.buf.len() }
127}
128
129/// Decodes a compact size encoded integer as a length prefix.
130///
131/// The decoded value is returned as a `usize` and is bounded by a configurable limit (default:
132/// 4,000,000). This limit is a denial-of-service protection: a malicious peer can send a compact
133/// size value up to 2^64-1, and without a limit check the caller might attempt to allocate an
134/// enormous buffer based on that value. [`CompactSizeDecoder`] prevents this by rejecting values
135/// that exceed the limit before returning them to the caller.
136///
137/// If you are decoding an arbitrary `u64` integer that is genuinely not a length prefix, use
138/// [`CompactSizeU64Decoder`] instead.
139///
140/// For more information about decoders see the documentation of the [`Decoder`] trait.
141#[derive(Debug, Clone)]
142pub struct CompactSizeDecoder {
143    buf: ArrayVec<u8, 9>,
144    limit: usize,
145}
146
147impl CompactSizeDecoder {
148    /// Constructs a new compact size decoder with the default 32MB length limit.
149    pub const fn new() -> Self { Self { buf: ArrayVec::new(), limit: MAX_COMPACT_SIZE } }
150
151    /// Constructs a new compact size decoder with a custom length limit.
152    ///
153    /// The decoded value must not exceed `limit`, otherwise [`end`](Self::end) will return an
154    /// error. Use this when you know the field you are decoding has a tighter bound than the
155    /// default limit of 32MB.
156    pub const fn new_with_limit(limit: usize) -> Self { Self { buf: ArrayVec::new(), limit } }
157}
158
159impl Default for CompactSizeDecoder {
160    fn default() -> Self { Self::new() }
161}
162
163impl Decoder for CompactSizeDecoder {
164    type Output = usize;
165    type Error = CompactSizeDecoderError;
166
167    fn push_bytes(&mut self, bytes: &mut &[u8]) -> Result<DecoderStatus, Self::Error> {
168        Ok(compact_size_push_bytes(&mut self.buf, bytes))
169    }
170
171    fn end(self) -> Result<Self::Output, Self::Error> {
172        use CompactSizeDecoderErrorInner as E;
173
174        let dec_value = compact_size_decode_u64(&self.buf)?;
175
176        match usize::try_from(dec_value) {
177            Ok(nsize) if nsize <= self.limit => Ok(nsize),
178            _ => Err(LengthPrefixExceedsMaxError { limit: self.limit, value: dec_value })
179                .map_err(E::ValueExceedsLimit)
180                .map_err(CompactSizeDecoderError),
181        }
182    }
183
184    fn read_limit(&self) -> usize { compact_size_read_limit(&self.buf) }
185}
186
187/// Decodes a compact size encoded integer as a raw `u64`.
188///
189/// If you are decoding a length prefix, you probably want [`CompactSizeDecoder`] instead.
190///
191/// This decoder performs no limit check and no conversion to `usize`. It exists for the small
192/// number of Bitcoin protocol fields that are compact-size-encoded integers but are not length
193/// prefixes (e.g. service flags in the `version` message). For those fields the full `u64` range is
194/// meaningful and there is no associated allocation whose size would be controlled by the decoded
195/// value.
196///
197/// # Denial-of-service warning
198///
199/// Do not use this decoder for length prefixes. If the decoded value is used to size an allocation,
200/// for example as the length of a `Vec`, a malicious peer can send a compact size value of up to
201/// 2^64-1 and cause an out-of-memory condition. [`CompactSizeDecoder`] prevents this by enforcing a
202/// configurable upper bound before returning the value.
203///
204/// For more information about decoders see the documentation of the [`Decoder`] trait.
205#[derive(Debug, Clone)]
206pub struct CompactSizeU64Decoder {
207    buf: ArrayVec<u8, 9>,
208}
209
210impl CompactSizeU64Decoder {
211    /// Constructs a new `CompactSizeU64Decoder`.
212    ///
213    /// See the [struct-level documentation](Self) for guidance on when to use this decoder versus
214    /// [`CompactSizeDecoder`].
215    pub const fn new() -> Self { Self { buf: ArrayVec::new() } }
216}
217
218impl Default for CompactSizeU64Decoder {
219    fn default() -> Self { Self::new() }
220}
221
222impl Decoder for CompactSizeU64Decoder {
223    type Output = u64;
224    type Error = CompactSizeDecoderError;
225
226    fn push_bytes(&mut self, bytes: &mut &[u8]) -> Result<DecoderStatus, Self::Error> {
227        Ok(compact_size_push_bytes(&mut self.buf, bytes))
228    }
229
230    fn end(self) -> Result<Self::Output, Self::Error> { compact_size_decode_u64(&self.buf) }
231
232    fn read_limit(&self) -> usize { compact_size_read_limit(&self.buf) }
233}
234
235/// Pushes bytes into a compact size buffer, returning the decoder status.
236fn compact_size_push_bytes(buf: &mut ArrayVec<u8, 9>, bytes: &mut &[u8]) -> DecoderStatus {
237    if bytes.is_empty() {
238        return DecoderStatus::NeedsMore;
239    }
240
241    if buf.is_empty() {
242        buf.push(bytes[0]);
243        *bytes = &bytes[1..];
244    }
245    let len = match buf[0] {
246        PREFIX_U64 => 9,
247        PREFIX_U32 => 5,
248        PREFIX_U16 => 3,
249        _ => 1,
250    };
251    let to_copy = bytes.len().min(len - buf.len());
252    buf.extend_from_slice(&bytes[..to_copy]);
253    *bytes = &bytes[to_copy..];
254
255    if buf.len() == len {
256        DecoderStatus::Ready
257    } else {
258        DecoderStatus::NeedsMore
259    }
260}
261
262/// Returns the number of bytes the compact size decoder still needs to read.
263fn compact_size_read_limit(buf: &ArrayVec<u8, 9>) -> usize {
264    match buf.len() {
265        0 => 1,
266        already_read => match buf[0] {
267            PREFIX_U64 => 9_usize.saturating_sub(already_read),
268            PREFIX_U32 => 5_usize.saturating_sub(already_read),
269            PREFIX_U16 => 3_usize.saturating_sub(already_read),
270            _ => 0,
271        },
272    }
273}
274
275/// Decodes a compact size buffer to a u64, checking for minimal encoding.
276fn compact_size_decode_u64(buf: &ArrayVec<u8, 9>) -> Result<u64, CompactSizeDecoderError> {
277    use CompactSizeDecoderErrorInner as E;
278
279    fn arr<const N: usize>(slice: &[u8]) -> Result<[u8; N], CompactSizeDecoderError> {
280        slice
281            .try_into()
282            .map_err(|_| E::UnexpectedEof { required: N, received: slice.len() })
283            .map_err(CompactSizeDecoderError)
284    }
285
286    let (first, payload) = buf
287        .split_first()
288        .ok_or(E::UnexpectedEof { required: 1, received: 0 })
289        .map_err(CompactSizeDecoderError)?;
290
291    match *first {
292        PREFIX_U64 => {
293            let x = u64::from_le_bytes(arr(payload)?);
294            if x < 0x100_000_000 {
295                Err(E::NonMinimal { value: x }).map_err(CompactSizeDecoderError)
296            } else {
297                Ok(x)
298            }
299        }
300        PREFIX_U32 => {
301            let x = u32::from_le_bytes(arr(payload)?);
302            if x < 0x10000 {
303                Err(E::NonMinimal { value: x.into() }).map_err(CompactSizeDecoderError)
304            } else {
305                Ok(x.into())
306            }
307        }
308        PREFIX_U16 => {
309            let x = u16::from_le_bytes(arr(payload)?);
310            if x < 0xFD {
311                Err(E::NonMinimal { value: x.into() }).map_err(CompactSizeDecoderError)
312            } else {
313                Ok(x.into())
314            }
315        }
316        n => Ok(n.into()),
317    }
318}
319
320#[cfg(test)]
321mod tests {
322    use super::*;
323
324    #[test]
325    fn encoded_value_1_byte() {
326        // Check lower bound, upper bound (and implicitly endian-ness).
327        for v in [0x00u64, 0x01, 0x02, 0xFA, 0xFB, 0xFC] {
328            assert_eq!(CompactSizeEncoder::encoded_size(v as usize), 1);
329            // Should be encoded as the value as a u8.
330            let want = [v as u8];
331            let got = CompactSizeEncoder::encode(v);
332            assert_eq!(got.as_slice().len(), 1); // sanity check
333            assert_eq!(got.as_slice(), want);
334        }
335    }
336
337    macro_rules! check_encode {
338        ($($test_name:ident, $size:expr, $value:expr, $want:expr);* $(;)?) => {
339            $(
340                #[test]
341                fn $test_name() {
342                    let value = $value as u64; // Because default integer type is i32.
343                    assert_eq!(CompactSizeEncoder::encoded_size(value as usize), $size);
344                    let got = CompactSizeEncoder::encode(value);
345                    assert_eq!(got.as_slice().len(), $size); // sanity check
346                    assert_eq!(got.as_slice(), &$want);
347                }
348            )*
349        }
350    }
351
352    check_encode! {
353        // 3 byte encoding.
354        encoded_value_3_byte_lower_bound, 3, 0xFD, [0xFD, 0xFD, 0x00]; // 0x00FD
355        encoded_value_3_byte_endianness, 3, 0xABCD, [0xFD, 0xCD, 0xAB];
356        encoded_value_3_byte_upper_bound, 3, 0xFFFF, [0xFD, 0xFF, 0xFF];
357        // 5 byte encoding.
358        encoded_value_5_byte_lower_bound, 5, 0x0001_0000, [0xFE, 0x00, 0x00, 0x01, 0x00];
359        encoded_value_5_byte_endianness, 5, 0x0123_4567, [0xFE, 0x67, 0x45, 0x23, 0x01];
360        encoded_value_5_byte_upper_bound, 5, 0xFFFF_FFFF, [0xFE, 0xFF, 0xFF, 0xFF, 0xFF];
361    }
362
363    // 9-byte encoding requires values above u32::MAX which don't fit in usize on 32-bit platforms.
364    #[cfg(target_pointer_width = "64")]
365    check_encode! {
366        encoded_value_9_byte_lower_bound, 9, 0x0000_0001_0000_0000u64, [0xFF, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00];
367        encoded_value_9_byte_endianness, 9, 0x0123_4567_89AB_CDEFu64, [0xFF, 0xEF, 0xCD, 0xAB, 0x89, 0x67, 0x45, 0x23, 0x01];
368        encoded_value_9_byte_upper_bound, 9, u64::MAX, [0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF];
369    }
370
371    #[test]
372    fn compact_size_new_values_too_large() {
373        use CompactSizeDecoderErrorInner as E;
374
375        const EXCESS_COMPACT_SIZE: u64 = (MAX_COMPACT_SIZE + 1) as u64;
376
377        // MAX_COMPACT_SIZE should succeed for `new` constructor
378        // 0x0200_0000 as minimal 5-byte compact size: 0xFE + u32 little-endian
379        let mut decoder = CompactSizeDecoder::new();
380        let _ = decoder.push_bytes(&mut [0xFE, 0x00, 0x00, 0x00, 0x02].as_slice()).unwrap();
381        let got = decoder.end().unwrap();
382        assert_eq!(got, MAX_COMPACT_SIZE);
383
384        // MAX_COMPACT_SIZE + 1 should fail for `new` constructor
385        // 0x0200_0001 as minimal 5-byte compact size: 0xFE + u32 little-endian
386        let mut decoder = CompactSizeDecoder::new();
387        let _ = decoder.push_bytes(&mut [0xFE, 0x01, 0x00, 0x00, 0x02].as_slice()).unwrap();
388        let got = decoder.end().unwrap_err();
389        assert!(matches!(
390            got,
391            CompactSizeDecoderError(E::ValueExceedsLimit(LengthPrefixExceedsMaxError {
392                limit: MAX_COMPACT_SIZE,
393                value: EXCESS_COMPACT_SIZE,
394            })),
395        ));
396    }
397
398    #[test]
399    fn compact_size_new_with_limit_values_too_large() {
400        use CompactSizeDecoderErrorInner as E;
401
402        // 240 should succeed for `new_with_limit` constructor
403        let mut decoder = CompactSizeDecoder::new_with_limit(240);
404        let _ = decoder.push_bytes(&mut [0xf0].as_slice()).unwrap();
405        let got = decoder.end().unwrap();
406        assert_eq!(got, 240);
407
408        // 241 should fail for `new_with_limit` constructor
409        let mut decoder = CompactSizeDecoder::new_with_limit(240);
410        let _ = decoder.push_bytes(&mut [0xf1].as_slice()).unwrap();
411        let got = decoder.end().unwrap_err();
412        assert!(matches!(
413            got,
414            CompactSizeDecoderError(E::ValueExceedsLimit(LengthPrefixExceedsMaxError {
415                limit: 240,
416                value: 241,
417            })),
418        ));
419    }
420}
bitcoin_consensus_encoding/compact_size.rs

bitcoin_consensus_encoding/
compact_size.rs
