"Is "Chaum's design" the one where merchants are assigned identities, payment is offline but specific to the merchant's identity, and a double spender's identity is revealed if a coin has been spent at two different merchants?"

More or less; the important concept is that a double-spending attack will not only be detected, but that it will both reveal the identity of the attacker and allow the attacker to be blacklisted. It is not necessary to differentiate "merchants" and "spenders;" re-spending a transferred coin in an offline protocol is possible (without sacrificing the "double-spending reveals the attacker's identity" property).

"Bitcoin provides a property none of those other systems provided - freedom from a trusted "issuer"/bank/etc"

Bitcoin may do this, but it does so by sacrificing rigorous security and offline payments. Even if we assume that a monetary system without any authorities makes sense (I am doubtful about that), a system where the attacker's effort is linear in the system's parameters is not a system that can be trusted with any significant amount of money.

"What I meant to say is that being built from those primitives, it could be proved as secure as those primitives"

Except that Bitcoin is not a signature system, nor is it a hash function. The only statement that can really be made is this, "Bitcoin's security is dependent on the use of a secure signature system and a secure hash function." Again, look at the email robustness example; a system built from secure cryptographic primitives can still fail to meet its security goal.

"When we give up trusted authorities (and specific "parties" necessarily created by some trusted authority), what remains? What differentiates "the majority" ? One of the few things I see is computing power."

Parties are not created by authorities; parties are what communicate in a distributed system. In the commonly used model, the attacker is allowed to control some number of parties and coordinate their actions; any party, honest or malicious, can scale their computation by some polynomial of the system parameters.

In the case of Bitcoin, parties can enter or leave the computation at any time, without having to send messages to the other parties. That introduces an entirely different challenge, since the attacker can keep adding parties to the system, eventually controlling a majority of whatever capability the parties have. That is not to say that some notion of security cannot be achieved; rather, it means that any notion of security based on a "majority" of anything cannot be achieved without some way to restrict the number of parties the adversary can enter in the system.

The anonymous remailer system faces a similar problem: an attacker can create as many remailers as he wants. In the case of anonymous remailers, however, it is OK for the attacker to control a majority of parties, since it only takes one honest remailer for the system to be secure (i.e. for messages to be anonymized). That should be the goal of Bitcoin: the ability to prevent forgery and double spending as long as some honest parties remain in the system (assuming such a thing is even possible without a central authority; it could be the case that no such protocol can exist).

"Sybil attacks have been defined away, as they depend on some notion of "parties"."

I think the parties in Bitcoin are the people who use it. After all, the point of Bitcoin is to facilitate monetary transactions between its users.

"The "honest parties" wishful-thinking has vanished, leaving only "majority of computation" as the network authority"

No, there is still an issue of "honest parties" versus "malicious parties." Honest parties in Bitcoin are people who are willing to follow the rules and who are not trying to double spend their money or spend money they did not mine/receive. Malicious parties are those who are trying to break the rules by whatever means are available to them. The fact that the majority of computational resources is what decides the validity of the transactions just means that a malicious party needs to collect the majority of computational resources; this is not infeasible, and it is only somewhat impractical (and only really impractical for individual people).

"Of course the merits of this security model are still up for debate, but it seems to mostly work."

It seems to mostly work because nobody with the resources needed to carry out the known attacks cares enough about Bitcoin to do so. The NSA is too busy spying on people to worry about Bitcoin, and companies with large numbers of computers like Amazon or Google are busy using those computers to run their businesses.

This does bring up an interesting point, however: an attacker would only really need such large computing resources during the duration of the attack. The hardware would still be useful after the attack, and the attacker might simply sell it or use it for some profitable purpose. I think the only thing that really prevents fraudsters from doing this is the lack of capital/credit needed to procure the equipment in the first place (let's put it this way: if you were running a bank, would you give a billion dollar loan to someone whose business plan was "defrauding Bitcoin users?").

"Erm, given that the fork was a rare event, it actually shows that Bitcoin is mostly solving the problem, just not perfectly."

The problem is that the fork was caused by parties failing to adhere to the protocol. If Bitcoin is not resilient to parties failing to follow the protocol due to a bug, then it is also not resilient to parties that do not follow the protocol because of a coordinated attack. In other words, Bitcoin is not secure against malicious parties (which are defined as parties that do not faithfully follow the protocol).

> Bitcoin may do this, but it does so by sacrificing rigorous security and offline payments

Both seem like definite hard tradeoffs to me. Offline transactions imply there is some ultimate real-world identity that can be punished for fraud. By "sacrificing rigorous security", I assume you're referring to the majority of CPU power controlling the network. If we give up having a central authority and verified identities, we necessitate some measure of "majority of power" in the system (although it doesn't necessarily have to be CPU).

> a system built from secure cryptographic primitives can still fail to meet its security goal

Sure, but one can formalize the properties of Bitcoin, and could prove that it indeed meets those properties.

One of these properties is "network is controlled by the majority of computing power". I'm not saying this is a universal good thing or ultimate solution. What I am saying is that this property is what provides independence from a central authority, which is possibly what has enabled Bitcoin to actually be adopted.

> Parties are not created by authorities; parties are what communicate in a distributed system

No, "parties" are a convenient abstraction for distributed systems papers in that they bound the pervasiveness of an attacker. The reader intuitively understands them as some notion of identity (IP address, digital certificate, etc), but here we have no luxury. As you later touch upon, once you get rid of identities, a single attacker can create an unlimited number of parties.

I think general MPC has only been proved secure if a majority of parties are honest. Bitcoin is substituting 'parties' with computing power, for precisely the reason you describe. Would we say MPC is insecure because the effort required to attack it (number of malicious parties to establish) is linear in the size of the system (total number of parties)?

I understand this isn't the best security guarantee, but you seem to be having an allergic reaction to it. Complexity theoretic guarantees are useful because they work. However, most real-world power balances are close to linear.

I guess my main point has been that Bitcoin provides a property (authority-independence) that previous ecash papers have not. Its guarantees of this aren't the strongest, but if we're to improve it we must recognize the problem it's solving.

Maybe there's another way of implementing authority-independence that doesn't succumb to something as simplistic as computing power. As it is, it seems that Bitcoin will continue to centralize as miners further specialize and the requirements to be "on the network" (versus transacting through an agent) grow.

"Sure, but one can formalize the properties of Bitcoin, and could prove that it indeed meets those properties."

This seems a bit backwards. Rather than formalizing the properties of Bitcoin, it seems that we should be formalizing the goal of Bitcoin i.e. the properties we want, and then prove that Bitcoin satisfies those properties (if it does actually satisfy them). I think that such a formalization would require a formalization of the entire Bitcoin concept of money, which would probably be beneficial in and of itself.

"If we give up having a central authority and verified identities, we necessitate some measure of "majority of power" in the system"

I think that really depends on your notion of money. If you are like me, you believe that money has value because of its utility: fiat currencies have utility that is defined by a legal system (taxes, debt law, torts, etc.), but one could imagine something else. Suppose, for example, that you had a digital cash system in which the money was redeemable for CPU time in a secure outsourcing system; this could potentially be decentralized. Controlling more computing resources would not give an attacker greater power over the network, but would allow a party to receive more payments (because they are basically selling access to their CPU). It is of course possible that such a system could not be securely realized for technical reasons.

"One of these properties is "network is controlled by the majority of computing power"."

This is not a very precise definition, at least not in the cryptographic sense. What is the formal definition of computing power here -- what is the computation model? It would be very hard to prove that a system has this property in a rigorous way.

On the other hand, in the system I described above, you could formalize the measure of how much work a node did (and how much payment was received) by using circuit families as the computation model and the number of gates evaluated as the measure of work. This sort of abstraction would allow a rigorous proof of various properties of the protocol; e.g. maybe you want to show that the payment a party receives will be some proportion of the number of gates the party evaluates.

"As you later touch upon, once you get rid of identities, a single attacker can create an unlimited number of parties."

Not unlimited; the attacker's ability to enter parties into the system is bounded by the computing power of the attacker. If the attacker can only scale their computation by some polynomial in the parameters of the system, the attacker can only enter some polynomial number of parties. If the protocol is secure as long as there is one honest party, the attacker would not be able to win even under such a scenario.

"I think general MPC has only been proved secure if a majority of parties are honest."

It is not really that simple. For example:

http://eprint.iacr.org/2012/441.pdf

There is a protocol that is secure even if only one party is honest. The problem here is that "secure" does not have a single meaning in MPC. There are various adversary models: an adversary might only be able to choose which parties to corrupt before the protocol runs, or might be able to corrupt parties while the protocol is running; he might be allowed to adapt the attack between the computation rounds and the output round, as in that paper; he might be allowed to compose protocols together in arbitrary ways; etc. Some protocols require a setup phase or an authority, some are standalone (as in the paper), some require a broadcast channel, and so forth.

> you had a digital cash system in which the money was redeemable for CPU time in a secure outsourcing system ... It is of course possible that such a system could not be securely realized for technical reasons

I don't see how it could be possible to design a system were useful CPU work done for others was turned into tokens, as one could simply create a whole bunch of fake work. The fundamental question is who is the counterparty to the tokens? If it's the entity selling CPU time, then you're dealing with a gift card system that doesn't scale to a real currency. If it's not, then you're no longer describing the payment system but have switched to describing an application of it.

> What is the formal definition of computing power here

Clearly it's just the ability to calculate SHA2 preimages. If you want something better, you've got to come up with that formality and an implementation to show that it is practical.

I'm having a hard time responding because it seems like you want to postulate systems with these nice-sounding properties, but it seems apparent to me that you'd never be able to connect them with proofs to make a system. You simply won't be able to build proofs of work for something as simplistic as "number of gates evaluated" (and if you're talking about 'gates' in MPC, you're really just talking about eg group operations).

> If the attacker can only scale their computation by some polynomial in the parameters of the system, the attacker can only enter some polynomial number of parties

What you're describing here is Bitcoin. You've just been spoiled with attackers usually needing exponential resources. As I said, your formalities are misleading you - crypto algorithms may work this way, but not everything does! An algorithm cannot discern good guys from bad guys, meaning they're both on equal footing and the best we can do is have a power balance.