# 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](https://github.com/jsign/verkle-test-vectors)

## Cryptography test vectors
Sketch of test vectors:
- [X] Random vector commitment result check. (i.e: MSM with defined VKT basis)
- [X] MapToFieldElement
- Point serialization and deserialization:
- [x] Serialize point with `y` coordinate being lexicographically highest. (succeed)
- [x] Serialize point with `y` coordinate being lexicographically lowest. (succeed)
- [x] 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]
- [x] Deserialize point (compressed) in the curve but not in subgroup (legendre check). (fail)
- [x] Deserialize point with `x` coordinate bigger than field size. (fail)
- [x] Deserialize point with `x` with length: empty, truncated, bigger. (fail)
- Proofs
- Serialization/Deserialization
- [x] Deserialize proof containing final `a Fr` element bigger than field size. (fail)
- [x] Deserialize proof with wrong byte length (smaller or bigger). (fail)
- Generation/Verification
- [x] Soundness: verify a proof against the whole range expecting check failure and success.
- [x] 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:
- [x] Create EOA account with balance X and check final root.
- [x] 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:
- [x] Some easy cases.
- [x] Keys with long prefix match as to generate a long fork.
- [x] 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.