My apologies for posting to the wrong thread. On Fri, Jul 18, 2014 at 5:51 PM, Emin Gün Sirer wrote: > I thought I'd chime in and point out some research results that might help. > Even if they don't, there is a cool underlying technique that some of you > might find interesting. > > The problem being tackled here is very similar to "set reconciliation," > where > peer A thinks that the set of transactions that should be in the block is > S_A, > and peer B has actually included set S_B, and S_A and S_B are expected > to not differ much. Ideally, one would like the communication complexity > between A and B to be O(delta), not O(S_B) as it is right now. And ideally, > one would like B to send a single message to A, and for A to figure out the > difference between the two sets, without any lengthy back and forth > communication. In essence, I would like to give you some magical packet > that is pretty small and communicates just the delta between what you and > I know. > > This paper from Cornell describes a scheme for achieving this: > Yaron Minsky, Ari Trachtenberg, Richard Zippel: Set reconciliation with > nearly optimal communication complexity. IEEE Transactions on Information > Theory 49(9): 2213-2218 (2003) > http://ipsit.bu.edu/documents/ieee-it3-web.pdf > > Those of you looking for a TL;DR should read the intro and then skip to > page 8 for the example. The underlying trick is very cool, comes from the > peer-to-peer/gossip literature, and it is underused. It'd be really cool > if it > could be applied to this problem to reduce the size of the packets. > > This approach has three benefits over the Bloom filter approach (if I > understand the Bloom filter idea correctly): > > (1) Bloom filters require packets that are still O(S_A), > > (2) Bloom filters are probabilistic, so require extra complications > when there is a hash collision. In the worst case, A might get confused > about which transaction B actually included, which would lead to a > fork. (I am not sure if I followed the Bloom filter idea fully -- this may > not happen with the proposal, but it's a possibility with a naive Bloom > filter implementation) > > (3) Bloom filters are interactive, so when A detects that B has included > some transactions that A does not know about, it has to send a message > to figure out what those transactions are. > > Set reconciliation is O(delta), non-probabilistic, and non-interactive. The > naive version requires that one have some idea of the size of the delta, > but I think the paper has some discussion of how to handle the delta > estimate. > > I have not gone through the full exercise of actually applying this trick > to > the Bitcoin p2p protocol yet, but wanted to draw your attention to it. > If someone is interested in applying this stuff to Bitcoin, I'd be happy > to communicate further off list. > > - egs > > > > On Fri, Jul 18, 2014 at 6:44 AM, Jeff Garzik wrote: > >> Yes. That, and several other things. If you can figure out how to >> propagate a block without re-propagating all the transactions everyone >> already has, you address the large-blocks-slower-to-relay problem, and >> additionally create an incentive for miners to mine blocks consisting >> of publicly broadcast transactions (versus a bunch of secret ones >> mined with secret agreements). >> >> Democratizing transaction selection takes a bit of power away from the >> miners and gives it back to the network at large. GBT is another >> piece of that puzzle. >> >> >> On Fri, Jul 18, 2014 at 6:43 AM, Mike Hearn wrote: >> > Oops, sorry, I see the subject line changed. This is what I get for >> working >> > down the thread list top to bottom :) >> > >> > I think the best path forward now is to finish off getblocktemplate >> support >> > in the various tools so it's possible to pool for payout purposes >> without >> > giving up control of block creation modulo the coinbase. Combined with >> the >> > recent sipa performance enhancing goodness, it would hopefully persuade >> some >> > non-trivial chunk of hashpower to go back to running their own node and >> > start the process of turning pools merely into payout trackers rather >> than >> > block selectors. >> > >> > >> > On Fri, Jul 18, 2014 at 12:41 PM, Mike Hearn wrote: >> >> >> >> Jeff, I think the message you're replying to got clipped. >> >> >> >> Satoshi's only comment AFAIK on the topic of GPU mining was to wish >> for a >> >> gentlemen's agreement to postpone it as long as possible, to help make >> sure >> >> the distribution of coins was as even as possible. Indeed this predated >> >> pooled mining. >> >> >> > >> >> >> >> -- >> Jeff Garzik >> Bitcoin core developer and open source evangelist >> BitPay, Inc. https://bitpay.com/ >> >> >> ------------------------------------------------------------------------------ >> Want fast and easy access to all the code in your enterprise? Index and >> search up to 200,000 lines of code with a free copy of Black Duck >> Code Sight - the same software that powers the world's largest code >> search on Ohloh, the Black Duck Open Hub! Try it now. >> http://p.sf.net/sfu/bds >> _______________________________________________ >> Bitcoin-development mailing list >> Bitcoin-development@lists.sourceforge.net >> https://lists.sourceforge.net/lists/listinfo/bitcoin-development >> > >