proof-of-sql 0.129.0

High performance zero knowledge (ZK) prover for SQL.
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

use super::CompositePolynomialBuilder;
use crate::proof_primitive::inner_product::curve_25519_scalar::Curve25519Scalar;
use num_traits::One;

#[test]
fn we_combine_single_degree_fr_multiplicands() {
    let fr = [Curve25519Scalar::from(1u64), Curve25519Scalar::from(2u64)];
    let mle1 = [10, 20];
    let mle2 = [11, 21];
    let mut builder = CompositePolynomialBuilder::new(1, &fr);
    builder.produce_fr_multiplicand(&One::one(), &[Box::new(&mle1)]);
    builder.produce_fr_multiplicand(&-Curve25519Scalar::one(), &[Box::new(&mle2)]);
    let p = builder.make_composite_polynomial();
    assert_eq!(p.products.len(), 1);
    assert_eq!(p.flattened_ml_extensions.len(), 2);
    let pt = [Curve25519Scalar::from(9_268_764_u64)];
    let m0 = Curve25519Scalar::one() - pt[0];
    let m1 = pt[0];
    let eval1 = Curve25519Scalar::from(mle1[0]) * m0 + Curve25519Scalar::from(mle1[1]) * m1;
    let eval2 = Curve25519Scalar::from(mle2[0]) * m0 + Curve25519Scalar::from(mle2[1]) * m1;
    let eval_fr = fr[0] * m0 + fr[1] * m1;
    let expected = eval_fr * (eval1 - eval2);
    assert_eq!(p.evaluate(&pt), expected);
}

#[test]
fn we_dont_duplicate_repeated_mles() {
    let fr = [Curve25519Scalar::from(1u64), Curve25519Scalar::from(2u64)];
    let mle1 = [10, 20];
    let mle2 = [11, 21];
    let mut builder = CompositePolynomialBuilder::new(1, &fr);
    builder.produce_fr_multiplicand(&One::one(), &[Box::new(&mle1), Box::new(&mle1)]);
    builder.produce_fr_multiplicand(&One::one(), &[Box::new(&mle1), Box::new(&mle2)]);
    let p = builder.make_composite_polynomial();
    assert_eq!(p.products.len(), 3);
    assert_eq!(p.flattened_ml_extensions.len(), 5);
    let pt = [Curve25519Scalar::from(9_268_764_u64)];
    let m0 = Curve25519Scalar::one() - pt[0];
    let m1 = pt[0];
    let eval1 = Curve25519Scalar::from(mle1[0]) * m0 + Curve25519Scalar::from(mle1[1]) * m1;
    let eval2 = Curve25519Scalar::from(mle2[0]) * m0 + Curve25519Scalar::from(mle2[1]) * m1;
    let eval_fr = fr[0] * m0 + fr[1] * m1;
    let expected = eval_fr * (eval1 * eval1 + eval1 * eval2);
    assert_eq!(p.evaluate(&pt), expected);
}

#[test]
fn we_can_combine_identity_with_zero_sum_polynomials() {
    let fr = [Curve25519Scalar::from(1u64), Curve25519Scalar::from(2u64)];
    let mle1 = [10, 20];
    let mle2 = [11, 21];
    let mle3 = [12, 22];
    let mle4 = [13, 23];
    let mut builder = CompositePolynomialBuilder::new(1, &fr);
    builder.produce_fr_multiplicand(&One::one(), &[Box::new(&mle1), Box::new(&mle2)]);
    builder.produce_zerosum_multiplicand(
        &-Curve25519Scalar::one(),
        &[Box::new(&mle3), Box::new(&mle4)],
    );
    let p = builder.make_composite_polynomial();
    assert_eq!(p.products.len(), 3); //1 for the linear term, 1 for the fr multiplicand, 1 for the zerosum multiplicand
    assert_eq!(p.flattened_ml_extensions.len(), 6); //1 for fr, 1 for the linear term, and 4 for mle1-4
    let pt = [Curve25519Scalar::from(9_268_764_u64)];
    let m0 = Curve25519Scalar::one() - pt[0];
    let m1 = pt[0];
    let eval1 = Curve25519Scalar::from(mle1[0]) * m0 + Curve25519Scalar::from(mle1[1]) * m1;
    let eval2 = Curve25519Scalar::from(mle2[0]) * m0 + Curve25519Scalar::from(mle2[1]) * m1;
    let eval3 = Curve25519Scalar::from(mle3[0]) * m0 + Curve25519Scalar::from(mle3[1]) * m1;
    let eval4 = Curve25519Scalar::from(mle4[0]) * m0 + Curve25519Scalar::from(mle4[1]) * m1;
    let eval_fr = fr[0] * m0 + fr[1] * m1;
    let expected = eval_fr * eval1 * eval2 - eval3 * eval4;
    assert_eq!(p.evaluate(&pt), expected);
}

#[test]
fn we_can_handle_only_an_empty_fr_multiplicand() {
    let fr = [Curve25519Scalar::from(1u64), Curve25519Scalar::from(2u64)];
    let mut builder = CompositePolynomialBuilder::new(1, &fr);
    builder.produce_fr_multiplicand(&Curve25519Scalar::from(17), &[]);
    let p = builder.make_composite_polynomial();
    assert_eq!(p.products.len(), 1); //1 for the fr multiplicand
    assert_eq!(p.flattened_ml_extensions.len(), 2); //1 for fr, 1 for the linear term
    let pt = [Curve25519Scalar::from(9_268_764_u64)];
    let m0 = Curve25519Scalar::one() - pt[0];
    let m1 = pt[0];
    let eval1 = (m0 + m1) * Curve25519Scalar::from(17);
    let eval_fr = fr[0] * m0 + fr[1] * m1;
    let expected = eval_fr * eval1;
    assert_eq!(p.evaluate(&pt), expected);
}

#[test]
fn we_can_handle_empty_terms_with_other_terms() {
    let fr = [Curve25519Scalar::from(1u64), Curve25519Scalar::from(2u64)];
    let mle1 = [10, 20];
    let mle2 = [11, 21];
    let mle3 = [12, 22];
    let mle4 = [13, 23];
    let mut builder = CompositePolynomialBuilder::new(1, &fr);
    builder.produce_fr_multiplicand(&One::one(), &[Box::new(&mle1), Box::new(&mle2)]);
    builder.produce_fr_multiplicand(&Curve25519Scalar::from(17), &[]);
    builder.produce_zerosum_multiplicand(
        &-Curve25519Scalar::one(),
        &[Box::new(&mle3), Box::new(&mle4)],
    );
    let p = builder.make_composite_polynomial();
    assert_eq!(p.products.len(), 3); //1 for the linear term, 1 for the fr multiplicand, 1 for the zerosum multiplicand
    assert_eq!(p.flattened_ml_extensions.len(), 6); //1 for fr, 1 for the linear term, and 4 for mle1-4
    let pt = [Curve25519Scalar::from(9_268_764_u64)];
    let m0 = Curve25519Scalar::one() - pt[0];
    let m1 = pt[0];
    let eval1 = Curve25519Scalar::from(mle1[0]) * m0 + Curve25519Scalar::from(mle1[1]) * m1;
    let eval2 = Curve25519Scalar::from(mle2[0]) * m0 + Curve25519Scalar::from(mle2[1]) * m1;
    let eval3 = Curve25519Scalar::from(mle3[0]) * m0 + Curve25519Scalar::from(mle3[1]) * m1;
    let eval4 = Curve25519Scalar::from(mle4[0]) * m0 + Curve25519Scalar::from(mle4[1]) * m1;
    let eval_fr = fr[0] * m0 + fr[1] * m1;
    let expected = eval_fr * (eval1 * eval2 + Curve25519Scalar::from(17)) - eval3 * eval4;
    assert_eq!(p.evaluate(&pt), expected);
}