How does the bitcoin client choose sendfrom addresses?

[SgtSpike]

Last I heard, it always chose the addresses with the "newest" coins - i.e., the address that had received coins in the most recent block.  Can anyone confirm/deny this?

[Stephen Gornick]

Last I heard, it always chose the addresses with the "newest" coins - i.e., the address that had received coins in the most recent block.  Can anyone confirm/deny this?

Looking at some transactions from my wallet that behavior does not seem to jive with what occurred.

[edit: Looks like this is done in SelectCoins() and attempts to do a "stochastic approximation" based on values, and does not consider newer vs. older:
https://github.com/bitcoin/bitcoin/blob/master/src/wallet.cpp ]

[SgtSpike]

I'm having a bit of difficulty understanding the code...  I seem to remember a written-up bit in the wiki or on a website, but I can't seem to find it anymore.  Can you tell me more about the "stochastic approximation"?

[2112]

It actually does 3 stochastic passes:

Code:

bool CWallet::SelectCoins(int64 nTargetValue, set<pair<const CWalletTx*,unsigned int> >& setCoinsRet, int64& nValueRet) const
{
   return (SelectCoinsMinConf(nTargetValue, 1, 6, setCoinsRet, nValueRet) ||
           SelectCoinsMinConf(nTargetValue, 1, 1, setCoinsRet, nValueRet) ||
           SelectCoinsMinConf(nTargetValue, 0, 1, setCoinsRet, nValueRet));
}

The important numeric arguments are [mine] & [theirs] and represent minimum age of the coins. Coins are marked [mine] if their were sent from another account in the same wallet (shown as "Payment to self" in the transaction list)

[2112]

"stochastic approximation" means an approximate solution to an one-dimensional knapsack problem. Wikipedia has a good intro: http://en.wikipedia.org/wiki/Knapsack_problem

[SgtSpike]

So what is trying to be optimized with that algorithm?  Is it trying to optimize payments to have as low of fees as possible?  In reference to the knapsack problem, what is the "weight" for bitcoin?

[2112]

The "weight" of the coin is its value, unless the coin doesn't meet the selection criteria, in which case it is presumed non-existent.

The whole knapsack algorithm is somewhat inverted from the textbook. In the textbook one minimizes empty space in knapsack. In bitcoin one minimizes change required. The goal is the same, except that in a textbook you approach it from below and in bitcoin from above.

[SgtSpike]

The "weight" of the coin is its value, unless the coin doesn't meet the selection criteria, in which case it is presumed non-existent.

The whole knapsack algorithm is somewhat inverted from the textbook. In the textbook one minimizes empty space in knapsack. In bitcoin one minimizes change required. The goal is the same, except that in a textbook you approach it from below and in bitcoin from above.

Ahhh, ok.  So it'll select from the various addresses based on which combination of addresses give the least change?  Is that the only priority?

[2112]

Not the "only" priority. There are three passes over the wallet (as shown above). So there's a degree of priority given to the age of the coins, but in a very non-linear way.

[Pieter Wuille]

It first tries to find a combination of input coins using only coins with 6 confirmations. If that fails, it tries using coins with at least one confirmations. If that also fails, it tries again not requireing any confirmation from coins created by yourself (i.e. change, or send-to-self).

Within each pass, it tries to minimize the change approximately.

Also, when using sendfrom, all coins in your wallet are always considered, as coins never belong to a specific account.

[SgtSpike]

Peter, thanks - that makes a lot more sense regarding the three calls to the function now.

What would cause it to fail?  If there's not enough coins with more than 6 confirmations?  Or if those coins would cause too high of a transaction fee?

[theymos]

What would cause it to fail?  If there's not enough coins with more than 6 confirmations?  Or if those coins would cause too high of a transaction fee?

It only fails if there's not enough BTC. SelectCoins doesn't care about fees or transaction size (though it probably should).

[SgtSpike]

What would cause it to fail?  If there's not enough coins with more than 6 confirmations?  Or if those coins would cause too high of a transaction fee?

It only fails if there's not enough BTC. SelectCoins doesn't care about fees or transaction size (though it probably should).

So the basic process is:

if total coins with more than 6 conf > the amount to be sent, then find combination of addresses that results in the least amount of change.
else if total coins with more than 1 conf > the amount to be sent, then find combination of addresses that results in the least amount of change.
else if total coins with more than 1 conf or 0 conf if sent to self > the amount to be sent, then find combination of addresses that results in the least amount of change.
else don't send coins because you don't have enough!

Someone correct me if I am wrong.  Thanks for the explanation though everyone who contributed!

[theymos]

Right.