b-g-goodell
commented
6 years ago There is no perfect answer, afaict, because we haven't assessed the complexity for determining a "true path" of signers in a tree of ring signatures/implications, but I'm not sure if that's necessary or possible.
I suspect that exposing a path of transactions on the Monero blockchain is a problem with at least exponential complexity (2^2^k), in the absence of an EABE attack. We don't want the ring sizes to change over time with, say, difficulty, because then someone will be better able to use ring sizes and dynamic fees to pinpoint the IRL time of the transaction, although having a slow ring size updating each month or two-week period or something like that (slower than difficulty adjustments) I think would also be acceptable (maybe set a different fixed ring size for each HF for a few years or something like that).
_Below, I'm going to justify selecting a fixed ring size between base_ring_size = 5 and base_ringsize = 200, and either just leaving it alone forever or changing it occasionally.
Assumptions: Assume the probability of success of the attacker decays exponentially to zero with parameter L > 0 as ring size increases (I'm being super vague about how the attack is going down on purpose here, we will use L exp(-x/L) as the density function), and assume the "cost" (again, vague and abstract) of securing the network by boosting ring size grows linearly with ring size, say mx+b. Hence the average "cost" blown/wasted by the network in the case that a ring size x will be L exp(-x/L) * (mx+b). The units here: L has units "number of ring members", m has units "1/(number of ring members)", and b has units "cost points" (which I left abstract). We can assume m != 0 (this corresponds to: cost of finding true signer is constant regardless of ring size) and L != 0 by assumption. We can probably assume b = 0 (zero cost to determine the true signer of a regular signature, the pubkey comes along).
Minimizing: Then to minimize the attacker's success P = L exp(-x/L) subject to the constraint that we still keep costs C = mx+b = mx reasonable we merely must minimize the function PC. This point occurs when L (-1/L) exp(-x/L) mx + L exp(-x/L) m = 0. The factor L exp(-x/L) appears in both terms, so it cancel out (assuming L!=0) and we end up with (-1/L) * mx + m = 0 or x = L.
Note that this kicks the can down the road: we answer the question "how do we minimize the average cost blown by the network in the event of a successful attack" with an answer "estimate the inherent rate of decay of the probability of success and use that." Unfortunately, estimating this ring size decay rate requires a rigorous definition of the various sorts of attack to reveal the true signer, and estimating the complexity of doing so, etc etc.
So, we have reduced the problem to a specific answer, but in order to find an actual numerical result, we need to do a lot more work. But we have reduced the problem and we can ask some questions. Such as: what if L = ln(k) for some security parameter k? This gives us an indication of how small ring sizes could be to optimize this process: if k = 10^3, ln(k) = 6.9-ish, so a ring size of 7 "should" be optimal in this scenario. Even if k = 10^80 (about the number of particles in the known universe) we would end up with a ring size around 185, and something like k=2^256 has a ring size of 177.
That is to say: if costs are linear and ring sizes can be chosen to be logarithmic in a security parameter and if probability of attack success is exponentially decaying as the ring size gets larger, the range of ring sizes from 5 to 200 all seem reasonable to me. Without more information, more rigorous models, more justification for each of these choices... this is the best we can go for, I think. If we get crazy? Say we want k = biggest prime yet discovered, which is approximately 2^( 7 * 10^6)? With logarithmic ring sizes, we still need a ring size of 700,000. With RTRS ring signatures, this signature would be only 4.5 times as large as a ring signature with 20 signers. Really not bad at all, although verification time would be more than prohibitive.
Caveats/etc:
-
I chose logarithmic ring sizes purposely to demonstrate a point. We probably want to select ring size sublinearly in a security parameter: logarithmic ring sizes are of course only going to present small numbers from 5 to 200, because a^200 is a huge freaking number for any a > 2. But another choice is like Sqrt(k). In this case, for something absurd like k=10^80 will, unfortunately, also produce an absurd ring size (10^40), which, even with RTRS signatures, is pretty cumbersome in size (not to mention verification time!)
-
Not only have I selected logarithmic ring sizes rather arbitrarily, I also have not justified any particular choice of security parameter k. I have merely explored a space of possibilities between roughly 10^3 and 10^80. This may seem convincing, but keep in mind: since we don't have a good model for how the attack unrolls, maybe we should look at even larger numbers like 10^(10^(10^80))).
-
I suspect that probability of success to track a path of transactions through the implication tree is doubly exponential, exp(-L exp(S x)) but parallelizable. If this is true, then even moderate ring sizes of 5-10 is probably sufficient to balance security and cost.
Conclusions: For these reasons, I would support a fixed ring size of something like 8 or 16 for now, and if we have RTRS ring signatures, we can double it a few times every few hard forks... or every few decades... and we will have sufficiently protected our users from casual blockchain analysis. This may not be sufficient to stop large-scale state actors, especially in light of the EABE attack, but 16 year old hackers living with their parents in Cape Town some place will be very unlikely to be capable of exposing the blockchain using a nonogram-style attack. Fee structures probably also need to be changed in order to accommodate fixed ring sizes. Choosing a minimum ring size of 8 or 16 or 32 will "probably" be sufficient for several years, and anything between 5 and 200 can cover a very large region of the security parameter space.
Homework problem: Whether we use RTRS ringCT or MLSAG ringCT for ring sizes in this range is completely different question, which might needs its own issue: RTRS RingCT roughly has twice the verification time for a similarly sized MLSAG ringCT, but takes up a logarithmic amount of space. For which ring sizes between 5 and 200 is it worthwhile to use RTRS RingCT instead of MLSAG?
iamsmooth
Gingeropolous
stoffu
afighttilldeath
moneromooo-monero
SamsungGalaxyPlayer
This is a spinoff of #3035 , a proposal to increase ringsize and possibly remove the option of using variable ringsizes.
I feel that if we fix the ringsize as proposed by multiple people, ringsize will become our blocksize debate, and should therefore be algorithmified.
In an ideal situation, a transaction would be made with a ringsize of the entire chain.
In the real world, we are discussing moving from a ringsize of 5 to a ringsize greater than 8 but less than 16. From my understanding of things, we are not going to use a ringsize of the entire chain due to the cost of validation and size. This is logical.
However, computers will get faster. In another year or two, we may once again have this debate of "well, now it only takes 40 usec to verify a transaction of ringsize 16 on a raspberry pi Cream Filling edition, so we should increase it to 32"
What if, instead, the protocol assesses the state of computational power of the network and adjusts the ringsize accordingly?
Yes yes, I once again am proposing to use the network difficulty as a source of information about the real world.
Granted, I don't know which combination of variables it would be based on (I imagine a combination of blocksize and difficulty - difficulty would act as a more or less raw measure of computational power of the meatworld, but blocksize would possibly act as a denominator, because -using the assumption that increased chain activity == higher value (as used in the transaction fee adjustment) - the more valuable the monero network is, the more people are mining on it. So possibly something as "simple" as the difficulty / blocksize plotted over time, and then you evaluate the slope, and certain slope characteristics would trigger certain behavior)...
but the protocol could create a yearly adjustment that adds 0 or a positive number to the current ringsize (or we can think about allowing it to decrease, say if world war 3 knocks out 90% of the worlds computers and the network is struggling to run on smart toasters). Basically, the protocol can analyze the last years worth of block data and assess that conditions favor an increase in the ringsize, the current ringsize matches the system as assessed by the analysis, or that a decrease in ringsize is needed.