From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 17006A6E for ; Thu, 24 Sep 2015 00:31:52 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-ig0-f169.google.com (mail-ig0-f169.google.com [209.85.213.169]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 6C657174 for ; Thu, 24 Sep 2015 00:31:50 +0000 (UTC) Received: by igbkq10 with SMTP id kq10so110867663igb.0 for ; Wed, 23 Sep 2015 17:31:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; bh=RnW1hMtUYfq8AscqXHc/Kxsz49JiaTxTxVQpTJMYD3A=; b=UYsM5epQ/sb6Jwln0ayj9xNO7khXuXZ4plrN5h4XnNIUSHAag/p/Kj3Edp6K2/pj7i j78mEpWswSHdYhthFJcnqAmjS90v4BPcLQfEuZ1LaMKPwNaIkPRQPvr/dvlIF+i562LX uGLuolDSbnb7DkuJc5/3mivvhaCqDO4aDj5MjPjSF0ho93Of+qbzlPWzzt0e7NZgvv96 8KTVRLTcnPHovpxq7OQY+3VGS1OjnpZKDUDsmRPnWoVUgb8V0O2ssCBcumAs3601QZOO MuCISqtOXnEp9xfGbj+12LqVfA+LyMMSFDkO6PDTaGCStemceWrIcpJrCRtOdQbid6fa dB3Q== X-Received: by 10.50.43.166 with SMTP id x6mr27243895igl.89.1443054709798; Wed, 23 Sep 2015 17:31:49 -0700 (PDT) MIME-Version: 1.0 Received: by 10.36.14.85 with HTTP; Wed, 23 Sep 2015 17:31:27 -0700 (PDT) In-Reply-To: <36CE1B0F-3BE5-4DC3-8488-A57667256059@toom.im> References: <36CE1B0F-3BE5-4DC3-8488-A57667256059@toom.im> From: Angel Leon Date: Wed, 23 Sep 2015 20:31:27 -0400 Message-ID: To: "Jonathan Toomim (Toomim Bros)" Content-Type: multipart/alternative; boundary=089e01227f365e807c0520735b11 X-Spam-Status: No, score=-2.7 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,HTML_MESSAGE,RCVD_IN_DNSWL_LOW autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Cc: Bitcoin Dev Subject: Re: [bitcoin-dev] Torrent-style new-block propagation on Merkle trees X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Development Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 24 Sep 2015 00:31:52 -0000 --089e01227f365e807c0520735b11 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable has anybody ever submitted a patch using libtorrent's library for this purpose? would it make sense to create a torrent per confirmed valid block once it's been truly added to the blockchain? if we used libtorrent, I imagine the following to announce the new block on libtorrent's DHT (PSEUDO CODE) // this is how you could announce yourself as a peer on the DHT holding a block at a certain height. // the announcement would include a TCP port to then request more information about that block. string peer_announcement_key =3D sha1_hasher("blockchain::bitcoin::block::"= + last_block_height_number).final(); session.dht_announce(peer_announcement_key, rpc_port, 0); // then another peer looking for peers that might be seeding a block at N height would: sessoin.dht_get_peers(sha1_hasher("blockchain::bitcoin::block::" + N_height).final()); // asynchronously you'd handle the responses by the XOR-nearest peers on the DHT // this search would be O(log n) // you could then request from several of these guys what's the infohash for the .torrent // that's been created to seed the block at height N. then you'd start the block download by building a magnet link out of the infohash received for the block. The download would be done directly to memory and then such byte array would be serialized as a block as it is done now, and you'd then announce yourself both on the sha1(peer_announcement_key) and on the infohash of the block you just downloaded, after you start seeding it. perhaps the block's torrent chunk sizes could be made optimal so that chunks sent would perfectly match tranactions, this way you could start building the blocks on the other end as they're being downloaded from the swarm. http://twitter.com/gubatron On Wed, Sep 23, 2015 at 7:12 PM, Jonathan Toomim (Toomim Bros) via bitcoin-dev wrote: > > > As I understand it, the current block propagation algorithm is this: > > 1. A node mines a block. > 2. It notifies its peers that it has a new block with an *inv*. Typical > nodes have 8 peers. > 3. The peers respond that they have not seen it, and request the block > with *getdata* [hash]. > 4. The node sends out the block in parallel to all 8 peers simultaneously= . > If the node's upstream bandwidth is limiting, then all peers will receive > most of the block before any peer receives all of the block. The block is > sent out as the small header followed by a list of transactions. > 5. Once a peer completes the download, it verifies the block, then enters > step 2. > > (If I'm missing anything, please let me know.) > > The main problem with this algorithm is that it requires a peer to have > the full block before it does any uploading to other peers in the p2p mes= h. > This slows down block propagation to O( p =E2=80=A2 log_p(n) ), where n i= s the > number of peers in the mesh, and p is the number of peers transmitted to > simultaneously. > > It's like the Napster era of file-sharing. We can do much better than > this. Bittorrent can be an example for us. Bittorrent splits the file to = be > shared into a bunch of chunks, and hashes each chunk. Downloaders (leeche= s) > grab the list of hashes, then start requesting their peers for the chunks > out-of-order. As each leech completes a chunk and verifies it against the > hash, it begins to share those chunks with other leeches. Total propagati= on > time for large files can be approximately equal to the transmission time > for an FTP upload. Sometimes it's significantly slower, but often it's > actually faster due to less bottlenecking on a single connection and bett= er > resistance to packet/connection loss. (This could be relevant for crossin= g > the Chinese border, since the Great Firewall tends to produce random pack= et > loss, especially on encrypted connections.) > > Bitcoin uses a data structure for transactions with hashes built-in. We > can use that in lieu of Bittorrent's file chunks. > > A Bittorrent-inspired algorithm might be something like this: > > 0. (Optional steps to build a Merkle cache; described later) > 1. A seed node mines a block. > 2. It notifies its peers that it has a new block with an extended version > of *inv*. > 3. The leech peers request the block header. > 4. The seed sends the block header. The leech code path splits into two. > 5(a). The leeches verify the block header, including the PoW. If the > header is valid, > 6(a). They notify their peers that they have a header for an unverified > new block with an extended version of *inv*, looping back to 2. above. If > it is invalid, they abort thread (b). > 5(b). The leeches request the Nth row (from the root) of the transaction > Merkle tree, where N might typically be between 2 and 10. That correspond= s > to about 1/4th to 1/1024th of the transactions. The leeches also request = a > bitfield indicating which of the Merkle nodes the seed has leaves for. Th= e > seed supplies this (0xFFFF...). > 6(b). The leeches calculate all parent node hashes in the Merkle tree, an= d > verify that the root hash is as described in the header. > 7. The leeches search their Merkle hash cache to see if they have the > leaves (transaction hashes and/or transactions) for that node already. > 8. The leeches send a bitfield request to the node indicating which Merkl= e > nodes they want the leaves for. > 9. The seed responds by sending leaves (either txn hashes or full > transactions, depending on benchmark results) to the leeches in whatever > order it decides is optimal for the network. > 10. The leeches verify that the leaves hash into the ancestor node hashes > that they already have. > 11. The leeches begin sharing leaves with each other. > 12. If the leaves are txn hashes, they check their cache for the actual > transactions. If they are missing it, they request the txns with a > *getdata*, or all of the txns they're missing (as a list) with a few > batch *getdata*s. > > The main feature of this algorithm is that a leech will begin to upload > chunks of data as soon as it gets them and confirms both PoW and hash/dat= a > integrity instead of waiting for a fully copy with full verification. > > This algorithm is more complicated than the existing algorithm, and won't > always be better in performance. Because more round trip messages are > required for negotiating the Merkle tree transfers, it will perform worse > in situations where the bandwidth to ping latency ratio is high relative = to > the blocksize. Specifically, the minimum per-hop latency will likely be > higher. This might be mitigated by reducing the number of round-trip > messages needed to set up the blocktorrent by using larger and more compl= ex > *inv*-like and *getdata*-like messages that preemptively send some data > (e.g. block headers). This would trade off latency for bandwidth overhead > from larger duplicated *inv* messages. Depending on implementation > quality, the latency for the smallest block size might be the same betwee= n > algorithms, or it might be 300% higher for the torrent algorithm. For sma= ll > blocks (perhaps < 100 kB), the blocktorrent algorithm will likely be > slightly slower. For large blocks (e.g. 8 MB over 20 Mbps), I expect the > blocktorrent algo will likely be around an order of magnitude faster in t= he > worst case (adversarial) scenarios, in which none of the block's > transactions are in the caches. > > One of the big benefits of the blocktorrent algorithm is that it provides > several obvious and straightforward points for bandwidth saving and > optimization by caching transactions and reconstructing the transaction > order. A cooperating miner can pre-announce Merkle subtrees with some of > the transactions they are planning on including in the final block. Other > miners who see those subtrees can compare the transactions in those > subtrees to the transaction sets they are mining with, and can rearrange > their block prototypes to use the same subtrees as much as possible. In t= he > case of public pools supporting the *getblocktemplate* protocol, it might > be possible to build Merkle subtree caches without the pool's help by > having one or more nodes just scraping their *getblocktemplate* results. > Even if some transactions are inserted or deleted, it may be possible to > guess a lot of the tree based on the previous ordering. > > Once a block header and the first few rows of the Merkle tree have been > published, they will propagate through the whole network, at which time > full nodes might even be able to guess parts of the tree by searching > through their txn and Merkle node/subtree caches. That might be fun to > think about, but probably not effective due to O(n^2) or worse scaling wi= th > transaction count. Might be able to make it work if the whole network > cooperates on it, but there are probably more important things to do. > > There are also a few other features of Bittorrent that would be useful > here, like prioritizing uploads to different peers based on their upload > capacity, and banning peers that submit data that doesn't hash to the rig= ht > value. (It might be good if we could get Bram Cohen to help with the > implementation.) > > Another option is just to treat the block as a file and literally > Bittorrent it, but I think that there should be enough benefits to > integrating it with the existing bitcoin p2p connections and also with > using bitcoind's transaction caches and Merkle tree caches to make a nati= ve > implementation worthwhile. Also, Bittorrent itself was designed to optimi= ze > more for bandwidth than for latency, so we will have slightly different > goals and tradeoffs during implementation. > > One of the concerns that I initially had about this idea was that it woul= d > involve nodes forwarding unverified block data to other nodes. At first, = I > thought this might be useful for a rogue miner or node who wanted to > quickly waste the whole network's bandwidth. However, in order to perform > this attack, the rogue needs to construct a valid header with a valid PoW= , > but use a set of transactions that renders the block as a whole invalid i= n > a manner that is difficult to detect without full verification. However, = it > will be difficult to design such an attack so that the damage in bandwidt= h > used has a greater value than the 240 exahashes (and 25.1 BTC opportunity > cost) associated with creating a valid header. > > As I understand it, the O(1) IBLT approach requires that blocks follow > strict rules (yet to be fully defined) about the transaction ordering. If > these are not followed, then it turns into sending a list of txn hashes, > and separately ensuring that all of the txns in the new block are already > in the recipient's mempool. When mempools are very dissimilar, the IBLT > approach performance degrades heavily and performance becomes worse than > simply sending the raw block. This could occur if a node just joined the > network, during chain reorgs, or due to malicious selfish miners. Also, i= f > the mempool has a lot more transactions than are included in the block, t= he > false positive rate for detecting whether a transaction already exists in > another node's mempool might get high for otherwise reasonable bucket > counts/sizes. > > With the blocktorrent approach, the focus is on transmitting the list of > hashes in a manner that propagates as quickly as possible while still > allowing methods for reducing the total bandwidth needed. The blocktorren= t > algorithm does not really address how the actual transaction data will be > obtained because, once the leech has the list of txn hashes, the standard > Bitcoin p2p protocol can supply them in a parallelized and decentralized > manner. > > > > Thoughts? > > -jtoomim > > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > > --089e01227f365e807c0520735b11 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
has anybody ever submitted a patch using libtorrent's = library for this purpose?
would it make sense to create a torrent per co= nfirmed valid block once it's been truly added to the blockchain?
if we used libtorrent, I imagine the following to announce the new block = on libtorrent's DHT

(PSEUDO CODE)

// this is how you could announce yourself as a peer on the DHT holding a = block at a certain height.
// the announ= cement would include a TCP port to then request more information about that= block.
string peer_announcement_key =3D sha1_hasher("blockc= hain::bitcoin::block::" + last_block_height_number).final();=C2=A0
= session.dht_announce(peer_announcement_key, rpc_port, 0);

// then an= other peer looking for peers that might be seeding a block at N height woul= d:
sessoin.dht_get_peers(sha1_hasher("blockchain::bitcoin::block::&= quot; + N_height).final());

// asynchronously you'd handle the r= esponses by the XOR-nearest peers on the DHT
// this search would= be O(log n)
// you could then request from several of these guys what&#= 39;s the infohash for the .torrent
// that's been created to = seed the block at height N.

then you'd start the block download = by building a magnet link out of the infohash received for the block.
Th= e download would be done directly to memory and then such byte array would = be serialized as a block
as it is done now, and you'd then an= nounce yourself both on the sha1(peer_announcement_key) and
on th= e infohash of the block you just downloaded, after you start seeding it.
perhaps the block's torrent chunk sizes could be made optimal so t= hat chunks sent would perfectly match
tranactions, this way you c= ould start building the blocks on the other end as they're being downlo= aded from the swarm.


http://twitter.com/gubatron

On Wed, Sep 23, 2015 at 7:12 PM, Jonathan To= omim (Toomim Bros) via bitcoin-dev <bitcoin-dev@lists.= linuxfoundation.org> wrote:


As I understand it, the current block propagation algorithm is this= :

1. A node mines a block.
2. It notifie= s its peers that it has a new block with an=C2=A0inv. Typical nodes = have 8 peers.=C2=A0
3. The peers respond that they have not seen = it, and request the block with=C2=A0getdata=C2=A0[hash].=C2=A0
=
4. The node sends out the block in parallel to all 8 peers simultaneou= sly. If the node's upstream bandwidth is limiting, then all peers will = receive most of the block before any peer receives all of the block. The bl= ock is sent out as the small header followed by a list of transactions.
5. Once a peer completes the download, it verifies the block, then e= nters step 2.

(If I'm missing anything, please= let me know.)

The main problem with this algorith= m is that it requires a peer to have the full block before it does any uplo= ading to other peers in the p2p mesh. This slows down block propagation to = O( p =E2=80=A2 log_p(n) ), where n is the number of peers in the mesh, and = p is the number of peers transmitted to simultaneously.=C2=A0
It's like the Napster era of file-sharing. We can do much b= etter than this. Bittorrent can be an example for us. Bittorrent splits the= file to be shared into a bunch of chunks, and hashes each chunk. Downloade= rs (leeches) grab the list of hashes, then start requesting their peers for= the chunks out-of-order. As each leech completes a chunk and verifies it a= gainst the hash, it begins to share those chunks with other leeches. Total = propagation time for large files can be approximately equal to the transmis= sion time for an FTP upload. Sometimes it's significantly slower, but o= ften it's actually faster due to less bottlenecking on a single connect= ion and better resistance to packet/connection loss. (This could be relevan= t for crossing the Chinese border, since the Great Firewall tends to produc= e random packet loss, especially on encrypted connections.)

<= /div>
Bitcoin uses a data structure for transactions with hashes built-= in. We can use that in lieu of Bittorrent's file chunks.

=
A Bittorrent-inspired algorithm might be something like this:

0. (Optional steps to build a Merkle cache; describe= d later)
1. A seed node mines a block.
2. It notifies i= ts peers that it has a new block with an extended version of=C2=A0inv.=C2=A0
3. The leech peers request the block header.=C2=A0
=
4. The seed sends the block header. The leech code path splits into tw= o.
5(a). The leeches verify the block header, including the PoW. = If the header is valid,
6(a). They notify their peers that they h= ave a header for an unverified new block with an extended version of=C2=A0<= i>inv, looping back to 2. above.=C2=A0If it is invalid, they abort thre= ad (b).
5(b). The leeches request the Nth row (from the root) of = the transaction Merkle tree, where N might typically be between 2 and 10. T= hat corresponds to about 1/4th to 1/1024th of the transactions. The leeches= also request a bitfield indicating which of the Merkle nodes the seed has = leaves for. The seed supplies this (0xFFFF...).
6(b). The lee= ches calculate all parent node hashes in the Merkle tree, and verify that t= he root hash is as described in the header.
7. The leeches se= arch their Merkle hash cache to see if they have the leaves (transaction ha= shes and/or transactions) for that node already.
8. The leeches s= end a bitfield request to the node indicating which Merkle nodes they want = the leaves for.=C2=A0
9. The seed responds by sending leaves (eit= her txn hashes or full transactions, depending on benchmark results) to the= leeches in whatever order it decides is optimal for the network.
10. The leeches verify that the leaves hash into the ancestor node hashes = that they already have.=C2=A0
11. The leeches begin sharing leave= s with each other.
12. If the leaves are txn hashes, they check t= heir cache for the actual transactions. If they are missing it, they reques= t the txns with a=C2=A0getdata, or all of the txns they're missi= ng (as a list) with a few batch=C2=A0getdatas.=C2=A0

<= /div>
The main feature of this algorithm is that a leech will begin to = upload chunks of data as soon as it gets them and confirms both PoW and has= h/data integrity instead of waiting for a fully copy with full verification= .=C2=A0

This algorithm is more complicated than th= e existing algorithm, and won't always be better in performance. Becaus= e more round trip messages are required for negotiating the Merkle tree tra= nsfers, it will perform worse in situations where the bandwidth to ping lat= ency ratio is high relative to the blocksize. Specifically, the minimum per= -hop latency will likely be higher. This might be mitigated by reducing the= number of round-trip messages needed to set up the blocktorrent by using l= arger and more complex=C2=A0inv-like and=C2=A0getdata-like me= ssages that preemptively send some data (e.g. block headers). This would tr= ade off latency for bandwidth overhead from larger duplicated=C2=A0inv=C2=A0messages. Depending on implementation quality, the latency for the = smallest block size might be the same between algorithms, or it might be 30= 0% higher for the torrent algorithm. For small blocks (perhaps < 100 kB)= , the blocktorrent algorithm will likely be slightly slower. For large bloc= ks (e.g. 8 MB over 20 Mbps), I expect the blocktorrent algo will likely be = around an order of magnitude faster in the worst case (adversarial) scenari= os, in which none of the block's transactions are in the caches.
<= div>
One of the big benefits of the blocktorrent algorithm is= that it provides several obvious and straightforward points for bandwidth = saving and optimization by caching transactions and reconstructing the tran= saction order. A cooperating miner can pre-announce Merkle subtrees with so= me of the transactions they are planning on including in the final block. O= ther miners who see those subtrees can compare the transactions in those su= btrees to the transaction sets they are mining with, and can rearrange thei= r block prototypes to use the same subtrees as much as possible. In the cas= e of public pools supporting the=C2=A0getblocktemplate=C2=A0protocol= , it might be possible to build Merkle subtree caches without the pool'= s help by having one or more nodes just scraping their=C2=A0getblocktemp= late=C2=A0results. Even if some transactions are inserted or deleted, i= t may be possible to guess a lot of the tree based on the previous ordering= .

Once a block header and the first few rows of th= e Merkle tree have been published, they will propagate through the whole ne= twork, at which time full nodes might even be able to guess parts of the tr= ee by searching through their txn and Merkle node/subtree caches. That migh= t be fun to think about, but probably not effective due to O(n^2) or worse = scaling with transaction count. Might be able to make it work if the whole = network cooperates on it, but there are probably more important things to d= o.

There are also a few other features of Bittorre= nt that would be useful here, like prioritizing uploads to different peers = based on their upload capacity, and banning peers that submit data that doe= sn't hash to the right value. (It might be good if we could get Bram Co= hen to help with the implementation.)

Another opti= on is just to treat the block as a file and literally Bittorrent it, but I = think that there should be enough benefits to integrating it with the exist= ing bitcoin p2p connections and also with using bitcoind's transaction = caches and Merkle tree caches to make a native implementation worthwhile. A= lso, Bittorrent itself was designed to optimize more for bandwidth than for= latency, so we will have slightly different goals and tradeoffs during imp= lementation.

One of the concerns that I initially = had about this idea was that it would involve nodes forwarding unverified b= lock data to other nodes. At first, I thought this might be useful for a ro= gue miner or node who wanted to quickly waste the whole network's bandw= idth. However, in order to perform this attack, the rogue needs to construc= t a valid header with a valid PoW, but use a set of transactions that rende= rs the block as a whole invalid in a manner that is difficult to detect wit= hout full verification. However, it will be difficult to design such an att= ack so that the damage in bandwidth used has a greater value than the 240 e= xahashes (and 25.1 BTC opportunity cost) associated with creating a valid h= eader.

As I understand it, the O(1) IBLT appr= oach requires that blocks follow strict rules (yet to be fully defined) abo= ut the transaction ordering. If these are not followed, then it turns into = sending a list of txn hashes, and separately ensuring that all of the txns = in the new block are already in the recipient's mempool. When mempools = are very dissimilar, the IBLT approach performance degrades heavily and per= formance becomes worse than simply sending the raw block. This could occur = if a node just joined the network, during chain reorgs, or due to malicious= selfish miners. Also, if the mempool has a lot more transactions than are = included in the block, the false positive rate for detecting whether a tran= saction already exists in another node's mempool might get high for oth= erwise reasonable bucket counts/sizes.

With = the blocktorrent approach, the focus is on transmitting the list of hashes = in a manner that propagates as quickly as possible while still allowing met= hods for reducing the total bandwidth needed. The blocktorrent algorithm do= es not really address how the actual transaction data will be obtained beca= use, once the leech has the list of txn hashes, the standard Bitcoin p2p pr= otocol can supply them in a parallelized and decentralized manner.=C2=A0



Thoughts?
-jtoomim


___________= ____________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.= linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev


--089e01227f365e807c0520735b11--