path: root/d1/cc9a5708b977d3530e76fd304a87562d4a1b8c

Return-Path: <tier.nolan@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 21500C9B
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon, 29 Feb 2016 11:49:59 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-vk0-f50.google.com (mail-vk0-f50.google.com
	[209.85.213.50])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 09D61106
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon, 29 Feb 2016 11:49:58 +0000 (UTC)
Received: by mail-vk0-f50.google.com with SMTP id e6so130716252vkh.2
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon, 29 Feb 2016 03:49:57 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
	h=mime-version:in-reply-to:references:date:message-id:subject:from:cc; 
	bh=gU3OFvg7ky5h93zCX6Uxo2uSFxg5H621SBWs6QKfOs0=;
	b=0wvBOlbOaHyHKwZDoKUKPmnQ9ORJgeEU5iLTHEK1cFZFjOxzfxQZPOAjJxXN/oeWRm
	UzJRMHWYRJR8URw2qMXUF1ZfU9pZifUCkrVrA6o59EPOeqB4gkpPpq5St/OgNk11WHM7
	idk5bAg/jOMvnrTGSTy7/PcwHGW5Qsylu2da2Wm89EbmG5p1NC8Uinbk51Nr/7Kew4Y9
	Nzv8eHKSMXzeJaoQc/4AndhV75W2Q2AmhaMK1VAulmMB+9fGYx/uScmBsxT+BiLYWkDe
	OdWXdRtL40rx5aQwlvB/wUtfkIXTacaS1eTwZJ1xJHfku0p0/aHfB94QUGV4dWc9MYjX
	TpGw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=1e100.net; s=20130820;
	h=x-gm-message-state:mime-version:in-reply-to:references:date
	:message-id:subject:from:cc;
	bh=gU3OFvg7ky5h93zCX6Uxo2uSFxg5H621SBWs6QKfOs0=;
	b=TvZ6wyi6TZtz2wdX/215HfU3T3Ej5JhWTKKEC+JnOvojPa0qV9XUoNnXtCxcixxZXW
	h/zpozf9Pwt0XgOadqkGCqPiDS7/BvFdsHWbFZQFCBGloRA+WrNKeXQGiv3gSM866Wox
	LQDz45dSpa8GmEJaO4nnX0NdiPBTIcT9fcNpmWY+vomS+lNoJ8LzcnUsv8nr5WCQjjbW
	KPM4kfoILjpzRUG9fBkIdFX6lqSVRUEW8L3aVdX3+aytfzeXnSvSrnhxzUzVW3+hlZal
	e8eBWK7qv4ysKweMVtYBebOKnxtlAzByKnvSSOg2yAiWQgpPF9BDOlE6Kr6lFYl5gPCB
	KFMg==
X-Gm-Message-State: AD7BkJKlkm1MYF3rWKTdhWrWmvR6HoO+1dU6VWBvjM2SGgOUb3EVbgjezvAHqrABHQYMxCBGY4dZF/7aDXKftQ==
MIME-Version: 1.0
X-Received: by 10.31.150.215 with SMTP id y206mr10905317vkd.63.1456746597116; 
	Mon, 29 Feb 2016 03:49:57 -0800 (PST)
Received: by 10.159.37.137 with HTTP; Mon, 29 Feb 2016 03:49:57 -0800 (PST)
In-Reply-To: <56D41D71.80503@jonasschnelli.ch>
References: <56D41D71.80503@jonasschnelli.ch>
Date: Mon, 29 Feb 2016 11:49:57 +0000
Message-ID: <CAE-z3OXb3BCg37erbHuWRxy_x1dCGpQYy0-ObDBctmXUzASo8g@mail.gmail.com>
From: Tier Nolan <tier.nolan@gmail.com>
Cc: Bitcoin development mailing list <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary=001a1140fdd872f40c052ce73fbb
X-Spam-Status: No, score=-1.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,HTML_MESSAGE,MISSING_HEADERS,
	RCVD_IN_DNSWL_LOW autolearn=no version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
	smtp1.linux-foundation.org
Subject: Re: [bitcoin-dev] Fast bootstrapping with a pre-generated UTXO-set
	database
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, 29 Feb 2016 11:49:59 -0000

--001a1140fdd872f40c052ce73fbb
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

One of the proposals was to build the UTXO set backwards.  You start from
the newest block and work backwards.

The database contains UTXOs (unspent transaction outputs) and "UFTXI"
(unfunded transaction inputs).

The procedure would be

For each transaction (last to first ordering)
    For each output
        - check if it is in the UFTXI set
        -- If so, validate the signatures
        -- If not, add it to the UTXO set

    For each input
        - Add to the UFTXI set

When you receive a transaction, it checks all the inputs
-- If all inputs are in the UTXO set, it says confirmed
-- Otherwise, gets marked as "unknown inputs"

There would also be a counter indicating how many blocks it has validated.

A transaction with an unfunded input counts as validated back to the block
it was included in.  Transactions count as confirmed to their ancestor that
has the newest validation time.

Assume that the node had validated the last 10000 blocks and you had a
transaction with one input.  Assume the input transaction was included 5000
blocks ago and its input was included 50,000 blocks ago.

TX-A) input (TX-B:0) included in block 6 blocks ago
TX-B) input (TX-C:0) included in block 5000 ago
TX-C) input (TX-B:0) included in block 20000 ago

TX-C would not be known to the node since it has only gone back 10000
blocks.

TX-A would have confirms 6 / 5000.  This means that its outputs have been
confirmed by 6 blocks (confirms work as currently) and that its inputs have
been confirmed by 5000 blocks.

The reference client could mark transactions with 6+ output confirms and
1000+ input confirms as confirmed.

Once it hits the genesis block, then all transactions would be
6/<infinity>, so it could drop the second number.


On Mon, Feb 29, 2016 at 10:29 AM, Jonas Schnelli via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA256
>
> Hi
>
> I=E2=80=99ve been thinking around a solution to reduce nodes bootstrap ti=
me
> (IBD) as well as a way to reduce the amount of bandwidth/network usage
> per node.
> Not sure if this idea was/is already discussed, haven=E2=80=99t found any=
thing
> in a quick research.
>
>
> =3D=3DTitle=3D=3D
> Fast bootstrapping with a pre-generated UTXO-set database.
>
> =3D=3DAbstract=3D=3D
> This documents describes a way how bitcoin nodes can bootstrap faster
> by loading a pre-generated UTXO-set datafile with moderate reduction
> of the security model.
>
> =3D=3DSpecification=3D=3D
> Bitcoin-core or any other full node client will need to provide a
> feature to "freeze" the UTXO-set at a specified height (will require a
> reindex). The frozen UTXO-set =E2=80=93 at a specific height =E2=80=93 wi=
ll be
> deterministic linearized in a currently not specified
> data-serializing-format.
> Additionally, a serialized form of the current chain-index (chain
> containing all block-headers) up to the specified height will be
> appended to the pre-generated UTXO-set-datafile.
> The datafile will be hashed with a double SHA256.
>
> The corresponding hash will be produced/reproduced and signed (ECDSA)
> by a group of developers, ideally the same group of developers who are
> also signing deterministic builds (binary distribution).
>
> Full node client implementations that supports bootstrapping from a
> pre-generated UTXO-set, need to include...
> 1.) a set of pubkeys from trusted developers
> 2.) the hash (or hashes) of the pre-generated UTXO-set-datafile(s)
> 3.) n signatures of the hash(es) from 2) from a subset of developers
> defined in 1)
>
> To guarantee the integrity of developers pubkeys & signatures, methods
> like the current gitian build, used in bitcoin-core, must be used.
>
> New nodes could download a copy of the pre-generated UTXO-set, hash
> it, verify the hash against the allowed UTXO-sets, verify the ECDSA
> signatures from various developers, and continue bootstrapping from
> the specified height if the users accepts the amount of valid signatures
> .
>
> Sharing of the pre-generated UTXO-set can be done over CDNs,
> bit-torrent or any other file hosting solution. It would also be
> possible to extend the bitcoin p2p layer with features to
> distribute/share a such pre-generated UTXO-set, in chunks and with the
> according hashes to detect invalidity before downloading the whole
> content (but would probably end up in something very similar to
> bit-torrent).
>
>
> - ----------------------
> </jonas>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v2
>
> iQIcBAEBCAAGBQJW1B1wAAoJECnUvLZBb1PsqzsP/iSdvyhUzy+BZVSZbKXNjk5P
> 2vrtirI6NvKQd8hHbrcFeLfyswzYc2JWRnX8sATlauIS0pYdr97JriwUGlvxvNrY
> iVTDdf8MIVu8zScLQtJbMatpMvsewtqQEidn/yxWIhiCg4G2T5DZmlBU6O4XIKR6
> 5aPHElGOKZ15EWGHBG7z4owj3MiOaxhD9q5erBbfLPpcm08o6XAv5miqmGnnn3zh
> gocg4Gxs6iDygh3b2dCJFwWIVPxF6UVJhyjv2kLZUmEHT2Y2QvdGcLIIewcWHDze
> kgoZYmOEowujCbmeJ+LBwgOI0c1N6L/ciomPBne7ILmK4LyUEzyMLJKNYf/sZ8vI
> sVlmwZwZZLfILC7mzMAM0pfj99IOW680WHch9v31lWFlxW/bLvLqAO7n3acQuD6s
> xCZN2nAhmWC8FnMFxqB3EUz0lX8giV3qRJZjbQMS+ZrngYkAmVv2bAsoLndqf6MO
> l9W8B+ICg1KZLGIOF2pUrInpkB6gUALDFnypV4CeIVdeqtk5l4LnCHK6c4++Hl5n
> Bv5HQ/wTgKKNFtHBEJpWyYWvAjfFtgUZUKblR+Bh+D7/Gte1ehiYd02KYD4ds9Y4
> 3gfO8YbAz/I14Yuh2bIlvVKPWnLQBwL5BBioBfvmhV/r6rEpzWvB7H6Fmi1c759l
> VlL0GiUV8ar2LlFhEmWk
> =3DlZSy
> -----END PGP SIGNATURE-----
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

--001a1140fdd872f40c052ce73fbb
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div>One of the proposals was to build the UTXO set backwa=
rds.=C2=A0 You start from the newest block and work backwards.<br><br></div=
><div>The database contains UTXOs (unspent transaction outputs) and &quot;U=
FTXI&quot; (unfunded transaction inputs).<br><br></div><div>The procedure w=
ould be <br><br></div><div>For each transaction (last to first ordering)<br=
></div><div>=C2=A0=C2=A0=C2=A0 For each output<br>=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0 - check if it is in the UFTXI set<br></div><div>=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 -- If so, validate the signatures<br><=
/div><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 -- If not, add it to t=
he UTXO set<br><br></div><div>=C2=A0=C2=A0=C2=A0 For each input<br></div><d=
iv>=C2=A0 =C2=A0 =C2=A0 =C2=A0 - Add to the UFTXI set<br><br></div><div>Whe=
n you receive a transaction, it checks all the inputs<br></div><div>-- If a=
ll inputs are in the UTXO set, it says confirmed<br></div><div>-- Otherwise=
, gets marked as &quot;unknown inputs&quot;<br><br></div><div>There would a=
lso be a counter indicating how many blocks it has validated.<br><br></div>=
<div>A transaction with an unfunded input counts as validated back to the b=
lock it was included in.=C2=A0 Transactions count as confirmed to their anc=
estor that has the newest validation time.<br><br></div><div>Assume that th=
e node had validated the last 10000 blocks and you had a transaction with o=
ne input.=C2=A0 Assume the input transaction was included 5000 blocks ago a=
nd its input was included 50,000 blocks ago.<br><br></div><div>TX-A) input =
(TX-B:0) included in block 6 blocks ago<br></div><div>TX-B) input (TX-C:0) =
included in block 5000 ago<br></div><div>TX-C) input (TX-B:0) included in b=
lock 20000 ago<br><br></div><div>TX-C would not be known to the node since =
it has only gone back 10000 blocks.<br><br></div><div>TX-A would have confi=
rms 6 / 5000.=C2=A0 This means that its outputs have been confirmed by 6 bl=
ocks (confirms work as currently) and that its inputs have been confirmed b=
y 5000 blocks.<br><br></div><div>The reference client could mark transactio=
ns with 6+ output confirms and 1000+ input confirms as confirmed.<br><br></=
div><div>Once it hits the genesis block, then all transactions would be 6/&=
lt;infinity&gt;, so it could drop the second number.<br><br></div></div><di=
v class=3D"gmail_extra"><br><div class=3D"gmail_quote">On Mon, Feb 29, 2016=
 at 10:29 AM, Jonas Schnelli 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_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padd=
ing-left:1ex">-----BEGIN PGP SIGNED MESSAGE-----<br>
Hash: SHA256<br>
<br>
Hi<br>
<br>
I=E2=80=99ve been thinking around a solution to reduce nodes bootstrap time=
<br>
(IBD) as well as a way to reduce the amount of bandwidth/network usage<br>
per node.<br>
Not sure if this idea was/is already discussed, haven=E2=80=99t found anyth=
ing<br>
in a quick research.<br>
<br>
<br>
=3D=3DTitle=3D=3D<br>
Fast bootstrapping with a pre-generated UTXO-set database.<br>
<br>
=3D=3DAbstract=3D=3D<br>
This documents describes a way how bitcoin nodes can bootstrap faster<br>
by loading a pre-generated UTXO-set datafile with moderate reduction<br>
of the security model.<br>
<br>
=3D=3DSpecification=3D=3D<br>
Bitcoin-core or any other full node client will need to provide a<br>
feature to &quot;freeze&quot; the UTXO-set at a specified height (will requ=
ire a<br>
reindex). The frozen UTXO-set =E2=80=93 at a specific height =E2=80=93 will=
 be<br>
deterministic linearized in a currently not specified<br>
data-serializing-format.<br>
Additionally, a serialized form of the current chain-index (chain<br>
containing all block-headers) up to the specified height will be<br>
appended to the pre-generated UTXO-set-datafile.<br>
The datafile will be hashed with a double SHA256.<br>
<br>
The corresponding hash will be produced/reproduced and signed (ECDSA)<br>
by a group of developers, ideally the same group of developers who are<br>
also signing deterministic builds (binary distribution).<br>
<br>
Full node client implementations that supports bootstrapping from a<br>
pre-generated UTXO-set, need to include...<br>
1.) a set of pubkeys from trusted developers<br>
2.) the hash (or hashes) of the pre-generated UTXO-set-datafile(s)<br>
3.) n signatures of the hash(es) from 2) from a subset of developers<br>
defined in 1)<br>
<br>
To guarantee the integrity of developers pubkeys &amp; signatures, methods<=
br>
like the current gitian build, used in bitcoin-core, must be used.<br>
<br>
New nodes could download a copy of the pre-generated UTXO-set, hash<br>
it, verify the hash against the allowed UTXO-sets, verify the ECDSA<br>
signatures from various developers, and continue bootstrapping from<br>
the specified height if the users accepts the amount of valid signatures<br=
>
.<br>
<br>
Sharing of the pre-generated UTXO-set can be done over CDNs,<br>
bit-torrent or any other file hosting solution. It would also be<br>
possible to extend the bitcoin p2p layer with features to<br>
distribute/share a such pre-generated UTXO-set, in chunks and with the<br>
according hashes to detect invalidity before downloading the whole<br>
content (but would probably end up in something very similar to<br>
bit-torrent).<br>
<br>
<br>
- ----------------------<br>
&lt;/jonas&gt;<br>
-----BEGIN PGP SIGNATURE-----<br>
Version: GnuPG v2<br>
<br>
iQIcBAEBCAAGBQJW1B1wAAoJECnUvLZBb1PsqzsP/iSdvyhUzy+BZVSZbKXNjk5P<br>
2vrtirI6NvKQd8hHbrcFeLfyswzYc2JWRnX8sATlauIS0pYdr97JriwUGlvxvNrY<br>
iVTDdf8MIVu8zScLQtJbMatpMvsewtqQEidn/yxWIhiCg4G2T5DZmlBU6O4XIKR6<br>
5aPHElGOKZ15EWGHBG7z4owj3MiOaxhD9q5erBbfLPpcm08o6XAv5miqmGnnn3zh<br>
gocg4Gxs6iDygh3b2dCJFwWIVPxF6UVJhyjv2kLZUmEHT2Y2QvdGcLIIewcWHDze<br>
kgoZYmOEowujCbmeJ+LBwgOI0c1N6L/ciomPBne7ILmK4LyUEzyMLJKNYf/sZ8vI<br>
sVlmwZwZZLfILC7mzMAM0pfj99IOW680WHch9v31lWFlxW/bLvLqAO7n3acQuD6s<br>
xCZN2nAhmWC8FnMFxqB3EUz0lX8giV3qRJZjbQMS+ZrngYkAmVv2bAsoLndqf6MO<br>
l9W8B+ICg1KZLGIOF2pUrInpkB6gUALDFnypV4CeIVdeqtk5l4LnCHK6c4++Hl5n<br>
Bv5HQ/wTgKKNFtHBEJpWyYWvAjfFtgUZUKblR+Bh+D7/Gte1ehiYd02KYD4ds9Y4<br>
3gfO8YbAz/I14Yuh2bIlvVKPWnLQBwL5BBioBfvmhV/r6rEpzWvB7H6Fmi1c759l<br>
VlL0GiUV8ar2LlFhEmWk<br>
=3DlZSy<br>
-----END PGP SIGNATURE-----<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>
</blockquote></div><br></div>

--001a1140fdd872f40c052ce73fbb--