4

Imagine the Monero blockchain has been around for decades. It is incredibly massive and the total number of outputs far exceeds the rate of new outputs being created. Can obfuscation acquired by the ring signature technique decline to useless levels? In other words, can the rate of recent new possible outputs being included in forthcoming transactions fall to near zero, because the probability of inclusion falls toward zero? The probability of a new output being obscured by x amount of signatures after time t would always fall as the chain extends.

Someone on reddit https://www.reddit.com/r/Monero/comments/7k4lwx/question_longterm_ring_signatures/ mentioned 25% of signatures on new transactions are selected from the last 5 days of blocks. This seems like a fatal flaw, because blockchain analysis can just ignore that 5 day spike and treat subsequent appearances of an output with a lot of significance. Am I misunderstanding something?

If this is a problem, the solution seems to simply make output selection a probability distribution decaying from more recent to more distant blocks. Old outputs reappearing would be significant, but observers would have much less confidence than if they could ignore most of their obfuscation.

1
  • Does anyone think this might be a concern? Am I mistaken in some way about ring signatures and their benefits?
    – Tsoov
    Commented Dec 18, 2017 at 3:36

2 Answers 2

3

This issue is a known problem. A solution is discussed here: https://github.com/monero-project/monero/issues/1673.
A solution hasn't been created yet but the general plan is, as you suggested, to use some kind of probability distrubtion to selected inputs. In the edit in the first message of the above github issue, olarks mentions he is using data from Bitcoin to get a better idea of how transaction are distributed, because we lack that kind of data for Monero.

edit based on comments: As pointed out in the comment it appears that this has been implemented.
First, it guarentees 1/4 of the fake outputs (min of 1) are selected from a pool of recent outputs using a triangle distribution (code comments says equiprobable distribution, but the code doesn't reflect this).
Second, older outputs are then selected from the whole pool of outputs using a triangle distribution

2
  • Edit by anon: If I'm not mistaken, this is in fact already implemented in the official Monero wallet. What you were told on Reddit seems to be accurate.
    – assylias
    Commented Jan 10, 2018 at 19:00
  • Good point. I made an edit to reflect this. Commented Jan 11, 2018 at 20:53
1

This particular problem does not apply, since half of the fake outputs are selected from the last 1.8 days or so. The rest are taken from the rest of the blockchain. So as the chain grows, the recent outputs selection is not affected, only the "whole blockchain" tail is.

That said, improving the fake output selection algorithm is something that'll have to be done, it's just not clear how to do it best. Current plan is to use a gamma function as per Miller et al, but the parameters and their evolution with time is the sticking point to an actual implementation.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.