summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAngel Leon <gubatron@gmail.com>2015-09-23 20:31:27 -0400
committerbitcoindev <bitcoindev@gnusha.org>2015-09-24 00:31:52 +0000
commitfa9053277a20a7570f9dc5e7ede80b0027e2c99b (patch)
treed63d5180816b41dc7c5b4d581fe6b174d7a17d3b
parentb2c4a3ec2b8822b31fdcf64f81fe4341650d4a6f (diff)
downloadpi-bitcoindev-fa9053277a20a7570f9dc5e7ede80b0027e2c99b.tar.gz
pi-bitcoindev-fa9053277a20a7570f9dc5e7ede80b0027e2c99b.zip
Re: [bitcoin-dev] Torrent-style new-block propagation on Merkle trees
-rw-r--r--6c/20084428bec47027008ab89b2161dce118a8b3516
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&#39;s =
+library for this purpose?<br>would it make sense to create a torrent per co=
+nfirmed valid block once it&#39;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&#39;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(&quot;blockc=
+hain::bitcoin::block::&quot; + 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(&quot;blockchain::bitcoin::block::&=
+quot; + N_height).final());<br><br>// asynchronously you&#39;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&#39;s been created to =
+seed the block at height N.<br><br>then you&#39;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&#39;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&#39;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&#39;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">&lt;<a href=3D"mailto:=
+bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin-dev@lists.=
+linuxfoundation.org</a>&gt;</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&#39;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&#39;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&#39;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&#39;s significantly slower, but o=
+ften it&#39;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&#39;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&#39;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&#39;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 &lt; 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&#39;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&#39;=
+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&#39;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&#39;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&#39;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&#39;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&#39;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--
+