Topic: Layman's Journey to Understanding Zerocash (Read 3528 times)

I'm not sure I'm following. My base is this:


So, I can check for correctness pretty easily, but to solve the problem it could take generating, inputting and verifying 10.000 tries max (or if I was looking for a DES 8-char password, a lot more) versus just checking for correctness.

On one hand I must have a process to increase the counter loop, input something, check something, restart the loop, on the other hand I only have a process of inputting / checking for the one final answer.

Say if the pin is 6666, or even 0000, in one process I've gone through many more steps to start generating and checking candidates, on the other hand I already know that the pin is 6666 or 0000 and I'm just checking it to see if the computational problem (cracking the pin) is solved.

The process of solving the computational problem (=finding the right pin) takes more time than simply verifying that the problem is solved with the right answer (=checking the pin). If that happens for even one problem, then how can P=NP as a broader "rule"? It can't.

That holds only if you verify a single number
again and again.

Say I want to crack your 4 digit pin (0000-9999).

No matter what I do, I have to generate the numbers, try them, verify them.

Simply verifying the answer is just a subset of generating candidates/trying/verifying. So verification time alone is always less than trying candidates AND verifying.

Time spent (cracking + verifying) > (verifying), because verifying alone is (at least) -1 step.

So P ≠ NP.

@TPTB_need_war

Very good (tech) articles/posts.

Very delightful to read. Thank you!

BTW

Are those projects still alive?

http://zerocash-project.org

http://zercoin.org

http://z.cash

I haven't seen any action since 2014... 

They promise so much improvement towards privacy and anonymity.

Are there any active github repositories?

I just found this (inactive) one:

https://github.com/Zerocash

Is it all dead? 

Most definitely everything being written about here is running the practical software you use every day. NP algorithms are used extensively in software of all types.

Perhaps you do not realize how idiotic and embarrassingly ignorant your statement is?


Well that explains your irrationality doesn't it. Carry on attacking people and not even bothering to understand.

How ashamed will you be in the future if I win the $1 million proving P ≠ NP and simultaneously produce the coin that overtakes Bitcoin? What will you say then fool? Will you hide under a rock?

I wonder what motivates such a gorilla-like behavior. What did I do to you to deserve your irrational temper tantrum?

I understand that these are some theoretical concepts which never have been implemented in any practical way.
But if this is a good outlet for your ADHD, please carry on.

Other good books dealing with computational
complexity, mostly as it relates to AI

Douglas Hofstadter: Gödel, Escher, Bach (classic!)
Rudy Rucker: Infinity and the Mind (transfinite sets, Gödel's proof)
Rudy Rucker: Mind Tools (complexity, Chaitin's Omega)
Roger Penrose: Emperor's New Mind (Anti-AI: the first part of the book is
about the incompleteness theorems)

Hello glad to see your ideas get some flesh.
I will look deeper but a few thoughts on your firsts post, I will return with more
 
I too am not very happy with your approach on determinism , I think you need to look into Denotational semantics to streamline your thoughts on that matter.
As for the layman's journey I think the approach on Complexity of Gregory Chaitin in "Meta Math!: The Quest for Omega" may give you some ideas. Interesting read by an interesting person btw.

Thank you for making that distinction. It is something
that can (I think) be alleviated by proper incentives and rendered
relatively harmless by other means, mainly safety precautions.

In any case, I like privacy solutions that are implemented via
protocol and not by algorithm, as I think they are closer to
the philosophy of decentralization.



Starting to get way over my head again. A rank novice in post-quantum cryptography
such as myself usually gets to hear about hash-based schemes like Lamport
signatures first. Ignoring their negatives (size, one time use) for now,
what sort benefits do you see in employing purely mathematical means (such
as EC isogenies) instead?

Coinswap is trustless in terms of not losing funds, but afaics the anonymity only comes from trust that Carol doesn't reveal that Alice is paying Bob. And from a high flow of such swaps through Carol simultaneously so that an external observer sees a mixnet.

Adding quantum computing resistance to Zerocash or Cryptonote rings is some very intense and experimental math. Some of it hasn't been invented yet. I don't know if I am capable of making that contribution (certainly not without another year of study at least). The quantum resistance for super singular isogenies pairings of elliptic curves is attained because it forms a non-abelian group. This I assume kills Shor's algorithm for factoring because the commutativity property is lost. But I need to study this more deeply before I can comment intelligently on this matter and other potential methods. I do think it is likely that someone will be able to produce quantum computing resistant versions of Zerocash and the underlying zk-SNARKs.

Coinswap is trustless. The parties send refund transactions to
each other off the blockchain, to be published later if someone
disappears or tries to cheat. The protocol is a little
complicated and ugly, but the simplicity of the idea strikes to
me as beautiful.


I know Zerocash is not quantum resistant, and if memory
serves, you have been working to rectify that for some time already 

Coinswap requires trusting the intermediary Carol. You could have every participant act as an intermediary for another set of participants, and then run the transactions across numerous swaps, so that it becomes one big mix but this could I think be jammed. I don't want to be down on something you are developing. I haven't studied Coinswap in detail, but on quick glance my opinion of it hasn't improved. You are correct that the anonymity is quantum resistant, but only because there isn't any cryptography in the anonymity but rather trusting the intermediary.

Zerocash is not quantum resistant as currently formulated.

Don't know if you followed the link to Berstein paper where he makes the point that quantum computing may be too expensive to be more of a threat than classical computing.

Zerocash + quantum-resistant signature scheme is
indeed a kind of holy grail of cryptofinance. (That's why I'm
on this magical mystery bus)

That being said, Tor/i2p is "pretty good" privacy solution
too at the moment, and simple Coinswap-style anonymity
is afaics quantum-resistant (and that is the current goal of
my development efforts.)

Btw, why I am interested in Zerocash:

Sharing one more mental note on P vs. NP complexity, before putting this thread on my back burner. When I come back to this in the future, I will return to the attempt for a layman's explanation. Einstein said (paraphrased) that if one can't explain their science to a layman, then they don't thoroughly understand their science (still remember the public library in Aptos, CA, U.S.A. where I read that in 1995 when I was living in my car and sleeping in the parking lot of the library). I am just rushing at the moment to write down (upload) my thoughts, so I can download my brain dump easily in the future.

(Frankly, I am worn out mentally & physically ill from the past few days of doing this, most certainly due to my illness which prevents me from going full bore as I used to. And I can't sustain this high-level of hours upon hours of research. Seems the light from the monitor even hurts not only my eyes but feel the light penetrating my brain. My brain and stomach hurts. Need a break or pace myself.)

Factorization is inherently less hard than NP-hard problems and developing some generative essence conceptual insight into why, may be helpful.  (Note I made two minor edits yesterday to Wikipedia on this issue)

Note that security of all non-quantum resistant public-key cryptography (such as all elliptic curve cryptography, which includes RSA, Cryptonote, RingCT, CT, and Zerocash) depends on the security of factorization. Quantum secure public key cryptography includes for example the Winternitz signatures that I recently programmed and other candidates, which are covered in Bernstein's book and post-quantum cryptography website.

I believe the following explanation is driving towards a proof that P ≠ NP. I may or may not be very close and may just need to catch up on sleep and free time so I could formulate the necessary holistic understanding of what needs to be proved.

I described in my prior post that NP-hard problems are global walk optimization that requires enumerating every combination of nodes. The only optimization is to eliminate redundant walks that are not unique in the Kolmogorov complexity. Just adding one city in the "traveling salesman problem" can totally change the result and all the computations. There is no periodic structure nor structural localization that isn't a heuristic. I defined precisely what heuristic means. It means the Kolmogorov complexity considered is less than that of the optimum search, thus the result (which has discarded information content necessary for an assured optimization) can't be deterministic (and such heuristic estimations is how we convert NP-hard problems into NP-complete problems in the sense of finding a candidate in polynomial time, and also apparently how the human brain makes decisions about such optimization problems). These suboptimal heuristic estimations can often be quite close to fully optimized, but some cases of input cause the estimation to veer far from optimized (and I believe it may even be undecidable whether all such failure cases can be enumerated).

My conjured abstraction of NP-hard problems is they are co-inductive! I need to prove that. Co-induction means the structure is unknown until finality is reached. Co-induction is the process of peeling away an onion to discover the obscured (opaque) structure and is the mathematical dual of induction which is the process of recursively adding to the observable (transparent) structure. Solving NP-hard problems is the process of assembling the structure co-inductively. I believe this abstract insight might be one that can prove P ≠ NP.

Whereas, factorization is the process of disassembling the inductive process of multiplication. Conceptually we can see that structural disassembly is much less computationally complex than structural assembly, because disassembly can exploit global structure; whereas, assembly has no definitively global structure until the finality (of global walk).

A number has a periodic global structure where the periods are any of the divisors we want to divide that number by. That period cycles over and over through the numerator and the number of cycles of the period is the output of the division operation. Thus it is not surprising that factorization can be parallelized on a quantum computer because the problem of factorization can be converted into finding the period of a function where the Fourier transform to the frequency domain can leverage the 2ⁿ parallel states of quantum mechanics and decoherence of the adiabatic amplitude.


Although the above quoted paper goes into some wild theories about the potential of solving NP-hard problems on quantum computers, afaik (or afaics) those proposed ideas do not seem to factor in the exponential blowup in costs and/or space.

This distinction is also evident in verification. Whereas the verification of whether a number is prime (i.e. has factors or not) is a deterministic exact answer in polynomial time, deterministic exact verification of an HP-hard problem is NP-hard (and is in EXP) and deterministic verification in P (of a lower bound for the optimum) is only an estimation.

Thus I think this answer from Alon Amit is short-sighted in that the search space of factorization does have structure and he seems to assert (quite brashly) that structure is irrelevant. And note similar to my experience at cs.stackexchange where some professors and PhD students sometimes get basic concepts wrong (and are closed-minded to correction!), I noted Alon's answer was upvoted by such prominents. To my horror, I visited cs.stackexchange again today researching this post, and oh my lord the errors in logic there which all seem to stem from not having a solid grounding in the definition of these classes and the definition of nondeterminism being muddled (e.g. by NFAs). I recommend being very skeptical of anything you read on that site. Whereas, most of what Thomas Porin writes on the cryptography stackexchange is astute and helpful (although I saw one error he made also).


Edit: I haven't well developed this thought yet, but it seems that the co-P and other such codomain categorization in complexity theory may be violating category theory. Perhaps that is what my insight will illuminate. Afair, it isn't possible for a member to be both in its domain and codomain. Perhaps NP should be the codomain of P. I need to study all that more carefully. Probably I am incorrect on that, as one would assume many smart people have already looked at that, unless it has a non-obvious twist of insight or logic.

On proving P ≠ NP, I do not understand why it can't be proven that the algorithmic Kolmogorov complexity of the "traveling salesman problem" is at least O(n²(2ⁿ-n-1)), i.e. an exponential lower bound, which is just below the O(n²2ⁿ) of Held-Karp algorithm which is the best known algorithm  

My logic is so simple, that I must be missing something.

At best the algorithm can cache so optimal computation of each grouping of cities will only be computed once (i.e. the number of unique times), by Reed's law we get 2ⁿ-n-1 groupings of cities. And for the first leg of the path possibilities, Metcalf's law tells us there are n² possible unique links between cities.

Afaics, it is definitionally impossible to compute at fewer algorithmic steps than the Kolmogorov complexity, because that is the minimum information content of the algorithm, i.e. the entropy.

Even if we applied some heuristic such as grouping cities in clusters, this would not be an absolute assurance of the optimum path. There is no way to get the assurance while reducing the deterministic algorithm complexity below the Kolmogorov complexity.

Since this algorithm is NP-hard and the related NP-complete problem can be reduced to it, then every problem in NP has the same lower bound. The Independent Set on a planar graph is listed an exception of NP-complete problems being EXP, but this is for edges of the graph that can't intersect, which obviously the "traveling salesman problem" can't be reduced to without some exponential blowup remapping because the links between cities can overlap.

All the NP-hard (and NP-complete reduced on them) problems revolve around exhaustively searching an exponential set of unique possibilities for an optimum. The Kolmogorov complexity can't be reduced to polynomial, because there can't exist a short-cut that destroys information and still is optimum. Once the computation is below the threshold of the Kolmogorov complexity, the result can't be deterministically optimum.

Here is a nearly duplicate proof, but he fails to multiply by n².

One of the similar attempts at a proof I've seen is this one which also attempts to prove a lower bound of the algorithmic complexity. And in his 2014 update, he mentions Kolmogorov complexity as the justification.

Another paper on quick glance appears to try to prove all NP-complete problems are a clustering problem that can't be solved in polynomial time.

This is very well written.

P.S. I was amazed to stumble onto an attempted proof by our very own cohort MPex.


Edit: A possible reason my idea about doesn't work in a proof, from the researcher who discovered the NP complexity class:


More on that point:


Except my logic wasn't employing any probabilistic argument as apparently required by natural proofs nor was I stating that NP problems lack some simple feature that P problems have:


This is a more comprehensible explanation:

http://www.ams.org/journals/notices/201111/rtx111101586p.pdf

I thought maybe I was going to set this aside and go back to programming, but something that might be important has caught my attention and I want to settle this issue before putting this thread on my back burner.

There is an incongruence in my explanation and conceptualization the NP section of the my incomplete second installment (at least what is there as of now until I edit again to finish it), and it was making me confused. This incongruence might be an insight into solving the $1 million bounty for proving the relationship between P and NP. Probably not (given many smarter than me have thought about this problem extensively), but I want to correct my understanding or correct complexity theory, which ever is correct.

The NP class includes problems such as asking whether a specific input threshold distance has a shorter path distance in the "traveling salesman problem". Computing just the NP-hard (not NP) "traveling salesman problem" with exhaustively precise optimum global search is deterministic in EXP (i.e. intractable exponential time, actually factorial N! for naive bruteforce search but improved algorithms are EXP currently best O(2^N), where N is the number of cities input to the computation). Deterministic because it is guaranteed to find the optimum and terminate, but the problem is the time it takes is asymptotically intractable and can't be realistically computed for very large N. There are other estimation algorithms for this problem that can produce less than perfectly optimum answers in P (i.e. tractable polynomial time). These estimation algorithms are nondeterministic because the algorithms can continue searching forever looking for an improved result to the result computed so far. The nondeterminism is whether these estimation algorithms will ever find an improved result or not (relative to current best result found), so it is undecidable when to terminate the algorithm. Converting the NP-hard problem to a NP problem by asking whether the result is more optimum than some input distance threshold is analogous to asking for a consecutive number of 0 digits in the expansion of π, in that it is undecidable (i.e. not knowable a priori) how many steps the algorithm needs to execute to find the requested threshold or if the threshold will ever be found, so both problems are in the NP complexity class because if threshold result is found then it can be verified in P time (I need to explain more clearly that NP only requires verification in P). My conceptualization is the global search of the perfect deterministic algorithm has been converted to a localized perspective that is sampled over time for the estimation nondeterministic algorithm, and thus aliasing error results. By localization I mean observe how the various estimation algorithms sample some local heuristics such as number of times a city has been already visited, instead of a deterministic globalized search. Thus the conversion from the perfectly optimized total/global containment rule (c.f. my upthread discussion about that) which is finite in N thus possessing a bounded, finite entropy (yet requires intractable EXP time), is converted to a localized containment rule which thus opens the entropy to unbounded recursion (analogously as the expansion of the digits of π is unbounded recursion) thus nondeterministic (yet requires only tractable P time). I should explain in the future the congruence of integer factorization to this model of explanation/conceptualization I have employed.

So conceptually I do understand the NP computational complexity. It is proven that global optimization NP problems are NP-complete because the verification of such a nondeterministic global optimization problem is always reducible to a deterministic polynomial computation. Afaics an information-theoretic Pedersen commitment appears to satisfy the requirement of NP in that it can be verified with an algorithm in P. And information-theoretic security is predicated on the entropy of the solution space to be unbounded (i.e. every inversion of the commitment solution is equiprobable), so the valid solution is the one that is revealed for verification.


So where I am driving with this line of conceptualization is that the "traveling salesman problem" is not NP-hard as claimed, because its perfectly optimum solution is computable in EXP but the perfectly optimum solution for information-theoretic inversion is undecidable!! The definition of NP-hard is that these problems should be at least as hard to compute as every NP-complete problem. The error in complexity theory seems to be a conflation between the hardness of finding a result versus the hardness of verifying a result. In other words, there is no relationship between P and NP! Because I first conceptualized nondeterminism as unbounded entropy, this enabled me to see this incongruence (that is assuming I am not missing something and incorrect in my conceptualization).





Thus as we can see that what is proved is insufficient—if it is correct that verifying a Pedersen commitment is in NP—because an information-theoretic Pedersen commitment is always undecidable thus every guess is equiprobable to be correct so there are no solutions and thus the verification can't be converted to a guess on an NTM.

So let's assume that Pedersen commitments are not supposed to be in NP. How could we change the definition of NP so that it would exclude Pedersen commitments. We would have to require that every verification can be converted to a guess on a NTM in order to exclude Pedersen commitments. In that case, NP is not complete for polynomial time, deterministic verification. So what is this pointing to as a deeper insight into computational complexity theory?

The unifying concept (generative essence) appears to be that NP arises not from problems being hard, but because they are undecidable due to unbounded entropy. Thus leads to a conjecture that intractable problems (at least given the machine model available) are equivalent to unbounded entropy and thus can't be in P. Thus Donald Knuth's intuition expecting a bounded solution would be incorrect.

This would tell us something very profound about our universe. I speculate rather brashly that it ties into the Second Law of Thermodynamics that the entropy of the universe is always trending to maximum. So the edge of our universe need only be intractable to be unbounded. The implication is we can't contain infinity within itself and be total. Just as infinite speed-of-light would collapse the past, present, and future into an infinitesimal point in spacetime, if intractable problems were not unbounded entropy then we could compute the edge of the universe and thus compute nothing.

Now to turn that into some kind of defensible proof, even if it is correct which is not certain yet. I look forward to replies educating me on my myopia.

Edit: I realized my mistake. The Pedersen commitment is not binding. So this means the computation of a guess is deterministic because any guess always succeeds. And thus Pedersen commitments are actually in P not NP. I still believe there is some insight to gleem from the observation (conjecture or proven?) that converting deterministic intractable problems into tractable problems makes them nondeterministic and unbounded in entropy, but I am not seeing yet how to frame it in a way that proves anything. Perhaps proving that the conversion must be unbounded would prove P ≠ NP. I need to contemplate that.

P.S. I think I roughly conceptualize how Zerocash works. The program to prove and verify is converted to a boolean circuit and encoded into a quadratic form of a span program and the pairings (that originate from the insight of the ⊕P complexity class due to the completeness of the problem of computing the permanent for the binary case) are obfuscated in ECC fields, so that the computation is homomorphic and the proof only validates if the computation matches the public key. In other words, it is impossible to factor the encoded pairings such that one could create a public key for a program and then fake that they had run the program when they really didn't. I will explain this more clearly in the future when I have more time to study. The ECC math is beyond what I was educated to know, so it will take me some time to digest it.

The reason I was forceful in this point is because I think the aggressive territorialness it the antithesis of collaboration and reason. Szabo told him to go away and write a paper. Maxwell has treated me the same both in cases where I had an error (Winternitz sigs) and also in cases where I was correct (e.g. that CoinJoin can't be protected with blacklisting and also my posts about how to cure selfish mining). I understand these guys can get annoyed with those who are learning and don't have their thoughts well organized or when committing Dunning-Kruger ad nauseum. Wright didn't seem to be abusive, at least in the portion I viewed.

So I have a personal distaste for the "get your toe off my lawn" attitude. I need to remember to contain this urge as any emotional motivation is going to drive irrationality.

Any way, I want to get back on to the topic of this thread, so I hope to make this my last post on this diversion.

P.S. I was so sleepless when I wrote that post that pointed out the error, that I was afraid I had screwed up my thinking. I was rushing and not even enough time to review all the evidence before posting. And I almost messed up the articulation and started to conflate issues myself. I got lucky. Whew. I am trying to do too much. I will eventually make a big mistake too.

Solutions are already present which build on top of Bitcoin or other such coins to provide smart contracts, m of n transactions, programmable features and more for those who want to use more advanced scripting features which bitcoin would be unable to support. The currently most fully featured example of this is Open Transactions. It is also token-less in the sense there are no "coins" being minted in the use of the application keeping it pure.

I also did note that he seemed to be thinking about multiple stacks within the scripting, but then at one point in his response to Szabo, he also said, "...that would assume the only way of devising code would be to put it directly in the script".

And he also stated that the objective or overall point is that we don't need to replace the Bitcoin stack with Ethereum (which I agree is probably a dubious claim due to practical concerns).

So although I agree he did make that statement about multiple stacks within Forth, he also seemed to be alluding conceptually to the unbounded situation in general. It seemed as though he hadn't well prepared his thought process and was also conflating in his mind how he would accomplish it and then at the last moment he added the above quote. That he recovered by making that quoted statement evidenced to me that he was reasonably well informed about complexity theory. He was able to recover (in a live setting on a video feed!) from his initial mistake of asserting that multiple stacks within Forth would be anything other than a finite unrolling of a loop.

I haven't yet observed evidence that he is a total dunce. All of us make mistakes sometimes and have to recover from a faulty statement or thought process. I haven't seen evidence that he is astute enough to have created Bitcoin, but I am questioning whether he ever claimed that. I haven't reviewed enough of his work to form an opinion on what level of expert he likely is.

For example, I can tell you for sure that Gregory Maxwell and Nick Szabo are better mathematicians than me, and will embarrass me if we get into any discussion about algebraic geometry. I would need perhaps up to a year or more of focused deep study to catch up with them in that field. And I don't have that time, so I will defer to experts on that field.