Reversibility simply means that the outputs can always be recovered from the inputs simply by running the program in reverse. There are currently some reversible programming languages. For example, the programming language Janus is a high-level time reversible programming language, and you can play with Janus here http://topps.diku.dk/pirc/?id=janus. I also found the reversible programming language KAYAK. Right now, the only reversible programming languages are just-for-fun and purely-academic ones, but once reversible computers come into existence, I expect for many reversible programming languages or at least partially reversible programming languages to arise.
Topic: Proof-of-work problems designed to be solved by the reversible computers - page 2. (Read 1949 times)
June 27, 2017, 11:01:39 PM
June 27, 2017, 05:11:58 PM
AFAIK reversible computing is basically about minimizing changes(ever change costs!) from one operation to the next, state reversibility just happens to go hand in hand with the most efficient way to do it. I can't imagine how you'd translate such a low level problem to a very high level environment like computer software without losing the benefit incentive though.
June 27, 2017, 02:12:30 PM
I will need to construct several new POW algorithm since the current POW algorithms and all hash functions are unsuitable as RCO-POW problems. I already have an outline of how these RCO-POW algorithms will work.
A couple of the RCO-POW algorithms that I have in mind use chaotic non-linear 2D reversible cellular automata. Chaotic reversible cellular automata have already been studied by the cryptography community and they have been proposed to use as symmetric encryption-decryption schemes. Therefore, these RCO-POW problems are not completely new. In this paper,
https://thesai.org/Downloads/Volume5No5/Paper_31-A_fast_cryptosystem_using_reversible_cellular_automata.pdf,
the rule itself is used as the key for the encryption-decryption system (and thus nearly any rule is chaotic enough to be suitable for cryptographic purposes), and the efficiency of this cryptosystem is on par with the AES. Reversible cellular automata have the reversible computing advantage that the bits are not far from each other, and thus these RCO-POW problems will be suitable for mechanical nano-computers (mechanical nano-computers may be a good idea after all http://www.imm.org/Reports/rep046.pdf), and reversible quantum dot cellular automata. You can simulate the 2D reversible cellular automata that I am considering on this site https://dmishin.github.io/js-revca/index.html.
The other randomizing permutations f that I have in mind pretty much consist of circuits of randomly placed Toffoli, Fredkin, NOT, and CNOT gates.
It usually takes several years to evaluate the security of a cryptosystem and these cryptosystems sometimes get broken even after they have been approved (for example the hash functions MD2,MD4,MD5,SHA-1 are broken. Unfortunately, I would like to get this POW problem launched as soon as possible, so these RCO-POW problems will not be as rigorously tested before launch as AES or other cryptosystems. However, I have a couple solutions that will ensure security even though these problems have not gone through rigorous tests.
My first solution is to obtain security is what I would like to call "security-through-overkill." With security through overkill, I will simply be conservative about the security of the cryptosystem in the sense that I will include more rounds that are typically used for symmetric cryptosystems.
My second solution is to use the cryptocurrency itself to test the security of the POW problem and to calibrate its level of security automatically. My idea is to have two versions of the POW problem in the cryptocurrency. The first version of the POW problem will be the POW problem with its full security (in my case, I would need to use 3n rounds for full security) and the second version of the POW problem will be a version of the POW problem with weakened security (in this case, I will just use n rounds). The solution to 9/10 blocks will be the solution to the POW problem with full security while the solution to 1/10 blocks will be the solution to the POW problem with weakened security. The number of rounds in the weakened POW problem will increase if they are broken too quickly.
Keep in mind that the level of security required for a cryptocurrency POW problem is much less than the level of security required for hash functions and symmetric cryptosystems since one is usually given a couple minutes to break an instance of a cryptocurrency POW problem while an entity has an unlimited amount of time to break hash functions or versions of symmetric encryption. Also, the symmetric cryptosystems need to satisfy more stringent requirements since symmetric cryptography requires one to use a secret key while my RCO-POW systems require no such key. The main reason why symmetric cryptosystems need years of testing is that symmetric cryptosystems must be as secure and efficient and secure as possible and security and efficiency are opposing requirements. RCO-POW systems need to be efficient, but the efficiency of RCO-POW problems is not as crucial as it is for symmetric encryption-decryption systems or for cryptographic hash functions.
An RCO-POW problem will not be ASIC resistant. I want to construct problems which are as easy to solve as possible using future reversible computing devices, but ASIC resistant problems are meant to be difficult to solve using specialized devices. Since reversible computing devices can be thought of as ASICs, RCO-POW problems are by definition not ASIC-resistant. The closest thing that I can think of to an ASIC resistant RCO-POW problem is a problem that randomly reconfigures itself over time.
My proposed solution to the centralization problem is to use several different kinds of proof-of-work problems in order to maximize security. I am looking into using several kinds of RCO-POW problems where the reversible devices to solving each of these problems will need to have radically different designs. Another thing that one can do is to use RCO-POW problems together with ASIC resistant problems in order to maximize decentralization so that the neither the ASIC/RCO entities nor the GPU/CPU entities will control a majority of the mining power.
A couple of the RCO-POW algorithms that I have in mind use chaotic non-linear 2D reversible cellular automata. Chaotic reversible cellular automata have already been studied by the cryptography community and they have been proposed to use as symmetric encryption-decryption schemes. Therefore, these RCO-POW problems are not completely new. In this paper,
https://thesai.org/Downloads/Volume5No5/Paper_31-A_fast_cryptosystem_using_reversible_cellular_automata.pdf,
the rule itself is used as the key for the encryption-decryption system (and thus nearly any rule is chaotic enough to be suitable for cryptographic purposes), and the efficiency of this cryptosystem is on par with the AES. Reversible cellular automata have the reversible computing advantage that the bits are not far from each other, and thus these RCO-POW problems will be suitable for mechanical nano-computers (mechanical nano-computers may be a good idea after all http://www.imm.org/Reports/rep046.pdf), and reversible quantum dot cellular automata. You can simulate the 2D reversible cellular automata that I am considering on this site https://dmishin.github.io/js-revca/index.html.
The other randomizing permutations f that I have in mind pretty much consist of circuits of randomly placed Toffoli, Fredkin, NOT, and CNOT gates.
It usually takes several years to evaluate the security of a cryptosystem and these cryptosystems sometimes get broken even after they have been approved (for example the hash functions MD2,MD4,MD5,SHA-1 are broken. Unfortunately, I would like to get this POW problem launched as soon as possible, so these RCO-POW problems will not be as rigorously tested before launch as AES or other cryptosystems. However, I have a couple solutions that will ensure security even though these problems have not gone through rigorous tests.
My first solution is to obtain security is what I would like to call "security-through-overkill." With security through overkill, I will simply be conservative about the security of the cryptosystem in the sense that I will include more rounds that are typically used for symmetric cryptosystems.
My second solution is to use the cryptocurrency itself to test the security of the POW problem and to calibrate its level of security automatically. My idea is to have two versions of the POW problem in the cryptocurrency. The first version of the POW problem will be the POW problem with its full security (in my case, I would need to use 3n rounds for full security) and the second version of the POW problem will be a version of the POW problem with weakened security (in this case, I will just use n rounds). The solution to 9/10 blocks will be the solution to the POW problem with full security while the solution to 1/10 blocks will be the solution to the POW problem with weakened security. The number of rounds in the weakened POW problem will increase if they are broken too quickly.
Keep in mind that the level of security required for a cryptocurrency POW problem is much less than the level of security required for hash functions and symmetric cryptosystems since one is usually given a couple minutes to break an instance of a cryptocurrency POW problem while an entity has an unlimited amount of time to break hash functions or versions of symmetric encryption. Also, the symmetric cryptosystems need to satisfy more stringent requirements since symmetric cryptography requires one to use a secret key while my RCO-POW systems require no such key. The main reason why symmetric cryptosystems need years of testing is that symmetric cryptosystems must be as secure and efficient and secure as possible and security and efficiency are opposing requirements. RCO-POW systems need to be efficient, but the efficiency of RCO-POW problems is not as crucial as it is for symmetric encryption-decryption systems or for cryptographic hash functions.
An RCO-POW problem will not be ASIC resistant. I want to construct problems which are as easy to solve as possible using future reversible computing devices, but ASIC resistant problems are meant to be difficult to solve using specialized devices. Since reversible computing devices can be thought of as ASICs, RCO-POW problems are by definition not ASIC-resistant. The closest thing that I can think of to an ASIC resistant RCO-POW problem is a problem that randomly reconfigures itself over time.
My proposed solution to the centralization problem is to use several different kinds of proof-of-work problems in order to maximize security. I am looking into using several kinds of RCO-POW problems where the reversible devices to solving each of these problems will need to have radically different designs. Another thing that one can do is to use RCO-POW problems together with ASIC resistant problems in order to maximize decentralization so that the neither the ASIC/RCO entities nor the GPU/CPU entities will control a majority of the mining power.
June 27, 2017, 03:24:07 AM
I hadn't heard of a reversible computer before neither, but I looked into it and found it very interesting. Here is an article that explains it in simple terms for those who are interested:
https://www.cise.ufl.edu/research/revcomp/what.html
jvanname, does that mean that you have to design a PoW algorithm from scratch? If current algos can be modified to be RCO-POW friendly, then I would go for that. But I think that in order for a cryptocurrency to succeed you need to give incentives to miners (apart from the RCO-POW advantage). My opinion is that it needs to be ASIC-resistant and as decentralised as possible ie. CPU minable.
https://www.cise.ufl.edu/research/revcomp/what.html
jvanname, does that mean that you have to design a PoW algorithm from scratch? If current algos can be modified to be RCO-POW friendly, then I would go for that. But I think that in order for a cryptocurrency to succeed you need to give incentives to miners (apart from the RCO-POW advantage). My opinion is that it needs to be ASIC-resistant and as decentralised as possible ie. CPU minable.
June 25, 2017, 04:10:07 PM
I've never heard of revesible computing before but after reading a couple articles about it, it's a fascinating topic.
June 25, 2017, 03:44:54 PM
So I have recently been thinking about cryptocurrency proof-of-work (POW) problems and how one can use these POW problems to advance mathematics, science, or technology. The problem of developing a useful POW problem is not trivial, but there are much more difficult problems in cryptography than simply producing a useful POW (such as efficient fully homomorphic encryption and cryptographic code obfuscation which is in some sense impossible). It should therefore be so surprise when someone finds a useful POW problem for cryptocurrencies. I propose that one could use cryptocurrency POW problems in order to incentivize the development of reversible computers.
A reversible computer is a computer where almost every process can be run in reverse. In particular, reversible computers cannot delete too much information since deleting information is an irreversible process (however, with reversible computation, spent bits can be recovered through uncomputation). Reversible computers have the potential to be much more energy efficient than conventional computers because reversible computers are not limited by Landauer's principle which states that every bit erased costs ln(2)*k*T energy where T is the temperature and k is Boltzmann's constant. On the other hand, while anything calculable by a conventional computer is also calculable by a reversible computer, reversible computation typically requires more steps than conventional computation. Therefore, since reversible computers have a computational overhead, businesses currently do not have a strong incentive to produce reversible computational devices. On the other hand, since conventional computation has a limited amount of efficiency, businesses need to start developing reversible computing devices right now so that they have reversible computing infrastructure and inventions to work with for the time when conventional computers reach their limits and reversible computers are necessary in order to continue to improve performance. However, businesses currently do not have a financial incentive to produce reversible computing devices at the moment due to the computational overhead that is required with reversible computation.
An RCO-POW problem (reversible computing optimized POW) is a POW problem designed to be solved just as easily using a reversible computation device as it is to be solved using a conventional device. An RCO-POW problem for cryptocurrencies will incentivize the development of reversible computational devices since these RCO-POW problems do not introduce any computational overhead simply from being solved using reversible computers and thus reversible computational devices could be used to solve these TCO-POW problems immediately.
RCO-POW problem description: Suppose that f is a randomizing permutation from {0,1}^324 to {0,1}^324 which is just as easily computable using a reversible circuit without ancilla or garbage bits as it is with a conventional computer (f is similar to a cryptographic hash function). For example, f could be an iteration of a reversible cellular automaton or f could be the function computed by a circuit consisting of random Toffoli gates or Fredkin gates. Then the RCO-POW problem is to find some 256 bit hash k of the block header along with some 68 bit nonce x where f(k#x)
Comments
-In the future, all high-performance computers will be reversible because conventional computers will eventually be too inefficient to use and conventional computers will generate too much heat.
-Reversible computation will help pave the way for quantum computation. After all, reversible computation is in some sense simply quantum computation without entanglement.
-RCO-POW problems have little disadvantage over the POW problems which are currently in use since these RCO-POW problems are just as efficient
as hash-based POW problems. Furthermore, if the circuit computing f contains enough non-linear gates, then the RCO-POW problem will be as secure as a hash-based POW problem. I therefore have little concern that the function f will be insecure. The only possible disadvantage that I can see is that RCO-POW problems may foster mining centralization since there will likely be only a couple of businesses that will be able to produce reversible computing devices. Of course, one can mitigate this possible issue by including multiple RCO-POW problems in a cryptocurrency or including both RCO-POW problems and ASIC-resistant problems in a cryptocurrency (multiple RCO-POW problems will also incentivize the development for a diverse range of reversible computational technologies instead of any particular technology and give all reversible computational technologies a fair chance).
-RCO-POW problems may even increase the security of cryptocurrencies since governments will be much less likely to attack, ban, or restrict cryptocurrencies if their proof-of-work problems were used to advance science.
-Other cryptocurrencies have already attempted to include a useful POW problem. For example, the objective of the proof-of-work for Primecoin and Gapcoin is to find certain interesting chains of prime numbers. However, the utility and significance of these proof-of-work problems for these cryptocurrencies is questionable (I can only consider the POW for Primecoin to be significant once someone obtains a cryptosystem platform, theorem, or at least a conjecture as a result of these Primecoin computer calculations).
-An RCO-POW problem will probably be best suited for a new cryptocurrency rather than an existing cryptocurrency since the miners will not be very happy if their POW-problem is switched. An established cryptocurrency will only switch its cryptocurrency to an RCO-POW problem if the switch is gradual enough that the miners will not lose too much and if another cryptocurrency implements an RCO-POW first.
Questions-I want to know your opinions on RCO-POW problems for cryptocurrencies.
-Would you be more willing to use a particular cryptocurrency if its POW-problem incentivized the development of reversible computers or otherwise advanced technology or science in any way (here assume that useful POW-problem does not have any drawbacks including security concerns, mining centralization risks, inefficiencies or other issues)? Will you support a switch in an existing cryptocurrency from a conventional POW problem to an RCO-POW problem?
-Do you think that an RCO-POW problem will dissuade governments from placing restrictions or bans against cryptocurrencies?
-Will you consider a cryptocurrency as more valuable if its POW problem were used to incentivize the development of the reversible computer?
A reversible computer is a computer where almost every process can be run in reverse. In particular, reversible computers cannot delete too much information since deleting information is an irreversible process (however, with reversible computation, spent bits can be recovered through uncomputation). Reversible computers have the potential to be much more energy efficient than conventional computers because reversible computers are not limited by Landauer's principle which states that every bit erased costs ln(2)*k*T energy where T is the temperature and k is Boltzmann's constant. On the other hand, while anything calculable by a conventional computer is also calculable by a reversible computer, reversible computation typically requires more steps than conventional computation. Therefore, since reversible computers have a computational overhead, businesses currently do not have a strong incentive to produce reversible computational devices. On the other hand, since conventional computation has a limited amount of efficiency, businesses need to start developing reversible computing devices right now so that they have reversible computing infrastructure and inventions to work with for the time when conventional computers reach their limits and reversible computers are necessary in order to continue to improve performance. However, businesses currently do not have a financial incentive to produce reversible computing devices at the moment due to the computational overhead that is required with reversible computation.
An RCO-POW problem (reversible computing optimized POW) is a POW problem designed to be solved just as easily using a reversible computation device as it is to be solved using a conventional device. An RCO-POW problem for cryptocurrencies will incentivize the development of reversible computational devices since these RCO-POW problems do not introduce any computational overhead simply from being solved using reversible computers and thus reversible computational devices could be used to solve these TCO-POW problems immediately.
RCO-POW problem description: Suppose that f is a randomizing permutation from {0,1}^324 to {0,1}^324 which is just as easily computable using a reversible circuit without ancilla or garbage bits as it is with a conventional computer (f is similar to a cryptographic hash function). For example, f could be an iteration of a reversible cellular automaton or f could be the function computed by a circuit consisting of random Toffoli gates or Fredkin gates. Then the RCO-POW problem is to find some 256 bit hash k of the block header along with some 68 bit nonce x where f(k#x)
Comments
-In the future, all high-performance computers will be reversible because conventional computers will eventually be too inefficient to use and conventional computers will generate too much heat.
-Reversible computation will help pave the way for quantum computation. After all, reversible computation is in some sense simply quantum computation without entanglement.
-RCO-POW problems have little disadvantage over the POW problems which are currently in use since these RCO-POW problems are just as efficient
as hash-based POW problems. Furthermore, if the circuit computing f contains enough non-linear gates, then the RCO-POW problem will be as secure as a hash-based POW problem. I therefore have little concern that the function f will be insecure. The only possible disadvantage that I can see is that RCO-POW problems may foster mining centralization since there will likely be only a couple of businesses that will be able to produce reversible computing devices. Of course, one can mitigate this possible issue by including multiple RCO-POW problems in a cryptocurrency or including both RCO-POW problems and ASIC-resistant problems in a cryptocurrency (multiple RCO-POW problems will also incentivize the development for a diverse range of reversible computational technologies instead of any particular technology and give all reversible computational technologies a fair chance).
-RCO-POW problems may even increase the security of cryptocurrencies since governments will be much less likely to attack, ban, or restrict cryptocurrencies if their proof-of-work problems were used to advance science.
-Other cryptocurrencies have already attempted to include a useful POW problem. For example, the objective of the proof-of-work for Primecoin and Gapcoin is to find certain interesting chains of prime numbers. However, the utility and significance of these proof-of-work problems for these cryptocurrencies is questionable (I can only consider the POW for Primecoin to be significant once someone obtains a cryptosystem platform, theorem, or at least a conjecture as a result of these Primecoin computer calculations).
-An RCO-POW problem will probably be best suited for a new cryptocurrency rather than an existing cryptocurrency since the miners will not be very happy if their POW-problem is switched. An established cryptocurrency will only switch its cryptocurrency to an RCO-POW problem if the switch is gradual enough that the miners will not lose too much and if another cryptocurrency implements an RCO-POW first.
Questions-I want to know your opinions on RCO-POW problems for cryptocurrencies.
-Would you be more willing to use a particular cryptocurrency if its POW-problem incentivized the development of reversible computers or otherwise advanced technology or science in any way (here assume that useful POW-problem does not have any drawbacks including security concerns, mining centralization risks, inefficiencies or other issues)? Will you support a switch in an existing cryptocurrency from a conventional POW problem to an RCO-POW problem?
-Do you think that an RCO-POW problem will dissuade governments from placing restrictions or bans against cryptocurrencies?
-Will you consider a cryptocurrency as more valuable if its POW problem were used to incentivize the development of the reversible computer?
Jump to: