commonware_storage/qmdb/
verify.rs

1use crate::mmr::{
2    proof, verification, verification::ProofStore, Error, Location, Position, Proof,
3    StandardHasher as Standard,
4};
5use commonware_codec::Encode;
6use commonware_cryptography::{Digest, Hasher};
7use core::ops::Range;
8
9/// Verify that a [Proof] is valid for a range of operations and a target root.
10pub fn verify_proof<Op, H, D>(
11    hasher: &mut Standard<H>,
12    proof: &Proof<D>,
13    start_loc: Location,
14    operations: &[Op],
15    target_root: &D,
16) -> bool
17where
18    Op: Encode,
19    H: Hasher<Digest = D>,
20    D: Digest,
21{
22    let elements = operations.iter().map(|op| op.encode()).collect::<Vec<_>>();
23    proof.verify_range_inclusion(hasher, &elements, start_loc, target_root)
24}
25
26/// Extract pinned nodes from the [Proof] starting at `start_loc`.
27///
28/// # Errors
29///
30/// Returns [Error::LocationOverflow] if `start_loc + operations_len` > [crate::mmr::MAX_LOCATION].
31pub fn extract_pinned_nodes<D: Digest>(
32    proof: &Proof<D>,
33    start_loc: Location,
34    operations_len: u64,
35) -> Result<Vec<D>, Error> {
36    let Some(end_loc) = start_loc.checked_add(operations_len) else {
37        return Err(Error::LocationOverflow(start_loc));
38    };
39    proof.extract_pinned_nodes(start_loc..end_loc)
40}
41
42/// Verify that a [Proof] is valid for a range of operations and extract all digests (and their positions)
43/// in the range of the [Proof].
44pub fn verify_proof_and_extract_digests<Op, H, D>(
45    hasher: &mut Standard<H>,
46    proof: &Proof<D>,
47    start_loc: Location,
48    operations: &[Op],
49    target_root: &D,
50) -> Result<Vec<(Position, D)>, Error>
51where
52    Op: Encode,
53    H: Hasher<Digest = D>,
54    D: Digest,
55{
56    let elements = operations.iter().map(|op| op.encode()).collect::<Vec<_>>();
57    proof.verify_range_inclusion_and_extract_digests(hasher, &elements, start_loc, target_root)
58}
59
60/// Calculate the digests required to construct a [Proof] for a range of operations.
61///
62/// # Errors
63///
64/// Returns [crate::mmr::Error::LocationOverflow] if `op_count` or an element in `range` >
65/// [crate::mmr::MAX_LOCATION].
66///
67/// Returns [crate::mmr::Error::RangeOutOfBounds] if the last element position in `range`
68/// is out of bounds for the MMR size.
69pub fn digests_required_for_proof<D: Digest>(
70    op_count: Location,
71    range: Range<Location>,
72) -> Result<Vec<Position>, crate::mmr::Error> {
73    let mmr_size = Position::try_from(op_count)?;
74    proof::nodes_required_for_range_proof(mmr_size, range)
75}
76
77/// Create a [Proof] from a op_count and a list of digests.
78///
79/// To compute the digests required for a [Proof], use [digests_required_for_proof].
80///
81/// # Errors
82///
83/// Returns [crate::mmr::Error::LocationOverflow] if `op_count` > [crate::mmr::MAX_LOCATION].
84pub fn create_proof<D: Digest>(
85    op_count: Location,
86    digests: Vec<D>,
87) -> Result<Proof<D>, crate::mmr::Error> {
88    Ok(Proof::<D> {
89        size: Position::try_from(op_count)?,
90        digests,
91    })
92}
93
94/// Verify a [Proof] and convert it into a [ProofStore].
95pub fn create_proof_store<Op, H, D>(
96    hasher: &mut Standard<H>,
97    proof: &Proof<D>,
98    start_loc: Location,
99    operations: &[Op],
100    root: &D,
101) -> Result<ProofStore<D>, Error>
102where
103    Op: Encode,
104    H: Hasher<Digest = D>,
105    D: Digest,
106{
107    // Encode operations for verification
108    let elements = operations.iter().map(|op| op.encode()).collect::<Vec<_>>();
109
110    // Create ProofStore by verifying the proof and extracting all digests
111    ProofStore::new(hasher, proof, &elements, start_loc, root)
112}
113
114/// Create a [ProofStore] from a list of digests (output by [verify_proof_and_extract_digests]).
115///
116/// If you have not yet verified the proof, use [create_proof_store] instead.
117pub fn create_proof_store_from_digests<D: Digest>(
118    proof: &Proof<D>,
119    digests: Vec<(Position, D)>,
120) -> ProofStore<D> {
121    ProofStore::new_from_digests(proof.size, digests)
122}
123
124/// Create a Multi-Proof for specific operations (identified by location) from a [ProofStore].
125pub async fn create_multi_proof<D: Digest>(
126    proof_store: &ProofStore<D>,
127    locations: &[Location],
128) -> Result<Proof<D>, Error> {
129    // Generate the proof
130    verification::multi_proof(proof_store, locations).await
131}
132
133/// Verify a Multi-Proof for operations at specific locations.
134pub fn verify_multi_proof<Op, H, D>(
135    hasher: &mut Standard<H>,
136    proof: &Proof<D>,
137    operations: &[(Location, Op)],
138    target_root: &D,
139) -> bool
140where
141    Op: Encode,
142    H: Hasher<Digest = D>,
143    D: Digest,
144{
145    // Encode operations and convert locations to positions
146    let elements = operations
147        .iter()
148        .map(|(loc, op)| (op.encode(), *loc))
149        .collect::<Vec<_>>();
150
151    // Verify the proof
152    proof.verify_multi_inclusion(hasher, &elements, target_root)
153}
154
155#[cfg(test)]
156mod tests {
157    use super::*;
158    use crate::mmr::{iterator::nodes_to_pin, location::LocationRangeExt as _, mem::CleanMmr};
159    use commonware_cryptography::{sha256::Digest, Sha256};
160    use commonware_macros::test_traced;
161    use commonware_runtime::{deterministic, Runner};
162
163    fn test_digest(v: u8) -> Digest {
164        Sha256::hash(&[v])
165    }
166
167    fn test_hasher() -> Standard<Sha256> {
168        Standard::new()
169    }
170
171    #[test_traced]
172    fn test_verify_proof() {
173        let executor = deterministic::Runner::default();
174        executor.start(|_| async move {
175            let mut hasher = test_hasher();
176            let mut mmr = CleanMmr::new(&mut hasher);
177
178            // Add some operations to the MMR
179            let operations = vec![1, 2, 3];
180            let mut positions = Vec::new();
181            for op in &operations {
182                let encoded = op.encode();
183                let pos = mmr.add(&mut hasher, &encoded);
184                positions.push(pos);
185            }
186            let root = mmr.root();
187
188            // Generate proof for all operations
189            let proof = mmr
190                .range_proof(Location::new_unchecked(0)..Location::new_unchecked(3))
191                .unwrap();
192
193            // Verify the proof
194            assert!(verify_proof(
195                &mut hasher,
196                &proof,
197                Location::new_unchecked(0), // start_loc
198                &operations,
199                root,
200            ));
201
202            // Verify the proof with the wrong root
203            let wrong_root = test_digest(99);
204            assert!(!verify_proof(
205                &mut hasher,
206                &proof,
207                Location::new_unchecked(0),
208                &operations,
209                &wrong_root,
210            ));
211
212            // Verify the proof with the wrong operations
213            let wrong_operations = vec![9, 10, 11];
214            assert!(!verify_proof(
215                &mut hasher,
216                &proof,
217                Location::new_unchecked(0),
218                &wrong_operations,
219                root,
220            ));
221        });
222    }
223
224    #[test_traced]
225    fn test_verify_proof_with_offset() {
226        let executor = deterministic::Runner::default();
227        executor.start(|_| async move {
228            let mut hasher = test_hasher();
229            let mut mmr = CleanMmr::new(&mut hasher);
230
231            // Add some initial operations (that we won't prove)
232            for i in 0u64..5 {
233                mmr.add(&mut hasher, &i.encode());
234            }
235
236            // Add operations we want to prove (starting at location 5)
237            let operations = vec![10, 11, 12];
238            let start_loc = Location::new_unchecked(5u64);
239            for op in &operations {
240                let encoded = op.encode();
241                mmr.add(&mut hasher, &encoded);
242            }
243            let root = mmr.root();
244            let proof = mmr
245                .range_proof(Location::new_unchecked(5)..Location::new_unchecked(8))
246                .unwrap();
247
248            // Verify with correct start location
249            assert!(verify_proof(
250                &mut hasher,
251                &proof,
252                start_loc,
253                &operations,
254                root,
255            ));
256
257            // Verify fails with wrong start location
258            assert!(!verify_proof(
259                &mut hasher,
260                &proof,
261                Location::new_unchecked(0), // wrong start_loc
262                &operations,
263                root,
264            ));
265        });
266    }
267
268    #[test_traced]
269    fn test_extract_pinned_nodes() {
270        let executor = deterministic::Runner::default();
271        executor.start(|_| async move {
272            let mut hasher = test_hasher();
273            let mut mmr = CleanMmr::new(&mut hasher);
274
275            // Add elements
276            let mut positions = Vec::new();
277            for i in 0u64..10 {
278                positions.push(mmr.add(&mut hasher, &i.encode()));
279            }
280
281            // Generate proof for a range
282            let start_loc = Location::new_unchecked(2);
283            let operations_len = 4u64;
284            let end_loc = start_loc + operations_len;
285            let range = start_loc..end_loc;
286            let proof = mmr.range_proof(range).unwrap();
287
288            // Extract pinned nodes
289            let pinned_nodes = extract_pinned_nodes(&proof, start_loc, operations_len);
290            assert!(pinned_nodes.is_ok());
291            let nodes = pinned_nodes.unwrap();
292            assert!(!nodes.is_empty());
293
294            // Verify the extracted nodes match what we expect from the proof
295            let start_pos = Position::try_from(start_loc).unwrap();
296            let expected_pinned: Vec<Position> = nodes_to_pin(start_pos).collect();
297            assert_eq!(nodes.len(), expected_pinned.len());
298        });
299    }
300
301    #[test_traced]
302    fn test_verify_proof_and_extract_digests() {
303        let executor = deterministic::Runner::default();
304        executor.start(|_| async move {
305            let mut hasher = test_hasher();
306            let mut mmr = CleanMmr::new(&mut hasher);
307
308            // Add some operations to the MMR
309            let operations = vec![1, 2, 3, 4];
310            let mut positions = Vec::new();
311            for op in &operations {
312                let encoded = op.encode();
313                let pos = mmr.add(&mut hasher, &encoded);
314                positions.push(pos);
315            }
316            let root = mmr.root();
317            let range = Location::new_unchecked(1)..Location::new_unchecked(4);
318            let proof = mmr.range_proof(range.clone()).unwrap();
319
320            // Verify and extract digests for subset of operations
321            let result = verify_proof_and_extract_digests(
322                &mut hasher,
323                &proof,
324                Location::new_unchecked(1), // start_loc
325                &operations[range.to_usize_range()],
326                root,
327            );
328            assert!(result.is_ok());
329            let digests = result.unwrap();
330            assert!(!digests.is_empty());
331
332            // Should fail with wrong root
333            let wrong_root = test_digest(99);
334            assert!(verify_proof_and_extract_digests(
335                &mut hasher,
336                &proof,
337                Location::new_unchecked(1),
338                &operations[range.to_usize_range()],
339                &wrong_root,
340            )
341            .is_err());
342        });
343    }
344
345    #[test_traced]
346    fn test_create_proof() {
347        const OP_COUNT: Location = Location::new_unchecked(15);
348
349        let executor = deterministic::Runner::default();
350        executor.start(|_| async move {
351            let mut hasher = test_hasher();
352            let mut mmr = CleanMmr::new(&mut hasher);
353
354            // Build MMR with test operations
355
356            let operations: Vec<u64> = (0..*OP_COUNT).collect();
357            let mut positions = Vec::new();
358            for op in &operations {
359                let encoded = op.encode();
360                positions.push(mmr.add(&mut hasher, &encoded));
361            }
362            let root = mmr.root();
363
364            // The size here is the number of leaves added (15 in this case)
365            let start_loc = Location::new_unchecked(3u64);
366            let end_loc = Location::new_unchecked(8u64);
367
368            // Get required digests (note: range is exclusive, so end_loc + 1)
369            let end_plus_one = end_loc.checked_add(1).expect("test location in bounds");
370            let required_positions =
371                digests_required_for_proof::<Digest>(OP_COUNT, start_loc..end_plus_one).unwrap();
372
373            // Fetch the actual digests
374            let mut digests = Vec::new();
375            for pos in required_positions {
376                if let Some(digest) = mmr.get_node(pos) {
377                    digests.push(digest);
378                }
379            }
380
381            // Construct proof
382            let proof = create_proof(OP_COUNT, digests.clone()).expect("test locations valid");
383            assert_eq!(proof.size, Position::try_from(OP_COUNT).unwrap());
384            assert_eq!(proof.digests.len(), digests.len());
385
386            assert!(verify_proof(
387                &mut hasher,
388                &proof,
389                start_loc,
390                &operations[*start_loc as usize..=*end_loc as usize],
391                root,
392            ));
393        });
394    }
395
396    #[test_traced]
397    fn test_create_proof_store() {
398        let executor = deterministic::Runner::default();
399        executor.start(|_| async move {
400            let mut hasher = test_hasher();
401            let mut mmr = CleanMmr::new(&mut hasher);
402
403            // Add some operations to the MMR
404            let op_count = 15;
405            let operations: Vec<u64> = (0..op_count).collect();
406            let mut positions = Vec::new();
407            for op in &operations {
408                let encoded = op.encode();
409                let pos = mmr.add(&mut hasher, &encoded);
410                positions.push(pos);
411            }
412            let root = mmr.root();
413            let range = Location::new_unchecked(0)..Location::new_unchecked(3);
414            let proof = mmr.range_proof(range.clone()).unwrap();
415
416            // Create proof store
417            let result = create_proof_store(
418                &mut hasher,
419                &proof,
420                range.start,                         // start_loc
421                &operations[range.to_usize_range()], // Only the first 3 operations covered by the proof
422                root,
423            );
424            assert!(result.is_ok());
425            let proof_store = result.unwrap();
426
427            // Verify we can generate sub-proofs from the store
428            let range = Location::new_unchecked(0)..Location::new_unchecked(2);
429            let sub_proof = verification::range_proof(&proof_store, range.clone())
430                .await
431                .unwrap();
432
433            // Verify the sub-proof
434            assert!(verify_proof(
435                &mut hasher,
436                &sub_proof,
437                range.start,
438                &operations[range.to_usize_range()],
439                root,
440            ));
441        });
442    }
443
444    #[test_traced]
445    fn test_create_proof_store_invalid_proof() {
446        let executor = deterministic::Runner::default();
447        executor.start(|_| async move {
448            let mut hasher = test_hasher();
449            let mut mmr = CleanMmr::new(&mut hasher);
450
451            // Add some operations to the MMR
452            let operations = vec![1, 2, 3];
453            let mut positions = Vec::new();
454            for op in &operations {
455                let encoded = op.encode();
456                let pos = mmr.add(&mut hasher, &encoded);
457                positions.push(pos);
458            }
459            let range = Location::new_unchecked(0)..Location::new_unchecked(2);
460            let proof = mmr.range_proof(range).unwrap();
461
462            // Should fail with invalid root
463            let wrong_root = test_digest(99);
464            assert!(create_proof_store(
465                &mut hasher,
466                &proof,
467                Location::new_unchecked(0),
468                &operations,
469                &wrong_root
470            )
471            .is_err());
472        });
473    }
474
475    #[test_traced]
476    fn test_create_proof_store_from_digests() {
477        let executor = deterministic::Runner::default();
478        executor.start(|_| async move {
479            let mut hasher = test_hasher();
480            let mut mmr = CleanMmr::new(&mut hasher);
481
482            // Add some operations to the MMR
483            let operations = vec![1, 2, 3];
484            let mut positions = Vec::new();
485            for op in &operations {
486                let encoded = op.encode();
487                let pos = mmr.add(&mut hasher, &encoded);
488                positions.push(pos);
489            }
490            let root = mmr.root();
491            let proof = mmr
492                .range_proof(Location::new_unchecked(0)..Location::new_unchecked(3))
493                .unwrap();
494
495            // First verify and extract digests
496            let digests = verify_proof_and_extract_digests(
497                &mut hasher,
498                &proof,
499                Location::new_unchecked(0),
500                &operations,
501                root,
502            )
503            .unwrap();
504
505            // Create proof store from digests
506            let proof_store = create_proof_store_from_digests(&proof, digests);
507
508            // Verify we can use the proof store
509            let sub_proof = verification::range_proof(
510                &proof_store,
511                Location::new_unchecked(0)..Location::new_unchecked(2),
512            )
513            .await
514            .unwrap();
515
516            // Verify the sub-proof
517            assert!(verify_proof(
518                &mut hasher,
519                &sub_proof,
520                Location::new_unchecked(0),
521                &operations[0..2],
522                root,
523            ));
524        });
525    }
526
527    #[test_traced]
528    fn test_create_multi_proof() {
529        let executor = deterministic::Runner::default();
530        executor.start(|_| async move {
531            let mut hasher = test_hasher();
532            let mut mmr = CleanMmr::new(&mut hasher);
533
534            // Add operations to the MMR
535            let operations: Vec<u64> = (0..20).collect();
536            for op in &operations {
537                let encoded = op.encode();
538                mmr.add(&mut hasher, &encoded);
539            }
540            let root = mmr.root();
541
542            // Create proof for full range
543            let proof = mmr
544                .range_proof(Location::new_unchecked(0)..Location::new_unchecked(20))
545                .unwrap();
546
547            // Create proof store
548            let proof_store = create_proof_store(
549                &mut hasher,
550                &proof,
551                Location::new_unchecked(0),
552                &operations,
553                root,
554            )
555            .unwrap();
556
557            // Generate multi-proof for specific locations
558            let target_locations = vec![
559                Location::new_unchecked(2),
560                Location::new_unchecked(5),
561                Location::new_unchecked(10),
562                Location::new_unchecked(15),
563                Location::new_unchecked(18),
564            ];
565            let multi_proof = create_multi_proof(&proof_store, &target_locations)
566                .await
567                .unwrap();
568
569            // Prepare operations for verification
570            let selected_ops: Vec<(Location, u64)> = target_locations
571                .iter()
572                .map(|&loc| (loc, operations[*loc as usize]))
573                .collect();
574
575            // Verify the multi-proof
576            assert!(verify_multi_proof(
577                &mut hasher,
578                &multi_proof,
579                &selected_ops,
580                root,
581            ));
582        });
583    }
584
585    #[test_traced]
586    fn test_verify_multi_proof() {
587        let executor = deterministic::Runner::default();
588        executor.start(|_| async move {
589            let mut hasher = test_hasher();
590            let mut mmr = CleanMmr::new(&mut hasher);
591
592            // Add operations to the MMR
593            let operations: Vec<u64> = (0..10).collect();
594            let mut positions = Vec::new();
595            for op in &operations {
596                let encoded = op.encode();
597                let pos = mmr.add(&mut hasher, &encoded);
598                positions.push(pos);
599            }
600            let root = mmr.root();
601
602            // Generate multi-proof directly from MMR
603            let target_locations = vec![
604                Location::new_unchecked(1),
605                Location::new_unchecked(4),
606                Location::new_unchecked(7),
607            ];
608            let multi_proof = verification::multi_proof(&mmr, &target_locations)
609                .await
610                .unwrap();
611
612            // Verify with correct operations
613            let selected_ops = vec![
614                (Location::new_unchecked(1), operations[1]),
615                (Location::new_unchecked(4), operations[4]),
616                (Location::new_unchecked(7), operations[7]),
617            ];
618            assert!(verify_multi_proof(
619                &mut hasher,
620                &multi_proof,
621                &selected_ops,
622                root,
623            ));
624
625            // Verify fails with wrong operations
626            let wrong_ops = vec![
627                (Location::new_unchecked(1), 99),
628                (Location::new_unchecked(4), operations[4]),
629                (Location::new_unchecked(7), operations[7]),
630            ];
631            assert!(!verify_multi_proof(
632                &mut hasher,
633                &multi_proof,
634                &wrong_ops,
635                root,
636            ));
637
638            // Verify fails with wrong locations
639            let wrong_locations = vec![
640                (Location::new_unchecked(0), operations[1]),
641                (Location::new_unchecked(4), operations[4]),
642                (Location::new_unchecked(7), operations[7]),
643            ];
644            assert!(!verify_multi_proof(
645                &mut hasher,
646                &multi_proof,
647                &wrong_locations,
648                root,
649            ));
650        });
651    }
652
653    #[test_traced]
654    fn test_multi_proof_empty() {
655        let executor = deterministic::Runner::default();
656        executor.start(|_| async move {
657            let mut hasher = test_hasher();
658            let empty_mmr = CleanMmr::new(&mut hasher);
659            let empty_root = empty_mmr.root();
660
661            // Empty proof should verify against an empty MMR/database.
662            let empty_proof = Proof::default();
663            assert!(verify_multi_proof(
664                &mut hasher,
665                &empty_proof,
666                &[] as &[(Location, u64)],
667                empty_root,
668            ));
669
670            // Proofs over empty locations should otherwise not be allowed.
671            assert!(matches!(
672                verification::multi_proof(&empty_mmr, &[]).await,
673                Err(Error::Empty)
674            ));
675        });
676    }
677
678    #[test_traced]
679    fn test_multi_proof_single_element() {
680        let executor = deterministic::Runner::default();
681        executor.start(|_| async move {
682            let mut hasher = test_hasher();
683            let mut mmr = CleanMmr::new(&mut hasher);
684
685            // Add operations to the MMR
686            let operations = vec![1, 2, 3];
687            let mut positions = Vec::new();
688            for op in &operations {
689                let encoded = op.encode();
690                let pos = mmr.add(&mut hasher, &encoded);
691                positions.push(pos);
692            }
693            let root = mmr.root();
694
695            // Create proof store for all elements
696            let proof = mmr
697                .range_proof(Location::new_unchecked(0)..Location::new_unchecked(3))
698                .unwrap();
699            let proof_store = create_proof_store(
700                &mut hasher,
701                &proof,
702                Location::new_unchecked(0),
703                &operations,
704                root,
705            )
706            .unwrap();
707
708            // Generate multi-proof for single element
709            let multi_proof = create_multi_proof(&proof_store, &[Location::new_unchecked(1)])
710                .await
711                .unwrap();
712
713            // Verify single element
714            assert!(verify_multi_proof(
715                &mut hasher,
716                &multi_proof,
717                &[(Location::new_unchecked(1), operations[1])],
718                root,
719            ));
720        });
721    }
722}
commonware_storage/qmdb/verify.rs

commonware_storage/qmdb/
verify.rs
