From: Tomas <tomas@tomasvdw•nl>
To: Eric Voskuil <eric@voskuil•org>,
Bitcoin Protocol Discussion
<bitcoin-dev@lists•linuxfoundation.org>,
Libbitcoin Development <libbitcoin@lists•dyne.org>
Subject: Re: [bitcoin-dev] Using a storage engine without UTXO-index
Date: Fri, 07 Apr 2017 02:17:47 +0200 [thread overview]
Message-ID: <1491524267.715789.936916864.1156D8CB@webmail.messagingengine.com> (raw)
In-Reply-To: <eebc06a4-5ab8-46a8-2f50-a472cb57a775@voskuil.org>
Hi Eric,
Thanks, but I get the impression that the similarity is rather
superficial.
To address your points:
> (1) higher than necessary storage space requirement due to storing the
> indexing data required for correlate the spends, and
Hmm. No. Spends are simply scanned in the spend-tree (full tree,
prunable, fully 5.6gb), or caught by the spend-index (bit index,
non-prunable, fully 180mb). Neither impose significant storage
requirements.
> 2) higher than necessary validation complexity and cost in terms of
> computing the spent-ness (including spender height) of an output.
>
> With the exception of de-linking (not deleted) in the case of reorgs, the
> entire store is append only, implemented in a small set of memory
> mapped file
I guess this is the key difference. As the spend-tree stores the spend
information in a tree structure, no reorgs are required, and the
resulting code is actually much less complex.
Bitcrust simply scans the tree. Although earlier designs used a
skip-list, it turns out that accompanied by a spent-index lagging a few
blocks behind, raw scanning is faster then anything even though it needs
to scan ~5 blocks times ~4000 inputs before reaching the first
spent-index, the actual scan is highly cache efficient and little more
then a "REP SCASQ", reaching sub-microsecond per input on each core
*including* the lookup in the spend index.
> I don't follow this part, maybe you could clarify. A spends index
> grows with the size of the spend set (forever) as it cannot be pruned,
> which certainly exceeds the size of the UTXO set (unless nothing is
> spent). The advantage is that you don't have to keep rewriting the
> store when you use a spends set (because the store can be append only).
My point is, that the spend tree grows per *input* of a transaction
instead of per *output* of a transaction, because this is what is
scanned on order validation.
The spend tree can be pruned because the spend index (~200mb) catches
early spends.
Disregarding the baseload script validation, the peak load order
validation of bitcrust is more negatively effected by a transaction with
many inputs than by a transaction of many outputs.
I encourage you to check out the results at https://bitcrust.org
Regards,
Tomas
On Fri, Apr 7, 2017, at 01:38, Eric Voskuil wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA256
>
> On 04/06/2017 03:12 PM, Tomas via bitcoin-dev wrote:
>
> Hi Tomas,
>
> > I have been working on a bitcoin implementation that uses a
> > different approach to indexing for verifying the order of
> > transactions. Instead of using an index of unspent outputs, double
> > spends are verified by using a spend-tree where spends are scanned
> > against spent outputs instead of unspent outputs.
>
> This is the approach that genjix used in libbitcoin version2. With the
> exception of de-linking (not deleted) in the case of reorgs, the
> entire store is append only, implemented in a small set of memory
> mapped files. The downsides to the approach are:
>
> (1) higher than necessary storage space requirement due to storing the
> indexing data required for correlate the spends, and
>
> (2) higher than necessary validation complexity and cost in terms of
> computing the spent-ness (including spender height) of an output.
>
> His implementation used a hash table, so performance-wise it did quite
> well and would theoretically outperform a tree, O(1) vs. O(log2(N)).
>
> > This allows for much better concurrency, as not only blocks, but
> > also individual inputs can be verified fully in parallel.
>
> I was successful in parallelizing input validation (across the inputs
> of an unconfirmed tx and across the set of all inputs in a block)
> using the v2 store. However, it is not the case that the spends
> approach is necessary for concurrency.
>
> To resolve the above two problems the version3 store does not use a
> spends table/index. Nor does it store any table of UTXOs. Yet
> validation is highly parallelized. Instead of additional indexes it
> uses the tx hash table, augmented with 32 bits per output for spender
> height. So there is a O(1) cost of finding the tx and a O(N) cost of
> finding the spender height where N is the number of outputs in the tx.
> But because the number of outputs in a tx is bounded (by block size)
> this is constant time in the number of transactions.
>
> This works out much faster than the spends table, and without the
> storage cost or complexity disadvantages. It also scales with
> available hardware, as the memory mapped files become in-memory hash
> tables. For low memory machines we found it was important to implement
> an opaque UTXO cache to limit paging, but for higher end systems zero
> cache is optimal.
>
> > I am sharing this not only to ask for your feedback, but also to
> > call for a clear separation of protocol and implementations: As
> > this solution, reversing the costs of outputs and inputs, seems to
> > have excellent performance characteristics (as shown in the test
> > results), updates to the protocol addressing the UTXO growth, might
> > not be worth considering *protocol improvements* and it might be
> > best to address these concerns as implementation details.
>
> I don't follow this part, maybe you could clarify. A spends index
> grows with the size of the spend set (forever) as it cannot be pruned,
> which certainly exceeds the size of the UTXO set (unless nothing is
> spent). The advantage is that you don't have to keep rewriting the
> store when you use a spends set (because the store can be append only).
>
> Feel free to message me if you'd like to discuss in more detail, or to
> continue on the libbitcoin mailing list (copied).
>
> e
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v2.0.22 (GNU/Linux)
>
> iQEcBAEBCAAGBQJY5tFpAAoJEDzYwH8LXOFOcMgH/2mw5iOvUYNwvZ2z0KKTSUOA
> Pd8d5mKoWvd94QxhQ+RyTbkEkMhHl75+zcBgRsfUTtZlBIe/Z0+OgVIN6ibEw+WD
> w7k3HqgQi9gLgydEelxTAX+z3dJ24n4kCCdKAmZbBuK+Yr/7AViugbEqYemKepku
> pRWZZS74MUvrYesc0xPn4Ao3DTzMjjY0K2mkuqV8jlwdfZjlAQX9pTx+iSCuMhkd
> HJ8w7s8QnjVnUeOlLe29mZwaFJPyOTLJMqgDE6s2sXacAy5QQbVCatygvDQ8A/wC
> ktBnKPFb2lGX3bGKu/KwABegBy/hyec+NP0wFR+0MVivCwTK1+SjeHu5MNOSVlM=
> =tfVj
> -----END PGP SIGNATURE-----
next prev parent reply other threads:[~2017-04-07 0:17 UTC|newest]
Thread overview: 35+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-04-06 22:12 Tomas
2017-04-06 23:38 ` Eric Voskuil
2017-04-07 0:17 ` Tomas [this message]
2017-04-08 22:37 ` Eric Voskuil
2017-04-08 23:58 ` Tomas
2017-04-11 1:44 ` Eric Voskuil
2017-04-11 8:43 ` Tomas
2017-04-11 9:41 ` Eric Voskuil
2017-04-11 10:04 ` Tomas
[not found] ` <CAAS2fgTEMCkDWdhCWt1EsUrnt3+Z_8m+Y1PTsff5Rc0CBnCKWQ@mail.gmail.com>
2017-04-07 0:48 ` Tomas
2017-04-07 1:09 ` Gregory Maxwell
2017-04-07 1:29 ` Tomas
2017-04-07 18:52 ` Tom Harding
2017-04-07 19:42 ` Gregory Maxwell
2017-04-08 18:27 ` Tom Harding
2017-04-08 19:23 ` Tomas
2017-04-07 7:55 ` Marcos mayorga
2017-04-07 8:47 ` Tomas
2017-04-07 14:14 ` Greg Sanders
2017-04-07 16:02 ` Tomas
2017-04-07 18:18 ` Gregory Maxwell
2017-04-07 18:39 ` Bram Cohen
2017-04-07 19:55 ` Eric Voskuil
2017-04-07 21:44 ` Tomas
2017-04-07 23:51 ` Eric Voskuil
2017-04-07 21:14 ` Tomas
2017-04-08 0:44 ` Gregory Maxwell
2017-04-08 7:28 ` Tomas
2017-04-08 19:23 ` Johnson Lau
2017-04-08 19:56 ` Tomas
2017-04-08 20:21 ` Johnson Lau
2017-04-08 20:42 ` Tomas
2017-04-08 22:12 ` Gregory Maxwell
2017-04-08 22:34 ` Tomas
2017-04-08 21:22 ` Troy Benjegerdes
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1491524267.715789.936916864.1156D8CB@webmail.messagingengine.com \
--to=tomas@tomasvdw$(echo .)nl \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=eric@voskuil$(echo .)org \
--cc=libbitcoin@lists$(echo .)dyne.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox