Private delegated computation is here, and there will be bugs!
What is this new and exciting cryptography field called zero-knowledge cryptography? How is it related to trusted and confidential computing, and why do we need to rethink security because of it? This is what you’ll learn in this article. But first, who are we? We’re three cofounders: David, ex-Facebook security lead at Libra/Diem and author of the Real-World Cryptography book; Brandon, founding engineer of the Mina blockchain and ex-Pinterest/Facebook; and Gregor, tech lead of zero-knowledge framework SnarkyJS, and one of the winners of the largest zk competition ZPrize.
Where it all began
Let’s start with some humble beginnings. Back then, people mostly wanted to encrypt to one another. It was Alice encrypting to Bob, and then Bob encrypting to Alice. Pretty simple stuff in retrospect.
Things quickly evolved, and we ended up with new situations that Alice and Bob hadn’t seen before. To keep with the metaphor, Alice is now in jail and she either can’t be trusted with her stuff or needs the help of someone on the outside.
To make sense of that, we can look at the plethora of devices and protocols that were invented in recent years. You might have heard of trusted computing, or confidential computing. If you have, well forget about all of these keywords because they’re all unnecessary confusing. If you haven’t, then you’re in luck because you’re about to learn some cool nomenclature.
At some point in the history of technology, some companies realized that they couldn’t trust normal people (like Alice) with their secrets. They’d lose their credit cards, or misplace their phones, or worse they’d try to hack their TV box to watch Friends for free. Solutions had to be put in place to handle secrets in “untrusted” environments. Two branches of cryptography were born: hardware cryptography and whitebox cryptography.
Hardware cryptography consisted of little chips called “secure elements”. They looked like (warning: unnecessary buzzwords):
The smart cards in your banking cards and SIM cards.
The “trusted platform modules” (TPMs) in our modern laptops and the “secure enclaves” in our modern smartphones.
The “hardware security modules” (HSMs) in big companies and banks’ data centers, or the “trusted execution environments” (TEEs) in enterprise servers.
These hardware solutions all have one major goal: prevent someone with physical access from observing the secrets they control.
Whitebox cryptography on the other hand was a pure software solution and failed miserably. The idea was to mingle the software and the keys together in such a way that nobody could look at the code and extract the secrets. Nobody could find a way to provide secure constructions, and the products sold and bought by security companies were mostly based on non-cryptographic concepts like obfuscation and security through obscurity.
I call this private computing, but people today like to call this kind of technology “trusted computing” or “confidential computing”. It’s all mumbo jumbo though, the point really is that you don’t want the secrets to get out and you’re adding an additional layer of security in case your device gets compromised.
Private computing today is mostly boring from a pure cryptography standpoint because most solutions involve hardware and aim for what we call “good enough”. In their parlance they say “it would cost X amount of dollars for the attackers” as opposed to the “it would take billions of years to run the attack” we are used to in cryptography.
Now we’re entering the realm of what is interesting to us in this article. Delegated computing is when Alice wants to compute something but she doesn’t have the resources to do so. She needs to ask someone else to do it for her, she needs to “outsource” the computation.
Delegated computing is also split into two branches in cryptography, one providing hardware solutions and the other one providing strong cryptographic algorithms.
The hardware solutions are still called “trusted computing” or “confidential computing” though, because at some point we realized that we could reuse the hardware designed for private computing in order to also provide delegated computing.
The most famous hardware solution available is Intel SGX, which provides “remote attestation” on computation’s results. Basically, a signature of a hash of the software that was run on the hardware, the inputs that were used, and the output of the computation. The signature is created using a unique blessed-by-Intel key that was integrated within the chip during manufacturing.
On the other hand, the up-and-coming software solutions are general-purpose zero-knowledge proofs (ZKPs). Although in this case, we do not care too much about the “zero-knowledge” part (which will come later).
general-purpose ZKPs are a cryptographic primitive that allows you to create proofs of executions of programs. These proofs are claims that can be shared, similar to signatures. If signatures are claims that “whoever controls that public key signed this data”, ZKPs are claims that “if you run this program with these inputs, you’ll get these outputs”.
It was known for a while that you could do this, but it is only in the last few years that these protocols have become practical. So practical that entire cryptocurrencies (which appear to be the first users for this technology) run on this stuff, managing to rely on proofs to avoid having all users recompute the full history of state transitions (which usually are all the transactions that happened since genesis, or all of the “smart contracts” executions that happened since genesis).
Finally we come to the last term I want to coin, private delegated computing, which is delegated computing that involves secrets.
In this model, not only can someone produce a proof claiming that executing such program with such input gives you such output, they can also “hide” some of the inputs. In such a model, we distinguish public and private inputs, where the public inputs are part of the claim, and the private inputs are not.
The classical example is that you might want to prove that you know the solution of a sudoku grid, without revealing the solution. Thus, with your favorite private delegated computing solution you create a proof or claim that you ran a known sudoku solver, and that it returned true. In this case, the sudoku grid is the public input, and the solution is the private input.
Zero-knowledge proofs (and this is where the zero-knowledge part becomes important) provide a strong cryptographic solution to private delegated computing.
Hardware solutions like SGX and HSMs also provide these, with upsides and downsides. The upside is that the keys supposedly never leave the “enclave”, even when physically observed (and sometimes even physically tampered) by an attacker. The downsides is these can be costly, non-user friendly, and that in practice many attacks are being found.
Again, these solutions are usually referred to as “trusted computing” and “confidential computing” (when they involve hardware at least) and this is why I think these terms are generally not useful.
Zero-knowledge cryptography, there will be bugs
We’ve established that in recent years, general-purpose ZKPs have unlocked a purely cryptographic approach to “private delegated computing”. We should note that the complexity of the logic that can be proved via a ZKP is somewhat limited at the moment. Limited in a way that’s been a non-issue for many applications in blockchain, but that could be an issue for more complex blockchain or non-blockchain applications. The field is currently booming with breakthroughs happening every year, oddly similar to the mega/gigahertz wars of the CPUs that happened not so long ago.
Programming for ZKPs is a new paradigm, and with it comes new challenges and types of bugs that developers can create. We’ve seen this in the past with the advent of smart contracts, followed by billions of dollars being lost due to all sorts of bugs. More than 5 years ago we were part in releasing the Decentralized Application Security Project (or DASP) Top 10, proving our continuous historical engagement in the security of these new technological shifts.
So today, we’d like to announce the founding of zksecurity.xyz, the first security consultancy focused on zero-knowledge proof technology, and the next step in our pursuit of keeping up with where the technology and bugs are moving to.
Contact us at [email protected] if you’re interested in an audit for ZK-related software, and stay tuned for more stories about our journey into ZK security on this blog.