×

19
20

On-chain tracking of Monero and other Cryptonotes (medium.com)

submitted by fireice_ukxmr-stak

On-chain tracking of Monero and other Cryptonotes

12 points•1 comment•submitted by fireice_ukRyo to r/CryptoNoteTech
all 58 comments
sorted by:
best
topnewcontroversialoldq&a

[–]SamsungGalaxyPlayerXMR Contributor 20 points21 points  (22 children)

Thank you for mostly sticking to the facts. I appreciate this writeup about CryptoNote traceability techniques. This is a good high-level, ELI5 overview on what to look out for when trying to keep your outputs private. There are many potential problems when joining them together.

[–]Bassique 0 points1 point  (0 children)

I would be good if someone linked to this thread in the comments of the Medium article. Similar to how Justin replied in the zcash-forum. Just to make sure there is some easily available balance in the argument available.

[–]dEBRUYNE_1Moderator 17 points18 points  (11 children)

In this attack the authors introduce a very simple and intuitive concept. If a transaction spends both outputs of another transaction then it is overwhelmingly likely that those are the real outputs.

How often does this occur though? In a standard transaction, one output goes to the recipient and one goes back as change to the sender.

Also, can you explain where, in the second example (Tracking churning), output 2B is coming from? A normal transaction does only generate one change output (2A). Similarly, a normal sweep_all transaction only generates one change output (2A). The other output is going to a random address that is not under the sender's control. I suppose some people use sweep_all to create multiple outputs (in order to be able to spend more quickly). However, this is more exception than the rule.

Here Alice had three outputs in her wallet (1A

How would an observer know 1A belonged to Alice? Is the article based on the assumption that Bob send all outputs (1A - 1D) to Alice? Later in the article you state assume that Bob sent outputs 1A and 1D, but perhaps you could clarify this.

Did you notice how we deanonymised T2?

In this example, output 1A and output 2B are combined in transaction T2. However, how would an observer know that output 1A belonged to Alice? In case he wouldn't know, it would not be obvious that both outputs belonged to Alice, thereby significantly weakening this analysis.

and the other output didn’t form another ring therefore Alice either hasn’t spent it yet or it to someone else.

What if the output was used as decoy in another ring?

Let’s go back to the normal flow diagram and assume that Bob sent outputs 1A and 1D.

If 1B is not sent by Bob, how do you know transaction T2 (where 2A and 1B are combined) is not simply a transaction by another person where 2A is used as decoy output? Transaction T2 will also generate two outputs, namely 2A and 2B (one for the change and one for the recipient). How do you know, as an observer, which one of the two is change?

[–]SamsungGalaxyPlayerXMR Contributor 5 points6 points  (0 children)

In at least one of the examples, fireice outlined it as a user receiving an output, running sweep_all, receiving another output, running sweep_all again, etc. This is understood to be poor privacy practice, but I can see how some old references to sweep_all before churning was better defined (it still isn't btw, but it's slightly better) could lead users to performing this unusual action.

There is also a poisoned output element to the mentioned attack.

There definitely is more nuance here than the article lets on, but ultimately it is correct that users who essentially sweep_all after receiving poisoned outputs make their actions incredibly obvious. There are other related heuristics.

[–]fireice_ukxmr-stak[S] 2 points3 points  (9 children)

LATER EDIT

Since /u/dEBRUYNE_1 basically decided to play "I misinterpret your post therfore you are wrong" game, [ 1 ], run away [ 2 ], then claim some kind of victory [ 3 ], let me clarify one thing:

He didn't even notice half of the article doesn't deal with churning, for the other half he decided to beat a tactical retreat when presented with a screenshot that it is possible after-all. Nuff said, enjoy the rest of the conversation.

  --------  

Also, can you explain where, in the second example (Tracking churning), output 2B is coming from?

This is assuming Alice was slightly smarter with her churning and incorporated sub-address. "Official" sweep_all method is nearly useless as it generates a distinct chain of 1 input, 2 output transactions.

How would an observer know 1A belonged to Alice?

Because it forms an input to a cyclical reference of outputs. What's nice about this attack is that you get identities, not keys, since you are looking at groups of outputs that interact together. What's causing them to interact is a person not a key.

Is the article based on the assumption that Bob send all outputs (1A - 1D) to Alice?

No, Bob only comes in on the next paragraph, you confused the diagrams. I specifically varied the number of starting outputs to prevent it - "Alice had three outputs in her wallet"

However, how would an observer know that output 1A belonged to Alice? In case he wouldn't know, it would not be obvious that both outputs belonged to Alice, thereby significantly weakening this analysis.

I have a hangover but I think you asked the same question twice =), I answered above.

What if the output was used as decoy in another ring?

Then it won't form a cyclical reference and it disappears off our grid.

If 1B is not sent by Bob, how do you know transaction T2 (where 2A and 1B are combined) is not simply a transaction by another person where 2A is used as decoy output?

This is because such a short chain of reference (we are working with chain rather than cycle... ) between two known outputs (as this is an active attack) is unlikely to happen by accident. We only pick up change, as this is what stays under control of "Alice" identity and will interact with her other outputs.

[–]dEBRUYNE_1Moderator 7 points8 points  (7 children)

This is assuming Alice was slightly smarter with her churning and incorporated sub-address

Whether you churn to a subaddress or a main address does not matter. It will look the same for an observer. Also, this still doesn't explain where output 2B is coming from. Supposedly 2A and 2B are both going back to the sender as change. Are you assuming 2A goes back to the main address and 2B goes to a subaddress? Note that this normally does not happen.

"Official" sweep_all method is nearly useless as it generates a distinct chain of 1 input, 2 output transactions.

As long as it mimics spending behavior the chain will not be distinct.

Because it forms an input to a cyclical reference of outputs.

Which you can only point out if you initially know, as observer, that output 1A to 1D belong to Alice. If not, the analysis is significantly weakened.

Your example combines 2A with 1B. If you don't know, in advance and as an observer, that 1B belongs to Alice, how do you know which one of the 11 inputs is the real one?

No, Bob only comes in on the next paragraph, you confused the diagrams. I specifically varied the number of starting outputs to prevent it - "Alice had three outputs in her wallet"

I see. I do think the paragraph is confusing insofar as it doesn't specify which outputs are known to the observer.

""Alice had three outputs in her wallet" <= How do you know, as an observer, which outputs that are?

Then it won't form a cyclical reference and it disappears off our grid.

Your cyclical analysis rests on the assumption of output 2B being generated and later on used. However, you have not properly explained where output 2B is coming from.

This is because such a short chain of reference (we are working with chain rather than cycle... ) between two known outputs (as this is an active attack) is unlikely to happen by accident

This thus assumes both initial outputs (1B and 1C+1D) are known to the observer.

We only pick up change

Again, how do you know, as an observer, which one of the two is change?

I agree with this analysis in case all initial outputs are known to the observer. However, the analysis is significantly weakened in case they are not.

[–]fireice_ukxmr-stak[S] 1 point2 points  (6 children)

Supposedly 2A and 2B are both going back to the sender as change. Are you assuming 2A goes back to the main address and 2B goes to a subaddress? Note that this normally does not happen.

It isn't relevant, we track how groups of outputs interact with each other. And the motor behind that interaction is a person not an address.

Which you can only point out if you initially know, as observer, that output 1A to 1D belong to Alice. If not, the analysis is significantly weakened.

Nope, you just import the blockchain as one giant graph into analysis software and then look for cyclical references in that graph. As I discussed in the article, the chances or size 3 - 7 reference rings occurring by accident is negligible.

Your cyclical analysis rests on the assumption of output 2B being generated and later on used. However, you have not properly explained where output 2B is coming from.

I think you are getting to hang up on wallet behaviour, whereas what I'm interested in are systemic flaws. Here the steps to reproduce the graph in-vivo:

  1. Load wallet <addr> with 3 outputs
  2. transfer <addr> any_amount (T1)
  3. transfer <someone_else> 1.0 (T2)
  4. transfer <someone_else2> 1.0 (T3)

This thus assumes both initial outputs (1B and 1C+1D) are known to the observer.

I make no such assumption.

Again, how do you know, as an observer, which one of the two is change?

We sent two outputs to Alice. We observed a chain of references that links both outputs. As such it is fairly reasonable to conclude that the chain is all comprised of outputs controlled by Alice (aka, they are the change outputs)

[–]dEBRUYNE_1Moderator 4 points5 points  (5 children)

It isn't relevant, we track how groups of outputs interact with each other

It certainly is relevant, as your cyclical analysis rests on the assumption of output 2B being generated and later on used.

Nope, you just import the blockchain as one giant graph into analysis software and then look for cyclical references in that graph.

Which you can only spot if you know in advance which outputs belong to Alice. If not, it simply is a game of conjecture.

I think you are getting to hang up on wallet behaviour, whereas what I'm interested in are systemic flaws. Here the steps to reproduce the graph in-vivo:

Step 2, output 1B and 1C get combined. Output 2A goes back to the sender as change, output 2B normally goes to the recipient. The wallet, unless explicitly specified, will never send two outputs back to the sender.

We sent two outputs to Alice. We observed a chain of references that links both outputs. As such it is fairly reasonable to conclude that the chain is all comprised of outputs controlled by Alice (aka, they are the change outputs)

You sent 1C and 1D to Alice. Alice subsequently combines them in T1. T1 generates 2A and 2B. As an observer, you don't know which one is change and which one goes to the recipient. Additionally, outputs typically get included once as decoy outputs. Let's say Alice spends 2A and the recipient spends 2B. This thus creates four possible transaction paths. Each transaction path will again have two outputs. There will thus be eight outputs that possibly belong to Alice. Your analysis is only relevant if the observer (or whoever is trying to do the analysis) also knows Alice possesses 1A and 1B (which he doesn't, according to you).

[–]fireice_ukxmr-stak[S] 0 points1 point  (4 children)

It certainly is relevant, as your cyclical analysis rests on the assumption of output 2B being generated and later on used.

I gave you the mechanism later on in that post.

Which you can only spot if you know in advance which outputs belong to Alice. If not, it simply is a game of conjecture.

Nope, why would you need to know that? Of course you can't link the reference ring to Alice purely from that. But that's like saying bitcoin addresses are unlinkable because they don't have your name attached.

Step 2, output 1B and 1C get combined. Output 2A goes back to the sender as change, output 2B normally goes to the recipient. The wallet, unless explicitly specified, will never send two outputs back to the sender.

Not sure what you are talking about, I just tried the steps on cli wallet and it works.

You sent 1C and 1D to Alice. Alice subsequently combines them in T1. T1 generates 2A and 2B.

No.... Ah, I see you are still confusing the two sections. Notice "chain" (the red thing in the the third diagram) vs cyclic reference in the second diagram. We don't send anything cyclic reference section. This is a passive scan that can be done purely form blockchain data. To stop confusion I suggest we establish terminology, prefix any figures with "C" for cyclic reference section and "R" for reference chain section.

[–]dEBRUYNE_1Moderator 4 points5 points  (3 children)

I gave you the mechanism later on in that post.

That mechanism does not generate two outputs for the sender.

Nope, why would you need to know that?

Because otherwise it gets significantly more difficult to link outputs.

Not sure what you are talking about, I just tried the steps on cli wallet and it works.

Unless explicitly specified, the wallet will not generate two outputs for the sender. Any user can attest to that.

No.... Ah, I see you are still confusing the two sections.

I am not confused.

This is a passive scan that can be done purely form blockchain data.

The analysis (R) falls apart if not all initial outputs are known to the observer, as I've previously explained.

The other analysis (C) is based on the assumption that T1 generates two change outputs for the sender (2A and 2B), which is quite uncommon, as the wallet, by default, only generates one change output for the sender.

To stop confusion I suggest we establish terminology, prefix any figures with "C" for cyclic reference section and "R" for reference chain section.

I guess that would help readers, yes.

[–]fireice_ukxmr-stak[S] 1 point2 points  (2 children)

Maybe just me but I feel like we are rapidly departing from reality here:

That mechanism does not generate two outputs for the sender. Unless explicitly specified, the wallet will not generate two outputs for the sender. Any user can attest to that.

Did you even try the steps I outlined [ 1 ]? Because guess what, they do work. So, no, this user can't attest to that.

I am not confused.

 

The analysis (R) falls apart if not all initial outputs are known to the observer, as I've previously explained. The other analysis (C) is based on the assumption that T1 generates two change outputs for the sender (2A and 2B), which is quite uncommon, as the wallet, by default, only generates one change output for the sender.

Then feel free to humour me and restate while actually using the notation, because C1C and C1D don't need to be sent by me or Bob, contrary to what you are claiming.

[–]dEBRUYNE_1Moderator 4 points5 points  (1 child)

Did you even try the steps I outlined [ 1 ]? Because guess what, they do work. So, no, this user can't attest to that.

Your screenshot shows that you are sending a transaction to yourself of 1 XMR. Thus, you receive one output as recipient and one output as change. Normally, you are not both the recipient and the sender. Thus, normally you only receive one change output, as the other output goes to the sender. The scenario you are simulating does not happen either if one is churning, because then the sender will merely receive one output back (as the other output is destined for a random address). In sum, the scenario you are simulating is inconsistent with normal spending behavior and normal churns. Furthermore, this particular type of behavior (which is purposefully bad for the user) has never been recommend to users nor have I ever seen it discussed.

because C1C and C1D don't need to be sent by me or Bob, contrary to what you are claiming.

They do and even then the analysis falls apart if C1A and C1B are not known. I have previously explained why and you haven't rebutted that thus far.

[–]fireice_ukxmr-stak[S] 1 point2 points  (0 children)

Then feel free to humour me and restate while actually using the notation,

[–]dreefen 6 points7 points  (0 children)

You're like Monero's Craight Wright: string together a random sequence of technical jargon and claim to have made some point.

Then we someone asks you to clarify more nonsense is produced.

[–]HoboHaxor 7 points8 points  (0 children)

Gotta love the little sour grapes dig at the end.

[–]USER_citizenfive 3 points4 points  (1 child)

Can someone ELI3 ?

Letters and numbers within the same word confuse me

[–]fireice_ukxmr-stak[S] -5 points-4 points  (0 children)

ELI3: Monero's privacy is not fit for purpose.

[–]FattyMcBoomBoomz 4 points5 points  (11 children)

So this only applies to txs with change return or multiple recipients? Wouldn't churning the entire UTXO maintain untraceability? Please correct me if I'm wrong.

[–]strofenig 4 points5 points  (9 children)

I believe he is defining churn as 1) the first sweep_all transaction, and/or 2) the first time you spend two previously unrelated outputs. If, however, you continued to churn, and repeatedly sent an output to yourself, this type of analysis couldn't be performed.

Therefore his advice:

"Standard Monero advice is to “churn” (send money to yourself). I warned users very strongly not to do it."

is misleading, and holds true if you "churn" only once. Can someone else please confirm?

[–]fireice_ukxmr-stak[S] 2 points3 points  (8 children)

Your assumption is wrong, this method of churning is self-defeating as it generates a distinct chain of 1 input, 2 output transactions.

[–]dEBRUYNE_1Moderator 5 points6 points  (7 children)

Quoting myself:

As long as it mimics spending behavior the chain will not be distinct.

[–]fireice_ukxmr-stak[S] 2 points3 points  (6 children)

Nope, because we are not looking at single transactions in isolation, we are looking at networks of them. Can you suggest any other thing that would produce a 4+ long chain of 1/2 transactions referencing each other?

[–]dEBRUYNE_1Moderator 10 points11 points  (5 children)

Sure. Let's say a user buys 10 XMR and withdraws it to his wallet. Day 1, he pays his friend for dinner. Day 7, he buys something from the coral reef store. Day 22, he sends part of his stash to an exchange to sell it. Day 25, he pays another friend for diner. Day 35, he buys another thing from the coral reef store. This creates a 4+ long chain with 1/2 transactions referencing each other. Furthermore, a 4+ long chain does not even have to be created by a single user (a long chain can be created by multiple users if the output is used as decoy).

[–]SamsungGalaxyPlayerXMR Contributor 5 points6 points  (0 children)

Great example, thank you.

[–]fireice_ukxmr-stak[S] 2 points3 points  (3 children)

Point taken. I should have said - "Can you suggest any other thing that would produce a 4+ long chain of 1/2 transactions referencing each other that starts with a large merging (let's say 10/2 for the sake of argument) transaction."

Of course we are working with untagged outputs, so specificity rate will be low. It doesn't mean that you can't combine it with another test (tagging does exactly that) to weed out the false positives.

[–]dEBRUYNE_1Moderator 8 points9 points  (0 children)

Even then, if the subsequent churns mimic spending behavior, only the initial 'consolidation' transaction is vulnerable.

[–][deleted]  (1 child)

[deleted]

    [–]fireice_ukxmr-stak[S] 1 point2 points  (0 children)

    You'd have to introduce these tagged outputs during the churning process,

    Tagging would be wrong test to combine it with here, let me explain the general approach, since I believe in teaching to fish rather than giving out fish:

    Since "long chain of 1/2 and a 'head' on top" is extremely selective but not very specific, you need to combine it with fairly specific test (selectivity is not required), for example metadata interval.

    Some of your other articles concerning metadata apply of course, but disregarding churning outright is just wrong.

    I'm not disregarding it. I'm saying ordinary users are unlikely to accomplish it without self-incriminating, there are too many pits to fall into.

    [–]fireice_ukxmr-stak[S] 3 points4 points  (0 children)

    Monero does not have UTXO set.

    [–][deleted]  (5 children)

    [deleted]

      [–]fireice_ukxmr-stak[S] 2 points3 points  (4 children)

      DO NOT do this. It is useless as it creates a distinct chain of 1 input, 2 output transactions.

      [–]dEBRUYNE_1Moderator 3 points4 points  (3 children)

      Quoting myself:

      As long as it mimics spending behavior the chain will not be distinct.

      [–]fireice_ukxmr-stak[S] 1 point2 points  (2 children)

      Nope, because we are not looking at single transactions in isolation, we are looking at networks of them. Can you suggest any other thing that would produce a 4+ long chain of 1/2 transactions referencing each other?

      [–]Teknex 4 points5 points  (2 children)

      For Spectrecoin, we solved the 'output merging' deanonymization problem (or TRX output set problem as we call it) by implementing a mixin picking algorithm which adds mixins (fake outputs) of same transactions. For an observer it is than impossible to say if outputs of same TRX are real or fake.

      [–]SamsungGalaxyPlayerXMR Contributor 1 point2 points  (1 child)

      This is also called "binning outputs." There are pros and cons.

      [–]Teknex 1 point2 points  (0 children)

      I read about binning outputs in a paper, there was suggested to pick outputs from 'bins' containing outputs created in a certain time frame. Our strategy is a bit different, initially 1/3 of outputs is chosen from last 3 days, other 2/3 from all (not compromised) outputs. Then for further ring signatures of same TRX there is a certain chance that outputs are picked not completely random, but from TRX from where the initial mixins have been taken, mimicking a user which spends multiple outputs of one transaction.

      [–][deleted]  (2 children)

      [removed]

        [–]needmoney90[M] 4 points5 points  (0 children)

        Comment removed for ban evasion.

        [–]SamsungGalaxyPlayerXMR Contributor 1 point2 points  (0 children)

        No, I articles that look at Monero's limitations are very important.