"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 issue has been studied in the past; see e.g. http://world.std.com/~dtd/sign_encrypt/sign_encrypt7.html http://world.std.com/~dtd/sign_encrypt/sign_encrypt7.html or http://eprint.iacr.org/2008/440 http://eprint.iacr.org/2008/440)
"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).