Bitcoin Forum
December 09, 2016, 03:58:24 AM *
News: Latest stable version of Bitcoin Core: 0.13.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: How does the bitcoin client choose sendfrom addresses?  (Read 1208 times)
SgtSpike
Legendary
*
Offline Offline

Activity: 1344



View Profile
July 16, 2011, 01:18:07 AM
 #1

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?
1481255904
Hero Member
*
Offline Offline

Posts: 1481255904

View Profile Personal Message (Offline)

Ignore
1481255904
Reply with quote  #2

1481255904
Report to moderator
Satoshi is no god. He did not come down from the mountain with 10 golden rules engraved in stone for no one to question.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1481255904
Hero Member
*
Offline Offline

Posts: 1481255904

View Profile Personal Message (Offline)

Ignore
1481255904
Reply with quote  #2

1481255904
Report to moderator
Stephen Gornick
Legendary
*
Offline Offline

Activity: 2002



View Profile
July 16, 2011, 02:48:14 AM
 #2

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
Legendary
*
Offline Offline

Activity: 1344



View Profile
July 16, 2011, 03:13:43 AM
 #3

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
Legendary
*
Offline Offline

Activity: 1708



View Profile
July 16, 2011, 03:14:40 AM
 #4

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)

Please comment, critique, criticize or ridicule BIP 2112: https://bitcointalk.org/index.php?topic=54382.0
Long-term mining prognosis: https://bitcointalk.org/index.php?topic=91101.0
2112
Legendary
*
Offline Offline

Activity: 1708



View Profile
July 16, 2011, 03:17:02 AM
 #5

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

Please comment, critique, criticize or ridicule BIP 2112: https://bitcointalk.org/index.php?topic=54382.0
Long-term mining prognosis: https://bitcointalk.org/index.php?topic=91101.0
SgtSpike
Legendary
*
Offline Offline

Activity: 1344



View Profile
July 16, 2011, 03:46:28 AM
 #6

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
Legendary
*
Offline Offline

Activity: 1708



View Profile
July 16, 2011, 04:53:00 AM
 #7

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.

Please comment, critique, criticize or ridicule BIP 2112: https://bitcointalk.org/index.php?topic=54382.0
Long-term mining prognosis: https://bitcointalk.org/index.php?topic=91101.0
SgtSpike
Legendary
*
Offline Offline

Activity: 1344



View Profile
July 16, 2011, 04:56:00 AM
 #8

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
Legendary
*
Offline Offline

Activity: 1708



View Profile
July 16, 2011, 05:03:52 AM
 #9

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.

Please comment, critique, criticize or ridicule BIP 2112: https://bitcointalk.org/index.php?topic=54382.0
Long-term mining prognosis: https://bitcointalk.org/index.php?topic=91101.0
Pieter Wuille
Legendary
*
Offline Offline

Activity: 1036


View Profile WWW
July 16, 2011, 09:34:37 AM
 #10

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.

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
SgtSpike
Legendary
*
Offline Offline

Activity: 1344



View Profile
July 16, 2011, 06:52:05 PM
 #11

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
Administrator
Legendary
*
Offline Offline

Activity: 2506


View Profile
July 17, 2011, 09:39:50 PM
 #12

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).

1NXYoJ5xU91Jp83XfVMHwwTUyZFK64BoAD
SgtSpike
Legendary
*
Offline Offline

Activity: 1344



View Profile
July 17, 2011, 10:24:12 PM
 #13

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
Administrator
Legendary
*
Offline Offline

Activity: 2506


View Profile
July 18, 2011, 12:55:22 AM
 #14

Right.

1NXYoJ5xU91Jp83XfVMHwwTUyZFK64BoAD
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!