The Power and Potential of Zero-Knowledge Proofs

How can you prove something with nothing, confirm the correctness of a transaction with no underlying information, and design software that runs as required but does not reveal how it achieves its functionality?

The answer is zero-knowledge proofs (ZKPs), developed by computer scientists and mathematicians who acknowledge they are counterintuitive, and now are beginning to move out of the sphere of theoretical computer science, through the realm of possibility and into practical commercial applications.

The notion of ZKPs was introduced in a 1986 paper by Oded Goldreich at Technion, the Israel Institute of Technology in Haifa, Israel; Silvio Micali at the Massachusetts Institute of Technology; and Avi Wigderson at the Hebrew University in Jerusalem, Israel. The paper demonstrated the generality and wide applicability of such proofs, stating, “These are probabilistic and interactive proofs that, for the members of a language, efficiently demonstrate membership in the language without conveying any additional knowledge.”

An example based on the Where’s Waldo books was offered by Tom Gur, a professor in the department of computer science and technology at the U.K.’s University of Cambridge. “Suppose I am playing a game of Where’s Waldo with primary kids. I want to prove I know where he is without revealing his location. If I take a large piece of black paper and cut a small hole in it and put it on the page so that Waldo’s face can be seen, I can prove that I know where Waldo is without revealing his location.”

Gur added, “These proofs admit more powerful properties than traditional nondeterministic polynomial time (NP) proofs. One can prove a statement without revealing any information other than its correctness.”

ZKPs are the result of many years of research into how to solve some of the biggest problems in science and mathematics, a move away from lengthy documents designed to show proof and towards an interactive proof involving a proofer and verifier. Essentially, they use a cryptographic protocol that allows a proofer to convince a verifier that a statement is true without revealing any additional information.

Gur noted increasing interest in ZKPs as a means of proving a statement while retaining privacy and ensuring information security. “Today, these proofs are a major force in blockchain transactions and are also being applied in other large real-world systems that need to prove a transaction has been made while revealing zero information,” he said. While focused on the theoretical computer science behind ZKPs, Gur also helps industry partners understand the possibilities of the technology.

Michele Ciampi, a Chancellor’s Fellow at The University of Edinburgh in Scotland and a specialist in ZKPs and cryptography, referred to the early work of Goldreich, Micali, and Wigderson, saying, “This is a beautiful theorem. It doesn’t matter how complex a statement is, it is possible to produce mathematical proof that conveys nothing more than the fact the statement is true.”

Amit Sahai, a professor of computer science at the University of California, Los Angeles (UCLA), noted that early views described ZKPs for general statements as “beautiful math objects” that were impractical because they were so slow and inefficient. “In the 1990s, I couldn’t imagine that ZKPs for general statements would be used in a practical way, but I was wrong. It is fascinating to see how that has changed,” he said.

In a use case of economic capacity, Ciampi described convincing another person that you have enough cryptocurrency for a particular purpose, without telling them how much you have. “I don’t show the number of coins I have, but can prove the number of coins I have exceeds a certain threshold,” he said.

Where a large volume of computation is required and data is transferred to a cloud service provider, ZKPs can be used to verify the data computation is correct and in line with stated rules. In this scenario, the cloud gets access to the data to perform the computation. Hiding the data from the cloud service provider is a more advanced problem, but can be resolved using fully homomorphic encryption (FHE) that encrypts the data and allows it to be processed without being decrypted.

How can you be sure that ZKP computations are correct? “Randomness,” said Ciampi. “To prove that a computation is correct, the verifier checks a few locations and gains confidence that the proof is correct, despite having no knowledge of the underlying information.”

Ciampi collaborates with U.S. universities on ZKP research and development and has received interest in his work on the use of ZKPs in digital identity from the Scottish government. He notes that the more data we share, the more it becomes a concern, requiring sophisticated techniques to protect that data.

ZKPs can be applied to use cases in a variety of industries, especially where data integrity and accuracy are crucial. These include online security, data privacy, digital identity, gaming, healthcare records, verifying transactions, online voting systems, network security and authentication, digital signatures on blockchain networks, and tracing carbon emissions without revealing sensitive information.

They also are in continual development in terms of not only application, but also technical improvements in areas such as speed and efficiency. As part of his work, Sahai studied the feasibility of ZKPs, such as the use of elliptic curves to improve the speed of proofs, and a focus on blockchain that has allowed a step-change in the development of proofs and attracted interest, investment, and practical application from industry.

“Technology development is happening right now,” Sahai said, citing his activity in designing ZK software that runs as required, but does not reveal how it achieves its functionality. This, he said, is “far from anything practical,” but certainly has potential.

On a more practical level, Sahai offered the example of using a driver license to provide proof of a person’s identity when applying for a post at a company. “A driving license document verifies who the person is, but provides too much information about them. If the company wants specific information, the person can respond using ZKP technology that exposes only required credentials, such as address and birth year. Imagine a world of applications where you can selectively reveal information, but where the recipient can also be sure that the information is accurate.”

Imagine, too, a world with fewer hard-copy documents, fewer opportunities for mistakes, data breaches, and data manipulation, and more opportunities to manage and control your own data.

Fermah, a start-up founded in 2023 that released its universal proof generation layer in September 2024, aims to encourage the use of ZKPs by providing a tokenized marketplace that comprises a supply side of equipment such as GPUs, CPUs, and FPGAs to generate proofs and a demand side of proof seekers. In the middle, the Fermah Matchmaker, which is neutral to all proof systems, uses an algorithm to match the supply and demand sides. By aggregating demand from various sources, suppliers can achieve economies of scale and reduce the costs of proof generation on the demand side.

Vanishree Rao, founder of Fermah, has 15 years’ experience in designing and building ZKPs, was involved in development of the Mina and Midnight protocols, and completed a Ph.D. in cryptography at UCLA under the auspices of Sahai. She explained, “At Fermah, we completely take away the pain of proof generation and reduce the expense of generating proofs. Customers simply send proof requests and receive proofs that they can easily verify.”

The company’s early customers are in the blockchain space and need ZK-rollups that provide a scaling solution by moving computation off-chain while storing transaction data on-chain and using ZKPs to validate transactions while increasing transaction throughput and reducing costs. There is more to come. “We want to generate proofs for the world and we want the world to embrace ZKPs on the basis of their power, capability, and credibility,” said Rao.

Eli Ben-Sasson, co-founder and president of Israeli firm StarkWare, a provider of scalability, security, and privacy for blockchain applications using ZKPs, has been researching cryptographic and zero-knowledge proofs of computational integrity since he received his Ph.D. in theoretical computer science from the Hebrew University in 2001. He is also a co-inventor of the ZK-STARK, Fast Reed-Solomon IOP of Proximity (FRI), and Zerocash protocols, and a founding scientist of cryptocurrency firm Zcash.

In moving beyond the use of ZKPs for privacy and security to deliver scalability, Ben-Sasson noted, for example, that it isn’t possible to poll everyone to prove the integrity of election results, but it is possible to ask thousands of people across the country to get a feel for what has happened without revealing any personal information.

Like Ciampi, Ben-Sasson suggested a mathematical approach to integrity that does not require inspection of every step of a computation, and instead samples random locations to discover whether the computation has integrity, made an error, or has been manipulated in some way. “This is extremely efficient compared to initial processes that didn’t have enough computers to manage all the information,” he said.

Further efficiencies have been achieved by using a variant of Fast Fourier Transform (FFT), a mathematical technique for converting a signal from the time domain into the frequency domain. “We have used a version of FFT to take on the hardest part of proof generation and make it really fast,” explained Ben-Sasson.

StarkWare also uses the FRI protocol, which is now ubiquitous to blockchain, and ZK-STARKs, a type of ZKP that improves scalability, transparency, and security compared to other ZKP variants such as ZK-Snarks that require a trusted party to generate a common reference string that can be a security concern. ZK-STARKs does not require a trusted setup.

StarkWare, as a provider of infrastructure to commercial third parties, also has developed Cairo, a Rust-inspired programming language that can be used by developers to create STARK-provable programs for general computation. “Blockchain and ZKPs are two technologies that innovate on integrity,” Ben-Sasson said. “Blockchain solves problems through open and transparent networks that everyone can inspect. ZKPs solve integrity with brilliant math.”

While the power, potential, and practical application of ZKPs has accelerated over recent years, a challenge and opportunity lie ahead. As quantum computing gets closer to reality, current cryptography systems may prove vulnerable. STARKs, however, could save the day as they are considered the most scalable, safe, and secure post-quantum cryptography.

Further Reading

• Ben-Sasson, E., et al.
  Scalable, transparent, and post-quantum secure computational integrity, Cryptology ePrint Archive (2018).
• Goldreich, O., Micali, S., and Wigderson, A.
  Proofs that Yield Nothing But their Validity or All Languages in NP Have Zero-Knowledge Proof Systems, Journal of the Association for Computing Machinery, Vol 38 No 1, July 1991, pp 691-72
• Gur, T., O’Connor, J., and Spooner, N.
  Perfect Zero-Knowledge PCPs for #P. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing. 2024.
• Thaler, J.
  Proofs, arguments, and zero-knowledge. Foundations and Trends® in Privacy and Security 4: 2–4 (2022): 117-660.
• Vadhan, S. P.
  A study of statistical zero-knowledge proofs, Diss. Massachusetts Institute of Technology, 1999.