From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 21500C9B for ; 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 ; Mon, 29 Feb 2016 11:49:58 +0000 (UTC) Received: by mail-vk0-f50.google.com with SMTP id e6so130716252vkh.2 for ; 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: From: Tier Nolan Cc: Bitcoin development mailing list 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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/, 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). > > > - ---------------------- > > -----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
One of the proposals was to build the UTXO set backwa= rds.=C2=A0 You start from the newest block and work backwards.

The database contains UTXOs (unspent transaction outputs) and "U= FTXI" (unfunded transaction inputs).

The procedure w= ould be

For each transaction (last to first ordering)
=C2=A0=C2=A0=C2=A0 For each output
=C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0=C2=A0=C2=A0 - check if it is in the UFTXI set
=C2=A0= =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 -- If so, validate the signatures
<= /div>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 -- If not, add it to t= he UTXO set

=C2=A0=C2=A0=C2=A0 For each input
=C2=A0 =C2=A0 =C2=A0 =C2=A0 - Add to the UFTXI set

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

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

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

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.

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 b= lock 20000 ago

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

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.

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

Once it hits the genesis block, then all transactions would be 6/&= lt;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 time=
(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 anyth= ing
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 requ= ire a
reindex). The frozen UTXO-set =E2=80=93 at a specific height =E2=80=93 will= 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<= br> 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/mail= man/listinfo/bitcoin-dev

--001a1140fdd872f40c052ce73fbb--