Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Address Reuse occurs in Blinded Outputs #2034

Closed
AvivMilner opened this issue Jul 29, 2019 · 14 comments

Comments

@AvivMilner
Copy link

commented Jul 29, 2019

General Description

Address Reuse has been detected by a handful of users. In particular, the address that is re-used is the address given to the coordinator in the form of a blinded output. The result is that a user will mix coins, and have several mixed coins of various denominations in the same address.

  1. It is unclear if this bug has been resolved with 1.1.6, it may not need to be fixed.
  2. A small number of users have come forward, it is unclear if they are honest or not, however this problem has yet to be reproduced by a trusted dev.
  3. nopara73 and will try to replicate the problem over the next week to see if it reoccurs.

How To Reproduce?

  1. Users typically mixed a large amount of coins, in some cases the users had several distinct wallets on a single device. Users did not run multiple wallets at the same time.
  2. Users set the anonymity set to more than 100, and re-mixed frequently
  3. Users had a wallet that was on a slower computer
  4. Users de-queued and en-queued several times,

Screenshots

Please look at the following transactions as examples:

(a) 4 transactions - 2 were blinded oututs of 0.1 BTC, 2 were remixes of the 0.1 BTC outputs.
(b) The 2 coinjoins with same outputs were confirmed in the same block.
https://blockstream.info/address/bc1qr3l94myyg5ex82lydveuhawg08hw72va3xaxjq

(a) 4 Transactions - where the address was used as change twice in a CJ, then spent in a CJ twice
(b) Both transactions were confirmed in the same block.
https://blockstream.info/address/bc1qhzq5ck87rr5cfw9wjhfwnfalcn80fcy54mgwv9

The above two examples happened a while ago, these transactions below happened more recently and include a user who had address reuse on both sides of the transaction.

https://blockstream.info/address/bc1qtsypsw9aejrhphf28tzuhld7wgk5aj53l6tazv

Operating System

Users described this problem with:
Windows 10
macOS

Logs

Logs of certain users may be available upon request.

Wasabi Version

Users claim to be using 1.1.6

@nopara73

This comment has been minimized.

Copy link
Collaborator

commented Jul 30, 2019

I am running mix for a week and will see if address reuse is happening or not. Will get back here on Monday.

@benthecarman

This comment has been minimized.

Copy link
Collaborator

commented Jul 30, 2019

Do you know if they were queueing and dequeueing before this happened?

@AvivMilner

This comment has been minimized.

Copy link
Author

commented Jul 30, 2019

I have decided to take a quick look at the types and frequency of address re-use among recent transactions. I have taken 1 transaction as a sample:
wtxid: 5b782886e602f0b55d4af0e5f2ddfac2eda783d0a4132c8821aeecbc3cd76302

I exclusively checked the blinded outputs to see if they had been re-used.
Participants (0.1): 87 participants
Address Re-use: 9 participants (10.3%)
The following participants (ordered from the 1st blinded output to the 87th) exhibited address re-use:
[7] bc1q0s03lysw0e4g709k4hfungt4n2kten6yreeekx
[12] bc1qcf7tcg7m6s5jcqlzzlsde9ez4sw6n4lvnt6j5f
[16] bc1qmelch02qsv8jvz3lltjkwrh47sngzv6rxphsdv
[19] bc1qq9p9e8ylq0vcs8svqrkka6aqac8q6kz4ehn7k6
[27] bc1qn8l89zx5f33cjrgsm6w43cvh3lyvllt3snx2vf
[34] bc1q3ffxw6ynyacslns9flucc9jp2qagwl7ry2s6sy
[54] bc1qhe2qyy2s4r4mkn65r3jczdxa7zcsary742gj59
[63] bc1qxtemzs2jmrrgk5gm6vj4z6mk55evthv78ze55g
[87] bc1q65gsu8us3jxf4sykudancr5ppgudfzhwxxgsv9

Observations:

  • 87 was the least harmful, 2 blinded outputs of 0.1 BTC which were both later remixed.
  • 63 was the worst case, 25 txns with 21 0.1 BTC blinded outputs used and even 1 0.2 BTC blinded output. 1 CoinJoin involved this address on both sides!
  • 54 had 1 blinded output and 1 use of change (particularly harmful)
  • 34 received 2 blinded outputs of 0.1 and 0.2
  • 27 received 2 blinded outputs of 0.1
  • 19 received 2 blinded outputs for 0.1 and 0.2
  • 16 received 2 blinded outputs for 0.8 and 0.2
  • 12 received 8 outputs - 3 change (!?) and 5 blinded output of 0.1
  • 7 received 2 blinded outputs for 0.1 each

Further observations:

  1. The common problem is for users to receive blinded outputs to the same address, but never used as change! Only 2 transactions involved reuse in change of a CoinJoin
  2. Blinded outputs are reused across denominations
  3. Addresses closer to the top of the blinded set had more reuse, are unblinded outputs ordered in any non-random way? For example, if they are ordered by the time seen, this could say tsomething.
  4. The address reuse only dropped the anonset of other participants by at most 8%. In several cases the address re-use had NO negative effect as the users recombined the coins after anyways.
  5. Address reuse happens even when transactions are confirmed many blocks apart.

I hope this saved you some time nopara73.

@MaxHillebrand

This comment has been minimized.

Copy link
Collaborator

commented Jul 30, 2019

Quite interesting, thanks for the detailed write-up @AvivMilner!

1] I confirmed this in the Slack, and unfortunately there is no way for the coordinator to see if a blinded coin join output has address reuse, because, well, it is blinded... So the coordinator can only abort the round after output registration - here the output addresses of all peers is revealed [although unused sine aborted],

3] #1927 #1944 change the input and output ordering, that might help you. Not sure about what exactly you mean though...

4] So, if this is a malicious adversary, then their attacks do not lead to de-anonymization, but it makes the CoinJoin "look bad" and scare away users. If it is a bug, then it affects only a small subset of users. Can you maybe calculate a median of the recent cases? And we would need more info from the users, what version of Wasabi and OS they are running, and how they use the wallet in general [multiple instances, often de-queueing, etc.]

5] Mhhh - ok, then this means that it is probably not the mempool dropping issue, which was fixed several versions back.

@MaxHillebrand

This comment has been minimized.

Copy link
Collaborator

commented Jul 30, 2019

Regarding address 63, it might be worth noting that there was a consolidation with 17 0.1 coin join outputs into a single output [no change!] P2SH, an address format not supported by Wasabi. This might indicate that the user is working with a non-Wasabi wallet.

@AvivMilner

This comment has been minimized.

Copy link
Author

commented Jul 30, 2019

Additional input from a client:

  • I've been constantly mixing for more than a month now. I've mixed about 50 BTCs to a minimum Anonymity Set of 101.
    -I'm working with three wallets. They all have a different seed and are run on different machines under macOS, with completely unrelated coins.
  • I've notices address reuse in the three wallets but with a few differences. The oldest wallet has much more reuse. This wallet is run on a slower machine and Wasabi often crashes there so I had to reopen the wallet often and requeue the coins.
  • In the past I also used to enqueue/dequeue some coins as a way to try to save some money on fees since I noticed that remixes aren't almost-free as advertised but can sometimes be costly since the base denomination keeps decreasing.
  • Approximate reuse rate: 20% *Second and third wallet are kept in different machines which appear to be more stable thus I almost never have to reopen Wasabi and I mostly leave the wallet figure out which coins to mix following his algorithm.
  • Those two wallets have a much lower reuse rate. I'd say between 1 to 10%. *I'm not sure how I will tackle this issue.

This is the most detail I have received yet about the issue.

@MaxHillebrand

This comment has been minimized.

Copy link
Collaborator

commented Jul 31, 2019

Thanks Aviv.

  1. It seems that this issue is then not related with running separate instances in parallel.
  2. The most address reuse happens on old Wasabi version, and unstable laptop running MacOS, which as I remember had many issues just a couple versions ago. This might be suggesting that i] somethings are fixed already, ii] it might be the hardware and crashes, iii] even the new versions have some reuse, so it's still not fixed properly.
  3. Also, there are many power users who mix similar amounts who do not experience this issue.
@nopara73

This comment has been minimized.

Copy link
Collaborator

commented Jul 31, 2019

As it has been discussed many times and many places, address reuse was a known issue when we lost unconfirmed transactions before 1.1.6. However, we cannot fix again what's already fixed, so looking at historical data is irrelevant.

As I said, I am mixing since Monday, and I just checked: I did not experience any address reuse so far, I will wait out the whole week and get back here.

@benthecarman

This comment has been minimized.

Copy link
Collaborator

commented Jul 31, 2019

Worst-case solution could be just stopping any Bob from registering an output that's address has been previously used. This would stop malicious attackers from doing this on purpose, however, requires us to index every address which would be a lot of overhead.

@nopara73

This comment has been minimized.

Copy link
Collaborator

commented Aug 5, 2019

The results of the 1week mixing test: #2077

@nopara73

This comment has been minimized.

Copy link
Collaborator

commented Sep 17, 2019

When we get an inv from a node we try to acquire the tx from that node and don't bother with other nodes' invs for the same tx.

So if the tx acquiring fails with this node, then it's possible we never get to know about the tx until it confirms.

It could be the reason why we experience this issue. I'll address it in my mempool refactoring PR.

@nopara73

This comment has been minimized.

Copy link
Collaborator

commented Sep 18, 2019

Possibly resolved: #2292

Should start another test.

@nopara73

This comment has been minimized.

Copy link
Collaborator

commented Sep 28, 2019

I'm running the 1week test.

@nopara73

This comment has been minimized.

Copy link
Collaborator

commented Oct 3, 2019

Results of 1 Week Mixing Test 2

Note that during the testing, I needed to use my Linux for development, I was running multiple instances and made the computer freeze and the index was corrupted a few times, so if there's address reuse then the test is invalid and needs to be repeated with more laboratory environment, but if there isn't, then the test is valid, in fact it gives us more confidence that it can withstand a couple of failure scenarios.

(without doxxing the exact amounts)

  • Period: 1 week mixing
  • Received: ~3.5BTC ($30_000)
  • Total Fees (Network + Coordinator): ~ 0.01 ($100)
  • Percentage of fee: ~0.35%
  • Average anonymity gained: 250 anonset

So far the stats are very similar as the first test.

Address Reuse

There were none.

@nopara73 nopara73 closed this Oct 3, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
4 participants
You can’t perform that action at this time.