|
Title: How does the bitcoin client choose sendfrom addresses? Post by: SgtSpike on July 16, 2011, 01:18:07 AM 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?
Title: Re: How does the bitcoin client choose sendfrom addresses? Post by: Stephen Gornick on July 16, 2011, 02:48:14 AM 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 ] Title: Re: How does the bitcoin client choose sendfrom addresses? Post by: SgtSpike on July 16, 2011, 03:13:43 AM 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"?
Title: Re: How does the bitcoin client choose sendfrom addresses? Post by: 2112 on July 16, 2011, 03:14:40 AM It actually does 3 stochastic passes:
Code: bool CWallet::SelectCoins(int64 nTargetValue, set<pair<const CWalletTx*,unsigned int> >& setCoinsRet, int64& nValueRet) const Title: Re: How does the bitcoin client choose sendfrom addresses? Post by: 2112 on July 16, 2011, 03:17:02 AM "stochastic approximation" means an approximate solution to an one-dimensional knapsack problem. Wikipedia has a good intro: http://en.wikipedia.org/wiki/Knapsack_problem
Title: Re: How does the bitcoin client choose sendfrom addresses? Post by: SgtSpike on July 16, 2011, 03:46:28 AM 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?
Title: Re: How does the bitcoin client choose sendfrom addresses? Post by: 2112 on July 16, 2011, 04:53:00 AM 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. Title: Re: How does the bitcoin client choose sendfrom addresses? Post by: SgtSpike on July 16, 2011, 04:56:00 AM 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. 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?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. Title: Re: How does the bitcoin client choose sendfrom addresses? Post by: 2112 on July 16, 2011, 05:03:52 AM 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.
Title: Re: How does the bitcoin client choose sendfrom addresses? Post by: Pieter Wuille on July 16, 2011, 09:34:37 AM 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. Title: Re: How does the bitcoin client choose sendfrom addresses? Post by: SgtSpike on July 16, 2011, 06:52:05 PM 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? Title: Re: How does the bitcoin client choose sendfrom addresses? Post by: theymos on July 17, 2011, 09:39:50 PM 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). Title: Re: How does the bitcoin client choose sendfrom addresses? Post by: SgtSpike on July 17, 2011, 10:24:12 PM 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). 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! Title: Re: How does the bitcoin client choose sendfrom addresses? Post by: theymos on July 18, 2011, 12:55:22 AM Right.
|