Topic: Nebula-The upcoming cryptocurrency that will incentivize reversible computation. - page 2. (Read 4511 times)

All that math

*drools*

I am glad that you are still updating this thread jvanname.

Am really excited about this project as it could be truly revolutional.
In your last post you said that the project needs more work than you anticipated. Do you have a timeline or roadmap or sth like that yet?

I would love to follow your work and journey with this project. Is there something else I can follow you except this thread and your blog/homepage http://boolesrings.org/jvanname?

Would be very happy to hear from you.
Keep up the good work!
You will definitely have my hashpower once it is needed.

Warning: I has discovered major weaknesses in the following POW problem. Those weaknesses seem non-fatal. I am now working to patch those weaknesses.

-Joseph Van Name Ph.D.


A solution to the Erasure with Faulty Computation Problem

So recall that the objective in the Problem R5 is to find a 256 bit hash k along with a 68 bit string x such that f(k||x)5 without having to erase any data in order to correct the error that has been made in Solution attempt number 5.

Problem B: Suppose that f_k,T_k are both functions mapping {0,1}^{n} to {0,1}^n that depend on a 256 bit hash k and which can be easily computed using a reversible device. Then the objective of Problem B is to find a string x so that the final bit in the string f_k(x) differs from the final bit in the string f_k(T_k(x)).

Reversible Algorithm for Problem B: Suppose that the state of the device is (y,0) at the beginning of attempt n at solving Problem B.

Step 1: Transition from state (y,0) to state (y,y[last]) where y[last] denotes the last bit in the string y. This step requires one to simply apply a CNOT gate to the state.

Step 2: Transition from state (y,y[last]) to state (f(T(f^(-1)(y))),y[last]).

Step 3: Transition from state (f(T(f^(-1)(y))),y[last]) to state (f(T(f^(-1)(y))),y[last] XOR f(T(f^(-1)(y)))[last]). This step also requires simply a CNOT gate.

Step 4: Suppose that the device is in state (z,i). If z==1, then halt the device since a solution to Problem B has been obtained. Otherwise, continue on to Attempt n+1.

Partially Irreversible Algorithm for Problem B: First compute x,T_k(x),...,T^(n)_k(x) by applying the function T_k to the input x n-different times. Compute f(x),f(T_k(x)),f(T^(2)_k(x)),...,f(T^(n)_k(x)). If f(T^(i)_k(x))[last] is different from f(T^(i+1)_k(x))[last], then we have found our solution to Problem B. Notice how this algorithm is still quite reversible since the functions f,T are reversible.

Suppose that the function f takes j gates to compute while the function T takes k gates to compute. Then the reversible algorithm takes about 2j+k gates per solution attempt while the partially irreversible algorithm takes j+k gates to attempt. Therefore the ratio in the number of gates per solution attempt in irreversible algorithm to the number of gates per solution attempt in the reversible algortihm is (j+k)/(2j+k)=1-1/(2+k/j) and this ratio approaches 1 as k/j approaches infinity. Therefore while the partially irreversible algorithm may be more efficient than the reversible algorithm, by pumping up the value k, one can ensure that the reversible algorithm and the partially irreversible algorithm are almost as efficient as each other; in the case that one pumps the value of k up high, a miner will want to use a completely reversible device as opposed to a partially irreversible device.

The space of all feasible RCO-POW problems is much larger than I had originally imagined since I originally did not know how to make an RCO-POW problem which can be run on a completely reversible faulty computer.

-Joseph Van Name Ph.D.

After computational device manufacturers produce devices to solve RCO-POW problems, they will have the knowledge and infrastructure to produce reversible computers for many other purposes and possibly even quantum computers.

"Slimeland"-Incentivizing an energy efficient implementation of the CNOT gate-A complement to Nebula.

The purpose of Nebula is the make it as easy as possible for the corporations to develop reversible computers by giving them a return on their investment on new technologies as soon as possible. I have an idea for another kind of POW problem that can together with Nebula achieve this goal much better than Nebula can alone. For this post, let me temporarily call this new POW and its corresponding cryptocurrency Slimeland (I promise to come up with a more professional sounding name later on). To describe this kind of POW, I have to now talk some computer science.

Computer science background: Recall that the CNOT gate is the function from Z_{2}^{2} to Z_{2}^{2} defined by (x,y)->(x,x+y mod 2). The CNOT gate is a reversible gate. It should be easier to construct a reversible device solely out of CNOT gates that it would be to construct any other kind of reversible device for several reasons:

1. The CNOT gate only acts on 2 bits rather than 3 like the Toffoli and Fredkin gates do.

2. The CNOT gate is not universal for reversible computation. In fact, no reversible gate on 2 bits is universal for reversible computation.

3. The CNOT gate is linear.

The purpose of Slimeland is to incentivize the construction of a reversible computer consisting of as many CNOT gates as possible in the same way the Nebula incentivizes a more general purpose reversible computer.

Problem description: Suppose that f is a suitable function composed of CNOT gates. Then the POW Slimeland is to find an N bit hash k along with an M bit string x such that f(k||x)<2^(m+n)/D where D is the difficulty of the problem. Now, the way that I have stated Slimeland should raise some red flags to anyone who is familiar with any linear algebra or cryptography. Slimeland as I have stated is trivially breakable since one can solve for x in
f(k||x)<2^(m+n)/D simply by doing a little bit of linear algebra. Therefore, to remedy this problem, the function f shall be composed mainly of CNOT gates with a few non-linear gates such as Toffoli gates or Fredkin gates to give Slimeland the required non-linearity. For example, the function f could be a composition A_{n+1}L_{n}...A_{1}L_{1}A_{0} where each A_{i} is a non-singular linear transformation of {0,1}^{m+n} and where each L_i is a very thin layer of non-linear gates.

Security issues: As stated Slimeland should still raise some major security concerns since the function f is still nearly linear. Of course, one can make Slimeland secure simply by making f composed of an extreme number of gates (for example, if f contains 1,000,000 gates and 10,000 of these gates are non-linear and the rest are CNOT gates, then Slimeland should be secure). However, this solution brings with itself a few of its own problems. First of all, if f is composed of too many gates, then the security of Slimeland will be reduced since fewer entities will be willing to validate the Slimeland POW. Second of all, as the number of gates in Slimeland increases, there is a greater chance of an experimental reversible device making an error in calculation. We want Slimeland to make it as easy as possible for corporations to construct reversible computing devices, so we therefore want to not burden these corporations with extra error correction and accuracy issues. I do not have any intuition about the number of non-linear gates that we need to ensure the security of Slimeland, and I do not know if this minimal non-linearity issue has been studied in cryptography elsewhere.

Another possible security issue of Slimeland stems from the fact that various circuits may be used to calculate the function f. Suppose that Alice has a circuit A that computes the function has a circuit B that computes f, and suppose that B has twice as many gates as A. Then since A has much fewer gates than B, Alice will have an advantage over Bob (we shall call this problem with f the "possible optimizability" of the function f). I do not have much of an intuition about whether Slimeland is possibly optimizable but I do not want to rule out the possibility just yet.

A proposed solution to these security issues:

So the solution which I propose to these issues shall be called the "internal testing technique." The internal testing technique uses two versions of the POW Slimeland which we shall call Secure Slimeland and Testing Slimeland. Slimeland will therefore have two different POW problems. Secure Slimeland is the POW which is used to incentivize the development of the reversible computer while Testing Slimeland is a POW that tests the cryptographic security of Secure Slimeland without compromising the security of Slimeland.

Suppose that N is a natural number (N will change over time). Then Secure Slimeland will require the function f to run for 3N rounds while Testing Slimeland will only require the function f to run for N rounds. If Slimeland becomes to insecure N will automatically increment by 1 in order to ensure that Secure Slimeland remains secure.

Slimeland will only allow Testing Slimeland to be solved for about 1 percent of all blocks. Furthermore, if Testing Slimeland is solved for Block R and for Block S for distinct R,S then we will require that |R-S|>25. This requirement will ensure that an attacker is not able to use Testing Slimeland to launch an attack against Slimeland. If the difficulty of Testing Slimeland grows too high because an entity has an algorithm that breaks Testing Slimeland, then N will increment by 1.

Testing Slimeland will also be weakened in the sense that a miner will have the option of slightly modifying the circuit that computes the N round version of the function f, and therefore Testing Slimeland will be easier to break than Secure Slimeland even if both problems only had N rounds.

Of course, since Testing Slimeland must be solved for only 1% of all problems, the outputs for the hashes for Testing Slimeland must be 100,000 times lower than they are required to be for Secure Slimeland (otherwise the Testing Slimeland problems will be solved all the time).

As I have mentioned before, the internal testing technique will in itself be a useful POW problem since testing the security of a new cryptosystem is in itself a useful problem (and hence the internal testing technique will help Slimeland obtain a strong perception of value).

The internal testing technique guarantees that Secure Slimeland will remain cryptographically secure, but the internal testing technique does not provide any protection against the possible optimization of the circuit for Secure Slimeland. In order to protect Slimeland against any possible optimization for the circuits that compute Secure Slimeland, miners are allowed to submit optimized circuits the Slimeland blockchain in exchange for coins (the miners will first submit the hash of the circuit+their public key and after the hash has been conformed, the miner may post the circuit). The Slimeland miners will then be informed about the best circuits to use to compute the POW, and Slimeland may use this information to automatically improve its POW.

The prognosis of Slimeland: With these security issues of Slimeland and due to the intricacies present with the solutions to these security issues, it will probably take much more resources to research and develop Slimeland than it would to research and develop other cryptocurrency ideas. I will therefore only devote my time to Slimeland once Nebula is up and running. Let me know if you see any insecurities or if you have any other concerns with Slimeland. Slimeland and Nebula will both incentivize reversible computation in different ways, and they are both necessary for the transition from conventional computational devices to reversible computational devices.

-Joseph Van Name Ph.D.
11/16/2017

Again if you bothered to read my post, then you will see that i  didn't try to discredit this coin rather am actually discrediting the individuals that were trying to do that. Thanks

That sounds freaking Interesting, cant wait so see more and the whole Project, nice Job.

People will take you seriously when you stop posting like that. I already have you ignored because goddamn is that fucking annoying.

This coin looks incredible though, can't wait to see how it all works.

LOL. Princa and Dvyanc are the one responsible for Nebule and Stripple ( Nebule cash) i have been following and busting their several scam attempts in this forum. I find it funny that they trying to use reverse psychology to fool forum members into thinking that their intention is pure. This guys are also responsible for Sonic Ether, Supertonin Network, Evolution lab, Padideo coin, Securivitas, Logic AI, Regrar, Bitcoinash and several other countless scam coins

Princa. dvyanc.

This post is not related to Nebule Cash in any way or any other cryptocurrency or token. The purpose of my upcoming coin is to use a POW that will incentivize the development of the reversible computer. I am trying to solve the problem of "useless" POW problems by introducing a coin with a useful POW problem. No other cryptocurrency is incentivizing reversible computation (I currently resist the urge to change the name of this coin at this point because I am pretty sure that the scamcoin Nebule Cash will probably fail pretty soon. I apologize for any confusion, but the confusion will go away once those scamcoins fall by the wayside).

Hmm. Interesting.

I remember this posted a while ago. I'm super interested in Nebula to be released

jukKas. I am actually using an image that arises from the Laver tables as the logo for Nebula.

Nebulas Token (NAS) is completely unrelated.

Hello Dev, quite an interesting project you have got here. Nebula isn't connected to Nebulas (NAS) in any way right?

It is an interesting project.
I look forward to next information.

I have just posted the security report on http://boolesrings.org/jvanname/2017/11/09/security-report-for-r5-the-pow-problem-for-nebula. I now have the functions for R5 ready and coded in c++, but I need to get the thing launched (at this point, I am pretty sure that I will need some help from professional cryptocurrency developer in exchange for unobfuscated code access that will allow for quicker mining for problems 1-3, and a short period of pre-mining).

jukKas. I appreciate your interest in the Laver tables. They are truly unique and profound mathematical structures that arise from the highest levels of infinity (and they can be understood and calculated by just about anyone too).

I doubt that there will be any security issue for R5 that cannot be remedied by simply increasing the number of rounds since R5 is a symmetric cryptosystem rather than a public key cryptosystem (symmetric cryptography gains its security through the number of rounds while public key cryptography is another story since the Merkle-Hellman knapsack cryptosystem has been broken overnight and it cannot be improved by increasing the  number of rounds.). Each problem in R5 employs many Toffoli gates and Fredkin gates and both the Toffoli gates and the Fredkin gates are universal for reversible computation. Furthermore, any permutation of {0,1}^n can be computed by Toffoli gates with at most 3 ancilla bits.

I have ultimately decided that having a mechanism in R5 that automatically increases the number of rounds in case there is any insecurity of R5 is unnecessary since the security requirements for R5 do not seem too demanding. For R5, recall that the POW is simply to find a 256 bit hash k along with 68 bit string x so that f_i(k#x)<1/d where d is the difficulty. A miner will have little control over k since a miner can only try many different hashes until he finds a good one. A miner can only control the 68 bit string x, and it will be difficult for an attacker to break R5 when he only has control over the 68 bit string x. By the nature of R5, the attacker does not have much room to work with. Therefore, since attackers do not have much room to work with, the functions f_1,...,f_5 only need to be OK randomizing functions in order for R5 to be secure. Most of the work has already been done for me since we already have secure hash functions. In essence, for all i, a one bit change to the input for f_i will result in a completely different output even after going through 1/4 of all rounds.

For option 2, the mechanism to increase the number of rounds will have an additional POW problem which for our purposes we shall call weak R5. Weak R5 will be like strong R5 except that weak R5 will only employ 1/3 as many rounds as strong R5, and weak R5 may employ other features that make it less secure. If weak Problem i is solved too often in proportion to strong Problem i, then the number of rounds in both weak and strong Problem i will automatically increase. Therefore, strong R5 will remain secure since an attacker cannot break strong R5 unless someone is able to break weak R5.

P.S. Since I have posted the original whitepaper on Nebula, I have changed each of the problems R5 slightly in order to increase the level of security.

I wonder if there could be security issues which aren't addressed by any number of additional rounds.

For option 2, how would the number of rounds be increased?  How can an algorithm detect the security is at risk?

I am now testing the security of the problem R5 and my observations will be outlined in a paper. The security of R5 is an issue since it typically takes at least a couple of years for major organizations such as the NIST to analyze the security of a symmetric cryptosystem and much longer for public key cryptosystems. I do not have any of these luxuries and since R5 uses 5 problems, I can only give a basic security analysis of each of these problems and show the security report to a few fellow cryptographers to gauge their approval. Nevertheless, at this point, there are two possible things I can do to ensure the security of R5. I can either make sure that the POW problems in R5 have enough rounds in order to ensure that the cryptosystem remains secure beyond any reasonable doubt for the foreseeable future (Solution 1) OR I can put a mechanism into the cryptocurrency that will automatically increase the number of rounds in the POW problem.

Let me list a few pros of each of the solutions.

Pros for Solution 1:

-A large number of rounds for R5 will increase the reversible computer friendliness since a greater portion of the processing power will be spent on computing reversible functions rather than setting up the input or reading the output for every "hash."

-This solution is simpler than Solution 2. Therefore, with this solution Nebula will be launched more quickly and solution 2 may present its own security weaknesses.

Pros for Solution 2:

-The built in mechanism for testing the security of R5 can be thought of as a useful POW problem which will be in the spirit of Nebula and which will advance cryptography.

-Cryptographers will likely have a greater peace of mind with this solution since any security issue with R5 will be resolved automatically by adding more rounds.

-It may be easier to construct reversible machines that solve R5 if there are fewer rounds (especially for problems 3-5).

Joseph Van Name, take your time to research, we'll be waiting. It's very interesting project, watching this thread!