MIME-Version: 1.0
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
Subject: Re: [bitcoin-dev] Fast bootstrapping with a pre-generated UTXO-set
	database
Precedence: list

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