Erlay: A new Bitcoin transaction relay protocol

Erlay is a brand new type of transaction dissemination protocol that aims to significantly reduce the bandwidth required to connect Bitcoin nodes.
According to research conducted by Gleb Naumenko and other crypto-experts like Gregory Maxwell and Peter Wuille, Erlay could reduce the amount of bandwidth required to maintain current levels of connectivity between Bitcoin nodes by about 40%.

The current protocol and the resources problem

One of the most pressing issues regarding Bitcoin’s node connectivity is the fact it takes large amounts of bandwidth to keep the connection open with all other nodes given the decentralised and open nature of the protocol.
As described in the research paper’s abstract: “The security of the Bitcoin network depends on connectivity between the nodes. That means that higher connectivity yields better security.”
The main observations by the authors were:

1. Current connectivity in the Bitcoin network is too low for optimal security.
2. At the same time, increasing connectivity will substantially increase the bandwidth used by the transaction dissemination protocol.

In essence, increasing connectivity between nodes would essentially make it prohibitively expensive to operate a Bitcoin node. Another key point made by the authors is that “half of the total bandwidth needed to operate a Bitcoin node is currently used to just announce transactions”.
By focusing on the transaction dissemination process, the authors recommend an approach that will transmit transaction identifiers more efficiently, thereby reducing the number of messages sent between nodes while supporting the transmission of new transactions to all nodes at the same time.
Currently, nodes share transaction IDs even with peers that have already been sent the transaction. This means there are a great deal of redundant messages being shared on the Bitcoin network.
Arguably, 50% of the bandwidth required to run a Bitcoin node is presently used for announcing transactions. Another 45% of bandwidth is needed for relaying the actual transaction body and only 5% is needed for various other messages, like block header information for instance.
The Erlay research paper estimates that 44% of all traffic between Bitcoin nodes consists of redundant messages.
The conclusion is that there is great room for improvement.

Erlay’s Minisketch – an elegant solution

The Erlay protocol reduces the number of messages passed between Bitcoin nodes using a solution called “Minisketch”, which was previously proposed by Naumenko, Wuille, and Maxwell. In addition to transaction IDs, Bitcoin nodes share “sketches” of transactions with one another.
As explained on the Bitcoin-Dev forum:

“The main idea is that instead of announcing every transaction to every peer, announcements are only sent directly over a small number of connections (only eight outgoing ones). Further relay is achieved by periodically running a set reconciliation protocol over every connection between the sets of withheld announcements in both directions.
“The set reconciliation protocol uses error correcting codes to communicate a set of transactions to a peer with an unknown but similar set using bandwidth only equal to the size of the difference and not the size of the sets themselves.
“Results: we save half of the bandwidth a node consumes, allowing for increased connectivity almost for free – and, as a side effect, Bitcoin can better withstand timing attacks.”

The idea of sketches is to have a data packet that contains identifiers for all of the transactions that a node has accepted (since the last reconciliation) but in compact form. Using the sketches, a node can figure out which transactions it doesn’t have that its peers do have. Afterwards, it can request only those transactions from those peers that don’t appear in their sketch.
This approach consumes far less bandwidth than sharing all of the transaction IDs.
If this new proposal gets implemented, we could see a huge incentive for Bitcoin enthusiasts to run full nodes.