Zero Knowledge Proofs - an overview (without the maths)
If you spend enough time in the cryptocurrency/digital assets space, you will hear the words “Zero Knowledge” mentioned quiet often. For most, the maths just block out all the maths and cryptography terminology when people talk about zero knowledge proofs.
In this short post, I will attempt to explain zero knowledge proofs as well as their many applications - all without the hard maths and cryptography formulae.
Zero Knowledge proofs isn’t new, it’s been around since the 1980s - although mostly theoretical, in recent years this field of study has taken a life of its own with the practical implementation in the blockchain space.
Cool, but what are Zero Knowledge proofs (zkp)?
It’s a protocol used for mathematically proving knowledge of something by one party (“Prover”) to another party (“Verifier”), in such a way that the proof doesn’t leak any more information.
Every Zero Knowledge proof contains the following properties:
Completeness - if the proof is true, the Prover can prove it repeatedly
Soundness - if the proof is false, it’s very hard for a Prover to claim it’s true to the Verifier
Zero Knowledge - if the proof is true, no other info about it is disclosed to the Verifier
In other words, one can prove knowledge of something, without disclosing that ‘something’ or providing clues that could lead to the knowledge of that ‘thing’, but done in such a way that the party you are proving to is satisfied of your knowledge of that ‘thing’. These Zero Knowledge proofs prove knowledge of something, not merely its existence i.e. with zkp, I can prove my age, not necessarily prove that age exists. This blogpost provides some illustrations of such examples, but for a more deeper dive into zkps, this matter Labs Awesome Zero Knowledge Proofs repo contains alot of information.
Given the number of years this field of study has had, we can be assured that the maths/cryptography is correct. With this assurance, we can forgo trying to fully understand the maths/cryptography and focus, instead, on the various applications and implementations of this novel cryptographic field of study.
An overview of some major/well-known ZKP systems include zk-STARK, zk-SNARK and bulletproofs (efficient range proofs):
zk-SNARK is an acronym for Zero-Knowledge Succinct Non-Interactive Argument of Knowledge. This has the following explanation:
Zero-knowledge: if the statement is true, a verifier does not learn anything beyond the fact that the statement is true.
Succinct: The size of the proof needs to be small enough to be verified in a few milliseconds.
Non-Interactive: Only one set of information is sent to the verifier for verification, therefore there is no back and forth communication between the prover and verifier.
ARgument: A computationally sound proof: soundness holds against a prover that leverages polynomial-time, i.e. bounded computation.
of Knowledge: The proof cannot be constructed without access to the witness (the private input needed to prove the statement)
zk-STARK is an acronym for Zero-Knowledge Scalable Transparent ARguments of Knowledge. zk-STARKs improve on the scalability of zk-SNARKs, but also removes the “trusted setup” which zk-SNARKs rely on. Trusted setup is the process of requiring a trust third-party to initially setup the ZK proof system. But this reliance on a third-party weakens the privacy properties of such a system. What zk-STARKs rely on instead, is to use publicly verifiable randomness to create trust-less, verifiable computation systems.
Bulletproofs are short non-interactive zero-knowledge proofs that require no trusted setup. Bulletproofs are a new type of more efficient range proofs (a range proof is basically cryptographic proof that a secret number is within a certain range e.g. with range proofs, I can prove that my age is between 19 and 25 years old, without expressly disclosing my age - just the range)
These ZKPs all differ with sizes of proofs, time it takes for proof computation, etc. These zkp implementations in blockchain protocols help with financial privacy, security size and speed of the values transacted on these protocols.
ZKPs in Blockchains
Ethereum, Zcash, Grin, Monero, Beam, Mina & Aleo, etc are just a few of the many blockchain protocols that utilize some form of ZKP.
Since there is already ample content about ZKPs in the blockchain ecosystem, we won’t dwell much on this application/implementation.
ZKPs in CyberSecurity
Vulnerability/exploit disclosures
An interesting development of ZKPs in CyberSecurity field is one spearheaded by DARPA (Defense Advanced Research Projects Agency) as part of their Securing Information for Encrypted Verification and Evaluation (SIEVE) program. Specifically, the focus is using ZKPs in vulnerability disclosures, such that a researcher can prove to a vendor that, not only does a particular vulnerability exists but that they have an exploit for such a vulnerability, all the while without revealing any further details about the vulnerability or exploit in question.
2 teams that took part in this DARPA challenge, Galois and Trail of Bits have already developed capability to mathematically prove exploitability of vulnerable software without revealing critical information. Trail of Bits have a more detailed walk-through of their thought process on this. Galois also have an overview of their approach to this in their Project Fromager.
Authentication (e.g username, password, MFA)
M-Pin is client-server protocol, which features two-factor client authentication as an alternative to Username/Password.
The basic idea is that a registered client is provided with a cryptographic secret, which is used to prove to a server for authentication purposes; all without ever disclosing the secret to the server. This means no information about that secret is ever stored on that server.
The cryptographic key is split into two factors for authentication : a user-select PIN and a token (stored in the Browser, for example). I recommend reading the paper linked above about this protocol.
There is already a live product that uses the M-Pin protocol, MIRACL Trust®, a cloud-based MFA platform that provides secure, multi-factor authentication to employees, partners, and external users without sending authentication credentials across the web for storage in the cloud.
Cyber Attribution?
The U.S Intelligence and Law Enforcement agencies have been public about some attributions, without always being in a position to disclose how knowledge of that information came about - it could be via sources, via compromising enemy infrastructure, etc. So it’s understandable why it would not be operationally wise to disclose that information.
We are required to trust and believe the unnamed methods and sources from these agencies relating to their attribution.
Although unsure of how the actual mechanics would work, on a theoretical level, this is another area which zero knowledge proofs would be beneficial for cyber attribution. Just as with how they have always done it, they could make a statement, and prove they have this knowledge, in such a manner that the public, and indeed the outed enemy, wouldn’t know exactly how they know, but would be assured that indeed that knowledge and proof is true.
We can leave it up to DARPA to fund another program to tackle this :-)
ZKPs in Decentralized Identity Standards
Microsoft and the Decentralized Identity Foundation, among others, have an initiative for Zero-Knowledge Proof scheme that enhances user privacy and security for digital credential systems.
Current issues with Verifiable Credentials (VCs), which their SNARK-based ZKP credential scheme could address
The specific scenarios their zk-vc scheme is looking at are: Publishing a resume on a career networking app, checking the current status of work history credentials or interviewing for a new job.
I would highly recommend you read their paper, zero knowledge credentials with deferred revocation checks, on this if this is of interest to you.
Conclusion
Many of us, being non-cryptographers or mathematicians by training, tend to shut off our minds when reading/hearing about most things cryptography related (we only like the cryptocurrencies coz….hey, who doesn’t like money :-D ).
But I hope this short post has given you an overview of the various applications of zero knowledge proofs beyond just blockchains.