From: "Emin Gün Sirer" <el33th4x0r@gmail•com>
To: Jeff Garzik <jgarzik@bitpay•com>
Cc: Bitcoin Dev <bitcoin-development@lists•sourceforge.net>
Subject: Re: [Bitcoin-development] Decentralizing ming
Date: Fri, 18 Jul 2014 17:54:36 -0700 [thread overview]
Message-ID: <CAPkFh0sqFFU-JWJ1f49DZSBORTo__Nwis8TrakJS5ZT_oWSN5A@mail.gmail.com> (raw)
In-Reply-To: <CAPkFh0uk9uAODo2Pp654xapoD=J=3HukMouCSdnYZuAN43Y=2A@mail.gmail.com>
[-- Attachment #1: Type: text/plain, Size: 5569 bytes --]
My apologies for posting to the wrong thread.
On Fri, Jul 18, 2014 at 5:51 PM, Emin Gün Sirer <el33th4x0r@gmail•com>
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 <jgarzik@bitpay•com> 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 <mike@plan99•net> 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 <mike@plan99•net> 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
>>
>
>
[-- Attachment #2: Type: text/html, Size: 7455 bytes --]
next prev parent reply other threads:[~2014-07-19 0:55 UTC|newest]
Thread overview: 8+ messages / expand[flat|nested] mbox.gz Atom feed top
2014-07-17 16:14 Jeff Garzik
2014-07-17 17:22 ` slush
2014-07-18 10:41 ` Mike Hearn
2014-07-18 10:43 ` Mike Hearn
2014-07-18 13:44 ` Jeff Garzik
2014-07-19 0:51 ` Emin Gün Sirer
2014-07-19 0:54 ` Emin Gün Sirer [this message]
2014-07-18 13:39 ` Jeff Garzik
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAPkFh0sqFFU-JWJ1f49DZSBORTo__Nwis8TrakJS5ZT_oWSN5A@mail.gmail.com \
--to=el33th4x0r@gmail$(echo .)com \
--cc=bitcoin-development@lists$(echo .)sourceforge.net \
--cc=jgarzik@bitpay$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox