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