1// Copyright (c) 2012 Pieter Wuille
2// Copyright (c) 2012-present The Bitcoin Core developers
3// Distributed under the MIT software license, see the accompanying
4// file COPYING or http://www.opensource.org/licenses/mit-license.php.
5
6#ifndef BITCOIN_ADDRMAN_H
7#define BITCOIN_ADDRMAN_H
8
9#include <netaddress.h>
10#include <protocol.h>
11#include <util/time.h>
12
13#include <cstddef>
14#include <cstdint>
15#include <ios>
16#include <memory>
17#include <optional>
18#include <string>
19#include <unordered_set>
20#include <utility>
21#include <vector>
22
23class NetGroupManager;
24
25/** Over how many buckets entries with tried addresses from a single group (/16 for IPv4) are spread */
26inline constexpr uint32_t ADDRMAN_TRIED_BUCKETS_PER_GROUP{8};
27/** Over how many buckets entries with new addresses originating from a single group are spread */
28inline constexpr uint32_t ADDRMAN_NEW_BUCKETS_PER_SOURCE_GROUP{64};
29/** Maximum number of times an address can occur in the new table */
30inline constexpr int32_t ADDRMAN_NEW_BUCKETS_PER_ADDRESS{8};
31/** How old addresses can maximally be */
32inline constexpr auto ADDRMAN_HORIZON{30 * 24h};
33/** After how many failed attempts we give up on a new node */
34inline constexpr int32_t ADDRMAN_RETRIES{3};
35/** How many successive failures are allowed ... */
36inline constexpr int32_t ADDRMAN_MAX_FAILURES{10};
37/** ... in at least this duration */
38inline constexpr auto ADDRMAN_MIN_FAIL{7 * 24h};
39/** How recent a successful connection should be before we allow an address to be evicted from tried */
40inline constexpr auto ADDRMAN_REPLACEMENT{4h};
41/** The maximum number of tried addr collisions to store */
42inline constexpr size_t ADDRMAN_SET_TRIED_COLLISION_SIZE{10};
43/** The maximum time we'll spend trying to resolve a tried table collision */
44inline constexpr auto ADDRMAN_TEST_WINDOW{40min};
45
46class InvalidAddrManVersionError : public std::ios_base::failure
47{
48public:
49    InvalidAddrManVersionError(std::string msg) : std::ios_base::failure(msg) { }
50};
51
52class AddrManImpl;
53class AddrInfo;
54
55/** Default for -checkaddrman */
56inline constexpr int32_t DEFAULT_ADDRMAN_CONSISTENCY_CHECKS{0};
57
58/** Location information for an address in AddrMan */
59struct AddressPosition {
60    // Whether the address is in the new or tried table
61    const bool tried;
62
63    // Addresses in the tried table should always have a multiplicity of 1.
64    // Addresses in the new table can have multiplicity between 1 and
65    // ADDRMAN_NEW_BUCKETS_PER_ADDRESS
66    const int multiplicity;
67
68    // If the address is in the new table, the bucket and position are
69    // populated based on the first source who sent the address.
70    // In certain edge cases, this may not be where the address is currently
71    // located.
72    const int bucket;
73    const int position;
74
75    bool operator==(const AddressPosition&) const = default;
76    explicit AddressPosition(bool tried_in, int multiplicity_in, int bucket_in, int position_in)
77        : tried{tried_in}, multiplicity{multiplicity_in}, bucket{bucket_in}, position{position_in} {}
78};
79
80/** Stochastic address manager
81 *
82 * Design goals:
83 *  * Keep the address tables in-memory, and asynchronously dump the entire table to peers.dat.
84 *  * Make sure no (localized) attacker can fill the entire table with his nodes/addresses.
85 *
86 * To that end:
87 *  * Addresses are organized into buckets that can each store up to 64 entries.
88 *    * Addresses to which our node has not successfully connected go into 1024 "new" buckets.
89 *      * Based on the address range (/16 for IPv4) of the source of information, or if an asmap is provided,
90 *        the AS it belongs to (for IPv4/IPv6), 64 buckets are selected at random.
91 *      * The actual bucket is chosen from one of these, based on the range in which the address itself is located.
92 *      * The position in the bucket is chosen based on the full address.
93 *      * One single address can occur in up to 8 different buckets to increase selection chances for addresses that
94 *        are seen frequently. The chance for increasing this multiplicity decreases exponentially.
95 *      * When adding a new address to an occupied position of a bucket, it will not replace the existing entry
96 *        unless that address is also stored in another bucket or it doesn't meet one of several quality criteria
97 *        (see IsTerrible for exact criteria).
98 *    * Addresses of nodes that are known to be accessible go into 256 "tried" buckets.
99 *      * Each address range selects at random 8 of these buckets.
100 *      * The actual bucket is chosen from one of these, based on the full address.
101 *      * When adding a new good address to an occupied position of a bucket, a FEELER connection to the
102 *        old address is attempted. The old entry is only replaced and moved back to the "new" buckets if this
103 *        attempt was unsuccessful.
104 *    * Bucket selection is based on cryptographic hashing, using a randomly-generated 256-bit key, which should not
105 *      be observable by adversaries.
106 *    * Several indexes are kept for high performance. Setting m_consistency_check_ratio with the -checkaddrman
107 *      configuration option will introduce (expensive) consistency checks for the entire data structure.
108 */
109class AddrMan
110{
111protected:
112    const std::unique_ptr<AddrManImpl> m_impl;
113
114public:
115    explicit AddrMan(const NetGroupManager& netgroupman, bool deterministic, int32_t consistency_check_ratio);
116
117    ~AddrMan();
118
119    template <typename Stream>
120    void Serialize(Stream& s_) const;
121
122    template <typename Stream>
123    void Unserialize(Stream& s_);
124
125    /**
126    * Return size information about addrman.
127    *
128    * @param[in] net              Select addresses only from specified network (nullopt = all)
129    * @param[in] in_new           Select addresses only from one table (true = new, false = tried, nullopt = both)
130    * @return                     Number of unique addresses that match specified options.
131    */
132    size_t Size(std::optional<Network> net = std::nullopt, std::optional<bool> in_new = std::nullopt) const;
133
134    /**
135     * Attempt to add one or more addresses to addrman's new table.
136     * If an address already exists in addrman, the existing entry may be updated
137     * (e.g. adding additional service flags). If the existing entry is in the new table,
138     * it may be added to more buckets, improving the probability of selection.
139     *
140     * @param[in] vAddr           Address records to attempt to add.
141     * @param[in] source          The address of the node that sent us these addr records.
142     * @param[in] time_penalty    A "time penalty" to apply to the address record's nTime. If a peer
143     *                            sends us an address record with nTime=n, then we'll add it to our
144     *                            addrman with nTime=(n - time_penalty).
145     * @return    true if at least one address is successfully added, or added to an additional bucket. Unaffected by updates. */
146    bool Add(const std::vector<CAddress>& vAddr, const CNetAddr& source, std::chrono::seconds time_penalty = 0s);
147
148    /**
149     * Mark an address record as accessible and attempt to move it to addrman's tried table.
150     *
151     * @param[in] addr            Address record to attempt to move to tried table.
152     * @param[in] time            The time that we were last connected to this peer.
153     * @return    true if the address is successfully moved from the new table to the tried table.
154     */
155    bool Good(const CService& addr, NodeSeconds time = Now<NodeSeconds>());
156
157    //! Mark an entry as connection attempted to.
158    void Attempt(const CService& addr, bool fCountFailure, NodeSeconds time = Now<NodeSeconds>());
159
160    //! See if any to-be-evicted tried table entries have been tested and if so resolve the collisions.
161    void ResolveCollisions();
162
163    /**
164     * Randomly select an address in the tried table that another address is
165     * attempting to evict.
166     *
167     * @return CAddress The record for the selected tried peer.
168     *         seconds  The last time we attempted to connect to that peer.
169     */
170    std::pair<CAddress, NodeSeconds> SelectTriedCollision();
171
172    /**
173     * Choose an address to connect to.
174     *
175     * @param[in] new_only Whether to only select addresses from the new table. Passing `true` returns
176     *                     an address from the new table or an empty pair. Passing `false` will return an
177     *                     empty pair or an address from either the new or tried table (it does not
178     *                     guarantee a tried entry).
179     * @param[in] networks Select only addresses of these networks (empty = all). Passing networks may
180     *                     slow down the search.
181     * @return    CAddress The record for the selected peer.
182     *            seconds  The last time we attempted to connect to that peer.
183     */
184    std::pair<CAddress, NodeSeconds> Select(bool new_only = false, const std::unordered_set<Network>& networks = {}) const;
185
186    /**
187     * Return all or many randomly selected addresses, optionally by network.
188     *
189     * @param[in] max_addresses  Maximum number of addresses to return (0 = all).
190     * @param[in] max_pct        Maximum percentage of addresses to return (0 = all). Value must be from 0 to 100.
191     * @param[in] network        Select only addresses of this network (nullopt = all).
192     * @param[in] filtered       Select only addresses that are considered good quality (false = all).
193     *
194     * @return                   A vector of randomly selected addresses from vRandom.
195     */
196    std::vector<CAddress> GetAddr(size_t max_addresses, size_t max_pct, std::optional<Network> network, bool filtered = true) const;
197
198    /**
199     * Returns an information-location pair for all addresses in the selected addrman table.
200     * If an address appears multiple times in the new table, an information-location pair
201     * is returned for each occurrence. Addresses only ever appear once in the tried table.
202     *
203     * @param[in] from_tried     Selects which table to return entries from.
204     *
205     * @return                   A vector consisting of pairs of AddrInfo and AddressPosition.
206     */
207    std::vector<std::pair<AddrInfo, AddressPosition>> GetEntries(bool from_tried) const;
208
209    /** We have successfully connected to this peer. Calling this function
210     *  updates the CAddress's nTime, which is used in our IsTerrible()
211     *  decisions and gossiped to peers. Callers should be careful that updating
212     *  this information doesn't leak topology information to network spies.
213     *
214     *  net_processing calls this function when it *disconnects* from a peer to
215     *  not leak information about currently connected peers.
216     *
217     * @param[in]   addr     The address of the peer we were connected to
218     * @param[in]   time     The time that we were last connected to this peer
219     */
220    void Connected(const CService& addr, NodeSeconds time = Now<NodeSeconds>());
221
222    //! Update an entry's service bits.
223    void SetServices(const CService& addr, ServiceFlags nServices);
224
225    /** Test-only function
226     * Find the address record in AddrMan and return information about its
227     * position.
228     * @param[in] addr       The address record to look up.
229     * @return               Information about the address record in AddrMan
230     *                       or nullopt if address is not found.
231     */
232    std::optional<AddressPosition> FindAddressEntry(const CAddress& addr);
233};
234
235#endif // BITCOIN_ADDRMAN_H
236