HashWires: Hyperefficient Credential-Based Range Proofs

Authors: Konstantinos Chalkias (Novi / Facebook), Shir Cohen (Novi / Facebook / Technion), Kevin Lewi (Novi / Facebook), Fredric Moezinia (Novi / Facebook), Yolan Romailler (Novi / Facebook / Kudelski Security)

Volume: 2021
Issue: 4
Pages: 76–95
DOI: https://doi.org/10.2478/popets-2021-0061


Download PDF

Abstract: This paper presents HashWires, a hash-based range proof protocol that is applicable in settings for which there is a trusted third party (typically a credential issuer) that can generate commitments. We refer to these as “credential-based” range proofs (CBRPs). HashWires improves upon hashchain solutions that are typically restricted to micro-payments for small interval ranges, achieving an exponential speedup in proof generation and verification time. Under reasonable assumptions and performance considerations, a HashWires proof can be as small as 305 bytes for 64-bit integers. Although CBRPs are not zero-knowledge and are inherently less flexible than general zero-knowledge range proofs, we provide a number of applications in which a credential issuer can leverage HashWires to provide range proofs for private values, without having to rely on heavyweight cryptographic tools and assumptions.

Keywords: range proofs, credentials, hash-chains, accumulators, cryptographic commitments, malleability, micro-payments, location privacy

Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution-NonCommercial-NoDerivs license.