schnorr/src/schnorr_prover.rs
src/schnorr_prover.rsRaw
1use anyhow::Result;
2use plonky2::field::extension::{Extendable, FieldExtension};
3use plonky2::field::types::Field;
4use plonky2::field::goldilocks_field::GoldilocksField;
5use plonky2::hash::hash_types::RichField;
6use plonky2::hash::poseidon::PoseidonHash;
7use plonky2::iop::target::{BoolTarget, Target};
8use plonky2::iop::witness::{PartialWitness, WitnessWrite};
9use plonky2::plonk::circuit_builder::CircuitBuilder;
10use plonky2::plonk::circuit_data::{CircuitConfig, CircuitData, CommonCircuitData, VerifierCircuitData, VerifierOnlyCircuitData};
11use plonky2::plonk::config::{GenericConfig, PoseidonGoldilocksConfig};
12use plonky2::plonk::proof::ProofWithPublicInputs;
13
14pub struct MessageTarget {
15 msg: Vec<Target>,
16}
17
18impl MessageTarget {
19 fn new_with_size(builder: &mut CircuitBuilder<GoldilocksField, 2>, n: usize) -> Self {
20 Self {
21 msg: builder.add_virtual_targets(n),
22 }
23 }
24}
25
26pub struct SchnorrSignatureTarget {
27 s: Target,
28 e: Target,
29}
30
31impl SchnorrSignatureTarget {
32 fn new_virtual(builder: &mut CircuitBuilder<GoldilocksField, 2>) -> Self {
33 let s = builder.add_virtual_target();
34 let e = builder.add_virtual_target();
35 Self{ s, e }
36 }
37}
38
39pub struct SchnorrPublicKeyTarget {
40 pk: Target,
41}
42
43#[derive(Debug, Default)]
44pub struct Mod65537Generator {
45 a: Target,
46 q: Target,
47 r: Target,
48}
49
50pub struct SchnorrBuilder {
51
52}
53
54impl SchnorrBuilder {
55 // Reduce a modulo the constant 65537
56 // where a is the canonical representative for an element of the field
57 // (meaning: 0 \leq a < p)
58
59 // To verify this, write
60 // a = 65537 * q + r, and do range checks to check that:
61 // 0 <= q <= floor(p / 65537)
62 // 0 <= r < 65537
63 // (these first two checks guarantee that a lies in the range [0, p + 65536])
64 // if q = floor(p / 65537) then r = 0
65 // (note that p % 65537 == 1 so this is the only possibility)
66 fn mod_65537 <
67 C: GenericConfig<2, F = GoldilocksField>,
68 > (
69 builder: &mut CircuitBuilder::<GoldilocksField, 2>,
70 a: &Target,
71 ) -> Target {
72 let q = builder.add_virtual_target();
73 let r = builder.add_virtual_target();
74
75 // the Mod65537Generator will assign values to q and r later
76 builder.add_simple_generator( Mod65537Generator { a, q, r } );
77
78 // impose four constraints
79 // 1. a = 65537 * q + r
80 let t65537 = builder.constant(GoldilocksField::from_canonical_u64(65537));
81 let a_copy = builder.mul_add(t65537, q, r);
82 builder.connect(*a, a_copy);
83
84 // 2. 0 <= q <= floor(p / 65537)
85 // max_q is 281470681743360 = floor(p / 65537) = (p-1) / 65537 = 2^48 - 2^32
86 let max_q = builder.constant(GoldilocksField::from_canonical_u64(281470681743360));
87 builder.range_check(q, 48);
88 builder.range_check(builder.sub(max_q, q), 48);
89
90 // 3. 0 <= r < 65537
91 let max_r = builder.constant(GoldilocksField::from_canonical_u64(65537));
92 builder.range_check(r, 17);
93 builder.range_check(builder.sub(max_r, r), 17);
94
95 // 4. if q = floor(p / 65537) then r = 0
96 let q_equals_max = builder.is_equal(q, max_q);
97 builder.connect(builder.mul(q_equals_max.target, r), builder.zero());
98
99 r
100 }
101
102 fn constrain_sig <
103 C: GenericConfig<2, F = GoldilocksField>,
104 > (
105 &self,
106 builder: &mut CircuitBuilder::<GoldilocksField, 2>,
107 sig: &SchnorrSignatureTarget,
108 msg: &MessageTarget,
109 pk: &SchnorrPublicKeyTarget,
110 ) -> () {
111 let PRIME_GROUP_GEN: Target = builder.constant(GoldilocksField::from_canonical_u64(6612579038192137166));
112 let PRIME_GROUP_ORDER: Target = builder.constant(GoldilocksField::from_canonical_u64(65537));
113 const num_bits_exp: usize = 32;
114
115 /*
116 let r: GoldilocksField = Self::pow(self.PRIME_GROUP_GEN, sig.s)
117 * Self::pow(pk.pk, sig.e);
118 let e_v: u64 = self.hash_insecure(&r, msg);
119 e_v == sig.e */
120
121 let gs: Target = builder.exp(PRIME_GROUP_GEN, sig.s, num_bits_exp);
122 let pe: Target = builder.exp(pk.pk, sig.e, num_bits_exp);
123 let r: Target = builder.mul(gs, pe);
124
125 // compute hash
126 // note that it's safe to clone Targets since they just contain indices
127 let hash_input: Vec<Target> = std::iter::once(r)
128 .chain(msg.iter().cloned())
129 .collect();
130 let e: Target = builder.hash_n_to_hash_no_pad::<PoseidonHash>(
131 hash_input,
132 ).elements[0] // whoops have to take mod group order;
133
134 // enforce equality
135 builder.connect(e, sig.e);
136 }
137}
138
139#[cfg(test)]
140mod tests{
141 use crate::schnorr::{SchnorrPublicKey, SchnorrSecretKey, SchnorrSigner, SchnorrSignature};
142 use crate::schnorr_prover::SchnorrBuilder;
143 use plonky2::plonk::circuit_builder::CircuitBuilder;
144 use plonky2::plonk::circuit_data::{CircuitConfig, CircuitData, CommonCircuitData, VerifierCircuitData, VerifierOnlyCircuitData};
145 use plonky2::plonk::config::{GenericConfig, PoseidonGoldilocksConfig};
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 builder.add_virtual_fri_proof(num_leaves_per_oracle, params)
161
162 let sb: SchnorrBuilder = SchnorrBuilder{};
163
164 // create keypair, message, signature
165 let sk: SchnorrSecretKey = SchnorrSecretKey{ sk: 133 };
166 let ss = SchnorrSigner::new();
167 let pk: SchnorrPublicKey = ss.keygen(&sk);
168 let msg: Vec<GoldilocksField> = ss.u64_into_goldilocks_vec(
169 vec![1500, 1600, 0, 0, 0]
170 );
171 let msg_size: usize = msg.len();
172 let sig: SchnorrSignature = ss.sign(&msg, &sk, &mut rng);
173
174 let sig_target = builder.constant(sig);
175 // instead of verifying we're going to prove the verification
176 sb.constrain_sig(
177 &mut builder,
178 &sig,
179 &msg,
180 &pk
181 );
182 }
183}