{"type":"rich","version":"1.0","author_name":"Tomas [ARCHIVE] (npub1rs…9evk4)","author_url":"https://nostr.ae/npub1rsp4w56r24w3zv4xy8zfgesep45qmf9rq6aghxfw3wr7yemqnnwsf9evk4","provider_name":"njump","provider_url":"https://nostr.ae","html":"📅 Original date posted:2017-04-06\n📝 Original message:Hi Eric,\n\nThanks, but I get the impression that the similarity is rather\nsuperficial.  \n\nTo address your points:\n\n\u003e (1) higher than necessary storage space requirement due to storing the\n\u003e indexing data required for correlate the spends, and\n\nHmm. No. Spends are simply scanned in the spend-tree (full tree,\nprunable, fully 5.6gb), or caught by the spend-index (bit index,\nnon-prunable, fully 180mb). Neither impose significant storage\nrequirements.\n\n\u003e 2) higher than necessary validation complexity and cost in terms of\n\u003e computing the spent-ness (including spender height) of an output.\n\u003e\n\u003e With the exception of de-linking (not deleted) in the case of reorgs, the\n\u003e entire store is append only, implemented in a small set of memory\n\u003e mapped file\n\nI guess this is the key difference. As the spend-tree stores the spend\ninformation in a tree structure, no reorgs are required, and the\nresulting code is actually much less complex.\n\nBitcrust simply scans the tree. Although earlier designs used a\nskip-list, it turns out that accompanied by a spent-index lagging a few\nblocks behind, raw scanning is faster then anything even though it needs\nto scan ~5 blocks times ~4000 inputs before reaching the first\nspent-index,  the actual scan is highly cache efficient and little more\nthen a \"REP SCASQ\", reaching sub-microsecond per input on each core\n*including* the lookup in the spend index.\n\n \u003e I don't follow this part, maybe you could clarify. A spends index\n\u003e grows with the size of the spend set (forever) as it cannot be pruned,\n\u003e which certainly exceeds the size of the UTXO set (unless nothing is\n\u003e spent). The advantage is that you don't have to keep rewriting the\n\u003e store when you use a spends set (because the store can be append only).\n\nMy point is, that the spend tree grows per *input* of a transaction\ninstead of per *output* of a transaction, because this is what is\nscanned on order validation.\n\nThe spend tree can be pruned because the spend index (~200mb) catches\nearly spends.\n\nDisregarding the baseload script validation, the peak load order\nvalidation of bitcrust is more negatively effected by a transaction with\nmany inputs than by a transaction of many outputs.\n\nI encourage you to check out the results at https://bitcrust.org\n\nRegards,\nTomas\n\nOn Fri, Apr 7, 2017, at 01:38, Eric Voskuil wrote:\n\u003e -----BEGIN PGP SIGNED MESSAGE-----\n\u003e Hash: SHA256\n\u003e \n\u003e On 04/06/2017 03:12 PM, Tomas via bitcoin-dev wrote:\n\u003e \n\u003e Hi Tomas,\n\u003e \n\u003e \u003e I have been working on a bitcoin implementation that uses a\n\u003e \u003e different approach to indexing for verifying the order of\n\u003e \u003e transactions. Instead of using an index of unspent outputs, double\n\u003e \u003e spends are verified by using a spend-tree where spends are scanned\n\u003e \u003e against spent outputs instead of unspent outputs.\n\u003e \n\u003e This is the approach that genjix used in libbitcoin version2. With the\n\u003e exception of de-linking (not deleted) in the case of reorgs, the\n\u003e entire store is append only, implemented in a small set of memory\n\u003e mapped files. The downsides to the approach are:\n\u003e \n\u003e (1) higher than necessary storage space requirement due to storing the\n\u003e indexing data required for correlate the spends, and\n\u003e \n\u003e (2) higher than necessary validation complexity and cost in terms of\n\u003e computing the spent-ness (including spender height) of an output.\n\u003e \n\u003e His implementation used a hash table, so performance-wise it did quite\n\u003e well and would theoretically outperform a tree, O(1) vs. O(log2(N)).\n\u003e \n\u003e \u003e This allows for much better concurrency, as not only blocks, but\n\u003e \u003e also individual inputs can be verified fully in parallel.\n\u003e \n\u003e I was successful in parallelizing input validation (across the inputs\n\u003e of an unconfirmed tx and across the set of all inputs in a block)\n\u003e using the v2 store. However, it is not the case that the spends\n\u003e approach is necessary for concurrency.\n\u003e \n\u003e To resolve the above two problems the version3 store does not use a\n\u003e spends table/index. Nor does it store any table of UTXOs. Yet\n\u003e validation is highly parallelized. Instead of additional indexes it\n\u003e uses the tx hash table, augmented with 32 bits per output for spender\n\u003e height. So there is a O(1) cost of finding the tx and a O(N) cost of\n\u003e finding the spender height where N is the number of outputs in the tx.\n\u003e But because the number of outputs in a tx is bounded (by block size)\n\u003e this is constant time in the number of transactions.\n\u003e \n\u003e This works out much faster than the spends table, and without the\n\u003e storage cost or complexity disadvantages. It also scales with\n\u003e available hardware, as the memory mapped files become in-memory hash\n\u003e tables. For low memory machines we found it was important to implement\n\u003e an opaque UTXO cache to limit paging, but for higher end systems zero\n\u003e cache is optimal.\n\u003e \n\u003e \u003e I am sharing this not only to ask for your feedback, but also to\n\u003e \u003e call for a clear separation of protocol and implementations: As\n\u003e \u003e this solution, reversing the costs of outputs and inputs, seems to\n\u003e \u003e have excellent performance characteristics (as shown in the test\n\u003e \u003e results), updates to the protocol addressing the UTXO growth, might\n\u003e \u003e not be worth considering *protocol improvements* and it might be\n\u003e \u003e best to address these concerns as implementation details.\n\u003e \n\u003e I don't follow this part, maybe you could clarify. A spends index\n\u003e grows with the size of the spend set (forever) as it cannot be pruned,\n\u003e which certainly exceeds the size of the UTXO set (unless nothing is\n\u003e spent). The advantage is that you don't have to keep rewriting the\n\u003e store when you use a spends set (because the store can be append only).\n\u003e \n\u003e Feel free to message me if you'd like to discuss in more detail, or to\n\u003e continue on the libbitcoin mailing list (copied).\n\u003e \n\u003e e\n\u003e -----BEGIN PGP SIGNATURE-----\n\u003e Version: GnuPG v2.0.22 (GNU/Linux)\n\u003e \n\u003e iQEcBAEBCAAGBQJY5tFpAAoJEDzYwH8LXOFOcMgH/2mw5iOvUYNwvZ2z0KKTSUOA\n\u003e Pd8d5mKoWvd94QxhQ+RyTbkEkMhHl75+zcBgRsfUTtZlBIe/Z0+OgVIN6ibEw+WD\n\u003e w7k3HqgQi9gLgydEelxTAX+z3dJ24n4kCCdKAmZbBuK+Yr/7AViugbEqYemKepku\n\u003e pRWZZS74MUvrYesc0xPn4Ao3DTzMjjY0K2mkuqV8jlwdfZjlAQX9pTx+iSCuMhkd\n\u003e HJ8w7s8QnjVnUeOlLe29mZwaFJPyOTLJMqgDE6s2sXacAy5QQbVCatygvDQ8A/wC\n\u003e ktBnKPFb2lGX3bGKu/KwABegBy/hyec+NP0wFR+0MVivCwTK1+SjeHu5MNOSVlM=\n\u003e =tfVj\n\u003e -----END PGP SIGNATURE-----"}