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