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