An interesting article. Jon Matonis discusses payment processors' attack on merchants who step outside the sandbox of transaction types the processors consider legitimate. He points out something also pointed out by Peter Šurda at the recent London Bitcoin conference: all this effort at control only increases the overall awkwardness to merchants of using these traditional payment channels, and can be expected to accelerate the adoption of methods to route around them, such as Bitcoin.

(Peter was talking about AML/KYC efforts increasing the transaction costs of using the banking system, not "transaction type monitoring" efforts doing the same to the payment processor network, but the punchline is the same in both cases: the comparative advantage of Bitcoin is improved.)

EDIT: merged into Stephen Gornick's similar thread. (I can't delete my own topic starting message - moderators please delete.)

http://www.forbes.com/sites/jonmatonis/2012/10/26/generic-viagra-industry-is-pro-choice-in-payments/

Jon Matonis discusses payment processors' attack on merchants who step outside the sandbox of transaction types the processors consider legitimate. He points out something also pointed out by Peter Surda at the recent London Bitcoin conference: all this effort at control only increases the overall awkwardness to merchants of using these traditional payment channels, and can be expected to accelerate the adoption of methods to route around them, such as Bitcoin.

(Peter was talking about AML/KYC efforts increasing the transaction costs of using the banking system, not "transaction type monitoring" efforts doing the same to the payment processor network, but the punchline is the same in both cases: the comparative advantage of Bitcoin is improved.)

They're measuring wildly different kinds of computation - real number (floating point) calculations for weather simulations, weapons simulations, etc etc (for which "flops" [floating point operations per second] makes sense) vs. endlessly repeated integer-based hashing (for which "flops" has not the slightest relevance).

STATEMENT BANDIED ABOUT IN LOTS OF PLACES (on this forum and elsewhere): "No way can anyone ever mount a 51% attack, because the Bitcoin network is far more powerful than all the world's supercomputers combined." (or variant wordings with greater or lesser degrees of hyperbole)

TRANSLATION TO REALITY: It's a few thousand graphics cards. A mere footnote in the budget of any bank or government that wanted to outpace it. We do need to worry about how to stand up to 51% attacks, 90% attacks... the full gamut. Let's start thinking and worrying now!

(My own thoughts: https://en.bitcoin.it/wiki/Proof_of_blockchain_fair_sharing. And yes, I'll say it before anyone else does, these thoughts are still hopelessly unfinished - barely more than started - but I've published them in unfinished form because I want to get as many people thinking about this as possible!)

I'd really be happy with any "reasonably plain-text-ish" representation - JSON (object or array) is just the obvious leading candidate. This is of course, exactly as you say, a lot less space- and time-efficient to handle than a binary format (Berkeley DB in the Satoshi client, perhaps other binary formats in other clients). But it, uh, postpones my day of reckoning (of having to master Bdb) 

(Just to clarify: I wouldn't be trying to respond interactively and quickly to web requests for a chart or whatever - I wouldn't be competing with the marvellous charts at https://blockchain.info/charts. I'd just like to analyse the blockchain [in various ways that go a bit beyond those charts] offline, at leisure, for my own interest. So, for now at least, efficiency is not so important for me!)

Hello folks... is the blockchain available somewhere as one giant JSON object? I'd like to try my hand at some analysis of its structure (bitcoin days destroyed, lengths of txout/in/out/in chains, that sort of thing), and the Satoshi client's Berkeley DB format is utterly beyond me.

Yes indeed, you're quite right, my worry was groundless. Well then, this is really exciting, the road to a secure lightweight client is open and clear!

Ah, of course! Thanks for the explanation.

Perhaps a record of spent txouts would still be of some value, to cover the case where a light client wants to query a full node with "prove to me how (i.e. into what tx) this txout was spent"? (But then again, maybe the need (if any) for such a query type would be sufficiently rare and specialized that running a full node oneself can be deemed the reasonable way to meet such an "expert" need.)

Apologies if this is a stupid question, but... would it not also be of benefit to make available, by the same sort of methods, a record of all the spent txouts? I'm thinking of how things can go when a future light client is querying (in untrusting style) a full client node - perhaps in exchange for a micropayment, or a subscription or whatever - about whether various txouts are spent or unspent. Here's an anthropomorphized dialogue. (Obviously the number of rounds back and forth is higher than it needs to be, just for the sake of anthropomorphizing the exchange.)

Light client (LC): hi, is this txout (.....) spent or unspent?
Full client (FC): unspent.
LC: ...and your proof? (I don't trust you, remember!)
FC: here's the merkle chain [or similar thing for whatever the data structure is exactly] leading from your txout to the root hash, which you can acquire from the network with suitably impressive [merged-]mining effort associated therewith. (transmits a pleasantly short merkle chain)
LC: ok, thanks very much! now, what about this txout: spent or unspent?
FC: spent.
LC: ...and your proof?
FC: well, uh, the proof is the fact that I'm not sending you a merkle chain like I did with the unspent one!
LC: sorry, but that's not a proof from my point of view!

With a record of spent txouts, the FC can send a merkle chain convincing the untrusting LC of a txout's spent status, rather than having to say "trust my absence-of-proof-of-unspent to mean it's spent".

(Maybe this is overkill? The FC could just send the transaction which spends the given txout. But maybe that was a transaction that "died" (failed to be bedded down in the winning blockchain) long ago, and for the FC to send it is misleading. Admittedly, the main reason for such "dyings" is losing a double-spending battle, in which case the relevant txout is likely still in fact spent, just not by the transaction the FC is advertising. But one can imagine scenarios where the LC wants proof not just of spent status, but of where it went, and a suitable data structure could support a reply of "it's spent, and here's the tx it went into, and here's a pleasantly short merkle chain establishing this".)

Ah, but remember the asymmetry of the two communities' goals. Imagine the 90% attacker (I'll use the word "attacker" because we can live with a benevolent monopolist - it's when they stop being benevolent that we have to start caring, so to speak...) has already built a tall contiguous chain run, perhaps tens or hundreds of blocks tall, which is purely theirs - the attacker has (so far!) kept successfully reversing and excluding the blocks offered up by the 10% of honest miners. Thus, so far the attacker's chain has kept out the transactions the honest miners are including as a matter of course (to earn the fees), and has let in only those transactions (if any) the attacker wants to deign to permit.

At this point, because the honest 10% aren't trying to build an honest-10%-only chain - a goal they would indeed have no hope of achieving - but merely to get an honest block into the chain here and there, we have the interesting situation that both communities are trying to build on the attacker's proudly built tall chain.

This is where "proof of blockchain fair sharing" - a suitably cleverly chosen structure-aware chain height formula - could swing into action. The attacker's would-be (n+1)th block is keeping things as skewed as ever - the 90% having 100%, the 10% having 0%; whereas the honest miner's would-be block is at last moving things incrementally towards proportionality - the 90%'s share down a little to 99% or whatever, the 10%'s share up from 0% to 1% or whatever. So, with the right formula, we can hope that the candidate chain we're rooting for, i.e. the one with n attacker blocks followed by 1 honest miner's block, will win over the "pure evil" one (with n+1 attacker blocks)! - And so on up from there, giving the reasonable interspersal the honest miners crave.

OK, I freely admit that this is all talk until I, or someone else, actually comes up with a structure-aware formula with that property. But I think the omens are good - there's such rich pseudonymous structure in a proof-of-stake chain (compared with a proof-of-work chain) that some formula can maybe do the job! (It doesn't have to be literally a "formula" in the traditional mathematical sense - "algorithm" would be a better word really.)

It's precisely to get as large a talent pool as possible thinking about these possibilities that has motivated me to go ahead and publish the broad framework right now, without having come up with a formula myself. Better that, I think, than to have just me working silently away on a formula, and, uh, perhaps not having the talent to find one that someone else could find quickly!

I have some thoughts on the 51% (even >>50%) attack problem which may be of interest to those following this thread. Rather than duplicate them here I'll just give an intra-forum link: Proof of stake - done right - is maybe, just maybe, the way to eliminate 51% (even 90%!) attack worries altogether! https://bitcointalk.org/index.php?topic=68213.msg920853#msg920853

(Note that it's not, yet, a specific technically detailed proposal. It's more the launching of a new paradigm for how to design proposal(s) for standing up to attacks that go over the 50% mark. I hope it's of some interest to someone!)

(Copied, with minor edits, from my recent contribution to https://en.bitcoin.it/wiki/Talk:Proof_of_Stake.)

Proof of stake - done right - is maybe, just maybe, the way to eliminate 51% (even 90%!) attack worries altogether!

The vigorous debate about which of various systems, on a spectrum from pure proof of work to pure proof of stake via hybrids in between, is very enjoyable and thought-provoking. But when all is said and done, the evaluation process always boils down to "which system is least likely to allow the horror of a 51% attacker getting total control?". It's just assumed, by everybody as far as I can tell reading through the forums etc, that a 51% attack is a sure-fire route to total control, and that there's nothing anyone can ever do about that.

(And make no mistake, total control will not stay benevolent, even if it starts off that way. The temptation of the total controller to start acting exactly like the banking system as we know it today - inventing ever more elaborate rules for what sort of transactions it will deign to process, how much it feels like "knowing" about its "customers", and so on - and, beyond that, the temptation of the political system to put unstoppable pressure on the controlling entity to do all these things and more - will be huge, permanent and irresistible. "Decentralisation" will become worthy only of a hollow laugh.)

But, I would like to ask: are we thinking imaginatively enough about this? What about seeking a protocol where even a much more than 50% attack still fails? (Where the "%" figure refers to whatever the scarce resource is - work, stake, an optimum Cobb-Douglas mix of the two in a hybrid system... whatever.)

It's been taken as "obvious" that a 51% attack will succeed. One unit of the scarce resource is the same as another, and 51% beats 49%, and that's all there is to it! But proof of stake means the scarce resource is not the fungible "stuff" we're used to from proof of work. Stakeholders (unlike proof-of-work miners) are pseudonymously trackable. (They sign with a pseudonymous identity when they supply bitcoin days destroyed into a coinbase transaction, or whatever similar thing they have to do to establish they're a stakeholder.) And they can't cheaply change their pseudonymous identity (sloshing bitcoins around before landing them on a coinbase throws away all those lovely bitcoin days that could have been destroyed into the coinbase).

This opens up wonderful new possibilities. We no longer have to compute the "height" of a candidate blockchain as just the sum of atomistic contributions from each block (like the sum of their difficulties, in the case of the current Bitcoin). We can reward preferred structures and patterns in the way the pseudonymously-trackable stakeholders are interleaved in the chain.

In particular: we can reward "closeness", in some mathematical sense yet to be pinned down, to a sort of proportionality or "fair sharing" pattern. So, for example, a miner or set of miners with 10% of the deployable stake, who so far has less than 10% occupation fraction of the blockchain (maybe they've barely started mining at all), can have each block they mine (and help bring their share closer to the "ideal" 10%) be deemed to contribute more incremental height to the chain than an atomistic sum formula would have given. And conversely, if they overshoot and already have 15%, a structure-aware chain height formula can allocate less incremental chain height for the overshooting fraction than an atomistic formula would have given.

I believe that if we choose such a formula cleverly, we may well be able to protect against attacks that have been considered an obvious lost cause - 51%, 80%, 90%. For note that the attacker(s), say with 90% of the stake resource, and the honest miners, with the remaining 10%, have asymmetrically different goals.

The attacker, or attacker cartel, wants (in the scenario we're traditionally most worried about) to either bring down Bitcoin, or keep it going but with control over what transactions are "acceptable" - e.g. to act like a know-your-customer bank, or to harass targeted persons or economic sectors by rejecting their transactions. To achieve this, the attacker has to keep all blocks generated by the honest 10% out of the winning blockchain. (If even an occasional one got through, in a way the attacker couldn't reverse, it would of course include all the accumulated pool of "ordinary, reasonable" transactions the attacker is trying to reject - the 10% just want to earn an honest profit by collecting all those fees.)

By contrast, the honest 10% do not have to aim for the symmetrically opposite goal (of excluding the malicious 90%). They merely have to aim for achieving a reasonable interleaving of their honest blocks into the winning blockchain. Then ordinary users will get their transactions handled (albeit more slowly than they might have got used to); and the honest miners will collect their fees.

The challenge, then, is to design the structure-aware chain height formula so that the attacker's would-be chain loses (even though, of course, a mere sum of stake-achievements block by block would allow a 90% attacker to effortlessly win). The idea is that, if closeness to fair share interleaving is being especially highly rewarded, then the attacker's chain gets penalized for being far away from fairness: the 90% have 100% occupancy, and the 10% have 0%. The competing chain with some honest blocks here and there gets strongly rewarded by comparison (say for example the 90% have 93% and the 10% have 7% - that's closer to fair shares than the attacker-only chain). It wins!

The exasperated attacker fumes, "Why the hell can't I reverse these pesky honest blocks? I'm deploying 90% of the network's entire power! My chain without them should be the winner!" Ah, but structure-awareness is rewarding their presence and penalizing their absence. And with a strong enough such effect, who knows, perhaps any percentage level of such a style of attack can be thwarted!

I've created a draft page, https://en.bitcoin.it/wiki/Proof_of_blockchain_fair_sharing, for ideas fitting into this general milieu. At the moment it just has a teaser description of the general idea (pretty much similar to what you've just finished reading here). I had hoped to spring a polished structure-aware height formula on the world; sadly, my first effort I believe has subtle economies and diseconomies of scale (giving stakeholders perverse incentives to either club together, cartel-like, or disaggregate, taking on multiple pseudonymous identities each). That's not the end of the world perhaps - especially since the whole point of this revolutionary new approach is that a cartel (even going above 50%) is no longer something to be terrified of - but I'd prefer long-run scale-neutrality if possible. More importantly, I now also believe my first effort doesn't achieve a strong enough bias in favour of fair-shares chains to make much difference (it maybe means a 67% attack is needed to gain total power, rather than 51%... mildly helpful I suppose, but I still aspire to the dream case where no finite attack succeeds in the long run).

Naturally, I'm hoping to invent a formula that achieves the miracle of letting any honest minority, no matter how small, achieve a non-zero occupation fraction of the winning chain. (Their achieved occupation fraction might not be exactly the "fair" one; but any non-zero fraction would let Bitcoin continue, albeit slowly and creakily, and with luck the attacker eventually concedes defeat.) To speed up progress, I thought it only fair to throw open this challenge to all mathematically-minded Bitcoin folk - after all, there are doubtless others far more talented than me!

I'd like to contribute to the various "proof of work vs. proof of stake" threads, in particular with the contribution I've currently placed in this newbie ghetto area: https://bitcointalk.org/index.php?topic=82843.msg912847#msg912847 I'd love to draw these thoughts to the attention of the currently active proof of stake folk, and hear their thoughts and opinions!

(new non-newbie location for this post: https://bitcointalk.org/index.php?topic=68213.msg920853#msg920853)