In the vector commitment based on RSA accumulators with batching, witnesses can be updated efficiently. The opening of an element of the vector is a combination of a batched RSA membership witness and a batched non-membership witness. Both can be updated in time independent of N. Updating the commitment value requires deletes from the accumulator, which cannot be done efficiently in general. However, it can be done efficiently if all the updates also include the witnesses for the current values in the VC. One other detail is that the batched non-membership witness (compressed proof) cannot be updated directly, updating requires the individual non-membership witnesses for each of the zero-bits of the element. Non-membership updates are described in https://www.cs.purdue.edu/homes/ninghui/papers/accumulator_acns07.pdf.
That said, the scheme based on RSA accumulators does have high concrete overhead, so you may be looking for something more efficient.
OK, I think we need to clarify on this point 5.ii: The cost per witness is of course small in both Kate and RSA accumulators. However, if you want to satisfy point 4, then you need to precompute all the witnesses (for all n points); Updating this full set of witnesses take O(n) or longer, this is the problem.
I think we can do better with RSA accumulators than O(n) in the case that we do not need the full set of witnesses after every update, but only a small subset of the witnesses. I guess a lot of applications fall in this category.
The trick is to split the values in \sqrt{n} groups and calculate a base witness per group. This is the part that all witnesses in the group have in common. For every update we only need to update these O(\sqrt{n}) base witnesses. To generate a witness for a set of values from a single group we need O(\sqrt{n}) time, because we can use the base witness as a starting point.
@vbuterin I think we are missing a pretty fundamental requirement: I shouldn’t need linear O(K) data to update my witness or someone else should be able to calculate all such updates in less than O(k^2) time and give me the witness.
Otherwise, it seems if we scale Eth2 to say, all of Amazon EC2, then for me to update my toy ERC20 contract, I’d need to go through all of O(K) updates that happened on the entirety of EC2. Thats way too much data for my client to handle. In fact thats too much for most end users in Eth1 today. We’ve created validators that don’t need to store blocks, but at the cost of making end users see and process every block.
As far as I know, Merkle trees are the only thing that stops this, requiring roughly log(k) data to update a witness. This seems to scale well. But they fail requirement 3).
Is 3) a necessary requirement? For account based payments, Alice should be able to payBob (i.e. update his account) while only knowing the witness to her account and her balance. Merkle tree’s fail this requirement. But for a smart contract call from contract A to B, we need to know the state of B to execute the contract. So why do we care ?
I think that’s covered by the other requirements; you can just ping one of the nodes that has the “auxiliary information” (which by the other requirements is required to be efficiently updateable) and ask it for an updated proof. But yeah, the ability to maintain a smaller amount of auxiliary info to maintain a partial state and keep it updated in less time would be nice.
I actually think this should be taken seriously: The proof size for this “KZG verkle tree” construction is not sublinear, but still way smaller than for Merkle trees. All the KZG proofs can actually batched together into a single one; the only thing that needs to be transmitted is the intermediat KZG commitments that these need to be checked against. Proof size is therefore something like \log_k n - 1 group elements, where r is the verkle branching factor. In practice e.g. r=2^{16} and n=2^{30}, so we realistically only need one additional group element per proven position. That’s about 20x better than Merkle trees!
In terms of updating witnesses, an update does not touch all the commitments, so for each update only k \log_r n have to be updated. So using the KZG precomputation/updating techniques from this paper would allow efficient proofs and updates as per 5.(ii)
Even though they don’t fulfill all the criteria, I actually now feel that verkle trees are better than what we have considered so far. In addition, they provide another elegant construction for key-value stores in the form of “verkle tries”.
Thanks to @Pratyush for pointing out these properties on the twitter thread!
[Edit: I noticed I was using k to describe two different values. I now changed it so that k is the same as previously (number of reveals), and r is the verkle branching factor]
What do you mean by “verkle branching factor” here? The number of KZG commitments? The branching factor of the top-level Merkle tree? I’m confused as to how such a small proof at the top is possible; seems to me like if there 2^{30} elements in 2^{16} trees, then the tree proof for k accounts would still be of size k * (16 - log(k)).
Sorry I think I might have confused this by using k to mean two different things – corrected above.
The proof for k accounts would be
The KZG commitments of all the intermediate layers to be proven – that’s k (\log_r(n) - 1) group elements
One single proof that all elements and intermediate commitments were decomitted correctly – this can be aggregated into a single KZG proof, so another group element.
I’m still confused by (1). Is there a Merkle tree at the top, or something else? If it’s a Merkle tree, where are the hashes? Or is it just a commitment to a set of values each of which are themselves commitments?
Ah, I see. So it functions like a Merkle tree, except instead of proofs having length (r-1) * log_r(n) it’s just log_r(n). Got it. Witness update costs would be on the order of r * log_r(n) though, correct?
If n ~= 2**28 then maybe we can encode a compact vector commitment using prime number indices and an RSA accumulator.
Suppose there’s a function p(k) returning the k-th prime for k<2^{32} (e.g. the Meissel Lehmer Algorithm). Then we can encode a pair (key, value) into a single prime number: pair = p( key * p(value + 2**28) ).
(This assumes the value is also in the ballpark \text{value} < 2^{28}).
We can update an accumulator as usually: A1 = A0^t where t = pair_1 * pair_2 * pair_3 * ... . Difference is that now the pairs are about 4 bytes instead of the 32 bytes when using the conventional approach of hashing into primes. That makes updating witnesses 8 times more efficient. The scheme also becomes more simple than regular RSA VC.
Further techniques regarding batching and efficient witness updates have been mentioned here by @ben-a-fisch .
How fast are the witness update techniques? Is there a way to adjust the construction so that you can update all the data needed to compute any witness after one update in log(n) time?
I do not understand how the pairing works. If both key and value are 28 bits, then key * p(value + 2^{28}) will be larger than 2^{32} so you can not apply the p-function on it again.
You’re right. I was sloppy with the bounds. That’s an error. You have to adjust it. Either you’re able to calculate p(k) for higher k or you have to reduce number of different values or keys. Nevertheless, the overall concept stays the same.
In the section “Distributed accumulator updates” the paper of Boneh et al. says about updating membership witnesses: “Using the RootFactor algorithm this time can be reduced to O(n log(n)) operations or amortized O(log(n)) operations per witness.”
BTW, I guess the “ideal” in the title means meeting the 5 properties you @vbuterin list, instead of using “ideal group/ring, etc.” (from Math perspectives)?