How to detect the change output?

[auzaar]

bitcoin-qt tries to randomize the position of the change output, but I believe the code has a flaw:

// Insert change txn at random position:
vector<CTxOut>::iterator position = wtxNew.vout.begin()+GetRandInt(wtxNew.vout.size());
wtxNew.vout.insert(position, CTxOut(nChange, scriptChange));

The problem is that size() is one in the common case of one payee, so GetRandInt will always return 0.The change ends up in the first output.

I think it should be size()+1.

long live the open source!

[1714662470]

1714662470

[1714662470]

1714662470

[1714662470]

1714662470

[1714662470]

1714662470

[molecular]

When will we have a fix for this?

you could just add "+1" after "size()" and recompile. maybe do some testing before using it productively.

[SgtSpike]

When will we have a fix for this?

you could just add "+1" after "size()" and recompile. maybe do some testing before using it productively.

I don't compile. Did it once, never planning to do it again. Biggest headache I've ever experienced.  So, I am asking about a general installer release.

Personally, I don't really care about this anonymous side of things and hiding my true balance or associated addresses.  I don't have anything to hide with regards to my transactions.  But I know a lot of people do care about it, so I am sort of asking on everyone's behalf when we can expect an updated client to be released.

[BkkCoins]

I think it's also worthwhile pointing out that now there is a "known" history of change/payment values. It should be easier to develop algorithms that can select future change values even after the bug is fixed, which a much higher confidence level.

[Peter Todd]

I think Hal's donation wallet address has a flaw. The problem is that balance() returned 0.

I added one bitcoin, but balance()+1 doesn't seem like enough.

Details here: http://blockchain.info/address/1HALookLvrqrn2kxHhXCnwDgknD3RXifhH

From Hal's sig:

Hal 157i5gK7iN4bNAN39Ahuoiq6Tx5TaQukTE

So Hal, which one is your current Bitcoin address?


Also, it's funny how every tx to 1HALook is obviously affected by this bug.

[Hal]

Actually the OP observed that the software always puts the change first. I was working on a separate project suggested by Mike Hearn, using the new secure "trusted computing" modes on modern cpus to enforce spending limits even when infested with malware. I'm using Jon McCune's flicker software from sourceforge. The secure mode signs transactions and enforces limits on spends, but to know the transaction amount it has to know which is the change output.So I was just looking at this code yesterday and scratching my head (figuratively). I'll post more on this project when it's further along.

As far as my donation address, I created that years ago using Gavin's original vanitygen patch. I don't even know if I still have the key. It might be on a computer I don't use any more. I've substituted one of my offline savings wallet addresses. I shouldn't lose that.I'm not hurting for bitcoins; I started running the first day (and gave up after a few weeks because of the fan noise). Still, it's the thought that counts - thanks!

[Peter Todd]

Yes, I saw that project, I'm curious to try it out myself, although I'll have to upgrade my computer first.

It's interesting that you found this bug by looking at the code. I mean, the results of it have been sitting in plain sight for, well, anyone to see. Heck, I'm kicking myself for not realizing it, let alone how Gavin and the other devs must feel. It's remarkable that Meni was the first person to notice and bring it to the attention of the forum after all this time, and even then it took your post for what he actually said to sink in.

Re: donations, I sent both you and the OP a BTC after applying your patch. Fortunately for Meni it took two tries for it to be obvious that the patch worked...

[Hal]

I felt bad about losing that donation address, particularly after elux very generously donated a whole bitcoin. I found a wallet on a backup that had the key, and so I was able to retrieve the funds. Again, thanks very much!

[Sergio_Demian_Lerner]

I'm proud of myself    because I saw this kind of bug coming. I posted this line on November 6, 2012 in my blog (bitslog):

"The (pseudo) anonymization property of Bitcoin is the easiest property to be lost while modifying the code, since the related code is not encapsulated in a certain class or file, but spread all over the code."

[keystroke]

I'm proud of myself    because I see this kind of bug coming. I posted this line on November 6, 2012 in my blog (bitslog):

"The (pseudo) anonymization property of Bitcoin is the easiest property to be lost while modifying the code, since the related code is not encapsulated in a certain class or file, but spread all over the code."

Good call Sergio

[molecular]

bitcoin-qt tries to randomize the position of the change output, but I believe the code has a flaw:

// Insert change txn at random position:
vector<CTxOut>::iterator position = wtxNew.vout.begin()+GetRandInt(wtxNew.vout.size());
wtxNew.vout.insert(position, CTxOut(nChange, scriptChange));

The problem is that size() is one in the common case of one payee, so GetRandInt will always return 0.The change ends up in the first output.

I think it should be size()+1.

Exploiting this bug I made a chart showing transaction volume of output #1 only: [CHART] Bitcoin Actual Transaction Volume? (using "change is never last" bug)

[zebedee]

bitcoin-qt tries to randomize the position of the change output, but I believe the code has a flaw:

// Insert change txn at random position:
vector<CTxOut>::iterator position = wtxNew.vout.begin()+GetRandInt(wtxNew.vout.size());
wtxNew.vout.insert(position, CTxOut(nChange, scriptChange));

The problem is that size() is one in the common case of one payee, so GetRandInt will always return 0.The change ends up in the first output.

I think it should be size()+1.

Exploiting this bug I made a chart showing transaction volume of output #1 only: [CHART] Bitcoin Actual Transaction Volume? (using "change is never last" bug)

Electrum had the opposite behaviour though - it always sent the change as the last output (and as currently exists can only do single-destination transactions, so the change was always the second output if there was change).  So guessing change still means guessing what the client used to send the transaction was, which helps anonymity a bit from the date electrum was released.

So I can't agree with you that your results are meaningful.

The most recent 1.6.2 release of Electrum randomizes the change output.

Also, I know some people deliberately send transactions with excess precision to the real output to make the change output have less precision and look like it isn't change.

I really think it's near-impossible to reliably guess the change output if it's not a 0.01xxx amount.

[molecular]

bitcoin-qt tries to randomize the position of the change output, but I believe the code has a flaw:

// Insert change txn at random position:
vector<CTxOut>::iterator position = wtxNew.vout.begin()+GetRandInt(wtxNew.vout.size());
wtxNew.vout.insert(position, CTxOut(nChange, scriptChange));

The problem is that size() is one in the common case of one payee, so GetRandInt will always return 0.The change ends up in the first output.

I think it should be size()+1.

Exploiting this bug I made a chart showing transaction volume of output #1 only: [CHART] Bitcoin Actual Transaction Volume? (using "change is never last" bug)

Electrum had the opposite behaviour though - it always sent the change as the last output (and as currently exists can only do single-destination transactions, so the change was always the second output if there was change).  So guessing change still means guessing what the client used to send the transaction was, which helps anonymity a bit from the date electrum was released.

So I can't agree with you that your results are meaningful.

The most recent 1.6.2 release of Electrum randomizes the change output.

Also, I know some people deliberately send transactions with excess precision to the real output to make the change output have less precision and look like it isn't change.

I really think it's near-impossible to reliably guess the change output if it's not a 0.01xxx amount.

Thanks for pointing out the electrum behavior.

There could be many useful heuristics which, especially when taken together, might yield good results. I'm not going to attempt any such thing and just agree with you that it can't reliably be done.