Unlocking the Future with ProgCrypto

At Devconnect 2023, a revolutionary concept was spotlighted during the ProgCrypto event: Programmable Cryptography. This two-day gathering of researchers, developers, and community members focused on the future of cryptography and its potential to reshape digital interactions. Vitalik Buterin, in his opening keynote, emphasized Programmable Cryptography as a key concept in the d/acc vision. We worked with ZK and MPC in the past and now we want to find out how much further we can push the boundaries of those technologies.

What is Programmable Cryptography?

Programmable cryptography signifies a pivotal shift in the cryptographic landscape, moving from the traditional focus on encryption and signatures to a more advanced and versatile framework. This evolution marks the transition to a second generation of cryptography, where the tools at our disposal are no longer confined to specific functions but can be programmed to perform complex operations. The advent of general-purpose cryptographic compilers, such as ZK-SNARKs showcases this shift, offering a level of flexibility and security in digital communication and data operations previously unattainable. For instance, with digital signatures you can sign a document, but with ZK-SNARKS you can sign the execution of a computer program.

At its core, programmable cryptography transforms cryptographic processes from being restricted to single-function devices to resembling CPUs in their programmability, flexibility, and capacity to handle multifaceted operations with robust guarantees. This transformation expands the scope of cryptography beyond traditional goals of privacy and security, enabling a broader spectrum of digital interactions and computational processes without compromising on privacy and data ownership. Thus, programmable cryptography not only enhances existing cryptographic capabilities but also opens the door to innovative applications that leverage secure, private verification and computation in unprecedented ways.

However, there is no scientific definition for this concept. One way to describe it is to say Programmable Cryptography is the subset of privacy-enhancing technologies (PETs) that are based on cryptographic principles. Another way would be to say that it contains all cryptographic technologies that go beyond “first-generation” cryptography such as encryption and signatures. Either way it is used as an umbrella term for the combined capabilities of the following technologies Zero-Knowledge Proofs (ZK), Fully Homomorphic Encryption (FHE), Multi-Party Computation (MPC), Functional Encryption (FE), Attribute-Based Encryption (ABE), Identity-Based Encryption (IBE), witness encryption, and Indistinguishability Obfuscation (IO).

The Revolutionary Potential of Programmable Cryptography

To appreciate the necessity of Programmable Cryptography, one must consider the internet's evolution, as depicted in "Read, Write, Own" by Chris Dixon:

• The Read Era (1990-2005): Users primarily consumed content, exploring the vast expanses of information available online.
• The Read-Write Era (2006-2020): The emergence of social media and blogging platforms transformed consumers into creators, democratizing content production.
• The Read-Write-Own Era (2020+): A phase that merges the previous models to revolutionize network participation and ownership. This new era empowers individuals to have a stake in the internet's infrastructure, offering the chance for influence and economic benefits previously reserved for a narrow group of corporate stakeholders.

Blockchain technology, with its decentralized ethos, stands as the pillar of this new era. Yet, for blockchain to fulfill its promise of revolutionizing how we interact with digital worlds, Programmable Cryptography is indispensable. It ensures the privacy and security necessary for true digital ownership and innovation.

Let’s focus on ZK and MPC (viewing FHE as a specialized form of a two-party MPC protocol) for the rest of the blog post. The choice of these technologies is not arbitrary. Specifically, in numerous applications, such as decentralized exchanges (DEXs), the utility of ZK by itself falls short in safeguarding confidentiality against intermediaries — a cornerstone principle for decentralized finance (DeFi) and Web3 initiatives. The limitation of ZK lies in its inability to manage shared secrets effectively. However, when MPC is integrated with ZK, this challenge can be overcome. Moreover, MPC has achieved a level of maturity that makes it viable for immediate implementation, setting it apart from other emerging technologies like IO. This combination of ZK and MPC offers a robust solution for achieving the privacy and security goals central to the ethos of DeFi and Web3.

MPC turns existing blockchain networks into decentralized computers with privacy. Something Vitalik dubbed secret sharing DAOs back in 2014. The capabilities of Programmable Cryptography will enable builders to create applications and services where users are in full control of their own data without compromising on functionality. In an abstract sense, Programmable Cryptography let us create a virtual trusted third party which offers solutions to longstanding issues of privacy and trust in the digital domain. A few examples are:

• Privacy-Preserving Financial Transactions: Trustless dark pools and decentralized finance (DeFi) platforms can operate without revealing strategic trade information.
• Secure Biometric Applications: Biometric data can be used safely, ensuring user privacy while leveraging unique identifiers.
• Health Data Applications: Supporting private diagnostic services, using data from multiple providers without risking exposure to insurers, advertisers, or third parties.
• Confidential Computing: This concept enables the processing of sensitive data within a decentralized network, safeguarding personal and corporate data.
• Decentralized Matchmaking: From ride-sharing to dating, Programmable Cryptography allows to be match so that no one sees any information (including the services provider) about you unless there is a match.

The culmination of all this could enable DAOs for the democratic governance of AI, i.e. an on-chain DAO to oversee the criteria for submitting training data (including necessary attestations for the data), determine eligibility for making queries, the volume of queries permitted, and Programmable Cryptography to secure the entire AI creation and operation process, from each user's training input to the ultimate result of every query. This structure could also meet the widespread goal of rewarding individuals for their data contributions.

The Journey Ahead of Us

gubsheep categorized the development of programmability into four distinct stages: theoretical feasibility, circuit language, program-to-circuit compilers, and virtual machines (VMs).

A decade ago, MPC was ahead of ZK. However, the landscape shifted dramatically over the past 5-7 years due to substantial investments in ZK technology, leading to groundbreaking advancements (think about zkVMs recently). These developments indicate that ZK is now transitioning into the last stage of its evolution. In contrast, MPC currently lags by approximately one stage.

Looking ahead, we anticipate that MPC will undergo a similar evolution to ZK over the next five years, progressing through the following stages:

1. Tailored implementations for specific, large-scale applications (MPC setup ceremonies for SNARKS, MPC Wallets, etc.).
2. Development of an "MPC-engine": A critical intermediary step involves the creation of domain-specific languages (DSLs) that compile into a specialized intermediary representation (IR) or circuit. This IR or circuit is then executed by an MPC engine, which, while not a full-fledged VM, offers general-purpose capabilities. This approach effectively circumvents challenges associated with dynamic memory access, and the management of arbitrary loops and branches.
3. The establishment of a comprehensive MPC VM capable of executing code, for instance, compiled from Rust. Addressing memory management in this context is crucial and currently imposes significant overhead. However, this area is ripe for innovation, with major advancements anticipated from ongoing research.

There is no Free Lunch

Discussing the trade-offs of security and privacy, it's acknowledged that these features inherently come with additional costs, and currently, ZK and MPC may appear prohibitively expensive. However, the perception of affordability is dynamic. Reflecting on the past three decades, we've willingly accepted 1000x in computational overhead for the sake of simplified software development. It's conceivable that we might similarly embrace such overheads for better security and privacy guarantees.

The question of whether we're approaching 1000x overhead with these technologies is nuanced. Delving into ZK, Wei Dai's presentation, "The Cost of Verifiability" at Devconnect, provides invaluable insights. Dai suggests, albeit with caution, that today we're looking at an approximate 10000x overhead for end-to-end system circuits, and two orders of magnitude more for zkVMs. Thus, achieving a 1000x overhead, particularly with advancements like dedicated ZK hardware, appears within reach.

In the domain of MPC, a parallel comprehensive analysis is less common, compounded by the diversity of use cases and the complexities inherent in varying configurations (such as the number of participants, security models, trust assumptions, bandwidth requirements, etc.). Yet, there are specific applications and protocols that show immense promise. For instance, collaborative SNARKs — effectively conducting MPC over a ZK proof system — demonstrate performance on par with a single prover and require only 3x the workload. Our own endeavors in developing an efficient MPC protocol for conducting iris code membership checks within a shared database suggest that overheads can be as low as 25x or even better. While introducing programmability to MPC, much like with ZK, still incurs considerable overhead, the numbers are promising.

Conclusion

The implications of Programmable Cryptography extend far beyond technical enhancements. They touch upon the very fabric of digital interaction, ownership, and governance. As we envision a future where democratic governance of AI and data privacy are paramount, Programmable Cryptography stands as a key enabler, promising a more secure, private, and equitable digital world.

The dialogue initiated at Devconnect is just the beginning. As we delve deeper into the possibilities afforded by Programmable Cryptography, we not only anticipate a shift in how digital services are delivered and consumed but also how individuals engage with and contribute to the digital commons. The journey is as ambitious as it is critical, paving the way for a new era of digital enlightenment.