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