{"type":"rich","version":"1.0","author_name":"npub1zw7cc8z78v6s3grujfvcv3ckpvg6kr0w7nz9yzvwyglyg0qu5sjsqhkhpx","author_url":"https://nostr.ae/npub1zw7cc8z78v6s3grujfvcv3ckpvg6kr0w7nz9yzvwyglyg0qu5sjsqhkhpx","provider_name":"njump","provider_url":"https://nostr.ae","html":"📅 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."}