Erlay: Bandwidth-Efficient Transaction Relay in Bitcoin

Paper by G. Naumenko, G. Maxwell, P. Wuille

Abstract:

Bitcoin is a top-ranked cryptocurrency that has experienced huge growth and survived numerous attacks. The protocols making up Bitcoin must therefore accommodate the growth of the network and ensure security.

Security of the Bitcoin network depends on connectivity be- tween the nodes. Higher connectivity yields better security. In this paper we make two observations: (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, mak- ing it prohibitively expensive to operate a Bitcoin node. Half of the total bandwidth needed to operate a Bitcoin node is currently used to just announce transactions. Unlike block relay, transaction dissemination has received little attention in prior work.

We propose a new transaction dissemination protocol, Erlay, that not only reduces the bandwidth consumption by 40% assum- ing current connectivity, but also keeps the bandwidth use almost constant as the connectivity increases. In contrast, the existing protocol increases the bandwidth consumption linearly with the number of connections. By allowing more connections at a small cost, Erlay improves the security of the Bitcoin network. And, as we demonstrate, Erlay also hardens the network against attacks that attempt to learn the origin node of a transaction. Erlay is currently being investigated by the Bitcoin community for future use with the Bitcoin protocol.

Resources

Paper: https://arxiv.org/pdf/1905.10518.pdf
Issue opened in Grin: https://github.com/mimblewimble/grin/issues/2857

6 Likes

We looked briefly into “set reconciliation” when thinking about aggregate txs and how to deaggregate them during propagation (we deaggregate to reduce the effect of malicious/conflicting aggregation). Each aggregate tx can be thought of as a set of kernels (with an accompanying set of inputs/outputs and an offset), single kernel txs are just a simple case of this.

The whole tx pool (and stempool) can be thought of as a single aggregate tx also.
And “set reconciliation” there would operate in effectively the same way (everything in Grin looks like a set of tx kernels).

Would be good to take another look at minisketch and the new Erlay proposal.
I’m pretty sure it would be a good fit for Grin/MW and actually be simpler in a lot of ways due to how we represent txs/blocks/txpool in Grin.

3 Likes

Here is my Rust bindings for minisketch: minisketch-rs
And my WIP simulator of Erlay: actix-erlay-sim

1 Like

Looking over the paper, it doesn’t look like Erlay was tested on low-traffic environments. Grin has averaged 0.05 tx/s since its launch. Would it still consume less bandwidth than a flooding strategy on such a network?

Grin has averaged 0.05 tx/s since its launch. Would it still consume less bandwidth than a flooding strategy on such a network?

Not sure. I would imagine that part of the motivation for introducing such a protocol, i.e. to make it more efficient to run a node and therefore improving the security of the network, becomes more useful once there’s more network activity.

In the meanwhile, we might be inspired by some of the approaches in Erlay and let that instruct other work we do, in Dandelion for instance.

1 Like

Talk at scaling bitcoin:

Draft BIP Posted to the bitcoin mailing list:

We are opening for review a draft of the new BIP, which describes low-level specifications for the reconciliation-based transaction announcement protocol.

https://github.com/naumenkogs/bips/blob/bip-reconcil/bip-reconcil.mediawiki

Agreeing on this spec would enable integration of more bandwidth-efficient relay protocols, like Erlay (https://arxiv.org/abs/1905.10518).

The draft has all the background necessary to understand the work, so please read and review.
It introduces salted short transaction IDs (required to do reconciliation efficiently) and demonstrates how to compute sketches based on these IDs (including simple python scripts).
It also introduces wtxid-based truncated transaction IDs (to trivially save significant fraction of the bandwidth).
Finally, it specifies all the messages to be used by an efficient reconciliation-based protocol, and new state variables required for the protocol.

Please note that, comparing to the Erlay paper, we decided to add extra round, where 2 parties explicitly map 32-bit short IDs to 128-bit truncated IDs, because otherwise peers which take >1s to reconcile would cause transmitting duplicate transactions (extra bandwidth), and we cannot assume <1s latency in Bitcoin, especially over Tor.
According to my estimates, the bandwidth overhead due to the measure from the BIP (extra communication round) is only extra 10% comparing to the original Erlay estimates.

It is possible that we missed some of the state variables required to handle corner cases of the protocol, because the spec is based on my prototype code, and it might evolve when we will be building an actual production-ready implementation.

Overall, I believe that this spec is ready for review.

Even though this work does not require a fork, the change is quite significant, and peer-review is critical for the system, so please take a look. Feel free to reach out for questions and comments here or directly over email.

– gleb

1 Like