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
use ;
use crate::;
use ;
/// The result of an sql query along with a proof that the query is valid. The
/// result and proof can be verified using commitments to database columns.
///
/// Note: the query result is stored in an intermediate form rather than the final form
/// the end-user sees. The final form is obtained after verification. Using an
/// intermediate form allows us to handle overflow and certain cases where the final
/// result might use floating point numbers (e.g. `SELECT STDDEV(A) FROM T WHERE B = 0`).
///
/// Below we demonstrate typical usage of [`VerifiableQueryResult`] with pseudo-code.
///
/// Here we assume that a verifier only has access to the commitments of database columns. To
/// process a query, the verifier forwards the query to an untrusted
/// prover. The prover has full access to the database and constructs a [`VerifiableQueryResult`] that
/// it sends back to the verifier. The verifier checks that the result is valid using its
/// commitments, and constructs the finalized form of the query result.
///
/// ```ignore
/// prover_process_query(database_accessor) {
/// query <- receive_query_from_verifier()
///
/// verifiable_result <- VerifiableQueryResult::new(query, database_accessor)
/// // When we construct VerifiableQueryResult from a query expression, we compute
/// // both the result of the query in intermediate form and the proof of the result
/// // at the same time.
///
/// send_to_verifier(verifiable_result)
/// }
///
/// verifier_process_query(query, commitment_accessor) {
/// verifiable_result <- send_query_to_prover(query)
///
/// verify_result <- verifiable_result.verify(query, commitment_accessor)
/// if verify_result.is_error() {
/// // The prover did something wrong. Perhaps the prover tried to tamper with the query
/// // result or maybe its version of the database was out-of-sync with the verifier's
/// // version.
/// do_verification_error()
/// }
///
/// query_result <- verify_result.query_result()
/// if query_result.is_error() {
/// // The prover processed the query correctly, but the query resulted in an error.
/// // For example, perhaps the query added two 64-bit integer columns together that
/// // resulted in an overflow.
/// do_query_error()
/// }
///
/// do_query_success(query_result)
/// // The prover correctly processed a query and the query succeeded. Now, we can
/// // proceed to use the result.
/// }
/// ```
///
/// Note: Because the class is deserialized from untrusted data, it
/// cannot maintain any invariant on its data members; hence, they are
/// all public so as to allow for easy manipulation for testing.