Skip to content

Independent conformance vectors: external zstd frames, multi-level chunk-map proofs, frozen MTP2 branch partition #5

Description

@Ivanbeethoven

Context

The codec's test suite is currently its own oracle for several properties:

  • the zstd strictness rules (single frame, exact raw_len, no concatenation,
    no skippable frame, no trailing bytes, window <= 8 MiB) are asserted with
    frames produced by the same zstd crate the decoder uses (src/zstd1.rs
    tests) — self-consistent but not independent;
  • the MTP2 route walk (Page::pages_along_route) is tested against trees
    generated in-process, so a shared misunderstanding of the canonical partition
    would pass;
  • the chunk-map Merkle proofs are exercised on generated leaf sets; the
    multi-level case (more than one page of 256 chunk digests, i.e. files beyond
    256 GiB at the fixed 1 MiB chunk size) has never been produced by an outside
    implementation.

Spec 16 §1 requires conformance evidence that does not reduce to "the encoder
and the decoder agree with each other", and the spec bundle itself carries
vectors/ that this repository already consumes as regression input.

Scope

  1. Independent zstd vectors. Add a small set of frames produced by the
    reference zstd CLI (not by this crate) to vectors/, together with a
    generator script so they can be reproduced, and assert:

    • one valid frame decodes to the expected bytes;
    • a concatenation of two valid frames is rejected;
    • a skippable frame (0x184D2A5X) is rejected;
    • a valid frame with an appended byte is rejected;
    • a frame whose decompressed length differs from the advertised raw_len is
      rejected in both directions (short and long);
    • a frame requesting a window larger than 8 MiB is rejected.
      These must be checked-in bytes, not generated at test time by the same
      library that decodes them.
  2. Multi-level chunk-map Merkle vectors. Add fixed vectors for pages_root
    and per-page proofs at leaf counts that force multi-level trees (for example
    2, 3, 257 and 600 pages), computed independently of this crate's
    implementation, and assert both the root and every proof verify — plus the
    negative cases (wrong length, wrong side, wrong sibling count) the spec's
    proof-shape derivation requires.

  3. MTP2 branch route vectors. Freeze the canonical partition with at least
    one directory wide enough to produce a branch root (>128 entries), including
    the expected child labels and page ids, so the route walk is checked against
    bytes rather than against a tree built in the same test.

  4. Mark clearly in the repository which vectors are independently produced and
    which are regression-only, so a reader can tell what a green run actually
    proves.

Acceptance

  • A CI-visible test run that consumes the checked-in vectors and fails if any
    is missing or differs.
  • Each vector has a documented origin (tool + invocation, or the spec section it
    was computed from).
  • The negative vectors fail for the intended reason (assert the error variant,
    not merely "is_err").
  • README states the independent-vs-regression distinction.

References

  • Spec 16 §1 (conformance), spec 06 §2–4 (frame rules), spec 07 §§4–5
    (chunk-map pages and proofs), spec 05 §5 (canonical partition)
  • src/zstd1.rs, src/metapage.rs, src/chunkmap.rs, vectors/

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions