Team Wizkit (WIde-scale Zero Knowledge Interpreter Toolkit) – an effort led by Stealth in collaboration with Ligero, Inc.; Northwestern University; Texas A&M University; and University of Vermont – was formed in response to DARPA’s Securing Information for Encrypted Verification and Evaluation (SIEVE) program, which seeks to develop zero-knowledge proofs (ZK proofs) for DoD scale applications.
ZK proofs refer to a cryptographic technology that enables one party — the “Prover” — to prove some fact to another party — the “Verifier” — using knowledge that will remain hidden from the Verifier. In a simple example, a web server may want to minimize its risk from poorly chosen passwords (“god”, “dogs”, “password”, “123”, and the like). Although the server can recognize an incorrect password, it doesn’t know (or want to learn) the password. Instead, it could ask each of its users to prove that their password is not contained in a list of common insecure passwords. In the past, specialized ZK proofs have been developed specifically for applications to distributed ledgers; however, the technology has broad applications far beyond cryptocurrencies or blockchain technologies more generally. The SIEVE program seeks to advance the state of the art in ZK proofs to enable complex, DoD-relevant applications.
Properties that ZK applications could provide include:
- Confidentiality: A party can prove something without revealing their hidden knowledge
- Authenticity: Prove not just that a document was created by a particular originator but through a particular process
- Transparency: An organization can prove adherence to procedures or regulations without revealing specifics
- Verified computing: Assure that a computation was performed to specification
Wizkit is developing specialized ZK tools for several key applications, including:
- ZK for machine learning and AI
- Private application of the Gale–Shapley algorithm for the stable matching problem
- ZK for smart code signatures
Sample Application: Compliance and Transparency
With ZK, improving personal, corporate, and government transparency could be possible without undesirable revelation of knowledge that should remain confidential. For example, ZK allows you to prove compliance (within some level of confidence), while still allowing you to hide whatever “it” happens to be. Wizkit has already demonstrated the ability to prove classification of sensitive data under a public convolutional neural network (CNN) model (or vice versa, with public data and a private CNN model). This could enable an individual to prove, for example, that an encrypted message complies with a network’s terms of service without compromising the privacy of the message. We are currently working on the ability to prove acceptability of non-discrimination and fairness metrics applied to sensitive ML models. Doing so could help enable watchdog organizations to hold both public agencies and private-sector organizations to account.
Sample Application: Smart Code Signatures
At present, a code signature attests only to the originator of a software binary and relies on their reputation and trustworthiness. In the future, ZK could be used to attest to additional security properties, such as inclusion or exclusion of specific dependencies, a clean static-analysis report, or even invulnerability to a particular exploit … and all this while remaining entirely closed-source.
The SIEVE program, and consequently Team Wizkit, is structured as a pipeline from users and developers through frontends and compilers (the program’s Technical Area 1) which produce statements using a common Intermediate Representation (IR), and ultimately into backend ZK proof systems (Technical Area 2). Since ZK naturally involves some computation, the first step in the process is for a developer to write a program that is compiled for ZK to ingest. All SIEVE TA1 frontends are expected to produce statements using the SIEVE IR – a joint deliverable of all teams. The TA2 backends may then ingest the IR, enabling one party to prove a statement to another.
Team Wizkit’s WizPL framework allows users to write high-level programs and easily turn these programs into zero-knowledge proofs. Specifically, WizPL provides:
- Haskell-like and Python-like general-purpose programming languages
- Compilers that transform programs written in these languages into ZK statements that are ingested by ZK proof systems
The SIEVE IR
A unique aspect of the SIEVE Program is that all performers must agree to a common program-wide Intermediate Representation (IR). This should allow any SIEVE-developed frontend technology to interconnect with any backend. The SIEVE IR is based upon arithmetic circuits but adds features for repetition and reuse. The Wizkit team has participated heavily in the development of both the SIEVE IR and tools for ingesting it. To learn more, check out the SIEVE IR tag on our blog or download a copy of the IR Specification.
WizToolKit is a C++ library and a collection of command line tools for working with the SIEVE IR. It is geared toward consuming and processing the IR; however, it can also help in testing and debugging IR statements. WizToolKit provides the following capabilities:
- Reading/parsing libraries for backends to ingest all forms of the IR
- The BOLT interpreter library for easily and performantly bridging ZK backends with the IR
- Tools for testing and debugging IR statements in the non-ZK setting
ZK Proof Systems
ZK Proof systems, or colloquially “backends”, do the sophisticated mathematics required to prove facts while hiding data.
Line Point Zero Knowledge
Line Point Zero Knowledge (LPZK) is a Zero Knowledge proof system built by Stealth using Vector Oblivious Linear Evaluation (VOLE) technology. LPZK is a concretely efficient designated-verifier proof system. It can process 20 million multiplication gates per second over a 61-bit prime field, and it requires only one field element of communication per gate, which can be reduced to one-half field elements with the use of more complex correlated randomness technology. LPZK has also contributed to theoretical advances in other areas of cryptographic research.
Other ZK Proof Systems
This material is based upon work done in collaboration with Ligero Inc., Northwestern University, Texas A&M University, the University of Michigan, and the University of Vermont; and was supported by DARPA under Contract No. HR001120C0087, Distribution Statement A: “Approved for Public Release, Distribution Unlimited. If you have any questions, please contact the Public Release Center”. The views, opinions and/or findings expressed are those of the author and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government.