mkit_core/verify/
proof_size.rs

1//! Exact MKDP/MKDS lengths from metadata, without constructing Merkle or Bao
2//! proofs. Chunk lengths describe canonical Blob content, excluding its ten
3//! header bytes. All results enforce the 64 MiB wire cap.
4
5use super::span::{RangeProofError, RangeProofKind};
6use super::{MAX_BUNDLE_BYTES, MAX_COMMIT_BYTES, VerifyError};
7use crate::merkle;
8
9/// Metadata describing one authenticated tree path component.
10#[derive(Debug, Clone, Copy)]
11pub struct PrefixStep {
12    /// Number of bytes in the entry name.
13    pub name_len: usize,
14    /// Entry position within its tree.
15    pub position: u32,
16    /// Number of entries in that tree.
17    pub leaf_count: u32,
18}
19
20/// Exact format, chunk bounds and wire length selected by a chunked range.
21#[derive(Debug, Clone, Copy)]
22pub struct EncodedRangePlan {
23    /// MKDP for one chunk; MKDS for a range crossing a boundary.
24    pub kind: RangeProofKind,
25    /// First requested chunk index.
26    pub first: usize,
27    /// Last requested chunk index.
28    pub last: usize,
29    /// Complete encoded response length, already checked against the cap.
30    pub encoded_size: u64,
31}
32
33fn varint_size(mut value: u64) -> u128 {
34    let mut size = 1;
35    while value >= 128 {
36        value >>= 7;
37        size += 1;
38    }
39    size
40}
41
42fn vector_size(bytes: u64) -> u128 {
43    varint_size(bytes) + u128::from(bytes)
44}
45
46fn capped(size: u128) -> Result<u64, RangeProofError> {
47    if size > MAX_BUNDLE_BYTES as u128 {
48        Err(RangeProofError::ProofTooLarge)
49    } else {
50        u64::try_from(size).map_err(|_| RangeProofError::ProofTooLarge)
51    }
52}
53
54fn proof_size(count: u32, positions: &[u32]) -> Result<u128, RangeProofError> {
55    merkle::proof_encoded_size(count, positions.iter().copied())
56        .map(|size| size as u128)
57        .map_err(|error| VerifyError::from(error).into())
58}
59
60fn prefix_size(commit_bytes: u64, steps: &[PrefixStep]) -> Result<u128, RangeProofError> {
61    if commit_bytes > MAX_COMMIT_BYTES as u64 {
62        return Err(RangeProofError::ProofTooLarge);
63    }
64    if steps.len() > crate::store::MAX_TREE_DEPTH {
65        return Err(VerifyError::TooManySteps(steps.len()).into());
66    }
67    let mut size = 38 + vector_size(commit_bytes) + varint_size(steps.len() as u64);
68    for step in steps {
69        if step.name_len == 0 || step.name_len > 255 {
70            return Err(VerifyError::Malformed.into());
71        }
72        size +=
73            vector_size(step.name_len as u64) + 69 + proof_size(step.leaf_count, &[step.position])?;
74    }
75    capped(size)?;
76    Ok(size)
77}
78
79/// Exact canonical Object bundle size, including manifest and root-tree
80/// objects. `commit_bytes` and `object_bytes` are canonical encoded lengths.
81///
82/// # Errors
83/// Invalid path metadata or an encoded bundle exceeding the cap.
84pub fn object_proof_size(
85    commit_bytes: u64,
86    steps: &[PrefixStep],
87    object_bytes: u64,
88) -> Result<u64, RangeProofError> {
89    capped(prefix_size(commit_bytes, steps)? + vector_size(object_bytes))
90}
91
92// Number of Bao parent pairs included for the selected inclusive chunk
93// interval. Fully covered subtrees have leaves-1 parents; only boundary
94// paths recurse, so sizing is logarithmic even for enormous lengths.
95fn bao_parents(base: u64, leaves: u64, first: u64, last: u64) -> u64 {
96    if first <= base && base + leaves - 1 <= last {
97        return leaves - 1;
98    }
99    if leaves == 1 || last < base || first >= base + leaves {
100        return 0;
101    }
102    let left = 1u64 << (leaves - 1).ilog2();
103    1 + bao_parents(base, left, first, last) + bao_parents(base + left, leaves - left, first, last)
104}
105
106fn bao_slice_size(canonical_bytes: u64, offset: u64, len: u64) -> Result<u64, RangeProofError> {
107    if len == 0 {
108        return Err(RangeProofError::ZeroLength);
109    }
110    let end = offset
111        .checked_add(len)
112        .ok_or(RangeProofError::OffsetOverflow)?;
113    if end > canonical_bytes {
114        return Err(RangeProofError::OutOfBounds);
115    }
116    let first = offset / 1024;
117    let last = (end - 1) / 1024;
118    let covered_end = u128::from(last + 1) * 1024;
119    let covered = covered_end.min(u128::from(canonical_bytes)) - u128::from(first) * 1024;
120    let parents = bao_parents(0, canonical_bytes.div_ceil(1024), first, last);
121    capped(8 + covered + u128::from(parents) * 64)
122}
123
124/// Exact MKDP range size for a plain canonical Blob.
125///
126/// # Errors
127/// Invalid metadata, zero length, overflow, content bounds or wire cap.
128pub fn blob_range_proof_size(
129    commit_bytes: u64,
130    steps: &[PrefixStep],
131    canonical_blob_bytes: u64,
132    offset: u64,
133    len: u64,
134) -> Result<u64, RangeProofError> {
135    let bao_offset = offset
136        .checked_add(10)
137        .ok_or(RangeProofError::OffsetOverflow)?;
138    let slice = bao_slice_size(canonical_blob_bytes, bao_offset, len)?;
139    capped(prefix_size(commit_bytes, steps)? + 1 + 16 + vector_size(slice) + 1)
140}
141
142fn canonical_length(content: u64, index: usize) -> Result<u64, RangeProofError> {
143    if content == 0 {
144        return Err(RangeProofError::InvalidChunk { index });
145    }
146    content
147        .checked_add(10)
148        .ok_or(RangeProofError::OffsetOverflow)
149}
150
151/// Exact chunked MKDP/MKDS size from indexed lengths through the last
152/// included chunk. Metadata after the span is unnecessary: `total_chunks`
153/// alone fixes the Merkle shape. The caller checks the manifest's total
154/// content bounds before collecting these lengths.
155///
156/// # Errors
157/// Invalid metadata, zero length, overflow, insufficient length prefix,
158/// content bounds or wire cap. No proof bytes or sibling hashes are built.
159pub fn chunked_range_proof_size(
160    commit_bytes: u64,
161    steps: &[PrefixStep],
162    total_chunks: u32,
163    chunk_content_lengths: &[u64],
164    offset: u64,
165    len: u64,
166) -> Result<EncodedRangePlan, RangeProofError> {
167    let mut sizer = ChunkedRangeSizer::new(
168        commit_bytes,
169        steps,
170        total_chunks,
171        offset,
172        len,
173        MAX_BUNDLE_BYTES as u64,
174    )?;
175    for &content in chunk_content_lengths {
176        if let Some(plan) = sizer.push(content)? {
177            return Ok(plan);
178        }
179    }
180    Err(RangeProofError::OutOfBounds)
181}
182
183/// Incremental wire sizing with constant retained metadata. Feed only the
184/// lengths through the selected span; caps stop collection as soon as the
185/// encoded prefix alone proves the complete representation is too large.
186#[derive(Debug)]
187pub struct ChunkedRangeSizer {
188    prefix: u128,
189    count: u32,
190    offset: u64,
191    end: u64,
192    cap: u64,
193    preceding: u128,
194    cursor: u64,
195    index: usize,
196    first: Option<usize>,
197    container: u128,
198    finished: bool,
199}
200
201impl ChunkedRangeSizer {
202    /// Start metadata sizing with a deployment cap no greater than 64 MiB.
203    ///
204    /// # Errors
205    /// Zero length, offset overflow, invalid prefix/count or oversized prefix.
206    pub fn new(
207        commit_bytes: u64,
208        steps: &[PrefixStep],
209        total_chunks: u32,
210        offset: u64,
211        len: u64,
212        max_encoded_size: u64,
213    ) -> Result<Self, RangeProofError> {
214        if len == 0 {
215            return Err(RangeProofError::ZeroLength);
216        }
217        let end = offset
218            .checked_add(len)
219            .ok_or(RangeProofError::OffsetOverflow)?;
220        if total_chunks > crate::serialize::MAX_CHUNKS {
221            return Err(VerifyError::TooManyChunks.into());
222        }
223        let mut sizer = Self {
224            prefix: prefix_size(commit_bytes, steps)?,
225            count: total_chunks
226                .checked_add(1)
227                .ok_or(VerifyError::TooManyChunks)?,
228            offset,
229            end,
230            cap: max_encoded_size.min(MAX_BUNDLE_BYTES as u64),
231            preceding: 0,
232            cursor: 0,
233            index: 0,
234            first: None,
235            container: 0,
236            finished: false,
237        };
238        sizer.check(sizer.prefix)?;
239        // A zero-chunk manifest cannot satisfy any nonempty range.
240        sizer.finished = total_chunks == 0;
241        Ok(sizer)
242    }
243
244    fn check(&self, size: u128) -> Result<u64, RangeProofError> {
245        let size = capped(size)?;
246        if size > self.cap {
247            Err(RangeProofError::ProofTooLarge)
248        } else {
249            Ok(size)
250        }
251    }
252
253    /// Add one canonical Blob content length, excluding its ten header bytes.
254    /// Returns the exact final plan at the last selected chunk.
255    ///
256    /// # Errors
257    /// Invalid length/count, overflow or a provably exceeded encoded cap.
258    #[allow(clippy::too_many_lines)] // Mirrors the MKDP/MKDS wire fields in one sizing transition.
259    pub fn push(&mut self, content: u64) -> Result<Option<EncodedRangePlan>, RangeProofError> {
260        let index = self.index;
261        let position = u32::try_from(index)
262            .ok()
263            .and_then(|n| n.checked_add(1))
264            .filter(|&n| n < self.count && !self.finished)
265            .ok_or(RangeProofError::OutOfBounds)?;
266        let canonical = canonical_length(content, index)?;
267        let next = self
268            .cursor
269            .checked_add(content)
270            .ok_or(RangeProofError::OffsetOverflow)?;
271        let plan = if self.first.is_none() && self.offset >= next {
272            let slice = bao_slice_size(canonical, 0, 10)?;
273            self.preceding += 36 + proof_size(self.count, &[position])? + vector_size(slice);
274            self.check(self.prefix + self.preceding)?;
275            None
276        } else {
277            let first_index = *self.first.get_or_insert(index);
278            let chunk_proof = proof_size(self.count, &[0, position])?;
279            if index == first_index {
280                let single = self.end <= next;
281                let (local_offset, selected_len) = if single {
282                    (self.offset - self.cursor, self.end - self.offset)
283                } else {
284                    (0, 1)
285                };
286                let slice = bao_slice_size(canonical, local_offset + 10, selected_len)?;
287                let range_size = self.check(
288                    self.prefix
289                        + 81
290                        + chunk_proof
291                        + 16
292                        + vector_size(slice)
293                        + varint_size(first_index as u64)
294                        + self.preceding,
295                )?;
296                if single {
297                    self.finished = true;
298                    return Ok(Some(EncodedRangePlan {
299                        kind: RangeProofKind::Mkdp,
300                        first: index,
301                        last: index,
302                        encoded_size: range_size,
303                    }));
304                }
305                self.container = 53 + vector_size(range_size);
306            }
307            let chunk_size = self.check(self.prefix + 48 + chunk_proof + vector_size(canonical))?;
308            self.container += vector_size(chunk_size);
309            let encoded_size =
310                self.check(self.container + varint_size((index - first_index + 1) as u64))?;
311            (self.end <= next).then_some(EncodedRangePlan {
312                kind: RangeProofKind::Mkds,
313                first: first_index,
314                last: index,
315                encoded_size,
316            })
317        };
318        self.cursor = next;
319        self.index += 1;
320        self.finished = plan.is_some();
321        Ok(plan)
322    }
323}
324
325#[cfg(test)]
326#[allow(clippy::unwrap_used, clippy::cast_possible_truncation)]
327mod tests {
328    use super::*;
329    use crate::object::ChunkedBlob;
330    use commonware_codec::EncodeSize;
331
332    #[test]
333    fn bao_sizing_matches_actual_extractors_at_chunk_and_tree_edges() {
334        for canonical in [10, 11, 1023, 1024, 1025, 2048, 2049, 4097, 8193, 16383] {
335            let bytes = vec![42; canonical];
336            for offset in [0, 1, 9, 10, 1023, 1024, 2047, 2048, canonical - 1] {
337                if offset >= canonical {
338                    continue;
339                }
340                for len in [1, 10, 1024, canonical - offset] {
341                    if offset + len > canonical {
342                        continue;
343                    }
344                    let actual =
345                        super::super::extract_bao_slice(&bytes, offset as u64, len as u64).unwrap();
346                    assert_eq!(
347                        bao_slice_size(canonical as u64, offset as u64, len as u64).unwrap(),
348                        actual.len() as u64,
349                        "canonical={canonical}, offset={offset}, len={len}"
350                    );
351                }
352            }
353        }
354    }
355
356    #[test]
357    fn merkle_sizes_match_odd_even_and_power_of_two_shapes() {
358        for chunks in 1u32..=70 {
359            let manifest = ChunkedBlob {
360                total_size: u64::from(chunks),
361                chunk_size: 0,
362                chunks: (0..chunks).map(|n| [n as u8; 32]).collect(),
363            };
364            for index in 0..chunks {
365                let position = index + 1;
366                assert_eq!(
367                    proof_size(chunks + 1, &[position]).unwrap(),
368                    merkle::build_chunk_proof(&manifest, position)
369                        .unwrap()
370                        .encode_size() as u128
371                );
372                assert_eq!(
373                    proof_size(chunks + 1, &[0, position]).unwrap(),
374                    merkle::build_chunks_multi_proof(&manifest, [0, position])
375                        .unwrap()
376                        .encode_size() as u128
377                );
378            }
379        }
380    }
381
382    fn metadata(steps: &[super::super::Step]) -> Vec<PrefixStep> {
383        steps
384            .iter()
385            .map(|step| PrefixStep {
386                name_len: step.name.len(),
387                position: step.position,
388                leaf_count: step.proof.leaf_count,
389            })
390            .collect()
391    }
392
393    fn canonical_slice_length(slice: &[u8]) -> u64 {
394        u64::from_le_bytes(slice[..8].try_into().unwrap())
395    }
396
397    #[test]
398    fn canonical_object_and_range_goldens_have_exact_planned_lengths() {
399        let goldens: &[&[u8]] = &[
400            include_bytes!("../../../../tests/golden/disclosure/root_tree.bin"),
401            include_bytes!("../../../../tests/golden/disclosure/shallow_file.bin"),
402            include_bytes!("../../../../tests/golden/disclosure/nested_file_3levels.bin"),
403            include_bytes!("../../../../tests/golden/disclosure/small_blob_range_whole.bin"),
404            include_bytes!("../../../../tests/golden/disclosure/small_blob_range_first_block.bin"),
405            include_bytes!(
406                "../../../../tests/golden/disclosure/small_blob_range_last_partial_block.bin"
407            ),
408            include_bytes!("../../../../tests/golden/disclosure/chunked_range_with_offsets.bin"),
409        ];
410        for golden in goldens {
411            let (_, commit, steps, payload) = super::super::decode_disclosure(golden).unwrap();
412            let steps = metadata(&steps);
413            let predicted = match payload {
414                super::super::PayloadWire::Object { bytes } => {
415                    object_proof_size(commit.len() as u64, &steps, bytes.len() as u64).unwrap()
416                }
417                super::super::PayloadWire::Range {
418                    chunk: None,
419                    offset_in_blob,
420                    len,
421                    slice,
422                    ..
423                } => blob_range_proof_size(
424                    commit.len() as u64,
425                    &steps,
426                    canonical_slice_length(&slice),
427                    offset_in_blob,
428                    len,
429                )
430                .unwrap(),
431                super::super::PayloadWire::Range {
432                    chunk: Some(chunk),
433                    offset_in_blob,
434                    len,
435                    slice,
436                    chunk_len_proofs,
437                } => {
438                    let mut lengths: Vec<u64> = chunk_len_proofs
439                        .iter()
440                        .map(|proof| canonical_slice_length(&proof.slice) - 10)
441                        .collect();
442                    let offset = lengths.iter().sum::<u64>() + offset_in_blob;
443                    lengths.push(canonical_slice_length(&slice) - 10);
444                    chunked_range_proof_size(
445                        commit.len() as u64,
446                        &steps,
447                        chunk.proof.leaf_count - 1,
448                        &lengths,
449                        offset,
450                        len,
451                    )
452                    .unwrap()
453                    .encoded_size
454                }
455                _ => panic!("fixture selector"),
456            };
457            assert_eq!(predicted, golden.len() as u64);
458        }
459    }
460
461    #[test]
462    fn huge_metadata_is_rejected_without_proof_allocation() {
463        assert!(matches!(
464            object_proof_size(MAX_COMMIT_BYTES as u64 + 1, &[], 1),
465            Err(RangeProofError::ProofTooLarge)
466        ));
467        assert!(matches!(
468            object_proof_size(200, &[], u64::MAX),
469            Err(RangeProofError::ProofTooLarge)
470        ));
471        assert!(matches!(
472            blob_range_proof_size(200, &[], u64::MAX, 0, u64::MAX),
473            Err(RangeProofError::OffsetOverflow)
474        ));
475        assert!(matches!(
476            chunked_range_proof_size(200, &[], 1, &[1], u64::MAX, 1),
477            Err(RangeProofError::OffsetOverflow)
478        ));
479        assert!(chunked_range_proof_size(200, &[], 1, &[MAX_BUNDLE_BYTES as u64], 0, 1).is_ok());
480        assert!(matches!(
481            chunked_range_proof_size(
482                200,
483                &[],
484                2,
485                &[MAX_BUNDLE_BYTES as u64, 1],
486                0,
487                MAX_BUNDLE_BYTES as u64 + 1
488            ),
489            Err(RangeProofError::ProofTooLarge)
490        ));
491    }
492
493    #[test]
494    fn preceding_cap_and_prefix_only_metadata_are_enforced() {
495        let lengths = vec![65536; 40000];
496        assert!(matches!(
497            chunked_range_proof_size(200, &[], 50000, &lengths, 39999 * 65536, 1),
498            Err(RangeProofError::ProofTooLarge)
499        ));
500        let result = chunked_range_proof_size(200, &[], 50000, &[100], 99, 1).unwrap();
501        assert_eq!((result.first, result.last), (0, 0));
502        assert!(matches!(result.kind, RangeProofKind::Mkdp));
503    }
504
505    #[test]
506    #[allow(clippy::too_many_lines)] // One fixture matrix compares metadata with both canonical builders.
507    fn incremental_sizing_matches_builders_across_varint_and_merkle_edges() {
508        use super::super::span::{RangeProof, build_range_proof_from, verify_disclosure_span};
509        use crate::layout::RepoLayout;
510        use crate::object::{Blob, Commit, EntryMode, Identity, Object, Tree, TreeEntry};
511        use crate::serialize::serialize;
512        use crate::sign::{KeyPair, sign_commit};
513        use crate::store::ObjectStore;
514
515        let temp = tempfile::TempDir::new().unwrap();
516        let store = ObjectStore::init(&RepoLayout::single(temp.path())).unwrap();
517        for (count, name_len) in [
518            (2, 127),
519            (3, 128),
520            (7, 255),
521            (8, 1),
522            (9, 1),
523            (127, 1),
524            (128, 1),
525            (129, 1),
526        ] {
527            let lengths: Vec<u64> = (0..count)
528                .map(|i| [1, 1013, 1014, 1015, 2038][i % 5])
529                .collect();
530            let chunks: Vec<_> = lengths
531                .iter()
532                .enumerate()
533                .map(|(i, &len)| {
534                    store
535                        .write(
536                            &serialize(&Object::Blob(Blob {
537                                data: vec![i as u8; len as usize],
538                            }))
539                            .unwrap(),
540                        )
541                        .unwrap()
542                })
543                .collect();
544            let manifest = Object::ChunkedBlob(ChunkedBlob {
545                total_size: lengths.iter().sum(),
546                chunk_size: 0,
547                chunks,
548            });
549            let leaf = store.write(&serialize(&manifest).unwrap()).unwrap();
550            let name = vec![b'f'; name_len];
551            let tree = Object::Tree(Tree {
552                entries: vec![
553                    TreeEntry {
554                        name: b"a".to_vec(),
555                        mode: EntryMode::Blob,
556                        object_hash: leaf,
557                    },
558                    TreeEntry {
559                        name: name.clone(),
560                        mode: EntryMode::Blob,
561                        object_hash: leaf,
562                    },
563                    TreeEntry {
564                        name: b"z".to_vec(),
565                        mode: EntryMode::Blob,
566                        object_hash: leaf,
567                    },
568                ],
569            });
570            let root = store.write(&serialize(&tree).unwrap()).unwrap();
571            let key = KeyPair::from_seed([3; 32]);
572            let mut commit = Commit::new_unannotated(
573                root,
574                vec![],
575                Identity::ed25519(key.public.0),
576                key.public.0,
577                vec![],
578                1,
579                [0; 64],
580            );
581            commit.signature = sign_commit(&commit, &key).unwrap().0;
582            let canonical = serialize(&Object::Commit(commit)).unwrap();
583            let id = store.write(&canonical).unwrap();
584            let steps = [PrefixStep {
585                name_len,
586                position: 1,
587                leaf_count: 3,
588            }];
589            let total = lengths.iter().sum::<u64>();
590            for (offset, len) in [(0, total), (total - 1, 1), (1, total - 2)] {
591                let plan = chunked_range_proof_size(
592                    canonical.len() as u64,
593                    &steps,
594                    count as u32,
595                    &lengths,
596                    offset,
597                    len,
598                )
599                .unwrap();
600                let built =
601                    build_range_proof_from(&store, &id, &[&name], offset, len, None).unwrap();
602                let bytes = match built {
603                    RangeProof::Mkdp(bytes) => {
604                        assert_eq!(plan.kind, RangeProofKind::Mkdp);
605                        super::super::verify_disclosure(&id, &bytes).unwrap();
606                        bytes
607                    }
608                    RangeProof::Mkds(bytes) => {
609                        assert_eq!(plan.kind, RangeProofKind::Mkds);
610                        verify_disclosure_span(&id, &bytes).unwrap();
611                        bytes
612                    }
613                };
614                assert_eq!(
615                    plan.encoded_size,
616                    bytes.len() as u64,
617                    "count={count}, offset={offset}, len={len}"
618                );
619                let mut sizer = ChunkedRangeSizer::new(
620                    canonical.len() as u64,
621                    &steps,
622                    count as u32,
623                    offset,
624                    len,
625                    plan.encoded_size - 1,
626                )
627                .unwrap();
628                assert!(lengths.iter().any(|&length| matches!(
629                    sizer.push(length),
630                    Err(RangeProofError::ProofTooLarge)
631                )));
632            }
633        }
634    }
635}
mkit_core/verify/proof_size.rs

mkit_core/verify/
proof_size.rs
