diff options
author | Angel Leon <gubatron@gmail.com> | 2015-09-23 20:31:27 -0400 |
---|---|---|
committer | bitcoindev <bitcoindev@gnusha.org> | 2015-09-24 00:31:52 +0000 |
commit | fa9053277a20a7570f9dc5e7ede80b0027e2c99b (patch) | |
tree | d63d5180816b41dc7c5b4d581fe6b174d7a17d3b | |
parent | b2c4a3ec2b8822b31fdcf64f81fe4341650d4a6f (diff) | |
download | pi-bitcoindev-fa9053277a20a7570f9dc5e7ede80b0027e2c99b.tar.gz pi-bitcoindev-fa9053277a20a7570f9dc5e7ede80b0027e2c99b.zip |
Re: [bitcoin-dev] Torrent-style new-block propagation on Merkle trees
-rw-r--r-- | 6c/20084428bec47027008ab89b2161dce118a8b3 | 516 |
1 files changed, 516 insertions, 0 deletions
diff --git a/6c/20084428bec47027008ab89b2161dce118a8b3 b/6c/20084428bec47027008ab89b2161dce118a8b3 new file mode 100644 index 000000000..6606d1a43 --- /dev/null +++ b/6c/20084428bec47027008ab89b2161dce118a8b3 @@ -0,0 +1,516 @@ +Return-Path: <gubatron@gmail.com> +Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org + [172.17.192.35]) + by mail.linuxfoundation.org (Postfix) with ESMTPS id 17006A6E + for <bitcoin-dev@lists.linuxfoundation.org>; + 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 <bitcoin-dev@lists.linuxfoundation.org>; + Thu, 24 Sep 2015 00:31:50 +0000 (UTC) +Received: by igbkq10 with SMTP id kq10so110867663igb.0 + for <bitcoin-dev@lists.linuxfoundation.org>; + 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 <gubatron@gmail.com> +Date: Wed, 23 Sep 2015 20:31:27 -0400 +Message-ID: <CADZB0_ZCmWdj+mD5O-CR6a6w0RWZhgUL_TRu7Jzth=kvK504xw@mail.gmail.com> +To: "Jonathan Toomim (Toomim Bros)" <j@toom.im> +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 <bitcoin-dev@lists.linuxfoundation.org> +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 <bitcoin-dev.lists.linuxfoundation.org> +List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, + <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe> +List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/> +List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org> +List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help> +List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, + <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=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 <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 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 + +<div dir=3D"ltr">has anybody ever submitted a patch using libtorrent's = +library for this purpose?<br>would it make sense to create a torrent per co= +nfirmed valid block once it's been truly added to the blockchain?<br><b= +r>if we used libtorrent, I imagine the following to announce the new block = +on libtorrent's DHT<br><br>(PSEUDO CODE)<br><br><font color=3D"#999999"= +>// this is how you could announce yourself as a peer on the DHT holding a = +block at a certain height.</font><div><font color=3D"#999999">// the announ= +cement would include a TCP port to then request more information about that= + block.<br></font>string peer_announcement_key =3D sha1_hasher("blockc= +hain::bitcoin::block::" + last_block_height_number).final();=C2=A0<br>= +session.dht_announce(peer_announcement_key, rpc_port, 0);<br><br>// then an= +other peer looking for peers that might be seeding a block at N height woul= +d:<br>sessoin.dht_get_peers(sha1_hasher("blockchain::bitcoin::block::&= +quot; + N_height).final());<br><br>// asynchronously you'd handle the r= +esponses by the XOR-nearest peers on the DHT</div><div>// this search would= + be O(log n)<br>// you could then request from several of these guys what&#= +39;s the infohash for the .torrent</div><div>// that's been created to = +seed the block at height N.<br><br>then you'd start the block download = +by building a magnet link out of the infohash received for the block.<br>Th= +e download would be done directly to memory and then such byte array would = +be serialized as a block</div><div>as it is done now, and you'd then an= +nounce yourself both on the sha1(peer_announcement_key) and</div><div>on th= +e infohash of the block you just downloaded, after you start seeding it.<br= +><br>perhaps the block's torrent chunk sizes could be made optimal so t= +hat chunks sent would perfectly match</div><div>tranactions, this way you c= +ould start building the blocks on the other end as they're being downlo= +aded from the swarm.<br><br></div></div><div class=3D"gmail_extra"><br clea= +r=3D"all"><div><div class=3D"gmail_signature"><a href=3D"http://twitter.com= +/gubatron" target=3D"_blank">http://twitter.com/gubatron</a><br></div></div= +> +<br><div class=3D"gmail_quote">On Wed, Sep 23, 2015 at 7:12 PM, Jonathan To= +omim (Toomim Bros) via bitcoin-dev <span dir=3D"ltr"><<a href=3D"mailto:= +bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin-dev@lists.= +linuxfoundation.org</a>></span> wrote:<br><blockquote class=3D"gmail_quo= +te" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"= +><div style=3D"word-wrap:break-word"><br><div><div dir=3D"ltr"><div><br></d= +iv><div>As I understand it, the current block propagation algorithm is this= +:</div><div><br></div><div>1. A node mines a block.</div><div>2. It notifie= +s its peers that it has a new block with an=C2=A0<i>inv</i>. Typical nodes = +have 8 peers.=C2=A0</div><div>3. The peers respond that they have not seen = +it, and request the block with=C2=A0<i>getdata</i>=C2=A0[hash].=C2=A0</div>= +<div>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.</di= +v><div>5. Once a peer completes the download, it verifies the block, then e= +nters step 2.</div><div><br></div><div>(If I'm missing anything, please= + let me know.)</div><div><br></div><div>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</div><div><br= +></div><div>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><div><br><= +/div><div>Bitcoin uses a data structure for transactions with hashes built-= +in. We can use that in lieu of Bittorrent's file chunks.</div><div><br>= +</div><div>A Bittorrent-inspired algorithm might be something like this:</d= +iv><div><br></div><div>0. (Optional steps to build a Merkle cache; describe= +d later)</div><div>1. A seed node mines a block.</div><div>2. It notifies i= +ts peers that it has a new block with an extended version of=C2=A0<i>inv</i= +>.=C2=A0</div><div>3. The leech peers request the block header.=C2=A0</div>= +<div>4. The seed sends the block header. The leech code path splits into tw= +o.</div><div>5(a). The leeches verify the block header, including the PoW. = +If the header is valid,</div><div>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</i>, looping back to 2. above.=C2=A0If it is invalid, they abort thre= +ad (b).</div><div>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...).<br></div><div>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.<br></div><div>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.</div><div>8. The leeches s= +end a bitfield request to the node indicating which Merkle nodes they want = +the leaves for.=C2=A0</div><div>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.</div><div= +>10. The leeches verify that the leaves hash into the ancestor node hashes = +that they already have.=C2=A0</div><div>11. The leeches begin sharing leave= +s with each other.</div><div>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=A0<i>getdata</i>, or all of the txns they're missi= +ng (as a list) with a few batch=C2=A0<i>getdata</i>s.=C2=A0</div><div><br><= +/div><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</div><div><br></div><div>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=A0<i>inv</i>-like and=C2=A0<i>getdata</i>-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=A0<i>inv</= +i>=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><= +div><br></div><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=A0<i>getblocktemplate</i>=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=A0<i>getblocktemp= +late</i>=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= +.</div><div><br></div><div>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.</div><div><br></div><div>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.)</div><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div><div>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.</div></div><div><br></div><div>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</d= +iv><div><br></div><div><br></div><div><br></div><div>Thoughts?</div><div><b= +r></div><div>-jtoomim</div></div><div><br></div></div></div><br>___________= +____________________________________<br> +bitcoin-dev mailing list<br> +<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.= +linuxfoundation.org</a><br> +<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" = +rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail= +man/listinfo/bitcoin-dev</a><br> +<br></blockquote></div><br></div> + +--089e01227f365e807c0520735b11-- + |