Multi-layer hashmaps for state storage

Are you saying that, for membership, you only need to prove \exists i such that p_i(\mathsf{hash}(k,i)) = \mathsf{hash}(k,v)? In other words, just reveal i and a KZG evaluation proof for p_i(\mathsf{hash}(k,i))?

Don’t you also have to prove v is the only value of key k? After all, the authenticated data structure can be constructed maliciously and the same key can be added twice, no?

i.e., Don’t you have to prove that no other values for k exist in the other polynomials p_{i'}(X)?
i.e., \forall i' \ne i:

p_{i'}(\mathsf{hash}(k,i')) = \left\{\begin{array}{ll}\mathsf{hash}(k', v'),\ \text{for any v' and any}\ k'\ne k\\ 0\end{array}\right.

Otherwise, it seems I could pick two different indices i,j and store (k,v) at p_i(\mathsf{hash}(k, i)) while storing a different (k,v') at p_j(\mathsf{hash}(k, j)).

Then, I could equivocate about the value of k: I can convince you k has value v with a proof against p_i or it has value v' with a proof against p_j.

Maybe this can be worked around by splitting up the p_i's into two polynomials (as mentioned in your post): one for keys (e.g., \alpha_i(\mathsf{hash(k,i)}) = k) and one for values (e.g., p(\mathsf{hash(k,i)}) = v). Then, you’d have to show that all the \alpha_i's don’t share any k's.