-
knaccc
this is my attempt at a diagram
imgur.com/a/FX8KN1j cc: sgp_
-
knaccc
;/
-
knaccc
(that was accidental typing, not a smilie)
-
sgp_
knaccc: how do you know which set of subaddresses to select from? Ideally the exchange would use one subaddress per user
-
knaccc
sgp_ the hash is just a simple hash of the subaddress. so alongside every output in every transaction (involving exchanges or otherwise), the hash that appears corresponds to whatever subaddress the recipient asked for funds to be sent to
-
knaccc
and all tx senders, including exchanges, must use the correct hash, or wallets will not notice the transaction
-
knaccc
because wallets can now directly look for hashes matching wallet subaddresses, instead of doing heavy-ECDH scanning
-
knaccc
cc moneromooo - i think what I just typed addresses the question you just posted to github? please let me know if it doesn't answer your question and i've misunderstood
-
gingeropolous
<knaccc> (that was accidental typing, not a smilie) <---- its a funny emoticon to throw after posting a link for this :) im getting a good chuckle.
-
knaccc
:)
-
moneromooo
It does, but it presupposes honest adversaries.
-
moneromooo
If an exchange wants to do this, you'll get lots of people asking for patches to recognize those outputs, since they were sent to the wallet.
-
moneromooo
Not sure it'd get done since an exhcange would not gain that much from it though.
-
moneromooo
The first paragraph (the question) was not addressed though, just the second one.
-
gingeropolous
sorry knaccc , that figure didn't do it for me :( but EABE makes my head hurt. i need to go prime myself on it again
-
moneromooo
Assuming I understand your technique, I think that it's mostly pointless if the number of exchanges is high enough compared to the ring size.
-
moneromooo
If low enough, I see it helping, but whether it overrides the flaws I dunno.
-
knaccc
moneromooo ah sorry, i updated the github comment to address the first part
-
knaccc
the scheme does not rely on hoping to get outputs from any particular exchange or from any exchange at all
-
knaccc
all that matters is that it's not only A's outputs that appear in all 3 branches, but other users' outputs too
-
moneromooo
That will only be the case if those come from the exchange, no ?
-
knaccc
i don't think i understand your question. i hope its clear that these hashes appear in all txs, not just txs sent by exchanges
-
knaccc
and this scheme also solves the equivalent of EABE traceability issues in ABC scenarios etc
-
knaccc
so exchanges aren't even necessary to think specially about
-
moneromooo
Well, F is another exchange, and Carol and Dave are F users.
-
moneromooo
Alice sends to Bob, and looks for grouped outputs. She finds lots of stuff F sent Carol and Dave. She uses those in her ring.
-
moneromooo
When E receives Bob's monero, it finds lots of A smelling outputs, but also some of C and D.
-
moneromooo
And... I can see why it doesn't matter actually.
-
gingeropolous
its like trying to bin based on the emergent characteristics of a particular output type
-
gingeropolous
mebbe
-
knaccc
yes all that matters is that when A's outputs pop up in all 3 branches, outputs owned by other users pop up per-user in all 3 branches
-
moneromooo
So... interestingly, if A withdraws from E to a different subaddress every time, it makes Bob stand out more, does it not.
-
knaccc
that's correct
-
moneromooo
Since Carol and Dave will not use A's outputs.
-
knaccc
yes, you've totally got it
-
moneromooo
That's counter intuitive since people will generate addresses to be more private.
-
knaccc
it's good that people use a subaddress per-sender
-
knaccc
it's a problem if no one receives more than one output to any particular subaddress
-
moneromooo
But if they keep the same subaddress for multiple withdraws, then if someone learns about one, they can track all others. That's kinda catch 22.
-
sgp_
We are currently pushing for one-time use subaddresses for manual payments though, which means this is a breaking UX recommendation
-
knaccc
that's correct, there is no forward secrecy
-
sgp_
Also I'm worried about change outputs to the same subaddress being used to clearly identify timing
-
knaccc
can you elaborate on the that threat sgp_? what could be inferred
-
moneromooo
I really don't like the fact that if a group puts a donation address up, everyone knows whenever they receive somehting.
-
sgp_
Someone uses their subaddress to buy goods from a malicious seller, say for something illegal. Then the same person buys coffee from a cooperating store
-
knaccc
moneromooo neither do i. that is a problem.
-
sgp_
Would those transactions not be linked based on the change output to the same subaddress?
-
moneromooo
Oh, that is a good point. Change goes to 0 now.
-
sgp_
Afaict, change would connect all transactions to a single subaddress identity
-
knaccc
sgp_ you make an interesting point. i think hashes on change outputs will have to be set randomly
-
sgp_
At that point the benefit is decreased though from more blocks of subaddresses to choose the decoys from though, no?
-
knaccc
yeah that's a very good point
-
moneromooo
It makes churn pointless too. Which might be good :D
-
moneromooo
Well, unless churning through a new subaddress every time...
-
knaccc
well churn has never been popular because of bloat, and i also did work with either sarang or surae, i can't remember whom now, where it was becoming really obvious that multiple churns could not work because they stood out so clearly on the blockchain and were therefore not of any benefit
-
sgp_
E send funds to Alice address. Alice sends funds to entity X, n transactions away. Entity X knows all transactions made by Alice. If given to exchange, they tie real identity to all these transactions. X can be any entity on the receiving end of those n transactions
-
knaccc
sgp_ is this only if hashes are put on change addresses?
-
sgp_
I don't understand fully, but if there is some linked grouping known to a counterparty
-
knaccc
when you say "n transactions away", you mean it's EABCX or something like that?
-
knaccc
and how does X know about all transactions made by Alice?
-
knaccc
Alice is never transacting with X
-
sgp_
Here's an example:
-
sgp_
E -> A
-
sgp_
A -> B,C,D,E,F,...X
-
knaccc
so you're not saying A->B->C->D.... etc, you're saying A->B, A->C, etc?
-
sgp_
E already knows all transactions sent by A without cooperation, if sent to the same subaddress
-
sgp_
Yeah A->B, A->C, ...
-
knaccc
ok so A->X happens too?
-
knaccc
dircetly
-
sgp_
Yes
-
knaccc
ok
-
knaccc
so yes you are talking about the change problem. this is easily fixed by A never putting that hash on change outputs A sends to herself
-
sgp_
Let's say A->X is for a suspicious purchase where X is LE
-
sgp_
X asks for the real identity of A from E
-
knaccc
right, but how does X know A transacted with E?
-
knaccc
and if that is known, how does X know that A transacted with both E and X?
-
sgp_
If the change back to A and the transaction from E to A went to the same grouped, identifiable address
-
knaccc
right, so the hash on change going back during A->B and A->C and A->X etc cannot be the same hash each time
-
knaccc
or those txs will be linked
-
sgp_
Yes it must always be different and unlinkable or else you learn the full list of someone's transactions
-
knaccc
this is an easily solvable problem, all that needs to be done is to use hash(a || change one-time pubkey) instead for the hash on change
-
knaccc
although that does break the bloom filter stuff a little
-
sgp_
Suppose I'm B now and want to hide my association with A, who is not an exchange but is a malicious party
-
knaccc
so this is a totally different scenario, right?
-
sgp_
Yeah
-
sgp_
How does B select the decoy outputs if they can't identify which outputs are related to A
-
knaccc
so this is with A sending funds to B?
-
sgp_
Suppose for simplicity that A sends funds to B 3 times
-
knaccc
right, so the first time A->B happens, A chooses 10 decoys, each from a different per-subaddress bucket
-
knaccc
and the subsequent times A->B happens, A chooses further decoys from each of those buckets used in the prior transaction
-
sgp_
Okay, I think I'm with you so far
-
knaccc
there is a problem, which is if the wallet is sending to B using a different subaddress owned by B each time, then the wallet won't realize
-
knaccc
and so won't bucket properly
-
sgp_
When B wants to send, what bucket(s) do they choose from?
-
knaccc
it works exactly the same way again
-
sgp_
Suppose A send 3 times to B, each to the same subaddress
-
sgp_
Then what buckets does B select?
-
knaccc
as a quick side-note, it doesn't acutally matter if B does anything clever at all or not when sending funds on to cash out at E
-
knaccc
but B will just do the same thing A did
-
sgp_
How can B identify A's buckets?
-
knaccc
which is that on every tx from B to any particular destination, it will choose decoys from buckets
-
knaccc
B doesn't care about A's buckets
-
knaccc
that's not B's concern
-
knaccc
just like A didn't care about E's buckets
-
knaccc
assuming A got outputs in the first place by purchasing them from E
-
sgp_
Okay, maybe I had the selection backwards in my head then one sec
-
sgp_
knaccc I'm still not getting it. Can you try explaining the bucket selection from scratch again? Do I select the groupings arbitrarily or from someone I'm related to?
-
knaccc
sure, so here are the steps:
-
knaccc
1. you want to send funds to X
-
knaccc
it doesn't matter who sent anything to you in the past. that's not relevant
-
knaccc
2. you search the blockchain for a random bucket that contains at least a few outputs
-
knaccc
3. you pick 10 such buckets at random, and pick an output from each of those buckets as a decoy
-
knaccc
4. the next time you send to X, you check which buckets you had previously randomly picked from
-
knaccc
and you pick from each of those buckets a decoy which you have not previously used as a decoy
-
knaccc
that's it.
-
knaccc
i should clarify:
-
knaccc
s/you check which buckets you had previously randomly picked from/you check which buckets you had previously randomly picked from when sending to X
-
monerobux
knaccc meant to say: 4. the next time you send to X, you check which buckets you had previously randomly picked from when sending to X
-
sgp_
Okay, I think I get it now
-
sgp_
You're trying to find another possible identity
-
sgp_
Would this setup not encourage users to act selfishly and not make buckets whenever possible?
-
sgp_
Buckets would only be created if someone resent to the same subaddress correct?
-
sgp_
Also as a separate issue, when sending one transaction each to two addresses, how do you know both addresses are controlled by different people? You wouldn't know to select from buckets
-
sgp_
*from the same buckets
-
sgp_
And if you are always selecting from the same buckets for all transactions regardless, then all your transactions are trivially grouped together by any outside observers
-
knaccc
> act selfishly and not make buckets < it's possible, but recoding wallets isn't easy
-
knaccc
> how do you know both addresses are controlled by different people < you don't. this is a problem
-
knaccc
and that last point is very good, i'll think about it
-
sgp_
Last point is only relevant if you expect to always select from the same buckets for all transactions you send
-
sgp_
Multiple transactions to the same subaddress will already be grouped due to the nature of the design
-
sgp_
If someone transacts with one entity frequently, the change outputs are quite obvious too then
-
knaccc
yes, but that would be what you'd want to do if you wanted to be sure you were never missing situations when the wallet thinks it is sending to two different entities, but they're actually the same entitiy asking for payment via different subaddressses each time
-
knaccc
and i'm pondering the implications of always picking from the same buckets over and over
-
sgp_
Conditionally dropping linkability will have a bunch of weird complications like these I imagine
-
sgp_
Suppose this other extreme example:
-
sgp_
E has only one customer, A
-
sgp_
E -> A x3
-
sgp_
Hmm, I need to flesh out that example a bit more before I write it down actually
-
sgp_
But my thought process is: can E reliably eliminate buckets?
-
knaccc
i don't understand what you mean by eliminate them
-
sgp_
Heuristically eliminate all decoys related to specific buckets
-
knaccc
you mean consider them not likely decoys simply beacuse they are not customers of E?
-
sgp_
Yeah that was my first line of thinking, but I need to think about it more
-
knaccc
i don't think so. none of this requires exchanges to be large or small
-
knaccc
and works in non-exchange scenarios to prevent ABC issues if C is hacked (allowing A to see if B is transacting with C)
-
sgp_
Different thought: could attackers increase the likelihood of their outputs being selected as decoys by making a ton of buckets, thus increasing their selection chances easier than spamming outputs?
-
sgp_
Back to MRL 1 and 4 😎
-
knaccc
yes, and that's the same as the problem of choosing decoys in general
-
sgp_
True but it's exacerbated no? Since exchange deposits, mining pool payouts, etc would be 1 selection per user, not 1 selection per output
-
sgp_
Maybe you could weight the bucket selection chance by the number outputs in it instead of treating all buckets as equal
-
knaccc
i think in both cases it's still a case of proportion spammed that determines if they can get you that way, i may be wrong
-
knaccc
oh i see, yes perhaps
-
sgp_
I think with current ringsizes, there definitely is a way to conditionally sacrifice linkability to improve traceability for a net benefit, but damn it's hard to weigh those things
-
sgp_
I dare guess the greatest chance of a net positive sweet spot is by losing a *tiny* bit of linkability
-
sgp_
But wow would that increase the scope of Breaking Monero lmao
-
sgp_
Thanks for the conversation knaccc!
-
knaccc
sgp_ thank you for brainstorming it. my hope is that this could spark thoughts and it helps find the eventual solution
-
sgp_
knaccc: I support all crazy ideas :) Did you see this slightly less sweeping idea for public wallets like mining pools?
monero-project/monero #5222
-
knaccc
oh i missed that, thanks, will read
-
gingeropolous
i wonder if fake inputs would fix this
-
gingeropolous
probably not. because E would see A making a transaction to B, and so E could see E's output being used as an input, and now there's just another random (false) input. B then uses A's output as an input + some false input and sends back to E.
-
gingeropolous
still a loop, and E would know that A is actually spending that output... yeah, not much different than if A combined E's output with another of its inputs to make a transaction
-
gingeropolous
ugh this nomenclature is so cumbersome
-
moneromooo
Since the scheme is voluntary and people will normally use a subaddres per sender, the wallet could hash the subaddress *and* the sending wallet secret key. This makes the "locate donations to the EFF" impossible, while still allowing matching sends to the same subaddress by a blockchain observer.
-
» moneromooo goes back to sleep
-
moneromooo
Also, if change gets random tags due to the issue sgp mentioned, then if you see grouped outputs, you now know they aren't change. So change would have to *sometimes* reuse a tag.
-
sgp_
Change would hide among outputs sent to single-use stealth addresses though, so I wonder how much that matters in practice. It definitely could matter
-
knaccc
moneromooo > the wallet could hash the subaddress *and* the sending wallet secret key < whoa, i think that might be a really good idea
-
knaccc
because as you point out, it's supposed to be a subaddress-per-sender anyway
-
knaccc
so there is no loss when limiting the bucket in that manner
-
moneromooo
It definitely breaks fast scan and janus though.
-
knaccc
true
-
knaccc
i think the biggest showstopper at the moment could be what sgp_ came up with yesterday, which is that the wallet won't know if you're sending to the same merchant via different subaddresses, or to different merchants via different subaddresses
-
knaccc
and it pains me to type this, but maybe the answer to that is to recommend subaddresses for normal people, and integrated addressses/integrated subaddresses for merchants
-
knaccc
i can't believe i just typed that. this is messy.
-
knaccc
and it feels a bit clunky to ask the user if an outgoing payment is to a merchant they've paid before
-
knaccc
so the cleanest way to handle this is to consider the implications of having buckets that are used for all outgoing txs
-
knaccc
and then have those buckets rotated in and out over time
-
knaccc
and now the wallet doesn't need to know whether it's sending more outputs to the same entity or not
-
knaccc
i think what i just wrote might work. it was already the case that merchants could have kept a note of all purchaser-change-addresses they observed during incoming transactions to the merchant, and then compared notes with other merchants to see if any of those change outputs were spent with other merchants
-
knaccc
s/purchaser-change-addresses/purchaser-change-outputs
-
monerobux
knaccc meant to say: i think what i just wrote might work. it was already the case that merchants could have kept a note of all purchaser-change-outputs they observed during incoming transactions to the merchant, and then compared notes with other merchants to see if any of those change outputs were spent with other merchants
-
sgp_
just make a consensus rule so that exchanges need to pinky promise to share their data cleanly, but in a way no one else can :p
-
sarang
What's the most clear way to share CLSAG timing data?
-
sarang
Signatures only? Overall transaction estimates?
-
sarang
Range proof batching? No batching?
-
moneromooo
All of it :D But there was some verging on dishonest hyping of crazy speed improvements based on batching 64 txes or so recently, so should be careful how people use the data.
-
sarang
I've presented batch results before
-
moneromooo
Sure. But IIRC someone took the best number possible and threw it out to the masses.
-
moneromooo
Having numbers for all interesting cases is good.
-
sarang
Oh, was this for the BP improvement?
-
moneromooo
I might be wrong. My memory's hazy here.
-
moneromooo
Could be.
-
sarang
I had put a few batch examples into the PR, but they were clearly marked as such
-
moneromooo
Felt like shitcoin time.
-
sarang
For the blog post, I can list timing for CLSAG+BP with no batching, and then note that during sync, the improvement is better because of batching
-
sarang
That seems fair and accurate
-
moneromooo
Sounds good to me.
-
sarang
For a single 2-2 transaction, CLSAG+BP verification improvement is 10%
-
sarang
just signature is 20%
-
sarang
so you asymptotically approach something closer to 20% with higher batching
-
moneromooo
Most people will be interested in the whole tx verification really. Which is... annoying to get in monero.
-
sarang
Yeah
-
sarang
I count signature verification, balance check, and range proof
-
sarang
Which are the heavy hitters
-
sarang
and I note that YMMV
-
sarang
Oh even better, I can note that signature speedup is 20%, with at least 10% speedup for transactions as a whole
-
sarang
That doesn't downplay CLSAG's improvements, but also gives some better real-world estimates
-
sarang
-
dEBRUYNE
fwiw, I have typically used the 20% figure if someone asked about the relative improvements
-
sarang
20% is accurate for signatures along
-
sarang
*alone
-
moneromooo
Looks good. But uses ! for effect, which amused me.
-
sarang
I'm pretty sparing with exclamation marks :)
-
sarang
Never get to use them in formal papers
-
sarang
dEBRUYNE: for signatures alone, space is ~50%, time is ~20%
-
sarang
For overall 2-2 transactions, space is ~25%, time is ~10%
-
sarang
time improves with range proof batching
-
sarang
FWIW, I consider the size improvements to be the bigger deal
-
sarang
timing improvements are a nice benefit
-
sarang
(and depend on some optimizations that I did)
-
dEBRUYNE
Ok, thanks
-
sarang
moneromooo: now you have me questioning the excitement of my punctuation...
-
sarang
bah
-
moneromooo
Sorry. I guess it's fine for blog post.
-
sarang
heh
-
moneromooo
I've got an overflow of hate for hype and dishonest arguments of late and I may be overmatching, you can ignore me ^_^