Natanael via bitcoin-dev

2017-04-18 10:34:04 UTC

To expand on this below;

Den 18 apr. 2017 00:34 skrev "Natanael" <***@gmail.com>:

IMHO the best option if we change PoW is an algorithm that's moderately

processing heavy (we still need reasonably fast verification) and which

resists partial state reuse (not fast or fully "linear" in processing like

SHA256) just for the sake of invalidating asicboost style attacks, and it

should also have an existing reference implementation for hardware that's

provably close in performance to the theoretical ideal implementation of

the algorithm (in other words, one where we know there's no hidden

optimizations).

[...] The competition would mostly be about packing similar gate designs

closely and energy efficiency. (Now that I think about it, the proof MAY

have to consider energy use too, as a larger and slower but more efficient

chip still is competitive in mining...)

What matters for miners in terms of cost is primarily (correctly computed)

hashes per joule (watt-seconds). The most direct proxy for this in terms of

algorithm execution is the number of transistor (gate) activations per

computed hash (PoW unit).

To prove that an implementation is near optimal, you would show there's a

minimum number of necessary transistor activations per computed hash, and

that your implementation is within a reasonable range of that number.

We also need to show that for a practical implementation you can't reuse

much internal state (easiest way is "whitening" the block header,

pre-hashing or having a slow hash with an initial whitening step of its

own). This is to kill any ASICBOOST type optimization. Performance should

be constant, not linear relative to input size.

The PoW step should always be the most expensive part of creating a

complete block candidate! Otherwise it loses part of its meaning. It should

however still also be reasonably easy to verify.

Given that there's already PoW ASIC optimizations since years back that use

deliberately lossy hash computations just because those circuits can run

faster (X% of hashes are computed wrong, but you get Y% more computed

hashes in return which exceeds the error rate), any proof of an

implementation being near optimal (for mining) must also consider the

possibility of implementations of a design that deliberately allows errors

just to reduce the total count of transistor activations per N amount of

computed hashes. Yes, that means the reference implementation is allowed to

be lossy.

So for a reasonably large N (number of computed hashes, to take batch

processing into consideration), the proof would show that there's a

specific ratio for a minimum number of average gate activations per

correctly computed hash, a smallest ratio = X number of gate activations /

(N * success rate) across all possible implementations of the algorithm.

And you'd show your implementation is close to that ratio.

It would also have to consider a reasonable range of time-memory tradeoffs

including the potential of precomputation. Hopefully we could implement an

algorithm that effectively makes such precomputation meaningless by making

the potential gain insignificant for any reasonable ASIC chip size and

amount of precomputation resources.

A summary of important mining PoW algorithm properties;

* Constant verification speed, reasonably fast even on slow hardware

* As explained above, still slow / expensive enough to dominate the costs

of block candidate creation

* Difficulty must be easy to adjust (no problem for simple hash-style

algorithms like today)

* Cryptographic strength, something like preimage resistance (the algorithm

can't allow forcing a particular output, the chance must not be better than

random within any achievable computational bounds)

* As explained above, no hidden shortcuts. Everybody has equal knowledge.

* Predictable and close to constant PoW computation performance, and not

linear in performance relative to input size the way SHA256 is (lossy

implementations will always make it not-quite-constant)

* As explained above, no significant reusable state or other reusable work

(killing ASICBOOST)

* As explained above, no meaningful precomputation possible. No unfair

headstarts.

* Should only rely on just transistors for implementation, shouldn't rely

on memory or other components due to unknowable future engineering results

and changes in cost

* Reasonably compact implementation, measured in memory use, CPU load and

similar metrics

* Reasonably small inputs and outputs (in line with regular hashes)

* All mining PoW should be "embarrassingly parallel" (highly

parallellizable) with minimal or no gain from batch computation,

performance scaling should be linear with increased chip size & cycle

speed.

What else is there? Did I miss anything important?

Den 18 apr. 2017 00:34 skrev "Natanael" <***@gmail.com>:

IMHO the best option if we change PoW is an algorithm that's moderately

processing heavy (we still need reasonably fast verification) and which

resists partial state reuse (not fast or fully "linear" in processing like

SHA256) just for the sake of invalidating asicboost style attacks, and it

should also have an existing reference implementation for hardware that's

provably close in performance to the theoretical ideal implementation of

the algorithm (in other words, one where we know there's no hidden

optimizations).

[...] The competition would mostly be about packing similar gate designs

closely and energy efficiency. (Now that I think about it, the proof MAY

have to consider energy use too, as a larger and slower but more efficient

chip still is competitive in mining...)

What matters for miners in terms of cost is primarily (correctly computed)

hashes per joule (watt-seconds). The most direct proxy for this in terms of

algorithm execution is the number of transistor (gate) activations per

computed hash (PoW unit).

To prove that an implementation is near optimal, you would show there's a

minimum number of necessary transistor activations per computed hash, and

that your implementation is within a reasonable range of that number.

We also need to show that for a practical implementation you can't reuse

much internal state (easiest way is "whitening" the block header,

pre-hashing or having a slow hash with an initial whitening step of its

own). This is to kill any ASICBOOST type optimization. Performance should

be constant, not linear relative to input size.

The PoW step should always be the most expensive part of creating a

complete block candidate! Otherwise it loses part of its meaning. It should

however still also be reasonably easy to verify.

Given that there's already PoW ASIC optimizations since years back that use

deliberately lossy hash computations just because those circuits can run

faster (X% of hashes are computed wrong, but you get Y% more computed

hashes in return which exceeds the error rate), any proof of an

implementation being near optimal (for mining) must also consider the

possibility of implementations of a design that deliberately allows errors

just to reduce the total count of transistor activations per N amount of

computed hashes. Yes, that means the reference implementation is allowed to

be lossy.

So for a reasonably large N (number of computed hashes, to take batch

processing into consideration), the proof would show that there's a

specific ratio for a minimum number of average gate activations per

correctly computed hash, a smallest ratio = X number of gate activations /

(N * success rate) across all possible implementations of the algorithm.

And you'd show your implementation is close to that ratio.

It would also have to consider a reasonable range of time-memory tradeoffs

including the potential of precomputation. Hopefully we could implement an

algorithm that effectively makes such precomputation meaningless by making

the potential gain insignificant for any reasonable ASIC chip size and

amount of precomputation resources.

A summary of important mining PoW algorithm properties;

* Constant verification speed, reasonably fast even on slow hardware

* As explained above, still slow / expensive enough to dominate the costs

of block candidate creation

* Difficulty must be easy to adjust (no problem for simple hash-style

algorithms like today)

* Cryptographic strength, something like preimage resistance (the algorithm

can't allow forcing a particular output, the chance must not be better than

random within any achievable computational bounds)

* As explained above, no hidden shortcuts. Everybody has equal knowledge.

* Predictable and close to constant PoW computation performance, and not

linear in performance relative to input size the way SHA256 is (lossy

implementations will always make it not-quite-constant)

* As explained above, no significant reusable state or other reusable work

(killing ASICBOOST)

* As explained above, no meaningful precomputation possible. No unfair

headstarts.

* Should only rely on just transistors for implementation, shouldn't rely

on memory or other components due to unknowable future engineering results

and changes in cost

* Reasonably compact implementation, measured in memory use, CPU load and

similar metrics

* Reasonably small inputs and outputs (in line with regular hashes)

* All mining PoW should be "embarrassingly parallel" (highly

parallellizable) with minimal or no gain from batch computation,

performance scaling should be linear with increased chip size & cycle

speed.

What else is there? Did I miss anything important?