A comment on Andrew Poelstra's paper ASICs and Decentralization FAQ

[jvanname]

So this post is a comment on Andrew Poelstra's paper "ASICs and Decentralization FAQ" https://download.wpsoftware.net/bitcoin/asic-faq.pdf about Landauer's limit for cryptocurrency mining. Landauer's principle states that erasing a bit always uses ln(2)*k*T energy where T is the temperature and k is Boltzmann's constant (in other words, erasing bits always produces entropy and use energy). Since conventional computation (by conventional computation I mean irreversible computation) always requires one to erase information, conventional computation is subject to Landauer's limit. However, reversible computation is not subject to Landauer's limit, so reversible computation is potentially many times more efficient than irreversible computation.

Andrew Poelstra argues that ASIC resistance for POW problems is undesirable since ASICs push cryptocurrency mining efficiency towards Landauer's limit and when the efficiency of ASICs reaches Landauer's limit, the probability that one will add the next block to the blockchain will be proportional to the amount of energy used to mine that block. Therefore since energy usage is decentralized, as the efficiency of ASICs reaches Landauer's limit, these ASIC friendly cryptocurrencies will themselves be decentralized.

I have an issue with this reasoning however. As ASICs approach Landauer's limit, people will produce reversible computing devices which are not subject to Landauer's limit. Andrew Poelstra claims that hash-based cryptocurrency mining problems are essentially irreversible and are therefore subject to Landauer's limit. I claim that these POW problems are not subject to Landauer's limit however because the garbage bits produced by hashes can be uncomputed instead of erased. In reversible computation and quantum computation, uncomputing refers to running a computation in reverse in order to erase garbage information. Uncomputing is completely reversible and not subject to Landauer's limit. By using uncomputation, hash-based cryptocurrency mining can be made nearly reversible and therefore not subject to Landaeur's limit. Uncomputation takes as many steps as the original computation. Therefore, if it takes N steps to compute a function on a conventional device, then it will take 2N steps on a reversible device to compute the original computation and then uncompute all of the garbage information accumulated. Uncomputation also has some memory overhead since one must keep all the garbage data in memory until it is time to uncompute (conventional computation does not have this memory overhead since one can delete information at any time using a conventional computer). However, the gains in energy efficiency of reversible computation will eventually exceed the overhead costs of reversible computing devices that comes from storing garbage data and uncomputing that garbage data.

Frank's law states that reversible computation will eventually be necessary for high performance computing-"Achieving the maximum possible computational performance for a given rate of bit dissipation generally requires explicit reversibility not only at the lowest level, but at all levels of computing--in devices, circuits, architectures, languages, and algorithms (a strongly conjectured, but not yet formally proven result-call it Frank's Law)." Eventually reversible devices for mining cryptocurrencies will be more efficient than Landauer's limit for conventional devices. Therefore, the decentralization of cryptocurrency POW problems will never be proportional to the decentralization of energy usage.

Instead of relying on Landauer's limit to enforce the decentralization of POW problems, one should instead employ many different kinds of POW problems for a cryptocurrency. It will be much more difficult to launch a 51 percent attack against a cryptocurrency with 100 different POW problems than it will be to launch such an attack against a cryptocurrency with only one POW. Furthermore, cryptocurrency mining today is essentially a multi-billion dollar pollution contest (whoever produces the most pollution wins) since these POW problems have no other practical use outside the cryptocurrency market. It will be much easier to securely use a useful POW problem in a cryptocurrency if there are many different kinds of POW problems for that cryptocurrency than if there is only one useful POW problem for that cryptocurrency.

-Joseph Van Name Ph.D.
boolesrings.org/jvanname

[1713857182]

1713857182

[1713857182]

1713857182

[puwaha]

Instead of relying on Landauer's limit to enforce the decentralization of POW problems, one should instead employ many different kinds of POW problems for a cryptocurrency. It will be much more difficult to launch a 51 percent attack against a cryptocurrency with 100 different POW problems than it will be to launch such an attack against a cryptocurrency with only one POW. Furthermore, cryptocurrency mining today is essentially a multi-billion dollar pollution contest (whoever produces the most pollution wins) since these POW problems have no other practical use outside the cryptocurrency market. It will be much easier to securely use a useful POW problem in a cryptocurrency if there are many different kinds of POW problems for that cryptocurrency than if there is only one useful POW problem for that cryptocurrency.

There are some interesting assertions that I'll need to dive more into later, but you can already see a trend with newer POW based coins that aren't straight copies of existing coins with a name change.  They are combining known algorithms to create new schemes of POW just like you suggest.  They are using multiple kinds of POW problems.

For instance you have something like Chaincoin with their C11 scheme, and Denarius coin with their Tribus scheme.  [Disclosure: I advertise Denarius coin in my signature block, but I didn't put them here in this reply for that reason.]

I think you will see more coins doing this to help them stand out from the crowded field, maybe not realizing the potential impact they are having on what "better, more secure POW" looks like.

[jvanname]

I would not consider having a chained hash or combining multiple hash functions together as multiple POW problems since combining multiple hash functions together simply creates a more complicated hash function or hash-like function. Using a complicated hash function will not achieve decentralization because mining power will be centralized towards the entities who have access to ASICs which can compute these complicated hash functions.

By a multi-POW problem, I mean that the cryptocurrency has a system in place where for example there are 10 different kinds of POW problems and each of these problems have their distinct difficulty level so that each of these 10 problems is solved about 10% of the time or possibly where the blocks in the blockchain cycle through these problems. This will achieve decentralization since it will be difficult for an entity to be the best at solving each of these 10 different kinds of POW problems. To maximize decentralization, one should also not just include hash-based POW problems but as many different kinds of POW problems as well.

[jvanname]

The idea that computing hash functions to mine cryptocurrencies necessarily takes energy because of Landauer's principle is also found in the book
"Bitcoin and Cryptocurrency Technologies: A Comprehensive Introduction." I need to contact the authors of the book about this issue and about how one could recycle the energy used to compute SHA-256 hashes by uncomputing these hashes.

[puwaha]

I would not consider having a chained hash or combining multiple hash functions together as multiple POW problems since combining multiple hash functions together simply creates a more complicated hash function or hash-like function. Using a complicated hash function will not achieve decentralization because mining power will be centralized towards the entities who have access to ASICs which can compute these complicated hash functions.

By a multi-POW problem, I mean that the cryptocurrency has a system in place where for example there are 10 different kinds of POW problems and each of these problems have their distinct difficulty level so that each of these 10 problems is solved about 10% of the time or possibly where the blocks in the blockchain cycle through these problems. This will achieve decentralization since it will be difficult for an entity to be the best at solving each of these 10 different kinds of POW problems. To maximize decentralization, one should also not just include hash-based POW problems but as many different kinds of POW problems as well.

I'm not sure if miners would participate if they can only solve a block every 10 blocks.  That would be in addition to the luck factor in solving a block on the algo for which they have an ASIC for already.  You would have to heavily incentivize miners to potentially reduce their mining rates by 90%, or lower their barrier to entry with low-cost ASICs.

And none of this speaks to the problem of difficulty.  The more decentralized your pool of miners becomes, the more difficulty rises, which inversely affects miners.  They get fewer mining rewards, and become disincentivized to participate.  Realistically, you will also have ASICs that are more efficient at certain algos than others... so miners will gravitate towards those ASICS as they are more profitable.  This will tilt difficulty for a specific algo to an even worse state of competition.  If each algo had it's own difficulty parameters, but the rewards were the same, then you might see some balance across the 10 POW algos.  But, then again, you may have miners crying "foul" because ASICs tend to be in short supply, and the most efficient ASICs would be preferred.

[jvanname]

The only way that I see a multiple algorithm POW of working is if each algorithm has its own difficulty level. Otherwise, certain types of POW problems will be solved much more often than other kinds of POW problems and this will defeat the purpose of having multiple POW problems in the first place.

One does not have to upgrade the POW problem if one develops a new cryptocurrency with a multi-algorithm POW problem. For existing cryptocurrencies, miners have a conflict of interest in selecting or upgrading the POW problems since it is in their interest to maintain centralization and to maintain the current POW so that they do not have too much competition. The non-mining stakeholders however do not have this conflict of interest and they will want as much decentralized mining as possible. On the other hand, stakeholders will also have an incentive not to haphazardly change the POW problems since they do not want to turn away any miners. It is therefore best for the stakeholders to make the decisions on upgrading the POW problems instead of the miners. One way for an existing cryptocurrency to switch from a single algorithm POW problem to a multi-algorithm POW without harming the miners would be to gradually introduce new POW problems over a couple years.