schnorr/src/schnorr_prover.rs
src/schnorr_prover.rsRaw
1use anyhow::Result;
2
3use plonky2::iop::{
4 target::{BoolTarget, Target},
5 witness::{PartialWitness, WitnessWrite},
6};
7use plonky2::field::{
8 goldilocks_field::GoldilocksField,
9 types::Field,
10};
11use plonky2::hash::poseidon::PoseidonHash;
12use plonky2::plonk::{
13 circuit_builder::CircuitBuilder,
14 config::GenericConfig,
15};
16
17use crate::{
18 mod65537::Mod65537Builder,
19 schnorr::{SchnorrPublicKey, SchnorrSignature},
20};
21
22type GoldF = GoldilocksField;
23
24pub struct MessageTarget {
25 msg: Vec<Target>,
26}
27
28impl MessageTarget {
29 fn new_with_size(builder: &mut CircuitBuilder<GoldF, 2>, n: usize) -> Self {
30 Self {
31 msg: builder.add_virtual_targets(n),
32 }
33 }
34
35 fn set_witness(&self, pw: &mut PartialWitness<GoldF>, msg: &Vec<GoldF>) -> Result<()> {
36 assert!(msg.len() == self.msg.len());
37 for (&t, &x) in self.msg.iter().zip(msg.iter()) {
38 pw.set_target(t, x)?;
39 }
40
41 Ok(())
42 }
43}
44
45pub struct SchnorrSignatureTarget {
46 s: Target,
47 e: Target,
48}
49
50impl SchnorrSignatureTarget {
51 fn new_virtual(builder: &mut CircuitBuilder<GoldF, 2>) -> Self {
52 let s = builder.add_virtual_target();
53 let e = builder.add_virtual_target();
54 Self{ s, e }
55 }
56
57 fn set_witness(&self, pw: &mut PartialWitness<GoldF>, sig: &SchnorrSignature) -> Result<()> {
58 pw.set_target(self.s, GoldilocksField::from_canonical_u64(sig.s))?;
59 pw.set_target(self.e, GoldilocksField::from_canonical_u64(sig.e))?;
60 Ok(())
61 }
62}
63
64pub struct SchnorrPublicKeyTarget {
65 pk: Target,
66}
67
68impl SchnorrPublicKeyTarget {
69 fn new_virtual(builder: &mut CircuitBuilder<GoldF, 2>) -> Self {
70 Self{ pk: builder.add_virtual_target() }
71 }
72
73 fn set_witness(&self, pw: &mut PartialWitness<GoldF>, pk: &SchnorrPublicKey) -> Result<()> {
74 pw.set_target(self.pk, pk.pk)?;
75 Ok(())
76 }
77}
78
79pub struct SchnorrBuilder {}
80
81impl SchnorrBuilder {
82 pub fn constrain_sig <
83 C: GenericConfig<2, F = GoldF>,
84 > (
85 &self,
86 builder: &mut CircuitBuilder::<GoldF, 2>,
87 sig: &SchnorrSignatureTarget,
88 msg: &MessageTarget,
89 pk: &SchnorrPublicKeyTarget,
90 ) -> () {
91 let verification_output = self.verify_sig::<C>(builder, sig, msg, pk);
92 let true_target = builder._true();
93 builder.connect(verification_output.target, true_target.target);
94 }
95
96 pub fn verify_sig <
97 C: GenericConfig<2, F = GoldF>,
98 > (
99 &self,
100 builder: &mut CircuitBuilder::<GoldF, 2>,
101 sig: &SchnorrSignatureTarget,
102 msg: &MessageTarget,
103 pk: &SchnorrPublicKeyTarget,
104 ) -> BoolTarget {
105 let PRIME_GROUP_GEN: Target = builder.constant(GoldF::from_canonical_u64(6612579038192137166));
106 let PRIME_GROUP_ORDER: Target = builder.constant(GoldF::from_canonical_u64(65537));
107 const num_bits_exp: usize = 32;
108
109 /* here's the direct verification calculation,
110 which we verify in-circuit
111 let r: GoldF = Self::pow(self.PRIME_GROUP_GEN, sig.s)
112 * Self::pow(pk.pk, sig.e);
113 let e_v: u64 = self.hash_insecure(&r, msg);
114 e_v == sig.e */
115
116 let gs: Target = builder.exp(PRIME_GROUP_GEN, sig.s, num_bits_exp);
117 let pe: Target = builder.exp(pk.pk, sig.e, num_bits_exp);
118 let r: Target = builder.mul(gs, pe);
119
120 // compute hash
121 // note that it's safe to clone Targets since they just contain indices
122 let hash_input: Vec<Target> = std::iter::once(r)
123 .chain(msg.msg.iter().cloned())
124 .collect();
125 let hash_output: Target = builder.hash_n_to_hash_no_pad::<PoseidonHash>(
126 hash_input,
127 ).elements[0]; // whoops have to take mod group order;
128
129 let e: Target = Mod65537Builder::mod_65537(builder, hash_output);
130
131 // test equality
132 builder.is_equal(e, sig.e)
133 }
134}
135
136#[cfg(test)]
137mod tests{
138 use crate::schnorr::{SchnorrPublicKey, SchnorrSecretKey, SchnorrSigner, SchnorrSignature};
139 use crate::schnorr_prover::{MessageTarget, SchnorrBuilder, SchnorrPublicKeyTarget, SchnorrSignatureTarget};
140 use plonky2::iop::witness::PartialWitness;
141 use plonky2::plonk::{
142 circuit_builder::CircuitBuilder,
143 circuit_data::CircuitConfig,
144 config::{GenericConfig, PoseidonGoldilocksConfig},
145 };
146 use plonky2::field::goldilocks_field::GoldilocksField;
147 use rand;
148
149 #[test]
150 fn test_schnorr() -> () {
151 const D: usize = 2;
152 type C = PoseidonGoldilocksConfig;
153 type F = <C as GenericConfig<D>>::F;
154
155 let mut rng: rand::rngs::ThreadRng = rand::thread_rng();
156
157 let config = CircuitConfig::standard_recursion_config();
158 let mut builder = CircuitBuilder::<F, D>::new(config);
159
160 let sb: SchnorrBuilder = SchnorrBuilder{};
161
162 // create keypair, message, signature
163 let sk: SchnorrSecretKey = SchnorrSecretKey{ sk: 133 };
164 let ss = SchnorrSigner::new();
165 let pk: SchnorrPublicKey = ss.keygen(&sk);
166 let msg: Vec<GoldilocksField> = ss.u64_into_goldilocks_vec(
167 vec![1500, 1600, 0, 0, 0]
168 );
169 let msg_size: usize = msg.len();
170 let sig: SchnorrSignature = ss.sign(&msg, &sk, &mut rng);
171
172 let pk_targ = SchnorrPublicKeyTarget::new_virtual(&mut builder);
173 let sig_targ = SchnorrSignatureTarget::new_virtual(&mut builder);
174 let msg_targ = MessageTarget::new_with_size(&mut builder, msg_size);
175
176 sb.constrain_sig::<PoseidonGoldilocksConfig> (
177 &mut builder,
178 &sig_targ,
179 &msg_targ,
180 &pk_targ
181 );
182
183 // assign witnesses for verification
184 let mut pw: PartialWitness<F> = PartialWitness::new();
185 pk_targ.set_witness(&mut pw, &pk).unwrap();
186 sig_targ.set_witness(&mut pw, &sig).unwrap();
187 msg_targ.set_witness(&mut pw, &msg).unwrap();
188
189
190 let data = builder.build::<C>();
191 let proof = data.prove(pw).unwrap();
192 }
193
194 #[test]
195 fn test_schnorr_fails() {
196 const D: usize = 2;
197 type C = PoseidonGoldilocksConfig;
198 type F = <C as GenericConfig<D>>::F;
199
200 let mut rng: rand::rngs::ThreadRng = rand::thread_rng();
201
202 let config = CircuitConfig::standard_recursion_config();
203 let mut builder = CircuitBuilder::<F, D>::new(config);
204
205 let sb: SchnorrBuilder = SchnorrBuilder{};
206
207 // create keypair, message, signature
208 let sk: SchnorrSecretKey = SchnorrSecretKey{ sk: 133 };
209 let ss = SchnorrSigner::new();
210 let pk: SchnorrPublicKey = ss.keygen(&sk);
211 let msg0: Vec<GoldilocksField> = ss.u64_into_goldilocks_vec(
212 vec![1500, 1600, 0, 0, 0]
213 );
214 let msg_size: usize = msg0.len();
215 let sig: SchnorrSignature = ss.sign(&msg0, &sk, &mut rng);
216
217 let msg1: Vec<GoldilocksField> = ss.u64_into_goldilocks_vec(
218 vec![1510, 1600, 0, 0, 0]
219 );
220
221 let pk_targ = SchnorrPublicKeyTarget::new_virtual(&mut builder);
222 let sig_targ = SchnorrSignatureTarget::new_virtual(&mut builder);
223 let msg_targ = MessageTarget::new_with_size(&mut builder, msg_size);
224
225 let verification_result = sb.verify_sig::<PoseidonGoldilocksConfig> (
226 &mut builder,
227 &sig_targ,
228 &msg_targ,
229 &pk_targ
230 );
231
232 // assign witnesses for verification
233 let mut pw: PartialWitness<F> = PartialWitness::new();
234 pk_targ.set_witness(&mut pw, &pk).unwrap();
235 sig_targ.set_witness(&mut pw, &sig).unwrap();
236 msg_targ.set_witness(&mut pw, &msg1).unwrap();
237
238 // check value of verification result
239 let false_target = builder._false();
240 builder.connect(verification_result.target, false_target.target);
241
242 let data = builder.build::<C>();
243 let proof = data.prove(pw).unwrap();
244 }
245
246 #[test]
247 #[should_panic]
248 fn test_schnorr_panics() {
249 const D: usize = 2;
250 type C = PoseidonGoldilocksConfig;
251 type F = <C as GenericConfig<D>>::F;
252
253 let mut rng: rand::rngs::ThreadRng = rand::thread_rng();
254
255 let config = CircuitConfig::standard_recursion_config();
256 let mut builder = CircuitBuilder::<F, D>::new(config);
257
258 let sb: SchnorrBuilder = SchnorrBuilder{};
259
260 // create keypair, message, signature
261 let sk: SchnorrSecretKey = SchnorrSecretKey{ sk: 133 };
262 let ss = SchnorrSigner::new();
263 let pk: SchnorrPublicKey = ss.keygen(&sk);
264 let msg0: Vec<GoldilocksField> = ss.u64_into_goldilocks_vec(
265 vec![1500, 1600, 0, 0, 0]
266 );
267 let msg_size: usize = msg0.len();
268 let sig: SchnorrSignature = ss.sign(&msg0, &sk, &mut rng);
269
270 let msg1: Vec<GoldilocksField> = ss.u64_into_goldilocks_vec(
271 vec![1510, 1600, 0, 0, 0]
272 );
273
274 let pk_targ = SchnorrPublicKeyTarget::new_virtual(&mut builder);
275 let sig_targ = SchnorrSignatureTarget::new_virtual(&mut builder);
276 let msg_targ = MessageTarget::new_with_size(&mut builder, msg_size);
277
278 let verification_result = sb.verify_sig::<PoseidonGoldilocksConfig> (
279 &mut builder,
280 &sig_targ,
281 &msg_targ,
282 &pk_targ
283 );
284
285 // assign witnesses for verification
286 let mut pw: PartialWitness<F> = PartialWitness::new();
287 pk_targ.set_witness(&mut pw, &pk).unwrap();
288 sig_targ.set_witness(&mut pw, &sig).unwrap();
289 msg_targ.set_witness(&mut pw, &msg1).unwrap();
290
291 // value of verification result should be false
292 let true_target = builder._true();
293 builder.connect(verification_result.target, true_target.target);
294
295 let data = builder.build::<C>();
296 let proof = data.prove(pw).unwrap();
297 }
298}