p2p: Announce reconciliation support

If we're connecting to the peer which might support
transaction reconciliation, we announce we want to reconcile
with them.

We store the reconciliation salt so that when the peer
responds with their salt, we are able to compute the
full reconciliation salt.

This behavior is enabled with a CLI flag.

2 files changed, 132 insertions, 0 deletions

diff --git a/src/node/txreconciliation.cpp b/src/node/txreconciliation.cpp
new file mode 100644
index 0000000000..dfac2ad82e
--- /dev/null
+++ b/src/node/txreconciliation.cpp
@@ -0,0 +1,66 @@
+// Copyright (c) 2022 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <node/txreconciliation.h>
+
+#include <util/check.h>
+#include <util/system.h>
+
+#include <unordered_map>
+#include <variant>
+
+
+namespace {
+
+/**
+ * Keeps track of txreconciliation-related per-peer state.
+ */
+class TxReconciliationState
+{
+};
+
+} // namespace
+
+/** Actual implementation for TxReconciliationTracker's data structure. */
+class TxReconciliationTracker::Impl
+{
+private:
+    mutable Mutex m_txreconciliation_mutex;
+
+    /**
+     * Keeps track of txreconciliation states of eligible peers.
+     * For pre-registered peers, the locally generated salt is stored.
+     * For registered peers, the locally generated salt is forgotten, and the state (including
+     * "full" salt) is stored instead.
+     */
+    std::unordered_map<NodeId, std::variant<uint64_t, TxReconciliationState>> m_states GUARDED_BY(m_txreconciliation_mutex);
+
+public:
+    explicit Impl() {}
+
+    uint64_t PreRegisterPeer(NodeId peer_id) EXCLUSIVE_LOCKS_REQUIRED(!m_txreconciliation_mutex)
+    {
+        AssertLockNotHeld(m_txreconciliation_mutex);
+        LOCK(m_txreconciliation_mutex);
+        // We do not support txreconciliation salt/version updates.
+        assert(m_states.find(peer_id) == m_states.end());
+
+        LogPrintLevel(BCLog::TXRECONCILIATION, BCLog::Level::Debug, "Pre-register peer=%d\n", peer_id);
+        const uint64_t local_salt{GetRand(UINT64_MAX)};
+
+        // We do this exactly once per peer (which are unique by NodeId, see GetNewNodeId) so it's
+        // safe to assume we don't have this record yet.
+        Assert(m_states.emplace(peer_id, local_salt).second);
+        return local_salt;
+    }
+};
+
+TxReconciliationTracker::TxReconciliationTracker() : m_impl{std::make_unique<TxReconciliationTracker::Impl>()} {}
+
+TxReconciliationTracker::~TxReconciliationTracker() = default;
+
+uint64_t TxReconciliationTracker::PreRegisterPeer(NodeId peer_id)
+{
+    return m_impl->PreRegisterPeer(peer_id);
+}
diff --git a/src/node/txreconciliation.h b/src/node/txreconciliation.h
new file mode 100644
index 0000000000..6e94a51cf2
--- /dev/null
+++ b/src/node/txreconciliation.h
@@ -0,0 +1,66 @@
+// Copyright (c) 2022 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#ifndef BITCOIN_NODE_TXRECONCILIATION_H
+#define BITCOIN_NODE_TXRECONCILIATION_H
+
+#include <net.h>
+#include <sync.h>
+
+#include <memory>
+#include <tuple>
+
+/** Whether transaction reconciliation protocol should be enabled by default. */
+static constexpr bool DEFAULT_TXRECONCILIATION_ENABLE{false};
+/** Supported transaction reconciliation protocol version */
+static constexpr uint32_t TXRECONCILIATION_VERSION{1};
+
+/**
+ * Transaction reconciliation is a way for nodes to efficiently announce transactions.
+ * This object keeps track of all txreconciliation-related communications with the peers.
+ * The high-level protocol is:
+ * 0.  Txreconciliation protocol handshake.
+ * 1.  Once we receive a new transaction, add it to the set instead of announcing immediately.
+ * 2.  At regular intervals, a txreconciliation initiator requests a sketch from a peer, where a
+ *     sketch is a compressed representation of short form IDs of the transactions in their set.
+ * 3.  Once the initiator received a sketch from the peer, the initiator computes a local sketch,
+ *     and combines the two sketches to attempt finding the difference in *sets*.
+ * 4a. If the difference was not larger than estimated, see SUCCESS below.
+ * 4b. If the difference was larger than estimated, initial txreconciliation fails. The initiator
+ *     requests a larger sketch via an extension round (allowed only once).
+ *     - If extension succeeds (a larger sketch is sufficient), see SUCCESS below.
+ *     - If extension fails (a larger sketch is insufficient), see FAILURE below.
+ *
+ * SUCCESS. The initiator knows full symmetrical difference and can request what the initiator is
+ *          missing and announce to the peer what the peer is missing.
+ *
+ * FAILURE. The initiator notifies the peer about the failure and announces all transactions from
+ *          the corresponding set. Once the peer received the failure notification, the peer
+ *          announces all transactions from their set.
+
+ * This is a modification of the Erlay protocol (https://arxiv.org/abs/1905.10518) with two
+ * changes (sketch extensions instead of bisections, and an extra INV exchange round), both
+ * are motivated in BIP-330.
+ */
+class TxReconciliationTracker
+{
+private:
+    class Impl;
+    const std::unique_ptr<Impl> m_impl;
+
+public:
+    explicit TxReconciliationTracker();
+    ~TxReconciliationTracker();
+
+    /**
+     * Step 0. Generates initial part of the state (salt) required to reconcile txs with the peer.
+     * The salt is used for short ID computation required for txreconciliation.
+     * The function returns the salt.
+     * A peer can't participate in future txreconciliations without this call.
+     * This function must be called only once per peer.
+     */
+    uint64_t PreRegisterPeer(NodeId peer_id);
+};
+
+#endif // BITCOIN_NODE_TXRECONCILIATION_H