A technique that could be used to construct and improve proof-of-work problems.

In this post, I am going to talk about a trick using hash functions that takes computational problems and makes them suited or better suited to use as cryptocurrency proof-of-work (POW) problems. Yes, this trick can be applied to any potential cryptocurrency POW problem.

Review and references

If you are already familiar with cryptocurrencies and cryptocurrency POW problems, then feel free to skip this section. If you are not familiar with cryptocurrencies and their POW problems, then please read Satoshi Nakamoto’s paper Bitcoin. For a more in-depth study of cryptocurrencies, I recommend the coursera course Bitcoin and Cryptocurrency Technologies (there is also a book Bitcoin and Cryptocurrency Technologies that I recommend).

If you have not read Satoshi Nakamoto’s paper and don’t plan to right now, then just take note that many cryptocurrencies are distributed by solving computational problems which are known as proof-of-work problems; the process of solving these problems is known as mining.

Requirements for cryptocurrency POW problems

Consider the following characteristics which are desirable or required in POW problems.

  1. (Verifiable but intractible) The problem must be difficult to solve yet easy to verify.
  2. (Fine tunability) The difficulty of the problem must be finely tunable so that coins are distributed at a constant rate.
  3. (Automatic generation) Instances of the problem must be generated automatically and efficiently.
  4. (Solution tied to block and solver) The solutions must depend on the block and the solver of the block so that a valid solution for Alice will no longer be a valid solution for Bob.
  5. (Usefulness) The solution to the problem together with the process of obtaining the solution should have enough value outside the cryptocurrency to justify the resources used to solve the problem.

Let me now add a few more desired characteristics for proof-of-work problems.

  1. (Endless problems) There should be an unlimited amount of problems to work on so that the POW will not quickly expire.
  2. (Unbreakability) The problem should be cryptographically secure in the sense that it should be thought to be impossible for an entity to have a secret algorithm that solves the POW problem at a much faster rate than everyone else can. If an entity has a secret algorithm, then that entity could launch a 51 percent attack, and such a secret algorithm will produce an unfair wealth distribution.
  3. (Progress-freeness and pre-computation resistance) Suppose that Alice and Bob are working on the POW problem and they both have an equal amount of computational power. If Alice has not solved the problem but Alice has started working on the problem five minutes ago, then Alice should have no advantage over Bob in solving the POW problem. Furthermore, Alice should have no way of computing the solutions in advance. The chance of someone solving the mining problem needs to be directly proportional to her computational power.

The multi-algorithm approach

So one way to alleviate the issues that arise with useful POW problems is to use multiple POW problems so that the cryptocurrency does not fall apart in the case that there is a bad POW problem or in the case that a POW problem becomes bad. Characteristics 1-4 and i-iii are required for all cryptocurrencies with a single POW problem, but characteristics i-iii though desired are not required for cryptocurrencies with many POW problems.

There may be some POW problems which are useful up to a point but where the practical value of these problems satisfies the law of diminishing returns, but with a multi-algorithm POW, certain problems may be retired from the problem schedule when their practical value is no longer worth the computational effort put into solving them. Multiple algorithm POW problems also help alleviate the initial distribution problem for cryptocurrencies since multiple algorithms will distribute a new cryptocurrency more evenly and fairly than a single algorithm could.

A POW scheme consisting of many algorithms is much more complex than a single algorithm scheme and it will take much more work to develop a multi-algorithm POW scheme than a single algorithm POW (in a multi-algorithm POW scheme, one also needs to develop techniques for removing broken or outdated problems; for example, in a multi-algorithm POW, one will need to have a system that automatically removes a broken problem once someone submits a formal proof that the POW problem can be solved in polynomial time).

The solution lottery technique

The solution lottery technique is a tool that one can use to make a POW problem obtain several of the advantages of hash based POW problems without any of their disadvantages. Stated informally, the solution lottery technique (SLT) is a technique where one increases the difficulty of a POW problem without changing any other characteristic of the POW problem simply by only accepting solutions with exceptionally low hashes. While the SLT uses hash functions, the SLT is designed so that a miner seldomly calls upon a hash function in order to solve the POW problems. Therefore, miners will focus their energy on solving the main problem rather than computing hashes.

Let me now state how the SLT is applied to a typical POW problem. Suppose that $D$ is a set of ordered pairs. Suppose that $H$ is a cryptographic hash function and $\text{Data}(k,x)$ is a piece of information that can be easily obtained when after one verifies that $(k,x)\in D$ but which cannot be obtained if one does not verify whether $(k,x)\in D$ or not.

Problem A without SLT: The objective of Problem A is to find an input $x$ and a suitable hash $k$ so that $(k,x)\in D$.

Problem A with SLT: The objective of Problem A with SLT is to find an input $x$ along with a suitable hash $k$ so that $(k,x)\in D$ and $H(k||x||\text{Data}(k,x)) < C$.
For Problem A with or without the SLT, the data $k$ may be reused many times, so one does not have to compute very many hashes $k$ but one has to determine whether $(k,x)\in D$ many times. Similarly, one only has to compute the hash $H(k||x||\text{Data}(k,x))$ if $(k,x)\in D$. Since hash functions are computed seldomly with the SLT, miners will devote almost all of their resources into finding pairs $(k,x)\in D$ rather than in computing hashes, and hence the POW problems will retain their characteristics such as usefulness or ASIC resistance with or without the SLT. The input $\text{Data}(k,x)$ is necessary for the SLT to opeate correctly since otherwise a miner would solve Problem A with SLT simply by first computing $H(k||x)$ and if $H(k||x) < C$, then the miner would verify whether $(k,x)\in D$ (and hence the miner would most of the resources computing hashes rather than determinine whether $(k,x)\in D$).
Let us now look at a few ways that the SLT can improve cryptocurrency POW problems.

Fine-tunability: It may be difficult to fine tune the difficulty of a certain POW problem. However, with the SLT, it is much easier to fine tune the difficulty of the POW problem since the software simply has to adjust the parameter $C$ in order to make the problem easier or more difficult.

Smoothly tuning coarse parameters with SLT: In some POW problems, changing the set $D$ could change the difficulty of the POW problem in an unpredictable manner. The SLT could help smoothly change the set $D$ in these cases. Suppose that the POW problem at block $n$ is to find a hash $k$ and data $x$ so that $(k,x)\in D$ and $H(k||x||\text{Data}(k,x)) < C$. Then the POW starting in block $n+1$ would be to find a hash $k$ and data $x$ so that ($(k,x)\in D$ and $H(k||x||\text{Data}(k,x)) < C$) or ($(k,x)\in D'$ and $H(k||x||\text{Data}(k,x)) < C'$) where $C'$ is chosen so that it is easier to find $k,x$ so that $(k,x)\in D$ and $H(k||x||\text{Data}(k,x)) < C$ than it is to find $k,x$ so that $(k,x)\in D'$ and $H(k||x||\text{Data}(k,x)) < C'$. Then the constant $C'$ will gradually increase. At the same time, the constant $C$ will decrease so that the difficulty of the POW problem remains constant until $C=0$ and when $C=0$, the POW problem will simply be to find $k,x$ so that $(k,x)\in D'$ and $H(k||x||\text{Data}(k,x)) < C'$.
Security boost: The SLT can also take very low security POW problems and make these problems viable as cryptocurrency POW problems even though their security level without the SLT is very low.

Progress freeness: The SLT could also be used to take a POW problem which is not progress free and make it into a problem which is progress free. For example, suppose that one wants to use a POW problem that incentivizes the development of computers that can perform tasks at higher and higher frequencies (I am currently as of January of 2018 not endorsing nor opposing this kind of POW problem as a useful POW problem). Then the POW problem should be a problem which can be easily verified but where the most efficient algorithm for solving the POW problem requires one to perform N steps in a sequence so that the person with the computer that runs at the highest frequency always wins the block reward. This POW problem without the SLT however is a very bad problem for cryptocurrencies since the entity with the fastest processor will always win; this problem is not progress free. However, the SLT can take this problem and turn it into a progress free problem which still incentivizes people to develop faster computers. Suppose that $N$-step version of this POW problem without the SLT is to find a pair $(k,x)$ such that $(k,x)\in D_{N}$. Then the goal of this POW problem with the SLT is to find a pair $(k,x)$ where $k$ is a hash and $x$ is data so that $(k,x)\in D_{N}$ and $H(k||x||\text{Data}(k,x)) Suppose that the problem of finding a suitable hash $k$ along with data $x$ so that $(k,x)\in D$ has only 32 bits of security. Furthermore, suppose that any increase in the security level of the cryptocurrency POW problem will make the verification of the POW problem too inefficient to use in practice (useful POW problems tend to take a much longer time to validate than useless POW problems). Then while the problem of finding some $(k,x)\in D$ will not be a viable POW problem since its difficulty cannot be increased beyond 32 bits of security, the problem of
finding some $(k,x)\in D$ where $H(k||x||\text{Data}(k,x)) < C$ could be made arbitrarily difficult.

The lost solution problem for the SLT

In a useful POW problem that employs the SLT where the solutions to the problems themselves are of a practical use, someone needs to keep a record of the solutions $(k,x)$ where $(k,x)\in D$ but $H(k||x||\text{Data}(k,x)) \geq C$ which are thrown out using the solution lottery technique; the fact that the SLT throws out useful solutions to a POW problem shall be called the lost solution problem (LSP) for this post. The solution thrown out by the SLT do not need to be posted on the blockchain nor should they be put on the blockchain, but they need to be publicly available. For useful POW problems where the process of obtaining a solution rather than the solution itself is what is important, the LSP is not an issue, but it is an issue to useful POW problems where the solution itself is of interest. The most basic solution to the LSP is for the miners to post their inputs $(k,x)$ where $k$ is an appropriate hash and where $(k,x)\in D$ but $H(k||x||\text{Data}(k,x))\geq C$ or where $(k,x)$ is an otherwise good solution simply as a matter of courtesy. Miners would probably be willing to post these solutions as a matter of courtesy since it does not take very much work to post these solutions. If a miner is discourteous and does not post his solutions, then the POW will not be as useful as it could be, but the cryptocurrency will not suffer from any security weaknesses, so discourteous miners can only do a limited amount of harm against the reputation of the cryptocurrency. Courtesy may not be a strong enough incentive for miners to compel them to post their solutions since courtesy does not give miners any financial incentive. Furthermore, if the miners have an incentive to keep their solutions as a secret, they will not be willing to post their solutions simply out of courtesy. Therefore, in order to solve the SLT problem by incentivizing miners to post their solutions, the cryptocurrency protocol should require all miners to accept the blockchain fork backed up with the highest number of posted solutions $(k,x)$ such that $(k,x)\in D$. Since the cryptocurrency miners do not want their blocks to become orphan blocks, they will post all of their solutions $(k,x)$ such that $(k,x)\in D$ and they will only mine on the fork with the most solutions $(k,x)$ such that $(k,x)\in D$. The miners may also be encouraged to boycott all chains if they suspect that the miner has not posted all of his solutions and such a boycott against suspected bad miners may be incorporated into the cryptocurrency protocol (for a simplistic example of such a protocol, the protocol could be to always accept a block from an established miner over a block from a new miner (or someone pretending to be a new miner) if the new miner does not post at least the average number of solutions per block and to outright reject all blocks from established miners if they are suspected of intentionally withholding more than 10 percent of solutions with a 3 sigma confidence).


It will probably be very difficult to make useful POW problems if one just used a single algorithm per cryptocurrency that does not employ the SLT. However, if one uses many kinds of POW problems in a cryptocurrency and if one employs the SLT in many of these problems, then constructing a new useful POW problem is no longer as difficult. With multiple POW problems and with the SLT a useful POW problem only needs to be useful, difficult to solve, easy to verify, automatically generated, and the solutions need to be tied to the solver and the blockchain. Since the problem of constructing useful POW problems is a tractible applied mathematics research problem with great economic benefit, it will be a good idea for mathematicians and other experts to work on developing such problems.

A warning against proof-of-stake cryptocurrencies and against altcoins

I am making this post since recently several altcoins which are not mined by proof-of-work problems have gained a very high market cap and because I see a major downside to these non-minable coins. Furthermore, the newer cryptocurrencies are non-minable, and people should be very wary of non-minable coins.

To make things short, there are two ways in which transactions are verified in a cryptocurrency without the use of a central authority, namely proof-of-work (POW) and proof-of-stake (POS). With POW, people gain the right to validate cryptocurrency transactions by solving a computationally difficult problem (the process of solving this problem is known as “mining”), and the people are rewarded for solving these POW problems and validating the transactions with newly minted coins and with transaction fees. The difficulty of this problem is automatically adjusted so that the average time it takes to solve the problem remains constant. POS does away with the need to solve such a computationally difficult problem. With POS, the cryptocurrency rewards an entity the right to validate transactions according to how much of the cryptocurrency the entity possesses. POS should be thought of as a cheap alternative to POW, and by cheap I mean that POS is of low quality rather than inexpensive as a result of a community unwilling to put the effort into making a good POW problem and solving these problems.

In this post, I am not going to discuss whether POS is suitable as a mechanism for validating transactions in the long run since I am currently far from the best person to write about such an issue (this post will therefore not be very technical). However, I am going to make the case that one needs POW in order to fairly initially distribute a cryptocurrency and that POS is insufficient for initially distributing the cryptocurrency. Most of the ideas in this post are not original ideas and they have been broadcasted elsewhere by other people.

We observe that recently POS coins have been gaining a high market cap while the POW coins have not received such great gains. Furthermore, the newer cryptocurrencies with a high market cap are all POS coins as opposed to POW coins. I also want to make it clear that my criticism of POS is only limited to the initial distribution of the coin.

So there is about 800 billion dollars in cryptocurrencies floating around as of 1/06/2017. With such a high market cap, we must now ask the question as to whether the people who own these cryptocurrencies have truly earned the coins that they have. A related question one should also ask is whether the coins have been distributed evenly and fairly. If these cryptocurrencies have not been distributed fairly, we must then find and employ the best strategy for fairly distributing these new coins.

One possible solution to the initial distribution problem without resorting to POW is to give every single person in a certain region of the world. For example, in the cryptocurrency Auroracoin, an equal number of coins were given to each citizen of Iceland. This solution however has its problems. Cryptocurrencies distributed like Auroracoin have a major competitive disadvantage since such cryptocurrencies are limited to certain regions of the world, and as a result any coin similar to Auroracoin will probably have a low market cap. By limiting a cryptocurrency to a certain part of the world, such a cryptocurrency is not that much different from fiat currencies since cryptocurrencies should not be limited to certain groups of people. Fairly distributing a cryptocurrency to every citizen of a nation also has some logistic disadvantages since during the initial distribution, not every citizen would accept such a cryptocurrency and there is no guarantee that the citizens of that nation would accept such a cryptocurrency in the future. It is difficult to distribute a currency if the people do not want that new currency.

Auroracoin’s solution to the initial distribution problem is the best possible solution to this problem without resorting to POW. Other solutions to the initial distribution problem in a POS system are very unfair and/or logistical nightmares. For example, if the coin has been initially distributed through an ICO (initial coin offering), then one’s wealth is determined solely by how much one gives to a central non-government organization. While this method of initial distribution works well for distributing stocks, it is not a fair way to distribute new cryptocurrencies because it is necessary for cryptocurrencies to be distributed as evenly as possible. There is no way to evenly and fairly distribute a new cryptocurrency solely through a high risk ICO since ICOs distribute coins based on how much people are willing to risk their money at cryptocurrency projects which have not been launched yet and which have not stood the test of time. ICOs are unnecessary to develop a new cryptocurrency since new cryptocurrencies could be launched simply by cutting and pasting, and the development of the cryptocurrency could be funded by a sort of treasury system similar to that of the cryptocurrency Dash. Let us also observe that many ICOs are complete scams. If a cryptocurrency must use an ICO, then only a small portion of the total number of coins should be distributed through that ICO and the rest of the coins should be distributed by using POW (Ethereum has combined ICO with POW for its initial distribution and that is fine).

Would you like your national currency to be initially distributed based on how much money one gives to someone who may or may not be a scam artist? Or would you instead like your national currency to be distributed to people according to how much they work for it?

Many people say that POS is cheaper than POW. But the damage to an economy caused by POS because all of the wealth has been distributed to the wrong people will be much more expensive than POW could ever be.

Even though I consider POW to be a fair way to initial distribute a new cryptocurrency, one still has to be careful with POW coins since POW still could have major initial distribution problems if it is not done correctly.

The initial distribution mining period needs to be long enough for the cryptocurrency to be fairly distributed among the users. If most of the coins are given to the early adopters and the cryptocurrency gains a high market cap only after most of the coins have been distributed, then a few people will have an excessive amount of wealth that they have not worked for and which they have not earned. In my opinion, the initial distribution period should last at least a decade for a fair distribution, and Bitcoin’s halving period of four years is too short for newer cryptocurrencies (of course even a one year initial distribution period using POW is much better than any ICO since at least with a POW people are investing in a cryptocurrency that has been launched).

With what I had said, you may be tempted to cry foul at the initial distribution of Bitcoin, but I would not consider the initial distribution of Bitcoin to be unfair in any way. The early investors into Bitcoin became rich, but they also provided a great deal of value to the cryptocurrency community. The early investors into Bitcoin were the people who made the notion of a cryptocurrency what it is today, and the early investors of Bitcoin were necessary in order for the market caps of cryptocurrencies to grow to where they are today. However, one cannot make the argument that if someone becomes rich from being an early adopter of an altcoin, then that person has truly earned his money. An early adopter of an altcoin has not helped make cryptocurrencies become mainstream so it is unfair for such an entity to have an enormous amount of wealth. The early adopters of Bitcoin also deserve their wealth because they decided to get Bitcoin early because they truly understood either how Bitcoin works or how Bitcoin is important; the same cannot be said of the early adopters of altcoins. Since Bitcoin early adopters truly deserve their wealth because they believed in the system and because they helped bring cryptocurrencies into the mainstream, one could argue that Bitcoin is the most fairly distributed cryptocurrency.

The cryptocurrency must also choose a useful POW problem that has real-world applications outside of the cryptocurrency community. For example, the POW problem for Bitcoin is to find a SHA256 hash $k$ so that $k < C$ where $C$ is a number that changes every 2016 blocks; the hashes $k$ with $k < C$ have no purpose outside of the cryptocurrency itself, nor is the process of mining bitcoins of much value. Bitcoin mining therefore becomes a nearly useless job whose only purpose outside the cryptocurrency is to keep people employed doing a nearly useless job.
A useful POW problem cannot be seen as wasteful in any way since the work needed to solve that problem will be used to advance science, technology, or mathematics.

If a person gets rich from solving useless POW problems from cryptocurrencies, then that person has not done work to improve anyone’s lives. It is not fair for someone to get rich off a cryptocurrency by performing a nearly useless job. It is definitely not fair for all coins in a cryptocurrency to arise from performing a nearly useless job.

We need a useful POW problem also because people should get paid for performing useful jobs rather than useless jobs. Unfortunately, the cryptocurrencies launched so far have not successfully employed useful POW problems, so mathematicians still have a lot of work to do.

Now, it is not solely up to the cryptocurrency authorities to solve the initial distribution problem, but the people can also help solve the initial distribution problem by investing in a diversified set of cryptocurrencies. One will incur a much lower risk by investing in a diverse set of cryptocurrencies at least until stable cryptocurrencies emerge. While useful POWs whose mining period elapses over several years will help fairly distribute cryptocurrencies, the people need to also do their part by investing in a diverse set of cryptocurrencies and creating systems that will allow others to more easily invest in a diverse set of cryptocurrencies.

I should mention that POW and POS are not the only ways of initially distributing new cryptocurrencies since one could use proof-of-burn in order to transfer coins from an existing cryptocurrency to a new cryptocurrency. However, proof-of-burn is a rarely used consensus and initial distribution mechanism, so proof-of-burn currently should not be considered to be a substitute for proof-of-work or proof-of-stake.

Let me know your thoughts about the cryptocurrency initial distribution problem.

Extraneous remarks:

If you want to know if a cryptocurrency is a proof-of-work coin or a proof-of-stake coin, go to https://coinmarketcap.com/ and look for the cryptocurrency; if you see an asterisk next to the cryptocurrency, that means that the coin is not minable and hence it is not a proof-of-work coin.

One may claim that Auroracoin’s solution to the initial distribution problem is an act of socialism, but Auroracoin is not quite as socialistic as one might think at first glance. First of all, the people of Iceland have the choice of accepting Auroracoin as a legitimate currency or not, and since the people may choose to accept Auroracoin, Auroracoin should be considered as a part of a capitalistic society even though the initial distribution of Auroracoin is socialistic. Second of all, Auroracoin is only a socialistic in its initial distribution, so the socialistic distribution of Auroracoin will only dominate the cryptocurrency in the short-term. Finally, the socialistic initial distribution of Auroracoin is not intended to spread socialism but instead to solve the initial distribution problem.

While I have criticized POS coins in this post, we must give the POS coins some credit for testing POS in practice so that people better understand its advantages and disadvantages.

Security report for R5, the POW problem for Nebula.

Hello everyone,

Attached is the security report for R5, the POW problem for Nebula. I had to give an account on the security of Nebula since Nebula employs new kinds of cryptosystems which have not been implemented in practice so far. Keep in mind that it is ill-advised to employ a new symmetric cryptosystem in practice as soon as it is developed. It typically takes a couple of years for people to thoroughly investigate a new symmetric cryptosystem before it is employed in practice, and for public key cryptosystems it takes much longer. However, by the nature of R5, a security report that should be sufficient to ensure the security of R5 since it is much more difficult for something to go wrong with R5 that it is for something to go wrong with a symmetric cryptosystem such as a hash function.

I will at one point release an updated version of the security report for R5 since there is information about R5 which I do not want to reveal publicly at the moment (I apologize for my violation of Kerckhoffs’s principle.Don’t worry. All information about R5 will be openly available soon enough though. And my violation for Kerckoff’s principle are not for cryptographic security reasons but instead for logistical reasons).

A lesson to be learned from the recent cryptocurrency dip

Today in the news, you can find countless articles which tell us that China has just banned ICO’s (an ICO, an initial coin offering, is the way that many people fund new cryptocurrency endeavors. In an ICO, investors buy new cryptocurrency tokens since they believe that the upcoming cryptocurrency will eventually become valuable). As a result on this ban on ICOs, the total market cap for all cryptocurrencies has fallen from an all-time high of 180 billion USD (on September 2, 2:00 UTC) to 138 billion USD at the time of writing. The price of a bitcoin was almost 5000 USD but now after the dip, a bitcoin now costs 4100 USD.

One government action has the power to sway the value of cryptocurrencies so that they lose 20-25 percent of their value overnight. It is therefore necessary for those who value cryptocurrencies to make a great effort to improve the reputation of cryptocurrencies so that the world’s governments accept these cryptocurrencies. Not only are governments able to harm cryptocurrencies by passing laws against them, but these governments also have the power to launch attacks against cryptocurrencies and thus break the security of these cryptocurrencies and likely destroy these cryptocurrencies.

Cryptocurrencies currently have a mixed reputation. Since it is possible for cryptocurrencies to disrupt global economies, replace any national currency, and cause other changes that people will not want to accept, governments may want to place restrictions and regulations upon cryptocurrencies to keep them under control. Today, cryptocurrencies are not backed by gold or any other precious metals, and the process of mining new coins does not provide any product or service of value outside the cryptocurrency except for pollution. Since cryptocurrencies are not produced by providing useful products or useful services and cannot be traded for precious metals, cryptocurrencies do not have nearly as many advantages over fiat currencies as they could have, but they could improve their reputation simply by making mining useful. It is therefore necessary for cryptocurrencies to employ useful proof-of-work problems which provide benefits outside the cryptocurrency.

My solution in my upcoming cryptocurrency Nebula is to use a proof-of-work problem R5 so that in order to efficiently solve R5, one will need to construct a reversible computer and advance computational technology.
The proof-of-work R5 is nearly as efficient as a cryptographic hash function, so R5 does not suffer from negative characteristics which are present in other so-called useful proof-of-work problems. R5 is also much more useful than all other proof-of-work problems proposed so far since one cannot question the future value of reversible computation. Since Nebula will advance technology, the people and hence the governments will view cryptocurrencies more favorably (at least Nebula anyways). As a consequence, governments will be less willing to place restrictions on cryptocurrencies if some of those cryptocurrencies advance science in positive ways. The only way for cryptocurrencies to last among a skeptical population is if people only use a cryptocurrency which employs a good useful proof-of-work problem. If we keep on using the same cryptocurrencies with the same proof-of-work problems, then people will rightfully see these cryptocurrencies as useless and wasteful. I have hope that eventually, people will only use the cryptocurrencies with useful proof-of-work problems since people will rightfully perceive these new cryptocurrencies as being much more valuable than our current cryptocurrencies.

Unfortunately, it is too late for Bitcoin to start using a useful proof-of-work problem since most bitcoins have already been mined and switching a proof-of-work will require a destructive hard-fork, so one will need to start using new altcoins instead. Fortunately, in recent months, altcoins have come to dominate over half of the total market cap of all cryptocurrencies, and new altcoins are constantly being created. In a few years, the dominant cryptocurrencies will likely be ones which have not been launched yet but which will employ new innovations. Nebula is one of these cryptocurrencies with a new innovation that challenges the status quo in the cryptocurrency community.

A message to the skeptics

There have been many people in the pure mathematics community who have denied the possibility that reversible computing may be more energy efficient than conventional (by conventional I mean irreversible) computing. I hope you know that if conventional computing can potentially be infinitely efficient, then one could construct a computer that could decrease entropy within a closed system. You are denying the second law of thermodynamics. You are denying everything that people know about statistical mechanics. Stop denying science.

There are also other skeptics who have denied the value of cryptocurrencies altogether. To those of you I will say that you need to read and understand the original paper Bitcoin by Satoshi Nakamoto.

Generalizations of Laver tables is posted (140 pages)

The full version of the paper Generalizations of Laver tables is now posted.

In the paper, I have focused on building the general theory of Laver tables rather than solving a major problem with regards to the Laver tables. In fact, one should consider this paper as an account of “what everyone needs to know about Laver tables” rather than “solutions to problems about Laver tables.” This paper lays the foundations for future work on Laver tables. Since there is only one paper on the generalizations of Laver tables as of August 2017, an aspiring researcher currently does not have to go through many journal articles in order to further investigate these structures. I hope and expect that this paper on Laver tables will incite a broad interest on these structures among set theorists and non-set theorists, and that further investigation on these structures will be made possible by this paper.

Researching Laver tables

If you would like to investigate Laver tables, then please investigate the permutative LD-systems, multigenic Laver tables, and endomorphic Laver tables instead of simply the classical Laver tables. Very little work has been done on the classical Laver tables since the mid 1990’s. The classical Laver tables by themselves are a dead-end research direction unless one investigates more general classes of structures.

The most important avenue of further investigation will be to evaluate the security and improve the efficiency of the functional endomorphic Laver table based cryptosystems. Here are some ways in which one can directly improve functional endomorphic Laver table based cryptography.

  1. Try to break these cryptosystems.
  2. Compute $A_{96}$.
  3. Find compatible linear orderings on Laver-like LD-systems.
  4. Find new multigenic Laver tables and new Laver-like LD-systems.

It usually takes about 15 years from when a new public key cryptosystem is proposed for the public to gain confidence in such a cryptosystem. Furthermore, people will only gain confidence in a new public key cryptosystem if the mathematics behind such a cryptosystem is well-developed. Therefore, any meaningful investigation into large cardinals above hugeness and the Laver tables will indirectly improve the security of these new cryptosystems.

While people have hoped for a strong connection between knots and braids and Laver tables, the Laver tables so far have not produced any meaningful results about knots or braids that cannot be proven without Laver tables. The action of the positive braid monoid is essential for even the definition of the permutative LD-systems, so one may be able to apply the permutative LD-systems to investigating knots and braids or even apply knots and braids to investigating permutative LD-systems. However, I would regard any investigation into the application of Laver tables to knots and braids to be a risky endeavor since so far people have not been able to establish a deep connection between these two types of structures.

If you are a set theorist investigating the Laver tables and you are not sure if you will stay in academia for your entire career, then I recommend for you to work on something that requires extensive computer programming. This will greatly improve your job prospects if you ever leave academia for any reason. Besides, today nearly all respectable mathematicians need to also be reasonably proficient computer programmers. You do not want to be in academia trying to help students get real-world jobs when you do not yourself have the invaluable real-world skill of computer programming.

My future work

I will not be able to work on Laver-like algebras too much in the near future since I am currently preoccupied with my work on Nebula, the upcoming cryptocurrency which will incentivize the construction of the reversible computer. I am already behind on my work on Nebula since this paper has taken most of my time already, so I really need to work more on Nebula now. Since developing and maintaining a cryptocurrency is a full-time job, I will probably not be able to continue my investigations on Laver tables.

Slides from talk at BLAST 2017 and a rant on giving talks about the classical Laver tables

Here are my slides for my talk at the BLAST 2017 conference at Vanderbilt University in Nashville, Tennessee.

As a side note, I just noticed this other conference. All of the talks at that other conference on Laver tables are woefully outdated (i.e. 1995 or so). They only talk about the classical Laver tables. As an analogy, only talking about the classical Laver tables is like only talking about the cyclic groups of order $3^{n}$ and then claiming that they some how represent group theory as a whole. If you are going to give a talk about Laver tables or write a paper on the Laver tables, then please read the abridged version of my paper before you do so.

The classical Laver tables by themselves are a rather dead-end research area that have not been active within the last 20 years (one can probably try to analyze the fractal structure obtained from the classical Laver tables but such an analysis will probably be difficult and incremental). In order to advance further research in this area, one needs to consider the generalizations including Laver-like algebras, multigenic Laver tables, and functional endomorphic Laver tables. The classical Laver tables do not explain what the subalgebras of $\mathcal{E}_{\lambda}/\equiv^{\gamma}$ generated by multiple elements look like (one cannot even show that $\mathcal{E}_{\lambda}/\equiv^{\gamma}$ is locally finite without using the multigenic Laver tables). The classical Laver tables do not have any cryptographic applications. The classical Laver tables are just one sequence of structures, and it is hard to advance mathematics simply by looking at only one kind of structure with limited complexity. There is no reason at all to look at the classical Laver tables without looking at more general structures.

It is better to call the structures $A_{n}=(\{1,…,2^{n}\},*_{n})$ “classical Laver tables ” instead of simply “Laver tables.” There are other structures to consider.

How to give a classical Laver table talk.

The first step to giving a presentation on the classical Laver tables is to make sure you give your talk to the proper audience. The best audience to give a classical Laver table talk to is an audience of middle schoolers or maybe high schoolers (it is not that hard to fill out the multiplication table of a classical Laver table). Once you have your audience of middle schoolers present, you should get them to fill out an $8\times 8$ classical Laver table and then a $16\times 16$ classical Laver table. After they fill out the $16\times 16$ classical Laver table. And yes, middle schoolers are completely capable of filling out classical Laver tables. It is not that hard. After they are done filling out the tables, you can show them pictures that arise from the classical Laver tables on the projector and hint about how these objects come from infinity.

Nebula-The cryptocurrency that will produce the reversible computer

So I have just posted the paper outlining the proof-of-work problem for my upcoming cryptocurrency Nebula. Here is the link for the paper. I hope to launch Nebula as soon as possible.

The idea behind Nebula is to use a reversible computing optimized proof-of-work (RCO-POW) problem instead of an ordinary proof-of-work problem (if you do not know what I am talking about, I suggest for you to read the original paper on Bitcoin). An RCO-POW problem is like an ordinary proof-of-work problem except for the fact that the RCO-POW problem can be solved by a reversible computing device just as easily as it can be solved using a conventional computing device.

It is very rare for a problem to be solvable by a reversible computing device using just as many steps as it is solvable using a conventional computing device. In general, it takes more steps to solve a problem using a reversible computation than it takes to solve the same problem using conventional computation. Therefore, since reversible computation has this computational overhead and since reversible computers currently do not exist, chip manufacturers do not have much of an incentive to manufacture reversible computing devices. However, since RCO-POW problems are just as easily solved using nearly reversible computational devices, chip manufacturers will be motivated to produce energy efficient reversible devices to solve these RCO-POW problems. After chip manufacturers know how to produce reversible devices that can solve these RCO-POW problems better than conventional devices, these manufacturers can use their knowledge and technology to start producing reversible devices for other purposes. Since reversible computation is theoretically much more efficient than conventional computation, these reversible computing devices will eventually perform much better than conventional computing devices. Hopefully these reversible computational devices will also eventually spur the development of quantum computers (one can think of reversible computation as simply quantum computation where the bits are not in a superposition of each other).

Nebula shall use the RCO-POW which I shall call R5. R5 is a POW that consists of five different algorithms which range from computing reversible cellular automata to computing random reversible circuits. I use the multi-algorithm approach in order to ensure decentralization and to incentivize the production of several different kinds of reversible devices instead of just one kind of device.

The only thing that will be different between Nebula and one of the existing cryptocurrencies is the POW problem since I did not want to add features which have not been tested out on existing cryptocurrencies already.

Cryptographic applications of very large cardinals-BLAST 2017

In August, I will be giving a contributed talk at the 2017 BLAST conference.

I am going to give a talk about the applications of functional endomorphic Laver tables to public key cryptography. In essence, the non-abelian group based cryptosystems extend to self-distributive algebra based cryptosystems, and the functional endomorphic Laver tables are, as far as I can tell, a good platform for these cryptosystems.

ABSTRACT: We shall use the rank-into-rank cardinals to construct algebras which may be used as platforms for public key cryptosystems.

The well-known cryptosystems in group based cryptography generalize to self-distributive algebra based cryptosystems. In 2013, Kalka and Teicher have generalized the group based Anshel-Anshel Goldfeld key exchange to a self-distributive algebra based key exchange. Furthermore, the semigroup based Ko-Lee key exchange extends in a trivial manner to a self-distributive algebra based key exchange. In 2006, Patrick Dehornoy has established that self-distributive algebras may be used to establish authentication systems.

The classical Laver tables are the unique algebras $A_{n}=(\{1,…,2^{n}-1,2^{n}\},*_{n})$ such that $x*_{n}(y*_{n}z)=(x*_{n}y)*_{n}(x*_{n}z)$ and $x*_{n}1=x+1\mod 2^{n}$ for all $x,y,z\in A_{n}$. The classical Laver tables are up-to-isomorphism the monogenerated subalgebras of the algebras of rank-into-rank embeddings modulo some ordinal. The classical Laver tables (and similar structures) may be used to recursively construct functional endomorphic Laver tables which are self-distributive algebras of an arbitrary arity. These functional endomorphic Laver tables appear to be secure platforms for self-distributive algebra based cryptosystems.

The functional endomorphic Laver table based cryptosystems should be resistant to attacks from adversaries who have access to quantum computers. The functional endomorphic Laver table based cryptosystems will be the first real-world application of large cardinals!

How cryptocurrencies could incentivize the development of efficient reversible computers and the cryptocurrency market cap reaches 100 billion dollars.

I have some amazing news. The total market cap for all cryptocurrencies has for the first time has reached 100 billion dollars. On April 24,2017 the total market map for all cryptocurrencies has hit 30 billion for the first time and it has been growing ever since. At the same time, while Bitcoin has in the past been the only major cryptocurrency, Bitcoin no longer is the only major cryptocurrency since Bitcoin currently amounts for about 45 percent of the total market cap for all cryptocurrencies (on March 1,2017 Bitcoin amounted to about 85 percent of the total market cap for all cryptocurrencies).

I believe that unless most of the world’s governments wage a cyber war against cryptocurrencies, in the somewhat near future cryptocurrencies will for the most part replace fiat currencies or at least compete with government fiat currencies. Governments today have an incentive to produce more fiat currencies since governments are able to fund their programs by printing more of their own money (producing more money is a bit more subtle than simply taxing people). However, there is no motivation for anyone to exponentially inflate any particular cryptocurrency (I would never own any cryptocurrency which will continue to exponentially inflates its value). For example, there will never be any more than 21 million bitcoins. Since cryptocurrencies will not lose their value through an exponential inflation, people will gain more confidence in cryptocurrencies than they would with their fiat currencies. Furthermore, cryptocurrencies also have the advantage that they are not connected to any one government and are supposed to be decentralized.

Hopefully the world will transition from fiat currencies to digital currencies smoothly though. Cryptocurrencies are still very new and quite experimental, but cryptocurrencies have the potential to disrupt the global economy. There are currently many problems and questions about cryptocurrencies which people need to solve. One of the main issues with cryptocurrencies is that the proof-of-work problem for cryptocurrencies costs a lot of energy and resources and these proof-of-work problems produce nothing of value other than securing the cryptocurrency. If instead the proof-of-work problems for cryptocurrencies produce something of value other than security, the public image of cryptocurrencies will be improved, and as a consequence, governments and other organizations will be less willing to attack or hinder cryptocurrencies. In this post, I will give another attempt of producing useful proof-of-work problems for cryptocurrencies.

In my previous post on cryptocurrencies, I suggested that one could achieve both security and also obtain useful proofs-of-work by employing many different kinds of problems into the proof-of-work scheme instead of a single kind of problem into such a scheme. However, while I think such a proposal is possible, it will be difficult for the cryptocurrency community to accept and implement such a proposal for a couple of reasons. First of all, in order for my proposal to work, one needs to find many different kinds of proof-of-work problems which are suitable for securing cryptocurrency blockchains (this is not an easy task). Second of all, even if all the proof-of-work problems are selected, the implementation of the proposal will be quite complex since one will have to produce protocols to remove broken problems along with a system that can work together with all the different kinds of problems. Let me therefore propose a type of proof-of-work problem which satisfies all of the nice properties that hash-based proof-of-work problems satisfy but which will spur the development of reversible computers.

I am seriously considering creating a cryptocurrency whose proof-of-work problem will spur the development of reversible computers, and this post should be considered a preliminary outline of how such a proof-of-work currency would work. The next time I post about reversible computers spurred by cryptocurrencies, I will likely announce my new cryptocurrency, a whitepaper, and other pertinent information.

What are reversible computers?

Reversible computers are theoretical super-efficient classical computers which use very little energy because they can in some sense recycle the energy used in the computation. As analogies, an electric motor can recover the kinetic energy used to power a vehicle using regenerative braking by running the electric motor in reverse, and when people recycle aluminum cans the aluminum is used to make new cans. In a similar manner, a reversible computer can theoretically in a sense regenerate the energy used in a computation by running the computation in reverse.

A reversible computer is a computer whose logic gates are all bijective and hence have the same number of input bits as output bits. For example, the AND and OR gates are irreversible gates since the Boolean operations AND and OR are not bijective. The NOT gate is a reversible gate since the NOT function is bijective. The Toffoli gate and Fredkin gates are the functions $T$ and $F$ respectively defined by
$$T:\{0,1\}^{3}\rightarrow\{0,1\}^{3},T(x,y,z)=(x,y,(x\wedge y)\oplus z)$$
The Toffoli gate and the Fredkin gate are both universal reversible gates in the sense that Toffoli gates alone can simulate any circuit and Fredkin gates can also simulate any circuit.

While reversible computation is a special case of irreversible computation, all forms of classical computation can be somewhat efficiently simulated by reversible circuits. Furthermore, when reversible computers are finally constructed, one should be able to employ a mix of reversibility and irreversibility to optimize efficiency in a partially reversible circuit.

Reversible computation is an improvement over classical computation since reversible computation is potentially many times more efficient than classical computation. Landauer’s principle states that erasing a bit always costs $k\cdot T\cdot\ln(2)$ energy where $T$ is the temperature and $k$ is the Boltzmann constant. Here the Boltzmann constant is $1.38064852\cdot 10^{−23}$ joules per Kelvin. At the room temperature of 300 K, Landauer’s principle requires $2.8\cdot 10^{−21}$ joules for every bit erased. The efficiency of irreversible computation is limited by Landauer’s principle since irreversible computation requires one to erase many bits. On the other hand, there is no limit to the efficiency of reversible computation since reversible computation does not require anyone to erase any bit of information. Since reversible computers are potentially more efficient than classical computers, reversible computers do not generate as much heat and hence reversible computers can potentially run at much faster speeds than ordinary classical computers.

While the hardware for reversible computation has not been developed, we currently have software that could run on these reversible computers. For example, the programming language Janus is a reversible programming language. One can therefore produce, test, and run much reversible software even though the super-efficient reversible computers currently do not exist.

The proof-of-work problem

Let me now give a description of the proof-of-work problem. Suppose that

  1. $a_{i,j},b_{i,j},c_{i,j}\in\{0,1\}$ are randomly generated whenever $1\leq i\leq 128,1\leq j\leq 85$,
  2. $T_{i,j}:\{0,1\}^{3}\rightarrow\{0,1\}$ is the mapping defined by
    $$T_{i,j}(x,y,z)=((a_{i,j}\oplus x)\wedge(b_{i,j}\oplus y))\oplus c_{i,j}\oplus z,$$
  3. $a_{i}\in\{1,\ldots,256\}$ for $i\in\{1,\ldots,128\},$
  4. $((a_{i,1,1},a_{i,1,2},a_{i,1,3}),…,(a_{i,85,1},a_{i,85,2},a_{i,85,3}))$ is a randomly generated partition of $\{1,\ldots,256\}\setminus\{a_{i}\}$ for $1\leq i\leq 128$,
  5. For $i\in\{1,…,128\},j\in\{1,…,85\}$, $f_{i,j}:\{0,1\}^{256}\rightarrow\{0,1\}^{256}$ is the mapping where
    $f_{i,j}((x_{n})_{n=1}^{256})=(y_{n})_{n=1}^{256}$ if and only if $x_{n}=y_{n}$ whenever $n\neq a_{i,j,3}$ and
  6. $$f_{i}=f_{i,1}\circ…\circ f_{i,85},$$
  7. $\sigma:\{0,1\}^{256}\rightarrow\{0,1\}^{256}$ is the mapping where $\sigma((x_{n})_{n=1}^{256})=(y_{n})_{n=1}^{256}$ precisely when $x_{n}=y_{n}$ for $n>128$ and $y_{n}=x_{n}+x_{n+128}$ whenever $n\leq 128$,
  8. $\mu:\{0,1\}^{256}\rightarrow\{0,1\}^{256}$ is the mapping where $\mu((x_{n})_{n=1}^{256})=(y_{n})_{n=1}^{256}$ precisely when $x_{n}=y_{n}$ for $n>128$ and $y_{n}=x_{n}+x_{257-n}$ whenever $n\leq 128$,
  9. $\tau:\{0,1\}^{256}\rightarrow\{0,1\}^{256}$ is the mapping where $\tau((x_{n})_{n=1}^{256})=(y_{n})_{n=1}^{256}$ precisely when
    $x_{n}=y_{n}$ for $n>64$ and $y_{n}=x_{n}+x_{n+64}$ whenever $n\leq 64$,
  10. $$f=\tau\circ\sigma\circ f_{128}\circ…\circ f_{1}\circ \sigma\circ\mu.$$

The function $f$ can be computed by a reversible circuit which we shall denote by $C$ with 132 different layers. The 128 layers in the circuit $C$ which are used to compute the functions $f_{1},…,f_{128}$ shall be called rounds. The circuit $C$ consists of 10880 Toffoli-like gates along with 576 CNOT gates (The circuit $C$ has a total of 11456 gates).

Since the randomizing function $f$ is randomly generated, one will be able to replace the function $f$ with a new randomly generated function $f$ periodically if one wants to.

Proof-of-work problem:

Let $\alpha$ be an adjustable 256 bit number. Let $k$ be a 128 bit hash of the current block in the blockchain. Then the proof-of-work problem is to find a 128 bit nonce $\mathbf{x}$ such that $f(k\#\mathbf{x})\leq\alpha$. The number $\alpha$ will be periodically adjusted so that the expected value of the amount of time it takes to obtain a new block in the blockchain remains constant.

Efficiency considerations

It is very easy to check whether a solution to our proof-of-work problem is correct or not but it is difficult to obtain a correct solution to our proof-of-work problem. Furthermore, the randomizing function $f$ in our proof-of-work problem can be just as easily computed on a reversible computer as it can on an irreversible computer. If reversible gates are only slightly more efficient than irreversible gates, then using a reversible computer to solve a proof-of-work problem will only be profitable if the randomizing function is specifically designed to be computed by a reversible circuit with no ancilla, no garbage bits, and which cannot be computed any faster by using an irreversible circuit instead. Standard cryptographic hash functions are not built to be run on reversible computers since they require one to either uncompute or to stockpile garbage bits that you will have to erase anyways.

Security considerations

The security of the randomizing permutation $f$ described above has not yet been thoroughly analyzed. I do not know of any established cryptographic randomizing permutation $f:\{0,1\}^{n}\rightarrow\{0,1\}^{n}$ that is written simply as a composition of reversible gates. I therefore had to construct a cryptographic randomizing permutation specifically as a proof-of-work problem for cryptocurrencies.

There are several reasons why I have chosen to use mostly randomness to construct the function $f$ instead of intentionally designing each gate of the function $f$. The circuit $C$ has depth 132 which is quite low. Perhaps I can slightly increase the security or the efficiency of the proof-of-work problem by designing each particular gate without any randomness but I do not believe that I can increase the security or efficiency by much. If the function $f$ is constructed once using random or pseudorandom information, then one can set up a system to automatically replace the function $f$ with a new function generated in the same manner (periodically changing the function). A randomly constructed function $f$ may even provide better security than a function $f$ constructed without randomness because it seems like since the function $f$ is constructed randomly, the function $f$ would be difficult to analyze. Another reason why I chose a randomly constructed circuit is that a randomly constructed circuit $f$ has a much simpler design than a function such as the SHA-256 hash.

In the worst case that the randomizing function is suspected to be insecure, one would have to increase the number of rounds in the randomizing function $f$ from 128 to a larger number such as 192 or 256 so that the randomizing function $f$ would become secure (it is better if 128 rounds is suspected to be insecure before the cryptocurrency is launched since if we need to increase the number of rounds from 128 to 192, then that would require a hard fork which will annoy users and miners and devalue such a currency).

The security requirement for the randomizing permutation $f$ as a proof-of-work problem is weaker than the security problem for a randomizing permutation when used to construct a cryptographic hash function or a symmetric encryption-decryption system. For a cryptographic hash function or a symmetric encryption or decryption to remain secure when used for cryptographic purposes, such a function must remain secure until the end of time, so an adversary may potentially use an unlimited amount of resources in order to attack an individual instance of a cryptographic hash function or symmetric encryption/decryption system. Furthermore, in the case of symmetric cryptography, an adversary will have access to a large quantity of data encrypted with a particular key. However, the current blockchain data $k$ changes every few seconds, so it will be quite difficult to break the proof-of-work problem.

Reversible computers are half-way in-between classical computers and quantum computers

I believe that the large scale quantum computer will by far be the greatest technological advancement that has ever or will ever happen. When people invent the large scale quantum computer, I will have to say “we have made it.” Perhaps the greatest motivation for constructing reversible computers is that reversible computers will facilitate the construction of large scale quantum computers. There are many similarities between quantum computers and reversible computers. The unitary operations that make up the quantum logic gates are reversible operations, and a large portion of all quantum algorithms consists of just reversible computation. Both quantum computation and reversible computation must be adiabatic (no heat goes in or out) and isentropic (entropy remains constant). However, quantum computers are more complex and more difficult to construct than reversible computers since the quantum gates are unitary operators and the quantum states inside quantum computers must remain in a globally coherent superposition. Since quantum computers are more difficult to construct than reversible computers, a more modest goal would be to construct reversible computers instead of quantum computers. Therefore, since reversible computers will be easier to construct than large scale quantum computers, we should now focus on constructing reversible computers rather than large scale quantum computers. The technology and knowledge used to construct super efficient reversible computers will then likely be used to construct quantum computers.

An anti-scientific attitude among the mathematics community

I have seen much unwarranted skepticism against Landauer’s principle and the possibility that reversible computation can be more efficient than classical irreversible computation could ever be. The only thing I have to say to you is that you are wrong, you are a science denier, you are a troll, and you are just like the old Catholic church who has persecuted Galileo.

2D heat maps and 3D topographical surfaces from endomorphic Laver tables

At this link you can create 2D heat maps and 3D topographical surfaces from the endomorphic Laver tables. Here is what the pictures which you could obtain from the endomorphic Laver tables look like.


Heat map

I was able to obtain pictures from the endomorphic Laver tables simply by giving the coordinate $(i,j)$ temperature and elevation
$t^{\sharp}(\mathfrak{l}_{1},\mathfrak{l}_{2},\mathfrak{l}_{3})(\mathbf{0}^{i}\mathbf{1}^{j})$. Obviously, the images that you can produce here only show a small portion of the functional endomorphic Laver tables and the functional endomorphic Laver table operations are too complicated to be completely represented visually.