From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192] helo=mx.sourceforge.net) by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1XCxGc-0005ZE-BH for bitcoin-development@lists.sourceforge.net; Thu, 31 Jul 2014 20:48:02 +0000 Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of gmail.com designates 209.85.214.182 as permitted sender) client-ip=209.85.214.182; envelope-from=keziahw@gmail.com; helo=mail-ob0-f182.google.com; Received: from mail-ob0-f182.google.com ([209.85.214.182]) by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1XCxGa-000746-Ql for bitcoin-development@lists.sourceforge.net; Thu, 31 Jul 2014 20:48:02 +0000 Received: by mail-ob0-f182.google.com with SMTP id wm4so1973167obc.13 for ; Thu, 31 Jul 2014 13:47:55 -0700 (PDT) X-Received: by 10.60.121.99 with SMTP id lj3mr1186289oeb.44.1406839675279; Thu, 31 Jul 2014 13:47:55 -0700 (PDT) MIME-Version: 1.0 Received: by 10.202.61.195 with HTTP; Thu, 31 Jul 2014 13:47:35 -0700 (PDT) In-Reply-To: References: From: Kaz Wesley Date: Thu, 31 Jul 2014 13:47:35 -0700 Message-ID: To: =?UTF-8?Q?Emin_G=C3=BCn_Sirer?= Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Spam-Score: -1.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 (keziahw[at]gmail.com) -0.0 SPF_PASS SPF: sender matches SPF record -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: 1XCxGa-000746-Ql Cc: Bitcoin Dev Subject: Re: [Bitcoin-development] Squashing redundant tx data in blocks on the wire 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: Thu, 31 Jul 2014 20:48:02 -0000 I don't see how set reconciliation alone would be practical for condensed block exchange -- if the keys are txids it'd require a round trip to request the missing tx; if we could somehow get the "What's the Difference" approach to effectively operate on full transactions instead, the log(keysize) factor overhead would make any transactions not mutually-known very expensive to exchange (at keysize=3D32b, data would need to be 80% mutually-known just to break even). There's also the complication and/or overhead of establishing an "expected block" to reconcile with the actual block. The approach of remembering what invs have been transmitted both directions along each connection is less elegant; it requires remembering a lot of communication history, introducing a major point of statefulness to the protocol, and custom-compacting blocks for each peer. But it is also very effective at squeezing bytes, cheap in cpu cycles, and the implementation is fairly simple. The wealth of mutual knowledge already available in the current protocol allows accomplishing the goal of exchanging blocks efficiently by solving a much easier problem than its context-less cousin. I have my doubts that it is possible for even an optimal contextless solution to do as well as channel memory in terms of bytes exchanged or computational complexity -- you can't beat making use of the available information. I have an implementation of inv-history-tracking that uses a 2b/tx alternative to getdata for tx, and I've had that running between two nodes for ~2 weeks now. I've been working on a better implementation of that plus the sparseblock messages, and I'll have the sparseblock prototype (suitable for something like Gregory's remember-last-N approach) up and running in a couple of days or so. The prototype handles assigning compact identifiers to transactions and using those in block messages; there's a lot of bit-packing sort of tweaks that can be done that I'm not including in the initial prototype. The prototype will be able to log history-hit rates, so if we run a few sparseblocks nodes connected to each other for a while we should get a good idea of how much efficiency gain this provides, and how it can be improved. This approach even without the intensive bit packing has a total vtx transmission size of 2*nTxKnown + 1*nTxUnknown + nBytesTxUnknown, where only a small window of very recent transactions and any transactions that have fallen out of the history limit would be mutually known but not known to be known. It would be possible to nearly eliminate even that overhead for both known and unknown transactions with compact descriptions of block tx inclusion and ordering policies as Gavin brought up, for which something like scripts defining priority formulas would be a possible implementation (https://gist.github.com/kazcw/43c97d3924326beca87d#ordering= -policy -- n.b. most of the rest of the gist is currently outdated). But since priority scripts are themselves more complicated than the rest of the sparseblock implementation, and basic sparseblocks achieve the vast majority of bandwidth savings, I think it's worth implementing sparseblocks without priority scripts now and then using priority scripts for sparseblocks2 along with all the other things they can do later. Set reconciliation does look like a great way to synchronize mempools. I've been thinking, contextless low-cost mempool exchange would enable a node to have one or more "roaming" peer slots -- connect to a node, fill in each other's mempools, move on to another peer. It seems like this would go a long way to mitigate potential pathological network topologies -- it would make it very difficult to sybil attack a node (barring an attacker in a position to spoof IP addresses), and if a serious bug or DoS attack caused the network to start to partition itself due to DoS bans, it only takes occasional roamers crossing the partition to keep both sides generally in sync. Efficient mempool synchronization would also increase the efficacy of channel-memory sparseblocks: it picks up transactions too old to have been exchanged via invs, and could also allow nodes to know exactly what transactions their peers have discarded. On Thu, Jul 31, 2014 at 8:31 AM, Gavin Andresen w= rote: > I've been reading up on set reconciliation algorithms, and thinking about > constant-bandwidth propagation of new block announcements. > > Emin: the approach in this paper: > What's the Difference? Efficient Set Reconciliation without Prior Context > http://conferences.sigcomm.org/sigcomm/2011/papers/sigcomm/p218.pdf > > ... looks like it would be much better suited for Bitcoin's use case, > because > > a) it looks much easier to implement (no polynomial math) > b) CPU/latency versus bandwidth tradeoff looks better (somewhat higher > bandwidth than Yaron's method, but much lower CPU/latency cost) > > Kaz: how much time do you have to work on this? Perhaps we can get a > road-map for a prototype and split up work. I actually think the first st= ep > might be to gather a couple days worth of tx / block message broadcasts f= rom > a few network nodes and then create a test/benchmark harness that will te= ll > us how much overlap there is in what nodes know and how much faster our > newer algorithms are. > > -- > -- > Gavin Andresen On Thu, Jul 31, 2014 at 12:10 PM, Emin G=C3=BCn Sirer wrote: > Hi Gavin, > > Great find. I read (and sadly forgot) this paper back in 2011 and indeed, > I'd also pick this approach over Yaron's. My reasons: > > a. this paper provides a more concrete implementation roadmap that has be= en > explored thoroughly. While I understand Yaron's technique, there are stil= l > various design decisions (e.g. estimating the set difference involves a > doubling process; representing TX ids seems to take up a lot of space) th= at > are left unspec'ed for an implementation. (In general, Yaron is a > theoretician at heart and Varghese is a very practical guy, there will be > far fewer unforeseen issues with a Varghese tried and tested algorithm). > > b. on the surface, this paper seems to use a bit more bandwidth in that i= t > requires O(size of set diff * log of keyspace) vs. Yaron's claim of O(siz= e > of set diff). But I believe that in practice Yaron's method would also ha= ve > an O(log of keyspace) multiplier in place because the roots of his > polynomial (the TX ids) have to be represented as numbers, and that requi= res > log-of-keyspace bits. I suspect that Yaron is cleverly folding that facto= r > into the constant factor of O notation, and Varghese et al are being poli= te > by not pointing it out too overtly. So I suspect that the two schemes are > actually identical in terms of space complexity. > > c. this technique is far more efficient in decoding than Yaron's, which > requires Gaussian elimination, which in turn is O(d^3). > > If Bitcoin adopts this technique, it'll be adopting one of the best known > techniques from the research community. > > BTW, don't hesitate to ping me with researchy issues in the future; I'll > gladly point the effort in the right direction if I can. > > - egs > > > > On Thu, Jul 31, 2014 at 6:31 PM, Gavin Andresen > wrote: >> >> I've been reading up on set reconciliation algorithms, and thinking abou= t >> constant-bandwidth propagation of new block announcements. >> >> Emin: the approach in this paper: >> What's the Difference? Efficient Set Reconciliation without Prior Contex= t >> http://conferences.sigcomm.org/sigcomm/2011/papers/sigcomm/p218.pdf >> >> ... looks like it would be much better suited for Bitcoin's use case, >> because >> >> a) it looks much easier to implement (no polynomial math) >> b) CPU/latency versus bandwidth tradeoff looks better (somewhat higher >> bandwidth than Yaron's method, but much lower CPU/latency cost) >> >> Kaz: how much time do you have to work on this? Perhaps we can get a >> road-map for a prototype and split up work. I actually think the first s= tep >> might be to gather a couple days worth of tx / block message broadcasts = from >> a few network nodes and then create a test/benchmark harness that will t= ell >> us how much overlap there is in what nodes know and how much faster our >> newer algorithms are. >> >> -- >> -- >> Gavin Andresen > >