{"id":341,"date":"2021-08-31T14:39:28","date_gmt":"2021-08-31T14:39:28","guid":{"rendered":"https:\/\/fde.cat\/?p=341"},"modified":"2021-08-31T14:39:28","modified_gmt":"2021-08-31T14:39:28","slug":"open-sourcing-winterfell-a-stark-prover-and-verifier","status":"publish","type":"post","link":"https:\/\/fde.cat\/index.php\/2021\/08\/31\/open-sourcing-winterfell-a-stark-prover-and-verifier\/","title":{"rendered":"Open sourcing Winterfell: A STARK prover and verifier"},"content":{"rendered":"

We are releasing Winterfell, our implementation of a STARK prover\/verifier to Crates.io\u00a0<\/span>
\nWinterfell is an easy to use open source implementation of STARKs for security and privacy applications.<\/span>
\nOne potential application for Winterfell\u2019s zero-knowledge proofs is blockchain privacy and scalability.\u00a0<\/span><\/p>\n

\u201cAny sufficiently advanced technology is indistinguishable from magic.\u201d \u2014Clarke\u2019s Third Law<\/span><\/p>\n

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?\u00a0<\/span><\/p>\n

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.<\/span> And they can verify this correctness in just a few milliseconds, regardless of how complex or long-running the original computation was.<\/span> To bring the power of CI proofs to the masses, we\u2019ve 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.<\/span><\/p>\n<\/p>\n

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\u2019t a match between them.<\/span><\/p>\n

The magic of ZKPs<\/span><\/h2>\n

The general ideas behind ZKPs were developed as early as the 1980s, but interest in this area of cryptography has <\/span>exploded<\/span><\/a> 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:<\/span><\/p>\n

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.<\/span>
\nWhile 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.<\/span><\/p>\n

We developed Winterfell to bridge these gaps and to bring ZKPs within reach of regular developers.\u00a0<\/span><\/p>\n

Winterfell is here<\/span><\/h2>\n

Winterfell is a general purpose STARK prover and verifier written in <\/span>Rust<\/span><\/a> at <\/span>Novi Research<\/span><\/a>. <\/span>General purpose<\/span> 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).<\/span><\/p>\n

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:<\/span><\/p>\n

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.<\/span>
\nUnlike many other proving systems, STARKs are fully transparent. This means we don\u2019t 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.<\/span>
\nIn 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.<\/span><\/p>\n

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 <\/span>here<\/span><\/a>). Moreover, we have plans to enable fully distributed proof generation across multiple machines and have already started work in this direction.<\/span><\/p>\n

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\u2019s zero-cost abstractions.<\/span><\/p>\n

Last, and perhaps most important, you don\u2019t 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.<\/span><\/p>\n<\/p>\n

Using Winterfell<\/span><\/h2>\n

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.\u00a0<\/span><\/p>\n

To help you get started, we\u2019ve put together an end-to-end <\/span>tutorial<\/span><\/a> on how to define AIR for a very simple computation. We also have examples of more interesting computations in the <\/span>examples crate<\/span><\/a>, 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: <\/span>Arithmetization I<\/span><\/a> and <\/span>Arithmetization II<\/span><\/a>.<\/span><\/p>\n

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).<\/span><\/p>\n

Another point worth mentioning: We wrote Winterfell as a set of modular crates, all of which are being published to Crates.io<\/a> 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 <\/span>winter-fri<\/span><\/a> crate, which is also used as a building block for several other proof systems (e.g., <\/span>Fractal<\/span><\/a> and <\/span>Aurora<\/span><\/a>) 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.<\/span><\/p>\n

Applications<\/span><\/h2>\n

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.<\/span><\/p>\n

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.<\/span><\/p>\n

Please check out the <\/span>Winterfell repository<\/span><\/a>, and feel free to open issues for comment and leave feedback!<\/span><\/p>\n

The post Open sourcing Winterfell: A STARK prover and verifier<\/a> appeared first on Facebook Engineering<\/a>.<\/p>\n

Read More<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

We are releasing Winterfell, our implementation of a STARK prover\/verifier to Crates.io\u00a0 Winterfell is an easy to use open source implementation of STARKs for security and privacy applications. One potential application for Winterfell\u2019s zero-knowledge proofs is blockchain privacy and scalability.\u00a0 \u201cAny sufficiently advanced technology is indistinguishable from magic.\u201d \u2014Clarke\u2019s Third Law What if the average… Continue reading Open sourcing Winterfell: A STARK prover and verifier<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"spay_email":"","footnotes":""},"categories":[7],"tags":[],"class_list":["post-341","post","type-post","status-publish","format-standard","hentry","category-technology","entry"],"jetpack_featured_media_url":"","jetpack-related-posts":[{"id":701,"url":"https:\/\/fde.cat\/index.php\/2023\/04\/13\/deploying-key-transparency-at-whatsapp\/","url_meta":{"origin":341,"position":0},"title":"Deploying key transparency at WhatsApp","date":"April 13, 2023","format":false,"excerpt":"WhatsApp has launched a new cryptographic security feature to automatically verify a secured connection based on key transparency.\u00a0 The feature requires no additional actions or steps from users and helps ensure that a conversation is secure.\u00a0 Key transparency solutions help strengthen the guarantee that end-to-end encryption provides to private, personal\u2026","rel":"","context":"In "Technology"","img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":626,"url":"https:\/\/fde.cat\/index.php\/2022\/08\/31\/introducing-velox-an-open-source-unified-execution-engine\/","url_meta":{"origin":341,"position":1},"title":"Introducing Velox: An open source unified execution engine","date":"August 31, 2022","format":false,"excerpt":"Meta is introducing Velox, an open source unified execution engine aimed at accelerating data management systems and streamlining their development. Velox is under active development. Experimental results from our paper published at the International Conference on Very Large Data Bases (VLDB) 2022 show how Velox improves efficiency and consistency in\u2026","rel":"","context":"In "Technology"","img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":553,"url":"https:\/\/fde.cat\/index.php\/2022\/03\/15\/eflow-racing-towards-millions-of-ml-flows\/","url_meta":{"origin":341,"position":2},"title":"EFlow\u200a\u2014\u200aRacing towards millions of ML flows","date":"March 15, 2022","format":false,"excerpt":"EFlow\u200a\u2014\u200aRacing towards millions of ML\u00a0flows Salesforce Einstein operates many machine learning applications that cater to a variety of use cases inside Salesforce\u200a\u2014\u200avision and language, but also classic machine learning (ML) approaches using tabular data to classify customer cases, score leads, and more. We also offer many of these ML solutions\u2026","rel":"","context":"In "Technology"","img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":583,"url":"https:\/\/fde.cat\/index.php\/2022\/03\/15\/eflow-racing-towards-millions-of-ml-flows-2\/","url_meta":{"origin":341,"position":3},"title":"EFlow\u200a\u2014\u200aRacing towards millions of ML flows","date":"March 15, 2022","format":false,"excerpt":"Salesforce Einstein\u00a0operates many machine learning applications that cater to a variety of use cases inside Salesforce \u2014 vision and language, but also classic machine learning (ML) approaches using tabular data to classify customer cases, score leads, and more. We also offer many of these ML solutions and applications to our\u2026","rel":"","context":"In "Technology"","img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":275,"url":"https:\/\/fde.cat\/index.php\/2021\/08\/31\/mitigating-the-effects-of-silent-data-corruption-at-scale\/","url_meta":{"origin":341,"position":4},"title":"Mitigating the effects of silent data corruption at scale","date":"August 31, 2021","format":false,"excerpt":"What the research is:\u00a0 Silent data corruption, or data errors that go undetected by the larger system, is a widespread problem for large-scale infrastructure systems. This type of corruption can propagate across the stack and manifest as application-level problems. It can also result in data loss and require months to\u2026","rel":"","context":"In "Technology"","img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":743,"url":"https:\/\/fde.cat\/index.php\/2023\/08\/08\/how-meta-is-improving-password-security-and-preserving-privacy\/","url_meta":{"origin":341,"position":5},"title":"How Meta is improving password security and preserving privacy","date":"August 8, 2023","format":false,"excerpt":"Meta is developing new privacy-enhancing technologies (PETs) to innovate and solve problems with less data. These technologies enable teams to build and launch privacy-enhanced products in a way that\u2019s verifiable and safeguards user data. Using state-of-the-art cryptographic techniques, we have developed Private Data Lookup (PDL) that allows users to privately\u2026","rel":"","context":"In "Technology"","img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"_links":{"self":[{"href":"https:\/\/fde.cat\/index.php\/wp-json\/wp\/v2\/posts\/341","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/fde.cat\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/fde.cat\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/fde.cat\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/fde.cat\/index.php\/wp-json\/wp\/v2\/comments?post=341"}],"version-history":[{"count":1,"href":"https:\/\/fde.cat\/index.php\/wp-json\/wp\/v2\/posts\/341\/revisions"}],"predecessor-version":[{"id":369,"href":"https:\/\/fde.cat\/index.php\/wp-json\/wp\/v2\/posts\/341\/revisions\/369"}],"wp:attachment":[{"href":"https:\/\/fde.cat\/index.php\/wp-json\/wp\/v2\/media?parent=341"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fde.cat\/index.php\/wp-json\/wp\/v2\/categories?post=341"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fde.cat\/index.php\/wp-json\/wp\/v2\/tags?post=341"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}