bitcoin/
bip152.rs

1// SPDX-License-Identifier: CC0-1.0
2
3//! BIP152 Compact Blocks
4//!
5//! Implementation of compact blocks data structure and algorithms.
6//!
7
8use core::{convert, fmt, mem};
9#[cfg(feature = "std")]
10use std::error;
11
12use hashes::{sha256, siphash24, Hash};
13use internals::impl_array_newtype;
14use io::{Read, Write};
15
16use crate::consensus::encode::{self, Decodable, Encodable, VarInt};
17use crate::internal_macros::{impl_bytes_newtype, impl_consensus_encoding};
18use crate::prelude::*;
19use crate::{block, Block, BlockHash, Transaction};
20
21/// A BIP-152 error
22#[derive(Debug, Clone, PartialEq, Eq)]
23#[non_exhaustive]
24pub enum Error {
25    /// An unknown version number was used.
26    UnknownVersion,
27    /// The prefill slice provided was invalid.
28    InvalidPrefill,
29}
30
31internals::impl_from_infallible!(Error);
32
33impl fmt::Display for Error {
34    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
35        match *self {
36            Error::UnknownVersion => write!(f, "an unknown version number was used"),
37            Error::InvalidPrefill => write!(f, "the prefill slice provided was invalid"),
38        }
39    }
40}
41
42#[cfg(feature = "std")]
43impl std::error::Error for Error {
44    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
45        use self::Error::*;
46
47        match *self {
48            UnknownVersion | InvalidPrefill => None,
49        }
50    }
51}
52
53/// A [PrefilledTransaction] structure is used in [HeaderAndShortIds] to
54/// provide a list of a few transactions explicitly.
55#[derive(PartialEq, Eq, Clone, Debug, PartialOrd, Ord, Hash)]
56pub struct PrefilledTransaction {
57    /// The index of the transaction in the block.
58    ///
59    /// This field is differentially encoded relative to the previous
60    /// prefilled transaction as described as follows:
61    ///
62    /// > Several uses of CompactSize below are "differentially encoded". For
63    /// > these, instead of using raw indexes, the number encoded is the
64    /// > difference between the current index and the previous index, minus one.
65    /// > For example, a first index of 0 implies a real index of 0, a second
66    /// > index of 0 thereafter refers to a real index of 1, etc.
67    pub idx: u16,
68    /// The actual transaction.
69    pub tx: Transaction,
70}
71
72impl convert::AsRef<Transaction> for PrefilledTransaction {
73    fn as_ref(&self) -> &Transaction { &self.tx }
74}
75
76impl Encodable for PrefilledTransaction {
77    #[inline]
78    fn consensus_encode<W: Write + ?Sized>(&self, w: &mut W) -> Result<usize, io::Error> {
79        Ok(VarInt::from(self.idx).consensus_encode(w)? + self.tx.consensus_encode(w)?)
80    }
81}
82
83impl Decodable for PrefilledTransaction {
84    #[inline]
85    fn consensus_decode<R: Read + ?Sized>(r: &mut R) -> Result<Self, encode::Error> {
86        let idx = VarInt::consensus_decode(r)?.0;
87        let idx = u16::try_from(idx)
88            .map_err(|_| encode::Error::ParseFailed("BIP152 prefilled tx index out of bounds"))?;
89        let tx = Transaction::consensus_decode(r)?;
90        Ok(PrefilledTransaction { idx, tx })
91    }
92}
93
94/// Short transaction IDs are used to represent a transaction without sending a full 256-bit hash.
95#[derive(PartialEq, Eq, Clone, Copy, Hash, Default, PartialOrd, Ord)]
96pub struct ShortId([u8; 6]);
97impl_array_newtype!(ShortId, u8, 6);
98impl_bytes_newtype!(ShortId, 6);
99
100impl ShortId {
101    /// Calculate the SipHash24 keys used to calculate short IDs.
102    pub fn calculate_siphash_keys(header: &block::Header, nonce: u64) -> (u64, u64) {
103        // 1. single-SHA256 hashing the block header with the nonce appended (in little-endian)
104        let h = {
105            let mut engine = sha256::Hash::engine();
106            header.consensus_encode(&mut engine).expect("engines don't error");
107            nonce.consensus_encode(&mut engine).expect("engines don't error");
108            sha256::Hash::from_engine(engine)
109        };
110
111        // 2. Running SipHash-2-4 with the input being the transaction ID and the keys (k0/k1)
112        // set to the first two little-endian 64-bit integers from the above hash, respectively.
113        (
114            u64::from_le_bytes(h[0..8].try_into().expect("8 byte slice")),
115            u64::from_le_bytes(h[8..16].try_into().expect("8 byte slice")),
116        )
117    }
118
119    /// Calculate the short ID with the given (w)txid and using the provided SipHash keys.
120    pub fn with_siphash_keys<T: AsRef<[u8]>>(txid: &T, siphash_keys: (u64, u64)) -> ShortId {
121        // 2. Running SipHash-2-4 with the input being the transaction ID and the keys (k0/k1)
122        // set to the first two little-endian 64-bit integers from the above hash, respectively.
123        let hash = siphash24::Hash::hash_with_keys(siphash_keys.0, siphash_keys.1, txid.as_ref());
124
125        // 3. Dropping the 2 most significant bytes from the SipHash output to make it 6 bytes.
126        let mut id = ShortId([0; 6]);
127        id.0.copy_from_slice(&hash[0..6]);
128        id
129    }
130}
131
132impl Encodable for ShortId {
133    #[inline]
134    fn consensus_encode<W: Write + ?Sized>(&self, w: &mut W) -> Result<usize, io::Error> {
135        self.0.consensus_encode(w)
136    }
137}
138
139impl Decodable for ShortId {
140    #[inline]
141    fn consensus_decode<R: Read + ?Sized>(r: &mut R) -> Result<ShortId, encode::Error> {
142        Ok(ShortId(Decodable::consensus_decode(r)?))
143    }
144}
145
146/// A structure to relay a block header, short IDs, and a select few transactions.
147///
148/// A [HeaderAndShortIds] structure is used to relay a block header, the short
149/// transactions IDs used for matching already-available transactions, and a
150/// select few transactions which we expect a peer may be missing.
151#[derive(PartialEq, Eq, Clone, Debug, PartialOrd, Ord, Hash)]
152pub struct HeaderAndShortIds {
153    /// The header of the block being provided.
154    pub header: block::Header,
155    ///  A nonce for use in short transaction ID calculations.
156    pub nonce: u64,
157    ///  The short transaction IDs calculated from the transactions
158    ///  which were not provided explicitly in prefilled_txs.
159    pub short_ids: Vec<ShortId>,
160    ///  Used to provide the coinbase transaction and a select few
161    ///  which we expect a peer may be missing.
162    pub prefilled_txs: Vec<PrefilledTransaction>,
163}
164impl_consensus_encoding!(HeaderAndShortIds, header, nonce, short_ids, prefilled_txs);
165
166impl HeaderAndShortIds {
167    /// Create a new [HeaderAndShortIds] from a full block.
168    ///
169    /// The version number must be either 1 or 2.
170    ///
171    /// The `prefill` slice indicates which transactions should be prefilled in
172    /// the block. It should contain the indexes in the block of the txs to
173    /// prefill. It must be ordered. 0 should not be included as the
174    /// coinbase tx is always prefilled.
175    ///
176    /// > Nodes SHOULD NOT use the same nonce across multiple different blocks.
177    pub fn from_block(
178        block: &Block,
179        nonce: u64,
180        version: u32,
181        mut prefill: &[usize],
182    ) -> Result<HeaderAndShortIds, Error> {
183        if version != 1 && version != 2 {
184            return Err(Error::UnknownVersion);
185        }
186
187        let siphash_keys = ShortId::calculate_siphash_keys(&block.header, nonce);
188
189        let mut prefilled = Vec::with_capacity(prefill.len() + 1); // +1 for coinbase tx
190        let mut short_ids = Vec::with_capacity(block.txdata.len() - prefill.len());
191        let mut last_prefill = 0;
192        for (idx, tx) in block.txdata.iter().enumerate() {
193            // Check if we should prefill this tx.
194            let prefill_tx = if prefill.first() == Some(&idx) {
195                prefill = &prefill[1..];
196                true
197            } else {
198                idx == 0 // Always prefill coinbase.
199            };
200
201            if prefill_tx {
202                let diff_idx = idx - last_prefill;
203                last_prefill = idx + 1;
204                prefilled.push(PrefilledTransaction {
205                    idx: diff_idx as u16,
206                    tx: match version {
207                        // >  As encoded in "tx" messages sent in response to getdata MSG_TX
208                        1 => {
209                            // strip witness for version 1
210                            let mut no_witness = tx.clone();
211                            no_witness.input.iter_mut().for_each(|i| i.witness.clear());
212                            no_witness
213                        }
214                        // > Transactions inside cmpctblock messages (both those used as direct
215                        // > announcement and those in response to getdata) and in blocktxn should
216                        // > include witness data, using the same format as responses to getdata
217                        // > MSG_WITNESS_TX, specified in BIP144.
218                        2 => tx.clone(),
219                        _ => unreachable!(),
220                    },
221                });
222            } else {
223                short_ids.push(ShortId::with_siphash_keys(
224                    &match version {
225                        1 => tx.compute_txid().to_raw_hash(),
226                        2 => tx.compute_wtxid().to_raw_hash(),
227                        _ => unreachable!(),
228                    },
229                    siphash_keys,
230                ));
231            }
232        }
233
234        if !prefill.is_empty() {
235            return Err(Error::InvalidPrefill);
236        }
237
238        Ok(HeaderAndShortIds {
239            header: block.header,
240            nonce,
241            // Provide coinbase prefilled.
242            prefilled_txs: prefilled,
243            short_ids,
244        })
245    }
246}
247
248/// A [BlockTransactionsRequest] structure is used to list transaction indexes
249/// in a block being requested.
250#[derive(PartialEq, Eq, Clone, Debug, PartialOrd, Ord, Hash)]
251pub struct BlockTransactionsRequest {
252    ///  The blockhash of the block which the transactions being requested are in.
253    pub block_hash: BlockHash,
254    ///  The indexes of the transactions being requested in the block.
255    ///
256    ///  Warning: Encoding panics with [`u64::MAX`] values. See [`BlockTransactionsRequest::consensus_encode()`]
257    pub indexes: Vec<u64>,
258}
259
260impl Encodable for BlockTransactionsRequest {
261    /// # Panics
262    ///
263    /// Panics if the index overflows [`u64::MAX`]. This happens when [`BlockTransactionsRequest::indexes`]
264    /// contains an entry with the value [`u64::MAX`] as `u64` overflows during differential encoding.
265    fn consensus_encode<W: Write + ?Sized>(&self, w: &mut W) -> Result<usize, io::Error> {
266        let mut len = self.block_hash.consensus_encode(w)?;
267        // Manually encode indexes because they are differentially encoded VarInts.
268        len += VarInt(self.indexes.len() as u64).consensus_encode(w)?;
269        let mut last_idx = 0;
270        for idx in &self.indexes {
271            len += VarInt(*idx - last_idx).consensus_encode(w)?;
272            last_idx = *idx + 1; // can panic here
273        }
274        Ok(len)
275    }
276}
277
278impl Decodable for BlockTransactionsRequest {
279    fn consensus_decode<R: Read + ?Sized>(r: &mut R) -> Result<Self, encode::Error> {
280        Ok(BlockTransactionsRequest {
281            block_hash: BlockHash::consensus_decode(r)?,
282            indexes: {
283                // Manually decode indexes because they are differentially encoded VarInts.
284                let nb_indexes = VarInt::consensus_decode(r)?.0 as usize;
285
286                // Since the number of indices ultimately represent transactions,
287                // we can limit the number of indices to the maximum number of
288                // transactions that would be allowed in a vector.
289                let byte_size = (nb_indexes)
290                    .checked_mul(mem::size_of::<Transaction>())
291                    .ok_or(encode::Error::ParseFailed("Invalid length"))?;
292                if byte_size > encode::MAX_VEC_SIZE {
293                    return Err(encode::Error::OversizedVectorAllocation {
294                        requested: byte_size,
295                        max: encode::MAX_VEC_SIZE,
296                    });
297                }
298
299                let mut indexes = Vec::with_capacity(nb_indexes);
300                let mut last_index: u64 = 0;
301                for _ in 0..nb_indexes {
302                    let differential: VarInt = Decodable::consensus_decode(r)?;
303                    last_index = match last_index.checked_add(differential.0) {
304                        Some(i) => i,
305                        None => return Err(encode::Error::ParseFailed("block index overflow")),
306                    };
307                    indexes.push(last_index);
308                    last_index = match last_index.checked_add(1) {
309                        Some(i) => i,
310                        None => return Err(encode::Error::ParseFailed("block index overflow")),
311                    };
312                }
313                indexes
314            },
315        })
316    }
317}
318
319/// A transaction index is requested that is out of range from the
320/// corresponding block.
321#[derive(Debug, Clone, PartialEq, Eq)]
322#[non_exhaustive]
323pub struct TxIndexOutOfRangeError(u64);
324
325impl fmt::Display for TxIndexOutOfRangeError {
326    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
327        write!(
328            f,
329            "a transaction index is requested that is \
330            out of range from the corresponding block: {}",
331            self.0,
332        )
333    }
334}
335
336#[cfg(feature = "std")]
337impl error::Error for TxIndexOutOfRangeError {
338    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> { None }
339}
340
341/// A [BlockTransactions] structure is used to provide some of the transactions
342/// in a block, as requested.
343#[derive(PartialEq, Eq, Clone, Debug, PartialOrd, Ord, Hash)]
344pub struct BlockTransactions {
345    ///  The blockhash of the block which the transactions being provided are in.
346    pub block_hash: BlockHash,
347    ///  The transactions provided.
348    pub transactions: Vec<Transaction>,
349}
350impl_consensus_encoding!(BlockTransactions, block_hash, transactions);
351
352impl BlockTransactions {
353    /// Construct a [BlockTransactions] from a [BlockTransactionsRequest] and
354    /// the corresponding full [Block] by providing all requested transactions.
355    pub fn from_request(
356        request: &BlockTransactionsRequest,
357        block: &Block,
358    ) -> Result<BlockTransactions, TxIndexOutOfRangeError> {
359        Ok(BlockTransactions {
360            block_hash: request.block_hash,
361            transactions: {
362                let mut txs = Vec::with_capacity(request.indexes.len());
363                for idx in &request.indexes {
364                    if *idx >= block.txdata.len() as u64 {
365                        return Err(TxIndexOutOfRangeError(*idx));
366                    }
367                    txs.push(block.txdata[*idx as usize].clone());
368                }
369                txs
370            },
371        })
372    }
373}
374
375#[cfg(test)]
376mod test {
377    use hex::FromHex;
378
379    use super::*;
380    use crate::blockdata::block::TxMerkleNode;
381    use crate::blockdata::locktime::absolute;
382    use crate::blockdata::transaction;
383    use crate::consensus::encode::{deserialize, serialize};
384    use crate::{Amount, CompactTarget, OutPoint, ScriptBuf, Sequence, TxIn, TxOut, Txid, Witness};
385
386    fn dummy_tx(nonce: &[u8]) -> Transaction {
387        Transaction {
388            version: transaction::Version::ONE,
389            lock_time: absolute::LockTime::from_consensus(2),
390            input: vec![TxIn {
391                previous_output: OutPoint::new(Txid::hash(nonce), 0),
392                script_sig: ScriptBuf::new(),
393                sequence: Sequence(1),
394                witness: Witness::new(),
395            }],
396            output: vec![TxOut { value: Amount::ONE_SAT, script_pubkey: ScriptBuf::new() }],
397        }
398    }
399
400    fn dummy_block() -> Block {
401        Block {
402            header: block::Header {
403                version: block::Version::ONE,
404                prev_blockhash: BlockHash::hash(&[0]),
405                merkle_root: TxMerkleNode::hash(&[1]),
406                time: 2,
407                bits: CompactTarget::from_consensus(3),
408                nonce: 4,
409            },
410            txdata: vec![dummy_tx(&[2]), dummy_tx(&[3]), dummy_tx(&[4])],
411        }
412    }
413
414    #[test]
415    fn test_header_and_short_ids_from_block() {
416        let block = dummy_block();
417
418        let compact = HeaderAndShortIds::from_block(&block, 42, 2, &[]).unwrap();
419        assert_eq!(compact.nonce, 42);
420        assert_eq!(compact.short_ids.len(), 2);
421        assert_eq!(compact.prefilled_txs.len(), 1);
422        assert_eq!(compact.prefilled_txs[0].idx, 0);
423        assert_eq!(&compact.prefilled_txs[0].tx, &block.txdata[0]);
424
425        let compact = HeaderAndShortIds::from_block(&block, 42, 2, &[0, 1, 2]).unwrap();
426        let idxs = compact.prefilled_txs.iter().map(|t| t.idx).collect::<Vec<_>>();
427        assert_eq!(idxs, vec![0, 0, 0]);
428
429        let compact = HeaderAndShortIds::from_block(&block, 42, 2, &[2]).unwrap();
430        let idxs = compact.prefilled_txs.iter().map(|t| t.idx).collect::<Vec<_>>();
431        assert_eq!(idxs, vec![0, 1]);
432    }
433
434    #[test]
435    fn test_compact_block_vector() {
436        // Tested with Elements implementation of compact blocks.
437        let raw_block = Vec::<u8>::from_hex("000000206c750a364035aefd5f81508a08769975116d9195312ee4520dceac39e1fdc62c4dc67473b8e354358c1e610afeaff7410858bd45df43e2940f8a62bd3d5e3ac943c2975cffff7f200000000002020000000001010000000000000000000000000000000000000000000000000000000000000000ffffffff04016b0101ffffffff020006062a0100000001510000000000000000266a24aa21a9ed4a3d9f3343dafcc0d6f6d4310f2ee5ce273ed34edca6c75db3a73e7f368734200120000000000000000000000000000000000000000000000000000000000000000000000000020000000001021fc20ba2bd745507b8e00679e3b362558f9457db374ca28ffa5243f4c23a4d5f00000000171600147c9dea14ffbcaec4b575e03f05ceb7a81cd3fcbffdffffff915d689be87b43337f42e26033df59807b768223368f189a023d0242d837768900000000171600147c9dea14ffbcaec4b575e03f05ceb7a81cd3fcbffdffffff0200cdf5050000000017a9146803c72d9154a6a20f404bed6d3dcee07986235a8700e1f5050000000017a9144e6a4c7cb5b5562904843bdf816342f4db9f5797870247304402205e9bf6e70eb0e4b495bf483fd8e6e02da64900f290ef8aaa64bb32600d973c450220670896f5d0e5f33473e5f399ab680cc1d25c2d2afd15abd722f04978f28be887012103e4e4d9312b2261af508b367d8ba9be4f01b61d6d6e78bec499845b4f410bcf2702473044022045ac80596a6ac9c8c572f94708709adaf106677221122e08daf8b9741a04f66a022003ccd52a3b78f8fd08058fc04fc0cffa5f4c196c84eae9e37e2a85babe731b57012103e4e4d9312b2261af508b367d8ba9be4f01b61d6d6e78bec499845b4f410bcf276a000000").unwrap();
438        let raw_compact = Vec::<u8>::from_hex("000000206c750a364035aefd5f81508a08769975116d9195312ee4520dceac39e1fdc62c4dc67473b8e354358c1e610afeaff7410858bd45df43e2940f8a62bd3d5e3ac943c2975cffff7f2000000000a4df3c3744da89fa010a6979e971450100020000000001010000000000000000000000000000000000000000000000000000000000000000ffffffff04016b0101ffffffff020006062a0100000001510000000000000000266a24aa21a9ed4a3d9f3343dafcc0d6f6d4310f2ee5ce273ed34edca6c75db3a73e7f368734200120000000000000000000000000000000000000000000000000000000000000000000000000").unwrap();
439
440        let block: Block = deserialize(&raw_block).unwrap();
441        let nonce = 18053200567810711460;
442        let compact = HeaderAndShortIds::from_block(&block, nonce, 2, &[]).unwrap();
443        let compact_expected = deserialize(&raw_compact).unwrap();
444
445        assert_eq!(compact, compact_expected);
446    }
447
448    #[test]
449    fn test_getblocktx_differential_encoding_de_and_serialization() {
450        let testcases = vec![
451            // differentially encoded VarInts, indicies
452            (vec![4, 0, 5, 1, 10], vec![0, 6, 8, 19]),
453            (vec![1, 0], vec![0]),
454            (vec![5, 0, 0, 0, 0, 0], vec![0, 1, 2, 3, 4]),
455            (vec![3, 1, 1, 1], vec![1, 3, 5]),
456            (vec![3, 0, 0, 253, 0, 1], vec![0, 1, 258]), // .., 253, 0, 1] == VarInt(256)
457        ];
458        let deser_errorcases = vec![
459            vec![2, 255, 254, 255, 255, 255, 255, 255, 255, 255, 0], // .., 255, 254, .., 255] == VarInt(u64::MAX-1)
460            vec![1, 255, 255, 255, 255, 255, 255, 255, 255, 255], // .., 255, 255, .., 255] == VarInt(u64::MAX)
461        ];
462        for testcase in testcases {
463            {
464                // test deserialization
465                let mut raw: Vec<u8> = [0u8; 32].to_vec();
466                raw.extend(testcase.0.clone());
467                let btr: BlockTransactionsRequest = deserialize(&raw.to_vec()).unwrap();
468                assert_eq!(testcase.1, btr.indexes);
469            }
470            {
471                // test serialization
472                let raw: Vec<u8> = serialize(&BlockTransactionsRequest {
473                    block_hash: Hash::all_zeros(),
474                    indexes: testcase.1,
475                });
476                let mut expected_raw: Vec<u8> = [0u8; 32].to_vec();
477                expected_raw.extend(testcase.0);
478                assert_eq!(expected_raw, raw);
479            }
480        }
481        for errorcase in deser_errorcases {
482            {
483                // test that we return Err() if deserialization fails (and don't panic)
484                let mut raw: Vec<u8> = [0u8; 32].to_vec();
485                raw.extend(errorcase);
486                assert!(deserialize::<BlockTransactionsRequest>(&raw.to_vec()).is_err());
487            }
488        }
489    }
490
491    #[test]
492    #[cfg(debug_assertions)]
493    #[should_panic] // 'attempt to add with overflow' in consensus_encode()
494    fn test_getblocktx_panic_when_encoding_u64_max() {
495        serialize(&BlockTransactionsRequest {
496            block_hash: Hash::all_zeros(),
497            indexes: vec![u64::MAX],
498        });
499    }
500}
bitcoin/bip152.rs

bitcoin/
bip152.rs
