<div dir="ltr"><span style="font-family:arial,sans-serif;font-size:12.727272033691406px">I thought I'd chime in and point out some research results that might help.</span><div style="font-family:arial,sans-serif;font-size:12.727272033691406px">
Even if they don't, there is a cool underlying technique that some of you</div><div style="font-family:arial,sans-serif;font-size:12.727272033691406px">might find interesting.<br><div><br><div>The problem being tackled here is very similar to "set reconciliation," where</div>
<div>peer A thinks that the set of transactions that should be in the block is S_A,</div><div>and peer B has actually included set S_B, and S_A and S_B are expected</div><div>to not differ much. Ideally, one would like the communication complexity</div>
</div><div>between A and B to be O(delta), not O(S_B) as it is right now. And ideally,</div><div>one would like B to send a single message to A, and for A to figure out the</div><div>difference between the two sets, without any lengthy back and forth </div>
<div>communication. In essence, I would like to give you some magical packet</div><div>that is pretty small and communicates just the delta between what you and</div><div>I know.</div><div><br></div><div>This paper from Cornell describes a scheme for achieving this:</div>
<div> Yaron Minsky, Ari Trachtenberg, Richard Zippel: Set reconciliation with nearly optimal communication complexity. IEEE Transactions on Information Theory 49(9): 2213-2218 (2003)</div><div> <a href="http://ipsit.bu.edu/documents/ieee-it3-web.pdf" target="_blank">http://ipsit.bu.edu/documents/ieee-it3-web.pdf</a><br>
</div><div><br></div><div>Those of you looking for a TL;DR should read the intro and then skip to</div><div>page 8 for the example. The underlying trick is very cool, comes from the</div><div>peer-to-peer/gossip literature, and it is underused. It'd be really cool if it</div>
<div>could be applied to this problem to reduce the size of the packets.</div><div><br></div><div>This approach has three benefits over the Bloom filter approach (if I </div><div>understand the Bloom filter idea correctly): </div>
<div><br></div><div>(1) Bloom filters require packets that are still O(S_A), </div><div><br></div><div>(2) Bloom filters are probabilistic, so require extra complications</div><div>when there is a hash collision. In the worst case, A might get confused</div>
<div>about which transaction B actually included, which would lead to a </div><div>fork. (I am not sure if I followed the Bloom filter idea fully -- this may </div><div>not happen with the proposal, but it's a possibility with a naive Bloom</div>
<div>filter implementation)</div><div><br></div><div>(3) Bloom filters are interactive, so when A detects that B has included</div><div>some transactions that A does not know about, it has to send a message</div><div>to figure out what those transactions are. </div>
<div><br></div><div>Set reconciliation is O(delta), non-probabilistic, and non-interactive. The</div><div>naive version requires that one have some idea of the size of the delta,</div><div>but I think the paper has some discussion of how to handle the delta </div>
<div>estimate.</div><div><br></div><div>I have not gone through the full exercise of actually applying this trick to</div><div>the Bitcoin p2p protocol yet, but wanted to draw your attention to it. </div><div>If someone is interested in applying this stuff to Bitcoin, I'd be happy </div>
<div>to communicate further off list.</div><div><br></div><div>- egs</div><div><br></div></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Fri, Jul 18, 2014 at 12:55 PM, Jeff Garzik <span dir="ltr"><<a href="mailto:jgarzik@bitpay.com" target="_blank">jgarzik@bitpay.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Related: We must handle some legitimate miner-privately-mined cases,<br>
such as miner payout TXs (outside coinbase) or side chain conditional<br>
TXs[1].<br>
<br>
[1] <a href="https://bitcointalk.org/index.php?topic=676703.msg7682680#msg7682680" target="_blank">https://bitcointalk.org/index.php?topic=676703.msg7682680#msg7682680</a><br>
<div class="HOEnZb"><div class="h5"><br>
On Fri, Jul 18, 2014 at 3:51 PM, Kaz Wesley <<a href="mailto:keziahw@gmail.com">keziahw@gmail.com</a>> wrote:<br>
> I've updated the gist, and added an additional proposal that I think<br>
> meshes well:<br>
> <a href="https://gist.github.com/kazcw/43c97d3924326beca87d#ultra-fast-block-validation" target="_blank">https://gist.github.com/kazcw/43c97d3924326beca87d#ultra-fast-block-validation</a><br>
><br>
> sparseblocks + UFBV would tighten the new-block process to this (when<br>
> txes have been received in advance):<br>
> - receive block (~2kB for 1000 tx)<br>
> - check whether block contains txes known to belong to conflict-sets,<br>
> and if so whether more than one tx from a single conflict-set has been<br>
> included (a few operations on very small sets)<br>
> - relay block (~2kB)<br>
><br>
> The benefits of these changes only occur when the transactions have<br>
> been seen in advance, but incentivizing ahead-of-block transaction<br>
> propogation is a plus, as Jeff mentioned; working on a block without<br>
> first ensuring peers have its transactions would be very expensive<br>
> from a miner's point of view.<br>
><br>
> ------------------------------------------------------------------------------<br>
> Want fast and easy access to all the code in your enterprise? Index and<br>
> search up to 200,000 lines of code with a free copy of Black Duck<br>
> Code Sight - the same software that powers the world's largest code<br>
> search on Ohloh, the Black Duck Open Hub! Try it now.<br>
> <a href="http://p.sf.net/sfu/bds" target="_blank">http://p.sf.net/sfu/bds</a><br>
> _______________________________________________<br>
> Bitcoin-development mailing list<br>
> <a href="mailto:Bitcoin-development@lists.sourceforge.net">Bitcoin-development@lists.sourceforge.net</a><br>
> <a href="https://lists.sourceforge.net/lists/listinfo/bitcoin-development" target="_blank">https://lists.sourceforge.net/lists/listinfo/bitcoin-development</a><br>
<br>
<br>
<br>
</div></div><div class="im HOEnZb">--<br>
Jeff Garzik<br>
Bitcoin core developer and open source evangelist<br>
BitPay, Inc. <a href="https://bitpay.com/" target="_blank">https://bitpay.com/</a><br>
<br>
</div><div class="HOEnZb"><div class="h5">------------------------------------------------------------------------------<br>
Want fast and easy access to all the code in your enterprise? Index and<br>
search up to 200,000 lines of code with a free copy of Black Duck<br>
Code Sight - the same software that powers the world's largest code<br>
search on Ohloh, the Black Duck Open Hub! Try it now.<br>
<a href="http://p.sf.net/sfu/bds" target="_blank">http://p.sf.net/sfu/bds</a><br>
_______________________________________________<br>
Bitcoin-development mailing list<br>
<a href="mailto:Bitcoin-development@lists.sourceforge.net">Bitcoin-development@lists.sourceforge.net</a><br>
<a href="https://lists.sourceforge.net/lists/listinfo/bitcoin-development" target="_blank">https://lists.sourceforge.net/lists/listinfo/bitcoin-development</a><br>
</div></div></blockquote></div><br></div>