MoneroResearch.info

WIKINDX Resources

Chow, S. S., Egger, C., Lai, R. W. F., Ronge, V., & Woo, I. K. Y. (2023). On sustainable ring-based anonymous systems. Cryptology ePrint Archive, 
Added by: Jack (2023-06-06 21:05)   Last edited by: Jack (2023-06-06 21:13)
Resource type: Journal Article
BibTeX citation key: Chow2023
View all bibliographic details
 Categories: Monero-focused
Creators: Chow, Egger, Lai, Ronge, Woo
Collection: Cryptology ePrint Archive		 Views: 412/1797
Attachments   sustainability.pdf [40/443] URLs   https://eprint.iacr.org/2023/743.pdf
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 anony- mous 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
  
Notes
Rucknium's Comments from MRL May 31, 2023.

https://github.com/monero-project/meta/issues/844

17:48:09 <Rucknium[m]> My comments:

17:48:20 <Rucknium[m]> 1) AFAIK, this is the first paper that discusses the possibility of "pruning of spent
outputs" in my list of Monero open research questions (MRL issue #94).

17:48:31 <Rucknium[m]> 2) Their "garbage collector" of spent outputs would require, in practice, a
partitioning decoy selection algorithm (DSA). That means each ring would be "one big bin". Each big would be a
contiguous set of outputs. The bins would be disjoint sets.

17:48:45 <Rucknium[m]> 3) The garbage collection procedure with partitioning DSA is very simple: You garbage
collect the whole bin if the number of transaction inputs that reference the bin equal the size of the bin.

17:48:57 <Rucknium[m]> 4) There is an alternative garbage collector for a mimicking decoy selection algorithm
(or another DSA that is not partitioning), which is what Monero has to tried to have. It's basically to run
the Dulmage-Mendelsohn Decomposition to see if any sets of outputs can be proven to be spent.

17:49:08 <Rucknium[m]> 5) This alternative does not collect much garbage at all (and maybe none) at Monero's
ring size and transaction volume. That's why they say Monero is "unsustainable". Monero can not really prune
outputs in its current form.

17:49:22 <Rucknium[m]> 6) My opinion: The partitioning DSA + Garbage collector is vulnerable to malicious
parties simply producing a single output in each bin and never spending them. Then the garbage can never be
collected and pruning does not happen after all. What do you think?

17:49:34 <Rucknium[m]> 7) Something that this paper made me realize is that if Monero has a partitioning DSA
then it would need to be required at the protocol level since otherwise nonstandard DSA could be pulling
decoys from "bags of black marbles" that are already provably spent.

17:49:45 <Rucknium[m]> 8) Disadvantages of a partitioning DSA are discussed here:
https://libera.monerologs.net/monero-research-lab/20220829#c142533

 


Added by: Jack  Last edited by: Jack
WIKINDX 6.5.0 | Total resources: 210 | Username: -- | Bibliography: WIKINDX Master Bibliography | Style: American Psychological Association (APA)