Expand description
SigmaFUN!
A rust library for making Sigma protocols fun!
Use
[dependencies]
sigma_fun = {version = "0.4", nodefaultfeatures = true, features = ["alloc"]}
sigma_fun = { version = "0.4", features = ["secp256k1", "serde"] }
rand_chacha = "0.3"
sha2 = "0.9"
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 threeround honest verifier zero knowledge protocols and one of the most fundamental ZeroKnowledge proof systems. They are useful because they are easy to make noninteractive through the FiatShamir heuristic and support various types of 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 (usuallyA
is the same kind of proof asB
).all(n,A)
proves thatn
statements of typeA
are true.eqall(n,A)
proves thatn
statements of typeA
all have the same witness.
We are missing support for generically proving tofm
statements are true (which is much more tricky).
Unfortunately, at the moment n
in all
and eqall
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 noninteractive 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 generatorrng

announce(statement, announce_secret) > announcement
: Given the statement to be proved and anannounce_secret
previously generated byannouncement_secret
, returns anannouncement
. 
implied_announcement(statement, challenge, response) > announcement
: Determines anannouncement
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 thechallenge
Each Sigma protocol also has defines its ChallengeLength
as an associated type.
With these algorithms the interactive Sigma protocol plays out like this:
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
Noninteractive proofs
The standard trick for making Sigma protocols noninteractive is to produce the challenge
in the above diagram from a hash function.
This is called the FiatShamir 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 noninteractive proof for this claim by showing that we know r
such that C = r * G
OR C  H = r * G
.
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 16byte (128bit) 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().expect_nonzero("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().expect_nonzero("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<L>, secp256k1::DLG<L>>;
// 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 noninteractive proof system so we apply the FiatShamir transform with Sha256 as the challenge hash.
// We use ChaCha20Rng to help produce our announcement.
let proof_system = FiatShamir::<Protocol, HashTranscript<Sha256, ChaCha20Rng>>::default();
// Make the noninteractive 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::<Protocol, HashTranscript<Sha256>>::default();
// They recreate the statement
let statement = (C, g!(C  H).normalize().expect_nonzero("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 proofssecp256k1
: enable secp256k1 discrete log proofs (using secp256kfun)
See Also
 ZKP – Helped inspire this library and is much more developed.
zkp
is opinionated about hash function (sha3) and group (ristretto) and only supportseq
andand
type composition.
Reexports
Modules
Proofs of knowledge of discrete logarithm on Edwards twist of curve25519 using using curve25519dalek
.
Module for implemenations of protocols that are composed of sigma protocols.
Proofs of knowledge of discrete logarithm for the secp256k1 curve using secp256kfun
.
Structs
Combinator for proving all of N statements of the same type is true.
Combinator for proving that both A
and B
are true where A
and B
are not the same relation.
A proof produced by FiatShamir
.
Combinator for showing that two Sigma protocols have the same witness.
Combinator for proving any number of statements of the same kind have the same witness.
Applies the FiatShamir transform to a given Sigma
protocol given a Transcript
.
A transcript which consists of a hash with fixed length output and a seedable RNG.
Combinator for proving that A
OR B
is true.
Enums
Enum for the prover to choose which of the two statements she knows.
Traits
A Transcript
that can also generate a rng.
The Sigma
trait is used to define a Sigma protocol.
A trait for a FiatShamir proof transcript.
Utility tarait for something that can be written as a string.