<div dir="ltr"><div>OVERVIEW</div><div><br></div><div>To improve block propagation, add a new block message that doesn&#39;t include</div><div>transactions the peer is known to have. The message must never require an</div>

<div>additional round trip due to any transactions the peer doesn&#39;t have, but should</div><div>be compatible with peers sometimes forgetting transactions they have known.</div><div><br></div><div>APPROACH<br></div><div>

<br></div><div>For peers advertising support for squashed blocks: a node tracks what txes it</div><div>knows each peer has seen (inv received, tx sent, tx appeared in competing block</div><div>known to peer). Nodes push block contents as txes-not-already-known +</div>

<div>txids-known.</div><div><br></div><div>A node should be able to forget invs it has seen without invalidating what peers</div><div>know about its known txes. To allow for this, a node assembles a bloom filter of</div>
<div>
a set of txes it is going to forget, and sends it to peers. The node can erase</div><div>the txes as soon as no blocks requested before the filter was pushed are in</div><div>flight (relying on the assumption that messages can be expected to be processed</div>

<div>in order).</div><div><br></div><div>When a node receives a forgotten-filter, it ORs it into its forgotten-filter for</div><div>that peer. Any transactions matching the forgotten-filter are always included in</div><div>

full with a block. If the filter is getting full, the node can just clear it</div><div>along with peer.setTxKnown.</div><div><br></div><div>COSTS</div><div><br></div><div>Bloom filtering:</div><div>Since the bloom filter is likely to grow slowly and can be dropped when it is</div>

<div>becoming full, a cheap set of hash functions and element size can be used to</div><div>keep overhead more restricted than the bloom filtering done for spv. It&#39;s</div><div>important for testing txes against the filter to be fast so that it doesn&#39;t</div>

<div>delay pushing the block more than the squashing helps.</div><div>Nodes currently forget txes rarely, so the bloom filters would only need to be</div><div>used at all under conditions that are not currently common -- but I think</div>

<div>they&#39;re important to include to allow for different node behavior in this regard</div><div>in the future.</div><div><br></div><div>Tracking txes known to peers:</div><div>A multimap of txid-&gt;peerId would obviate the current setCurrentlyKnown, and</div>

<div>would not take much more space since each additional peer adds about 1 peerId</div><div>per txid (setCurrentlyKnown keeps a uint256 per peer per txid, although it</div><div>tracks somewhat fewer txid per node).</div>

<div><br></div><div>Potential vulnerabilities:</div><div>- Since the bloom filters will have lower maximum overhead than the current SPV</div><div>  filters and can be dropped at will, this shouldn&#39;t enable any resource</div>

<div>  exhaustion attacks that aren&#39;t already possible.</div><div>- A squashed block with bogus or missing data would be easily detected not to</div><div>  produce the correct merkle root for its BlockHeader.</div><div>

<br></div><div>BENEFITS</div><div><br></div><div>Assuming a fairly typical 500 tx block with transaction sizes averaging 300b</div><div>(both on the low side), for a 150kb block:</div><div><br></div><div>% pruned | block size reduction | relative size reduction</div>

<div>-------- | -------------------- | -----------------------</div><div>100      | 134 kB               | 89%</div><div>50       | 67 kB                | 45%</div><div>25       | 33.5 kB              | 17%</div><div><br>

</div><div>I&#39;ve been doing some logging, and when my node pushes a block to a peer it seems</div><div>to typically know that a peer has seen most of the txes in the block. Even in</div><div>the case of a small block with only 25% known-known transactions, total network</div>

<div>bandwidth saved is greater than the bloom filters transmitted unless a node is</div><div>forgetting transactions so rapidly that it pushes new maximum-size</div><div>forget-filters every block.</div><div><br></div><div>

So this is a net gain even in total bandwidth usage, but most importantly it&#39;s</div><div>an improvement in block propagation rate and in how block propagation rate</div><div>scales with additional transactions.</div>
<div>
<br></div><div>IMPLEMENTATION QUESTIONS</div><div><br></div><div>How should block squashing capability be advertised -- new service bit?</div><div><br></div><div>Bloom filters:</div><div>- How fast to test against could a suitable bloom filter be made?</div>

<div>- How much memory would each filter need to take, at maximum?</div><div>- Can the inputs all being 32 byte hashes be used to optimize filter hash</div><div>  calculations?</div><div><br></div><div>ROADMAP</div><div>
<br>
</div><div>If there&#39;s support for this proposal, I can begin working on the specific</div><div>implementation details, such as the bloom filters, message format, and</div><div>capability advertisment, and draft a BIP once I have a concrete proposal for</div>

<div>what those would look like and a corresponding precise cost/benefit analysis.</div><div><br></div><div>--kaz</div></div>