BIP 330: Transaction announcements reconciliation #851

naumenkogs commented at 3:41 PM on October 9, 2019: member

This spec is necessary to implement higher-level efficient tx relay protocols (such as Erlay).

Submitted to mailing list in late September: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-September/017323.html

bip for erlay messages 311c085cab

bip-reconcil: Switch PD "license" to CC0

See https://github.com/bitcoin/bips/blob/master/bip-0002.mediawiki#recommended-licenses

be33606bfe

Merge pull request #1 from MarcoFalke/patch-2

bip-reconcil: Switch PD "license" to CC0

63504d9f9c

Update bip-reconcil.mediawiki

Fix mediawiki syntax for italic text

630052355d

Acknowledge suhas' contributions 0ee067c70e

minor fixes

Co-authored-by: Rusty Russel <rusty@rustcorp.com.au>

32af098957

Merge pull request #2 from MarcoFalke/patch-2

Update bip-reconcil.mediawiki

394601bb3c

in bip-reconcil.mediawiki:2 in 394601bb3c outdated

   0 | @@ -0,0 +1,297 @@
   1 | +<pre>
   2 | +  BIP: ???

luke-jr commented at 3:26 PM on November 4, 2019:

Use BIP 330

in bip-reconcil.mediawiki:5 in 394601bb3c outdated

   0 | @@ -0,0 +1,297 @@
   1 | +<pre>
   2 | +  BIP: ???
   3 | +  Layer: Peer Services
   4 | +  Title: Transaction announcements reconciliation
   5 | +  Author: Gleb Naumenko <naumenko.gs@gmail.com>, Pieter Wuille <pieter.wuille@gmail.com>

luke-jr commented at 3:27 PM on November 4, 2019:

Should be multiple lines

in bip-reconcil.mediawiki:11 in 394601bb3c outdated

   6 | +  Comments-Summary: ???
   7 | +  Comments-URI: ???
   8 | +  Status: Draft
   9 | +  Type: Standards Track
  10 | +  Created: 2010-00-00
  11 | +  License: CC0-1.0

luke-jr commented at 3:29 PM on November 4, 2019:

Suggest a separate License-Code

MarcoFalke commented at 3:37 PM on November 4, 2019:

Every other bip uses this format:

$ git grep 'License: CC0-'
bip-0079.mediawiki:  License: CC0-1.0
bip-0084.mediawiki:  License: CC0-1.0
bip-0123.mediawiki:  License: CC0-1.0
bip-0127.mediawiki:  License: CC0-1.0
bip-0135.mediawiki:  License: CC0-1.0
bip-0156.mediawiki:  License: CC0-1.0
bip-0157.mediawiki:  License: CC0-1.0
bip-0158.mediawiki:  License: CC0-1.0
bip-0178.mediawiki:  License: CC0-1.0
bip-0322.mediawiki:  License: CC0-1.0

So it seems like they should be fixed up?

luke-jr commented at 5:26 PM on November 4, 2019:

It's not a question of format. License-Code is a separate field to give included code a different license.

CC0 isn't a very good license for code. For example, to include code in Core, we would want MIT license terms.

MarcoFalke commented at 5:41 PM on November 4, 2019:

Oh, I forgot there were different license tags for the text and code

luke-jr changes_requested

luke-jr renamed this:
~~BIP for transaction reconciliation~~
BIP 330: Transaction announcements reconciliation
on Nov 4, 2019

Assigned a number, separated lines for authors, added License-Code field. aae7384c46

Merge branch 'master' of https://github.com/naumenkogs/bips

* 'master' of https://github.com/naumenkogs/bips:
  Update bip-reconcil.mediawiki

161c482f12

in bip-330.mediawiki:115 in 161c482f12 outdated

 111 | @@ -110,13 +112,13 @@ For announcing and relaying transaction outside of reconciliation, we need an un
 112 |  
 113 |  Set reconciliation primarily consists of the transmission and decoding of a reconciliation set sketch upon request.
 114 |  
 115 | -[[File:bip-reconcil/recon_scheme_merged.png|framed|center|Set reconciliation protocol flow]]
 116 | +[[File:bip-330/recon_scheme_merged.png|framed|center|Set reconciliation protocol flow]]

luke-jr commented at 6:28 PM on November 4, 2019:

Missing the leading zero

naumenkogs commented at 6:29 PM on November 4, 2019:

oops.

luke-jr commented at 6:35 PM on November 4, 2019:

Filename too

naumenkogs commented at 6:38 PM on November 4, 2019:

oh god, I should be more attentive, sorry for that.

added missing leading zero 2e7dab87ef

add trailing zero to the file name 7f9ad3ebe5

Add comments links and created date. affe5cb881

in bip-0330.mediawiki:8 in 7f9ad3ebe5 outdated

   0 | @@ -0,0 +1,299 @@
   1 | +<pre>
   2 | +  BIP: 330
   3 | +  Layer: Peer Services
   4 | +  Title: Transaction announcements reconciliation
   5 | +  Author: Gleb Naumenko <naumenko.gs@gmail.com>
   6 | +          Pieter Wuille <pieter.wuille@gmail.com>
   7 | +  Comments-Summary: ???
   8 | +  Comments-URI: ???

MarcoFalke commented at 10:02 PM on November 4, 2019:

First Comments-URI must be exactly "https://github.com/bitcoin/bips/wiki/Comments:BIP-0330" in bip-0330.mediawiki at scripts/buildtable.pl line 161, <$F> line 8.

luke-jr commented at 5:29 PM on November 5, 2019: member

Need to add to README:

|-
| [[bip-0330.mediawiki|330]]
| Peer Services
| Transaction announcements reconciliation
| Gleb Naumenko, Pieter Wuille
| Standard
| Draft

update readme 544e883488

pull[bot] referenced this in commit 96382166b0 on Nov 5, 2019

in bip-0330.mediawiki:94 in 544e883488

  89 | +    ret = 0
  90 | +    for bit in [(x >> i) & 1 for i in range(x.bit_length())]:
  91 | +        ret, y = ret ^ bit * y, mul2(y)
  92 | +    return ret
  93 | +
  94 | +def create_sketch(shortids, capacity):

ysangkok commented at 7:57 PM on November 5, 2019:

would benefit from type annotations

in bip-0330.mediawiki:264 in 544e883488

 259 | +
 260 | +Clients which do not implement this protocol remain fully compatible after this change using existing protocols, because transaction announcement reconciliation is used only for peers that negotiate support for it.
 261 | +
 262 | +==Rationale==
 263 | +
 264 | +====Why using PinSketch for set reconciliation?====

ysangkok commented at 8:03 PM on November 5, 2019:

Wouldn't "Why use" sound better here? I don't think this sentence is like the second example here.

in bip-0330.mediawiki:252 in 544e883488

 247 | +The snapshot is also used to efficiently lookup the transactions requested by short ID.
 248 | +The snapshot is cleared after the end of the reconciliation round (sending or receiving of the reconcildiff message).
 249 | +
 250 | +====q-coefficient====
 251 | +The q value should be stored to make efficient difference estimation. It is shared across peers and changed after every reconciliation.
 252 | +q-coefficient represents the discrepancy in sets: the closer the sets are, the lower optimal ''q'' is.

ysangkok commented at 8:03 PM on November 5, 2019:

why the inconsistent italics for q?

in bip-0330.mediawiki:282 in 544e883488

 277 | +To avoid problems caused by the delays in the network, our protocol requires extra round of announcing unsalted transaction IDs. [https://arxiv.org/pdf/1905.10518.pdf Erlay] protocol on top of this work also requires announcing unsalted transaction IDs for flooding. 
 278 | +Both of these measures allow to deduplicate transaction announcements across the peers.
 279 | +However, using full 256-bit IDs to uniquely identify transactions seems to be an overkill.
 280 | +128 is the highest power of 2 which provides good enough collision-resistance in an adversarial model, and trivially saves a significant portion of the bandwidth related to these announcements.
 281 | +
 282 | +====Why using bisection instead of extending the sketch?====

ysangkok commented at 8:03 PM on November 5, 2019:

again, I suggest "use" instead of "using"

in bip-0330.mediawiki:245 in 544e883488

 240 | +Every node stores a set of 128-bit truncated IDs for every peer which supports transaction reconciliation, representing the transactions which would have been sent according to the regular flooding protocol.
 241 | +Incoming transactions are added to sets when those transactions are received (if they satisfy the policies such as minimum fee set by a peer).
 242 | +A reconciliation set is moved to the corresponding set snapshot after the transmission of the initial sketch.
 243 | +
 244 | +====Reconciliation set snapshot====
 245 | +After the transmitting of the initial sketch (either sending or receiving of reconcildiff message), every node should store the snapshot of the current reconciliation set, and clear the set.

ysangkok commented at 8:06 PM on November 5, 2019:

I suggest inserting a "the" before "message" in "sending or receiving of reconcildiff message". I suggest "After transmitting the initial sketch" instead of "After the transmitting of the initial sketch".

in bip-0330.mediawiki:67 in 544e883488

  62 | +* Let ''k<sub>0</sub>'' be the 64-bit integer obtained by interpreting the first 8 bytes of ''h'' in little-endian byte order.
  63 | +* Let ''k<sub>1</sub>'' be the 64-bit integer obtained by interpreting the second 8 bytes of ''h'' in little-endian byte order.
  64 | +* Let ''s = SipHash-2-4((k<sub>0</sub>,k<sub>1</sub>),wtxid)'', where ''wtxid'' is the transaction hash including witness data as defined by BIP141.
  65 | +* The short ID is equal to ''1 + (s mod 0xFFFFFFFF)''.
  66 | +
  67 | +This results in approximately uniformly distributed IDs in the range ''[1..0xFFFFFFFF]'', which is a requirement for using them as elements in 32-bit sketches. See the next paragraph for details.

ysangkok commented at 8:07 PM on November 5, 2019:

would be clearer if it was specified whether the range is inclusive or not

naumenkogs commented at 9:28 PM on November 21, 2020:

brackets [] usually mean inclusive?

in bip-0330.mediawiki:177 in 544e883488

 172 | +The sketch message is used to communicate a sketch required to perform set reconciliation.
 173 | +
 174 | +{|class="wikitable"
 175 | +! Data type !! Name !! Description
 176 | +|-
 177 | +| byte[] || skdata || The sketch of the sender's reconciliation snapshot

ysangkok commented at 8:08 PM on November 5, 2019:

I suggest using code formatting for data types like byte[]. Many sans-serif fonts make [] look like a box.

in bip-0330.mediawiki:201 in 544e883488

 196 | +{|class="wikitable"
 197 | +! Data type !! Name !! Description
 198 | +|-
 199 | +| uint8 || success || Indicates whether sender of the message succeeded at set difference decoding.
 200 | +|-
 201 | +| uint32[] || ask_shortids || The short IDs that the sender did not have.

ysangkok commented at 8:08 PM on November 5, 2019:

Again, I prefer code formatting for data types.

in bip-0330.mediawiki:218 in 544e883488

 213 | +The invtx message is used to announce transactions (both along with reconcildiff message and as a response to the reconcildiff message). It is the truncated ID analogue of "inv" (which cannot be used because it has 256-bit elements).
 214 | +
 215 | +{|class="wikitable"
 216 | +! Data type !! Name !! Description
 217 | +|-
 218 | +| uint128[] || inv_truncids || The truncated IDs of transactions the sender believes the receiver does not have.

ysangkok commented at 8:09 PM on November 5, 2019:

Again, I prefer code formatting for data types.

in bip-0330.mediawiki:230 in 544e883488

 225 | +The gettx message is used to request transactions by 128-bit truncated IDs. It is the truncated ID analogue of "getdata".
 226 | +
 227 | +{|class="wikitable"
 228 | +! Data type !! Name !! Description
 229 | +|-
 230 | +| uint128[] || ask_truncids || The truncated IDs of transactions the sender wants the full transaction data for.

ysangkok commented at 8:09 PM on November 5, 2019:

Again, I prefer code formatting for data types.

in bip-0330.mediawiki:272 in 544e883488

 267 | +PinSketch is as bandwidth efficient as CPISync, but PinSketch has quadratic decoding complexity, while CPISync have cubic decoding complexity. This makes PinSketch significantly faster.
 268 | +
 269 | +====Why using 32-bit short transaction IDs?====
 270 | +
 271 | +To use Minisketch in practice, transaction IDs should be shortened (ideally, not more than 64 bits per element).
 272 | +Small number of bits per transaction also allows to save extra bandwidth and make operations over sketches faster.

ysangkok commented at 8:11 PM on November 5, 2019:

Should be "A small number of bits" instead of "Small number of bits". "Allows to" is clumsy, I prefer "allows saving" instead of "allows to save"

in bip-0330.mediawiki:285 in 544e883488

 280 | +128 is the highest power of 2 which provides good enough collision-resistance in an adversarial model, and trivially saves a significant portion of the bandwidth related to these announcements.
 281 | +
 282 | +====Why using bisection instead of extending the sketch?====
 283 | +
 284 | +Unlike extended sketches, bisection does not require operating over sketches of higher order.
 285 | +This allows to avoid the high computational cost caused by quadratic decoding complexity.

ysangkok commented at 8:12 PM on November 5, 2019:

Ditto, "allows to avoid" should be avoided and replaced with "allows avoiding".

ysangkok changes_requested

luke-jr commented at 9:28 PM on November 5, 2019: member

This is merged, but GitHub messed up detecting it..

luke-jr closed this on Nov 5, 2019

shesek commented at 10:23 PM on November 19, 2019: none

Shouldn't the exchanged salts also be mentioned under the local state section?

Also, I'm not sure if this fits in the BIP format, but it might be worth mentioning the additional steps needed to make Erlay happen after this is implemented.

naumenkogs commented at 10:50 PM on November 19, 2019: member

Shouldn't the exchanged salts also be mentioned under the local state section?

Yes indeed. Feel free to send a PR, otherwise I'll probably get to it in couple days :)

Also, I'm not sure if this fits in the BIP format, but it might be worth mentioning the additional steps needed to make Erlay happen after this is implemented.

I'm not sure either. It shouldn't be as difficult as, say, utreexo, but the deployment is still not trivial.