{"type":"rich","version":"1.0","author_name":"npub1e46n428mcyfwznl7nlsf6d3s7rhlwm9x3cmkuqzt3emmdpadmkaqqjxmcu","author_url":"https://nostr.ae/npub1e46n428mcyfwznl7nlsf6d3s7rhlwm9x3cmkuqzt3emmdpadmkaqqjxmcu","provider_name":"njump","provider_url":"https://nostr.ae","html":"📅 Original date posted:2016-05-17\n📝 Original message:Implemented a few of your suggestions.\n\nAlso opened a formal pull request for the BIP at\nhttps://github.com/bitcoin/bips/pull/389 and the code at\nhttps://github.com/bitcoin/bitcoin/pull/8068.\n\nOn 05/09/16 17:06, Pieter Wuille via bitcoin-dev wrote:\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\u003e \n\u003e\u003e ===New data structures===\n\u003e\u003e Several new data structures are added to the P2P network to relay\n\u003e\u003e compact blocks: PrefilledTransaction, HeaderAndShortIDs,\n\u003e\u003e BlockTransactionsRequest, and BlockTransactions. Additionally, we\n\u003e\u003e introduce a new variable-length integer encoding for use in these data\n\u003e\u003e structures.\n\u003e\u003e\n\u003e\u003e For the purposes of this section, CompactSize refers to the\n\u003e\u003e variable-length integer encoding used across the existing P2P protocol\n\u003e\u003e to encode array lengths, among other things, in 1, 3, 5 or 9 bytes.\n\u003e \n\u003e This is a not, but I think it's a bit strange to have two separate\n\u003e variable length integers in the same specification. I understand is one\n\u003e is already the default for variable-length integers currently, and there\n\u003e are reasons to use the other one for efficiency reasons in some places,\n\u003e but perhaps we should aim to get everything using the latter?\n\nFixed, the whole thing now uses New Varints.\n\n\u003e\u003e ====New VarInt====\n\u003e\u003e Variable-length integers: bytes are a MSB base-128 encoding of the number.\n\u003e\u003e The high bit in each byte signifies whether another digit follows. To make\n\u003e\u003e sure the encoding is one-to-one, one is subtracted from all but the last\n\u003e\u003e digit.\n\u003e \n\u003e Maybe it's worth mentioning that it is based on ASN.1 BER's compressed\n\u003e integer format (see\n\u003e https://www.itu.int/ITU-T/studygroups/com17/languages/X.690-0207.pdf\n\u003e section 8.1.3.5), though with a small modification to make every integer\n\u003e have a single unique encoding.\n\u003e \n\u003e\u003e ====HeaderAndShortIDs====\n\u003e\u003e A HeaderAndShortIDs structure is used to relay a block header, the short\n\u003e\u003e transactions IDs used for matching already-available transactions, and a\n\u003e\u003e select few transactions which we expect a peer may be missing.\n\u003e\u003e\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\u003e \n\u003e For any reasonable numbers I can come up with (in a very wide range),\n\u003e the number of bits needed is very well approximated by:\n\u003e \n\u003e   log2(#receiver_mempool_txn * #block_txn_not_in_receiver_mempool /\n\u003e acceptable_per_block_failure_rate)\n\u003e \n\u003e For example, with 20000 mempool transactions, 2500 transactions in a\n\u003e block, 95% hitrate, and a chance of 1 in 10000 blocks to fail to\n\u003e reconstruct, needed_bits = log2(20000 * 2500 * (1 - 0.95) / 0.0001) =\n\u003e 34.54, or 5 byte txids would suffice.\n\u003e \n\u003e Note that 1 in 10000 failures may sound like a lot, but this is for each\n\u003e individual connection, and since every transmission uses separately\n\u003e salted identifiers, occasional failures should not affect global\n\u003e propagation. Given that transmission failures due to timeouts, network\n\u003e connectivity, ... already occur much more frequently than once every few\n\u003e gigabytes (what 10000 blocks corresponds to), that's probably already\n\u003e more than enough.\n\u003e \n\u003e In short: I believe 5 or 6 byte txids should be enough, but perhaps it\n\u003e makes sense to allow the sender to choose (so he can weigh trying\n\u003e multiple nonces against increasing the short txid length).\n\nI switched to 6-byte short txids.\n\n\u003e\u003e ====Short transaction IDs====\n\u003e\u003e Short transaction IDs are used to represent a transaction without\n\u003e\u003e sending a full 256-bit hash. They are calculated by:\n\u003e\u003e # single-SHA256 hashing the block header with the nonce appended (in\n\u003e\u003e little-endian)\n\u003e\u003e # XORing each 8-byte chunk of the double-SHA256 transaction hash with\n\u003e\u003e each corresponding 8-byte chunk of the hash from the previous step\n\u003e\u003e # Adding each of the XORed 8-byte chunks together (in little-endian)\n\u003e\u003e iteratively to find the short transaction ID\n\u003e \n\u003e An alternative would be using SipHash-1-3 (a form of SipHash with\n\u003e reduced iteration counts; the default is SipHash-2-4). SipHash was\n\u003e designed as a Message Authentication Code, where the security\n\u003e requirements are much stronger than in our case (in particular, we don't\n\u003e care about observers being able to finding the key, as the key is just\n\u003e public knowledge here). One of the designers of SipHash has commented\n\u003e that SipHash-1-3 for collision resistance in hash tables may be enough:\n\u003e https://github.com/rust-lang/rust/issues/29754#issuecomment-156073946\n\u003e \n\u003e Using SipHash-1-3 on modern hardware would take ~32 CPU cycles per txid.\n\nSwitched to SipHash2-4.\n\n\u003e\u003e ===Implementation Notes===\n\u003e \n\u003e There are a few more heuristics that MAY be used to improve performance:\n\u003e \n\u003e * Receivers should treat short txids in blocks that match multiple\n\u003e mempool transactions as non-matches, and request the transactions. This\n\u003e significantly reduces the failure to reconstruct.\n\nDone.\n\n\u003e * When constructing a compact block to send, the sender can verify it\n\u003e against its own mempool to check for collisions, and if so, choose to\n\u003e either try another nonce, or increase the short txid length.\n\nAdditionally we should compare to the orphan pool (which apparently\nhelps a lot)."}