Cryptographic accumulators and proof of immutability

Question

I'm looking for a possible primitive representing an updatable accumulator with some features. Basically, I would like to perform in-place updates of an ordered list of elements and provide a proof that the new accumulator value encodes the updated elements leaving the others untouched.

In other terms:

1. $\alpha$ accumulates $v_1$, $v_2$, $\dots$, $v_n$ in this order.
2. I replace $v_i$ with $v^{\prime}_i$ and get $\alpha^{\prime}$.
3. I want to have a proof $P$ so that $\textrm{ACCEPT}(P,\alpha,\alpha^{\prime},i,v_i,v^{\prime}_i) = \textrm{YES}$ if and only if the $i$-th element changed from $v_i$ to $v^{\prime}_i$ in $\alpha^{\prime}$ and that $v_j$ (with $j\neq i$) are untouched w.r.t. $\alpha$.

I'm aware of techniques that allows one to append elements to an accumulator and proving that the new value is given by the old list with just the new elements appended (see Google's Certificate Transparency Initiative) but I've found nothing about the above features.

Thanks a lot!

Answer 1

Note: What you describe is actually a vector commitment (VC), not an accumulator, since you're committing to an order list of elements and presumably want to prove that a position $i$ has a certain value $v_i$.

It's actually very simple to prove that position $i$ changed from $v_i$ in digest $\alpha$ to $v_i'$ in digest $\alpha'$, thanks to the fact that most vector commitments are homomorphic.

Let $\mathsf{VC.Com}(\vec{v}) \rightarrow \alpha$ denote the algorithm that returns the commitment $\alpha$ to a vector $\vec{v}$.

Most VCs have a useful homomorphism property:

$$\mathsf{VC.Com}(\vec{v}) + \mathsf{VC.Com}(\vec{v}') = \mathsf{VC.Com}(\vec{v} + \vec{v}')$$

As a result, if you have a homomorphic VC and you want to check only position $i$ was updated, then all you need to verify is that:

$$\alpha' - \alpha = \mathsf{VC.Com}([0,0, \ldots, v_i' - v_i, \ldots 0])$$ where: $$[0,0, \ldots, v_i' - v_i, \ldots 0]$$ denotes the vector where all positions are 0 except for the $i$th, which is set to $v_i' - v_i$.

Therefore, the proof $P$ is empty.

Even better, most schemes support computing $\mathsf{VC.Com}([0,0, \ldots, v_i' - v_i, \ldots 0])$ in $O(1)$ time, so you can perform this check in constant time.

An example with [KZG10]-based VCs.

To commit to vectors of size $n$, KZG requires public parameters $h_i = g^{\mathcal{L}_i(\tau)}$ for all $i\in[n]$, where $\tau$ is a trapdoor.

(For the purpose of this example, you thankfully do NOT need to know that $\mathcal{L}_i(X) = \prod_{\substack{j\in[n]\\j\ne i}}\frac{X - j}{i - j}$ denotes the $i$th Lagrange polynomial for the evaluation domain $[n]$.)

The commitment is computed as:

$$\mathsf{VC.Com}(\vec{v}) = \alpha = \prod_{i\in [n]} h_i^{v_i}$$

The homomorphism should be obvious: \begin{align} \mathsf{VC.Com}(\vec{v} + \vec{v}') &= \prod_{i\in [n]} h_i^{v_i + v_i'}\\ &= \prod_{i\in [n]} \left(h_i^{v_i} \cdot h_i^{v_i'}\right)\\ &= \left(\prod_{i\in [n]} h_i^{v_i}\right) \cdot \left(\prod_{i\in[n]} h_i^{v_i'}\right)\\ &= \mathsf{VC.Com}(\vec{v}) + \mathsf{VC.Com}(\vec{v}') \end{align}

Therefore, to verify the update was done correctly, you can check if: $$\alpha' - \alpha \stackrel{?}{=} h_i^{v'_i - v_i}$$

References

[KZG10] Constant-Size Commitments to Polynomials and Their Applications; by Kate, Aniket and Zaverucha, Gregory M. and Goldberg, Ian; in ASIACRYPT'10; 2010