📅 Original date posted:2016-05-10
📝 Original message:Pieter Wuille via bitcoin-dev <bitcoin-dev at lists.linuxfoundation.org> writes:
> On 05/03/2016 12:13 AM, lf-lists at mattcorallo.com (Matt Corallo) wrote:
>> Hi all,
>>
>> The following is a BIP-formatted design spec for compact block relay
>> designed to limit on wire bytes during block relay. You can find the
>> latest version of this document at
>> https://github.com/TheBlueMatt/bips/blob/master/bip-TODO.mediawiki.
>
> Hi Matt,
>
> thank you for working on this!
Indeed! Sorry for the delayed feedback.
>> |shortids||List of uint64_ts||8*shortids_length bytes||Little
>> Endian||The short transaction IDs calculated from the transactions which
>> were not provided explicitly in prefilledtxn
>
> I tried to derive what length of short ids is actually necessary (some
> write-up is on
> https://gist.github.com/sipa/b2eb2e486156b5509ac711edd16153ed but it's
> incomplete).
I did this for IBLT testing.
I used variable-length bit encodings, and used the shortest encoding
which is unique to you (including mempool). It's a little more work,
but for an average node transmitting a block with 1300 txs and another
~3000 in the mempool, you expect about 12 bits per transaction. IOW,
about 1/5 of your current size. Critically, we might be able to fit in
two or three TCP packets.
The wire encoding of all those bit arrays was:
[varint-min-numbits] - Shortest bit array length
[varint-array-size] - Number of bit arrays.
[varint-num].... - Number of entries in array N (x varint-array-size)
[packed-bit-arrays...]
Last byte was padded with zeros.
See: https://github.com/rustyrussell/bitcoin-iblt/blob/master/wire_encode.cpp#L12
I would also avoid the nonce to save recalculating for each node, and
instead define an id as:
[<64-bit-short-id>][txid]
Since you only ever send as many bits as needed to distinguish, this only
makes a difference if there actually are collisions.
As Peter R points out, we could later enhance receiver to brute force
collisions (you could speed that by sending a XOR of all the txids, but
really if there are more than a few collisions, give up).
And a prototype could just always send 64-bit ids to start.
Cheers,
Rusty.
Rusty Russell [ARCHIVE] /
npub1zw…hkhpx
2023-06-07 17:50:21
in reply to nevent1q…ctmc
Author Public Key
npub1zw7cc8z78v6s3grujfvcv3ckpvg6kr0w7nz9yzvwyglyg0qu5sjsqhkhpxPublished at
2023-06-07 17:50:21Event JSON
{
"id": "1cdc415e8ef0c84672a3aa26d1ff1fc475204e1d4a0074405cc2af54d8334ee5",
"pubkey": "13bd8c1c5e3b3508a07c92598647160b11ab0deef4c452098e223e443c1ca425",
"created_at": 1686160221,
"kind": 1,
"tags": [
[
"e",
"37fe3d2b857e9599a14c87e34f77dee62e90bb6721200fbd7752c60823834c1e",
"",
"root"
],
[
"e",
"db809d35316f488d3e04c6e21cca1884b63857109f1c60e4e0f8cc903f9a3473",
"",
"reply"
],
[
"p",
"6185f02289f12c01c6f7c80cdc0331a01eae9c6356f228be12efdb7fb395bc19"
]
],
"content": "📅 Original date posted:2016-05-10\n📝 Original message:Pieter Wuille via bitcoin-dev \u003cbitcoin-dev at lists.linuxfoundation.org\u003e writes:\n\u003e On 05/03/2016 12:13 AM, lf-lists at mattcorallo.com (Matt Corallo) wrote:\n\u003e\u003e Hi all,\n\u003e\u003e \n\u003e\u003e The following is a BIP-formatted design spec for compact block relay\n\u003e\u003e designed to limit on wire bytes during block relay. You can find the\n\u003e\u003e latest version of this document at\n\u003e\u003e https://github.com/TheBlueMatt/bips/blob/master/bip-TODO.mediawiki.\n\u003e\n\u003e Hi Matt,\n\u003e\n\u003e thank you for working on this!\n\nIndeed! Sorry for the delayed feedback.\n\n\u003e\u003e |shortids||List of uint64_ts||8*shortids_length bytes||Little\n\u003e\u003e Endian||The short transaction IDs calculated from the transactions which\n\u003e\u003e were not provided explicitly in prefilledtxn\n\u003e\n\u003e I tried to derive what length of short ids is actually necessary (some\n\u003e write-up is on\n\u003e https://gist.github.com/sipa/b2eb2e486156b5509ac711edd16153ed but it's\n\u003e incomplete).\n\nI did this for IBLT testing.\n\nI used variable-length bit encodings, and used the shortest encoding\nwhich is unique to you (including mempool). It's a little more work,\nbut for an average node transmitting a block with 1300 txs and another\n~3000 in the mempool, you expect about 12 bits per transaction. IOW,\nabout 1/5 of your current size. Critically, we might be able to fit in\ntwo or three TCP packets.\n\nThe wire encoding of all those bit arrays was:\n [varint-min-numbits] - Shortest bit array length\n [varint-array-size] - Number of bit arrays.\n [varint-num].... - Number of entries in array N (x varint-array-size)\n [packed-bit-arrays...]\n\n Last byte was padded with zeros.\n See: https://github.com/rustyrussell/bitcoin-iblt/blob/master/wire_encode.cpp#L12\n\nI would also avoid the nonce to save recalculating for each node, and\ninstead define an id as:\n\n [\u003c64-bit-short-id\u003e][txid]\n\nSince you only ever send as many bits as needed to distinguish, this only\nmakes a difference if there actually are collisions.\n\nAs Peter R points out, we could later enhance receiver to brute force\ncollisions (you could speed that by sending a XOR of all the txids, but\nreally if there are more than a few collisions, give up).\n\nAnd a prototype could just always send 64-bit ids to start.\n\nCheers,\nRusty.",
"sig": "de3913bdbfbb65aeca81a866d1c2c7f9d2f47c9ae2f366521bb06f5ae9bdeb72f46aec750ce1fe0988bdfb2eef57e7f36d15e88349eadb36fce8e6df6abf876c"
}