grovedb/operations/proof/
mod.rs

1//! Proof operations
2
3#[cfg(feature = "minimal")]
4mod generate;
5pub mod util;
6mod verify;
7
8use std::{collections::BTreeMap, fmt};
9
10use bincode::{Decode, Encode};
11use grovedb_merk::{
12    proofs::{
13        query::{Key, VerifyOptions},
14        Decoder, Node, Op,
15    },
16    CryptoHash,
17};
18use grovedb_version::version::GroveVersion;
19
20use crate::{
21    operations::proof::util::{element_hex_to_ascii, hex_to_ascii, ProvedPathKeyValues},
22    query_result_type::PathKeyOptionalElementTrio,
23    Error, GroveDb, PathQuery,
24};
25
26#[derive(Debug, Clone, Copy, Encode, Decode)]
27pub struct ProveOptions {
28    /// This tells the proof system to decrease the available limit of the query
29    /// by 1 in the case of empty subtrees. Generally this should be set to
30    /// true. The case where this could be set to false is if there is a
31    /// known structure where we know that there are only a few empty
32    /// subtrees.
33    ///
34    /// !!! Warning !!! Be very careful:
35    /// If this is set to `false` then you must be sure that the sub queries do
36    /// not match many trees, Otherwise you could crash the system as the
37    /// proof system goes through millions of subtrees and eventually runs
38    /// out of memory
39    pub decrease_limit_on_empty_sub_query_result: bool,
40}
41
42impl fmt::Display for ProveOptions {
43    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
44        write!(
45            f,
46            "ProveOptions {{ decrease_limit_on_empty_sub_query_result: {} }}",
47            self.decrease_limit_on_empty_sub_query_result
48        )
49    }
50}
51
52impl Default for ProveOptions {
53    fn default() -> Self {
54        ProveOptions {
55            decrease_limit_on_empty_sub_query_result: true,
56        }
57    }
58}
59
60#[derive(Encode, Decode)]
61pub struct LayerProof {
62    pub merk_proof: Vec<u8>,
63    pub lower_layers: BTreeMap<Key, LayerProof>,
64}
65
66#[derive(Encode, Decode)]
67pub enum GroveDBProof {
68    V0(GroveDBProofV0),
69}
70
71impl GroveDBProof {
72    /// Verifies a query with options using the proof and returns the root hash
73    /// and the query result.
74    pub fn verify_with_options(
75        &self,
76        query: &PathQuery,
77        options: VerifyOptions,
78        grove_version: &GroveVersion,
79    ) -> Result<(CryptoHash, Vec<PathKeyOptionalElementTrio>), Error> {
80        GroveDb::verify_proof_internal(self, query, options, grove_version)
81            .map(|(root_hash, _, results)| (root_hash, results))
82    }
83
84    /// Verifies a raw query using the proof and returns the root hash and the
85    /// query result.
86    pub fn verify_raw(
87        &self,
88        query: &PathQuery,
89        grove_version: &GroveVersion,
90    ) -> Result<(CryptoHash, ProvedPathKeyValues), Error> {
91        GroveDb::verify_proof_raw_internal(
92            self,
93            query,
94            VerifyOptions {
95                absence_proofs_for_non_existing_searched_keys: false,
96                verify_proof_succinctness: false,
97                include_empty_trees_in_result: true,
98            },
99            grove_version,
100        )
101        .map(|(root_hash, _, results)| (root_hash, results))
102    }
103
104    /// Verifies a query using the proof and returns the root hash and the query
105    /// result.
106    pub fn verify(
107        &self,
108        query: &PathQuery,
109        grove_version: &GroveVersion,
110    ) -> Result<(CryptoHash, Vec<PathKeyOptionalElementTrio>), Error> {
111        GroveDb::verify_proof_internal(
112            self,
113            query,
114            VerifyOptions {
115                absence_proofs_for_non_existing_searched_keys: false,
116                verify_proof_succinctness: true,
117                include_empty_trees_in_result: false,
118            },
119            grove_version,
120        )
121        .map(|(root_hash, _, results)| (root_hash, results))
122    }
123
124    /// Verifies a query with an absence proof and returns the root hash and the
125    /// query result.
126    pub fn verify_with_absence_proof(
127        &self,
128        query: &PathQuery,
129        grove_version: &GroveVersion,
130    ) -> Result<(CryptoHash, Vec<PathKeyOptionalElementTrio>), Error> {
131        GroveDb::verify_proof_internal(
132            self,
133            query,
134            VerifyOptions {
135                absence_proofs_for_non_existing_searched_keys: true,
136                verify_proof_succinctness: true,
137                include_empty_trees_in_result: false,
138            },
139            grove_version,
140        )
141        .map(|(root_hash, _, results)| (root_hash, results))
142    }
143
144    /// Verifies a subset query using the proof and returns the root hash and
145    /// the query result.
146    pub fn verify_subset(
147        &self,
148        query: &PathQuery,
149        grove_version: &GroveVersion,
150    ) -> Result<(CryptoHash, Vec<PathKeyOptionalElementTrio>), Error> {
151        GroveDb::verify_proof_internal(
152            self,
153            query,
154            VerifyOptions {
155                absence_proofs_for_non_existing_searched_keys: false,
156                verify_proof_succinctness: false,
157                include_empty_trees_in_result: false,
158            },
159            grove_version,
160        )
161        .map(|(root_hash, _, results)| (root_hash, results))
162    }
163
164    /// Verifies a subset query with an absence proof using the proof and
165    /// returns the root hash and the query result.
166    pub fn verify_subset_with_absence_proof(
167        &self,
168        query: &PathQuery,
169        grove_version: &GroveVersion,
170    ) -> Result<(CryptoHash, Vec<PathKeyOptionalElementTrio>), Error> {
171        GroveDb::verify_proof_internal(
172            self,
173            query,
174            VerifyOptions {
175                absence_proofs_for_non_existing_searched_keys: true,
176                verify_proof_succinctness: false,
177                include_empty_trees_in_result: false,
178            },
179            grove_version,
180        )
181        .map(|(root_hash, _, results)| (root_hash, results))
182    }
183}
184
185#[derive(Encode, Decode)]
186pub struct GroveDBProofV0 {
187    pub root_layer: LayerProof,
188    pub prove_options: ProveOptions,
189}
190
191impl fmt::Display for LayerProof {
192    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
193        writeln!(f, "LayerProof {{")?;
194        writeln!(f, "  merk_proof: {}", decode_merk_proof(&self.merk_proof))?;
195        if !self.lower_layers.is_empty() {
196            writeln!(f, "  lower_layers: {{")?;
197            for (key, layer_proof) in &self.lower_layers {
198                writeln!(f, "    {} => {{", hex_to_ascii(key))?;
199                for line in format!("{}", layer_proof).lines() {
200                    writeln!(f, "      {}", line)?;
201                }
202                writeln!(f, "    }}")?;
203            }
204            writeln!(f, "  }}")?;
205        }
206        write!(f, "}}")
207    }
208}
209
210impl fmt::Display for GroveDBProof {
211    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
212        match self {
213            GroveDBProof::V0(proof) => write!(f, "{}", proof),
214        }
215    }
216}
217
218impl fmt::Display for GroveDBProofV0 {
219    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
220        writeln!(f, "GroveDBProofV0 {{")?;
221        for line in format!("{}", self.root_layer).lines() {
222            writeln!(f, "  {}", line)?;
223        }
224        write!(f, "}}")
225    }
226}
227
228fn decode_merk_proof(proof: &[u8]) -> String {
229    let mut result = String::new();
230    let ops = Decoder::new(proof);
231
232    for (i, op) in ops.enumerate() {
233        match op {
234            Ok(op) => {
235                result.push_str(&format!("\n    {}: {}", i, op_to_string(&op)));
236            }
237            Err(e) => {
238                result.push_str(&format!("\n    {}: Error decoding op: {}", i, e));
239            }
240        }
241    }
242
243    result
244}
245
246fn op_to_string(op: &Op) -> String {
247    match op {
248        Op::Push(node) => format!("Push({})", node_to_string(node)),
249        Op::PushInverted(node) => format!("PushInverted({})", node_to_string(node)),
250        Op::Parent => "Parent".to_string(),
251        Op::Child => "Child".to_string(),
252        Op::ParentInverted => "ParentInverted".to_string(),
253        Op::ChildInverted => "ChildInverted".to_string(),
254    }
255}
256
257fn node_to_string(node: &Node) -> String {
258    match node {
259        Node::Hash(hash) => format!("Hash(HASH[{}])", hex::encode(hash)),
260        Node::KVHash(kv_hash) => format!("KVHash(HASH[{}])", hex::encode(kv_hash)),
261        Node::KV(key, value) => {
262            format!("KV({}, {})", hex_to_ascii(key), element_hex_to_ascii(value))
263        }
264        Node::KVValueHash(key, value, value_hash) => format!(
265            "KVValueHash({}, {}, HASH[{}])",
266            hex_to_ascii(key),
267            element_hex_to_ascii(value),
268            hex::encode(value_hash)
269        ),
270        Node::KVDigest(key, value_hash) => format!(
271            "KVDigest({}, HASH[{}])",
272            hex_to_ascii(key),
273            hex::encode(value_hash)
274        ),
275        Node::KVRefValueHash(key, value, value_hash) => format!(
276            "KVRefValueHash({}, {}, HASH[{}])",
277            hex_to_ascii(key),
278            element_hex_to_ascii(value),
279            hex::encode(value_hash)
280        ),
281        Node::KVValueHashFeatureType(key, value, value_hash, feature_type) => format!(
282            "KVValueHashFeatureType({}, {}, HASH[{}], {:?})",
283            hex_to_ascii(key),
284            element_hex_to_ascii(value),
285            hex::encode(value_hash),
286            feature_type
287        ),
288    }
289}
grovedb/operations/proof/mod.rs

grovedb/operations/proof/
mod.rs
