1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186
//! Zero knowledge membership proofs based on the //! [One-out-of-Many](https://eprint.iacr.org/2014/764) proof scheme. //! //! This membership proofs allow you to prove knowledge of the opening of a //! pedersen commitment, within a set of pedersen commitments, without //! revealing anything about the commitment or its position within the set. //! //! # Examples //! Prove you know a commitment to zero, `C_l`, within a set of commitments: //! ``` //! # use rand::rngs::OsRng; // You should use a more secure RNG //! # use one_of_many_proofs::proofs::{ProofGens, OneOfManyProofs}; //! # use curve25519_dalek::scalar::Scalar; //! # use curve25519_dalek::ristretto::RistrettoPoint; //! # use merlin::Transcript; //! # //! // Set up proof generators //! let gens = ProofGens::new(5).unwrap(); //! //! // Create the prover's commitment to zero //! let l: usize = 3; // The prover's commitment will be third in the set //! let v = Scalar::zero(); //! let r = Scalar::random(&mut OsRng); // You should use a more secure RNG //! let C_l = gens.commit(&v, &r).unwrap(); //! //! // Build a random set containing the prover's commitment at index `l` //! let mut set = (1..gens.max_set_size()) //! .map(|_| RistrettoPoint::random(&mut OsRng)) //! .collect::<Vec<RistrettoPoint>>(); //! set.insert(l, C_l); //! //! // Compute a `OneOfMany` membership proof for this commitment //! let mut t = Transcript::new(b"OneOfMany-Test"); //! let proof = set.iter().prove(&gens, &mut t.clone(), l, &r).unwrap(); //! //! // Verify this membership proof, without any knowledge of `l` or `r`. //! assert!(set //! .iter() //! .verify(&gens, &mut t.clone(), &proof) //! .is_ok()); //! ``` //! Prove you know a commitment that opens to any value (possibly non-zero), //! within a set of commitments: //! ``` //! # use rand::rngs::OsRng; // You should use a more secure RNG //! # use one_of_many_proofs::proofs::{ProofGens, OneOfManyProofs}; //! # use curve25519_dalek::scalar::Scalar; //! # use curve25519_dalek::ristretto::RistrettoPoint; //! # use merlin::Transcript; //! # //! // Set up proof generators //! let gens = ProofGens::new(5).unwrap(); //! //! // Create the prover's commitment to zero //! let l: usize = 3; // The prover's commitment will be third in the set //! let v = Scalar::random(&mut OsRng); // Commit to any random value //! let r = Scalar::random(&mut OsRng); // You should use a more secure RNG //! let C_l = gens.commit(&v, &r).unwrap(); //! //! // Build a random set containing the prover's commitment at index `l` //! let mut set = (1..gens.max_set_size()) //! .map(|_| RistrettoPoint::random(&mut OsRng)) //! .collect::<Vec<RistrettoPoint>>(); //! set.insert(l, C_l); //! //! // Create a new commitment to the same value as `C_l` //! let r_new = Scalar::random(&mut OsRng); // You should use a more secure RNG //! let C_new = gens.commit(&v, &r_new).unwrap(); //! //! // Compute a `OneOfMany` membership proof for this commitment //! let mut t = Transcript::new(b"OneOfMany-Test"); //! let proof = set.iter().prove_with_offset(&gens, &mut t.clone(), l, &(r - r_new), Some(&C_new)).unwrap(); //! //! // Verify this membership proof, without any knowledge of `l` or `r`. //! assert!(set //! .iter() //! .verify_with_offset(&gens, &mut t.clone(), &proof, Some(&C_new)) //! .is_ok()); //! ``` //! //! # Ring Signatures //! One particularly useful application of membership proofs is ring signatures. This can easily be //! accomplished by committing to some message before computing or verifying a proof. Consider the //! below example, signing and verifying a message from an anonymous member of the set: //! ``` //! # use rand::rngs::OsRng; // You should use a more secure RNG //! # use one_of_many_proofs::proofs::{ProofGens, OneOfManyProofs}; //! # use curve25519_dalek::scalar::Scalar; //! # use curve25519_dalek::ristretto::RistrettoPoint; //! # use merlin::Transcript; //! # //! // Set up proof generators //! let gens = ProofGens::new(5).unwrap(); //! //! // Create the prover's commitment to zero //! let l: usize = 3; // The signer's commitment will be third in the set //! let v = Scalar::random(&mut OsRng); // Commit to any random value //! let r = Scalar::random(&mut OsRng); // You should use a more secure RNG //! let C_l = gens.commit(&v, &r).unwrap(); //! //! // Build a random set containing the prover's commitment at index `l` //! let mut set = (1..gens.max_set_size()) //! .map(|_| RistrettoPoint::random(&mut OsRng)) //! .collect::<Vec<RistrettoPoint>>(); //! set.insert(l, C_l); //! //! // Create a new commitment to the same value as `C_l` //! let r_new = Scalar::random(&mut OsRng); // You should use a more secure RNG //! let C_new = gens.commit(&v, &r_new).unwrap(); //! //! // Compute a `OneOfMany` membership proof for this commitment //! let mut t = Transcript::new(b"OneOfMany-Test"); //! //! // Commit to a message to be signed //! t.append_message(b"msg", b"Hello, World!"); //! //! // Sign the message anonymously //! let proof = set.iter().prove_with_offset(&gens, &mut t.clone(), l, &(r - r_new), Some(&C_new)).unwrap(); //! //! // Compute a `OneOfMany` membership proof for this commitment //! let mut t = Transcript::new(b"OneOfMany-Test"); //! //! // Verification will fail, because this transcript doesn't commit to the same message //! assert!(set //! .iter() //! .verify_with_offset(&gens, &mut t.clone(), &proof, Some(&C_new)) //! .is_err()); //! //! // Commit to a message to be signed //! t.append_message(b"msg", b"Hello, World!"); //! //! // Verification will now succeed, because this transcript commits to the signed message //! assert!(set //! .iter() //! .verify_with_offset(&gens, &mut t.clone(), &proof, Some(&C_new)) //! .is_ok()); //! ``` //! //! # Perfomance //! The proof(s) provided by this crate depend heavily on the //! [curve25519-dalek](https://docs.rs/curve25519-dalek) for elliptic curve operations on the //! ristretto255 curve group. These operations can be optimized by compiling to use the SIMD //! backend. To do set this compile option, set the following environment variable: //! ```bash //! export RUSTFLAGS="-C target_cpu=native" //! ``` //! //! Benchmarks are run using [criterion.rs](https://docs.rs/criterion): //! ```bash //! cargo bench //! ``` //! //! # References //! * [One-out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin](https://eprint.iacr.org/2014/764) //! * [Short Accountable Ring Signatures Based on DDH](https://eprint.iacr.org/2015/643) //! * [Lelandus: Towards Confidentiality and Anonymity of Blockchain Transactions From Standard Assumptions](https://eprint.iacr.org/2019/373) #![no_std] #![feature(test)] //----------------------------------------------------------------------------- // External dependencies: //----------------------------------------------------------------------------- extern crate curve25519_dalek; extern crate polynomials; extern crate sha3; #[cfg(not(feature = "std"))] #[macro_use] extern crate alloc; #[cfg(feature = "std")] #[macro_use] extern crate std; //----------------------------------------------------------------------------- // Public modules //----------------------------------------------------------------------------- pub mod errors; pub mod proofs; //----------------------------------------------------------------------------- // Internal modules //----------------------------------------------------------------------------- pub(crate) mod gray_code; pub(crate) mod transcript;