# SPV Proof Theory Explanation ## SPV Proof Theory Explanation SPV (in the context of this repository) refers to: On a Merkle state tree of a certain data version, for a key provided by the user, the server constructs proof data, allowing the verifier to independently verify "whether the key exists, and if so, what the value is" or "that the key does not exist", given that the verifier only knows the root hash (or equivalent commitment). In this implementation, the state is organized as a **nibble Trie**, with node hashes cryptographically bound to keys/values. The Letus-side entry point is `MerkleIndex::GetSPV`, and the key-based downward traversal follows `TrieNode::NodeRead` (TreeOpType::kGetSPV). ### Merkle Tree Structure #### Two Layers: Grid (MSU) + Subtrees In upper layers such as MyGrid, the state is sharded by MSU (Multi-Shard Unit): it can be understood as first routing keys to one of 256 slots based on the key, with each slot corresponding to a Letus Merkle subtree. The global root hash is obtained by concatenating "the root hashes of each MSU subtree" and then hashing them once more; on the client side, the 256×32-byte subtree roots are concatenated into a "large internal node" as the first hop of the proof chain, see `GetMerkleProofGridReq::handleAllPartIOSuccess`. ``` RootHash = Hash( MSU[0] || MSU[1] || ... || MSU[255] ) (each MSU[i] is a 32-byte subtree root hash) MSU[0] MSU[1] MSU[255] | | | +--- Letus +--- Letus +--- ... (nibble Trie) subtree subtree (nibble Trie) (nibble Trie) ``` Within a single MSU is Letus's 16-ary nibble Trie (each layer takes one nibble 0\~F of the key\_hash). Below is a minimal schematic diagram using ASCII art (showing only some slots and two layers): ``` [ Root_internal ] / | \\ ... (up to 16 child slots) / | \\ v v v slot_3 slot_7 slot_A | | | [Inter] (Leaf K1) [Inter] | \\ v v (Leaf K2) (Leaf K3) ``` * **Internal nodes**: Up to 16 child slots, each slot corresponding to a 32-byte subtree hash (empty slots are often all zeros). * **Leaf nodes**: Store key\_hash and value\_hash, corresponding one-to-one with the existence of the queried key. #### State Tree Root Hash Calculation Method ``` Explanation: 1. The + in the formulas below indicates string concatenation 2. RootHash represents the root hash of the state DB 3. MSU[0] represents the root hash of MSU slot 0 4. Inter_0 represents the hash of the intermediate node corresponding to slot 0 on the Merkle tree 5. Leaf_0 represents the hash of the leaf node corresponding to slot 0 on the Merkle tree RootHash = Hash( MSU[0] + MSU[1] + ... + MSU[255] ) MSU[0] = Hash( Inter_0 + Inter_1 + ... + Inter_e ) Inter_x = Hash( Leaf_0 + Leaf_1 + ... + Leaf_e ) Leaf_x = Hash( key + value ) ``` Additionally, note that to more efficiently handle the case where there are many empty slots in intermediate nodes in the Trie, Letus chooses to skip empty slots when computing hashes. The relevant logic is similar to the following code: ```c++ std::string hash_val = ""; for (int i = 0; i < kInternalSlotCount; i++) { if (node_impl->IsSlotCommittedEmpty(i)) { continue; } hash_val = hash_update(hash_val, node_impl->GetSlotHash[i]); } ``` ### SPV Verification Method Like other Merkle tree implementations, Letus's SPV is the reverse process of computing the root hash. Specifically, the process is as follows: #### Trie Path 1. Perform `ComputeKeyHash` on the user key to obtain a fixed-length NibbleHash. 2. Starting from the MSU root (and the Grid layer above), sequentially take key\_hash\[d] as the slot index 0\~15 for depth d = 0,1,2…, enter the corresponding subtree on the internal node, until reaching a **leaf** or terminating at some layer where the **slot is empty**. 3. These obtained slots (slot\_idx) will be used later to verify the SPV return results layer by layer. #### Proof Chain tree\_proofs 1. Each element in the chain is a `TreeProofNode`, which may correspond to an intermediate node or a leaf node. 2. For an **intermediate node TreeProofNode**: It contains the `proof_node` with hex-encoded node content, and `next_begin_offset` and `next_end_offset` that indicate "where the current subtree root hash falls within the parent node's byte string". **A sound verifier MUST independently derive these offsets from the key and treat the prover-supplied values as advisory cross-check inputs only.** The derivation differs by layer: * **MSU Root layer** (the first proof node, 256 × 32-byte flat slot array, no header): `next_begin_offset = slot_idx * 32`, where `slot_idx` is derived from the queried key via the network's MSU routing function — `slot_idx = key[len(key) - 1]` for the Pharos mainnet/testnet — not from any prover-supplied data. * **Internal node layer** (every subsequent non-leaf node): `next_begin_offset = 3 + 32 * slot_idx`, where `slot_idx` is the nibble of `ComputeKeyHash(key)` at the corresponding trie depth. The leading 3 bytes are node metadata. * `next_end_offset = next_begin_offset + 32` in both cases. If the prover-supplied `next_begin_offset` disagrees with the key-derived value at any layer — especially at the MSU Root — the proof must be rejected. See the Correctness Discussion below for why this is load-bearing for non-existence soundness. 3. For a **leaf node TreeProofNode**: It contains the `proof_node` with hex-encoded node content, representing the concatenation of the key's hash and the value's hash (specific encoding depends on the implementation). #### Proof Chain Verification Logic Verifier input: `root_hash` (committed root), `key`, returned `proofs[]` (and optional sibling sub-proofs, see below). ``` cur = Starting from the last node (deepest) in proofs, compute "the subtree root hash of that node" according to the node type for i = len(proofs)-2 .. 0: parent = proofs[i] # Independently derive the expected slot offset from the queried key — do not # trust the prover-supplied next_begin_offset for slicing. if parent is the MSU Root layer (i == 0): expected_offset = key[len(key) - 1] * 32 # 256-slot flat array else: slot_idx = nibble_at_depth(ComputeKeyHash(key), trie_depth_of(parent)) expected_offset = 3 + slot_idx * 32 # internal node layout Assert parent.next_begin_offset == expected_offset # cross-check H_slot = parent.proof_node[expected_offset : expected_offset + 32] Assert H_slot == cur cur = Hash(parent.proof_node) // Or the parent node hash rule agreed upon by the implementation Assert cur == root_hash (or consistent with the root after concatenation with the MSU/Grid chain) ``` **Existence**: The last hop is a leaf, and the key\_hash in the leaf is consistent with `ComputeKeyHash(key)`, and the value can be verified. **Non-existence** has two typical forms (consistent with the "instance" numbering below): * **Case 1**: The last hop is a leaf, but the key\_hash in the leaf is inconsistent with the queried key (the path leads to "someone else's leaf") — typically without sibling sub-proofs. * **Case 2**: At an internal node, the next nibble corresponding to the query is an empty slot, while other slots at the same layer have data — often accompanied by `sibling_leftmost_leaf_proofs` (sub-chains to the leftmost leaf of each sibling slot); the information of these sibling slots is also used to assist in non-existence proofs. ## SPV Instance Explanation Consistent with the implementation: The `sha256(key)` in the pseudocode below and the hexadecimal strings in the comments (such as "12e2aef") are only for illustrative purposes to facilitate comparison with the diagrams; actual verification should be based on the NibbleHash obtained from `ComputeKeyHash` and the node encoding rules. ### Existence Proof **Scenario**: key = K, (K, V) exists in the tree, the query path goes from the MSU root along the nibble of hash(K) all the way to a leaf, and that leaf is the storage for K. **Instance**:

SPV Existence Proof

As shown in the figure above, a total of three diagrams illustrate an actual example of SPV verification. * The **leftmost diagram** shows the structure of the Trie, and the hash corresponding to the key we expect to verify, i.e., "12e2aef" * The **middle diagram** shows the response given by SPV, and the correspondence between the response content and each layer of the Trie * The **rightmost diagram** shows the SPV verification flow, verifying from the leaf node to the state root hash. We focus on explaining the SPV verification flow shown on the rightmost side: ``` # Step 1: Get slot_idx at each layer key_hash = sha256(key) # key_hash = "12e2aef" slot_idx[0] = 1 slot_idx[1] = 2 ... # Step 2: Verify leaf node check: proof[-1][1] == key_hash # proof[-1] consists of three elements, proof[-1][1] represents key_hash tmp_hash = sha256(proof[-1]) # Step 3: Verify the intermediate node one layer above the leaf node check: proof[-2][slot_idx[-1]] == tmp_hash # Additionally, the correspondence between next_begin_offset and slot_idx can be checked tmp_hash = sha256(proof[-2]) # Step 4: Verify the intermediate node one layer above that check: proof[-3][slot_idx[-2]] == tmp_hash # Additionally, the correspondence between next_begin_offset and slot_idx can be checked tmp_hash = sha256(proof[-3]) ... # Final step: Verify the root hash matches the expected state DB root hash check: tmp_hash == root_hash ``` ### Non-Existence Proof - Case 1 **Meaning**: The proof chain ends with a leaf node, but the key\_hash stored in that leaf is inconsistent with the key\_hash obtained by applying the same hash algorithm to the queried key — that is, following the query path leads to the leaf of another existing key (the path prefix overlaps with another, and the last hop lands on "someone else's leaf").

SPV Non-Existence Proof - Case 1

As shown in the figure above, this is an example of a non-existence proof: the hash corresponding to the key we expect to verify is "12e2111". Obviously, from the leftmost diagram, we can see that according to our expected key\_hash, a leaf node of the Merkle tree is still found. However, the key corresponding to this leaf node is not the same as the key we expect, which indicates that the key we expect for SPV does not exist. Next, let's look at how to verify this through SPV. ``` # Step 1: Get slot_idx at each layer key_hash = sha256(key) # key_hash = "12e2111" slot_idx[0] = 1 slot_idx[1] = 2 ... # Step 2: Verify leaf node check: proof[-1][1] != key_hash # This step indicates that this verification is a non-existence proof! tmp_hash = sha256(proof[-1]) # Step 3: Verify the intermediate node one layer above the leaf node check: proof[-2][slot_idx[-1]] == tmp_hash # Additionally, the correspondence between next_begin_offset and slot_idx can be checked tmp_hash = sha256(proof[-2]) # Step 4: Verify the intermediate node one layer above that check: proof[-3][slot_idx[-2]] == tmp_hash # Additionally, the correspondence between next_begin_offset and slot_idx can be checked tmp_hash = sha256(proof[-3]) ... # Final step: Verify the root hash matches the expected state DB root hash check: tmp_hash == root_hash ``` **In summary**: "key\_hash verification fails" && "the entire proof can be verified using the target key's offset" yields a valid non-existence proof. ### Non-Existence Proof - Case 2 **Meaning**: At a certain internal node, the next nibble of the query path corresponds to an empty slot (the subtree is not created, or an all-zero empty slot proof is provided), and the path ends at an intermediate node rather than a leaf node.

SPV Non-Existence Proof - Case 2

As shown in the figure above, this is an example of a non-existence proof: the hash corresponding to the key we expect to verify is "12221". In this case, the verification process is more complex. Returning only the main path of the target key (tree\_proofs) is not sufficient; we also need `sibling_leftmost_leaf_proofs` corresponding to each non-empty sibling slot: each sibling item contains `slot_index`, `leftmost_leaf_key` (the original key of the leftmost leaf in that slot's subtree), and `proof_path` (the sequence of nodes from a certain layer's internal node down to that leaf along the leftmost path). The reason is explained in the "Non-Existence Proof Case Discussion - Case 2" section below. During verification, it can be understood in a manner consistent with the implementation: the main chain first verifies to the "empty slot internal"; then for each sibling sub-proof, concatenate "main chain prefix + sibling path" to form a complete chain, and verify to the root using the existence proof method (using the sibling's leftmost leaf key to walk the nibble path). ``` # The main chain is denoted as proof (i.e., tree_proofs); siblings are sibling_leftmost_leaf_proofs. # The last section is an internal node, not a leaf. # Step 1: Get slot_idx at each layer for the queried key key_hash = sha256(key) # key_hash = "12221" slot_idx[0] = 1 slot_idx[1] = 2 ... # Step 2: Verify the last section internal node: the query path falls on an empty slot at the last layer check: proof[-1][slot_idx[-1]] == 0 # Step 3: Compute hash upward from the last section internal node tmp_hash = sha256(proof[-1]) # Step 4: Verify the intermediate node one layer above check: proof[-2][slot_idx[-2]] == tmp_hash # Additionally, the correspondence between next_begin_offset and slot_idx can be checked tmp_hash = sha256(proof[-2]) # Step 5: One layer above that check: proof[-3][slot_idx[-3]] == tmp_hash # Additionally, the correspondence between next_begin_offset and slot_idx can be checked tmp_hash = sha256(proof[-3]) ... # Final step: Verify the root hash matches the expected state DB root hash check: tmp_hash == root_hash # For each sibling sub-proof in siblings (where proof_path is non-empty): # Remove the last section from the main chain, append that item's proof_path, # then roll to the root using the same steps as "existence proof" for sib in siblings: if not sib.proof_path: continue combined = proof[0 : len(proof)-1] + sib.proof_path key_hash = sha256(sib.leftmost_leaf_key) slot_idx[0] = 1 slot_idx[1] = 2 ... check: combined[-1][1] == key_hash tmp_hash = sha256(combined[-1]) check: combined[-2][slot_idx[-1]] == tmp_hash tmp_hash = sha256(combined[-2]) check: combined[-3][slot_idx[-2]] == tmp_hash tmp_hash = sha256(combined[-3]) ... check: tmp_hash == root_hash ``` **Summary**: Case 2 = Main chain (terminating at empty slot internal) + Several sibling chains (each being an "existence-style" sub-proof of the leftmost leaf of a certain slot); sibling chains share the same root\_hash with the main chain, ensuring branch completeness under the parent node's 16-slot semantics. ## Correctness Discussion This section explains: Given that the root\_hash root\_hash is trustworthy (or has been anchored to a trusted state), why the verification steps above are semantically sufficient to support the conclusion of "existence / non-existence". The text first explains SkipEmpty and the overall security goals, then discusses existence, non-existence (leaf key mismatch), and non-existence (internal empty slot + sibling sub-proofs) in three sections. ### Prerequisites and Overall Conclusions (Including SkipEmpty) **Prerequisite — Key-Derived Slot Offsets at Every Layer (including MSU Root).** All correctness arguments below presume that the verifier derives the slot offset at each layer of the proof chain from the queried key itself, **not** from prover-supplied fields. For internal nodes inside an MSU subtree the slot index is the corresponding nibble of `ComputeKeyHash(key)`; for the MSU Root layer the slot index is fixed by the network's MSU routing function applied to the key (the last byte of the key for the Pharos network). If a verifier accepts the prover-supplied `next_begin_offset` for the MSU Root layer, the Case 2 non-existence argument below collapses: a malicious prover can redirect the chain to a sibling MSU that genuinely does not contain the key, present an honest non-existence path inside that wrong MSU, and the sibling-leftmost-leaf subchains will still close to the unchanged `root_hash`. The 16-slot pinning argument constrains internal layers within an MSU but does not by itself constrain which MSU subtree was descended into. The key→MSU-slot derivation is therefore load-bearing and must be enforced before any other check. Letus skips committed empty slots when computing hashes for internal nodes (see the loop illustration earlier), therefore: * The same root\_hash may correspond to multiple "logical tree shapes" (which slots are empty, how nodes are laid out), and the proof\_node byte layout seen by the verifier from the SPV may not necessarily correspond one-to-one with the "complete 16-ary expanded diagram". * However, this does not weaken the SPV's goal: The verifier only cares about "whether the path of this key is consistent with the root commitment under the current hash rules". Skipping empty slots changes "how to compress and encode child hashes", but does not change the commitment relationship that "non-empty subtree hashes are rolled into the root by the parent node and ancestors all the way". Under this premise, when the hash function satisfies the expected cryptographic properties (collision resistance, preimage resistance; corresponding to the algorithms used in ComputeKeyHash, node hashes, etc. in the implementation), it can be considered that: * An attacker cannot tamper with a valid existence proof for a certain key and turn it into a valid non-existence proof for the same key; * Nor can they tamper with a valid non-existence proof and turn it into a valid existence proof for the same key. (If hashes could be arbitrarily collided or preimages could be found, the above conclusions would no longer hold; the arguments below all assume "ideal" hash behavior.) ### Existence Proof Case Discussion An existence proof must simultaneously satisfy: rolling hashes from bottom to top are consistent with root\_hash, and the key\_hash in the leaf is consistent with the hash computed from the queried key using the same rules. The key points of reliability can be broken down into three layers: 1. **Leaf Layer Binding** The leaf node encoding contains key\_hash (and value-side commitments). The verifier explicitly checks that the key\_hash in the leaf is consistent with `ComputeKeyHash(query key)`, which is equivalent to requiring that "this existence claim is bound to this key", not some other preimage. 2. **Path and Slot Consistency** In each layer's internal node, the 32-byte subtree root hash of the child slot must be consistent with the "current subtree root" being verified; and the slot\_idx used by the verifier to select slots is derived entirely from the nibble path of the **same key\_hash**. Therefore, an attacker cannot disguise a "subtree hash pointing elsewhere" as "the one that should be seen when going down along the query key", unless they can break the binding between the parent node hash and the child slot content (which boils down to hash collision or forging node encoding). 3. **Root Anchoring** The final `tmp_hash == root_hash` pins the entire path to that version of the state. If the root comes from a trusted source, then the meaning of "exists (K, V)" under that version is fixed jointly by the tree and encoding rules. **In summary**: The three-layer checks of leaf—path—root together ensure that the "claimed existing key" aligns with the "actual leaf content on the Merkle path" and the "global state commitment". ### Non-Existence Proof Case Discussion - Case 1 **Case 1**: Following the nibble path of the query key leads to a leaf, but the key\_hash in the leaf ≠ `ComputeKeyHash(query key)` (reaching "someone else's leaf" — the path prefix overlaps with another, and the last hop lands on an already existing different key). **Argument**: 1. **Path Authenticity** If the proof chain can close from bottom to top to root\_hash under the slot\_idx (and next\_begin\_offset consistency) at each layer derived from the query key, it indicates: On the slot sequence that the key claims to follow, the Merkle structure is self-consistent, not randomly assembled isolated nodes. 2. **Uniqueness Semantics of Leaf Content** The key\_hash in the leaf is obtained from the key at storage time using the same hash rules. In the sense of preimage resistance, it is impossible to forge a value for the "query key" that is the same as the key\_hash already written in the leaf, unless by chance of collision or it is the original key. What is written in the leaf is the hash of "another key", so the query key is not the key bound by that leaf. 3. **Conclusion** Chain verification passes ⇒ There is indeed a leaf hanging at the end of the query path on the tree; the key bound in the leaf is determined and is not the query key ⇒ In that version of the state, one cannot claim that the query key exists using that leaf as evidence. This is the semantics of "non-existence" in Case 1. ### Non-Existence Proof Case Discussion - Case 2 **Case 2**: At a certain internal node in the query path, the next nibble corresponds to an empty slot, the main chain tree\_proofs ends at the internal node without passing through a leaf. #### Why "Only Main Chain, No Sibling Information" Is Not Sufficient When only providing node material for "walking to a certain layer's internal node along the query key, with the next slot being empty", the verifier can only confirm: On the chain provided by the attacker, the sub-slot in the query direction appears to be empty. However, the SkipEmpty and sparse Trie encoding methods make the "appearance of the intermediate" less transparent in the proof than the "entire subtree commitment": A malicious Prover could theoretically attempt to construct a kind of local view — pretending the slot is empty on the query nibble, while concealing or forging the subtrees that actually exist on other slots at the same layer, as long as those slots' real paths and leaf bindings below have not been required to be shown. In other words: Relying solely on the main chain of "empty slot termination" is not sufficient to prove that "the subtree hashes on other non-empty slots at the same layer are also consistent with the current parent node, ancestors, and root"; without constraints on the "side branches", the "emptiness" could be fabricated. ```plaintext Suppose a malicious full node wants to forge a proof of "key K does not exist" to a light client, but K actually exists in the Trie: 1. Layout of the Real Internal Node (depth=d): slot[2] = H_child_a slot[7] = H_child_k - Key K's path key_hash[d]=7 leads here (non-empty, indicating K exists) slot[11] = H_child_c All other slots are empty (all zeros) 2. Forged Internal Node Constructed by the Attacker: slot[2] = H_child_a slot[7] = all zeros // "Vacate" this slot slot[9] = H_child_k // Move H_child_k to another empty slot slot[11] = H_child_c All other slots are empty (all zeros) 3. The Hashes of Both Nodes Are Identical, Because: Real: SHA256(type || padding || H_child_a || H_child_k || H_child_c) Forged: SHA256(type || padding || H_child_a || H_child_k || H_child_c) The concatenation order of non-empty hashes remains unchanged (it's the order encountered when scanning slots 0-15); only the positions have changed. 4. Verifier checks slot[7] and finds all zeros, concluding K does not exist 5. Verifier executes HashInternalNodeSkipEmpty and obtains the same hash as the real node 6. Tracing up the path to the root, the child hash recorded in the parent node matches 7. Result: The light client is deceived - it believes K does not exist, but K actually exists! ``` The figure above illustrates this kind of tampering/concealment: For example, the attacker lets the query path stop at an empty slot in the narrative, but does not synchronously provide sibling branch information consistent with the real state. #### What Role Do sibling\_leftmost\_leaf\_proofs Play For each non-empty sibling slot that needs to be declared as "indeed having data at the same layer", the Prover additionally provides `sibling_leftmost_leaf_proofs`: for the key of the leftmost leaf in that slot's subtree, and a sub-chain from a certain layer's internal node (sharing a prefix with the main chain) down to that leaf along the "leftmost path" (see the combined in the instance pseudocode earlier). During verification: 1. The main chain still verifies according to the query key's slot\_idx to the internal node where "empty slot termination" occurs, and closes with root\_hash. 2. Each sibling sub-proof, after concatenating "the main chain minus the last section" with proof\_path, rolls to the **same** root\_hash in the manner of an existence proof, recalculating the slot indices at each layer using leftmost\_leaf\_key. In this way, under the same parent node (and ancestors), the "empty slot" in the query direction and the "non-empty subtree down to a certain leaf" in the sibling direction are simultaneously constrained by the same root commitment: The subtree hashes of each non-empty slot in the parent internal must be able to support both the empty slot narrative on the main chain and the sibling chains going all the way down to real leaf nodes; both must be consistent with the parent hash computed under the node encoding and SkipEmpty rules. #### Why It Is Difficult for an Attacker to Forge Sibling Chains The verification of sibling chains uses the **own nibble path of leftmost\_leaf\_key**, not the path of the query key. Therefore: * One cannot arbitrarily take "any other leaf on the tree" to impersonate the "leftmost leaf" of that slot, unless going down from the leftmost path along leftmost\_leaf\_key, the next\_begin\_offset / slot\_idx at each layer are consistent with the encoding and close to the root — this is equivalent to performing a complete existence-style verification for that key. * One cannot simply reuse "another key" as leftmost\_leaf\_key without regard to the path: If that key is not the leftmost leaf in that slot's subtree, or if its slot positions at deeper layers are inconsistent with the structure implied by proof\_path, the verification will fail at some layer. * Under the assumptions of preimage resistance and collision resistance, forging a sibling chain that can pass verification means forging node content and leaf bindings compatible with the real root\_hash, which is computationally infeasible. **Summary (Correctness Discussion)**: Existence relies on leaf key binding + path slots + root; Case 1 relies on path authenticity + leaf bound to non-query key; Case 2 uses sibling leftmost leaf existence sub-chains in addition to the empty slot main chain to pin non-empty branches at the same layer to the same root\_hash, thereby plugging the gap of "only fabricating a segment of internal". All three are compatible with Letus's SkipEmpty encoding: not pursuing "one-to-one correspondence between proof and unique tree shape", but pursuing "semantic consistency under root commitment, and types cannot be mutually tampered". --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://docs.pharos.xyz/api-and-sdk/eth-getproof/spv-proof-theory.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.