path: root/49/5ca9ee2a01e288d7e0d06d34a7bbff664809ca

Return-Path: <j@toom.im>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 5DE9619C6
	for <bitcoin-dev@lists.linuxfoundation.org>;
	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 <bitcoin-dev@lists.linuxfoundation.org>;
	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)" <j@toom.im>
In-Reply-To: <CAPswA9xei1UNMeNqi=XzSnZU=SeroaeKN_6xHJ0HfhgXBzY_mw@mail.gmail.com>
Date: Mon, 28 Sep 2015 06:30:22 -0700
Message-Id: <8166B5CA-BE2A-444E-B826-BFA18F4C4757@toom.im>
References: <CABsx9T2+dG0AE+MgKRAU97KhkHTU1MuxXuwHKv3BgpJswZ5vVg@mail.gmail.com>
	<CABaSBaxcDRzw0X7-fAfxPJyLcWxTHigpHuAPb4aNQ5zk5NoDCQ@mail.gmail.com>
	<CAAS2fgTr-OuL3T6mXX-4xFC_LHnAiogTTcPMbcjsM7WtRisQEQ@mail.gmail.com>
	<CABsx9T3NFRO5nw3z=jrs0Hu3caVNkkTTTb1ibqR7LMWsoou9RQ@mail.gmail.com>
	<CAAS2fgRj+fE+znXZzFsXXBivKSxnJ2Lheo_g9us4FXN_yCLhgw@mail.gmail.com>
	<CAE-z3OU50cZBR27QrQsRT5Gtb0AVkE6K33XR0GebsyNWNrbf+w@mail.gmail.com>
	<CAPswA9xFNgdbH1JXBx+CqjT5HbkK0WGaWQLrJzm+BJCmrXRQcA@mail.gmail.com>
	<CAAS2fgRX-LLiNwcmbHtF6ymEX+uUx3SNjqAe4iyxouhHj=4Abw@mail.gmail.com>
	<CAPswA9xei1UNMeNqi=XzSnZU=SeroaeKN_6xHJ0HfhgXBzY_mw@mail.gmail.com>
To: Kalle Rosenbaum <kalle@rosenbaum.se>
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 <bitcoin-dev@lists.linuxfoundation.org>
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 <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: 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 =
<bitcoin-dev@lists.linuxfoundation.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.
>=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

<html><head><meta http-equiv=3D"Content-Type" content=3D"text/html =
charset=3Dus-ascii"></head><body style=3D"word-wrap: break-word; =
-webkit-nbsp-mode: space; -webkit-line-break: =
after-white-space;"><br><div><div>On Sep 28, 2015, at 1:30 AM, Kalle =
Rosenbaum via bitcoin-dev &lt;<a =
href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.li=
nuxfoundation.org</a>&gt; wrote:</div><br =
class=3D"Apple-interchange-newline"><blockquote type=3D"cite"><div =
style=3D"font-family: Helvetica; font-size: 12px; font-style: normal; =
font-variant: normal; font-weight: normal; letter-spacing: normal; =
line-height: normal; orphans: auto; text-align: start; text-indent: 0px; =
text-transform: none; white-space: normal; widows: auto; word-spacing: =
0px; -webkit-text-stroke-width: 0px;">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.<br></div><br =
class=3D"Apple-interchange-newline"></blockquote></div><br><div>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.</div><div><br></div><div>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.</div><div><br></div><div>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:&nbsp;<a =
href=3D"http://bitcoin-development.narkive.com/dGIxjVI5/torrent-style-new-=
block-propagation-on-merkle-trees">http://bitcoin-development.narkive.com/=
dGIxjVI5/torrent-style-new-block-propagation-on-merkle-trees</a></div><div=
><br></div><div>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.</div><div><br></div><div>Or maybe there's a better =
way.</div></body></html>=

--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--