# SigmaFUN! [![crates_badge]][crates_url] [![docs_badge]][docs_url] [docs_badge]: https://docs.rs/sigma_fun/badge.svg [docs_url]: https://docs.rs/sigma_fun [crates_badge]: https://img.shields.io/crates/v/sigma_fun.svg [crates_url]: https://crates.io/crates/sigma_fun A rust library for making Sigma protocols fun! ## Use ``` toml [dependencies] # For just the traits and combinators sigma_fun = {version = "0.6", no-default-features = true, features = ["alloc"]} # To create secp256k1 non-interactive proofs and serialize them sigma_fun = { version = "0.6", features = ["secp256k1", "serde", "alloc"] } # you need a hash function and an rng for non-interactive proofs rand_chacha = "0.3" sha2 = "0.10" ``` ### Should use? Highly experimental and breaking changes to the API and to the backwards compatibility of the proofs may happen at any time. There could easily be implementation mistakes especially in the more complicated proofs in the `ext` module! ## "Sigma" Protocols Sigma protocols are three-round *honest verifier zero knowledge protocols* and one of the most fundamental Zero-Knowledge proof systems. They are useful because they are easy to make non-interactive through the Fiat-Shamir heuristic and support various types of [composition](#composition). Sigma protocols can be used to construct signature schemes, verifiable random functions, authentication schemes, anonymous credential schemes and many more exotic things. For a basic background on Sigma protocols see section 5 of [Shoenmaker]'s excellent lecture notes. ## Composition Sigma protocols can be securely combined with each other to form a new Sigma protocol. For example, if you have two Sigma protocols for proving statements `A` and `B` you can compose them into a protocol for proving `A or B`. The resulting protocol will also be a Sigma protocol! At the moment this library supports the following combinators: - `or(A,B)` proves that one of the two statements is true. - `and(A,B)` proves both statements are true. - `eq(A,B)` proves two statements have the same witness (usually `A` is the same kind of proof as `B`). - `all(n,A)` proves that `n` statements of type `A` are true. - `eq-all(n,A)` proves that `n` statements of type `A` all have the same witness. We are missing support for generically proving `t-of-m` statements are true (which is much more tricky). Unfortunately, at the moment `n` in `all` and `eq-all` must be known at compile time. ## The `Sigma` trait This library provides a [`Sigma`] trait which can be implemented for any Sigma protocol regardless of how the underlying proof is structured. Anything implementing [`Sigma`] can then be composed with the combinators to create more intricate Sigma protocols. Finally, the protocol can be made non-interactive with the resulting proofs implementing [`serde`] serialization traits. We define the [`Sigma`] trait with five main core functions: - **`gen_announce_secret(rng) -> announce_secret`**: Generates the secret random value used in the proof from a given random number generator `rng` - **`announce(statement, announce_secret) -> announcement`**: Given the statement to be proved and an `announce_secret` previously generated by `announcement_secret`, returns an `announcement`. - **`implied_announcement(statement, challenge, response) -> announcement`**: Determines an `announcement` such that `(statement, announcement, challenge, response)` is a *valid* transcript for the sigma protocol. - **`sample_response(rng) -> response`**: samples a response uniformly from the response space. - **`respond(witness, statement, announce_secret, announcement, challenge) -> response`**: Computes a valid response to the `challenge` Each Sigma protocol also has defines its `ChallengeLength` as an associated type. With these algorithms the interactive Sigma protocol plays out like this: ```ignore Prover(witness, statement, rng) Verifier(statement) ====== announce_secret = gen_announce_secret(rng) announcement = announce(statement, announce_secret) announcement +-------------------> challenge *uniformly sample ChallengeLength bytes* <-------------------+ response = respond(witness, statement, announce_secret, announcement, challenge) response +-------------------> check implied_announcement(statement, challenge, response) == announcement ``` ### Non-interactive proofs The standard trick for making Sigma protocols non-interactive is to produce the `challenge` in the above diagram from a hash function. This is called the Fiat-Shamir heuristic and is secure in the *random oracle model*. The verifier can just check that the hash was computed correctly and the response is correct. ## Example A Pedersen commitment is in the form `C = r * G + c * H` where `c` is the value committed to a value for `h` such that `H = h * G` is unknown to the committer. For a background on Pedersen commitments see [Shoenmaker] section 3.2.2. Suppose we want to prove that `c` is either 0 or 1 in Zero knowledge to someone who only knows `C`. We can construct a non-interactive proof for this claim by showing that we know `r` such that `C = r * G` OR `C - H = r * G`. ```rust use std::string::ToString; use sigma_fun::{ typenum::U16, FiatShamir, HashTranscript, Either, Or, secp256k1::{ self, fun::{Point, Scalar, G, marker::*, g}}}; use sha2::Sha256; use rand_chacha::ChaCha20Rng; // Pretend to choose H securely in a public setup let H = Point::random(&mut rand::thread_rng()); // our commitment will be to 1 let c = Scalar::::from(1u32); // We use a 16-byte (128-bit) challenge length type L = U16; let (C,r) = { // make a pedersen commitment let r = Scalar::random(&mut rand::thread_rng()); let C = g!(r * G + c * H).normalize().non_zero().expect("zero is computationally unreachable"); (C,r) }; // Our strategy is to prove that we know r such that either C = r * G or C - H = r * G using // an OR composition between two standard knowledge of discrete logarithm proofs. let statement = (C, g!(C - H).normalize().non_zero().expect("computationally unreachable")); // since we are commiting to 1 we know the witness for the right hand side statement. let witness = Either::Right(r); // Our prover is going to prove knowledge of one of two point to the base G (either C or C - H). type Protocol = Or::, secp256k1::DLG>; // Every protocol has an unambiguous name which is hashed into the transcript for protocol separation purposes. assert_eq!(Protocol::default().to_string(), "or(DLG(secp256k1),DLG(secp256k1))"); // we want a non-interactive proof system so we apply the Fiat-Shamir transform with Sha256 as the challenge hash. // We use ChaCha20Rng to help produce our announcement. let proof_system = FiatShamir::>::default(); // Make the non-interactive proof -- pass in a system rng to make the proof more robust. let proof = proof_system.prove(&witness, &statement, Some(&mut rand::thread_rng())); // The verifier gets sent (C, proof) { // The verifier's proof system doesn't need the rng let proof_system = FiatShamir::>::default(); // They recreate the statement let statement = (C, g!(C - H).normalize().non_zero().expect("bogus commitment")); // and verify it against the proof assert!(proof_system.verify(&statement, &proof)); // The verifier is convinced of the statement and nothing else } ``` ## Feature flags - `ed25519`: enable ed25519 discrete log proofs - `secp256k1`: enable secp256k1 discrete log proofs (using [secp256kfun]) ## See Also - [ZKP](https://crates.io/crates/zkp) -- Helped inspire this library and is much more developed. `zkp` is opinionated about hash function (sha3) and group (ristretto) and only supports `eq` and `and` type composition. [`serde`]: https://docs.rs/serde [`Sigma`]: https://docs.rs/sigma_fun/latest/sigma_fun/trait.Sigma.html [Shoenmaker]: https://www.win.tue.nl/~berry/CryptographicProtocols/LectureNotes.pdf [`secp256kfun`]: https://docs.rs/secp256kfun