{"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-08\n📝 Original message:-----BEGIN PGP SIGNED MESSAGE-----\nHash: SHA256\n\nOn 04/06/2017 05:17 PM, Tomas wrote:\n\u003e Thanks, but I get the impression that the similarity is rather \n\u003e superficial.\n\nMy point was that \"Using a storage engine without UTXO-index\" has been\ndone, and may be a useful reference, not that implementation details\nare the same.\n\n\u003e To address your points:\n\nBelow you addressed two points I made regarding the downside of the\noriginal libbitcoin implementation. These were initial learnings that\ninformed future implementations (also without a UTXO index). These\nwere not comparisons to your implementation.\n\n\u003e\u003e (1) higher than necessary storage space requirement due to\n\u003e\u003e storing the indexing data required for correlate the spends, and\n\u003e \n\u003e Hmm. No. Spends are simply scanned in the spend-tree (full tree, \n\u003e prunable, fully 5.6gb), or caught by the spend-index (bit index, \n\u003e non-prunable, fully 180mb). Neither impose significant storage \n\u003e requirements.\n\u003e \n\u003e\u003e 2) higher than necessary validation complexity and cost in terms\n\u003e\u003e of computing the spent-ness (including spender height) of an\n\u003e\u003e output.\n\u003e\u003e \n\u003e\u003e With the exception of de-linking (not deleted) in the case of\n\u003e\u003e reorgs, the entire store is append only, implemented in a small\n\u003e\u003e set of memory mapped file\n\u003e \n\u003e I guess this is the key difference. As the spend-tree stores the\n\u003e spend information in a tree structure, no reorgs are required, and\n\u003e the resulting code is actually much less complex.\n\nThe references to \"higher than necessary storage\" and \"higher than\nnecessary validation cost\" are explicitly relative statements,\ncomparing earlier and later libbitcoin implementations.\n\nIt is not clear to me how you are relating both the storage cost\n(\"Hmm. No. ... Neither impose significant storage requirements.\") and\ncode complexity (\"... resulting code is actually much less complex\")\nof your tx ordering software to my statements. Do you think I am wrong\nand libbitcoin v3 is not actually more space and code efficient than\nlibbitcoin v2?\n\nBut given that you have thrown some numbers and ideas out in a request\nfor feedback, I'm happy to give you some based on several years of\nexperience working closely with these issues.\n\nFirst, I remain confused on your comments pertaining to UTXO growth\nand network protocol. I followed your conversation with Greg and it\nremains unclear to me. From what I understand you have isolated order\n(double spend) from script validation. I think we all understand that\nscript validation requires inputs and outputs while double spend\ndetection requires correlation of inputs. What I do not understand is\nyour choice of optimization axis.\n\nDetection of double spend is not useful in isolation. One must also\nvalidate scripts, which requires outputs. I can see that there is an\nopportunity to reject blocks (within the same branch) faster by\nvalidating for double spends before validating script. But unconfirmed\ntransactions do not exist in a branch, and are therefore not truly\nconflicting, until they are mined. And even after they are mined\nconflicting txs remain potentially valid in other branches. So\nrejecting txs due to conflict comes down to a denial of service\npolicy, which ultimately must be based on fee increment (e.g. RBF).\nBut fees are based on the amount of the output value that remains\nunspent in the transaction. So this in turn requires the retrieval of\noutputs.\n\nAnd yet the remaining scenario of fast rejection of invalid blocks is\nnot a meaningful optimization. Optimizing for the case where a block\nhas valid and sufficient PoW and yet is invalid (for double spend) is\ncounterproductive. And even so, the txs within the invalid block may\nbe entirely valid independent of the block, so you are back to looking\nup their outputs to obtain fees in the case of a double spend or to\nvalidate script otherwise. In all cases you need to get the outputs.\n\n\u003e Bitcrust simply scans the tree. Although earlier designs used a \n\u003e skip-list, it turns out that accompanied by a spent-index lagging a\n\u003e few blocks behind, raw scanning is faster then anything even though\n\u003e it needs to scan ~5 blocks times ~4000 inputs before reaching the\n\u003e first spent-index,  the actual scan is highly cache efficient and\n\u003e little more then a \"REP SCASQ\", reaching sub-microsecond per input\n\u003e on each core *including* the lookup in the spend index.\n\nI realize that you see the implementation of the ordering validation\nas interesting detail, but I find it hard to justify contemplating the\nimplementation in isolation from the output lookup requirement. And if\none must looking up both outputs and spends for each validation, it\nmakes more sense to co-locate that data.\n\nRecovering in one step all data necessary to validate a tx has real\nadvantages over either interleaving queries and validation or\nsplitting input vs. output validation queries into two steps. It is a\nsignificantly more test-friendly approach, has better performance\ncharacteristics, and simplifies code. I cannot see any reason to\nperform the data read for double spend validation in isolation of that\nfor script validation.\n\n\u003e\u003e I don't follow this part, maybe you could clarify. A spends\n\u003e\u003e index grows with the size of the spend set (forever) as it cannot\n\u003e\u003e be pruned, which certainly exceeds the size of the UTXO set\n\u003e\u003e (unless nothing is spent). The advantage is that you don't have\n\u003e\u003e to keep rewriting the store when you use a spends set (because\n\u003e\u003e the store can be append only).\n\u003e \n\u003e My point is, that the spend tree grows per *input* of a\n\u003e transaction instead of per *output* of a transaction, because this\n\u003e is what is scanned on order validation.\n\nI think the conversation with Greg resolved my questions in this area.\nWhat I find interesting is the reliance on Core's UTXO store to\nimplement script validation. This is not, \"a storage engine without a\nUTXO-index\" as it has a dependency on Core's UTXO index.\n\nOn the other hand the initial libbitcoin implementation that I\ndescribed to you is *actually* a bitcoin store with no UTXO index. The\ncurrent implementation is as well, however it is implemented\ndifferently and is much more efficient than the original. How it\ncompares to your design is not really the point and impossible to\nmeasure until you have production code.\n\nI can say however that your assumptions about the storage (and\nperformance) superiority of the design, or at least its\nimplementation, seem unfounded. If you are storing more index data\n(5.6gb) than 32 bits per output, you are using more space than\nproduction implementations. As for complexity, I don't think you'll\nget any simpler than a loop to populate spend heights from a hash\ntable and a loop to test their integer values.\n\n\u003e The spend tree can be pruned because the spend index (~200mb)\n\u003e catches early spends.\n\u003e \n\u003e Disregarding the baseload script validation, the peak load order \n\u003e validation of bitcrust is more negatively effected by a transaction\n\u003e with many inputs than by a transaction of many outputs.\n\u003e \n\u003e I encourage you to check out the results at https://bitcrust.org\n\nIf by results you are referring to performance numbers, it's very hard\nto draw any conclusions without a full benchmark. It's great that if\nyou are able to boost Core, but from my perspective the numbers aren't\nespecially compelling.\n\nAs for some of the site's comments, these again cause me to question\nthe optimization choices:\n\n\"Blocks can be verified in parallel...\"\n\nDespite the site's explanation I cannot think of any reason to ever\nvalidate two blocks at the same time. You would always prioritize the\nblock with the greatest PoW. Doing otherwise just slows down the net\nvalidation in all but the pathological case where a miner has produced\nan *invalid* block with *more* PoW than another valid block which\narrived at the node within the same second. Rejecting a *valid* block\nwith more PoW in favor of one with *less* \"processing\" is a hard fork,\nso you probably wouldn't want to do that either. But with compact\nblock validation times approaching 25ms it's hard to justify stopping\na block validation for any reason.\n\nThat's not to say parallel block validation difficult to do. If you\ncan validate one block's full set of inputs in parallel (which is not\nnovel) doing the same with additional blocks has trivial additional\ncomplexity.\n\n\"The storage engine is optimized from ground up for\nxthin/compact-block synchronization. This ensures that when the\nmajority of transactions are already synced, incoming blocks can be\nverified at minimal resources using order-validation only.\"\n\nThere are two distinct considerations here. One is pre-validation of\ntxs and the other is compact announcements. Just to be clear, the\nformer does not require the latter. Libbitcoin for example fully\nexploits the former, independent of compactness. With a low min fee\nsetting and a few peers it is typical for the node to have\npre-validated 100% of non-coinbase txs. Averages at 1 satoshi per byte\nare about 99.9%, effectively amortizing all script validation cost. So\nthis optimization is neither novel nor limited to compactness (which\nis about reducing latency).\n\nI am also interested in your previous comments about soft forks. These\nare material considerations that Greg touched on but it doesn't sound\nlike you fully appreciate just yet. When a tx is pre-validated the\nrules applied must be the same rules as those of some future block.\nYet a tx can be included in more than one block (different branches).\nAcross branches and even in one branch, validation rules change, and\ncan change back. The changes are based on accumulated branch history.\nPre-validation can later become invalidated, and differently in\ndifferent branches. And maintaining proper context requires either\nstoring state that you are apparently not storing, or invalidating\noptimizations. Based on your comments you do not seem to be accounting\nfor this in your storage assumptions or in your results. A recent post\nby Greg highlights the complexity and consensus criticality of these\nconsiderations.\n\nBy \"order-validation only\" I believe you are referring to a\ndetermination of whether the txs organized into a candidate block\ndouble spend internal to the block or in the ancestry. Assuming that\none recovers outputs at the same time (and presumably from the same\nlocation) as spender height (which is required both for validating\nspends of a coinbase and for determination of whether the spend is\nabove the fork point), this determination is straightforward. One\nsimply loops over the spender records and invalidates a tx that has a\nspender height not above the fork point (while also validating\ncoinbase maturity using the same height). A loop over the set of\nin-memory spend heights of each output a tx is certainly fast enough\nto not be worthy of any further optimization. And as previously\ndiscussed, the population of the spender heights is not even a\nmaterial additional cost over obtaining the (necessary) output scripts.\n\nThe hash table store that I described can fully navigate the block\ntree and transaction DAG, since the stored tx, parent and point hashes\nare also natural keys and each link is navigable in constant time. It\nis also lock-free, can concurrently write any number of blocks during\ninitial block download and supports read/write concurrency. It has\nsuccessfully indexed and stored the entire blockchain from the P2P\nnetwork in 16 minutes (locally). It also stores both confirmed and\nunconfirmed transactions in the same store, so there is nothing to\nwrite when a block is confirmed except for the block header/hashes and\nupdates to spender heights for any output spent by the new block's\ntxs. It is similarly capable of storage in the block table of weak\nchain blocks...\n\nBut one thing it does *not* do is maintain spender and fork state for\nmultiple branches. In other words it is optimized for one long chain,\nnot multiple long branches. Your approach has a limited (in terms of\ndouble spend identification) optimization for reorganization (i.e. a\nchange to the strong chain identity). However, applying that\noptimization to the full store and supportive of soft forks, as\nopposed to just input ordering, is a much larger task than it appears\nyou have attempted. I know, as I created a design for that approach\nand after some time scrapped it. The cost of performing the\nreorganization in the above store is low enough and very long reorgs\ninfrequent enough, for the optimization to be counterproductive. It's\nelegant in theory, but in practice it increases storage requirements,\nimpacts general performance and significantly increases complexity.\nBitcoin's data model pushes one away from a tree design in that it is\nalways pruning the tree. Having the tree is necessary, but it's not\nsomething to optimize for.\n\ne\n\n\n\u003e Regards, Tomas\n\u003e \n\u003e On Fri, Apr 7, 2017, at 01:38, Eric Voskuil wrote: On 04/06/2017\n\u003e 03:12 PM, Tomas via bitcoin-dev wrote:\n\u003e \n\u003e Hi Tomas,\n\u003e \n\u003e\u003e\u003e\u003e I have been working on a bitcoin implementation that uses a \n\u003e\u003e\u003e\u003e different approach to indexing for verifying the order of \n\u003e\u003e\u003e\u003e transactions. Instead of using an index of unspent outputs,\n\u003e\u003e\u003e\u003e double spends are verified by using a spend-tree where spends\n\u003e\u003e\u003e\u003e are scanned against spent outputs instead of unspent\n\u003e\u003e\u003e\u003e outputs.\n\u003e \n\u003e This is the approach that genjix used in libbitcoin version2. With\n\u003e the exception of de-linking (not deleted) in the case of reorgs,\n\u003e the entire store is append only, implemented in a small set of\n\u003e memory mapped files. The downsides to the approach are:\n\u003e \n\u003e (1) higher than necessary storage space requirement due to storing\n\u003e the indexing data required for correlate the spends, and\n\u003e \n\u003e (2) higher than necessary validation complexity and cost in terms\n\u003e of computing the spent-ness (including spender height) of an\n\u003e output.\n\u003e \n\u003e His implementation used a hash table, so performance-wise it did\n\u003e quite well and would theoretically outperform a tree, O(1) vs.\n\u003e O(log2(N)).\n\u003e \n\u003e\u003e\u003e\u003e This allows for much better concurrency, as not only blocks,\n\u003e\u003e\u003e\u003e but also individual inputs can be verified fully in\n\u003e\u003e\u003e\u003e parallel.\n\u003e \n\u003e I was successful in parallelizing input validation (across the\n\u003e inputs of an unconfirmed tx and across the set of all inputs in a\n\u003e block) using the v2 store. However, it is not the case that the\n\u003e spends approach is necessary for concurrency.\n\u003e \n\u003e To resolve the above two problems the version3 store does not use\n\u003e a spends table/index. Nor does it store any table of UTXOs. Yet \n\u003e validation is highly parallelized. Instead of additional indexes\n\u003e it uses the tx hash table, augmented with 32 bits per output for\n\u003e spender height. So there is a O(1) cost of finding the tx and a\n\u003e O(N) cost of finding the spender height where N is the number of\n\u003e outputs in the tx. But because the number of outputs in a tx is\n\u003e bounded (by block size) this is constant time in the number of\n\u003e 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\n\u003e hash tables. For low memory machines we found it was important to\n\u003e implement an opaque UTXO cache to limit paging, but for higher end\n\u003e systems zero cache is optimal.\n\u003e \n\u003e\u003e\u003e\u003e I am sharing this not only to ask for your feedback, but also\n\u003e\u003e\u003e\u003e to call for a clear separation of protocol and\n\u003e\u003e\u003e\u003e implementations: As this solution, reversing the costs of\n\u003e\u003e\u003e\u003e outputs and inputs, seems to have excellent performance\n\u003e\u003e\u003e\u003e characteristics (as shown in the test results), updates to\n\u003e\u003e\u003e\u003e the protocol addressing the UTXO growth, might not be worth\n\u003e\u003e\u003e\u003e considering *protocol improvements* and it might be best to\n\u003e\u003e\u003e\u003e 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\n\u003e pruned, which certainly exceeds the size of the UTXO set (unless\n\u003e nothing is spent). The advantage is that you don't have to keep\n\u003e rewriting the store when you use a spends set (because the store\n\u003e can be append only).\n\u003e \n\u003e Feel free to message me if you'd like to discuss in more detail, or\n\u003e to continue on the libbitcoin mailing list (copied).\n\u003e \n\u003e e\n-----BEGIN PGP SIGNATURE-----\nVersion: GnuPG v2.0.22 (GNU/Linux)\n\niQEcBAEBCAAGBQJY6WY4AAoJEDzYwH8LXOFO+wwH/1uE/+P1+KLJWTkcttVWsO//\nQAlikqg0HLFDtkd5jaYsBtx6op/Uz2o53ohZwVJt71ITCjQQI+yYK2RjBX92xIhd\nK0rE901Np4PfMFbDA60LB0c/65aPlkUCr3f2PYIlizJs4Qq5Kn2sIpC5v9T3B7H4\nMPq5UJwoPP+m3RZ9TSsVyee3ejHYXM7y2VNNnnWD3edIioA3cLh+y6sczpco2Hpa\nP+GSDnv2cwV6FA22Is1Z15tpfLyQnPrrGJ9QEJJ15vnhCTxZe0j1PQ4y+OOZh5Iq\nmqBkGRNPeUnPAPDM+/qvhr2kUyxFbaJNtwg5HDGHWFOq5B/YeKxVk8Qjnk+9epA=\n=XRKl\n-----END PGP SIGNATURE-----"}