Subject: [bitcoin-dev] New BIP for p2p messages/state enabling reconciliation-based protocols (Erlay)

From: Gleb Naumenko <[email-masked]>
Date: Wed, 25 Sep 2019 14:28:00 +0300

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