Inside Bitcoin

1// Copyright (c) 2019-present The Bitcoin Core developers
2// Distributed under the MIT software license, see the accompanying
3// file COPYING or http://www.opensource.org/licenses/mit-license.php.
4
5#include <util/asmap.h>
6
7#include <hash.h>
8#include <streams.h>
9#include <uint256.h>
10#include <util/check.h>
11#include <util/fs.h>
12#include <util/log.h>
13
14#include <bit>
15#include <cstddef>
16#include <cstdio>
17#include <span>
18#include <string>
19#include <utility>
20#include <vector>
21
22/*
23 * ASMap (Autonomous System Map) Implementation
24 *
25 * Provides a compressed mapping from IP address prefixes to Autonomous System Numbers (ASNs).
26 * Uses a binary trie structure encoded as bytecode instructions that are interpreted
27 * at runtime to find the ASN for a given IP address.
28 *
29 * The format of the asmap data is a bit-packed binary format where the entire mapping
30 * is treated as a continuous sequence of bits. Instructions and their arguments are
31 * encoded using variable numbers of bits and concatenated together without regard for
32 * byte boundaries. The bits are stored in bytes using little-endian bit ordering.
33 *
34 * The data structure internally represents the mapping as a binary trie where:
35 * - Unassigned subnets (no ASN mapping present) map to 0
36 * - Subnets mapped entirely to one ASN become leaf nodes
37 * - Subnets whose lower and upper halves have different mappings branch into subtrees
38 *
39 * The encoding uses variable-length integers and four instruction types (RETURN, JUMP,
40 * MATCH, DEFAULT) to efficiently represent the trie.
41 */
42
43namespace {
44
45// Indicates decoding errors or invalid data
46constexpr uint32_t INVALID = 0xFFFFFFFF;
47
48/**
49 * Extract a single bit from byte array using little-endian bit ordering (LSB first).
50 * Used for ASMap data.
51 */
52inline bool ConsumeBitLE(size_t& bitpos, std::span<const std::byte> bytes) noexcept
53{
54    const bool bit = (std::to_integer<uint8_t>(bytes[bitpos / 8]) >> (bitpos % 8)) & 1;
55    ++bitpos;
56    return bit;
57}
58
59/**
60 * Extract a single bit from byte array using big-endian bit ordering (MSB first).
61 * Used for IP addresses to match network byte order conventions.
62 */
63inline bool ConsumeBitBE(uint8_t& bitpos, std::span<const std::byte> bytes) noexcept
64{
65    const bool bit = (std::to_integer<uint8_t>(bytes[bitpos / 8]) >> (7 - (bitpos % 8))) & 1;
66    ++bitpos;
67    return bit;
68}
69
70/**
71 * Variable-length integer decoder using a custom encoding scheme.
72 *
73 * The encoding is easiest to describe using an example. Let's say minval=100 and
74 * bit_sizes=[4,2,2,3]. In that case:
75 * - x in [100..115]: encoded as [0] + [4-bit BE encoding of (x-100)]
76 * - x in [116..119]: encoded as [1,0] + [2-bit BE encoding of (x-116)]
77 * - x in [120..123]: encoded as [1,1,0] + [2-bit BE encoding of (x-120)]
78 * - x in [124..131]: encoded as [1,1,1] + [3-bit BE encoding of (x-124)]
79 *
80 * In general, every number is encoded as:
81 * - First, k "1"-bits, where k is the class the number falls in
82 * - Then, a "0"-bit, unless k is the highest class
83 * - Lastly, bit_sizes[k] bits encoding in big endian the position within that class
84 */
85uint32_t DecodeBits(size_t& bitpos, const std::span<const std::byte> data, uint8_t minval, const std::span<const uint8_t> bit_sizes)
86{
87    uint32_t val = minval;  // Start with minimum encodable value
88    bool bit;
89    for (auto bit_sizes_it = bit_sizes.begin(); bit_sizes_it != bit_sizes.end(); ++bit_sizes_it) {
90        // Read continuation bit to determine if we're in this class
91        if (bit_sizes_it + 1 != bit_sizes.end()) {  // Unless we're in the last class
92            if (bitpos >= data.size() * 8) break;
93            bit = ConsumeBitLE(bitpos, data);
94        } else {
95            bit = 0;  // Last class has no continuation bit
96        }
97        if (bit) {
98            // If the value will not fit in this class, subtract its range from val,
99            // emit a "1" bit and continue with the next class
100            val += (1 << *bit_sizes_it);  // Add size of this class
101        } else {
102            // Decode the position within this class in big endian
103            for (int b = 0; b < *bit_sizes_it; b++) {
104                if (bitpos >= data.size() * 8) return INVALID; // Reached EOF in mantissa
105                bit = ConsumeBitLE(bitpos, data);
106                val += bit << (*bit_sizes_it - 1 - b); // Big-endian within the class
107            }
108            return val;
109        }
110    }
111    return INVALID; // Reached EOF in exponent
112}
113
114/**
115 * Instruction Set
116 *
117 * The instruction set is designed to efficiently encode a binary trie
118 * that maps IP prefixes to ASNs. Each instruction type serves a specific
119 * role in trie traversal and evaluation.
120 */
121enum class Instruction : uint32_t
122{
123    // A return instruction, encoded as [0], returns a constant ASN.
124    // It is followed by an integer using the ASN encoding.
125    RETURN = 0,
126    // A jump instruction, encoded as [1,0], inspects the next unused bit in the input
127    // and either continues execution (if 0), or skips a specified number of bits (if 1).
128    // It is followed by an integer using jump encoding.
129    JUMP = 1,
130    // A match instruction, encoded as [1,1,0], inspects 1 or more of the next unused bits
131    // in the input. If they all match, execution continues. If not, the default ASN is returned
132    // (or 0 if unset). The match value encodes both the pattern and its length.
133    MATCH = 2,
134    // A default instruction, encoded as [1,1,1], sets the default variable to its argument,
135    // and continues execution. It is followed by an integer in ASN encoding.
136    DEFAULT = 3,
137};
138
139// Instruction type encoding: RETURN=[0], JUMP=[1,0], MATCH=[1,1,0], DEFAULT=[1,1,1]
140constexpr uint8_t TYPE_BIT_SIZES[]{0, 0, 1};
141Instruction DecodeType(size_t& bitpos, const std::span<const std::byte> data)
142{
143    return Instruction(DecodeBits(bitpos, data, 0, TYPE_BIT_SIZES));
144}
145
146// ASN encoding: Can encode ASNs from 1 to ~16.7 million.
147// Uses variable-length encoding optimized for real-world ASN distribution.
148// ASN 0 is reserved and used if there isn't a match.
149constexpr uint8_t ASN_BIT_SIZES[]{15, 16, 17, 18, 19, 20, 21, 22, 23, 24};
150uint32_t DecodeASN(size_t& bitpos, const std::span<const std::byte> data)
151{
152    return DecodeBits(bitpos, data, 1, ASN_BIT_SIZES);
153}
154
155// MATCH argument: Values in [2, 511]. The highest set bit determines the match length
156// n ∈ [1,8]; the lower n-1 bits are the pattern to compare.
157constexpr uint8_t MATCH_BIT_SIZES[]{1, 2, 3, 4, 5, 6, 7, 8};
158uint32_t DecodeMatch(size_t& bitpos, const std::span<const std::byte> data)
159{
160    return DecodeBits(bitpos, data, 2, MATCH_BIT_SIZES);
161}
162
163// JUMP offset: Minimum value 17. Variable-length coded and may be large
164// for skipping big subtrees.
165constexpr uint8_t JUMP_BIT_SIZES[]{5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30};
166uint32_t DecodeJump(size_t& bitpos, const std::span<const std::byte> data)
167{
168    return DecodeBits(bitpos, data, 17, JUMP_BIT_SIZES);
169}
170
171} // anonymous namespace
172
173/**
174 * Execute the ASMap bytecode to find the ASN for an IP
175 *
176 * This function interprets the asmap bytecode and uses bits from the IP
177 * address to navigate through the encoded trie structure, ultimately
178 * returning an ASN value.
179 */
180uint32_t Interpret(const std::span<const std::byte> asmap, const std::span<const std::byte> ip)
181{
182    size_t pos{0};
183    const size_t endpos{asmap.size() * 8};
184    uint8_t ip_bit{0};
185    const uint8_t ip_bits_end = ip.size() * 8;
186    uint32_t default_asn = 0;
187    while (pos < endpos) {
188        Instruction opcode = DecodeType(pos, asmap);
189        if (opcode == Instruction::RETURN) {
190            // Found leaf node - return the ASN
191            uint32_t asn = DecodeASN(pos, asmap);
192            if (asn == INVALID) break; // ASN straddles EOF
193            return asn;
194        } else if (opcode == Instruction::JUMP) {
195            // Binary branch: if IP bit is 1, jump forward; else continue
196            uint32_t jump = DecodeJump(pos, asmap);
197            if (jump == INVALID) break; // Jump offset straddles EOF
198            if (ip_bit == ip_bits_end) break; // No input bits left
199            if (int64_t{jump} >= static_cast<int64_t>(endpos - pos)) break; // Jumping past EOF
200            if (ConsumeBitBE(ip_bit, ip)) {  // Check next IP bit (big-endian)
201                pos += jump;  // Bit = 1: skip to right subtree
202            }
203            // Bit = 0: fall through to left subtree
204        } else if (opcode == Instruction::MATCH) {
205            // Compare multiple IP bits against a pattern
206            // The match value encodes both length and pattern:
207            // - highest set bit position determines length (bit_width - 1)
208            // - lower bits contain the pattern to compare
209            uint32_t match = DecodeMatch(pos, asmap);
210            if (match == INVALID) break; // Match bits straddle EOF
211            int matchlen = std::bit_width(match) - 1;  // An n-bit value matches n-1 input bits
212            if ((ip_bits_end - ip_bit) < matchlen) break; // Not enough input bits
213            for (int bit = 0; bit < matchlen; bit++) {
214                if (ConsumeBitBE(ip_bit, ip) != ((match >> (matchlen - 1 - bit)) & 1)) {
215                    return default_asn;  // Pattern mismatch - use default
216                }
217            }
218            // Pattern matched - continue execution
219        } else if (opcode == Instruction::DEFAULT) {
220            // Update the default ASN for subsequent MATCH failures
221            default_asn = DecodeASN(pos, asmap);
222            if (default_asn == INVALID) break; // ASN straddles EOF
223        } else {
224            break; // Instruction straddles EOF
225        }
226    }
227    // Reached EOF without RETURN, or aborted (see any of the breaks above)
228    // - should have been caught by SanityCheckAsmap below
229    assert(false);
230    return 0; // 0 is not a valid ASN
231}
232
233/**
234 * Validates ASMap structure by simulating all possible execution paths.
235 * Ensures well-formed bytecode, valid jumps, and proper termination.
236 */
237bool SanityCheckAsmap(const std::span<const std::byte> asmap, int bits)
238{
239    size_t pos{0};
240    const size_t endpos{asmap.size() * 8};
241    std::vector<std::pair<uint32_t, int>> jumps; // All future positions we may jump to (bit offset in asmap -> bits to consume left)
242    jumps.reserve(bits);
243    Instruction prevopcode = Instruction::JUMP;
244    bool had_incomplete_match = false;  // Track <8 bit matches for efficiency check
245
246    while (pos != endpos) {
247        // There was a jump into the middle of the previous instruction
248        if (!jumps.empty() && pos >= jumps.back().first) return false;
249
250        Instruction opcode = DecodeType(pos, asmap);