schnorr/src/mod65537.rs
src/mod65537.rsRaw
1
2use anyhow::Result;
3
4use plonky2::iop::{
5 generator::{GeneratedValues, SimpleGenerator},
6 target::Target,
7 witness::{PartitionWitness, Witness, WitnessWrite},
8};
9use plonky2::field::{
10 goldilocks_field::GoldilocksField,
11 types::{Field, PrimeField64},
12};
13use plonky2::plonk::{
14 circuit_builder::CircuitBuilder,
15 circuit_data::CommonCircuitData,
16 config::{GenericConfig, PoseidonGoldilocksConfig},
17 proof::ProofWithPublicInputs,
18};
19use plonky2::util::serialization::{Buffer, IoResult, Read, Write};
20
21use crate::schnorr::{SchnorrPublicKey, SchnorrSignature};
22
23type GoldF = GoldilocksField;
24
25
26
27#[derive(Debug, Default)]
28pub struct Mod65537Generator {
29 a: Target,
30 q: Target,
31 r: Target,
32}
33
34impl SimpleGenerator<GoldF, 2> for Mod65537Generator {
35 fn id(&self) -> String {
36 "Mod65537Generator".to_string()
37 }
38 fn dependencies(&self) -> Vec<Target> {
39 vec![self.a]
40 }
41
42 fn run_once(
43 &self,
44 witness: &PartitionWitness<GoldF>,
45 out_buffer: &mut GeneratedValues<GoldF>,
46 ) -> Result<()> {
47 let a = witness.get_target(self.a);
48 let a64 = a.to_canonical_u64();
49 let q64 = a64 / 65537;
50 let r64 = a64 % 65537;
51
52 out_buffer.set_target(self.q, GoldF::from_canonical_u64(q64));
53 out_buffer.set_target(self.r, GoldF::from_canonical_u64(r64));
54
55 Ok(())
56 }
57
58 fn serialize(&self, dst: &mut Vec<u8>, common_data: &CommonCircuitData<GoldF, 2>) -> IoResult<()> {
59 dst.write_target(self.a)?;
60 dst.write_target(self.q)?;
61 dst.write_target(self.r)?;
62 Ok(())
63 }
64
65 fn deserialize(src: &mut Buffer, common_data: &CommonCircuitData<GoldF, 2>) -> IoResult<Self>
66 where
67 Self: Sized
68 {
69 let a = src.read_target()?;
70 let q = src.read_target()?;
71 let r = src.read_target()?;
72 Ok(Self { a, q, r })
73 }
74}
75
76pub struct Mod65537Builder {}
77
78impl Mod65537Builder {
79 // Reduce a modulo the constant 65537
80 // where a is the canonical representative for an element of the field
81 // (meaning: 0 \leq a < p)
82
83 // To prove this, write
84 // a = 65537 * q + r, and do range checks to check that:
85 // 0 <= q <= floor(p / 65537)
86 // 0 <= r < 65537
87 // (these first two checks guarantee that a lies in the range [0, p + 65536])
88 // if q = floor(p / 65537) then r = 0
89 // (note that p % 65537 == 1 so this is the only possibility)
90 pub(crate) fn mod_65537 (
91 builder: &mut CircuitBuilder::<GoldF, 2>,
92 a: Target,
93 ) -> Target {
94 let q = builder.add_virtual_target();
95 let r = builder.add_virtual_target();
96
97 // the Mod65537Generator will assign values to q and r later
98 builder.add_simple_generator( Mod65537Generator { a, q, r } );
99
100 // impose four constraints
101 // 1. a = 65537 * q + r
102 let t65537 = builder.constant(GoldF::from_canonical_u64(65537));
103 let a_copy = builder.mul_add(t65537, q, r);
104 builder.connect(a, a_copy);
105
106 // 2. 0 <= q <= floor(p / 65537)
107 // max_q is 281470681743360 = floor(p / 65537) = (p-1) / 65537 = 2^48 - 2^32
108 let max_q = builder.constant(GoldF::from_canonical_u64(281470681743360));
109 builder.range_check(q, 48);
110 let diff_q = builder.sub(max_q, q);
111 builder.range_check(diff_q, 48);
112
113 // 3. 0 <= r < 65537
114 let max_r = builder.constant(GoldF::from_canonical_u64(65537));
115 builder.range_check(r, 17);
116 let diff_r = builder.sub(max_r, r);
117 builder.range_check(diff_r, 17);
118
119 // 4. if q = floor(p / 65537) then r = 0
120 let q_equals_max = builder.is_equal(q, max_q);
121 let prod_temp = builder.mul(q_equals_max.target, r);
122 let zero_temp = builder.zero();
123 builder.connect(prod_temp, zero_temp);
124
125 // throw in the Generator to tell builder how to compute r
126 builder.add_simple_generator( Mod65537Generator {a, q, r} );
127
128 r
129 }
130}
131
132#[cfg(test)]
133mod tests {
134 use crate::mod65537::{Mod65537Builder, Mod65537Generator};
135 use crate::schnorr::{SchnorrPublicKey, SchnorrSecretKey, SchnorrSigner, SchnorrSignature};
136 use crate::schnorr_prover::{MessageTarget, SchnorrBuilder, SchnorrPublicKeyTarget, SchnorrSignatureTarget};
137 use plonky2::hash::poseidon::Poseidon;
138 use plonky2::iop::{
139 target::Target,
140 witness::{PartialWitness, PartitionWitness, Witness, WitnessWrite},
141 };
142 use plonky2::plonk::{
143 circuit_builder::CircuitBuilder,
144 circuit_data::{
145 CircuitConfig,
146 CircuitData,
147 CommonCircuitData,
148 VerifierCircuitData,
149 VerifierOnlyCircuitData
150 },
151 config::{GenericConfig, PoseidonGoldilocksConfig},
152 };
153 use plonky2::field::{
154 goldilocks_field::GoldilocksField,
155 types::Field,
156 };
157 use rand;
158
159 #[test]
160 fn test_mod65537() -> () {
161 const D: usize = 2;
162 const p: u64 = 18446744069414584321; // the Goldilocks prime
163 type C = PoseidonGoldilocksConfig;
164 type F = <C as GenericConfig<D>>::F;
165
166 let config = CircuitConfig::standard_recursion_config();
167 let mut builder = CircuitBuilder::<F, D>::new(config);
168
169 let a64: Vec<u64> = vec![0, 1, 2, 65535, 65536, 65537, p - 4, p - 3, p - 2, p - 1];
170
171 let a: Vec<Target> = a64
172 .iter()
173 .map(|x| builder.constant(GoldilocksField::from_canonical_u64(*x)))
174 .collect();
175
176 let r: Vec<Target> = a.iter()
177 .map(|targ| Mod65537Builder::mod_65537(&mut builder, *targ))
178 .collect();
179
180 // check that the outputs are correct,
181 // obviously you don't need this in your own code
182 let r_expected64: Vec<u64> = a64.iter().map(|x| x % 65537).collect();
183 println!("Expected residues mod 64: {:?}", r_expected64);
184 let r_expected: Vec<Target> = r_expected64.iter()
185 .map(|x| builder.constant(GoldilocksField::from_canonical_u64(*x)))
186 .collect();
187 r.iter().zip(r_expected.iter())
188 .for_each(|(x, y)| builder.connect(*x, *y));
189
190 let mut pw: PartialWitness<F> = PartialWitness::new();
191 let data = builder.build::<C>();
192 let proof = data.prove(pw).unwrap();
193
194 ()
195 }
196
197}