Bitcoin Forum
December 10, 2023, 08:35:31 AM *
News: Latest Bitcoin Core release: 26.0 [Torrent]
 
  Home Help Search Login Register More  
  Show Posts
Pages: [1]
1  Bitcoin / Development & Technical Discussion / [RFD] Coin selection algorithm and anonymity on: April 08, 2011, 03:09:47 AM
    Abstract
    The transaction creation algorithm is not optimized for anonymity. It leaks information which could potentially be used to track money flowing through the system. While this may not be of concern to some individuals, it is of concern to others. In order to maximize anonymity for those who wish it, the behaviour of the transaction creation in the standard client should be biased as much as possible towards anonymity. This biasing can easily be accomplished without incurring any extra transaction fees.

    The Problem
    One of Bitcoin's properties is its ability to be anonymous. This ability is not perfect, but it is there. However, the current implementation allows enough side-channel information leakage to make it less difficult for someone to track the flow of cash through various transfers. Closing these side channels may not stop a determined analyst, especially if they have sufficient computing resources, but it will certainly make their job harder. To make the tracker's job harder, we need to minimize the amount of information that allows the tracker to draw an association between two bitcoin addresses.

    The primary problem with the current software is the coin selection algorithm (by "coin" I mean a previous transaction output, i.e. vin[x].prevout. I will sometimes use the terms "coin" and "address" interchangeably). By the way, transaction fees do not affect this discussion, and are assumed to be included in the "payment amount" - the amount of Bitcoins being transferred from one person to another.

    The selection algorithm, which I call the "best fit" algorithm, boils down to:
    • If there is a coin which exactly matches the payment amount, then use it
    • Otherwise, find the coin (if any) which exceeds the payment amount by the least amount; i.e. if the payment is 10BTC and you have an 11BTC coin and a 15BTC coin, use the 11BTC coin
    • Otherwise, find the best combination of coins which sums closest to the payment amount.
    The selection algorithm makes it a little easier for someone to track the ownership of a given coin, which could allow the tracker to link two transactions to a given individual.

    Rule 1 is easy. The coin goes from address A to address B. Following this transaction is trivial.

    Rule 2 is a little more difficult, but not much. The standard client doesn't allow a single payment to multiple recipients, therefore one of the two outputs (the change) must be controlled by the same person who controls address A. The transaction generation routine mitigates this somewhat by randomly selecting whether the change goes into vout[0] or vout[1]. But we know (and therefore the tracker also knows) that the client will try to choose a coin which comes as close as possible in value to the payment, therefore it's very likely that the output with the lesser value is the change, and the output with the greater value is the payment. The greater the difference between the output values, the more this is likely. It's still a guess, of course.

    Examples (output addresses are O1 and O2, input addresses are A, B, C, etc.):
    A=4, O1=3, O2=1: O2 is likely (but not guaranteed) the payment. Therefore O1 is likely controlled by the sender, and O2 is likely controlled by the recipient.
    A=100, O1=99, O2=1: Again, O1 is likely (but still not guaranteed) the payment
    A=10, O1=4, O2=6:  Since O1 and O2 are close together, either one is likely the payment.
    A=10, O1=5, O2=5: Impossible to tell which is the payment and which is the change.

    Rule 3 is trivial. One of the outputs will have a value greater than any individual input coin, and the other output will have a value smaller than any individual coin. The output coin that has the smaller value is the change, and the output coin with the larger value is the payment. Unlike rule 2, that property is guaranteed, and no assumptions or guesses are necessary.
    Examples:
    A=2, B=3, O1=4, O2=1: O1 is the payment, O2 is the change. If the payment were 1BTC, then coin B is not needed at all for the transaction.
    A=2, B=2, C=3, O1=1, O2=6: O2 is the payment, O1 is the change. As in the first example, if the payment were 1BTC, then any one of the inputs would satisfy the payment and the other two would not be included.
    A=?, B=?; O1=4, O2=4: This cannot happen. If it did, one of the two input coins would have to be greater than or equal to the payment amount, so the other one would not be included.


    Potential Coin Selection Algorithms
    A tracker knows that all the input coins to a transaction are controlled by a single person (except under unusual situations not covered by the standard client). Therefore, transactions should use as few inputs as possible.

    Transactions with a single output give away who received the money (it's very unlikely you'll make a payment to yourself).

    Randomizing which output is the payment and which is the change is good, so keep that.

    The goal is to make it difficult for a tracker to determine which output is the payment, and which is the change.

    Keeping those principles in mind, I propose the following algorithms:

    1) Select a coin which is exactly twice the value of the payment
    This makes the two outputs identical, making it impossible to guess which is the payment and which is the change. Variations: select two or more coins that total exactly twice the payment amount; select one coin which is approximately twice the payment amount (this will result in two outputs which are close in value, and as shown above you cannot reliably guess which is the payment)

    2) Select two coins such that either (a) the value of each input is less than the payment amount and sums to greater than (but NOT equal to) the payment amount, or (b) the value of each input is greater than the payment amount

    Example:
    A=4, B=2, O1=5, O2=1

    A tracker looking at this transaction cannot tell if it satisfies condition (a) or condition (b), therefore they cannot determine which is the payment and which is the change. For condition (a), O1 is the payment, and for condition (b) O2 is the payment.

    3) Select two coins: one whose value exactly matches the payment, and another coin at random.
    Example:
    A=5, B=2; O1=5, O2=2

    It's rather obvious what we're doing here, but since we (and the tracker) know the payment and change are randomized, a tracker cannot know which is the payment and which is the change.

    4) A special variation on (1) (I call this one the "In yo face!" selection): Select multiple coins adding to more than the payment amount, and if possible ensure at least one coin is redundant.
    Example:
    A=2, B=3, C=1, D=1, E=2, O1=4, O2=5

    It's clear from examining this transaction that several combinations of the coins could satisfy either O1 or O2, so the tracker cannot tell which is the payment and which is the change. Note that this algorithm, unlike the others, is guaranteed to find a set of coins that can be used.

    Important considerations
    The transaction creation function must be able to use any of the algorithms above. The specific algorithm must be chosen randomly. The randomness can be weighted towards algorithms 1 and 2.

    The transactions that are generated are unlikely to incur any transaction fees greater than they would normally. None of these algorithms chooses excessively large numbers of coins, thus there is no additional cost to the user.

    The current algorithm can potentially loop 1000 times seeking the best combination of coins to come closest to the payment amount. These algorithms eliminate that overhead.

    It is important that the default behaviour of the Bitcoin client is geared towards anonymity. In order for anonymity to succeed, it must be difficult or impossible to distinguish between a transaction generated by someone seeking anonymity, and a transaction generated by someone who doesn't care about anonymity. If the random algorithm selection is used only by those seeking anonymity, then the tracker just needs to look for transactions that don't fit the "best fit" algorithm.

    (Minor edits to clean up formatting)
    2  Bitcoin / Development & Technical Discussion / [Pull] Rework debug logging on: April 06, 2011, 12:45:25 AM
    Following sipa's example here Smiley

    The pull request for revamped debug logging has been open for a few weeks now, with very little discussion on it. I'd like to have some discussion here, in the hopes of having it pulled.

    The Problem
    The debug log file can grow very quickly. If you are looking for something in particular while debugging, you have to sift through hundreds of lines of debug output that do not apply to the problem at hand.

    The Patch
    The patch introduces a new function, OutputLogMessageF. This function contains the functionality in the existing OutputDebugStringF. OutputLogMessageF adds two new parameters:

    - a value indicating the context of the message (such as transactions, IRC, etc.)
    - the severity of the message (error, warning, info, etc.)

    The existing OutputDebugStringF function forwards its call to OutputLogMessageF, using parameters to indicate All contexts, severity Warning.

    Several functions have been added to support command-line configuration of logging.

    Compatibility
    Existing code does not have to change in order to use the logging. It can be migrated from the existing 'printf' macro to the function call as developers work on a particular section of code.

    3  Bitcoin / Development & Technical Discussion / [RFD] All classes which use IMPLEMENT_SERIALIZE should check nVersion on reading on: March 21, 2011, 12:33:18 AM
    Sipa's recent patch to the wallet (for tracking partially spent coins) got me thinking about serialization and versioning issues.

    Right now, few (if any) of the classes which use IMPLEMENT_SERIALIZE check the value of nVersion when reading. I propose that we should add that check to all classes, now.

    My reasoning is: if we wait to introduce the version check until it's needed, then we have to either make the change backwards-compatible (which, if you have any experience with legacy software you will know that backwards compatibility is an unrealistic goal in the long term), hope that older clients don't break, or hope that people upgrade quickly enough to take advantage of the new feature/fix/whatever.

    We aren't a big corporation, which can push out a new version whether people want it or not. Some people may wait months or even years before updating their clients. So, if we ensure that the clients check versions now, then if we do introduce a backwards-incompatible change, users can be immediately notified that they have to upgrade the client.

    Which brings up a side issue of how to notify users. In the GUI, we can pop up a message box. But what about the daeamon version? Is it sufficient to log a message and refuse to load the object?
    4  Bitcoin / Development & Technical Discussion / Unit tests? on: March 08, 2011, 04:28:53 AM
    Hi,

    Are there any unit tests, or testbeds of any kind, for Bitcoin?
    5  Bitcoin / Bitcoin Technical Support / Problems compiling wxWidgets on Mac OSX Snow Leopard on: March 08, 2011, 03:42:07 AM
    Hi,

    I'm trying to build from source on OSX. I've followed the instructions in build-osx.txt, and everything's gone well up to the wxWidget build.

    I'm getting the following errors:
    ../src/osx/cocoa/evtloop.mm: In function ‘NSUInteger CalculateNSEventMaskFromEventCategory(wxEventCategory)’:
    ../src/osx/cocoa/evtloop.mm:78: error: ‘NSEventMaskGesture’ was not declared in this scope
    ../src/osx/cocoa/evtloop.mm:79: error: ‘NSEventMaskMagnify’ was not declared in this scope
    ../src/osx/cocoa/evtloop.mm:80: error: ‘NSEventMaskSwipe’ was not declared in this scope
    ../src/osx/cocoa/evtloop.mm:81: error: ‘NSEventMaskRotate’ was not declared in this scope
    ../src/osx/cocoa/evtloop.mm:82: error: ‘NSEventMaskBeginGesture’ was not declared in this scope
    ../src/osx/cocoa/evtloop.mm:83: error: ‘NSEventMaskEndGesture’ was not declared in this scope

    repeated a few times in other functions.

    I'm much more experienced at Windows development than Mac development, so any suggestions would be greatly appreciated.
    6  Economy / Economics / Will deflationary model be a hindrance to general acceptance of Bitcoin? on: March 06, 2011, 05:58:19 AM
    Hi,

    I think I have a pretty good handle on the economic model of Bitcoin. As I understand it, as demand for BTC increases, the value of BTCs increases, pushing prices etc. down. Sounds reasonable to me. I think.

    In the inflationary model, when prices go up too much John Q. Factoryworker goes to his boss (or his union) and says that prices have gone up, he needs a raise. Eventually (hopefully) he gets a raise, and the company raises its prices to cover its increases in expenses, thus triggering another round of inflation and economic growth. Everybody's happy.

    In the deflationary model, prices will drop, which means the companies have fewer bitcoins to hand out to employees, so their salaries go down, so they barter down the amount they spend, thus triggering another round of deflation and everyone is happy.

    Except - how do you convince the majority of people, who have no clue how the economy works, that getting pay cuts is... well, maybe not "good" but is certainly normal? And unless you can convince people to start using Bitcoins in every day transactions, I don't see how BTC are going to be accepted very much. And if they're not going to be used in every day transactions, what's the point?
    Pages: [1]
    Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!