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?
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.Sign up to join this community
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.
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.