Erlay is an alternative method of announcing transactions between peers in the Bitcoin P2P network. Erlay's main goal is to reduce bandwidth utilization when propagating transaction data.
The protocol builds on the assumption that a significant percentage of the data exchanged between peers when broadcasting transactions belongs to inventory (or INV) messages 1️⃣, which are used to announce the transaction hashes between peers. On receiving an INV message containing a collection of transactions, a well-behaved peer will respond with a message requesting all its missing transactions, this is known as a getdata message (or GETDATA).
Erlay tries to solve this issue by using set reconciliation to work out the transaction differences between two nodes connected to each other instead of just announcing all transactions through all links. To do so, nodes keep a set of transactions to be reconciled ****(or reconciliation set) between each of their Erlay-enabled peers, and reconciliation is performed at regular intervals. Once it is time to reconcile, peers exchange sketches 2️⃣ ****of their reconciliation sets, which can be used to optimally compute the symmetrical difference between their reconciliation sets and, therefore, identify which transactions need to be sent by each end of the connection.
Therefore, Erlay aims to reduce traditional transaction relay (called fanout from now on) as much as possible but, maybe counterintuitively, not to completely replace it. For Erlay to be optimal, a small amount of fanout is still needed, given set reconciliation works best (sketches are smaller and sketch differences are cheaper to compute) when the differences between sets are small. This means that, even if all peers of a given node are Erlay enabled, some transactions will still be exchanged using fanout 3️⃣. Moreover, fanout is more efficient, and considerably faster, than set reconciliation provided the receiving node does not know about the transaction being announced.
One of the first details to decide on, when implementing Erlay, is how small we want the network transaction fanout to be. That is, for each Erlay node, how many peers should it select to exchange transactions using fanout. This is a tradeoff between bandwidth efficiency and transaction propagation latency: the bigger the fanout, ****the more initial fast coverage of the network, but the less bandwidth savings. If the fanout ****rate is too low, we could incur drastically slower transaction propagation times, if it is too big, the bandwidth saving would be too small (maybe even not worth the additional code complexity of implementing Erlay). Furthermore, what kind of nodes are selected also matters: in Bitcoin Core, inbound connections are not trusted 1️⃣, and doing fanout only via inbounds could lead to the transaction propagation being controlled by adversarial peers. On top of that, most nodes do not even accept incoming connections due to their hosting settings. However, completely ignoring inbound connections for fanout would also be a mistake.
This raises the question: How many peers do we fanout to, and how are they picked?
Our current approach is to pick a mix of both inbounds and outbound peers, as long as they are available (i.e. an unreachable node would only pick outbounds). The current version of the PR uses 1 outbound and 10% of inbounds, based on Gleb’s simulations.
<aside> <img src="/icons/barricade_yellow.svg" alt="/icons/barricade_yellow.svg" width="40px" />
We are currently working on extending this, given using a percentage of connections for this has the downside that it makes Erlay bandwidth usage still proportional to the number of connections a node maintains. A goal of Erlay is to allow for a higher number of connections per node without increasing the node’s bandwidth requirements. Sort of a scale-free solution.
</aside>
<aside> <img src="/icons/chemistry_orange.svg" alt="/icons/chemistry_orange.svg" width="40px" />
The goal would be finding values that do not necessarily scale with the number of connections. This needs to be simulated
</aside>
Another question that also relates to peer selection is: How do we decide what peers to fanout to / reconcile with?
This question has many parts, depending on the adopted solution. The first of them is: are peers selected for fanout/reconciliation on a connection level, or is the decision-making done at the transaction level (i.e. for every transaction, a subset of peers is selected for fanout/reconciliation)?
For this first part of the question, we have decided to go with the latter approach:
<aside> <img src="/icons/checkmark-line_green.svg" alt="/icons/checkmark-line_green.svg" width="40px" />
choose peers to fanout to on a transaction level
</aside>
The rationale for this is to make the process more fair, otherwise, once a peer is selected for fanout, all transaction exchange would be done using fanout, even if the peer is Erlay-enabled. Also, choosing this on a connection level makes the process way more gameable: if a peer is not happy with our selection they can try to find ways to be “promoted” to reconciliation, depending on how the decision is made (e.g. imagine a naive way of choosing such as flipping a coin per connection, a peer could try to reconnect until they are selected for reconciliation) or even find another peer that picks them for reconciliation.
Given peers are chosen for fanout on a transaction level, the next natural question is: When do we pick peers for fanout?
We have two options here, either on the transaction relay schedule (when transactions are queued to be sent to peers over the next trickle 2️⃣) or on the transaction relay itself (when the INV messages are being constructed and transactions are about to be sent out).