Quote from: storr on September 18, 2011, 03:49:44 PM

1) OK, it is usefull to make ASIC less effective. But it is not enough. At least, they can use 20,000-40,000 GPUs to make the 51% attack. We need one more solution for this case.

Modern GPUs are memory-limited too. My HD6990 has >3000 cores and only 4GB RAM. This is ~1M per core. And this is only a good starting point for further thoughts.
Also I mentioned earlier: if Bitcoin ever reach popularity comparable to Bittorrent that 51% attack should take much more GPUs, especially when POW is memory-bounded.
But there is one more issue. Favoring GPUs or any other highly-specialized solution for minig doesn't encourage wider Bitcoin popularization. We should keep the doors open for newcomers. And in average they don't have top-level GPUs.

Quote from: storr on September 18, 2011, 03:49:44 PM

2) What new POW do you suggest? Your scheme with N=32M/32=1M ? IMHO, it is not good because calculation of 2^20 sha256 is too time-consuming. Each node (not only miners) needs to calculate POW each time when recieves a new block. Do you have another one idea? We can remember results of intermediate steps 0,8,16,24,32,40,48,63 of sha256 calculation, for example. It is 8 times more information,
but 2^17 calculations of sha256 is very time-consuming too.

2^20 sha256 computations over 32-byte vectors is equal to 1 sha256 computation over 32M file. It takes less than a second on my box. So I considering this to be acceptable.
Moreover I don't insist on hashing something million times. That was only an example. Digging a little I've found interesting paper: Exponential Memory-Bound Functions for Proof of Work Protocols. Scheme that described in the paper is also two-dimensional (by memory amount and successive POW criteria). And I don't have any idea how to adjust memory requirements and "leading-zeros count" together with difficulty.

Quote from: storr on September 18, 2011, 03:49:44 PM

Yes, if we will make "net of trust", then an attacker with more then 50% of computational power can create "alternative reality" in bitcoin, i mean alternative block chain, that will begin with the same generic block but then diverses with the "real" block chain. In fact, in this case can exist more then two block chains. And for a node that connects to the net, there will be impossible understand wich of them to connect and belief. IMHO, this problem can be solved only by out-of-bitcoin methods. All sites that work with bitcoin may\have to publish in what reality\block chain they work. I belief that they can detect which block chain is real. And usual users will check from time to time that they live in the same reality. It is not excellent, but I don't see any better solution. At least, by this approach it is possible to eliminate other problems of 50%+ attack:

Reverse transactions that the atacker sends while he's in control
Prevent some or all transactions from gaining any confirmations
Prevent some or all other generators from getting any generations

That would be something like Reeple, not like Bitcoin.