3 ms·

I believe it also probably incentivizes miners to create smaller blocks full stop, since dealing with transaction dependencies - something this glosses over - m

by makomk 10y ago

I believe it also probably incentivizes miners to create smaller blocks full stop, since dealing with transaction dependencies - something this glosses over - means that the cost will likely scale with the number of transactions. This rather undercuts the supposed block size scaling justification for opposing Segwit, to put it mildly.

nullc 10y ago
This is perhaps misinformed. There is not reason to deal with transaction dependencies because permutation is just one option and not an especially attractive one. Without protocol upgrades that include commitments to other parts of the block (E.g. committed utxo, committed bloom filters, stxo, segwit, fraud proofs, etc) you can simply compute 4096 variations of left- side of the tree by altering the coinbase transaction and 4096 versions of the right side of the tree by just substituting any transaction on the right side with alternatives. Then combine the two in to the ~2^24-ish needed for a collision with only a single operation per try which is independent of the size of the block. The lack of a commitment gets you another effective sqrt speedup and makes all the other costs negligible. Now, as far as permutation goes, if you want to permute instead of replace you need only permute 7 transaction on the right side to get the variations you need. Virtually no blocks with more than a dozen transactions don't have at least 7 on the right side with no dependencies at all.
- jlrubin 10y ago
  Greg, I think the recursive algorithm should still be faster on the left hand side than just rolling the coinbase extra nonce, but after the first sqrt the numbers are pretty small so maybe the constants dominate.
  - optimiz3 10y ago
    A SegWit commitment on the left hand side causes any permutation on the right hand side to force a recalculation of the left hand side. This is still a non-issue as a solid GPU farm can crunch the SegWit version trivially and there are ASICBOOST compatible optimizations for SegWit that have not been publicly discussed. One should look at the R&D on ZCash's equihash to see some of the work that has gone into collision finding.

by makomk 10y ago

nullc 10y ago

This is perhaps misinformed. There is not reason to deal with transaction dependencies because permutation is just one option and not an especially attractive one. Without protocol upgrades that include commitments to other parts of the block (E.g. committed utxo, committed bloom filters, stxo, segwit, fraud proofs, etc) you can simply compute 4096 variations of left- side of the tree by altering the coinbase transaction and 4096 versions of the right side of the tree by just substituting any transaction on the right side with alternatives. Then combine the two in to the ~2^24-ish needed for a collision with only a single operation per try which is independent of the size of the block. The lack of a commitment gets you another effective sqrt speedup and makes all the other costs negligible. Now, as far as permutation goes, if you want to permute instead of replace you need only permute 7 transaction on the right side to get the variations you need. Virtually no blocks with more than a dozen transactions don't have at least 7 on the right side with no dependencies at all.

jlrubin 10y ago
Greg, I think the recursive algorithm should still be faster on the left hand side than just rolling the coinbase extra nonce, but after the first sqrt the numbers are pretty small so maybe the constants dominate.
- optimiz3 10y ago
  A SegWit commitment on the left hand side causes any permutation on the right hand side to force a recalculation of the left hand side. This is still a non-issue as a solid GPU farm can crunch the SegWit version trivially and there are ASICBOOST compatible optimizations for SegWit that have not been publicly discussed. One should look at the R&D on ZCash's equihash to see some of the work that has gone into collision finding.