On Sustainable Ring-based Anonymous Systems

Sherman S. M. Chow, Christoph Egger, Russell W. F. Lai, Viktoria Ronge, Ivy K. Y. Woo

Abstract: Anonymous systems (e.g. anonymous cryptocurrencies and updatable anonymous credentials) often follow a construction template where an account can only perform a single anonymous action, which in turn potentially spawns new (and still single-use) accounts (e.g. UTXO with a balance to spend or session with a score to claim). Due to the anonymous nature of the action, no party can be sure which account has taken part in an action and, therefore, must maintain an ever-growing list of potentially unused accounts to ensure that the system keeps running correctly. Consequently, anonymous systems constructed based on this common template are seemingly not sustainable. In this work, we study the sustainability of ring-based anonymous systems, where a user performing an anonymous action is hidden within a set of decoy users, traditionally called a ``ring''. On the positive side, we propose a general technique for ring-based anonymous systems to achieve sustainability. Along the way, we define a general model of decentralised anonymous systems (DAS) for arbitrary anonymous actions, and provide a generic construction which provably achieves sustainability. As a special case, we obtain the first construction of anonymous cryptocurrencies achieving sustainability without compromising availability. We also demonstrate the generality of our model by constructing sustainable decentralised anonymous social networks. On the negative side, we show empirically that Monero, one of the most popular anonymous cryptocurrencies, is unlikely to be sustainable without altering its current ring sampling strategy. The main subroutine is a sub-quadratic-time algorithm for detecting used accounts in a ring-based anonymous system.

References

  1. [ACR21] Thomas Attema, Ronald Cramer, and Matthieu Rambaud. “Compressed Σ-Protocols for Bilinear Group Arithmetic Circuits and Application to Logarithmic Transparent Threshold Signatures”. In: ASIACRYPT 2021, Part IV. Vol. 13093. LNCS. Springer, Heidelberg, Dec. 2021, pp. 526–556. doi: 10.1007/978-3-030-92068-5_18.
  2. [Bün+20] Benedikt Bünz et al. “Zether: Towards Privacy in a Smart Contract World”. In: FC 2020. Vol. 12059. LNCS. Springer, Heidelberg, Feb. 2020, pp. 423–443. doi: 10.1007/978-3-030-51280-4_23.
  3. [DM58] A. L. Dulmage and N. S. Mendelsohn. “Coverings of Bipartite Graphs”. In: Canadian Journal of Mathematics 10 (1958), 517–534. doi: 10.4153/CJM-1958-052-0.
  4. [Egg+22] Christoph Egger et al. “On Defeating Graph Analysis of Anonymous Transactions”. In: PoPETs 2022.3 (July 2022), pp. 538–557. doi: 10.56553/popets-2022-0085.
  5. [Fau+19] Prastudy Fauzi et al. “Quisquis: A New Design for Anonymous Cryptocurrencies”. In: ASIACRYPT 2019, Part I. Vol. 11921. LNCS. Springer, Heidelberg, Dec. 2019, pp. 649–678. doi: 10.1007/978-3-030-34578-5_23.
  6. [Lai+19] Russell W. F. Lai et al. “Omniring: Scaling Private Payments Without Trusted Setup”. In: ACM CCS 2019. ACM Press, Nov. 2019, pp. 31–48. doi: 10.1145/3319535.3345655. 22
  7. [LMR19] Russell W. F. Lai, Giulio Malavolta, and Viktoria Ronge. “Succinct Arguments for Bilinear Group Arithmetic: Practical Structure-Preserving Cryptography”. In: ACM CCS 2019. ACM Press, Nov. 2019, pp. 2057–2074. doi: 10.1145/3319535.3354262.
  8. [MC23] Jack P. K. Ma and Sherman S. M. Chow. “SMART Credentials in the Multi-queue of Slackness”. In: EuroS&P. IEEE, 2023, pp. 896-912, doi: 10.1109/EuroSP57164.2023.00057.
  9. [NM16] Shen Noether and Adam Mackenzie. “Ring Confidential Transactions”. In: Ledger 1 (Dec. 2016), pp. 1–18. doi: 10.5195/ledger.2016.34.
  10. [Ped92] Torben P. Pedersen. “Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing”. In: CRYPTO’91. Vol. 576. LNCS. Springer, Heidelberg, Aug. 1992, pp. 129–140. doi: 10.1007/3-540-46766-1_9.
  11. [RMM22] Michael Rosenberg, Mary Maller, and Ian Miers. “SNARKBlock: Federated Anonymous Blocklisting from Hidden Common Input Aggregate Proofs”. In: S&P 2022. IEEE, 2022, pp. 948–965. doi: 10.1109/SP46214.2022.9833656.
  12. [Ron+21] Viktoria Ronge et al. “Foundations of Ring Sampling”. In: PoPETs 2021.3 (July 2021), pp. 265–288. doi: 10.2478/popets-2021-0047.
  13. [Tas12] Tamir Tassa. “Finding all maximally-matchable edges in a bipartite graph”. In: Theoretical Computer Science 423 (2012), pp. 50–58. doi: 10.1016/j.tcs.2011.12.071.
  14. [Vad01] Salil P Vadhan. “The complexity of counting in sparse, regular, and planar graphs”. In: SIAM Journal on Computing 31.2 (2001), pp. 398–427.
  15. [Vij21] Saravanan Vijayakumaran. Analysis of CryptoNote Transaction Graphs using the DulmageMendelsohn Decomposition. Cryptology ePrint Archive, Report 2021/760. 2021.
  16. [Wij+18] Dimaz Ankaa Wijaya et al. “Monero ring attack: Recreating zero mixin transaction effect”. In: TrustCom/BigDataSE 2018. IEEE. 2018, pp. 1196–1201.
  17. [Yu+19] Zuoxia Yu et al. “New Empirical Traceability Analysis of CryptoNote-Style Blockchains”. In: FC 2019. Vol. 11598. LNCS. Springer, Heidelberg, Feb. 2019, pp. 133–149. doi: 10.1007/978-3-030-32101-7_9.