Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192] helo=mx.sourceforge.net) by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1X8IvX-00083T-Tg for bitcoin-development@lists.sourceforge.net; Sat, 19 Jul 2014 00:55:03 +0000 Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of gmail.com designates 209.85.218.52 as permitted sender) client-ip=209.85.218.52; envelope-from=el33th4x0r@gmail.com; helo=mail-oi0-f52.google.com; Received: from mail-oi0-f52.google.com ([209.85.218.52]) by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1X8IvW-0007C6-Gj for bitcoin-development@lists.sourceforge.net; Sat, 19 Jul 2014 00:55:03 +0000 Received: by mail-oi0-f52.google.com with SMTP id h136so2211691oig.11 for ; Fri, 18 Jul 2014 17:54:57 -0700 (PDT) X-Received: by 10.182.108.228 with SMTP id hn4mr12063504obb.73.1405731296928; Fri, 18 Jul 2014 17:54:56 -0700 (PDT) MIME-Version: 1.0 Received: by 10.76.23.193 with HTTP; Fri, 18 Jul 2014 17:54:36 -0700 (PDT) In-Reply-To: References: From: =?UTF-8?Q?Emin_G=C3=BCn_Sirer?= Date: Fri, 18 Jul 2014 17:54:36 -0700 Message-ID: To: Jeff Garzik Content-Type: multipart/alternative; boundary=089e0149d2bc9a783904fe8152a9 X-Spam-Score: -0.6 (/) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. -1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for sender-domain 0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider (el33th4x0r[at]gmail.com) -0.0 SPF_PASS SPF: sender matches SPF record 1.0 HTML_MESSAGE BODY: HTML included in message -0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from author's domain 0.1 DKIM_SIGNED Message has a DKIM or DK signature, not necessarily valid -0.1 DKIM_VALID Message has at least one valid DKIM or DK signature X-Headers-End: 1X8IvW-0007C6-Gj Cc: Bitcoin Dev Subject: Re: [Bitcoin-development] Decentralizing ming X-BeenThere: bitcoin-development@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 19 Jul 2014 00:55:04 -0000 --089e0149d2bc9a783904fe8152a9 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable My apologies for posting to the wrong thread. On Fri, Jul 18, 2014 at 5:51 PM, Emin G=C3=BCn Sirer wrote: > I thought I'd chime in and point out some research results that might hel= p. > 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 ideall= y, > one would like B to send a single message to A, and for A to figure out t= he > 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 wit= h > 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 ma= y > 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. T= he > 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 persuad= e >> some >> > non-trivial chunk of hashpower to go back to running their own node an= d >> > 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 mak= e >> sure >> >> the distribution of coins was as even as possible. Indeed this predat= ed >> >> 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 >> > > --089e0149d2bc9a783904fe8152a9 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
My apologies for posting to the wrong thread.=C2=A0


On Fri, Jul 18, 2014 at 5:51 PM, Emin G=C3=BCn Sirer <= ;el33th4x0r@gmail= .com> wrote:
I thought I'd chime in = and point out some research results that might help.
Even if they don&#= 39;t, there is a cool underlying technique that some of you
might find interesting.

The problem being tackled here is very similar to "set reconcilia= tion," 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 complexi= ty
between A and B to be O(delta), not O(S_B) as it is righ= t 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=C2= =A0
communication. In essence, I would like to give you some magi= cal packet
that is pretty small and communicates just the delta b= etween what you and
I know.

This paper from Cornell describes a s= cheme for achieving this:
=C2=A0 =C2=A0Yaron Minsky, Ari Trachten= berg, Richard Zippel: Set reconciliation with nearly optimal communication = complexity. IEEE Transactions on Information Theory 49(9): 2213-2218 (2003)=
=C2=A0 =C2=A0http://ipsit.bu.edu/documents/ieee-it3-web.pdf
<= /div>

Those of you looking for a TL;DR should read the i= ntro 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=C2=A0
understand the Bloom filter idea correctly):= =C2=A0

(1) Bloom filters require packets that are = still O(S_A),=C2=A0

(2) Bloom filters are probabilistic, so require extra c= omplications
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=C2=A0
fork. (I am not sure if I followed the Bloom filter idea fully -- this= may=C2=A0
not happen with the proposal, but it's a possibili= ty 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 mess= age
to figure out what those transactions are.=C2=A0
Set reconciliation is O(delta), non-probabilistic, and non-inter= active. 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=C2=A0
estimate.

I have not gone through the full ex= ercise of actually applying this trick to
the Bitcoin p2p protoco= l yet, but wanted to draw your attention to it.=C2=A0
If someone = is interested in applying this stuff to Bitcoin, I'd be happy=C2=A0
to communicate further off list.

- egs

=


On Fri, Jul 18, 2014 at 6:44 AM, Jeff Garzik= <jgarzik@bitpay.com> wrote:
Yes. =C2=A0That, and several other things. = =C2=A0If 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. =C2=A0GBT 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 wo= rking
> down the thread list top to bottom :)
>
> I think the best path forward now is to finish off getblocktemplate su= pport
> 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 persuad= e some
> non-trivial chunk of hashpower to go back to running their own node an= d
> 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 h= elp make sure
>> the distribution of coins was as even as possible. Indeed this pre= dated
>> pooled mining.
>>
>



--
Jeff Garzik
Bitcoin core developer and open source evangelist
BitPay, Inc. =C2=A0 =C2=A0 =C2=A0https://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/b= ds
_______________________________________________
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-de= velopment


--089e0149d2bc9a783904fe8152a9--