{"type":"rich","version":"1.0","author_name":"npub1sgs97fe0n9wehe6zw7drcxdz4cy9yt9pfqjv8gasz5jlk4zezc0quppx3c","author_url":"https://nostr.ae/npub1sgs97fe0n9wehe6zw7drcxdz4cy9yt9pfqjv8gasz5jlk4zezc0quppx3c","provider_name":"njump","provider_url":"https://nostr.ae","html":"📅 Original date posted:2017-04-06\n📝 Original message:-----BEGIN PGP SIGNED MESSAGE-----\nHash: SHA256\n\nOn 04/06/2017 03:12 PM, Tomas via bitcoin-dev wrote:\n\nHi Tomas,\n\n\u003e I have been working on a bitcoin implementation that uses a\n\u003e different approach to indexing for verifying the order of\n\u003e transactions. Instead of using an index of unspent outputs, double\n\u003e spends are verified by using a spend-tree where spends are scanned\n\u003e against spent outputs instead of unspent outputs.\n\nThis is the approach that genjix used in libbitcoin version2. With the\nexception of de-linking (not deleted) in the case of reorgs, the\nentire store is append only, implemented in a small set of memory\nmapped files. The downsides to the approach are:\n\n(1) higher than necessary storage space requirement due to storing the\nindexing data required for correlate the spends, and\n\n(2) higher than necessary validation complexity and cost in terms of\ncomputing the spent-ness (including spender height) of an output.\n\nHis implementation used a hash table, so performance-wise it did quite\nwell and would theoretically outperform a tree, O(1) vs. O(log2(N)).\n\n\u003e This allows for much better concurrency, as not only blocks, but\n\u003e also individual inputs can be verified fully in parallel.\n\nI was successful in parallelizing input validation (across the inputs\nof an unconfirmed tx and across the set of all inputs in a block)\nusing the v2 store. However, it is not the case that the spends\napproach is necessary for concurrency.\n\nTo resolve the above two problems the version3 store does not use a\nspends table/index. Nor does it store any table of UTXOs. Yet\nvalidation is highly parallelized. Instead of additional indexes it\nuses the tx hash table, augmented with 32 bits per output for spender\nheight. So there is a O(1) cost of finding the tx and a O(N) cost of\nfinding the spender height where N is the number of outputs in the tx.\nBut because the number of outputs in a tx is bounded (by block size)\nthis is constant time in the number of transactions.\n\nThis works out much faster than the spends table, and without the\nstorage cost or complexity disadvantages. It also scales with\navailable hardware, as the memory mapped files become in-memory hash\ntables. For low memory machines we found it was important to implement\nan opaque UTXO cache to limit paging, but for higher end systems zero\ncache is optimal.\n\n\u003e I am sharing this not only to ask for your feedback, but also to\n\u003e call for a clear separation of protocol and implementations: As\n\u003e this solution, reversing the costs of outputs and inputs, seems to\n\u003e have excellent performance characteristics (as shown in the test\n\u003e results), updates to the protocol addressing the UTXO growth, might\n\u003e not be worth considering *protocol improvements* and it might be\n\u003e best to address these concerns as implementation details.\n\nI don't follow this part, maybe you could clarify. A spends index\ngrows with the size of the spend set (forever) as it cannot be pruned,\nwhich certainly exceeds the size of the UTXO set (unless nothing is\nspent). The advantage is that you don't have to keep rewriting the\nstore when you use a spends set (because the store can be append only).\n\nFeel free to message me if you'd like to discuss in more detail, or to\ncontinue on the libbitcoin mailing list (copied).\n\ne\n-----BEGIN PGP SIGNATURE-----\nVersion: GnuPG v2.0.22 (GNU/Linux)\n\niQEcBAEBCAAGBQJY5tFpAAoJEDzYwH8LXOFOcMgH/2mw5iOvUYNwvZ2z0KKTSUOA\nPd8d5mKoWvd94QxhQ+RyTbkEkMhHl75+zcBgRsfUTtZlBIe/Z0+OgVIN6ibEw+WD\nw7k3HqgQi9gLgydEelxTAX+z3dJ24n4kCCdKAmZbBuK+Yr/7AViugbEqYemKepku\npRWZZS74MUvrYesc0xPn4Ao3DTzMjjY0K2mkuqV8jlwdfZjlAQX9pTx+iSCuMhkd\nHJ8w7s8QnjVnUeOlLe29mZwaFJPyOTLJMqgDE6s2sXacAy5QQbVCatygvDQ8A/wC\nktBnKPFb2lGX3bGKu/KwABegBy/hyec+NP0wFR+0MVivCwTK1+SjeHu5MNOSVlM=\n=tfVj\n-----END PGP SIGNATURE-----"}