The way the Bitcoin community handled this mornings fork in the bitcoin blockchain is nothing short of incredible. This event significantly increases my confidence in the Bitcoin ecosystem to thrive even when faced with critical issues.
If only the global finance institutions had a fraction of bitcoins capacity to resolve crises with the same unconditional transparency and full cooperation with all agents in the ecosystem.
"This event significantly increases my confidence in the Bitcoin ecosystem to thrive even when faced with critical issues."
It does the opposite for me, because it demonstrates that Bitcoin is extremely vulnerable to double spending. Either everyone uses the same version of the software, or you have to deal with the possibility that this event will happen again. Worse still, an attacker might use some kind of malware to modify Bitcoin clients, until they are able to fork the network and double spend.
Yes, making cryptosystems that are secure against malicious majorities is difficult, and experts have published tons of papers and several books on the subject. If Bitcoin's developers want people to trust their system for anything non-trivial, they really need to fix this problem. To break David Chaum's digital cash systems, an attacker would have required exponential computing power in a security parameter that could be scaled arbitrarily, while the users only require polynomial computing power in that same parameter; to break Bitcoin, an attacker only requires a little more than half the sum of all the computing power in the Bitcoin network. The Germans learned the hard way that just because an attack seems too pricey for anyone to bother with does not mean that the attack actually is too pricey for anyone to bother with.
The ability for clients to erroneously or maliciously fork the chain can't be designed out whilst keeping the system open and decentralised. The blockchain is a distributed copy of a shared truth which takes time to propagate and has to be agreed upon by all participants. If the network is open, then me, or me and 500,000 friends, can join the network and attempt to propagate a different truth.
If you compare the way the Bitcoin community responded to this with the response you might have expected from even a very well run company, I think the Bitcoin community comes out ahead.
It would be useful and or interesting to compare the Bitcoin community response with a specific failure and response of a for-profit closed-technology company, but I'm not sure what case to use for comparison.
"The ability for clients to erroneously or maliciously fork the chain can't be designed out whilst keeping the system open and decentralised"
That is not true. Cryptographers have published many thousands of papers on securing multiparty computation against malicious participants over the past twenty years. Here is a very brief introduction:
The relevant citations in this field, like the relevant citations about digital cash protocols, are conspicuously absent from Satoshi's writeup about Bitcoin. This is one of the things that bugs me the most about the Bitcoin community: nobody seems to have done any background research at all. There is a huge volume of work that has been done in this field, but little mention of it among Bitcoin's developers. The Bitcoin developers do not even seem to be worried about the fact that the work required to attack Bitcoin scales linearly with the work required to run the Bitcoin system:
"If you compare the way the Bitcoin community responded to this with the response you might have expected from even a very well run company, I think the Bitcoin community comes out ahead."
OK, the community is great at admitting that there are bugs and finding workarounds. That does not count for much in a secure multiparty system, where subtle problems in a protocol can undermine the security of the entire system. Security in a system like Bitcoin is about more than just "avoid X, remember to do Y, and patch bugs quickly!" Malicious clients are going to have to be dealt with in Bitcoin, and they are going to have to be dealt with better than what we saw today.
The thing you must realize is that those previous systems didn't solve the problem Bitcoin solves. It's not quite obvious - I read the Bitcoin paper when it had pretty much just come out, didn't recognize the actual problem it was solving, and ignored it as yet another "contradictory-caveat" system (eg. paper title: "Anonymous Offline Payments!!@" ... later section: "identity escrow, merchant accounts, only offline for honest parties, etc"). It sucks that there's finally a widespread digital currency and it's non-anonymous, but that's not the problem Satoshi actually solved.
"The thing you must realize is that those previous systems didn't solve the problem Bitcoin solves"
That is not the point. Previous work in the field of digital cash and in multiparty computation is very much relevant to Bitcoin, even if Bitcoin addresses a modified problem. The failure to even mention that such work has been done, coupled with a woefully deficient analysis, indicates that the author of the Bitcoin paper had not done much background research.
What stands out the most is the security analysis for Bitcoin. First, the author makes the claim that the system is secure as long as the attacker controls less than half the sum of the computing power of all nodes in the system. This is not really a well-understood model of security; cryptography researchers usually speak of either "honest but curious" models i.e. everyone follows the protocol faithfully or "malicious" models i.e. some parties may deviate from the protocol in arbitrary ways. The idea of a party that can deviate, but only as long as their work is less than the sum of the work done by all other parties, is strange -- but this new security model is not discussed in any depth, nor is it even mentioned as being a new model of security. No time is spent actually proving the claim, which is unsurprising given that the security model itself is not even formalized.
Worse still, the security analysis that is presented only deals with a specific attack carried out in a specific way. The author proves in a somewhat-formal way that this particular attack cannot be carried out in the way he envisioned. No evidence is given that another method of carrying out the attack is impossible, nor is any evidence given that other attacks are impossible.
There is an old proverb in cryptography: anyone can come up with a cryptosystem they themselves cannot break. That is what you are seeing with Bitcoin, but even worse, because the developers know how to break it but do not believe that anyone would be willing to put in the effort. The German cryptographers were surprised to discover that the Allies were willing to build the code-breaking machine necessary to crack Enigma; they knew it had weaknesses but believed that the cost of exploiting those weaknesses was too high for anyone to justify.
My point is less about what problem Bitcoin solves, and more about whether or not Bitcoin's developers are aware of just how much work has been done on secure multiparty computation or digital cash systems.
I don't really disagree with anything you're saying. Bitcoin has a lack of rigor all around, and it's quite annoying to see the masses of people defending Bitcoin as being anonymous (etc) when they've no context to place it in.
What I am trying to point out is that Bitcoin has a design property that enables it to actually be adopted (no "bank" - something no other ecash system had, as they were mostly designed in an era when people still believed that banks would be interested in preserving their customers' privacy. lol). This is important if someone is to ever build a better system.
I'm less familiar with recent MPC literature, but the general concept strikes me as more of an existence proof, given the actual efficiency of resulting implementations. Practical ZK/WI results seem to generally decompose larger domain-specific chunks of the problem into primitive operations, rather than one crypto op per generic logic gate. Which seems to be what Bitcoin is doing, in a bumbling sort of way. And I don't see too much of a philosophical leap between "majority of parties" and "majority of computation", given that the former is wishful thinking that admits Sybil attacks.
"What I am trying to point out is that Bitcoin has a design property that enables it to actually be adopted (no "bank" - something no other ecash system had, as they were mostly designed in an era when people still believed that banks would be interested in preserving their customers' privacy. lol). This is important if someone is to ever build a better system."
Keep in mind that there is more to digital cash than just maintaining customer privacy (and Bitcoin itself does not really give you anonymity, at least with any reliable guarantees). Banks benefits from digital cash because of the difficulty of committing fraud and (assuming offline transactions) the reduced load on their transaction processing systems. The real issue is not that banks have no incentive to deploy such a system, but rather that their existence fraud-mitigation measures are more cost effective (in the short term). As my colleagues who have worked with banks have explained it to me, the banks only want to know what amount of fraud would occur; if your system can reduce that fraud more than it costs to deploy, then the bank will spend the money to deploy it.
The same design that has led to Bitcoin's adoption is also something of a liability for the system. Without any banks, converting Bitcoin to other currencies requires the use of an exchange, which carries increased costs and risks. The lack of stability in the price of Bitcoin relative to USD is a result of this issue. It is easy to forget that there is a source of demand for USD, one that is grounded in legal structures like the tax code, debt law, torts, etc. Even when people use Bitcoin for their business, they still need to eventually exchange Bitcoin for some national currency to pay taxes and repay debts (and perhaps to pay employees who lack the time or sophistication needed to use a Bitcoin exchange).
Another issue is more technical: there is no secure way to process an offline Bitcoin transaction. In one of his published papers, Chaum proved a property of offline digital cash systems that is as relevant to Bitcoin as it is to Chaum's design: the amount of information that needs to be exchanged in an offline transaction must grow linearly in the length of the offline transaction chain (imagine if a dollar bill became heavier every time it was given from one person to another). What this means is that either you need the ability to "refresh" the unit of value (e.g. reissuing the token in Chaum's system) or else your offline transactions are either insecure or not scalable. As there is nothing in Bitcoin that can "reissue" currency (which involves creating fresh units and destroying old units), Bitcoin is either insecure, insecure for offline transactions, or it does not scale (note that "secure" in this case refers to formal notions of security; Bitcoin does not actually meet that standard, so this point may be moot anyway).
"Practical ZK/WI results seem to generally decompose larger domain-specific chunks of the problem into primitive operations, rather than one crypto op per generic logic gate."
Right, and that is within the field of MPC research. General MPC using circuits or some other description of functions is much slower than special-purpose protocols, which are themselves usually slower than just using a trusted third party. You are correct that Bitcoin is an example of special-purpose protocol; the problem is that Bitcoin as it exists today would only be secure in a minutely stronger variant of the honest-but-curious model. Honest-but-curious is really just a research tool, a model that is used to give feasibility results or to test new designs, and it is certainly not the right security model for anything involving money (of any sort).
"I don't see too much of a philosophical leap between "majority of parties" and "majority of computation","
The leap is this: a single party might gather immense computing power without corrupting any other party. As a simple example, my research group has access to a supercomputer run by the University of Texas, which I could potentially run anything on (not necessarily legally). If you and I were going to use a two-party protocol of some kind, would you really want to use one that forced you to get access to a similarly powerful supercomputer just to be secure?
Worse still, you might not be aware of the computing resources available to other parties. The Germans were not aware of the Enigma-cracking effort until after the end of the war. In today's world, it is possible that your adversary has a botnet, a bunch of EC2 credits, or that you are dealing with the NSA. In all cases, you do not want to rely on a system that requires you to get equal computing power to remain secure.
Some MPC protocols are secure unconditionally, meaning that even an attacker whose computing power is completely unbounded will not be able to violate the security property of the system. In such a case, controlling a majority of the computing power of all parties is not even a relevant detail, because increased computing power does not convey any advantage.
It is more common to assume some bound on the attacker's computing power and to use complexity theoretic arguments about security. Typically, the attacker is assumed to be able to scale their computing power up by some polynomial in the parameters of the system, which includes the participants. Again, it is because there are real-world adversaries who control large amounts of computing power, potentially in secret, that such models are used. The justification is intuitively this: if you have one desktop and your adversary requires a cluster of ten thousand desktops to break the security of the system, you can get a second desktop and double the work you need to do while forcing your adversary to find ten thousand clusters of ten thousand desktops (i.e. squaring his workload). Super-polynomial growth tends to "run away" at the second half of the chess board, so that a modest increase in the work done by honest parties can result in the attacker needing to keep working until the heat death of the sun.
On the other hand, a powerful adversary could potentially corrupt or control parties in the system. The Mafia is not going to buy NSA-level computers; they are going to find the participants and beat them with wrenches. A more real-world example would be the suspicious appearance of lots of highly-reliable anonymous remailers after the September 11th attacks. Having a lot of computing power does little to defeat the remailer system, but if you control all the remailers you can deanonymize anyone. Remailers have a nice security property: only one honest remailer is required to preserve your security (assuming you send your messages through all the remailers and that the remailer protocol itself has certain security properties which real-world remailers lack).
Sorry if that was a bit long. This is a pretty deep topic, and even the foundations are highly technical.
> Banks benefits from digital cash because of the difficulty of committing fraud and (assuming offline transactions) the reduced load on their transaction processing systems
Decades of non-adoption say otherwise. It's hard to say what the exact reason is - paralyzing conservatism, business models built on decommoditizing money into an identity-based instrument, conspiracy via government regulation, or something else. But enough time has passed that if banks were remotely receptive to the idea of digital cash, it would have caught on somewhere.
> there is nothing in Bitcoin that can "reissue" currency
Every new wallet address, no? Offline transactions are vulnerable to double spends, but this is the case with every digital cash system. IIRC, the ones that protect against offline double spends do so by revealing the fraudster's identity if a token is spent twice - requiring a bank and legal system for recourse.
> It is more common to assume some bound on the attacker's computing power and to use complexity theoretic arguments about security.
Sure, and this is what the SHA2/DSA parts of Bitcoin do. Nobody can forge transactions, the worry comes about from double-spending. You have to remember, digital currency is not a two-party problem - every involved party is what gives the currency value. This is essentially a coordination problem (which database copy is authoritative?), and is precisely the novel problem that Bitcoin solved. Previous p2p attempts would do something like "majority of parties", which is always vulnerable to Sybil attacks. Bitcoin went for something that can be algorithmically enforced, staking its outcome on the belief that NSA-level computing would both not dwarf the rest of the network, and that double spends would be detected and could be somehow mitigated down the line.
"enough time has passed that if banks were remotely receptive to the idea of digital cash, it would have caught on somewhere."
Again, the way I understand it, the problem is not a lack of benefit but that the benefit is not sufficient to convince any bank to switch. Banks are very concerned about fraud; the problem is that they do not get enough fraud protection from digital cash to outweigh the cost, because they already have good fraud mitigation methods. Why switch to a car that gets one more mile per gallon of fuel, when the cost of doing so would not be recouperated for decades?
"Offline transactions are vulnerable to double spends, but this is the case with every digital cash system."
The difference is that a person can double-spend in Bitcoin over and over again, even if the double spending is detected at some point. In Chaum's design, a person who double-spends is eventually ejected from the system, and so a person can only double spend until the double-spent money makes its way back to the bank. A legal system is not strictly needed here; all it takes is the bank blacklisting cheaters.
"this is what the SHA2/DSA parts of Bitcoin do. Nobody can forge transactions"
One does not follow from the other. SHA2 is a (hopefully) secure hash function. DSA is a secure signature system. People might still be able to forge transactions, due to some other property of the Bitcoin protocol that composes poorly with DSA/SHA2. A transaction in Bitcoin is not merely a signed message; there is a protocol that is used to decide the validity of the transaction, and that protocol might be vulnerable to attack (and maybe vulnerable to attack as a result of using DSA, as opposed to some other signature system). Without a formal proof of security for the entire transaction protocol, it is hard to say.
A simpler example might help to illustrate the point. Imagine a system for telling employees that they have been fired that works as follows: the boss signs and encrypts the letter "F" using his signing key and the target's encryption key. It may appear that forging a firing notification is hard, because the signature marks it as authentic and the encryption designates the target (i.e. if you cannot open the message, then you were not fired). However, it is possible for an employee who is fired to turn around and fire others by re-encrypting the message and signature -- which works even if the signature and encryption systems used are secure.
"This is essentially a coordination problem (which database copy is authoritative?),"
What does "authoritative" actually mean in the absence of an authority? Without a good definition, it is hard to actually say what a solution would have to look like.
"the novel problem that Bitcoin solved."
The fact that Tuesday's fork could happen is pretty strong evidence that Bitcoin is not really a solution to the problem (assuming we even know what the problem actually is). The fact that a double spending attack was made possible by the fork is a sign that Bitcoin is either (a) solving the wrong problem or (b) not solving the problem at all.
Even if we limit ourselves to considering only Sybil attacks, Bitcoin does not truly solve the problem. Sybil attacks are still possible; the only difference is that now the attacker will need more CPU power (maybe; more sophisticated attacks are certainly conceivable).
"Bitcoin went for something that can be algorithmically enforced"
Except that it is not enforced (at least not under any well-understood definition of that word), it is based on this sort of thing:
"staking its outcome on the belief that NSA-level computing would both not dwarf the rest of the network"
In other words, it is assumed that the adversary could never accumulate as much computing power as all the Bitcoin users combined have accumulated. This is a pretty bad assumption to make, since it fails under any number of entirely plausible circumstances. NSA-level computing is a complete mystery to the outside world; maybe they are using computing technology nobody else has, that works substantially more efficiently. How do you know your adversary does not have such systems? Every so often, Bitcoin "miners" switch to some faster technology for that task; is an adversary who invents a new technology for this really so hard to believe?
"double spends would be detected and could be somehow mitigated down the line"
What exactly can be done to "mitigate" double spending in Bitcoin? There is no system for denying access to the network. An attacker who double-spends Bitcoin could keep coming back and could keep double-spending. In Chaum's system, double-spending carries the cost of losing one's access to the system; with Bitcoin, it carries no cost at all (one might just sell the equipment used for the attack, and so one only really needs sufficient capital or credit to procure the equipment in the first place).
> because they already have good fraud mitigation methods
Then why is it such a big topic, with the banks even deflecting the blame by inventing "identity theft" etc? And even if the banks are fine, the merchants are not, and a new bank should have sprung up to address that. Which leaves us with the remaining option - incumbent banks are cooperating to prevent new competition. I'm not trying to specifically convince you of this paranoia, but provide it as something that may have to be overcome by a digital payment system to be adopted.
> Chaum's design, a person who double-spends is eventually ejected from the system
I'm hazy on my ecash citations. 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? That's the system that's stuck in my head as best-in-breed if there is a bank on board.
But what I've been trying to get across here is that Bitcoin provides a property none of those other systems provided - freedom from a trusted "issuer"/bank/etc. (While those protocols don't trust the bank to preserve privacy, they do trust the bank to administer the currency by being the counterparty to the tokens.)
> People might still be able to forge transactions, due to some other property of the Bitcoin protocol that composes poorly with DSA/SHA2
Oh sorry, you caught me with my rigor-pants down. What I meant to say is that being built from those primitives, it could be proved as secure as those primitives. Unlike the Byzantine agreement component, which will always have other security tradeoffs beyond SHA2.
> What does "authoritative" actually mean in the absence of an authority? Without a good definition, it is hard to actually say what a solution would have to look like.
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.
> Sybil attacks are still possible; the only difference is that now the attacker will need more CPU power
No, Sybil attacks have been defined away, as they depend on some notion of "parties". The "honest parties" wishful-thinking has vanished, leaving only "majority of computation" as the network authority. Of course the merits of this security model are still up for debate, but it seems to mostly work.
> The fact that Tuesday's fork could happen is pretty strong evidence that Bitcoin is not really a solution to the problem
Erm, given that the fork was a rare event, it actually shows that Bitcoin is mostly solving the problem, just not perfectly.
> What exactly can be done to "mitigate" double spending in Bitcoin? There is no system for denying access to the network
Lol. "no system for" is not the same as "system prevents" (see what happened to the End to End principle). I guarantee we will eventually see exchanges exerting control over what constitutes "valid transactions" and "the network". This is Bitcoin's real weakness.
"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."
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.
It was great to see in action, but given the way the system is right now it wasn't that incredible.
The maintainers of the biggest pools are all very active in the community; it would just take 2-3 of the big mining pools to say "hey, let's go back to 0.7" for this to be resolved automatically.
I agree. In the past few weeks, Bitcoin has really picked up lots of speed. So much in fact, that I'm wondering whether we're witnessing an exponential adoption where years of people doubting Bitcoin were simply the beginning of the curve. That would also mean that things are going to explode pretty soon.
I sincerely hope that the aftermath of said explosion will leave Bitcoin as the strong contender to established monetary systems that it always was - just "proven by reality" now. That would certainly be all I need to finally jump on board.
If only the global finance institutions had a fraction of bitcoins capacity to resolve crises with the same unconditional transparency and full cooperation with all agents in the ecosystem.