Verkle - Test vectors plan

Note: this document is still a draft

This document describes some high-level description of test-vectors to generate, separating in three categories:

• Cryptography test vectors: test vectors that test fundamental cryptography primitives and border cases.
• Tree test vectors: test vectors that test tree mutation and key generation.

Current repo: verkle-test-vectors

Cryptography test vectors

Sketch of test vectors:

• Random vector commitment result check. (i.e: MSM with defined VKT basis)
• MapToFieldElement
• Point serialization and deserialization:
  • Serialize point with y coordinate being lexicographically highest. (succeed)
  • Serialize point with y coordinate being lexicographically lowest. (succeed)
  • Deserialize point (uncompressed) not in the curve. (fail) [Note: not every implementation needs uncompressed point deserialization, if it does (be careful!) it requires this test]
  • Deserialize point (compressed) in the curve but not in subgroup (legendre check). (fail)
  • Deserialize point with x coordinate bigger than field size. (fail)
  • Deserialize point with x with length: empty, truncated, bigger. (fail)
• Proofs
  • Serialization/Deserialization
    • Deserialize proof containing final a Fr element bigger than field size. (fail)
    • Deserialize proof with wrong byte length (smaller or bigger). (fail)
  • Generation/Verification
    • Soundness: verify a proof against the whole range expecting check failure and success.
    • Verify IPA (not Multiproof) proof for evaluation in-domain (i.e: requires no usage of the barycentric formula).
    • (HOLD) Pull biggest proof from Kaustinen (>1k openings – only Multiproof part, not tree part). (succeed)

Tree test vectors

• Tree key generation:
  • Create EOA account with balance X and check final root.
  • Create smart-contract with big-ish code (i.e: multiple chunks) and check root.
• Tree mutation:
  • Kaustinen (e2e):
    • Select some big-ish Kaustinen block, provide tree full-state, provide post-values, and ask for expected root.
  • From empty tree, add a list of key-values and expect defined root:
    • Some easy cases.
    • Keys with long prefix match as to generate a long fork.
    • Insert and then update keys that update C1, C2, and C1&C2.
• VKT Proofs:
  • Serialization/Deserialization:
    • Deserialize + Re-serialize check a valid proof. (succeed)
    • Deserialize proof with wrong size (bigger, smaller, empty) (fail)
    • Deserialize proof with mismatch count of pre/post/keys count. (fail)
    • Deserialize proof with missing absent stem. (fail)
    • Deserialize proof with non-empty pre-values of proof of absence keys. (fail)
    • Deserialize proof with mismatch cound of extension status vs number of stems. (fail)
    • Deserialize proof with unsorted proof of absence stems. (fail)
    • Deserialize proof with unknown extension status code. (fail)
    • Deserialize proof with injected extra proof of absence stems that aren't used. (fail)
  • Pull large-ish proof from Kaustinen (ideally, with smallish tree state)
    • Provide pre-state to build an in-memory tree.
    • Check root.
    • Serialize, Deserialize, Re-serialize and check, verify.
    • Re-generate proof and check with original.
  • Prove (and verify) keys that generate hairy cases:
    • Multiple stems in the same extension status empty.
    • Proof of absence and presence in same Leaf node (absent ones "before" and "after" present one)
    • Extension status other with multiple stems.
    • Prove presence of key with empty value.
    • Prove presence of key with empty value + absence of other key in same leaf node.
    • Prove presence of key living in C1, C2 and C1&C2.