We are releasing Winterfell, our implementation of a STARK prover/verifier to Crates.io
Winterfell is an easy to use open source implementation of STARKs for security and privacy applications.
One potential application for Winterfell’s zero-knowledge proofs is blockchain privacy and scalability.
“Any sufficiently advanced technology is indistinguishable from magic.” —Clarke’s Third Law
What if the average developer could benefit from proofs of computational integrity (CI) that would normally require an in-depth knowledge of cryptography to implement?
CI proofs, of which zero-knowledge proofs (ZKPs) are a subset, are a cryptographic technology that let you do seemingly impossible things. For example, you can run a computation and get some result. You can then use a CI proof to convince anyone that you did the computation correctly without their having to rerun the computation themselves. And they can verify this correctness in just a few milliseconds, regardless of how complex or long-running the original computation was. To bring the power of CI proofs to the masses, we’ve developed Winterfell, a general-purpose STARK (Scalable Transparent Arguments of Knowledge) prover and verifier. We are happy to be publishing the v0.1 version of the library to crates.io.
Another important property of these CI proofs is the ability to hide some (or all) of the inputs that were used to run the computation. This is the zero-knowledge aspect. For example, you could prove that a number is in a given range without revealing the exact value of the number (these types of proofs are usually called range proofs). Or, you could do something as complex as comparing two number sequences, one public and one private (known only to yourself), and prove to anyone beyond a doubt that there is or isn’t a match between them.
The magic of ZKPs
The general ideas behind ZKPs were developed as early as the 1980s, but interest in this area of cryptography has exploded recently, driven in part by emergent applications in the blockchain space. In the last few years, over a dozen new proving systems have appeared. Some of them have even been deployed in production where tens of billions of dollars depend on their security properties. However, ZKPs are far from mainstream, primarily for two reasons:
Until recently, deploying ZKPs in applications required expert cryptographers with years of experience. The situation is somewhat better now, as there are plenty of relatively accessible materials available and more projects that try to make ZKPs accessible to the average developer. But even now, making sense of different proving systems and the trade-offs associated with them requires deep expertise and/or a steep learning curve, even for experienced software engineers.
While verifying a ZK proof is extremely fast and requires very few compute resources, generating a proof is a computationally intensive process. It may take seconds or even minutes (or many CPU cores) to generate proofs for even relatively simple computations. Only relatively recent advances in cryptography and implementation improvements have brought a large segment of computations to within practical feasibility for ZKPs. And there is a lot of ongoing work to expand the set of computations for which proof generation is practical.
We developed Winterfell to bridge these gaps and to bring ZKPs within reach of regular developers.
Winterfell is here
Winterfell is a general purpose STARK prover and verifier written in Rust at Novi Research. General purpose means that Winterfell can generate CI proofs for any computation. Basically, for any program that can be described with a Turing-complete language, we can generate a CI proof using Winterfell (though this would be much more straightforward for some programs than for others).
Winterfell uses STARKs, a proof-of-computation scheme developed by Eli Ben-Sasson, Michael Riabzev, et al. In comparison with many other CI proving systems, STARKs have a number of attractive properties, including:
STARKs rely on very few cryptographic assumptions. In fact, the only cryptographic primitive we need for STARKs to work is a collision resistant hash function (e.g., SHA256). This also makes STARKs resistant to potential attacks from adversaries with quantum computers.
Unlike many other proving systems, STARKs are fully transparent. This means we don’t need to run complicated trusted setup ceremonies to start using STARKs. Trusted setups are a potential security weakness in other zero knowledge protocols, because a compromised trusted setup allows attackers to generate fake CI proofs. STARKs are immune to this.
In comparison with other systems, STARK proof generation is extremely fast when we deal with uniform computations, or computations with regular structures. Fortunately, the vast majority of programs people write do possess such regular structures. Moreover, pretty much every single step of the STARK proof generation process is massively parallelizable. Thus, we can frequently speed up proof generation by distributing it across more and more CPU cores.
None of the individual properties listed above are unique to STARKs. However, no other proving system combines lean cryptography, transparency, and performance to the extent STARKs do. Winterfell takes full advantage of these benefits while abstracting away most of the complexity. For example, proof generation can be distributed across multiple CPU cores to dramatically reduce proof generation time (see our benchmarks here). Moreover, we have plans to enable fully distributed proof generation across multiple machines and have already started work in this direction.
In addition to being performant, Winterfell is highly configurable. That is, you can dynamically tune almost all parameters of the STARK protocol to attain specific performance and security targets. We are able to achieve such high configurability without sacrificing performance or code clarity by relying on Rust’s zero-cost abstractions.
Last, and perhaps most important, you don’t need to be a cryptographer to use Winterfell. As mentioned previously, Winterfell abstracts away most of the complexity of the STARK protocol. The only thing the user is responsible for is describing their computation in a format that the STARK prover/verifier can understand. This format is called algebraic intermediate representation (AIR), and the step of translating a program into AIR is called arithmetization.
Using Winterfell
Winterfell exposes a relatively simple interface for describing AIR for any computation. However, the concept of arithmetization is not something most developers are familiar with, so there is going to be a learning curve.
To help you get started, we’ve put together an end-to-end tutorial on how to define AIR for a very simple computation. We also have examples of more interesting computations in the examples crate, ranging from something as simple as a Fibonacci sequence to something as sophisticated as aggregation of hash-based signatures. And if you would like to get a little bit deeper into theory, we recommend reading two excellent blog posts from StarkWare: Arithmetization I and Arithmetization II.
Once you are comfortable with writing AIRs, using Winterfell to generate STARK proofs becomes relatively easy. For example, AIR for a Fibonacci sequence requires less than 100 lines of code and can be put together in about 15 minutes. Even for the relatively complicated example of hash-based signature aggregation mentioned above, the AIR is described in about 600 lines of code (though it did take several days to put together).
Another point worth mentioning: We wrote Winterfell as a set of modular crates, all of which are being published to Crates.io today as well. While we use these crates to build a STARK proving system, many of them are general enough to be used as building blocks in other CI proving systems. For example, for low-degree testing, we use the FRI protocol implemented in the winter-fri crate, which is also used as a building block for several other proof systems (e.g., Fractal and Aurora) that aim to be transparent and post-quantum. Thus, we hope that our work will help implementers of these protocols get their job done more quickly and efficiently.
Applications
Recent advancements in ZKPs are driven by emergent use cases in the blockchain space. Specifically, ZKPs offer attractive solutions to perhaps two of the most pressing blockchain challenges: privacy and scalability. However, ZKPs have numerous potential applications outside of the blockchain space as well.
While there still remain some technical challenges to overcome before proofs of computational integrity can be considered practical at a large scale, we believe that Winterfell represents an important stepping stone for bringing a well-studied subject in academic research into practical deployments. And we hope that the security and privacy community will also benefit from an easy to use open source implementation of STARKs.
Please check out the Winterfell repository, and feel free to open issues for comment and leave feedback!
The post Open sourcing Winterfell: A STARK prover and verifier appeared first on Facebook Engineering.