S2024:E22
We study blockchain-based provably anonymous payment systems between light clients. Such clients interact with the blockchain through full nodes, who can see what the light clients read and write. The goal of our work is to enable light clients to perform anonymous payments, while maintaining privacy even against the full nodes through which they interact with the blockchain. We formalize the problem in the universal composability model and present a provably secure solution to it. In comparison to existing works, we are the first ones that simultaneously provide strong anonymity guarantees, provable security, and anonymity with respect to the full nodes. Along the way, we make several contributions that may be of independent interest. We define and construct efficient compressible randomness beacons, which produce unpredictable values in regular intervals and allow for storing all published values in a short digest. We define and construct anonymous-coin friendly encryption schemes and we show how they can be used within anonymous payment systems. We define and construct strongly oblivious read-once map, which can be seen as a special data structure that needs to satisfy a stronger notion of obliviousness than what is usually considered. We present a new approach, which is compatible with light clients, for mitigating double- spending attacks in anonymous cryptocurrencies.