For proof of inclusion (used by SPV nodes) Bitcoin relies on Merkle proofs. Why Merkle trees were chosen and not RSA accumulators, as they can be used to provide a shorter proof?

What are the advantages/disadvantages of RSA accumulators vs. Merkle proof?

  • RSA accumulators are far harder to implement correctly
  • RSA accumulators need a trusted setup (someone, or multiple someones, must come up with a sufficiently large integer that is the product of 2 primes, and then throw those individual primes away). Bitcoin is generally designed to avoid trusted parties.
  • For a 128-bit security level, you need at least 3000 bits RSA moduli, meaning that a proof would be 3000 bits. That's only a win compared to Merkle paths for trees with more than 12 levels, which in the case of transactions in blocks, means over 4096 transaction. That isn't usually the case, and even when it is, it is only barely so.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.