Relaunched Completely

[Cryptorials]

I think I might be confusing myself here, but I was just reading over the whitepaper and the description of partial blocks. Each partial block which meets the requirements for the 'hooks' which the author puts in place gets a reward, even though they do not actually mine the block. If these hooks were a requirement for submitting work rather than an option, and if there is a minimum requirement for the number of payouts, would that not mean that our attacker with a faster algorithm would still only recoup part of what they paid to submit their slower algorithm to the network? For example, if his faster algorithm is twice as fast, then you only need three payouts and there is already a probable cost to the attack.

It looks like you guys are still making progress on making the faster algorithm attack impossible, but if that doesn't work out then perhaps it could be made prohibitively expensive by tweaking these variables? Or at least the computational overhead necessary to secure the network may be reduced by factoring in the financial overhead associated with the attack?

[Dazza]

My idea was to carry a variable that is initially seeded with the input to the algorithm. Then, with a yet-to-be-defined distribution random operations are added in between the lines of the original PoW function that perform changes to that new variable (here, it could frequently mix in the state in some form). As you pointed out, this boils down to creating some level of overhead that a faster-algorithm attacker needs to additionally perform to his handcrafted PoW function.

This is close enough to my scheme that I may as well just spell it out.

Declare a buffer of length L.  L is a network wide (and possibly varying) parameter and is the deterministic proxy for time.  "After 10ms" means deterministically "when the buffer is full".

As each executable statement is executed, write to the buffer the statement number followed by the list of variable assignments effected by that statement.  So for example, if in the C language, statement 100 was

Code:

a = b = c + d++

(I don't know if you can do that in python), and if before the statement was executed c=3 and d=4, then you would write to the buffer

Code:

100,a=7,b=7,d=5

And write all of this, even if b was already equal to 7, so was not changed (but could have been).  c can not have changed so doesn't need to be written.

I would argue that to write that buffer is by definition to run the program.  What does "running a program" even mean, if not to determine the sequence of changes to state defined by its statements?  If "work" means "runs the program" than I cannot think of a definition of the phrase "proof of work" that is not satisfied by writing that buffer.  Yet still an adversary could craft a program that writes the buffer in a way that he can predict using a faster algorithm.

But lets not worry about that now.  Instead, let me continue with my idea.  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.

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.

Finally let's take a look at how your idea fits into this:

My idea was to carry a variable that is initially seeded with the input to the algorithm. Then, with a yet-to-be-defined distribution random operations are added in between the lines of the original PoW function that perform changes to that new variable (here, it could frequently mix in the state in some form).

This is equivalent to encrypting the buffer using the seed as a key.  I have also had this idea.  It adds overhead that the adversary cannot avoid, but no more security because the attacker knows the key.  It's like DRM when the attacker is in the box.