(ZK) Sets vs. accumulators
Zero-knowledge sets and zero-knowledge accumulators are the same primitive: a hiding commitment to an unordered set $S = \{e_1, \ldots, e_n\}$ of elements with support for proofs of (non)membership that reveal nothing but their own validity (i.e., ZK).
However, some folks might want to distinguish between the two notions and require that accumulators have:
- constant-sized digest
- constant-sized proofs of (non)membership
- a quasi-commutativity property (see [Bd93])
For example, Micali et al.'s notion of zero-knowledge sets did not have constant-sized proofs, nor the quasi-commutativity property.
Vector commitments
Vector commitments (VC) are a binding commitment (and maybe even hiding) to a vector of ordered elements $v = [v_1, v_2, \ldots, v_n]$ which allow you to "open" the element $v_i$ at position $i$ with an "opening proof".
Vectors are a little different than sets, since an element has to have a position in a vector. In a set, it does not have a position.
This is useful if you want to keep track of some sort of ordered data, like balances of accounts in a cryptocurrency, numbered from 1 to $N$. In this sense, a VC can help convince any external verifier that user $i$'s balance is $b_i$.
With an accumulator you couldn't do this. (Well, you might try to, but you are likely to mess up in most situations, as I'll argue below.)
As you can imagine, one can also define a notion of ZK-VCs. Such VCs would satisfy:
- commitments leak nothing about the vector
- opening proofs leak nothing but their own validity.
- (it might even useful to have proofs of opening that hide the position, but not the value: e.g., a proof that $\exists$ a position $i$ such that $v_i = v$ for a public $v$.)
(ZK) elementary databases
A ZK elementary database (ZK-EDB) is a commitment to a dictionary $D$ which maps any key $k$ to a value $v$ or to $\bot$ (i.e., $D(k) = v$), with all the ZK properties you'd expect (see above). Mapping to $\bot$ means key $k$ has no value.
The word "any" here is very important because it serves to distinguish an elementary database from a VC: the keys can be anything, not just numbers from 1 to $N$. For example, the keys can be 256-bit numbers (i.e., the key-space can be exponentially-large).
This distinction is actually important in practice. For example, we can get a very efficient VC for vectors of size $N$ from KZG polynomial commitments [KZG10], with $N$ as large as $2^{28}$. But supporting larger $N$ becomes harder and harder due to the KZG trusted setup, which must output KZG public parameters sized linearly in $N$.
As a result, we could not use this KZG-based VC to build an elementary database by just treating the key as a position in the vector, because some keys would be too large and fall outside the vector. (You could try doing other things though, but there'd be caveats.)
Proofs of non-membership in (ZK-)EDBs
Another thing that differentiates a ZK elementary database from a VC is it supports proofs of non-membership: i.e., one can prove that a key is not mapped to any value.
In contrast, in VCs, we typically think of all positions as having a value. If there's no value, then the value is 0.
Of course, one can naturally define a notion of VC that supports non-membership.
Note that proving non-membership is not as simple as letting all unmapped keys be mapped to a hard-coded $\bot$ value.
Why? Because the space of keys can be exponentially-large! This means building such a database where all values are initially $\bot$ could take exponential time. So one has to be careful. A perfect example of doing this efficiently are compressed Merkle prefix trees, which you can think of as a non-ZK elementary database.
Alternative names for (ZK-)EDBs
Really, a commitment to a database as explained above goes by different names in the cryptographic literature:
- authenticated dictionary (my preferred terminology)
- authenticated database
- authenticated key-value store
- key-value commitments
- elementary database
- etc.
Depending on the constructions, some of these have ZK properties.
Your questions
$Q_1$ Could these primitives be transferred mutually?
It's not exactly clear to me what you mean by "transferred". But if, for example, you mean:
Can I build a VC from an accumulator, in a black-box fashion?
Then, the answer is mostly "no," unless you can assume that the source of your VC commitment/digests is trusted.
I'll explain.
You might naturally think that you can build a VC from an accumulator by accumulating the set $\{(i, v_i) | \forall i \in [n]\}$.
You could easily open position $i$ by showing an accumulator membership proof for $(i, v_i)$.
...but if the server computing the accumulator is malicious, they can easily attack you by:
- Showing you a valid proof for $(i, v_i)$, which is accumulated in, as expected.
- Showing you (or another person) a valid proof for $(i, v_i')$, with $v_i' \ne v_i$, which has been maliciously accumulated in.
This effectively breaks position binding the key property of a VC defined in [CF13].
The malicious server can do this because there is no guarantee that the accumulator/digest has only one tuple of the form $(i, *)$.
By the way, this type of setting where the server maliciously computes digests is quite realistic: e.g., consider applications such as Certificate Transparency (CT) [TBP+19]
Nonetheless, there are settings where you can assume the accumulator/digest is correct, such as in Byzantine-fault tolerant systems, a.k.a., "blockchains", where the digest is correctly computed by a quorum of honest servers.
$Q_2$: What's the difference?
Hopefully, this question is answered by now.
$Q_3$: Could we say that Vector commitment is Zero-knowledge Elementary Database
First, note that a ZK-EDB is also a ZK-VC: just treat the vector positions as keys (since the keys are arbitrarily large, any vector position will fit in a key, so we will not run into the issue from above).
Clearly though, a ZK-VC is not necessarily a ZK-EDB because, for example, you cannot map a key of 256 bits into a position of 28 bits (like in the KZG example from above).
Second, let's say that your VC could be tweaked into an non-ZK elementary database (e.g., this is actually possible for some constructions [TXN20e]).
You'd still have the problem that VCs are typically not zero-knowledge: i.e., commitments or opening proofs might leak something. See the original definition by Catalano and Fiore [CF13].
An example of a VC that's not ZK is the bilinear-based construction by from [CF13], where the digest of a vector $[v_1,\ldots, v_n]$ is:
$$d = \prod_i h_i^{v_i}$$
One can easily test for example if the vector is the "all ones" vectors:
$$d\stackrel{?}{=} \prod_i h_i$$
References
[Bd93] One-Way Accumulators: A Decentralized Alternative to Digital Signatures; by Benaloh, Josh and de Mare, Michael; in EUROCRYPT '93; 1994
[CF13] Vector Commitments and Their Applications; by Catalano, Dario and Fiore, Dario; in PKC'13; 2013
[KZG10] Constant-Size Commitments to Polynomials and Their Applications; by Kate, Aniket and Zaverucha, Gregory M. and Goldberg, Ian; in ASIACRYPT'10; 2010
[MRK03] Zero-knowledge sets; by S. Micali and M. Rabin and J. Kilian; in 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.; 2003; https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Zero%20Knowledge/Zero-Knowledge_Sets.pdf
[TBP+19] Transparency Logs via Append-Only Authenticated Dictionaries; by Tomescu, Alin and Bhupatiraju, Vivek and Papadopoulos, Dimitrios and Papamanthou, Charalampos and Triandopoulos, Nikos and Devadas, Srinivas; in ACM CCS'19; 2019; https://doi.org/10.1145/3319535.3345652
[TXN20e] Authenticated Dictionaries with Cross-Incremental Proof (Dis)aggregation; by Alin Tomescu and Yu Xia and Zachary Newman; in Cryptology ePrint Archive, Report 2020/1239; 2020; https://eprint.iacr.org/2020/1239
