“Any sufficiently advanced technology is indistinguishable from magic”
Clarke’s Third Law
It implies that breakthrough technologies might look like magic to those who don’t understand them.
Today, blockchain technology hasn’t reached this magical stage. Yet, zero-knowledge proofs stand out as a key innovation that could transform blockchain into something that feels truly magical.
This article series aims to simplify and explore zero-knowledge proofs: what they are, how this technology has evolved, and how it might shape our future in the coming decade.
Bridging the Past and the Future
The evolution of blockchain technology, initiated by Bitcoin’s vision to transform the financial landscape into a decentralised system, has been a tale of groundbreaking advancements tempered by inherent constraints.
Central to the blockchain ethos is the revolutionary idea of decentralisation, a model that distributes control of transactions and data away from centralised authorities, across a widespread network.
While Bitcoin set the stage with its narrow focus on creating a new financial paradigm, it also deliberately limited the scope for more complex developments to maintain its primary objective.
Emerging in Bitcoin’s wake, platforms like Ethereum sought to push the boundaries further by enabling a broader array of decentralised applications (dApps). These ranged from decentralised finance (DeFi) protocols, which introduced novel means for lending, borrowing, and exchanging digital assets, to marketplaces for trading digital art and collectibles. This expansion represented a significant leap towards realising the full potential of blockchain technology.
However, this progress has been checked by substantial challenges. The costs associated with conducting transactions on these networks remain prohibitively high, and the platforms themselves face severe limitations in the complexity and operational efficiency of the applications they support.
These obstacles have stifled the ambition to achieve a truly decentralised web, often referred to as Web3, where users can interact in a secure, private, and efficient digital ecosystem.
Throughout this journey, blockchain core developers were unceasingly in pursuit of a technology capable of navigating a course to full fill these grand ambitions without straying from the foundational principles of the blockchain space. This quest led to widespread recognition of the transformative potential of Zero-Knowledge (ZK) technology, which had already started to evolve massively in efficiency aspect.
ZK technology stands out for its unparalleled capacity to address the pressing issues that have so far curtailed the scalability, efficiency, and privacy of blockchain applications, aligning perfectly with the core ethos of decentralisation, security, and user sovereignty.
But how is this technology being leveraged by blockchain-based systems, or what exactly does ZK technology entail?
Let’s talk about that first.
Enter the World of Zero Knowledge Proofs
At its core, Zero-Knowledge Proofs (ZKPs) enables the exchange of information between two entities without compromising sensitive data. This groundbreaking technique was conceptualized in the 1980s by a trio of MIT researchers: Silvio Micali, Shafi Goldwasser, and Charles Rackoff.
They envisioned a mechanism whereby one party, known as the Prover, could validate the truth of a statement to another party, the Verifier, without divulging any information beyond the veracity of the claim.This method is akin to demonstrating one’s financial capability to a landlord without disclosing specific monetary details.
These contributions of Micali and Goldwasser in the field of cryptography were later recognized with the prestigious Turing Award, underscoring the profound impact of their work.
Where’s Waldo?
To elucidate the workings of ZKPs, let us consider the familiar challenge of the “Where’s Waldo?” puzzle. Within the pages of this children’s puzzle book, Waldo is a diminutive figure concealed amidst a multitude of characters, with the task being to pinpoint his location.
In this analogy, we introduce two protagonists:
- Alice (the Prover)
- Bob (the Verifier)
The game of “Where’s Waldo?” commences with Alice and Bob. Shortly after starting, Alice announces that she has identified Waldo’s hiding spot.
Bob, harboring doubts, requests Alice to substantiate her claim without revealing Waldo’s precise location. Ingeniously, Alice employs a zero-knowledge proof strategy.
She procures an opaque card significantly larger than the puzzle, into which she cuts a Waldo-shaped aperture at the center, just ample enough to expose Waldo and nothing more.
By overlaying the card atop the puzzle, Alice is able to demonstrate to Bob her knowledge of Waldo’s location, all the while concealing his exact whereabouts.
Through this inventive ZKP Alice, the Prover, convinces Bob, the Verifier, of her knowledge regarding Waldo’s location without imparting any supplementary details about his specific position. This example illustrates the essence and capability of zero-knowledge proofs in safeguarding privacy while affirming truth.
The Evolution of ZKPs: From Conceptual Foundations to Practical Applications
The foundational work in the 1980s on ZKPs not only heralded a new paradigm in cryptography but also validated the feasibility of zero-knowledge protocols, laying the groundwork for future exploration and development in this domain.
This era was characterized by the conceptualization of ZKPs, where the notion of proving the truth of a statement without revealing any information beyond its veracity was introduced, setting a precedent for privacy-preserving cryptographic protocols.
Through the 1990s, the efforts of the research community were concentrated on refining and broadening the initial models.
Initially, ZKPs were interactive, requiring multiple rounds of communication between the prover and the verifier. This interaction was a critical component of the proof process, where the verifier would challenge the prover, and the prover would respond to these challenges to establish the truth of the statement without revealing any underlying information.
While effective, this model had limitations in terms of efficiency and practicality, especially in scenarios where real-time or rapid verification was necessary, or where communication between the prover and verifier was constrained.
The Introduction of Non-Interactive Zero-Knowledge Proofs
The development of Non-Interactive Zero-Knowledge Proofs (NIZKPs) in the early 1990s marked a significant advancement. NIZKPs removed the need for this back-and-forth communication, allowing the prover to generate a single piece of evidence that the verifier could independently check.
This shift significantly broadened the potential applications of ZKPs, enabling their use in digital signatures, secure voting systems, and other areas where efficiency and scalability were paramount.
Formalization and Theoretical Advances
Concurrently, the period was characterized by the formalization of NIZKPs and an in-depth exploration of their theoretical underpinnings. Researchers dedicated efforts to delineate the mathematical and computational bases of NIZKPs, including the necessary assumptions for their construction and the conditions requisite for their secure application.
A notable concept that emerged during this phase was the “common reference string” (CRS), a critical element in some NIZKPs facilitating the construction of proofs by providing shared information between the prover and verifier.
Alongside theoretical advancements, the 1990s also witnessed endeavors to implement ZKPs in practical settings. This involved developing algorithms that were more efficient in generating and verifying proofs, thereby reducing the computational and storage demands.
However, this era also brought to light the limitations and challenges associated with ZKPs. Researchers grappled with issues related to the scalability of ZKP systems, the trade-offs between efficiency and security, and the complexities of implementing ZKPs in user-friendly and secure manners, particularly against evolving cybersecurity threats.
Emergence of zk-SNARKs’ Precursor Technologies
zk-SNARKs represent a breakthrough in the field of ZKPs, offering proofs that are both succinct (requiring very small amounts of data to be transmitted or stored) and non-interactive (eliminating the need for back-and-forth communication between the prover and verifier).
These properties make zk-SNARKs particularly well-suited for applications where bandwidth and computational resources are limited, and where privacy and security are paramount.
The path to zk-SNARKs involved several key innovations. One of the foundational elements was the use of cryptographic techniques such as homomorphic encryption and elliptic curve cryptography, which allowed for more efficient encoding and manipulation of data within proofs.
Another critical advancement was the development of new mathematical frameworks and algorithms that could support the construction of succinct and non-interactive proofs, such as the Quadratic Span Programs (QSPs) and Quadratic Arithmetic Programs (QAPs).
The Rise of zk-SNARKs, Bulletproofs, and Beyond
The term zk-SNARK was first introduced in the Bit+11 paper in 2011, heralding a new era for ZKPs.
Following this theoretical foundation, the development and application of ZKPs continued to evolve.
Development timeline
- 2011: Introduction of the term zk-SNARK in the Bit+11 paper.
- 2013: The Pinocchio paper (PHGR13) introduced refined protocols that use fewer cryptographic pairings and have smaller proof sizes compared to previous implementations, making the verification process more efficient.
- 2016: Introduction of the Groth16 algorithm, reducing computational complexity and improving efficiency of zk-SNARKs, establishing a widely-used standard.
- 2017: Introduction of Bulletproofs, a type of range proof that eliminates the need for a trusted setup, addressing a key security concern in zk-SNARKs.
- 2018: zk-STARKs introduced, providing scalability and post-quantum security without requiring a trusted setup.
- 2019: The PlonK paper presented a Universal Zero-Knowledge proof algorithm with a single trusted setup for multiple circuits or statements, enhancing the Groth16 algorithm.
By 2013, the Pinocchio paper demonstrated that zk-SNARKs could be used in real-world applications, marking a significant advancement. However, the technology was still limited by its computational complexity, making it impractical for widespread use.
The ZKP landscape changed dramatically in 2016 with the introduction of the Groth16 algorithm, which significantly reduced the computational complexity of zk-SNARKs, making them more efficient and setting a standard still in use today. This efficiency made it easier to integrate ZKPs into various applications, especially for secure and private transaction verification in blockchain technology.
The development of ZKPs did not stop with Groth16; the field continued to evolve rapidly with new innovations. In 2017, Bulletproofs were introduced, offering a type of range proof without a trusted setup, addressing security risks associated with such setups. In 2018, zk-STARKs were introduced, providing scalability, post-quantum security, and eliminating the need for a trusted setup.
The progression continued with the PlonK paper in 2019, introducing a Universal Zero-Knowledge proof algorithm that required only a single trusted setup for any number of circuits or statements, significantly improving upon the Groth16 algorithm’s limitations.
The Zcash Effect
The main surge of interest in zk technology within the blockchain space began when the Zcash founding team developed the first production-ready implementation of the zk-SNARK to support shielded/private transactions in the Zcash network.
Zcash, launched in October 2016, was the first widespread application of zk-SNARKs, providing a strong privacy guarantee by enabling fully encrypted transactions on the blockchain.
From that point onwards, there has been a constant surge in research into Zero-Knowledge Proofs (ZKPs) within the blockchain domain, primarily driven by the critical need to achieve privacy and scalability in blockchain systems without compromising decentralization. Researchers in the blockchain space have realized that ZKPs offer a promising solution to these challenges.
In part 2 of this article series, we’ll explore the latest technological breakthroughs, enhancements, and the practical implications of zk-technology’s utilization in blockchain systems, as well as the implications of these advancements for future blockchain-based systems.
Source:
- https://blog.lambdaclass.com/our-highly-subjective-view-on-the-history-of-zero-knowledge-proofs/
- https://medium.com/alliancedao/zkps-in-web-3-now-and-the-future-21b459348f29
- https://www.circularise.com/blogs/zero-knowledge-proofs-explained-in-3-examples
- https://z.cash/learn/what-are-zk-snarks/
- https://ijedr.org/papers/IJEDR2101020.pdf
- https://bitcoin.org/bitcoin.pdf
- https://eprint.iacr.org/2011/443.pdf
