I am trying to understand what is the cost of non-membership verification for a universal accumulator?
More specifically, how can I compute it?
Whether using an accumulator is more efficient than the Merkle Hash tree?
10
-
2$\begingroup$ Does this answer your question? Nonmembership witness in universal accumulator $\endgroup$– AleksanderCHCommented Mar 22, 2020 at 17:24
-
$\begingroup$ @ AleksanderRas I wonder the verification costs. Above two graphs one is constant one is linear, which one is correct. Its verification size o(1), is that true $\endgroup$– jhdmCommented Mar 23, 2020 at 11:09
-
$\begingroup$ Where are those graphs taken from? $\endgroup$– MaeherCommented Mar 25, 2020 at 9:58
-
$\begingroup$ @Maeher It is taken from "Real-World Performance of Cryptographic Accumulators" study $\endgroup$– jhdmCommented Mar 26, 2020 at 13:34
-
$\begingroup$ You seem to be misunderstanding what those graphs are showing. The first one shows how verification time scales with growing size of the accumulated set when run on 8 cores. The second shows how much additional cores help to speed up verification for a set of size 10.000. It turns out they don't really help at all. $\endgroup$– MaeherCommented Mar 26, 2020 at 13:57
|
Show 5 more comments
2 Answers
$\begingroup$
$\endgroup$
9
The answer depends on what universal accumulator scheme you're considering:
Sorted Merkle Tree If the Merkle Tree is sorted then one could just send two neighboring Merkle paths showing non inclusion of an element. This gives a logarithmic non-membership proof and also a logarithmic verification cost.
Merkle Tree Following the idea of Micali, Rabin and Kilian you could create two trees. One for the elements in the set and another tree for the so-called frontier set. Frontier is the set of ancestors to all values that are not in the tree (note that this is about the same size as the size of the set itself). Then, in order to prove that a value is contained in the set you use the first tree, and to prove that it is not you use the second tree. See a related answer here by Yehuda Lindell and the paper here.
RSA-accumulator Let $A$ denote the accumulator's current value and $g$ a generator in the RSA group. Let $A=g^u$ be, then, (quick reminder that in an RSA-accumulator you can "only" accumulate primes!) $exclusionProof(A,x):$ Since $x$ is not accumulated this implies that $gcd(u,x)=1,$ therefore one can compute $a,b$, so-called Bezout-coefficients, such that $ax+bu=gcd(x,u)=1$. Hence $\pi=(g^a,b).$ Verifying the proof is done by checking $\pi^x\cdot A^b=g$. Therefore, both the proof size and the verification cost is constant. However, you would need a trusted setup for an RSA accumulator. Batching exclusion proofs is also possible. See this recent result.
Pairing-based accumulator Damgard et al. creates non-membership proofs for pairing-based accumulators. The verification cost of a non-membership proof is a single pairing-check, however computing such a proof is polynomial in the accumulated set size.
answered Mar 21, 2020 at 7:59
-
$\begingroup$ Thank you. So can i say also space complexity for merkle tree is logarithmic or O(N).? I dont understand how can i compute it $\endgroup$– jhdmCommented Mar 21, 2020 at 11:45
-
$\begingroup$ If there are N elements in your set, then you will have N leaves in your Merkle-tree. Hence total number of nodes in the Merkle tree will be N+(N/2)+(N/4)+...4+2+1= 2N -1. Namely, your space complexity is O(N). $\endgroup$ Commented Mar 21, 2020 at 12:55
-
$\begingroup$ @stván András Seres you said verification cost is constant but "Batch verify n proofs faster than verifying a single proof n times" is written gakonst.com/deep-dive-rsa-accumulators. So verification cost o(n) or o(1). I dont understand it. $\endgroup$– jhdmCommented Mar 22, 2020 at 21:49
-
$\begingroup$ You could naively verify n non-membership proofs one-by-one. However, luckily, RSA-accumulators admit batching of non-membership proofs. Essentially you can batch-verify $n$ non-membership proofs and verify them at the cost of a single non-membership proof verification. Although the prover time is still linear in the number of batched non-membership proofs. Hence verification cost is o(1), but creating the batched proof is o(n). Pls refer to the linked blog post or to the Boneh et al. paper. $\endgroup$ Commented Mar 23, 2020 at 7:54
-
$\begingroup$
$\endgroup$
2
In section 5.3 of this paper you can find a comparison between an accumulator and MHT. The complexity totally depends on the scheme.
In general, MHT is linear in the proof of exclusion (in the order of depth of the tree). Because the verifier has to check all the possible paths to convince a leaf is not in the tree.
-
$\begingroup$ so sorted merkle tree needs logarithmic, rsa dynamic accumulator needs O(1) verification cost. Is it true? $\endgroup$– jhdmCommented Apr 1, 2020 at 9:44
-
$\begingroup$ I couldnt understand this article. What is the sorted merkle tree and rsa accumulator verification, cost? Which one is better for revocation. $\endgroup$– jhdmCommented Apr 20, 2020 at 7:31