{"action":"created","issue":{"url":"https://api.github.com/repos/monero-project/research-lab/issues/7","repository_url":"https://api.github.com/repos/monero-project/research-lab","labels_url":"https://api.github.com/repos/monero-project/research-lab/issues/7/labels{/name}","comments_url":"https://api.github.com/repos/monero-project/research-lab/issues/7/comments","events_url":"https://api.github.com/repos/monero-project/research-lab/issues/7/events","html_url":"https://github.com/monero-project/research-lab/issues/7","id":206280631,"number":7,"title":"[DRAFT] Monero Sub-addresses","user":{"login":"JollyMort","id":20967651,"avatar_url":"https://avatars.githubusercontent.com/u/20967651?v=3","gravatar_id":"","url":"https://api.github.com/users/JollyMort","html_url":"https://github.com/JollyMort","followers_url":"https://api.github.com/users/JollyMort/followers","following_url":"https://api.github.com/users/JollyMort/following{/other_user}","gists_url":"https://api.github.com/users/JollyMort/gists{/gist_id}","starred_url":"https://api.github.com/users/JollyMort/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/JollyMort/subscriptions","organizations_url":"https://api.github.com/users/JollyMort/orgs","repos_url":"https://api.github.com/users/JollyMort/repos","events_url":"https://api.github.com/users/JollyMort/events{/privacy}","received_events_url":"https://api.github.com/users/JollyMort/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":4,"created_at":"2017-02-08T18:16:14Z","updated_at":"2017-02-17T06:19:46Z","closed_at":null,"body":"Ok, so I'm moving this here to keep the https://github.com/monero-project/monero/pull/1345 clutter-free.\r\n\r\n@fluffypony @kenshi84 @knaccc @luigi1111\r\n\r\nTodo:\r\n- choice of method for `n` derivation\r\n- some tweaks: https://paste.fedoraproject.org/551200/77652148/\r\n\r\nChangelog:\r\n\r\n2017-02-07: Initial: http://termbin.com/vdam, http://termbin.com/0a3o, http://termbin.com/n58g - knaccc\r\n2017-02-07: Changed notation and supporting normal addresses as well: https://paste.fedoraproject.org/550729/50082614/ - all :)\r\n2017-02-07: Multi-address support: https://paste.fedoraproject.org/550761/06389148/ - Luigi/JM\r\n2017-02-08: More tweaks and improvement of readability: https://paste.fedoraproject.org/550825/65211341/ - Kenshi\r\n2017-02-08: More tweaks, formatted and copied from https://github.com/monero-project/monero/pull/1345#issuecomment-278228450 - Luigi/JM\r\n**2017-02-09: Apparently this is broken, because knowing C and n, it's trivial to find A**\r\n\r\nInitial discussion: https://paste.fedoraproject.org/551203/78349148/\r\n\r\n## Monero Sub-addresses\r\n\r\n### Brief\r\n\r\nCurrently, each Monero wallet generates one set of keys and one public address which is given out to receive payments. However, a user may want to give out a dedicated address to each sender for dual purpose: to know which payment came from which sender and to avoid privacy loss via off-chain linking of the one address. To accomplish both goals, we propose a way to create multiple addresses which maintains reasonable performance of scanning the blockchain for outputs sent to any of the addresses created, all accessible from within the same wallet.\r\n\r\n### Sub-addresses creation\r\n\r\nA recipient's root wallet address is defined as a pair of public view and spend keys (A,B) = (a\\*G,b\\*G), where a and b are the secret view and spend keys. The recipient creates a sub-address by choosing an arbitrary scalar n and defining a triplet (C,D,n). The choice of scalar n could be deterministic, as proposed below:\r\n \r\n    n = Hc(a || j)\r\n    C = n*A\r\n    m = Hs(a || n)\r\n    M = m*G\r\n    D = B+M,\r\n\r\nwhere\r\n\r\n    j = 1,...,p.\r\n \r\nSuch a sub-address (C,D,n) gets passed to the sender. Note that the sender can't determine its root address (A,B). The sender can, if necessary, transfer to more than one such sub-addresses (C\\_i,D\\_i,n\\_i), i=1,...,w (either to the same recipient or to different recipients) in a single\r\ntransaction.\r\n\r\n### Transaction Construction\r\n\r\nWhen constructing a transaction, the sender generates the transaction key R=r\\*G in a particular\r\nmanner: he rolls a random scalar s, and computes r as\r\n \r\n    r = s * n_1 * n_2 * ... * n_w.\r\n \r\nThen, an output public key P for any standard destination address (A,B) is created as usual:\r\n \r\n    P = Hs(r * A) * G + B\r\n \r\nIn contrast, an output public key P\\_i for the i-th sub-address (C\\_i, D\\_i, n\\_i) is created as:\r\n \r\n    P_i = Hs(s * n_1 * n_2 * ... * n_{i-1} * n_{i+1} * ... * n_w * C_i) * G + D_i\r\n \r\nSince C\\_i = n\\_i * A\\_i (while A\\_i is not known to the sender), the trick is in the following property:\r\n \r\n      s * n_1 * n_2 * ... * n_{i-1} * n_{i+1} * ... * n_w * C_i\r\n    = s * n_1 * n_2 * ... * n_{i-1} * n_{i+1} * ... * n_w * n_i * A_i\r\n    = r * A_i\r\n \r\nTherefore, the output public key P_i is effectively equivalent to:\r\n \r\n    P_i = Hs(r * A_i) * G + B_i + M_i\r\n \r\neven though the sender doesn't know (A\\_i,B\\_i).\r\n\r\n### Scanning for Incoming Transfers\r\n\r\nWhen a recipient checks for incoming transfers, he first performs the standard key derivation\r\nprocedure to check if a given output key P matches to:\r\n \r\n    P' = Hs(a * R) * G + B.\r\n \r\nIf this test fails, he then goes through all previously created sub-addresses (C,D,n) and\r\nchecks if P matches to:\r\n \r\n    Q' = Hs(a * R) * G + B + M.\r\n \r\nSimilar to the aggregated addresses approach [1], this search can be done in a constant time\r\nusing a hash table: instead of computing Q' directly, the recipient computes\r\n \r\n    (B + M)' = P - Hs(a * R) * G, // I think that this is faster, as you pre-compute the EC addition only once, store it in the hash table and now don't have to subtract the B for each output. So, only one EC subtraction per output.\r\n \r\nand looks for (B + M)' in the hash table. If such an (B + M)' is found, the output key P belongs to the recipient and its private key x can be recovered as:\r\n \r\n    x = Hs(a * R) + b + m.\r\n\r\n### Wallet Recovery\r\n\r\nFrom a known set of private keys (a,b), and with assumed number of previously used sub-addresses q>=p, the wallet must first reconstruct all the sub-address information:\r\n\r\n    n = Hc(a || j)\r\n    C = n*A\r\n    m = Hs(a || n)\r\n    M = m*G\r\n    D = B+M,\r\n\r\nwhere\r\n\r\n    j = 1,...,q.\r\n\r\nThen, it performs the full scan, as described in the previous section.\r\n\r\nTo make it stateless, wallet software could limit the range of p, and have q=p=10000, or any other arbitrary number.\r\n\r\n### Notes\r\n\r\nThe root address should never be made public because in that case, anyone could check whether any 2 sub-addresses belong to the same root address.\r\n\r\n### Credits\r\n\r\nknaccc for the initial idea, Luigi for guidance and solution for multiple addresses, and kenshi84 for opening the topic in the first place and final touches. \r\n\r\n### References\r\n \r\n[1] https://bytecoin.org/static/files/docs/aggregate-addresses.pdf"},"comment":{"url":"https://api.github.com/repos/monero-project/research-lab/issues/comments/280564244","html_url":"https://github.com/monero-project/research-lab/issues/7#issuecomment-280564244","issue_url":"https://api.github.com/repos/monero-project/research-lab/issues/7","id":280564244,"user":{"login":"RandomRun","id":22761515,"avatar_url":"https://avatars.githubusercontent.com/u/22761515?v=3","gravatar_id":"","url":"https://api.github.com/users/RandomRun","html_url":"https://github.com/RandomRun","followers_url":"https://api.github.com/users/RandomRun/followers","following_url":"https://api.github.com/users/RandomRun/following{/other_user}","gists_url":"https://api.github.com/users/RandomRun/gists{/gist_id}","starred_url":"https://api.github.com/users/RandomRun/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/RandomRun/subscriptions","organizations_url":"https://api.github.com/users/RandomRun/orgs","repos_url":"https://api.github.com/users/RandomRun/repos","events_url":"https://api.github.com/users/RandomRun/events{/privacy}","received_events_url":"https://api.github.com/users/RandomRun/received_events","type":"User","site_admin":false},"created_at":"2017-02-17T06:19:46Z","updated_at":"2017-02-17T06:19:46Z","body":"@knaccc: Thanks for finding out the that the view keys do leak the spend key.\r\n\r\nOne way of perhaps fixing that is to go back to the \"original approach\" we had, which is: fix `(a, b)`, and for each different sender, generate a random `s` value. Pass `(sA, sB, sG)` to them so that they can pick their own  random `r`, and compute `R = r(sG)`, and `P = H(r(sA))G + sB`. Sender sends out `R` and `P`.\r\n\r\nAlice checks: `P' = H(aR)G + sB = H(a(rsG))G + sB = H(r(saG))G + sB = H(r(sA))G + sB = P`. The corresponding view key is `(a, sB)`, and here I see no leak of the private spend key `sb`.\r\n_______________________________\r\n\r\n> The view key for each subaddress would be `(ab, cG)`\r\n\r\nIf your `b` varies, then `a` could be exposed, but I guess your approach is good because even if that happens, since there is no way to deduce `c`, right? I am just not clear how Bob computes his `R` here. It seems that it would have to be `R = r(bG)`, but he is not being given `bG`."}}
{"actor":{"display_login":"RandomRun"}}