dragoonfri 0.1.0

Fast Reed-solomon Interactive oracle proof of proximity
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

use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
use dragoonfri_test_utils::{
    do_for_multiple_folding_factors, Fq, BLOWUP_FACTOR, DOMAIN_SIZE, NUMBER_OF_POLYNOMIALS,
    NUM_QUERIES, POLY_COEFFS_LEN,
};
use rand::{thread_rng, Rng};
use winter_math::{fields::f128::BaseElement, FieldElement, StarkField};
use winter_rand_utils::{rand_value, rand_vector};
use winter_utils::transpose_slice;

use crate::{
    algorithms::Blake3,
    build_proof, commit_polynomial,
    folding::{reduce_polynomial, FoldedEvaluations},
    rng::FriChallenger,
    utils::to_evaluations,
    FriProof,
};

// This assumes winterfri is correct
#[test]
fn test_reduction() {
    for i in 0..NUMBER_OF_POLYNOMIALS {
        println!("    Testing on polynomial {i} / {NUMBER_OF_POLYNOMIALS}");

        let poly = rand_vector(POLY_COEFFS_LEN);
        let poly2 = convert_many(&poly);

        do_for_multiple_folding_factors!(FACTOR = 2, 4, 8, 16 => {
            println!("        --Folding factor={FACTOR}");
            let mut evaluations = prepare_winterfell_poly(poly.clone());
            let mut evaluations2 = to_evaluations(poly2.clone(), DOMAIN_SIZE);
            assert_eq!(convert_many(&evaluations), evaluations2);

            while evaluations.len() > FACTOR {
                let alpha = rand_value();
                let alpha2 = convert(&alpha);

                let transposed = transpose_slice::<_, FACTOR>(&evaluations);
                evaluations = winter_fri::folding::apply_drp(&transposed, BaseElement::ONE, alpha);
                let folded = FoldedEvaluations::new(&evaluations2);
                evaluations2 = reduce_polynomial::<FACTOR, _>(&folded, alpha2, None);

                assert_eq!(convert_many(&evaluations), evaluations2);
            }
        });
    }
}

#[test]
fn test_prove_verify() {
    let mut rng = thread_rng();
    let poly: Vec<Fq> = (0..POLY_COEFFS_LEN).map(|_| rng.gen()).collect();

    do_for_multiple_folding_factors!(FACTOR = 2, 4, 8, 16 => {
        println!("    --Folding factor={FACTOR}");

        let mut rng = FriChallenger::<Blake3>::default();
        let commitments = commit_polynomial::<FACTOR, _, Blake3, _>(poly.clone(), &mut rng, BLOWUP_FACTOR, 1);
        let proof = build_proof(commitments, &mut rng, NUM_QUERIES);

        rng.reset();
        assert!(proof.verify::<FACTOR, _>(rng.clone(), NUM_QUERIES, POLY_COEFFS_LEN, DOMAIN_SIZE).is_ok());

        assert!(proof.verify::<{FACTOR*2}, _>(rng.clone(), NUM_QUERIES, POLY_COEFFS_LEN, DOMAIN_SIZE).is_err());
        assert!(proof.verify::<{FACTOR/2}, _>(rng.clone(), NUM_QUERIES, POLY_COEFFS_LEN, DOMAIN_SIZE).is_err());

        assert!(proof.verify::<FACTOR, _>(rng.clone(), NUM_QUERIES, POLY_COEFFS_LEN, DOMAIN_SIZE * 2).is_err());
        assert!(proof.verify::<FACTOR, _>(rng.clone(), NUM_QUERIES, POLY_COEFFS_LEN, DOMAIN_SIZE / 2).is_err());

        assert!(proof.verify::<FACTOR, _>(rng.clone(), NUM_QUERIES, POLY_COEFFS_LEN / 2, DOMAIN_SIZE).is_err());

    });
}

#[test]
fn test_serialization() {
    let mut rng = thread_rng();
    let poly: Vec<Fq> = (0..POLY_COEFFS_LEN).map(|_| rng.gen()).collect();

    do_for_multiple_folding_factors!(FACTOR = 2, 4, 8, 16 => {
        println!("    --Folding factor={FACTOR}");

        let mut rng = FriChallenger::<Blake3>::default();
        let commitments = commit_polynomial::<FACTOR, _, Blake3, _>(poly.clone(), &mut rng, BLOWUP_FACTOR, 1);
        let proof = build_proof(commitments, &mut rng, NUM_QUERIES);

        let mut proof_bytes = vec![];
        proof.serialize_compressed(&mut proof_bytes).unwrap();

        let proof2 = FriProof::deserialize_compressed(&proof_bytes[..]).unwrap();
        assert_eq!(proof, proof2);

        rng.reset();
        proof2.verify::<FACTOR, _>(rng, NUM_QUERIES, POLY_COEFFS_LEN, DOMAIN_SIZE).unwrap();
    });
}

fn prepare_winterfell_poly<F: StarkField>(mut poly: Vec<F>) -> Vec<F> {
    use winter_math::fft::{evaluate_poly, get_twiddles};
    poly.resize(DOMAIN_SIZE, F::ZERO);
    let twiddles = get_twiddles(DOMAIN_SIZE);
    evaluate_poly(&mut poly, &twiddles);
    poly
}

fn convert(value: &BaseElement) -> Fq {
    Fq::from(value.as_int())
}

fn convert_many(values: &[BaseElement]) -> Vec<Fq> {
    values.iter().map(convert).collect()
}