Erlay: Efficienttransaction relay
Gleb Naumenko, Greg Maxwell, PieterWuille, Sasha Fedorova, Ivan BeschastnikhBitcoin p2p network (is redundant)
Ultimately, the network is used
to relay transactions.

By default, every node connects
to 8 reachable peers.

Bitcoin p2p network (is redundant)
Ultimately, the network is used
to relay transactions.

By default, every node connects
to 8 reachable peers.

Currently, transactions arerelayed by ﬂooding.

Lifecycle of a Bitcoin transaction

Lifecycle of a Bitcoin transactionProperties of transaction relay- Bandwidth- Latency- Privacy and security

Current protocol (BTCFlood)- Bandwidth: 18 GB/month- Latency: 3.15s to reach all nodes- Privacy and security

Current protocol (BTCFlood)- Bandwidth: 18 GB/month- Latency: 3.15s to reach all nodes- Privacy and security

Current protocol (BTCFlood)
This protocol avoids relaying a fulltransaction when it is not needed.

●

Full transaction is ~250 bytes●

Announcement is 32 bytes

Transaction relay protocol
This protocol avoids relaying a fulltransaction when it is not needed.

●

Full transaction is ~250 bytes●

Announcement is 32 bytes

Announcements are still redundant.
More than 85% announcements are“duplicate”

Transaction relay protocol
This protocol avoids relaying a fulltransaction when it is not needed.

●Full transaction is ~250 bytes●Announcement is 32 bytes

Announcements are still redundant.
More than 85% announcements are“duplicate”

Due to the redundancy (8 connections)
Peer 2 may receive this INV 8 times.

But how bad is that?
Ideally, for every node it is 1 INV, 1 GETDATA and 1 TX message per transaction

But how bad is that?
Ideally, for every node it is 1 INV, 1 GETDATA and 1 TX message per transaction

But how bad is that?
Ideally, for every node it is 1 INV, 1 GETDATA and 1 TX message per transaction

This result assumes 8 connections

We should increase the connectivity
Makes harder to:- isolate a node from the network (Eclipsing)- deanonymize transactions (link tx to the IP-address of the node)- Infer the topology of the networkBut if we increase the connectivity...

Prior work
- Block relay protocols: Compact Blocks, Graphene, XThin,bloxroute (different requirements and goals)- Topology-based routing policies: Freenet, Efa, Chord, Pastry(non-Byzantine)- Feedback-based approaches (leak information)

Erlay: Eﬃcient transaction relay

Erlay: Eﬃcient transaction relay

Erlay: Eﬃcient transaction relay
1. Rapid ﬂooding across well-connected public (reachable) nodes
2. Every node keeps a reconciliation set for every its peer
3. Include transactions would have been broadcasted throughﬂooding to a given peer in the respective set
4. Use Minisketch for efﬁcient set reconciliation

Erlay: Eﬃcient transaction relay

Transaction reconciliation to bridge gaps
The goal of set reconciliation is for each A and B computeset difference with minimum communication.

22

Transaction reconciliation to bridge gaps
The goal of set reconciliation is for each A and B computeset difference with minimum communication.

It helps not only to exchange missing transactions, but also to make sure you
share the rest of the state.

23

Transaction reconciliation

Node A knows about tx #1* A, B, C, D are connected24Transaction reconciliation

Every node maintains a set oftransactions it would have sent toevery peer

Nodes A, B know about tx #1* A, B, C, D are connected25

Transaction reconciliation

Every node maintains a set oftransactions it would have sent toevery peer

Nodes A, B know about tx #1
Node D knows about tx #2* A, B, C, D are connected26

Transaction reconciliation

Nodes A, B know about tx #1
Node D knows about tx #2* A, B, C, D are connected27

Transaction reconciliation

During reconciliation, 2 nodes
synchronize according to their localsets

Nodes A, B know about tx #1
Node D knows about tx #2* A, B, C, D are connected28

Transaction reconciliation

During reconciliation, 2 nodes
synchronize according to their local
sets.
After reconciliation those sets arecleared.
Nodes A, B, D know about tx #1
Node B, D knows about tx #2* A, B, C, D are connected29

Transaction reconciliation

During reconciliation, 2 nodes
synchronize according to their local
sets.
After reconciliation those sets arecleared.
Nodes A, B, D know about tx #1
Node B, D knows about tx #2* A, B, C, D are connected30

Finding set diﬀerence with BCH codes

Bob and Alice never communicated before,
but they think they share most of thetransactions and want to help each other31

Finding set diﬀerence with BCH codes

Bob and Alice never communicated before,
but they think they share most of thetransactions and want to help each other

It turns out that If a transaction ID is 32 bytes, we have to send just 32*2 bytes toﬁnd the diﬀerence in these sets

32

Finding set diﬀerence with BCH codes
1.

Alice estimates diff set size

2.

Alice computes a sketch of her set

3.

Alice sends the sketch to Bob

4.

Bob computes his sketch

5.

Bob XORs sketches6.

Bob can ﬁnd Tx #10 and Tx #15

33

Minisketch: Computing a BCH sketch* N — assumed max diﬀerence size
34

Minisketch (PinSketch implementation) benchmark

35

Minisketch (PinSketch implementation) benchmark

36Erlay bandwidth benchmark. Simulation

37

Minisketch (PinSketch implementation) benchmark

38

Erlay latency benchmark. Simulation
Time it takes for aprotocol to relay
across all nodes

39

Does latency increase matter?
Transaction relay latency increase might potentially
increase stale block rate, bad for the security of the network

40

Does latency increase matter?
Transaction relay latency increase might potentially
increase stale block rate, bad for the security of the network.

Because of the faster relay across public nodes, stale block rate with Erlayis actually lower!

Good for the security of the network.

41

Erlay benchmark. Prototype
100 Azure machines
running Bitcoin Coresoftware and relaying
500 transactions

42

Various
conﬁgurations ofthe Erlay-likeprotocols

43Erlay: Eﬃcienttransaction relay
Pros:- Saves ~40% bandwidth for every node
- Allows to increase connectivity for free
- Stronger privacy (ﬁrst-spy estimator)

Cons (not really):- Minor latency increaseErlay: Eﬃcienttransaction relay
Gleb Naumenko, Greg Maxwell,
Pieter Wuille, Sasha Fedorova, Ivan
Beschastnikh
Full paper:https://arxiv.org/abs/1905.10518

Email: naumenko.gs@gmail.com
Twitter/Telegram @tomatodread
Bitcoin-IRC: gleb