13 ms·

This is excellent. I've been trying to find a technical explanation of ASCIBOOST for some time. Most of the articles and discussions gloss over the details.

This is excellent. I've been trying to find a technical explanation of ASCIBOOST for some time. Most of the articles and discussions gloss over the details. It is possible that this is part of the reason some miners are blocking SegWit but there is more to it. Core (the main Bitcoin development team) promised to provide a block size scaling solution and then reneged. This pissed a lot of people off and led to the blocking of SegWit. I don't see ASCIBOOST as a real problem for Bitcoin.

tromp 10y ago
The AsicBoost inventors also wrote a good technical explanation at https://arxiv.org/pdf/1604.00575v1 https://arxiv.org/pdf/1604.00575v1
- jlrubin 10y ago
  Notably, they don't include the optimal root generation algorithm, nor do they discuss segwit incompatibilities. Also, their 20% figure is unclear. The more collisions you can find, the more hash per second you should be able to gain.
  - jcoffland 10y ago
    > The more collisions you can find, the more hash per second you should be able to gain. But the chance of finding three blocks with the necessary 4 byte collision is much more difficult. It's the same problem as finding 3 people with the same birthday. You need 87 people to have a 50/50 chance of three people having the same birthday vs. 23 for two people who share a birthday. That's nearly a 4x increase in required computation for a small increase in effective hash rate.
    - jlrubin 10y ago
      It's not that big of a computation even at 4 collisions, but yes, I'm familiar with the math (I wrote the PDF).
      - jcoffland 10y ago
        Do you have actual numbers handy? The point is that you only have about 10 mins to work on a block. The longer it takes to compute collisions the less benefit you get from them. That is unless you precompute the collisions using irrelevant transaction data. The collisions must be recomputed everytime one of the transactions used is accepted on the blockchain.
    - TD-Linux 10y ago
      Certain miners implementing ASICBOOST in their ASIC also have a FPGA with DRAM that could be used to find the 4 byte collisions extremely quickly. The calculation can be used for the hundreds of ASICs attached to the FPGA board. It's an easy win.
      - jcoffland 10y ago
        Right, but we're discussing the cost of finding more than two collisions.
        TD-Linux 10y ago
        Yes, you ideally want four, as that seems to be the maximum number that the chips support. I believe the zynq is still capable of that.
  - makomk 10y ago
    Indeed. As I understand it, the core Bitcoin developers only fully figured out how the covert version of ASICBOOST was implemented in practice and realised that it was incompatible with not just Segwit but a whole class of Bitcoin extensions a few days ago: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-April/013996.html https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017... Think about that. It looks like miners had been blocking a scalability extension for over a year not because of any of their stated complaints against it, but because they'd secretly rolled out hardware using a secret acceleration technique that was incompatible with extending Bitcoin. That's scary. (There's some explanation of which other kinds of improvements it'd block in the follow-up here: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-April/014000.html https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017... ) Furthermore, the miners in question were apparently plotting a Bitcoin protocol change without public discussion whose actual purpose appeared to be permanently blocking such future enhancements: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-April/014003.html https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017...
AgentME 10y ago
>I don't see ASCIBOOST as a real problem for Bitcoin. It often incentivizes miners to reorder or drop transactions until they hash to a specific value. (A certain mining pool is publishing a significant number of empty blocks.) Miners exist to verify transactions, and Bitcoin was designed with transaction fees in order to incentivize miners to include transactions. A competing force pushing miners away from including transactions that can be trivially fixed is just a bug. Imagine a mining "optimization" which involved miners making only empty blocks. That goes against why Bitcoin has mining in the first place, and would delay transactions eventually to a halt as more took advantage of the optimization. A trick that only often encourages miners to make empty blocks isn't categorically different, and it's something suboptimal about Bitcoin that can be fixed.
- 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
Another problem with ASICBOOST is that it incentivizes a miner to try to partition the network such that the orphan rate increases, because mining on top of orphan blocks is more profitable. If we have two competing successors (S_1 and S_2) to a Block B, an ASICBOOST miner can mine both simultaneously by creating Chunk 1's with different parent blocks. I call it "The Oliver Twist Attack". Increasing the Oprhan rate is incredibly costly to affected miners, this has the effect of making it also increase the hash rate of the attacker.
- jcoffland 10y ago
  This would be easy to detect. Just look for miners who regularly revive orphaned blocks.
deleted 10y ago
[deleted]
shea256 10y ago
> Core (the main Bitcoin development team) promised to provide a block size scaling solution and then reneged. This is not true at all and highly deceptive. They originally were supportive of doubling the transaction count via an increase to 2MB blocks and then realized they could accomplish this without a hard fork via SegWit. SegWit does in fact allow for 1.7x the number of single-signature transactions per block and 4x for multi-signature transactions. Core absolutely could have handled the communications around this better. But to say they reneged on providing a scaling solution is wrong. It's also important to keep in mind that what matters is not the block size but the number of transactions that can fit into a block. Block size doubling and cutting transaction sizes in half each double the throughput.
- hudon 10y ago
  > But to say they reneged on providing a scaling solution is wrong. Regardless of your position in the debate, to say that many well-known Core developers reneged is absolutely defensible, given than they signed this: https://medium.com/@bitcoinroundtable/bitcoin-roundtable-consensus-266d475a61ff https://medium.com/@bitcoinroundtable/bitcoin-roundtable-con... The agreement between all these parties was that they'd all support a SegWit soft-fork if Core developers also provided code and support for a ~2mb hard fork.
- 6nf 10y ago
  > Block size doubling and cutting transaction sizes in half each double the throughput. You can only cut transaction sizes in half once, but you can always double the block size again. Let's just double the block size?
  - jcoffland 10y ago
    SegWit does not cut block sizes in half it moves some data out of the main block and in to the SegWit block. Full nodes will need more disk space per transaction with SegWit not less.
- jcoffland 10y ago
  There is nothing deceptive about saying Core did not deliver on their promise to increase the block size. We still don't have a block size increase. Saying that SegWit provides the promised increase is deceptive. SegWit provides a theoretical 1.7x increase but only if everyone switches to SegWit transactions. To send a SegWit transaction you must upgrade your software, understand how to configure it to send SegWit transactions and be sure that the receiver's software understands SegWit. The only conclusion is that SegWit's effective block size increase will not take effective immediately. Regardless, Core signed an agreement with a majority of miners that they would implement a block size increase, not an effective block size increase but a real one. They reneged on this promise and are instead telling everyone that they are going to do as they please because miners don't control BitCoin.

tromp 10y ago

The AsicBoost inventors also wrote a good technical explanation at https://arxiv.org/pdf/1604.00575v1 https://arxiv.org/pdf/1604.00575v1

jlrubin 10y ago
Notably, they don't include the optimal root generation algorithm, nor do they discuss segwit incompatibilities. Also, their 20% figure is unclear. The more collisions you can find, the more hash per second you should be able to gain.
- jcoffland 10y ago
  > The more collisions you can find, the more hash per second you should be able to gain. But the chance of finding three blocks with the necessary 4 byte collision is much more difficult. It's the same problem as finding 3 people with the same birthday. You need 87 people to have a 50/50 chance of three people having the same birthday vs. 23 for two people who share a birthday. That's nearly a 4x increase in required computation for a small increase in effective hash rate.
  - jlrubin 10y ago
    It's not that big of a computation even at 4 collisions, but yes, I'm familiar with the math (I wrote the PDF).
    - jcoffland 10y ago
      Do you have actual numbers handy? The point is that you only have about 10 mins to work on a block. The longer it takes to compute collisions the less benefit you get from them. That is unless you precompute the collisions using irrelevant transaction data. The collisions must be recomputed everytime one of the transactions used is accepted on the blockchain.
  - TD-Linux 10y ago
    Certain miners implementing ASICBOOST in their ASIC also have a FPGA with DRAM that could be used to find the 4 byte collisions extremely quickly. The calculation can be used for the hundreds of ASICs attached to the FPGA board. It's an easy win.
    - jcoffland 10y ago
      Right, but we're discussing the cost of finding more than two collisions.
      - TD-Linux 10y ago
        Yes, you ideally want four, as that seems to be the maximum number that the chips support. I believe the zynq is still capable of that.
- makomk 10y ago
  Indeed. As I understand it, the core Bitcoin developers only fully figured out how the covert version of ASICBOOST was implemented in practice and realised that it was incompatible with not just Segwit but a whole class of Bitcoin extensions a few days ago: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-April/013996.html https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017... Think about that. It looks like miners had been blocking a scalability extension for over a year not because of any of their stated complaints against it, but because they'd secretly rolled out hardware using a secret acceleration technique that was incompatible with extending Bitcoin. That's scary. (There's some explanation of which other kinds of improvements it'd block in the follow-up here: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-April/014000.html https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017... ) Furthermore, the miners in question were apparently plotting a Bitcoin protocol change without public discussion whose actual purpose appeared to be permanently blocking such future enhancements: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-April/014003.html https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017...

AgentME 10y ago

>I don't see ASCIBOOST as a real problem for Bitcoin. It often incentivizes miners to reorder or drop transactions until they hash to a specific value. (A certain mining pool is publishing a significant number of empty blocks.) Miners exist to verify transactions, and Bitcoin was designed with transaction fees in order to incentivize miners to include transactions. A competing force pushing miners away from including transactions that can be trivially fixed is just a bug. Imagine a mining "optimization" which involved miners making only empty blocks. That goes against why Bitcoin has mining in the first place, and would delay transactions eventually to a halt as more took advantage of the optimization. A trick that only often encourages miners to make empty blocks isn't categorically different, and it's something suboptimal about Bitcoin that can be fixed.

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

Another problem with ASICBOOST is that it incentivizes a miner to try to partition the network such that the orphan rate increases, because mining on top of orphan blocks is more profitable. If we have two competing successors (S_1 and S_2) to a Block B, an ASICBOOST miner can mine both simultaneously by creating Chunk 1's with different parent blocks. I call it "The Oliver Twist Attack". Increasing the Oprhan rate is incredibly costly to affected miners, this has the effect of making it also increase the hash rate of the attacker.

jcoffland 10y ago
This would be easy to detect. Just look for miners who regularly revive orphaned blocks.

deleted 10y ago

[deleted]

shea256 10y ago

> Core (the main Bitcoin development team) promised to provide a block size scaling solution and then reneged. This is not true at all and highly deceptive. They originally were supportive of doubling the transaction count via an increase to 2MB blocks and then realized they could accomplish this without a hard fork via SegWit. SegWit does in fact allow for 1.7x the number of single-signature transactions per block and 4x for multi-signature transactions. Core absolutely could have handled the communications around this better. But to say they reneged on providing a scaling solution is wrong. It's also important to keep in mind that what matters is not the block size but the number of transactions that can fit into a block. Block size doubling and cutting transaction sizes in half each double the throughput.

hudon 10y ago
> But to say they reneged on providing a scaling solution is wrong. Regardless of your position in the debate, to say that many well-known Core developers reneged is absolutely defensible, given than they signed this: https://medium.com/@bitcoinroundtable/bitcoin-roundtable-consensus-266d475a61ff https://medium.com/@bitcoinroundtable/bitcoin-roundtable-con... The agreement between all these parties was that they'd all support a SegWit soft-fork if Core developers also provided code and support for a ~2mb hard fork.
6nf 10y ago
> Block size doubling and cutting transaction sizes in half each double the throughput. You can only cut transaction sizes in half once, but you can always double the block size again. Let's just double the block size?
- jcoffland 10y ago
  SegWit does not cut block sizes in half it moves some data out of the main block and in to the SegWit block. Full nodes will need more disk space per transaction with SegWit not less.
jcoffland 10y ago
There is nothing deceptive about saying Core did not deliver on their promise to increase the block size. We still don't have a block size increase. Saying that SegWit provides the promised increase is deceptive. SegWit provides a theoretical 1.7x increase but only if everyone switches to SegWit transactions. To send a SegWit transaction you must upgrade your software, understand how to configure it to send SegWit transactions and be sure that the receiver's software understands SegWit. The only conclusion is that SegWit's effective block size increase will not take effective immediately. Regardless, Core signed an agreement with a majority of miners that they would implement a block size increase, not an effective block size increase but a real one. They reneged on this promise and are instead telling everyone that they are going to do as they please because miners don't control BitCoin.