Paper 2026/1074

Cryptocurrency-Backed Trustless Anonymous Tokens and Their Applications

Abstract

Public blockchains like Ethereum deliver transparency, but adding anonymity remains a fundamental challenge. Existing proposals either offer limited anonymity guarantees or rely on heavy cryptographic machinery, e.g., zero-knowledge proofs. We introduce \emph{Blockchain Anonymous Tokens} (BAT), a system for efficient \emph{sender}-anonymous transactions on transparent blockchains. Building on the observation that \emph{one-time-spendable tokens suffice for many applications}, BAT has a lightweight design using classic anonymous tokens due to Chaum (1983). Unlike such tokens, though, BAT is designed to work in a transparent decentralized setting, where issuers are untrusted (i.e., any single potentially malicious entity can be the issuer) and spends happen publicly. BAT issuance is compact: A client can receive $\ell$ tokens with just $\mathcal{O}(1)$ on-chain communication and computation. We formalize the notion for BAT, and provide a concretely efficient construction. Our BAT construction requires no on-chain verification of expensive zero-knowledge proofs; just a signature verification during spends and a single exponentiation on-chain during issuance. We present several applications of BAT in various blockchain contexts. We prove the security of our BAT scheme assuming hardness of the one-more computational Diffie-Hellman assumption in a bilinear pairing group in the random oracle model and with any secure digital signature scheme. We implement and evaluate BAT and show that compared to the closest baseline, Zcash transactions, BAT tokens are more than 50$\times$ shorter, 9$\times$ faster to verify, and 7,000$\times$ faster to generate.