Is there mathematical proof?

[caspar.holzinger]

Is there mathematical proof that the double-spending problem can be solved only by a trusted party, be it network majority, central trusted party, something in between like a trustweb, or even directly trusting the sender of the money? (Yes, if you trust the sender, there is no need for a third party.)

cf. http://en.wikipedia.org/wiki/Double-spending

From intuition, it is quite clear that without trust, the double-spending problem can't be solved. But intuition can often mislead. For that reason: Is there mathematical proof that trust is an implicit requirement for solving the double-spending problem?

[t3a]

Well it isn't mathematical so I don't see how there could be a mathematical proof.

If you go by the assumption that a person is always trying to gain value, then you either have to have some disincentive to double-spend, or make it economically difficult to double spend (require a massive amount of mining equipment to double-spend after a few confirmations).

I'm guessing you're referring to 0 confirmation double spends. There is a theoretical solution to this, which is to have a disincentive to double-spending. In this theoretical update/cryptocurrency, if a miner finds two transactions that comprise a double-spend, the miner is given the entire transaction. This makes the double-spender not want to double-spend. In addition to this, the seller could require that the buyer have a certain amount of change. For example, the transaction could give $50 to the seller, $0.01 to the miner and $50 back in change. If he attempted a double-spend, he would lose as much as the seller.

[kuverty]

Well it isn't mathematical so I don't see how there could be a mathematical proof.

If you go by the assumption that a person is always trying to gain value, then you either have to have some disincentive to double-spend, or make it economically difficult to double spend (require a massive amount of mining equipment to double-spend after a few confirmations).

I'm guessing you're referring to 0 confirmation double spends. There is a theoretical solution to this, which is to have a disincentive to double-spending. In this theoretical update/cryptocurrency, if a miner has two double-spend transactions, the miner is given the entire transaction. This makes the double-spender not want to double-spend. In addition to this, the seller could require that the buyer have a certain amount of change. For example, the transaction could give $50 to the seller, $0.01 to the miner and $50 back in change. If he attempted a double-spend, he would lose as much as the seller.

I think it might be mathematical, I thought about this earlier but I don't know what would be a suitable mathematical formulation. It didn't make much sense to me when I tried to formulate the problem, though I didn't give any serious thought to it.

[gmaxwell]

Sort of, first you have to be more specific about "the double spending problem".   Information can be copied— so long as we're not using unclonable qbits to store it (google: quantum money)... so any money based on information can be replicated to yield double spends.

There are "change the rules" kinds of solutions where you make creating a double spend have consequences (e.g. give away your private key) but ignoring those the problem of double spending is really the problem of the whole universe (including the payee) coming to an irreversible agreement about what order two events happened in.

Relativity tells us that the order you perceive events to happen in depends on your relative position in space-time with the events, another party at another location will perceive another order.

With this in mind, it seems clear to me that you cannot autonomously achieve a consensus ordering without specifying a privileged location, even with perfect knoweldge.  Of course, we don't have perfect knoweldge so the problem is even harder.

For our purpose we also want the system to be anonymous— meaning the participants are unknown in advance and can come and go ant every time— and resistant to malicious parties. This means we cannot use a consensus solution that involves asking everyone if they agree on the order (because you can't enumerate them, and even if you could— some would lie just to wedge the process), and besides, most of those have quadratic communications complexity.

What Bitcoin itself did was largely believed to be not possible— it achieved it by relaxing some of the definitions.  The anonymous requirement means that you can never have a guarantee— perhaps there are some moon nazis on the dark side of the moon with a longer chain that we'll only discover a week from now, etc.
 

[kuverty]

Sort of, first you have to be more specific about "the double spending problem".   Information can be copied— so long as we're not using unclonable qbits to store it (google: quantum money)... so any money based on information can be replicated to yield double spends.

There are "change the rules" kinds of solutions where you make creating a double spend have consequences (e.g. give away your private key) but ignoring those the problem of double spending is really the problem of the whole universe (including the payee) coming to an irreversible agreement about what order two events happened in.

Relativity tells us that the order you perceive events to happen in depends on your relative position in space-time with the events, another party at another location will perceive another order.

With this in mind, it seems clear to me that you cannot autonomously achieve a consensus ordering without specifying a privileged location, even with perfect knoweldge.  Of course, we don't have perfect knoweldge so the problem is even harder.

For our purpose we also want the system to be anonymous— meaning the participants are unknown in advance and can come and go ant every time— and resistant to malicious parties. This means we cannot use a consensus solution that involves asking everyone if they agree on the order (because you can't enumerate them, and even if you could— some would lie just to wedge the process), and besides, most of those have quadratic communications complexity.

What Bitcoin itself did was largely believed to be not possible— it achieved it by relaxing some of the definitions.  The anonymous requirement means that you can never have a guarantee— perhaps there are some moon nazis on the dark side of the moon with a longer chain that we'll only discover a week from now, etc.
 

You can copy information but that isn't all there is. Alice wants to send some information to Bob and Bob wants to make sure that he is the only one who can make use of it. I can not see why there could no be such a scheme where Alice would have surely rendered this information unusable for everyone else and so on. Although it would be nice to know how this "spending" happens. But it's 5 AM and I don't make any sense I think, I'd like to see a proper formalization of this though. I am tired but can you comment on this?

[gmaxwell]

You can copy information but that isn't all there is. Alice wants to send some information to Bob and Bob wants to make sure that he is the only one who can make use of it. I can not see why there could no be such a scheme where Alice would have surely rendered this information unusable for everyone else and so on. Although it would be nice to know how this "spending" happens. But it's 5 AM and I don't make any sense I think, I'd like to see a proper formalization of this though. I am tired but can you comment on this?

Please read my message again. There are problems both with defining "everyone else" and, ignoring that, getting them into agreement over which of multiple spends was the bad one. I speak to both of these things.

[kuverty]

You can copy information but that isn't all there is. Alice wants to send some information to Bob and Bob wants to make sure that he is the only one who can make use of it. I can not see why there could no be such a scheme where Alice would have surely rendered this information unusable for everyone else and so on. Although it would be nice to know how this "spending" happens. But it's 5 AM and I don't make any sense I think, I'd like to see a proper formalization of this though. I am tired but can you comment on this?

Please read my message again. There are problems both with defining "everyone else" and, ignoring that, getting them into agreement over which of multiple spends was the bad one. I speak to both of these things.

Everyone else is simple, for Alice and Bob it's... everyone else. I though that maybe it would be possible to make sure, somehow, that Alice made the information only to Bob and not anyone else... would it be impossible for there to exist such a system that Alice could convince Bob he has the right to something, and only him? A proof that all the other possibilities are thrown out, that something is being released that  only Bob will get use of - practically.

[Dabs]

This is not the correct answer, just my contribution about the "math".

1. Spend.
2. Wait for 1000 nodes to see it. Probably about 30 seconds.
3. Even better, wait for a block.

So, I think your initial idea about network majority is part of your math. Also assuming the spend is properly formed and has at least a minimum fee (which sort of guarantees that it will be included in a block soon.)

Free transactions (without a fee) tend to be the ones that look suspect of actually being double-spent.

Sorry, this doesn't really answer the question, but I'm coming from the point of view as someone who is accepting payments. If I wait a bit, I'm almost sure I got it.

I usually now ask people to pay me bitcoins into a brand new address that no one else has. Once it gets a transaction (either on my client, or on block explorers), it's usually good enough for me.

[jdbtracker]

I thought it was already solved, isn't it coded in the software to not let you do that? Unless you mean people with hacked copies of a wallet, it can be pretty hard and far in between but I can imagine black market copies circulating.

[Nancarrow]

Totally OT nitpick:

Relativity tells us that the order you perceive events to happen in depends on your relative position in space-time with the events, another party at another location will perceive another order.

Only if the events are outside each other's lightcones, i.e. causally disconnected. As long as two events are separated by a timelike interval (so that an object moving slower than the speed of light could travel from one to the other), their order in time is invariant. ALL observers will agree which happened first, though they'll disagree about how much earlier it was. The only way two different observers can disagree about the order of two events is if the events are outside each other's light cones, in which case they cannot affect each other, and thank fuck for that or we'd have effects preceding causes, dogs and cats living together... mass hysteria!

[andytoshi]

You can copy information but that isn't all there is. Alice wants to send some information to Bob and Bob wants to make sure that he is the only one who can make use of it. I can not see why there could no be such a scheme where Alice would have surely rendered this information unusable for everyone else and so on. Although it would be nice to know how this "spending" happens. But it's 5 AM and I don't make any sense I think, I'd like to see a proper formalization of this though. I am tired but can you comment on this?

Please read my message again. There are problems both with defining "everyone else" and, ignoring that, getting them into agreement over which of multiple spends was the bad one. I speak to both of these things.

Everyone else is simple, for Alice and Bob it's... everyone else. I though that maybe it would be possible to make sure, somehow, that Alice made the information only to Bob and not anyone else... would it be impossible for there to exist such a system that Alice could convince Bob he has the right to something, and only him? A proof that all the other possibilities are thrown out, that something is being released that  only Bob will get use of - practically.

Let me make gmaxwell's comment a bit more concrete: suppose Bob wants to receive a payment from Alice, but Alice is conspiring with Eve to double-spend without his knowledge. Suppose there exists some spending protocol so that for any actors A and B, A can send money to B with probability p > 0 after a conversation consisting of N replies, each of which take at most t time to compute. You may suppose that all of p, N, t depend on A and B, if you like. Thus A can send money to B with probability p in time T = Nt + O(dist(A, B)), where the latter term comes from communication time.

Then Alice can send money to Bob, with probability p_B > 0 in some time T_B. (For concreteness, all times are measured in Alice's frame.) She can also send money to Eve, with probability p_E > 0, in some time T_E. As long as Eve is close (say, she and Alice are secretly the same person), T_E = Nt to a good approximation. But if Bob is far away, T_B = O(distance(Alice, Bob)), and if Bob is far enough away, Alice can spend completely to Eve before any information can be exchanged between Alice and Bob. So if Alice spends her money to Bob, but immediately after sending the last message to him, she also spends it to Eve, she has accomplished a double-spend (with probability p_Ap_B > 0), where each of Bob's and Eve's disjoint light cones see their transaction as complete but not the other. When these light cones intersect some time later there is no way to tell which of the two spends is the "real" one.

Now, this is somewhat fanciful, but if you replace the speed of light with the speed of propagation in real networks, you have a real problem. Because Alice and Eve might be on the same CPU doing this spend in L1, while Bob is on some other network, perhaps one which Alice is DOS'ing in the meantime.

(I had an even more fanciful post thought up involving Bob and Eve being in separate black holes, but it was too easy to think of simple rebuttals which missed the point :})

[N1no]

In this video its properly explained. I don't think its your mathematical explanation though...

http://www.youtube.com/watch?v=Lx9zgZCMqXE&feature=c4-overview&list=UUOGrxFj_j7PZRQM63OFCwmA

check @ 3:31 that is what you can google

[waxwing]

Everyone else is simple, for Alice and Bob it's... everyone else. I though that maybe it would be possible to make sure, somehow, that Alice made the information only to Bob and not anyone else... would it be impossible for there to exist such a system that Alice could convince Bob he has the right to something, and only him? A proof that all the other possibilities are thrown out, that something is being released that  only Bob will get use of - practically.

The part bolded is the problem solved by general crypto - how to make sure only Bob receives Alice's information, but that is not the function of money, because it leaves both Bob and Alice with the information. For money, we need Alice to lose access to the information.

That's why information can't function as money, since even with cryptography there is no way to prove that you have lost information (which is why intellectual property is a nonsensical concept - you can't own information).

In Bitcoin, there is no attempt to transfer something. Bitcoins as such do not exist. Bitcoin creates a ruleset according to which monetary balances may change.

I don't really, therefore, buy your premise that "Bitcoin solves double spend by use of network majority as trusted third party". There is no trust involved; the solution is mathematical and mathematics does not have the concept of trust, only *verifiable* truth and falsehood. That's what Bitcoin uses. A 51% attack is not a violation of trust, it is a continuation of the same ruleset. If the majority of the network says this is the correct chain, then this the correct blockchain - verifiable by all as the longest. In the extreme case the majority of miners run code with a modified protocol and then Bitcoin is no longer Bitcoin. There is no defence against that because there is no third party.

[caspar.holzinger]

It seems that most misundestood my post. Most only thought about the double spending problem in the domain of bitcoin. But my question is more general. The double-spending problem is not limited to bitcoin, but most people here only think about bitcoin when talking about double spending problem.

That is not correct, as the double spending problem is a more general one. Bitcoin has one possible solution to the double-spending problem, which is trusting the collective party which controls the majority of the network's hashing power.

As stated, there are many possible solutions to the double spending problem. Other solutions than that of bitcoin usually involve a centralized trusted party, e.g. linden dollars or the taken down liberty reserve. But all of the known solutions involve trust in some way. My question now was not about bitcoin. It was about the more general double spending problem and if there exists a mathematical proof that the double spending problem can only be solved with trust in one or the other way, or if this proof does not exist, if it might be possible to find a solution which does not involve trust.

Yes, I'm very aware of all the trivial prose intuitive explanations why trust is required. But prose explanations can mislead, while mathematical proof is guaranteed to be correct (provided there is no mistake in proof and premises).

I'm aware of them so you don't need to repeat them here, please! And I know bitcoin's solution to it extremely well, so please also don't explain bitcoin's individual solution here any more. I know it.

Finally, if you are not a maths pro, don't comment here.

[cr1776]

It seems that most misundestood my post. Most only thought about the double spending problem in the domain of bitcoin. But my question is more general. ... Finally, if you are not a maths pro, don't comment here.

Perhaps it was a problem with the OP - given this is a bitcoin forum and you didn't properly define the scope as being more general.  If you mathematically define the problem, then the question of whether or not there is a mathematical answer may become clear and it will certainly let the mathematically inclined respond.

In short, maybe expecting people to answer a non-mathematically defined problem mathematically is at the root of the answers that you got.

And if you don't want other comments, make a thread that you can moderate. :-)

[N1no]

Bitcoin uses: ecdsa (elliptic curve digital signature algorithm) + mathematical trap door

Does this help you?

[caspar.holzinger]

In short, maybe expecting people to answer a non-mathematically defined problem mathematically is at the root of the answers that you got.

You're right in this regard. Writing a question that people can read and speak out automatically makes them think that they understood it. At least something I learned through this thread.

[tl121]

Before you can get mathematical proof you need some kind of a model.  In this case, the model has to encompass distributed computation and trust.  There are computer scientists who have been working on these kinds of models as far back as the 1970's.   The major benefit of these models is to make explicit the assumptions needed to "prove" things.

Two computer scientists that come to mind are Nancy Lynch of MIT and Leslie Lamport of Microsoft Research.  If you go to their web pages you can start digging in.

Here's a Wikipedia article that may be relevant.
http://en.wikipedia.org/wiki/Consensus_%28computer_science%29

[coinrevo]

For that reason: Is there mathematical proof that trust is an implicit requirement for solving the double-spending problem?

I think such a notion of mathematical proof is not very helpful at all. I trust the other bitcoin nodes run the bitcoin source code I know. There I believe with high degree of certainy that the network will be behave in a certain way. What bitcoin as a network does is deal with probabilities. Bitcoin solves problems in the real world by using concept which are absolutely foreign to modern mathematics, viewed in the traditional way. 

[Altoidnerd]

That is not correct, as the double spending problem is a more general one....

State the general double spending problem. 

That is not correct, as the double spending problem is a more general one....if there exists a mathematical proof that the double spending problem can only be solved with trust in one or the other way, or if this proof does not exist, if it might be possible to find a solution which does not involve trust.

Yes, I'm very aware of all the trivial prose...while mathematical proof is guaranteed to be correct (provided there is no mistake in proof and premises).
Finally, if you are not a maths pro, don't comment here.

You'll need to clarify this question...you have not provided definitions for "double spend" nor for "trust".

If you define those terms your question has meaning, otherwise it is just trivial prose.