That term is misleading and implies actual RAM-type memory is needed, which is untrue. Monero scales quite well using a database on SSD up to transaction rates far in excess of anything Bitcoin can or will realistically handle now or any time soon (certainly hundreds and possibly thousands of tx/sec).
Likewise the total data that needs to be stored grows slowly at realistic tx rates, roughly 80 GB/year at 10 tx/sec. That's similar to the rate of growth of the bitcoin blockchain (unpruned) and well within the hardware capabilities of both existing cheap SSDs and even more so the visible trajectory for future cheap SSDs.
The comment to which I replied (not by you) claimed that the anonymity set is all shielded transactions.
It is, in the same sense that the first order anonymity set of Monero transactions is all outputs included in the ring signature which can't be proven implausible (e.g. using the methods in Section 3 of the paper). However, Section 4 of the paper points out that a non-uniform distribution means this is reduced, in practice, to a smaller effective degree. The same method can be used with Zcash to estimate a smaller effective degree since many previous shielded transactions are probabilistically unlikely.
This is certainly not 'deanonymization' or 'tracing' or any such thing, but it isn't that in the Monero case either.
Yes you are likely correct that "most recent" being the "most likely" is not accurate. However, there is a distribution and it has a peak. It is certainly not flat, so it is incorrect to say that the entire set constitutes an "effective anonymity set" while at the same time claiming that Monero's ring signatures only have an "effective mixin size" that is smaller than the actual size due to the same non-uniform distribution.
> In Monero, the adversary can refine their guess of the distribution based on the inputs that are actually mixed in, and that is what creates the privacy weakness.
That is not what is claimed in Section 4 of the paper. Section 4 merely indicates that of potential outputs, the time distribution introduces a bias toward the most recent (actually in Monero this might be inaccurate in some cases too: very, very recent might be less likely than merely very recent; the paper does not examine this). In Zerocash the same time distribution bias exists, though across a larger set of potential coins (or notes or whatever it is you call it).
However, very old members of that set are essentially irrelevant as their probability in the distribution is almost certainly extremely low (this is the same reason that more older outputs in Monero are essentially irrelevant).
It is not. The problems were previously identified and documented by Monero developers, and the paper acknowledges this.
The paper attaches specific historical numbers to those problems, which is good, though one can still quibble about how the numbers are aggregated and presented.
> The point they are trying to make is that the anonymity set between shielded addresses is that of all transactions in the anonymous set.
This way of stating is somewhat questionable in light of the claims in the second half of the paper.
What is shown in the second half of the paper is that all possible sources are not equally likely and this most probably applies to Zcash (and every other coin) as well. In the Figure 1 illustration of Zcash, it is most likely that the rightmost (most recent) arc is the correct one. Of course this can't be stated with certainty in either coin.
Another way of interpreting the trend shown in Figure 8 is that Zcash gains little (though of course it still gains something) from including all transactions in the anonymity set (arbitrarily far to the right) because once one departs from focusing predominantly on the more recent transactions, the effective anonymity set does not grow much.
> Instead, it looks like clients weren't even doing basic checks:
>> We find that among Monero transaction inputs with one or more mixins, 62% of these are deducible, i.e. they can be incontrovertibly linked to the prior TXO they spend.
There are no basic checks that can solve that issue. It was fixed in a different way.
> even if Monero fixes everything in this upcoming release,
Most of the issues in the paper were already addressed in the past, and the paper says this. The remaining issue is the time bias which the paper states has already been improved, but can be improved further.
The technique in the second half of the paper is not able to trace any transactions at all, as I explained in more detail in another reply. It identifies a partial weakness in the ring signatures but it is not capable of breaking them.
It was a deliberate design decision as the issue was mitigated in a different manner starting in early 2016 (and introducing that check wouldn't be very effective anyway for other reasons).
The results of the mitigation are shown in the paper as Figure 5. The success of the techniques in the paper decline rapidly over the course of 2016 and would effectively reach zero if the dataset were extended (this is noted in the text when it states that RingCT transactions are immune, although even without RingCT it would still effectively reach zero)
The section 3 vulnerability traces (aka "de-anonymizes") precisely no transactions at all. It indicates that the probabilities across potential outputs sources are biased, but does not offer any method at all to identify any actual source.
The estimate of the bias given in the paper for the current default and typical usage is that the most recent potential source has a probability of 45% instead of the ideal 20%. In fact this likely applies to 100% of current transactions, not 80%.
This is a known issue, and not ideal, and the quantitative results in the paper are helpful, but the paper does not show what you claim it shows.