{"type":"rich","version":"1.0","author_name":"npub149tvqh6gesh22h60jrehl5clrxscx6q65wznq9ty6pae8sxq00esg5vasy","author_url":"https://nostr.ae/npub149tvqh6gesh22h60jrehl5clrxscx6q65wznq9ty6pae8sxq00esg5vasy","provider_name":"njump","provider_url":"https://nostr.ae","html":"📅 Original date posted:2017-04-06\n📝 Original message:\u003e Just checking to see if I understand this optimization correctly. In order to find merkle roots in which the rightmost 32 bits are identical (i.e. partial hash collisions), we want to compute as many merkle root hashes as quickly as possible. The fastest way to do this is to take the top level of the Merkle tree, and to collect a set of left branches and right branches which can be independently manipulated. While the left branch can easily be manipulated by changing the extranonce in the coinbase transaction, the right branch would need to be modified by changing one of the transactions in the right branch or by changing the number of transactions in the right branch. Correct so far?\n\nEnvisioning it in my head and trying to read the white paper, it\nsounds like the process for a non-stratum mining farm would be this:\n\nOn primary server with sufficient memory, calculate ~4k-6k valid\nleft-side merkle tree roots and ~4k-6k right-side merkle tree roots.\nThen try hashing every left-side option with every right-side option.\nI'm not sure if modern asic chips are sufficiently generic that they\ncan also sha256-double-hash those combinations, but it seems logical\nto assume that the permutations of those hashes could be computed on\nan asic, perhaps via additional hardware installed on the server.\nHashing these is easier if there are fewer steps, i.e., fewer\ntransactions.\n\nOut of this will come N(2-16 at most, higher not needed) colliding\nmerkle roots where the last 4 bytes are identical.  Those N different\nmerkle combinations are what can be used on the actual mining devices,\nand those are all that needs to be sent for the optimization to work.\n\nOn the actual mining device, what is done is to take the identical\n(collision) right 4 bytes of the merkle root and hash it with one\nnonce value.  Since you have N(assume 8) inputs that all work with the\nsame value, calculating this single hash of once nonce is equivalent\nto calculating 8 nonce hashes during the normal process, and this step\nis 1/4th of the normal hashing process.  This hash(or mid-value?) is\nthen sent to 8 different cores which complete the remaining 3 hash\nsteps with each given collision value.  Then you increment the nonce\nonce and start over.\n\nThis works out to a savings of (assuming compressor and expander steps\nof SHA2 require computationally the same amount of time) 25% * (7 / 8)\nwhere N=8.\n\nGreg, or someone else, can you confirm that this is the right\nunderstanding of the approach?\n\n\u003e I have not seen or heard of any hardware available that can run more efficiently using getblocktemplate.\n\nAs above, it doesn't require such a massive change.  They just need to\nretrieve N different sets of work from the central server instead of 1\nset of work.  The central server itself might need substantial\nbandwidth if it farmed out the merkle-root hashing computational space\nto miners.  Greg, is that what you're assuming they are doing?  Now\nthat I think about it, even that situation could be improved.  Suppose\nyou have N miners who can do either a merkle-tree combinatoric\ndouble-sha or a block-nonce double-sha.  The central server calculates\nthe left and right merkle treeset to be combined and also assigns each\nminer each a unique workspace within those combinatorics.  The miners\ncompute each hash in their workspace and shard the results within\nthemselves according to the last 16 bits.  Each miner then needs only\nthe memory for 1/Nth of the workspace, and can report back to the\ncentral server only the highest number of collisions it has found\nuntil the central server is satisfied and returns the miners to normal\n(collided) mining.\n\nSeems quite workable in a large mining farm to me, and would allow the\ncollisions to be found very, very quickly.\n\nThat said, it strikes me that there may be some statistical method by\nwhich we can isolate which pools seem to have used this approach\nagainst the background noise of other pools.  Hmm...\n\nJared\n\n\n\nOn Wed, Apr 5, 2017 at 7:10 PM, Jonathan Toomim via bitcoin-dev\n\u003cbitcoin-dev at lists.linuxfoundation.org\u003e wrote:\n\u003e Just checking to see if I understand this optimization correctly. In order to find merkle roots in which the rightmost 32 bits are identical (i.e. partial hash collisions), we want to compute as many merkle root hashes as quickly as possible. The fastest way to do this is to take the top level of the Merkle tree, and to collect a set of left branches and right branches which can be independently manipulated. While the left branch can easily be manipulated by changing the extranonce in the coinbase transaction, the right branch would need to be modified by changing one of the transactions in the right branch or by changing the number of transactions in the right branch. Correct so far?\n\u003e\n\u003e With the stratum mining protocol, the server (the pool) includes enough information for the coinbase transaction to be modified by stratum client (the miner), but it does not include any information about the right side of the merkle tree except for the top-level hash. Stratum also does not allow the client to supply any modifications to the merkle tree (including the right side) back to the stratum server. This means that any implementation of this final optimization would need to be using a protocol other than stratum, like getblocktemplate, correct?\n\u003e\n\u003e I think it would be helpful for the discussion to know if this optimization were currently being used or not, and if so, how widely.\n\u003e\n\u003e All of the consumer-grade hardware that I have seen defaults to stratum-only operation, and I have not seen or heard of any hardware available that can run more efficiently using getblocktemplate. As the current pool infrastructure uses stratum exclusively, this optimization would require significant retooling among pools, and probably a redesign of their core algorithms to help discover and share these partial collisions more frequently. It's possible that some large private farms have deployed a special system for solo mining that uses this optimization, of course, but it's also possible that there's a teapot in space somewhere between the orbit of Earth and Mars.\n\u003e\n\u003e Do you know of any ways to perform this optimization via stratum? If not, do you have any evidence that this optimization is actually being used by private solo mining farms? Or is this discussion purely about preventing this optimization from being used in the future?\n\u003e\n\u003e -jtoomim\n\u003e\n\u003e\u003e On Apr 5, 2017, at 2:37 PM, Gregory Maxwell via bitcoin-dev \u003cbitcoin-dev at lists.linuxfoundation.org\u003e wrote:\n\u003e\u003e\n\u003e\u003e An obvious way to generate different candidates is to grind the\n\u003e\u003e coinbase extra-nonce but for non-empty blocks each attempt will\n\u003e\u003e require 13 or so additional sha2 runs which is very inefficient.\n\u003e\u003e\n\u003e\u003e This inefficiency can be avoided by computing a sqrt number of\n\u003e\u003e candidates of the left side of the hash tree (e.g. using extra\n\u003e\u003e nonce grinding) then an additional sqrt number of candidates of\n\u003e\u003e the right  side of the tree using transaction permutation or\n\u003e\u003e substitution of a small number of transactions.  All combinations\n\u003e\u003e of the left and right side are then combined with only a single\n\u003e\u003e hashing operation virtually eliminating all tree related\n\u003e\u003e overhead.\n\u003e\u003e\n\u003e\u003e With this final optimization finding a 4-way collision with a\n\u003e\u003e moderate amount of memory requires ~2^24 hashing operations\n\u003e\u003e instead of the \u003e2^28 operations that would be require for\n\u003e\u003e extra-nonce  grinding which would substantially erode the\n\u003e\u003e benefit of the attack.\n\u003e\n\u003e\n\u003e _______________________________________________\n\u003e bitcoin-dev mailing list\n\u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev\n\u003e"}