fastcrypto-tbls 0.1.0

Threshold BLS and DKG protocols
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204

// Copyright (c) 2022, Mysten Labs, Inc.
// SPDX-License-Identifier: Apache-2.0
//
// Most of the code below is based on code from https://github.com/celo-org/celo-threshold-bls-rs,
// modified for our needs.
//

use crate::polynomial::*;
use crate::types::ShareIndex;
use fastcrypto::groups::bls12381::{G1Element, G2Element, Scalar as BlsScalar};
use fastcrypto::groups::ristretto255::{RistrettoPoint, RistrettoScalar};
use fastcrypto::groups::{GroupElement, MultiScalarMul, Scalar};
use rand::prelude::*;
use std::num::NonZeroU16;

const I10: NonZeroU16 = unsafe { NonZeroU16::new_unchecked(10) };

#[generic_tests::define]
mod scalar_tests {
    use super::*;

    #[test]
    fn test_degree<S: Scalar>() {
        let s: usize = 5;
        let p = Poly::<S>::rand(s as u16, &mut thread_rng());
        assert_eq!(p.degree(), s);
    }

    #[test]
    fn add<S: Scalar>() {
        let p1 = Poly::<S>::rand(3, &mut thread_rng());
        let p2 = Poly::<S>::zero();
        let mut res = p1.clone();
        res += &p2;
        assert_eq!(res, p1);

        let p1 = Poly::<S>::zero();
        let p2 = Poly::<S>::rand(3, &mut thread_rng());
        let mut res = p1;
        res += &p2;
        assert_eq!(res, p2);

        let p1 = Poly::<S>::rand(3, &mut thread_rng());
        let p2 = Poly::<S>::rand(5, &mut thread_rng());
        let mut p3 = p1.clone();
        p3 += &p2;
        assert_eq!(p1.eval(I10).value + p2.eval(I10).value, p3.eval(I10).value);
    }

    #[test]
    fn test_recover_c0_errors<S: Scalar>() {
        let degree = 4;
        let threshold = degree + 1;
        let poly = Poly::<S>::rand(4, &mut thread_rng());
        // insufficient shares gathered
        let shares = (1..threshold).map(|i| poly.eval(ShareIndex::new(i).unwrap()));
        Poly::<S>::recover_c0(threshold, shares).unwrap_err();
        // duplications
        let shares = (1..=threshold)
            .map(|i| poly.eval(ShareIndex::new(i).unwrap()))
            .chain(std::iter::once(poly.eval(ShareIndex::new(1).unwrap()))); // duplicate value 1
        Poly::<S>::recover_c0(threshold, shares).unwrap_err();
    }

    #[test]
    fn test_recover_c0<S: Scalar>() {
        let poly = Poly::<S>::rand(123, &mut thread_rng());
        // insufficient shares gathered
        let mut shares = (1..300)
            .map(|i| poly.eval(ShareIndex::new(i).unwrap()))
            .collect::<Vec<_>>();
        let c0 = poly.c0();
        for _ in 0..10 {
            shares.shuffle(&mut thread_rng());
            let used_shares = shares.iter().take(124);
            assert_eq!(c0, &Poly::<S>::recover_c0(124, used_shares).unwrap());
        }
    }

    #[instantiate_tests(<RistrettoScalar>)]
    mod ristretto_scalar {}

    #[instantiate_tests(<BlsScalar>)]
    mod bls_scalar {}
}

#[generic_tests::define]
mod points_tests {
    use super::*;
    use itertools::Either;

    #[test]
    fn test_eval_and_commit<G: GroupElement>() {
        // test zero
        let p = Poly::<G::ScalarType>::zero();
        assert_eq!(p.eval(I10).value, G::ScalarType::zero());
        // test consistency
        let p = Poly::<G::ScalarType>::rand(5, &mut thread_rng());
        let e1 = p.eval(I10);
        let public_p = p.commit();
        let e2 = public_p.eval(I10);
        assert_eq!(e1.index, e2.index);
        assert_eq!(G::generator() * e1.value, e2.value);
        assert!(public_p.verify_share(e1.index, &e1.value).is_ok());
        // test simple poly
        let one = G::ScalarType::generator();
        let coeff = vec![one, one, one];
        let p = Poly::<G::ScalarType>::from(coeff);
        assert_eq!(p.degree(), 2);
        let s1 = p.eval(NonZeroU16::new(10).unwrap());
        let s2 = p.eval(NonZeroU16::new(20).unwrap());
        let s3 = p.eval(NonZeroU16::new(30).unwrap());
        let shares = vec![s1, s2, s3];
        assert_eq!(
            Poly::<G::ScalarType>::recover_c0(3, shares.iter()).unwrap(),
            one
        );
    }

    #[test]
    fn test_recover_c0_msm_errors<G: GroupElement + MultiScalarMul>() {
        let degree = 4;
        let threshold = degree + 1;
        let poly = Poly::<G::ScalarType>::rand(4, &mut thread_rng());
        let poly_g = poly.commit();
        // insufficient shares gathered
        let shares = (1..threshold).map(|i| poly_g.eval(ShareIndex::new(i).unwrap()));
        Poly::<G>::recover_c0_msm(threshold, shares).unwrap_err();
        // duplications
        let shares = (1..threshold)
            .map(|i| poly_g.eval(ShareIndex::new(i).unwrap()))
            .chain(std::iter::once(poly_g.eval(ShareIndex::new(1).unwrap()))); // duplicate value 1
        Poly::<G>::recover_c0_msm(threshold, shares).unwrap_err();
    }

    #[test]
    fn test_recover_c0_msm<G: GroupElement + MultiScalarMul>() {
        let one = G::generator();
        let coeff = vec![one, one, one];
        let p = Poly::<G>::from(coeff);
        assert_eq!(p.degree(), 2);
        let s1 = p.eval(NonZeroU16::new(10).unwrap());
        let s2 = p.eval(NonZeroU16::new(20).unwrap());
        let s3 = p.eval(NonZeroU16::new(30).unwrap());
        let shares = vec![s1, s2, s3];
        assert_eq!(Poly::<G>::recover_c0_msm(3, shares.iter()).unwrap(), one);

        // and random tests
        let poly = Poly::<G::ScalarType>::rand(123, &mut thread_rng());
        let poly_g = poly.commit();
        // insufficient shares gathered
        let mut shares = (1..200)
            .map(|i| poly_g.eval(ShareIndex::new(i).unwrap()))
            .collect::<Vec<_>>();
        let c0 = poly_g.c0();
        for _ in 0..10 {
            shares.shuffle(&mut thread_rng());
            let used_shares = shares.iter().take(124);
            assert_eq!(c0, &Poly::<G>::recover_c0_msm(124, used_shares).unwrap());
        }
    }

    #[test]
    fn test_fast_mult<G: GroupElement>() {
        let x = 1u128 << 109; // 110 bit set
        let y = 1u128 << 17; // 18 bit set
        assert!(Poly::<G::ScalarType>::fast_mult(x, y) == Either::Right(x * y));

        let x = 1u128 << 17;
        let y = 1u128 << 109;
        assert!(Poly::<G::ScalarType>::fast_mult(x, y) == Either::Right(x * y));

        let x = 1u128 << (109 - 1); // all 109 bits set
        let y = 1u128 << (19 - 1); // all 19 bits set
        assert!(Poly::<G::ScalarType>::fast_mult(x, y) == Either::Right(x * y));

        let x = 1u128 << 120;
        let y = 1u128 << 13;
        assert!(
            Poly::<G::ScalarType>::fast_mult(x, y) == Either::Left((G::ScalarType::from(x), y))
        );

        let x = 1u128 << 21;
        let y = 1u128 << 120;
        assert!(
            Poly::<G::ScalarType>::fast_mult(x, y) == Either::Left((G::ScalarType::from(x), y))
        );

        let x = std::u128::MAX;
        let y = 1u128;
        assert!(
            Poly::<G::ScalarType>::fast_mult(x, y) == Either::Left((G::ScalarType::from(x), y))
        );
    }

    #[instantiate_tests(<RistrettoPoint>)]
    mod ristretto_point {}

    #[instantiate_tests(<G1Element>)]
    mod g1_element {}

    #[instantiate_tests(<G2Element>)]
    mod g2_element {}
}