When I first heard about ProgCrypto (Programmable Cryptography) during Devconnect 2023, I was drawn to see how this simple term encompasses so many different kinds of cryptography techniques. As I read 0xPARC’s ProgCrypto book, I got a peek at how some of these protocols work at their most fundamental level.
In this post, I describe what ProgCrypto is and what it means to me. I will give you a taste of it by describing multi-party computation, one of the cryptography techniques as part of ProgCrypto. If you want to dive in to the details, read the book and run the Jupyter notebooks that I created to see the algorithms in action.
Table of Contents
So what is ProgCrypto?
We want cryptography that can be “programmed” to work on arbitrary problems and functions, rather than designing protocols on a per-problem or per-function basis.
Traditionally, cryptographic protocols have been about solving specific problems. When the problem changes, new cryptographic protocols would have to be developed. But in the last decade or two, a lot of research has been done on how cryptographic protocols can be better implemented. We are now seeing many protocols being able to solve more generalized problems, thus increasing the protocol’s robustness and reusability.
An Example: DSL vs zkVM
Let me give you an example. A few years ago, many projects were developing zero-knowledge Ethereum Virtual Machine (zkEVM) as a layer-2 scaling solution for Ethereum. The idea behind zkEVM is to increase transaction throughput while reducing costs by processing transactions off-chain and submitting them to the mainnet with proof.
DSLs are like custom-built cars — fast but hard to fix. zkVMs are like standard engines — versatile and easier to tune.”
These projects mainly used highly specialized Domain-Specific Languages (DSLs) to create arithmetic circuits. These DSL programs are not only complex to write but also easy to make mistakes and introduce security flaws. In addition, every time there is an Ethereum upgrade, these DSL programs will need to be updated, and the projects have to go through the same error-prone process. As these zkEVMs are written by cryptographers and cryptography engineers, the cost of maintaining them is very high.
Recently, we are seeing some of these projects starting to replace their DSL implementation with one that is written in a higher-level language like Rust (e.g. Scroll migrating to OpenVM). These Rust programs are run in a zero-knowledge Virtual Machine (zkVM) along with Ethereum transactions, which will produce a proof just like zkEVM would.
zkEVM vs zkVM: A zkVM is a generalization of a zkEVM. While zkEVM can only execute smart contracts on the Ethereum network and produce proof of its correct execution, a zkVM can execute any program within its framework and produce corresponding proof.
When using a more high-level language like Rust, it becomes much easier to maintain the program as one can now use all the developer tools and libraries that accompany a more common language when compared to a specialized DSL. Think of the number of Rust developers one can hire versus the few developers who are specialized in the DSL that was used.
While the jury is still out on whether zkVM can completely replace cryptographic DSL, we can all see the benefits that generic cryptographic protocols can bring.
Multi-party Computation
Besides ZK, the book introduced a few other topics related to cryptography. One of the chapters that caught my attention was Two-party Computation (2PC). It presented a basic implementation of how 2PC works by combining garbled circuit and oblivious transfer (OT).
While the idea behind garbled circuits and OT are straightforward to understand, their ingenious combination that allows for MPC is what makes it so interesting. Let me give you a brief overview of how it works.
Yao’s Garbled Circuit
Andrew Yao introduced garbled circuits in 1986 (paper) as a means to allow two or more parties to jointly compute a function over their private data. A classic example of how this applies is the famous millionaires’ problem.
To see how it works, imagine a circuit of logic gates (AND, OR, etc.) representing the function to compute. A garbled circuit is just a bunch of garbled gates connected to each other. Yao’s trick “garbles” this circuit: each wire gets encrypted labels, and each gate’s truth table is scrambled into a ciphertext table. One party (the garbler) prepares this and sends it to the other party (the evaluator). Once the evaluator computes the output using its private input and the garbled circuit, the output is revealed to both parties by design.
However, for this protocol to work, there are two more issues that need to be solved:
- the garbler does not learn which input the evaluator used to compute the output
- the evaluator should only get the output corresponding to its input
We can use OT to resolve both of these.
Oblivious Transfer
Oblivious Transfer was first invented by Michael O. Rabin in 1981 (paper). The 1-out-of-$n$ OT described here builds on Rabin’s idea, refined by Even et al. in 1985 (paper).
Its primary purpose is to allow the receiver to obtain one secret value from a set of secret values given by the sender without the sender knowing which value the receiver obtained. A simple implementation of this protocol is illustrated in the book (Section 2.2.3 OT in one step). Firstly, the order of the messages is agreed upon beforehand. The evaluator sends a list of public keys, but only knows the secret key to one of them. The garbler then encrypts all the messages with the evaluator’s given public keys in order. The garbler doesn’t know which public key the evaluator knows the secret key of. It just knows all the public keys look legit. The garbler then sends all the encrypted message back to the evaluator who can now decrypt the one message that it knows the secret key to.
In the context of the garbled circuit, the evaluator uses oblivious transfer to send its inputs to the garbler and get back the labels. The evaluator can now use the labels to calculate the output in the garbled circuit. During this process, the garbler does not learn anything about the evaluator’s input, and the evaluator does not learn anything about the other input labels.
Conclusion
Garbled circuits allows for trustless multi-party computation without relying on a trusted third party to perform the computation and to keep each party’s inputs private. While MPC implementations in the real world are much more optimized, the example given in the book illustrates the core idea and allows one to understand its applications.
To fully understand how the protocol above works, remember to check out my Jupyter notebooks.