Paper 2020/430

Hierarchical One-out-of-Many Proofs With Applications to Blockchain Privacy and Ring Signatures

Aram Jivanyan and Tigran Mamikonyan


The one-out-of-many proof is a cryptographic zero-knowledge construction enabling the prover to demonstrate knowledge of a secret element among the given public list of cryptographic commitments opening to zero. This method is relying on standard Decisional Diffie-Hellman security assumptions and can result in efficient accountable ring signature schemes [4] and proofs of set memberships [5] with a signature size smaller than all existing alternative schemes relying on standard assumptions. This construction also serves as a fundamental building block for numerous recent blockchain privacy protocols including Anonymous Zether, Zerocoin, Lelantus, Lelantus-MW, Triptych and Triptych-2. One-out-of-many proofs require O(logN)-sized communication and can be implemented in O(N) time for the verifier and O(NlogN) time for the prover. In this work, we introduce a new method of instantiating one-out-of-many proofs which reduces the proof generation time by an order of magnitude. In certain practical applications our method also helps to fasten the verification process of multiple simultaneously generated proofs. Our approach still results in shorter proofs comprised of only a logarithmic number of commitments and does not compromise the highly efficient batch verification properties endemic to the original construction. We believe this work can also foster further research towards building more efficient one-out-of-many proofs which are extremely useful constructions in the blockchain privacy space and beyond.

Available format(s)
Cryptographic protocols
Publication info
group signaturesring signaturesconfidential transactionsblockchain privacyZerocoinLelantusone-out-of-many zero-knowledge proofs
Contact author(s)
aram @ skycryptor com
reuben @ zcoin io
poramin @ zcoin io
2020-04-15: received
Short URL
Creative Commons Attribution


      author = {Aram Jivanyan and Tigran Mamikonyan},
      title = {Hierarchical One-out-of-Many Proofs With Applications to Blockchain Privacy and Ring Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2020/430},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.