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

[Tier Nolan]

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 at 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 at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20160229/b13250f5/attachment.html>