[bitcoin-dev] Fast bootstrapping with a pre-generated UTXO-set database

[bitcoin-dev] Fast bootstrapping with a pre-generated UTXO-set database

[Jonas Schnelli]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

Hi

I’ve 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’t found anything
in a quick research.


==Title==
Fast bootstrapping with a pre-generated UTXO-set database.

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

==Specification==
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 – at a specific height – 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
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
=lZSy
-----END PGP SIGNATURE-----

Re: [bitcoin-dev] Fast bootstrapping with a pre-generated UTXO-set database

[Tier Nolan]

[-- Attachment #1: Type: text/plain, Size: 5578 bytes --]

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’ve 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’t found anything
> in a quick research.
>
>
> ==Title==
> Fast bootstrapping with a pre-generated UTXO-set database.
>
> ==Abstract==
> 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.
>
> ==Specification==
> 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 – at a specific height – 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
> 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
> =lZSy
> -----END PGP SIGNATURE-----
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 6619 bytes --]