OpenZKP
OpenZKP - pure Rust implementations of Zero-Knowledge Proof systems.
Overview
Project current implements
-
🐺 the Stark protocol (see its readme for details)
and has
-
🌞 a simple interface (see the example below), -
🗜️ succinct proofs, -
🏎️ decent performance, and -
🌐 webassembly support.
That being said, it also has a number of limitations, it has
- no high-level language,
- no comprehensive security audit,
- no perfect zero-knowledge,
- hard-coded field and hash function,
and some others, see features and limitations below for details.
Packages
| Package | Version | Description |
|---|---|---|
utils/ |
||
criterion-utils |
 |
Criterion helpers to benchmark over size and number of processors. |
error-utils |
 |
Assertion like macros for returning Result::Err. |
logging-allocator |
 |
Wrapper around the system allocator that logs large allocations. |
mmap-vec |
 |
Substitute for Vec that uses file-backed storage. |
macros-lib |
 |
Library of procedural macros implemented using proc_macro2 |
macros-impl |
 |
Implementation crate for proc_macro_hack |
macros-decl |
 |
Procedural macros. |
algebra/ |
||
u256 |
 |
Implementation of 256-bit unsigned integers. |
primefield |
 |
A 251-bit prime field suitable for FFTs. |
elliptic-curve |
 |
An elliptic curve over the primefield. |
crypto/ |
||
elliptic-curve-crypto |
 |
Pedersen commitments and digital signatures. |
hash |
 |
Hash primitive used in zkp-stark. |
merkle-tree |
 |
Merkle tree based vector commitment. |
stark |
 |
STARK protocol implementation |
Example
Example from the stark package:
use zkp_stark::{*, primefield::*};
struct FibonacciClaim {
index: usize,
value: FieldElement,
}
impl Verifiable for FibonacciClaim {
fn constraints(&self) -> Constraints {
use RationalExpression::*;
// Seed
let mut seed = self.index.to_be_bytes().to_vec();
seed.extend_from_slice(&self.value.as_montgomery().to_bytes_be());
// Constraint repetitions
let trace_length = self.index.next_power_of_two();
let g = Constant(FieldElement::root(trace_length).unwrap());
let on_row = |index| (X - g.pow(index)).inv();
let every_row = || (X - g.pow(trace_length - 1)) / (X.pow(trace_length) - 1.into());
let mut c = Constraints::from_expressions((trace_length, 2), seed, vec![
(Trace(0, 1) - Trace(1, 0)) * every_row(),
(Trace(1, 1) - Trace(0, 0) - Trace(1, 0)) * every_row(),
(Trace(0, 0) - 1.into()) * on_row(0),
(Trace(0, 0) - (&self.value).into()) * on_row(self.index),
])
.unwrap()
}
}
impl Provable<&FieldElement> for FibonacciClaim {
fn trace(&self, witness: &FieldElement) -> TraceTable {
let trace_length = self.index.next_power_of_two();
let mut trace = TraceTable::new(trace_length, 2);
trace[(0, 0)] = 1.into();
trace[(0, 1)] = witness.clone();
for i in 0..(trace_length - 1) {
trace[(i + 1, 0)] = trace[(i, 1)].clone();
trace[(i + 1, 1)] = &trace[(i, 0)] + &trace[(i, 1)];
}
trace
}
}
pub fn main() {
let claim = FibonacciClaim {
index: 5000,
value: FieldElement::from_hex_str("069673d708ad3174714a2c27ffdb56f9b3bfb38c1ea062e070c3ace63e9e26eb"),
};
let secret = FieldElement::from(42);
let proof = claim.prove(&secret).unwrap();
claim.verify(&proof).unwrap();
}
Features and Limitations
Features
A simple interface. The public interface is simple and is considered semver-stable. Future versions are expected to add functionality without breaking this interface.
Succinct proofs. For a given security parameter, the proof size is close to minimal. Significant improvements here would require innovations in the way constraint systems are designed or in the underlying cryptography.
Decent performance. All steps of the proof are using asymptotically optimal algorithms and all of the major steps are multi-threaded. There are no hard memory requirements. We can expect a good amount of performance improvements by fine-tuning, but we don't expect orders of magnitude improvements.
Webassembly support. The verifier can be used in a WebAssembly environment without the Rust std lib. The prover will work too, but has not been a priority.
Limitations
No high-level language. Constraints are specified using their algebraic expressions. This requires complicated and careful design from the library user and is easy to do wrong, leading to insecure systems. A high level language would help make development simpler and safer and facilitate re-use of components.
No comprehensive security audit. While development is done with the best security practices in mind, it is still very early stage and has not had the amount of expert peer review required for a production grade system.
No perfect zero-knowledge. The current implementation provides succinct proofs but not perfect zero knowledge. While non-trivial, it is theoretically possible to learn something about the secret. Achieving perfect zero-knowledge is possible and can be implemented.
No side-channel resistance. The implementation favours performance over side-channel resistance. While this is common in zero-knowledge proof system, you should be aware that his might leak intermediate computations. Side-channel resistance can be implemented.
Hard-coded field and hash. The current implementation uses a particular prime field and a particular hash function. These are optimized for verification in the Ethereum Virtual Machine. This can be generalized to other primitives optimized for other use cases.
Contributing
See our Contributing guideline and Code of conduct.
See CircleCI documentation on how to run tests locally.
References
Resource overviews on Zero Knowledge Proof protoocols:
- The excelent zkp.science.
- The overview by Matter Labs
Resources on numeric and cryptographic algorithm implementation:
- Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone (2001). "Handbook of Applied Cryptography". Available online
- Donald Knuth (1968-). "The art of computer programming". In particular part II: Seminumerical algorithms.
4 Nov 21, 2023
43 May 20, 2023
3 Nov 8, 2023
653 Jan 3, 2023
99 Dec 22, 2022
270 Jan 5, 2023
50 Oct 31, 2022
1 Dec 30, 2021
404 Jan 1, 2023
7 Dec 20, 2022
21 Dec 28, 2022
68 Dec 5, 2022
40 Mar 6, 2023
7 Jul 28, 2023
386 Dec 27, 2022
2 Aug 10, 2022
31 Dec 12, 2022
3.7k Jan 6, 2023