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

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

[Gleb Naumenko]

[-- Attachment #1: Type: text/plain, Size: 1979 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 2462 bytes --]

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

[Rusty Russell]

Hi Gleb,

        Minor feedback on reading the draft:

> sendrecon:
> uint32 	version 	Must be exactly 1 currently.

At risk of quoting myself[1]: data doesn't have requirements.  Actors do.
In this case, I assume you mean "writers must set this to 1".  What do
readers do if it's not?

> reqreconcil
> uint8 	q 	Coefficient used to estimate set difference.

You describe how to calculate q (as a floating point value), but not how
to encode it?

> Every node stores sets of 128-bit truncated IDs per every peer

"*a* set..." or is it "two sets" (if you include the snapshot?).

And " *for* every peer" (maybe "which supports tx reconciliation?")

> To the best of our knowledge, PinSketch is more bandwidth efficient
> than IBLT, especially for the small differences in sets we expect to
> operate over.

Remove "To the best of our knowledge, ": that makes it sound like it's
up for debate.  I've implemented and experimented with IBLT, and it's
worse.

Cheers,
Rusty.

[1] https://github.com/lightningnetwork/lightning-rfc/blob/master/CONTRIBUTING.md#writing-the-requirements