1

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?

enter image description here

enter image description here

jhdm
  • 187
  • 6
  • 2
    Does this answer your question? Nonmembership witness in universal accumulator – AleksanderCH Mar 22 '20 at 17:24
  • @ 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 – jhdm Mar 23 '20 at 11:09
  • Where are those graphs taken from? – Maeher Mar 25 '20 at 09:58
  • @Maeher It is taken from "Real-World Performance of Cryptographic Accumulators" study – jhdm Mar 26 '20 at 13:34
  • 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. – Maeher Mar 26 '20 at 13:57
  • @Maeher So can i say rsa accumulator's verification cost is O(1) for exclusion testing – jhdm Mar 31 '20 at 07:59
  • No, since it quite clearly grows linearly with the number of accumulated elements. But you should also not try to reverse engineer the asymptotic runtime complexity of an algorithm from a graph depicting actual runtime for some range of inputs. The two are only weakly related. – Maeher Mar 31 '20 at 08:10
  • @István András Seres @ Maeher says verification cost is O(1) but reating the batched proof is o(n). According to this, rsa accumulator is faster verification cost compared to merkle tree for exclusion proof. Am i right? – jhdm Apr 01 '20 at 09:11
  • @Maeher According to figure rsa accumulator verification cost seems linearly but it should be o(1) – jhdm Apr 18 '20 at 21:41
  • @Maeher What should be verification cost ı dont understand because its update cost o(1) – jhdm Apr 19 '20 at 16:44

2 Answers2

0

In section 5.3 of this paper you can find a comparison between an accumulator and MHT. The complexity totally depends on the scheme.

enter image description here

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.

Mahdi
  • 306
  • 1
  • 4
  • 17
  • so sorted merkle tree needs logarithmic, rsa dynamic accumulator needs O(1) verification cost. Is it true? – jhdm Apr 01 '20 at 09:44
  • I couldnt understand this article. What is the sorted merkle tree and rsa accumulator verification, cost? Which one is better for revocation. – jhdm Apr 20 '20 at 07:31
0

The answer depends on what universal accumulator scheme you're considering:

  1. 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.

  2. 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.

  3. 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.

  4. 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.

István András Seres
  • 1,184
  • 1
  • 9
  • 23
  • 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 – jhdm Mar 21 '20 at 11:45
  • 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). – István András Seres Mar 21 '20 at 12:55
  • @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 https://www.gakonst.com/deep-dive-rsa-accumulators. So verification cost o(n) or o(1). I dont understand it. – jhdm Mar 22 '20 at 21:49
  • 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. – István András Seres Mar 23 '20 at 07:54
  • @ István András Seres Thank you! – jhdm Mar 23 '20 at 08:38
  • Can i ask one more question because my mind is confusing. "Real-World Performance of Cryptographic Accumulators" study verification seems logarithmic. Is that also prover time. I dont understand – jhdm Mar 23 '20 at 08:57
  • @ István András Seres I added an image for my previous question. I just want to know which one is more efficient about merkle hash tree or rsa accumulator which is supporting nonmember testing. Verification cost is o(1) for accumulator,isn't it – jhdm Mar 23 '20 at 09:03
  • The study you cite was published in 2013. Back then they did not know batched RSA non-membership proofs, hence your confusion. Batched RSA non-membership proofs are quite a recent result. – István András Seres Mar 23 '20 at 10:13
  • if i cancel 5 certificate, so what is the corresponding verification cost. How can i calculate it – jhdm Apr 18 '20 at 14:41