{"action":"created","issue":{"url":"https://api.github.com/repos/monero-project/monero/issues/1673","repository_url":"https://api.github.com/repos/monero-project/monero","labels_url":"https://api.github.com/repos/monero-project/monero/issues/1673/labels{/name}","comments_url":"https://api.github.com/repos/monero-project/monero/issues/1673/comments","events_url":"https://api.github.com/repos/monero-project/monero/issues/1673/events","html_url":"https://github.com/monero-project/monero/issues/1673","id":205351948,"number":1673,"title":"[Discussion] Raising the mandatory ringsize in the v5 hardfork, September 2017","user":{"login":"olarks","id":22985323,"avatar_url":"https://avatars.githubusercontent.com/u/22985323?v=3","gravatar_id":"","url":"https://api.github.com/users/olarks","html_url":"https://github.com/olarks","followers_url":"https://api.github.com/users/olarks/followers","following_url":"https://api.github.com/users/olarks/following{/other_user}","gists_url":"https://api.github.com/users/olarks/gists{/gist_id}","starred_url":"https://api.github.com/users/olarks/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/olarks/subscriptions","organizations_url":"https://api.github.com/users/olarks/orgs","repos_url":"https://api.github.com/users/olarks/repos","events_url":"https://api.github.com/users/olarks/events{/privacy}","received_events_url":"https://api.github.com/users/olarks/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":35,"created_at":"2017-02-04T14:51:01Z","updated_at":"2017-02-08T01:27:25Z","closed_at":null,"body":"You may want to grab a drink for this one...\r\n\r\nAs we all know there will be a hardfork in September 2017 that will raise the mandatory ringsize to 4\r\nbased on the recommendations of [MRL-4](https://lab.getmonero.org/pubs/MRL-0004.pdf), but this paper was published before RingCT was found to have extraordinary savings in transaction size for transactions with larger ringsizes.\r\n\r\nWe have 7 months to explore alternatives and I would like to discuss some viable options\r\nfor raising the mandatory ringsize for the v5 hardfork, so that we do not need to again change it in a\r\nfuture hardfork unless certain circumstances arise.\r\n\r\nIt is important to note that raising the ringsize of a transaction will increase the time it takes to verify\r\ntransactions for nodes, but as far as I am aware this scales linearly(?). So this can be maintained to a reasonable degree and if we assume processor speeds continue to improve, then this problem does not greatly impact the scalability of the Monero network in comparison to the relative gains of privacy for its users. Optimizations in ring signatures and rangeproofs will certainly ease these concerns.\r\n\r\nThere are two options I would like to explore:\r\n\r\n1) Simply raising the mandatory ringsize to a value greater than 4 that can take full advantage of RingCT's optimizations in transaction size without sacrificing very much performance. Ring size 8 could for example easily be used instead of 4 and still have very good performance for example.\r\n\r\nand the more interesting option\r\n\r\n2) Raising the mandatory ringsize and have it be static so no other ringsizes are accepted in the Monero network. Static ringsizes 9, 12, or 15 would be good options and I will explain a bit more about why those ringsizes specifically are special later below.\r\n\r\nThe first option would be simple to implement and the optimizations of RingCT would be immediately realized with very little added cost. However the second option will bolster privacy on the Monero network by a much higher degree. By enforcing only one valid ringsize for transactions this removes any confusion and complexity for new users who do not understand why you would want to increase the ringsize of a transaction if transactions in Monero are all already private. Since the protocol would be enforcing a static ringsize, then all transactions would be homogenous and would circumvent analysis of transactions by adversaries who may know that for example exchange x uses ringsize y for all their outgoing transactions, or that there is a user that regularly specifies atypical ringsizes like 41 for all their transactions. This removes a human element to transactions that could save people from unintentionally reducing their privacy as well as other users' privacy.\r\n\r\nIn the future, businesses and services could be 'assigned' very specific ringsizes that would stick out on the blockchain for passive observers to more easily identify their outputs in other ring signatures, this is only hypothetical and one of many possible scenarios where irregular ringsizes could reduce privacy in the Monero network.\r\n\r\nI believe that this is a very valuable and natural addition to Monero since the protocol already makes decisions to protect its users like dynamic fees and randomly choosing their ring partners according to specific parameters. A static ringsize would just further streamline the user experience while defending against many attacks via passive analysis of ring signatures.\r\n\r\nIn addition to the arguments I made for a static ringsize I will also propose a new output selection algorithm to assist a static ringsize. Going back to why I had specifically mentioned static ringsizes 9, 12, and 15 is because if a third of ring partners are chosen randomly from the past five days and the remaining two thirds of ring partners are chosen at random then a few narrow edge cases that would threaten privacy would be completely eliminated or at the very least much less impactful than only having a default ringsize 4.\r\n\r\nI will demonstrate these claims with some hypothetical scenarios using a ringsize of 12 as an example.\r\n\r\nScenario 1: Alice sends Bob a transaction with an output that is two days old. In Alice's ring signature are four inputs from the past five days chosen by our output selection algorithm(plus Alice's real spend) and eight additional inputs chosen at random.\r\n\r\nAlice has complete financial privacy as her real output is masked with the other 12 ring partners without any major inconsistencies in our output selection algorithm. Since there is a chance at least one of those eight outputs chosen at random could have been from the last five days the additional recent output in the ring signature is not entirely suspicious. This will still be taken into account by passive observers since a lot of people will be spending money soon after it has been received. Possible scenarios where this would definitely question the legitimacy of randomly chosen outputs and directly threaten privacy is discussed in more depth later.\r\n\r\nScenario 2: Same as Scenario 1 but instead Alice has an output that is one month old. Our output selection algorithm will again choose four random outputs from the past five days and eight outputs at random.\r\n\r\nNow the problem is Alice has an output that is older than the outputs that would be specified from the last five days and if the other eight random outputs do not coincide with the last five days then only four recent outputs will exist in the ring signature. This is a direct indication that none of those outputs is the real spent output because only four recent outputs would be chosen from our algorithm anyway, hence being fake. Luckily the other eight random outputs still mask Alice's real output so this scenario does not greatly threaten her privacy as the transaction would effectively still have the strength of ringsize 8 down from 12.\r\n\r\nScenario 2 is less likely to occur if a larger timespan is chosen for recent outputs in our algorithm so the randomly chosen outputs have a higher chance to be in that timespan, but since money is typically spent within a short time after being received this will directly weaken the obfuscation of our recent outputs selected for a ring signature.\r\n\r\nThe output inconsistencies in Scenario 2 cannot be solved very well without adding additional formality to the output selection algorithm making it easier to single out specific outputs that are not consistent with our output selection rules like in Scenario 2. With a ringsize of 12 at the very least an effective strength of ringsize 8 would still exist for a transaction.\r\n\r\nHowever if an observer were able to find inconsistencies within a transaction with multiple inputs, all or at least some, containing more than four outputs younger than five days old it is incredibly unlikely the other eight random outputs for each input's ring signature would contain very recent outputs. This would question the legitimacy of the eight other outputs older than five days giving the transaction a hypothetical strength equal to the number of outputs in the ring signature younger than five days old or at the absolute bare minimum the strength of ringsize 4.\r\n\r\nThese scenarios will need to be accepted to exist and thankfully do not completely destroy the privacy of a transaction with poorly chosen ring partners by the output selection algorithm.\r\n\r\nIncreasing the static ringsize would decrease the likelihood of these contradictions in ring signatures, but it is a tradeoff with transaction sizes. Ideally most transactions would be able to take full advantage of ringsize 12, but the privacy of ringsizes 4 and 8 can still be obtained in worst case scenarios.\r\n\r\nI personally prefer ringsize 12 because at the bare minimum when the output selection is not in your favour then at the very least ringsize 4 can still be obtained, which is the original ringsize scheduled for v5 hardfork. Ultimately any ringsize greater than 9 that is a multiple of 3 can be used and if we take into account optimizations of ring signatures and rangeproofs then even larger ringsizes, factors of 3s, could be considered.\r\n\r\nThe privacy that would be gained with a static ringsize 12 far outweighs any short term scalability issues that may arise in my opinion and would be a boon to the privacy and security of the Monero network while having good safe guards for maintaining a minimum privacy level of ringsize 4.\r\n\r\nI hope valuable discussions can be made from this post and further optimizations that can further the security of the network can be discovered.\r\n\r\nThanks for taking the time to read my writeup. Any input is greatly appreciated."},"comment":{"url":"https://api.github.com/repos/monero-project/monero/issues/comments/278200665","html_url":"https://github.com/monero-project/monero/issues/1673#issuecomment-278200665","issue_url":"https://api.github.com/repos/monero-project/monero/issues/1673","id":278200665,"user":{"login":"iamsmooth","id":8495206,"avatar_url":"https://avatars.githubusercontent.com/u/8495206?v=3","gravatar_id":"","url":"https://api.github.com/users/iamsmooth","html_url":"https://github.com/iamsmooth","followers_url":"https://api.github.com/users/iamsmooth/followers","following_url":"https://api.github.com/users/iamsmooth/following{/other_user}","gists_url":"https://api.github.com/users/iamsmooth/gists{/gist_id}","starred_url":"https://api.github.com/users/iamsmooth/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/iamsmooth/subscriptions","organizations_url":"https://api.github.com/users/iamsmooth/orgs","repos_url":"https://api.github.com/users/iamsmooth/repos","events_url":"https://api.github.com/users/iamsmooth/events{/privacy}","received_events_url":"https://api.github.com/users/iamsmooth/received_events","type":"User","site_admin":false},"created_at":"2017-02-08T01:27:25Z","updated_at":"2017-02-08T01:27:25Z","body":"@ RandomRun\r\n\r\nMy suggestion (quoted by @Gingeropolous) was to use the distribution of ages of outputs spent by inputs of recent transactions as a model distribution for choosing random fake outputs. This does not suggest using outputs similar in time to your own real output at all. \r\n\r\nWhat it does do is include a distribution of unknown real outputs (each candidate model transaction input necessarily includes a real output, as well as several fake ones). If everyone uses this algorithm, and there is no apparent reason why they shouldn't, then everyone's fake outputs will be chosen with ages from a distribution that matches the distribution of ages of real outputs, even though there is no other way to direct measure the distribution of ages of real outputs. That is the 'statistical magic' part.\r\n\r\nThe vulnerability I see in this is someone spamming the network with bogus transactions using a deliberately poor distribution of fake outputs to pollute the distribution used by the above method. As you say, this really needs to be addressed by maximizing legitimate usage (and I agree in principle with your comments on that point). Indeed someone performing this sort of spam/Sybil attack is already compromising privacy to a large degree, though in neither case is the attack fully effective, it ismore of a degradation.\r\n"}}
{"actor":{"display_login":"iamsmooth"}}