Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 5DE9619C6 for ; Mon, 28 Sep 2015 13:30:30 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from d.mail.sonic.net (d.mail.sonic.net [64.142.111.50]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 88B2F20D for ; Mon, 28 Sep 2015 13:30:27 +0000 (UTC) Received: from [192.168.1.190] (63.135.62.197.nwinternet.com [63.135.62.197] (may be forged)) (authenticated bits=0) by d.mail.sonic.net (8.15.1/8.15.1) with ESMTPSA id t8SDUNY6002725 (version=TLSv1 cipher=DHE-RSA-AES128-SHA bits=128 verify=NOT); Mon, 28 Sep 2015 06:30:25 -0700 Mime-Version: 1.0 (Mac OS X Mail 7.3 \(1878.6\)) Content-Type: multipart/signed; boundary="Apple-Mail=_BE80341B-FA0E-4F83-BAFD-DAA2A1AFA646"; protocol="application/pgp-signature"; micalg=pgp-sha512 X-Pgp-Agent: GPGMail 2.5.1 From: "Jonathan Toomim (Toomim Bros)" In-Reply-To: Date: Mon, 28 Sep 2015 06:30:22 -0700 Message-Id: <8166B5CA-BE2A-444E-B826-BFA18F4C4757@toom.im> References: To: Kalle Rosenbaum X-Mailer: Apple Mail (2.1878.6) X-Sonic-CAuth: UmFuZG9tSVbI5KeT9z1TJtWA3ItUdZkBI8Vy2wGm+yry7+eBEoghET+zNklwVhUcqCDdKOTCN2k70qZCvw3JCyWMRzwQEgLA X-Sonic-ID: C;9BdzEuVl5RG52+K7sH9FTg== M;3CRfE+Vl5RG52+K7sH9FTg== X-Sonic-Spam-Details: 0.0/5.0 by cerberusd X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,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] Weak block thoughts... 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: Mon, 28 Sep 2015 13:30:30 -0000 --Apple-Mail=_BE80341B-FA0E-4F83-BAFD-DAA2A1AFA646 Content-Type: multipart/alternative; boundary="Apple-Mail=_D625F09C-874C-484E-899B-A4ACBEC8A118" --Apple-Mail=_D625F09C-874C-484E-899B-A4ACBEC8A118 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=us-ascii On Sep 28, 2015, at 1:30 AM, Kalle Rosenbaum via bitcoin-dev = wrote: > Suppose that you've solved a block Z (weak or not) and you want to = propagate it using a previous weak block Y. With "efficient differential = transmission", I assume that you refer to the transmission of the = differences between Y and Z to a peer? What encodings are discussed? I = guess IBLTs are a hot candidate, but are there other schemes in the = making? I suppose that sending something like "weak block Y plus = transactions A, B, C minus transaction ids h(D), h(E)" is not considered = an efficient differential transmission. Then that's part of the answer = to my question. >=20 IBLTs are effective for synchronizing mempools, to ensure that all nodes = in a network can successfully map a transaction hash to a full = transaction. However, IBLTs do not help with the ordering of the = transactions. Encoding the new blocks as a diff (delete bytes x through y, insert = string s after byte z) based on a weak block would probably be pretty = effective, but it would probably require a lot of memory for keeping a = weak block (or chain of diffs) for each miner that publishes weak = blocks. It might be a little complicated to manage and remove duplicate = information between weak blocks published by different sources. You'd = probably have to build a weak block tree or DAG with diffs as edges, and = walk the tree each time you wanted to fetch a (weak) block. Another strategy is to use the Merkle tree nodes. Each node is a hash of = its concatenated child nodes, Each node thus specifies the order of 2^n = transaction hashes. Changing one transaction hash requires modifying = log_2(n) Merkle node hashes, which is okay but maybe not as good as the = diff approach. However, the main benefit comes from compressing and = storing data from many different weak blocks generated by different = miners. You can build a cache of Merkle nodes, and each time you get a = new weak block, you can add any new Merkle nodes to that cache. There's = some more info on this here: = http://bitcoin-development.narkive.com/dGIxjVI5/torrent-style-new-block-pr= opagation-on-merkle-trees Merkle tree encodings handle replacements of transactions well, but they = have trouble with insertions or deletions near the beginning of a block. = Efforts could be made to avoid insertions and deletions in the actual = transaction ordering to improve transmissibility, or a hybrid system = could be implemented in which byte-level diffs or transaction-level = diffs are used for transmitting the weak blocks as a diff against = previously cached Merkle nodes. Or maybe there's a better way. --Apple-Mail=_D625F09C-874C-484E-899B-A4ACBEC8A118 Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset=us-ascii
On Sep 28, 2015, at 1:30 AM, Kalle = Rosenbaum via bitcoin-dev <bitcoin-dev@lists.li= nuxfoundation.org> wrote:

Suppose that you've solved a block = Z (weak or not) and you want to propagate it using a previous weak block = Y. With "efficient differential transmission", I assume that you refer = to the transmission of the differences between Y and Z to a peer? What = encodings are discussed? I guess IBLTs are a hot candidate, but are = there other schemes in the making? I suppose that sending something like = "weak block Y plus transactions A, B, C minus transaction ids h(D), = h(E)" is not considered an efficient differential transmission. Then = that's part of the answer to my question.


IBLTs = are effective for synchronizing mempools, to ensure that all nodes in a = network can successfully map a transaction hash to a full transaction. = However, IBLTs do not help with the ordering of the = transactions.

Encoding the new blocks as a diff = (delete bytes x through y, insert string s after byte z) based on a weak = block would probably be pretty effective, but it would probably require = a lot of memory for keeping a weak block (or chain of diffs) for each = miner that publishes weak blocks. It might be a little complicated to = manage and remove duplicate information between weak blocks published by = different sources. You'd probably have to build a weak block tree or DAG = with diffs as edges, and walk the tree each time you wanted to fetch a = (weak) block.

Another strategy is to use the = Merkle tree nodes. Each node is a hash of its concatenated child nodes, = Each node thus specifies the order of 2^n transaction hashes. Changing = one transaction hash requires modifying log_2(n) Merkle node hashes, = which is okay but maybe not as good as the diff approach. However, the = main benefit comes from compressing and storing data from many different = weak blocks generated by different miners. You can build a cache of = Merkle nodes, and each time you get a new weak block, you can add any = new Merkle nodes to that cache. There's some more info on this = here: http://bitcoin-development.narkive.com/= dGIxjVI5/torrent-style-new-block-propagation-on-merkle-trees

Merkle tree encodings handle replacements of = transactions well, but they have trouble with insertions or deletions = near the beginning of a block. Efforts could be made to avoid insertions = and deletions in the actual transaction ordering to improve = transmissibility, or a hybrid system could be implemented in which = byte-level diffs or transaction-level diffs are used for transmitting = the weak blocks as a diff against previously cached Merkle = nodes.

Or maybe there's a better = way.
= --Apple-Mail=_D625F09C-874C-484E-899B-A4ACBEC8A118-- --Apple-Mail=_BE80341B-FA0E-4F83-BAFD-DAA2A1AFA646 Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename=signature.asc Content-Type: application/pgp-signature; name=signature.asc Content-Description: Message signed with OpenPGP using GPGMail -----BEGIN PGP SIGNATURE----- Comment: GPGTools - https://gpgtools.org iQEcBAEBCgAGBQJWCUDvAAoJEIEuMk4MG0P1CZwH/0ITqza78cp6QvJx6gBqeHf+ h2/PkxY91b0IJ0pos6IwwjIG/PqpGYM4CeQkti+l1z1JSnbvfwh5vG48iCsBXmxG Q744YaBv1V2SEDd5eCxg6Q5s2Q6YFTvvV/kYXojn067z97DiWcZUcQ2EWg9eZ6pq YDrJ6IiMnrK0PLFKsIaLdanC4+EOguNr6SRgd2O9yWCkb7gQ5YtrIbOwQNsQI5G6 3uXXm0YbsZY+WUB8ERedqxkFdxuEgWFLn4zkDZuIJ40bcQPeAEGGsB4H/zzMpwTB G6BhAXeQlnGdUCGJOarNLbNxfV178FE82x9xjBGT3BK27IYfyiRV1Md1uXegiME= =MdZu -----END PGP SIGNATURE----- --Apple-Mail=_BE80341B-FA0E-4F83-BAFD-DAA2A1AFA646--