Using polynomial commitments to replace state roots

To prove non-membership of some keys one could try to construct a fancy proof that a key is not in S_k(1), ..., S_k(N) . Instead we simply sort the keys so that to prove non-membership it suffices to prove membership of two adjacent keys, one smaller than the target key and one larger.

This is insufficient. There also needs to be proof that the smaller key and larger key are in fact, adjacent.