Transaction relay in Bitcoin is currently a simple scheme, any node announces transactions to every peer in its list, in turn every peer announces it to its peers and so on until the whole network is updated. This is simple but not bandwidth efficient as a transaction can reach one node multiple times through multiple peers, this ensures that there is no single point of failure but is highly inefficient.

Currently any node with 8 connections would be using about 18GB of bandwidth per month, if we increase the amount of peers, further enhancing security, we increase the usage, which would discourage some users from owning a node, according to a new research paper almost 44% of all bandwidth used is redundant.

That’s why a group of Bitcoin developers and researchers created Erlay, an efficient transaction relay protocol for Bitcoin, in simple terms the protocol works by optimizing the transaction relay while maintaining the security aspects, it reduces propagated information by using an efficient set of reconciliation method, it is also designed to withstand attacks like denial of service and timing.

To create a protocol for transaction relays a few requirements must be achieved:

• It needs to scale with number of connections as more connections mean better security for the network.
• Maintaining a network topology suited for a decentralized environment, the network’s topology must remain unstructured and the routing decision needs to happen independantly in every node to protect the network against censorship and partitioning.
• Maintaining a reasonable latency to allow for a smooth user experience.
• Robust to the same set of attacks the original protocol is.

Erlay consists of two main parts, low-fanout flooding and set reconciliation. Low-fanout flooding is like how Bitcoin currently works, except instead of a node sending the transaction to its entire list of peers, it chooses only a subset of peers to send this transaction too, but this alone doesn’t guarantee that every node on the network receives the transaction, what if my node was consistently not chosen as part of the subset that receive a transaction?

That’s where set reconciliation comes in to play, using set reconciliation a node in a P2P network periodically compares its local state with its peer’s, if it finds missing necessary information it sends a request for that information. The challenge here is how to efficiently compute which transactions are missing.

The reconciliation algorithm proposed uses something called a set sketch, a set sketch is a type of checksum with two distinct properties

• By XOring the bit representation of two sketches you can obtain all the elements that occur in one but not both sketches.
• As long as the sketches do not exceed a predetermined capacity, it is possible to recover the entire set from the sketch by decoding the sketch.

So for an example, nodes of Alice and Bob want to make sure they both have the same set of transactions, they both calculate a sketch of their sets and Alice sends the sketch to Bob, using XOring Bob obtains the set of transactions that exist in only one but not both sets, Bob then tries to recovers the transactions he doesn’t have and sends to Alice a list of transactions she doesn’t have.

Erlay researches simulated their protocol to demonstrate the latency, bandwidth usage and security and their results were fascinating, announcement bandwidth in Erlay is just 12.8% of the relay bandwidth, while it was about 47.6% for the original protocol. But this doesn’t come without a cost, Erlay’s latency was found to be almost at a constant overhead of 2.6 seconds more than the original protocol, this latency can be reduced at a higher bandwidth cost using a tunable parameter.

Erlay could be a promising addition to Bitcoin, it could lead to more people operating nodes as it heavily decreases the amount of data needed to operate one, it allows nodes to have higher connectivity leading to better security but at a latency cost. Erlay researchers are actively working on introducing it to Bitcoin Core’s node software.

References

• Discussion
• Paper