blocks|key|2832299|text|type|unstyled|depth|inlineStyleRanges|entityRanges|data|entityMap^0^^$0|@$1|2|3|-4|4|5|6|B|7|@]|8|@]|9|$]]]|A|$]]

<h2>(ZK) Sets vs. accumulators</h2>
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:
<ul>
<li>constant-sized digest</li>
<li>constant-sized proofs of (non)membership</li>
<li>a quasi-commutativity property (see [Bd93])</li>
</ul>
For example, Micali et al.'s notion of zero-knowledge sets did not have constant-sized proofs, nor the quasi-commutativity property.
<h2>Vector commitments</h2>
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 &quot;open&quot; the element $v_i$ at position $i$ with an &quot;opening proof&quot;.
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:
<ul>
<li>commitments leak nothing about the vector</li>
<li>opening proofs leak nothing but their own validity.</li>
<li>(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$.)</li>
</ul>
<h2>(ZK) elementary databases</h2>
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 &quot;any&quot; 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 <a href="https://ethresear.ch/t/multi-layer-hashmaps-for-state-storage/7211" rel="nofollow noreferrer">doing other things</a> though, but there'd be caveats.)
<h3>Proofs of non-membership in (ZK-)EDBs</h3>
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.
<h3>Alternative names for (ZK-)EDBs</h3>
Really, a commitment to a database as explained above goes by different names in the cryptographic literature:
<ul>
<li>authenticated dictionary (my preferred terminology)</li>
<li>authenticated database</li>
<li>authenticated key-value store</li>
<li>key-value commitments</li>
<li>elementary database</li>
<li>etc.</li>
</ul>
Depending on the constructions, some of these have ZK properties.
<h2>Your questions</h2>
<h3>$Q_1$ Could these primitives be transferred mutually?</h3>
It's not exactly clear to me what you mean by &quot;transferred&quot;. But if, for example, you mean:
<blockquote>
Can I build a VC from an accumulator, in a black-box fashion?
</blockquote>
Then, the answer is mostly &quot;no,&quot; 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:
<ol>
<li>Showing you a valid proof for $(i, v_i)$, which is accumulated in, as expected.</li>
<li>Showing you (or another person) a valid proof for $(i, v_i')$, with $v_i' \ne v_i$, which has been maliciously accumulated in.</li>
</ol>
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., &quot;blockchains&quot;, where the digest is correctly computed by a quorum of honest servers.
<h3>$Q_2$: What's the difference?</h3>
Hopefully, this question is answered by now.
<h3>$Q_3$: Could we say that Vector commitment is Zero-knowledge Elementary Database</h3>
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 &quot;all ones&quot; vectors:
$$d\stackrel{?}{=} \prod_i h_i$$
<h2>References</h2>
[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; <a href="https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Zero%20Knowledge/Zero-Knowledge_Sets.pdf" rel="nofollow noreferrer">https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Zero%20Knowledge/Zero-Knowledge_Sets.pdf</a>
[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; <a href="https://doi.org/10.1145/3319535.3345652" rel="nofollow noreferrer">https://doi.org/10.1145/3319535.3345652</a>
[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; <a href="https://eprint.iacr.org/2020/1239" rel="nofollow noreferrer">https://eprint.iacr.org/2020/1239</a>

Vector commitment allows one to commit to an ordered sequence of $q$ value ($m_1,\cdots,m_q$) in such a way that one can later open the commitment at specific positions (e.g., prove that $m_i$ is the $i$-th committed message).
A Zero-knowledge set means that users commit to a set and subsequently prove the (non-)membership of some elements without revealing any further information (not even the cardinality of the committed set).
Accumulator allows to succinctly present a set by an accumulation value with respect to which short (non-)membership proofs about the set can be efficiently constructed and verified.
Zero-knowledge accumulator additionally provides hiding guarantees: Accumulation values and proofs leak nothing about a set.
Zero-knowledge Elementary Database allows to commit a database that consists of the pairs $(i, DB[i])$ and prove that $DB[i]$ is the value on position $i$ without revealing any further information.
I confuse these primitives. The zero-knowledge set and Zero-knowledge accumulator set are designed for unordered data. Vector commitment and Zero-knowledge Elementary Database are designed for ordered data.
<ol>
<li>Could these primitives be transferred mutually?</li>
<li>What's the difference?</li>
<li>Could we say that Vector commitment is Zero-knowledge Elementary Database?</li>
</ol>

What's the difference among Vector Commitment, Zero-knowledge Set, Zero-knowledge Accumulator, and Zero-knowledge Elementary Database?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

Vector承诺允许您提交一个有序的q值序列(m_1,\cdots,m_q)，以便以后可以在特定位置打开承诺(例如，证明m_i是i-th提交的消息)。零知识集意味着用户提交到一个集合，并随后证明某些元素的(非)成员资格，而不透露任何进一步的信息(甚至是提交集合的基数)。累加器允许简洁地用累加值表示集合，从而有效地构造和验证关于集合的短(非)成员资格证明。零知识累加器另外还提供隐藏保证:累积值和证据

问向量承诺、零知识集、零知识累加器和零知识基础数据库有什么区别？
EN

回答 1

Cryptography用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问向量承诺、零知识集、零知识累加器和零知识基础数据库有什么区别？EN