vdf_classgroup/lib.rs
1// Copyright 2018 Chia Network Inc and POA Networks Ltd.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14#![deny(unsafe_code)]
15// Legacy GMP FFI: duplicate `extern` prototypes vs `gmp::mpz`, extensive unsafe patterns.
16#![allow(clashing_extern_declarations)]
17#![allow(clippy::all)]
18#![allow(invalid_value)] // `mpz_t` stack slots: `uninitialized` then `__gmpz_init` (migrate to MaybeUninit)
19
20use num_traits::{One, Zero};
21use std::ops::{Mul, MulAssign, Rem, ShlAssign};
22
23pub mod gmp;
24
25pub mod gmp_classgroup;
26pub use self::gmp_classgroup::{
27 do_compute,
28 ffi::{export_obj, import_obj},
29};
30pub trait BigNum:
31 Zero
32 + One
33 + Clone
34 + PartialOrd
35 + std::fmt::Debug
36 + Rem
37 + ShlAssign<usize>
38 + for<'a> MulAssign<&'a Self>
39 + std::ops::Sub<u64, Output = Self>
40 + std::ops::Add<u64, Output = Self>
41 + std::convert::From<u64>
42 + for<'a> std::convert::From<&'a [u8]>
43 + std::ops::Shl<usize, Output = Self>
44 + std::ops::Shr<usize, Output = Self>
45 + std::ops::Neg<Output = Self>
46 + std::str::FromStr
47 + for<'a> std::ops::Div<&'a Self, Output = Self>
48 + Eq
49 + std::hash::Hash
50{
51 fn probab_prime(&self, iterations: u32) -> bool;
52 fn setbit(&mut self, offset: usize);
53 fn mod_powm(&mut self, base: &Self, exponent: &Self, modulus: &Self);
54}
55
56pub trait BigNumExt: BigNum {
57 fn frem_u32(&self, modulus: u32) -> u32;
58 fn crem_u16(&mut self, modulus: u16) -> u16;
59}
60
61pub trait ClassGroup:
62 Sized + Clone + for<'a> MulAssign<&'a Self> + for<'a> Mul<&'a Self> + PartialEq + std::fmt::Debug
63{
64 type BigNum: BigNum;
65
66 /// Produces a `Self` from `a`, `b`, and a discriminant.
67 fn from_ab_discriminant(a: Self::BigNum, b: Self::BigNum, discriminant: Self::BigNum) -> Self;
68
69 /// Unmarshals a `Self` from a byte array and discriminant.
70 ///
71 /// The byte array will be in the format of two big-endian byte sequences
72 /// concatenated together.
73 fn from_bytes(bytearray: &[u8], discriminant: Self::BigNum) -> Self;
74
75 /// Computes the identity element of `Self` for a given discriminant.
76 ///
77 /// If the discriminant is not valid, the result is unspecified.
78 ///
79 /// # Panics
80 ///
81 /// This may panic (but is not required to) if the discriminant is not
82 /// valid. If this function does not panic, the results of future
83 /// operations are unspecified: they will not invoke undefined behavior,
84 /// but may panic, loop forever, or just compute garbage.
85 ///
86 /// In debug builds, this will always panic if the discriminant is invalid.
87 fn identity_for_discriminant(discriminant: Self::BigNum) -> Self {
88 Self::from_ab_discriminant(Self::BigNum::one(), Self::BigNum::one(), discriminant)
89 }
90
91 /// Serializes `self` to a byte array. Returns `Err(s)` if there
92 /// is not enough space in the buffer.
93 ///
94 /// The data must be serialized in twos-complement, big-endian format.
95 fn serialize(&self, buf: &mut [u8]) -> std::result::Result<(), usize>;
96
97 /// Deserializes a bignum from raw bytes. The bytes **must** be interpreted
98 /// as a big-endian unsigned integer.
99 fn unsigned_deserialize_bignum(_: &[u8]) -> Self::BigNum;
100
101 /// Reduce `self` in-place.
102 fn reduce(&mut self);
103
104 /// Squares `self`, modifying it in-place.
105 ///
106 /// A default implementation is provided, but implementations are suggested
107 /// to override it for performance reasons.
108 fn square(&mut self) {
109 let s = self.clone();
110 self.mul_assign(&s)
111 }
112
113 /// Normalize `self`.
114 fn normalize(&mut self);
115
116 /// The length of `num` in **bits**
117 fn size_in_bits(num: &Self::BigNum) -> usize;
118
119 /// Gets the discriminant of `self`.
120 fn discriminant(&self) -> &Self::BigNum;
121
122 /// Computes the identity element of a `ClassGroup`.
123 fn identity(&self) -> Self {
124 Self::identity_for_discriminant(self.discriminant().clone())
125 }
126
127 /// Generates a *generator* for the class group of `Self`, given a
128 /// discriminant.
129 ///
130 /// If the discriminant is not valid, the result is unspecified.
131 ///
132 /// # Relation to `Self::identity_for_discriminant`
133 ///
134 /// This is *not* the same as `Self::identity_for_discriminant`: the
135 /// identity element is *never* a generator for *any* group. This follows
136 /// from their definitions: the identity element, when multiplied by another
137 /// element, always gives that other element, whereas *every* element in the
138 /// group is some power of a generator.
139 ///
140 /// # Panics
141 ///
142 /// This may panic (but is not required to) if the discriminant is not
143 /// valid. If this function does not panic, the results of future
144 /// operations are unspecified: they will not invoke undefined behavior,
145 /// but may panic, loop forever, or just compute garbage.
146 ///
147 /// If the global allocator panics on running out of memory, then this
148 /// function may panic in the same situation, but it may also just abort the
149 /// program instead.
150 ///
151 /// In debug builds, this will always panic if the discriminant is invalid.
152 fn generator_for_discriminant(discriminant: Self::BigNum) -> Self {
153 Self::from_ab_discriminant(2.into(), One::one(), discriminant)
154 }
155
156 /// Replaces `*self` with its inverse.
157 fn inverse(&mut self);
158
159 /// Squares `self` repeatedly in-place.
160 ///
161 /// Implementors of this trait are encouraged to override this
162 /// with a more efficient implementation, if one exists.
163 fn repeated_square(&mut self, iterations: u64) {
164 for _ in 0..iterations {
165 self.square()
166 }
167 }
168
169 /// Exponentiation
170 fn pow(&mut self, exponent: Self::BigNum);
171
172 /// Deserialization
173 fn deserialize(buf: &[u8], discriminant: Self::BigNum) -> Self;
174}
175
176#[cfg(test)]
177mod test {
178
179 use std::{
180 fs::File,
181 io::{BufRead, BufReader},
182 path::PathBuf,
183 };
184
185 use super::gmp::mpz::Mpz;
186 use super::{gmp_classgroup::GmpClassGroup, ClassGroup};
187
188 fn split_into_three_pieces(line: &str, c: char) -> [&str; 3] {
189 let mut iter = line.split(c);
190 let fst = iter.next().expect("bad test file");
191 let snd = iter.next().expect("bad test file");
192 let thd = iter.next().expect("bad test file");
193 assert!(iter.next().is_none(), "bad test file");
194 [fst, snd, thd]
195 }
196
197 #[test]
198 fn multiplication_is_correct() {
199 let manifest_path =
200 std::env::var("CARGO_MANIFEST_DIR").expect("cargo should have set this");
201 let mut path = PathBuf::from(&manifest_path);
202 path.push("tests/multiply.txt");
203 let mut f = BufReader::new(File::open(path).expect("test file missing or unreadable"));
204 let mut buffer = String::new();
205 loop {
206 let bytes_read = f
207 .read_line(&mut buffer)
208 .expect("could not read from test file");
209 assert!(bytes_read == buffer.len());
210 if bytes_read == 0 {
211 break;
212 }
213 if buffer.ends_with('\n') {
214 buffer.pop();
215 }
216 if buffer.ends_with('\r') {
217 buffer.pop();
218 }
219 let mut current_discriminant: Option<Mpz> = None;
220 let q: Vec<_> = split_into_three_pieces(&buffer, '|')
221 .iter()
222 .map(|i| {
223 let k = split_into_three_pieces(i, ',');
224
225 let a = Mpz::from_str_radix(k[0], 10).expect("bad test file");
226 let b = Mpz::from_str_radix(k[1], 10).expect("bad test file");
227 let c = Mpz::from_str_radix(k[2], 10).expect("bad test file");
228 let mut discriminant: Mpz = &b * &b;
229 let mut minuand: Mpz = (4u64).into();
230 minuand *= &a * &c;
231 discriminant -= &minuand;
232 assert!(discriminant < Mpz::zero());
233 // takes waaaay too long
234 // assert!(discriminant.probab_prime(20) !=
235 // gmp::mpz::ProbabPrimeResult::NotPrime);
236 if let Some(ref q) = current_discriminant {
237 assert_eq!(q, &discriminant, "mismatching discriminant in test files");
238 } else {
239 current_discriminant = Some(discriminant.clone());
240 }
241 GmpClassGroup::from_ab_discriminant(a, b, discriminant)
242 })
243 .collect();
244 assert_eq!(q.len(), 3);
245 if q[0] == q[1] {
246 let mut i = q[0].clone();
247 i.square();
248 assert_eq!(i, q[2]);
249 }
250 assert_eq!(&q[1] * &q[0], q[2], "multiplication not valid");
251 assert_eq!(&q[0] * &q[1], q[2], "multiplication not valid");
252 buffer.clear();
253 }
254 }
255}