Proof of Work Question

[Arnold37]

Is it possible to make a proof of work scheme where you can prove how many iterations you have done without redoing the whole calculation?

Psuedocode Example:

var Value = StartValue;

Repeat(x)
{
     Value = IteratePoW(Value);
}

bool is50Iteration = ValidatePoW(StartValue, Value, 50);
if(is50Iteration)
{
    //Accept block
}
else
{
    //Deny block
}

Why I wonder about it is because it might be the requirement for a more energy efficient p2p Currency.

[1715555470]

1715555470

[1715555470]

1715555470

[1715555470]

1715555470

[1715555470]

1715555470

[1715555470]

1715555470

[mustyoshi]

How does increasing the amount of work, increase the energy efficiency?

[Arnold37]

If you can deterministically decide who will solve the next block depending on the result from such a proof of work scheme you would theoretically only need one active node that does the proof of work. That way the proof of work actually becomes a proof of CPUtime and has a difficulty roof because the answer needs to be iterated(=forced to 1 CPU thread) = limited amount of energy required to secure the blockchain.

[DeathAndTaxes]

Simple answer is no.  This is why Bitcoin all crypto-currencies use the random output of a hash function to approximate a given amount of work.

You in theory could solve a block of any difficulty with a single attempted hash or not solve a block even given a magnitude more attempts than difficulty suggests however neither of this single rare events are of much consequence.  To attack a network in any meaningful manner requires a large number of blocks and in the long run it will take "on average"  2^32 * Difficulty attempts to find a solution.

[gmaxwell]

Is it possible to make a proof of work scheme where you can prove how many iterations you have done without (the verifier) redoing the whole calculation?

Yes, with a number of conditions.

First, we need "iterations" which can be done in parallel:

E.g.

Code:

for i in 0..10: output[i] = pow(i)

instead of:

Code:

output[i] = pow(output[i-1])

Given that, say we're going to do 65536 iterations.

Code:

for i 0..65535:
  output[i] = pow(i)

Now arrange the output_i  into the leafs of a fully populated binary tree.  It will have a depth of 16 levels for 65536 iterations.  At each node in the tree hash its children... just like a transaction hash tree in Bitcoin.

Take the first ~128 bits of the root hash and use as indexes to pick eight unique iteration outputs.

Collect those outputs along with the tree fragments that connect them up to the root.

Your proof of work is the eight solutions and the connecting tree fragments.  This demonstrates with high probability that all the work was actually done— an attacker who only did eight of the iterations then searched for a random value that specified his 8 would have to do 2^128 work. You can twiddle the numbers for a bandwidth/security tradeoff.

This is called non-interactive cut and choose and it's often used in various kinds of zero knowledge proof.

If you were specifically wanting a _serial_ proof of work— then no, one can't be constructed. Unless you make everyone work on the same problem (and then its a race, which _bad_) anyone can use the randomization to convert an arbitrarily serial POW into a fully parallel one.

[TierNolan]

Your proof of work is the eight solutions and the connecting tree fragments.  This demonstrates with high probability that all the work was actually done— an attacker who only did eight of the iterations then searched for a random value that specified his 8 would have to do 2^128 work. You can twiddle the numbers for a bandwidth/security tradeoff.

This is called non-interactive cut and choose and it's often used in various kinds of zero knowledge proof.

This is similar to what I suggested in another thread.

The scheme I suggested was that there is a cost imposed for making claims.  If it costs X to make a claim and there is a 99.9% chance you will lose X if the claim is false, then that POW can guranteed 1000X as POW.

I guess if the odds of being caught are high enough, then you don't even need the guarantee, since the cost of generating a fake is enough disincentive.

The advantage was that a user could show that they did N hashes and not have to worry about variance.