Erlay refactored #21335

git-subtree-dir: src/minisketch
git-subtree-split: 80481500cdb3328adab751db30a3fa7e76fe1147

If a peer supports wtxid our node should notify them
that we are willing to participate in tx reconciliation.
At this point we generate a salt for computing
short tx IDs for reconciliations over this connection.

This helper will be used to determine whether we
should suggest our new peer reconciling with us.

Once we receive a message from a peer signalling
reconciliation support, we initialize the data structures
required to perform reconciliations. If we are planning to
initiate reconciliations with this peer (if it's an outbound connection),
add this peer to the reconciliation queue.

See how many flooding and how many reconciling
outbound peers we have, which is useful to see whether our new
peer should be using flooding or reconciliation.

It helps to save bandwidth and presumably reduces privacy leak.

Have a separate function to announce transactions to a peer (via INVs)
considering INV message limitations.

We need assign and keep track of the way we're going to relay a transaction
based on the connection type the transaction arrived from, to
enable transaction reconciliation protocol.

Flooding and reconciliation are two different ways to announce
transactions to the peers.
For transactions received from inbound links, use flooding to enable
a rapid relay across the reachable nodes.

Use reconciliation (add transactions to the reconciliation sets) for
all transactions which were received from outbound links to enable
an slower but more efficient relay to unreachable nodes.

Since reconciliation is naturally slower than flooding, and also
since we limit the flooding aspect, we should reduce the intervals
between broadcasts (flooding out or adding to reconciliation sets).
Otherwise, transaction relay will be too slow
(and probably less inefficient).

Note that for privacy reasons the ratio between inbound and outbound
delays matter much more than the actual delays. That ratio is preserved
here, so it is not a privacy degradation.

If the peer is next in the queue for reconciliation,
and enough time is passed from the previous
reconciliation, consider a peer for reconciliation.

If there is no pending reconciliation request to the peer,
send one, otherwise just move to the end of queue and
update global next reconciliation request time.

Upon receiving a reconciliation request, a node stores
it and schedules a response.
Do not respond to a request right away as it would enable
a DoS attack and allow monitoring of transaction a node has.
Instead, respond to all reconciliation requests at a same time
after a small delay.

Short ids are used to compute reconciliation sketches.

Sketch is a representation of list of transaction IDs,
which enables reconciliation (an efficient sync of lists
between peers).

When the time comes, a node computes a sketch of the
local transactions based on the parameters sent
in the reconciliation request, and sends that sketch
to the requestor. Clear local state.

At the end of a reconciliation round, a peer may ask us
for transactions by their short id. Add a function for a local
lookup short_id->wtxid.

This currently unused function is supposed to be used once
a reconciliation round is done. It cleans the state corresponding
to the passed reconciliation.

When the sketches from both sides are combined successfully,
the diff is produced. Then this diff can (together with the local txs)
be used to identified which transactions are missing locally and remotely.

Send/request missing transactions, clear the state,
and send a finalization message.

If after decoding a reconciliation sketch it turned out
to be insufficient to find set difference, request extension.
Store the initial sketches so that we are able to process
extension sketch.

If peer failed to reconcile based on our initial response sketch,
they will ask us for a sketch extension. Store this request to respond later.

Add 2 variables tracking reconciliation state:
(1) recon set snapshot and (2) capacity snapshot.
(1) is used to store transactions arrived after we sent out
an initial sketch, but before the reconciliation is over, since
these transactions should not go into a sketch extension.
(2) is used to set the capacity of the extended sketch because
it provides good estimation (efficiency/failure tradeoff).

Compute a sketch with extra capacity and send
those extra syndromes to the peer.
It is safe to respond to an extension request without a delay
because these requests are already limited by initial requests.

If a peer responded to our request with a sketch extension,
attempt to decode it to find missing transactions by combining
it with the initial sketch.
If success, share/request missing transactions.
If failure, send all the transactions we had for the peer.

Once a peer tells us reconciliation is done, we should behave as follows:
- if it was successful, just respond them with the transactions they asked
  by short ID.
- if it was a full failure, respond with all local transactions from the reconciliation
  set snapshot
- if it was a partial failure (only low or high part was failed after a bisection),
  respond with all transactions which were asked for by short id,
  and announce local txs which belong to the failed chunk.