proof-of-sql 0.129.1

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

use crate::{
    base::{
        polynomial::interpolate_evaluations_to_reverse_coefficients,
        proof::{ProofError, Transcript},
        scalar::Scalar,
    },
    proof_primitive::sumcheck::{prove_round, ProverState},
    utils::log,
};
/*
 * Adapted from arkworks
 *
 * See third_party/license/arkworks.LICENSE
 */
use alloc::vec::Vec;
use serde::{Deserialize, Serialize};

#[derive(Clone, Debug, Serialize, Deserialize)]
pub struct SumcheckProof<S: Scalar> {
    pub(super) coefficients: Vec<S>,
}
pub struct Subclaim<S: Scalar> {
    pub evaluation_point: Vec<S>,
    pub expected_evaluation: S,
    pub max_multiplicands: usize,
}

impl<S: Scalar> SumcheckProof<S> {
    #[tracing::instrument(name = "SumcheckProof::create", level = "debug", skip_all)]
    pub fn create(
        transcript: &mut impl Transcript,
        evaluation_point: &mut [S],
        mut state: ProverState<S>,
    ) -> Self {
        log::log_memory_usage("Start");

        assert_eq!(evaluation_point.len(), state.num_vars);
        transcript.extend_as_be([((state.max_multiplicands + 1) * state.num_vars) as u64]);
        // This challenge is in order to keep transcript messages grouped. (This simplifies the Solidity implementation.)
        transcript.scalar_challenge_as_be::<S>();
        let mut r = None;
        let mut coefficients = Vec::with_capacity(state.max_multiplicands * state.num_vars);
        for scalar in evaluation_point.iter_mut().take(state.num_vars) {
            let round_evaluations = prove_round(&mut state, &r);
            let round_coefficients =
                interpolate_evaluations_to_reverse_coefficients(&round_evaluations);
            transcript.extend_scalars_as_be(&round_coefficients);
            coefficients.extend(round_coefficients);
            *scalar = transcript.scalar_challenge_as_be();
            r = Some(*scalar);
        }

        log::log_memory_usage("End");

        SumcheckProof { coefficients }
    }

    #[tracing::instrument(
        name = "SumcheckProof::verify_without_evaluation",
        level = "debug",
        skip_all
    )]
    pub fn verify_without_evaluation(
        &self,
        transcript: &mut impl Transcript,
        num_variables: usize,
        claimed_sum: &S,
    ) -> Result<Subclaim<S>, ProofError> {
        log::log_memory_usage("Start");

        let coefficients_len = self.coefficients.len();
        if !coefficients_len.is_multiple_of(num_variables) {
            return Err(ProofError::VerificationError {
                error: "invalid proof size",
            });
        }
        let max_multiplicands = (coefficients_len / num_variables) - 1;
        transcript.extend_as_be([coefficients_len as u64]);
        // This challenge is in order to keep transcript messages grouped. (This simplifies the Solidity implementation.)
        transcript.scalar_challenge_as_be::<S>();
        let mut evaluation_point = Vec::with_capacity(num_variables);

        let mut expected_evaluation = *claimed_sum;
        for round_index in 0..num_variables {
            let start_index = round_index * (max_multiplicands + 1);
            transcript.extend_scalars_as_be(
                &self.coefficients[start_index..=(start_index + max_multiplicands)],
            );
            let round_evaluation_point = transcript.scalar_challenge_as_be();
            evaluation_point.push(round_evaluation_point);
            let mut round_evaluation = self.coefficients[start_index];
            let mut actual_sum =
                round_evaluation + self.coefficients[start_index + max_multiplicands];
            for coefficient_index in (start_index + 1)..=(start_index + max_multiplicands) {
                round_evaluation *= round_evaluation_point;
                round_evaluation += self.coefficients[coefficient_index];
                actual_sum += self.coefficients[coefficient_index];
            }
            if actual_sum != expected_evaluation {
                return Err(ProofError::VerificationError {
                    error: "round evaluation does not match claimed sum",
                });
            }
            expected_evaluation = round_evaluation;
        }

        log::log_memory_usage("End");

        Ok(Subclaim {
            evaluation_point,
            expected_evaluation,
            max_multiplicands,
        })
    }
}