Erlay is an alternative method of announcing transactions between peers in the Bitcoin P2P network. The main goal of Erlay is to reduce the 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 transaction, 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 on regular intervals. Once 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 send 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 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️⃣.
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 in 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 matter: in Bitcoin Core, inbound connections are not trusted 1️⃣, 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 peers 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 amount 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 main rationale for this is making 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 peers 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 mainly have two options here, either on transaction relay schedule (when transactions are queue to be sent to peers over then next trickle 2️⃣) or on transaction relay itself (when the INV messages are being constructed and transactions are about to be sent out).