Quote from: Alex Coventry on February 18, 2012, 05:20:30 PM

Hi, everyone. In my spare time, I've been thinking about ways to incorporate arbitrary computation into the proof of work for a bitcoin-like blockchain-based cryptocurrency. You can read about the design I've come up with here (click on the "Download" link in the top right-hand corner to view the PDF locally.)

I know nothing about the MCMC problems used for physics, but I sure can't see how this can be used for MC sampling for bayesian inference, since you actually need the whole chain data after the bootstrapping. Perhaps it would be helpful if you spelled out some example problems and gave the setups for them.

As someone who uses optimization frequently the idea of being able to buy cycles to run arbitrary stochastic algorithms is a very exciting one.

In particular, I often use optimization ~interactively while problem solving. While my average utilization is fairly low, I would really like enormous amounts of computation in short bursts. If I could buy EC2 in 5 minute chunks I'd regularly be buying 1000 CPUs worth at a time. So a distributed system which allowed me to shift computation in time in order to get more of it at once would be _VERY_ useful to me.

I have some vague concerns that the result of the Lua execution engine (with software floating point!) will be that such a system could not be competitive with centralized computational services simply because you're going to take some large slowdown to start with. You don't seem to have addressed resource exhaustion except for speed, e.g. running the systems out of memory, or simply requiring great amounts in order to disadvantage nodes with smaller amounts creating a race where all participants must have as much ram as the most and making it hard to reason about the returns on investing resources into this system. Yes, participants can use the escape hatch out, but at a 10x disadvantage to ones that have enough ram to keep going.

For the same reason, I'm unhappy with the alternative block regular hash how is such a system to be competative with 50% deadweight loss (on top of the other losses)?

Bleh. I wrote several paragraphs of text with excited ideas about this and that and also arguing that you didn't need the second hash function because if you already had 51% computing power you'd be better off using it to run optimized versions of your own computing work then using it to trick the rest of the network into running inefficient versions of your work.

When then made me realize that your system has a pretty debilitating "Optimization attack" I'm sure this isn't news to you, thus the every other block optimization... but I don't really think it helps much. I think your paper should spell this attack out clearly.

Say an attacker forms some A() which is just a trivial function e.g. A(x,y)=x, he also forms an A()', say A(x,y)'= sha256^1000(x) * 0 + x which is identical to A() in results but which is much more expensive to compute. He announces A()' to the network, but detects it on his own systems and runs A() instead. He now has a enormous speed advantage on all other nodes.

The alternative block idea prevents this from being trivially translated into an overpowering attack, though the security is still enormously reduced compared to blockchain cryptocurrencies. But I don't think thats the worse result.

The worst part of this is that even ignoring overpowering attacks, I believe it will be economically advantageous to perform this attack so long as getting the network to use some A() always costs strictly more than the reward. This means that currency will only enter the system through execution of the dummy A that cost no one anything to run, which (assuming constant computing power) means another 2x overhead: for every unit of real work you do, you must have a unit of dummy work to create the coin to run it.

This ... on top of the standing halving required to make overpowering even a little non-trivial.. and the halving (at best!) of using a highly sandboxed execution engine (rather than optimized machine code).... As a result this system probably has a peak computing efficiency of 12.5%, while offering substantially less security than existing cryptocurrency in a number of regards (the >25% attack, the fact that the POW can be expensive to validate burdening regular nodes not just mining ones, the fact that the POW might be insecure to validate, again burdening regular nodes and not just mining ones). For people who don't need to store up computing for burst loads this system could pretty much never be more cost effective then simply computing their desired work directly.

Have I gone off in space here?

In any case, in the chance that this isn't as useless as I now fear, before finalizing your system I'd like to encourage you to take the chance to pick up some protocol improvements which can't easily be implemented in Bitcoin. The anti-timewarping fix would be one obvious one, less trivially, you should probably change to Ed25519 from the secp256k1 curve. There are a number of proposed changes at https://en.bitcoin.it/wiki/Hardfork_Wishlist though many of them would be inapplicable to you or a bit too blue-sky.