Precomputation and updates

Caulk employs a precomputation step in order to make the use of it sublinear in the group size. This allows neatly separating the membership proof part of Semacaulk from the nullifier computation, while allowing to blind the precomputed membership proof differently at each use.

When a group is updated, precomputation is needed again, so there are a few options as to how to avoid many precomputations in frequently updated groups. These include storing a history of valid group commitments or batching insertions and updating the precomputation after some predefined time slot. This also opens the possibility to use a centralised, but verifiable, service to compute these for them, since a unique feature of the precomputation in Caulk is that a batch can be computed even more cheaply. There are, of course, privacy implications when using a service, but these can also be mitigated using several techniques and trade-offs.

Additionally, the precomputation done in Caulk is amenable to efficient updates when the group changes, justifying a higher cost for the initial precomputation.

Precomputed data

Precomputed data consists of the following:

  1. \(\mathsf{mimc\_cts}\)
  2. \(\mathsf{mimc\_cts\_coset\_evals}\)
  3. \(\mathsf{zh\_inverse\_coset\_evals}\)
  4. \(\mathsf{q\_mimc}\)
  5. \(\mathsf{q\_mimc\_coset\_evals}\)
  6. \(\mathsf{l0\_coset\_evals}\)
  7. \(\mathsf{w_1\_mapping}\)
  8. \([{\mathsf{W}_1}^{(i)}]_2\) for all indices \(i \in I\)
  9. \([{\mathsf{W}_2}^{(i)}]_2\) for all indices \(i \in I\)

The only parts of the precomputed data which rely on the secret index \(i\), which denotes the secret position of the prover's identity commitment in the accumulator, are \([{\mathsf{W}_1}^{(i)}]_2\) and \([{\mathsf{W}_2}^{(i)}]_2\).

The Caulk+ paper defines:

  • \({\mathsf{W}_1}^{(i)} = (C(X) - v_i) / (X - \omega^i)\)
  • \({\mathsf{W}_2}^{(i)} = Z_H(X) / (X - \omega^i)\)

Updating commitments to \(\mathsf{W}_1^{(i)}\)

For many of Semacaulk's use cases, users insert new items into the accumulator, and do not update existing items. As such, this section will only discuss how to update commitments to \(\mathsf{W}_1^{(i)}\) when the accumulator changes at an index \(j\) which is different from that of the user's entry \(i\).

We can efficiently update \([{\mathsf{W}_1}^{(i)}]_2\) using the technique described in TADBFK20, section 3.4.2, where \(i \neq j\).

When an element at \(j\) is updated and \(i \neq j\), and the new element is \(v_j = v_\mathsf{zero} + \delta\), the new accumulator is:

\(C(X) - L_j(X) \cdot v_\mathsf{zero} + L_j \cdot v_j\)

\(= C(X) - L_j(X) \cdot (v_\mathsf{zero} + v_j)\)

\(= C(X) + \delta \cdot L_j(X)\)

\({\mathsf{W{new}}_1}^{(i)}\) is therefore:

\(\frac{C(X) - v_i + \delta \cdot L_j(X)}{X - \omega^i}\) \( = {\mathsf{W}_1}^{(i)} + \delta \cdot \frac{L_j(X)}{X - \omega^i}\)

To use the homomorphic properties of KZG commitments, we need to compute \([\frac{L_j(X)}{X - \omega^i}]_2\), multiply it by \(\delta\), and add it to \([{\mathsf{W}_1}^{(i)}]_2\). Yet we must do this with lower than the \(O(n)\) cost of a full KZG \(\mathsf{commit}\) operation.

TADBFK20 section 3.4.2 describes how to do so without performing \(\mathsf{commit}\) at all. This document will be updated to elaborate on the method.

Updating commitments to \(\mathsf{W}_2^{(i)}\)

For use cases where users do not update their own entries (i.e. \(i \neq j\)), there is no need to update the precomputed commitments to \(\mathsf{W}_2^{(i)}\).