Diving Deeper into Zero-Knowledge Proofs (Part 2)

in #privacy4 years ago

“Knowing Nothing proves everything”
The Economic Times on Zero Knowledge Proofs

image.png

Following up to the previous post about Zero-Knowledge Proofs, we will be talking about them in much more detail.

If you haven’t read the post preceding this one, please do hear over there to make the most out of this one.
Two Men on an Island - An Introduction to Zero-Knowledge Proofs and What Follows (Part - 1)

In Part 1, we saw a brief introduction to Zero-Knowledge Proofs or ZKPs as they are commonly referred, along with a simplified understanding of how ZKPs work. In principle, a ZKP is an outcome that ensures one is able to provide ownership or possession of certain information, without effectively giving out any data about the said information. To put that into perspective, we discussed a hypothetical story of two men on a treasure hunt in a remote island, each holding one-half of the means to reach the treasure.

Assuming that you’re reasonably affirmative on the understanding of the philosophy of ZKP, we will move ahead to see how ZKPs can be calculated, the different methods by which one can calculate them, and some of their uses, until finally, we move on towards the final part of the series where we will be focusing on real-world applications of ZKPs.

It must be noted that the concept of ‘proof’ in ZKP is different from the traditional mathematical concept. Mathematical proofs are strict, using either self-evident statements or statements obtained from proofs established beforehand. ZK proofs are more similar to the dynamic process used by humans to establish the truth of a statement throughout the exchange of information.

Classification of ZKPs

ZKPs, with their apparent need in the virtual world, are immensely useful in everyday application. But the use of ZKP differs based on the number of participants involved. For a small group or a few million people, ZKPs are able to successfully transmit the said communication.

Interactive ZKP

Being one of the most used forms of ZKP, interactive ZKPs are exactly what the name says. The parties involved in proof have to interact with each other, affirming along the way about their satisfaction about the proof provided. Most Interactive ZKP involve a small number of parties, as it is not feasible to constantly ask for affirmation from a large group of participants. The example we used about two men on an Island falls under this category. To make sure “I” communicate the proof to “You”, I used an interactive method of probabilistically ensuring the ownership, i.e., taking trips around the island and reaching the starting point.

image.png
Source: TopRankBlog

To quote the definition, “An interactive proof protocol is complete if, given an honest prover and an honest verifier, the protocol succeeds with overwhelming probability (i.e., the verifier accepts the prover’s claim). The definition of overwhelming, of course, depends on the application, but generally implies that the probability of failure is not of practical significance.”

Non-Interactive ZKP

To break down the problem of mass communication, Non-Interactive proof have to be formulated. A Non-Interactive ZKP is a special kind of proof that does that involve constant verification on the other end. Say one has to communicate to the entire blockchain network about a transaction you just performed but do not wish to disclose information about the transaction, its receiver, etc., one has to use some form of Non-Interactive ZKP.

Non-interactive ZKPs are used when large number of participants are involved and most importantly, when one needs to give a proof without the need for constant interaction.

Ways by which ZKPs can be Solved

zk-SNARKs

Zero-Knowledge Succinct Non-Interactive ARgument of Knowledge or zk-SNARKs is one of the most used privacy concept within the cryptodevelopers community. As the name suggests, SNARKS are probabilistic means of assessing and arguing about the validity of a particular information. In simple words, zk-SNARKs present Proof-of-Knowledge in the form of a secret key, that could only be generated if the person claiming ownership has the information in the first place.

image.png
Source: MayContainMath

One of the most simple forms of zk-SNARK is the verification of a hash. If a person has to prove they are in possession of a certain number, he can hash that number using any of the hashing algorithms. Since that hash is a representation of a particular set of information, it can be verified that the hash belongs to the predetermined number when the number comes out.

Even though it wasn’t the first to use an iteration of zk-SNARKs, the cryptocurrency Zcash was responsible to popularize the protocol. Ethereum followed up in 2017 when they forked the chain to allow the option of using zk-SNARKs when creating smart contracts.

zk-STARKS

image.png
Source: Game of Thrones

“zk-STARKs were created by Eli-Ben Sasson, a professor at the Technion-Israel Institute of Technology. As an alternative version of zk-SNARK proofs, zk-STARKs are, generally, considered a more efficient variant of the technology - potentially faster and cheaper depending on the implementation. But more importantly, zk-STARKs do not require an initial trusted setup (hence, the “T” for transparent).”

zk-STARKs were created to fill the gaps of zk-SNARKs. It is quite tough to communicate how zk-STARKs improve zk-SNARKs without getting a bit technical, but I will try my best to tone it down.

zk-SNARKs are non-interactive proofs that give ownership information to a large group without the need to interact with the proof. To do this, the private keys of the proof have to be created and attached to the string of the proof to ensure it is true and fair. The private key is the only part of the SNARK proof that stays behind the eyes of the public. Even though zk-SNARKs are proven to be quite effective, a vested party with enough resources can manipulate the loophole by creating similar proofs, hiding the private key.

zk-STARKs fixes the loophole by using randomness instead of private keys to generate the proof. By this mechanism, all information regarding the proof is public and thus, the resilience against the proof is increased. Another advantage is that zk-STARKs are known to be Quantum resistant. As there is no cryptographic asymmetry due to the use of public/private keys, Quantum computers cannot be used to crack the protocol.

Although the proof is undergoing constant updates, zk-STARKs have a prospective future ahead.

Right now, no public blockchain has integrated zk-STARKs. Though, it is likely that they will find themselves in Zcash or Monero over the coming years and possibly Ethereum, also.

Bullet Proofs

Screenshot 2019-04-24 at 2.04.41 PM 1.png

One of the latest additions to the privacy based cryptographic protocols, Bulletproofs were proposed by Stanford’s Applied Cryptography Group (ACG) in December 2017 in an academic paper. Bulletproofs are “a new zero-knowledge argument of knowledge system, to prove that a secret committed value lies in a given interval.” The bulletproof name is credited to Shashank Agrawal for describing them as being “short like a bullet, with bulletproof security assumptions.”

The proofs of bulletproofs are much shorter than other range proofs. Bulletproofs also does not require a trusted setup. They are especially suited for the distributed and trustless nature of blockchains and can create substantial long-term cost savings, enormous space savings, lower fees, and faster verification times than current implementations of range proofs. Monero states that they have reached an 80% reduction in transaction size utilizing bulletproofs which leads to an 80% reduction in fees as well.

(I apologize for using words that stand out of the general level of understanding, but that was the best I could do without messing up the explanation.)

Places where ZKP can be used

  • A Blockchain where privacy is of utmost value can make use of ZKPs to ensure the trestles flow of value without the propagation of any information other than the ownership of the said value. Zcash and its predecessor, Zcoin make use of zk-SNARKS to ensure the safety of privacy along with the transmission of information and value.

  • Peer to Peer communication is when two parties communicate with each other without any intermediary in between. They might communicate P2P for several reasons; to stay away from prying eyes, to exchange sensitive information, to transfer value without much attention. ZKPs prove to be the best means for parties to have a truly private mechanism to communicate and transact.

  • Voting is also an essential part of every democracy from that of a country down to the shareholder participation of a company. Hence, with nations moving towards digitization and with the proliferation of security tokens, the demand for secure and anonymous voting solutions is bound to increase. ZKPs are bound to make an appearance here.

It is clear that both zk-SNARKS and zk-STARKs appeal to the growing concern in regards to privacy. Within the cryptocurrency world, these protocols have great potential and may be a groundbreaking avenue towards mainstream adoption.

In the last part of the series, we will dive into real world applications of ZKPs, where they are currently used and where they can be used. Please do let us know if you would like use to cover anything else other than what we have planned.

Sources:

  • SB


ReverseAcid Monthly Recap


Crypto Analysis Series


Previous Posts


About Reverse Acid


Be a part of our Discord community to engage in related topic conversation.


Follow our Instagram and Twitter page for timely market updates

​​

Sort:  

Dear @reverseacid

First of all, thanks for sharing link to your publication with me.

a ZKP is an outcome that ensures one is able to provide ownership or possession of certain information

I found it quite confusing and fascinating. Can information be owned and treated like an asset?

a hypothetical story of two men on a treasure hunt in a remote island, each holding one-half of the means to reach the treasure.

Oh yeah :) I remember now how I sugested my solution that involved a little bit of violence :)

ps. Difficult topic. As much as I found this issue quite interesting, it's also not easy to "digest" and understand.

Yours
Piotr

Hi there! The cost to spam my wallet is 0.5 Steem. So please increase your payment to this amount or remove me from your distribution list.

Failure to comply will result in flags to the value of 0.5 Steem.

Thanks!

Posted using Partiko iOS

Привет друг, отличная работа.

Hello!

This post has been manually curated, resteemed
and gifted with some virtually delicious cake
from the @helpiecake curation team!

Much love to you from all of us at @helpie!
Keep up the great work!


helpiecake

Great series!

Thanks for the education! ;)

Where and how does Grin (mimblewimble) come in?

@lauch3d this could be interesting

Posted using Partiko Android

Thank you for your introduction,
That gives the other party, let the other party verify that he is the real owner,
That verification code should only be used once!

Hi @reverseacid. Another well written article. Thank you.

This is an area I've not researched before, so I'm looking forward to learning more. Your article is a great starting point.

Thank you for sharing this post. I am not familiar with Zero-Knowledge proofs so a lot of info to start with. I will save it and reread it later again.

Posted using Partiko Android

Hello @wakeupkitty.

To make the everyday user familiar with concepts that usually try to scrap off our head is what we are thing to achieve. I hope you found a little clarity by going through our post.

We would personally like to thank you for all the effort you've been putting in for us. We don't really know how we could return the deed.

Always open for suggestions from your side. Much thanks.

Cheers.

Posted using Partiko iOS

Excellent information, educational, always present, congratulations, great job.

Hello @belkisa758.

Much thanks for taking out the time to go through our post. Do stayed tuned for more information in the future. Your suggestions are always welcome.

Cheers.

Posted using Partiko iOS

The entire crypto phenomena seems to come down to an issue of veiled centralization of controlled currency - surely there exists someone with the knowledge of the exact calculation of man hour labor over what course of time is equal to the sustainability of the growing human population. At what simple point have we reached such singularity? i.e. why is the internet not free (and tax free??) for all now that the sufficient worldwide infrastructure is in place? Please consider in terms of this angle.

  • your thoughts

Hello @lanceman. Thanks for checking out the post.

Coming to your point, what you ask say is reasonable. Due to the increasing exponential use in internet traffic, it is reasonable enough to assume that the cost of accessing the infrastructure should be astronomically low.

But as you said, centralized gatekeepers exist to keep a check and profit off of entry. That's why all of us here are fighting for. We are fighting for a decentralized internet infrastructure that's rewards users based on participation rather then charging them for usage.

IMO, the days where this is even a remote possibility sounds not to far. Recently we saw a projects trying to do just the same. @jadams2k18's introduction to the NOIA Network can help you gain some perspective. As we understand it, NOIA is a protocol for a decentralized internet architecture.

Hope that tries to answer your query.
Cheers.

Posted using Partiko iOS

Hi! I'm still using NOIA Node application

Congratulations @reverseacid! You have completed the following achievement on the Steem blockchain and have been rewarded with new badge(s) :

You made more than 5000 upvotes. Your next target is to reach 6000 upvotes.

You can view your badges on your Steem Board and compare to others on the Steem Ranking
If you no longer want to receive notifications, reply to this comment with the word STOP

You can upvote this notification to help all Steem users. Learn how here!

Your post is very interesting. ZPK will apparently prevent governments from seeing our transactions, ensuring our confidentiality. Although this would lead to problems when used for illicit purposes, such as drug smuggling, arms dealing or trafficking in women. So I must think they must have a form of protection against such uses.

I liked the fact that it can be used for voting. This way it would not be necessary so much expenditure to execute a referendum or elect a president. It would be excellent, I hope it is a not too distant future can be implemented.

Thanks for sharing

Dear @reverseacid,

Initially, I have to say that the whole zero knowledge proof was a bit confusing to me but, when I delved deeply, I was able to understand and appreciate its use and efficiency.

Here is a simply way in which it could be explained for those folks who are struggling: just take a sec and read the ali baba cave explanation.

https://en.wikipedia.org/wiki/Zero-knowledge_proof

I hope this simplifies things up.... for some of the folks out there who are struggling like me to understand things.

Hello @nurseanne84.

Thanks for taking out the time to go through our post. In general, it is our goal to aalow the everyday user exposed to concepts that may usually go above their understanding. Toning down concepts that require much thought and analysis is always our long standing goal.

We are glad that discussing topics such as this starts a discussion among our followers, on the hopes that somewhere in the long run, you look back and remember how it all came to you.

Thanks for sharing the link. I'm sure our fellow steemians will be quite interested.

Cheers.

Posted using Partiko iOS

Regards appreciated @reverseacid.
I confess that it cost me some effort to understand this concept, new for me.

The ZKP, with its apparent need in the virtual world, are immensely useful in everyday applications. But the use of ZKP differs according to the number of participants involved. For a small group or a few million people, the ZKP can successfully transmit such communication.

This shows that its scope and scalability is of great magnitude. If its applicability can "pierce" and benefit a large mass of people as well as a small group, then we are talking about a very versatile tool.

Thanks for sharing with us.

Quality post about ZKP! Thanks @reverseacid

"...I will try my best to tone it down."

I say tone it up! Make it as technical as you possibly can. You won't turn me away, and I doubt I'm alone in that.

No need to exclude the quick and dirty explanations however. Many appreciate that, myself included.