{"type":"rich","version":"1.0","author_name":"npub1lwrwp8dzn9x5nqc7d735e0nuwxh0nyz5ezkfpjzr332efdxw9asq4z8zjm","author_url":"https://nostr.ae/npub1lwrwp8dzn9x5nqc7d735e0nuwxh0nyz5ezkfpjzr332efdxw9asq4z8zjm","provider_name":"njump","provider_url":"https://nostr.ae","html":"📅 Original date posted:2014-07-17\n📝 Original message:OVERVIEW\n\nTo improve block propagation, add a new block message that doesn't include\ntransactions the peer is known to have. The message must never require an\nadditional round trip due to any transactions the peer doesn't have, but\nshould\nbe compatible with peers sometimes forgetting transactions they have known.\n\nAPPROACH\n\nFor peers advertising support for squashed blocks: a node tracks what txes\nit\nknows each peer has seen (inv received, tx sent, tx appeared in competing\nblock\nknown to peer). Nodes push block contents as txes-not-already-known +\ntxids-known.\n\nA node should be able to forget invs it has seen without invalidating what\npeers\nknow about its known txes. To allow for this, a node assembles a bloom\nfilter of\na set of txes it is going to forget, and sends it to peers. The node can\nerase\nthe txes as soon as no blocks requested before the filter was pushed are in\nflight (relying on the assumption that messages can be expected to be\nprocessed\nin order).\n\nWhen a node receives a forgotten-filter, it ORs it into its\nforgotten-filter for\nthat peer. Any transactions matching the forgotten-filter are always\nincluded in\nfull with a block. If the filter is getting full, the node can just clear it\nalong with peer.setTxKnown.\n\nCOSTS\n\nBloom filtering:\nSince the bloom filter is likely to grow slowly and can be dropped when it\nis\nbecoming full, a cheap set of hash functions and element size can be used to\nkeep overhead more restricted than the bloom filtering done for spv. It's\nimportant for testing txes against the filter to be fast so that it doesn't\ndelay pushing the block more than the squashing helps.\nNodes currently forget txes rarely, so the bloom filters would only need to\nbe\nused at all under conditions that are not currently common -- but I think\nthey're important to include to allow for different node behavior in this\nregard\nin the future.\n\nTracking txes known to peers:\nA multimap of txid-\u003epeerId would obviate the current setCurrentlyKnown, and\nwould not take much more space since each additional peer adds about 1\npeerId\nper txid (setCurrentlyKnown keeps a uint256 per peer per txid, although it\ntracks somewhat fewer txid per node).\n\nPotential vulnerabilities:\n- Since the bloom filters will have lower maximum overhead than the current\nSPV\n  filters and can be dropped at will, this shouldn't enable any resource\n  exhaustion attacks that aren't already possible.\n- A squashed block with bogus or missing data would be easily detected not\nto\n  produce the correct merkle root for its BlockHeader.\n\nBENEFITS\n\nAssuming a fairly typical 500 tx block with transaction sizes averaging 300b\n(both on the low side), for a 150kb block:\n\n% pruned | block size reduction | relative size reduction\n-------- | -------------------- | -----------------------\n100      | 134 kB               | 89%\n50       | 67 kB                | 45%\n25       | 33.5 kB              | 17%\n\nI've been doing some logging, and when my node pushes a block to a peer it\nseems\nto typically know that a peer has seen most of the txes in the block. Even\nin\nthe case of a small block with only 25% known-known transactions, total\nnetwork\nbandwidth saved is greater than the bloom filters transmitted unless a node\nis\nforgetting transactions so rapidly that it pushes new maximum-size\nforget-filters every block.\n\nSo this is a net gain even in total bandwidth usage, but most importantly\nit's\nan improvement in block propagation rate and in how block propagation rate\nscales with additional transactions.\n\nIMPLEMENTATION QUESTIONS\n\nHow should block squashing capability be advertised -- new service bit?\n\nBloom filters:\n- How fast to test against could a suitable bloom filter be made?\n- How much memory would each filter need to take, at maximum?\n- Can the inputs all being 32 byte hashes be used to optimize filter hash\n  calculations?\n\nROADMAP\n\nIf there's support for this proposal, I can begin working on the specific\nimplementation details, such as the bloom filters, message format, and\ncapability advertisment, and draft a BIP once I have a concrete proposal for\nwhat those would look like and a corresponding precise cost/benefit\nanalysis.\n\n--kaz\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20140717/810d2f69/attachment.html\u003e"}