I claim that the buffer will be written at a more or less constant rate. In general, statements which change more variables will also take proportionately longer to execute. If necessary we could add padding for statements that take much longer than average to execute.
I like the idea of padding.
I don't. Its only purpose is the make the subsequent SHA-256 operation a more constant proportion of the total running time. It also makes it more expensive. This whole idea of adding overhead to make the system more secure might have some merit if it worked, and if our goal was only to build a slightly better bitcoin by harvesting as useful work a few percent of its PoW effort. But it doesn't work, and I'd prefer to have the overhead rather than the useful work at the few percent level.
We would have to "empirically" determine which operations require padding and which not.
Yes, and average it over very different hardware. What if an attacker were to run his FAA on an ASIC crafted for the purpose? A faster-algorithm-in-the-hardware attack. In fact, this is exactly what has happened to bitcoin over the past few years. For us, it is a nightmare.
Next note that SHA-256 is a serial algorithm. We don't even need to allocate storage for the buffer; we just pipe it straight in. Finally, note that it is a linear-time algorithm. Any new algorithm computing the same function can be at best a constant times faster, otherwise finding collisions becomes trivial. This is the basis for my claim that even the most powerful faster algorithm imaginable - an oracle that fills the buffer instantly - can achieve at best a linear speed-up.
Agreed.
It's a convincing argument. It's not sound, though. It took me a while to realise that.
What I have informally proven here, is that in a
random oracle model in which the oracle is time-linear in the size of the input, the best an attacker can achieve is a linear speed-up.
Unfortunately it turns out that supra-linear speed-ups of SHA-256 and indeed all sequential hash algorithms are possible in some circumstances. Let s be a security parameter. Let S be a fixed string of length s. Let c be a constant. Let C
i be an arbitrary sequence of strings of length c. Let S.C
i denote the concatentation of S and C
i and let C
i.S be construed accordingly. Then in the time-linear random-oracle model, the time to compute both sequences Oracle(S.C
i) and Oracle(C
i.S) are, trivially, both O(s). However SHA-256(S.C
i) is trivially O(1). All you do reuse the saved state of the SHA-256 algorithm for the constant part of the string. I think SHA-256(C
i.S) is likely to be O(s), but I can't prove it. Can you?
And this is serious, because our PoW protocol is precisely to compute sequences of SHA-256 where the input string has parts which can be manipulated by an adversary, and other parts which are constant.
This should be an object lesson in why people should be very, very, skeptical about claims of security proofs.
Would it help to use the previous block to "seed" the buffer? It would add extra security in the sense that an attacker has only the time between two blocks to handcraft a PoW function which fits his "needs".
This is encryption, and if we're talking about 10ms segments, it helps not one iota, though it does add some overhead he can't avoid. He doesn't have a limited time to handcraft his function. He doesn't have to handcraft anything; he can use any innocent program such as might have been written by some other honest buyer. All he has to do is find a reasonably tight loop which the program stays in for longer than 10ms, and runs the program "honestly" to reach that point.
Next he runs a 10ms segment "honestly" to fill the buffer. Then he can screw around all he likes with any part of the state not read during the loop, and compute hash after hash after hash using the same buffer until he finds one that works. The state of the crypto at the start of the segment is just another part of the program state read during the loop. As long as he doesn't touch it, then the buffer will be valid.
The attacker has his oracle. The buffer is filled up instantly because it is the same buffer he used before.
In fact the attacker can do even better than this. He doesn't need to run the program "honestly" to reach his start point. He can just initialise the read variables, including the crypto state, with plausible values. If he keeps a copy of the unencrypted buffer, he could even screw around with the crypto state, reencrypting the buffer as necessary. Think of the unread state, excluding the crypto state as analogous to bitcoin's "Nonce" then the crypto state could be "ExtraNonce", there to be used if the "Nonce" is too small, with just a little extra overhead.
So we see that the FAA is like a virus that exploits the very immune system which is intended to fight it.
Of course if it's the entire program, not just a 10ms segment, that is the PoW function, then yes, I agree that it would be difficult for an attacker to craft his program, especially if the crypto is seeded by the previous block, but then we're back to limiting the program time, which I don't want to do. Additionally "difficult"/="impossible".
At this point it is my opinion that user supplied PoW is dead in the water and we need to find another way to secure the blockchain.
