Bitcoin Forum
May 19, 2022, 03:24:20 PM
 News: Latest Bitcoin Core release: 23.0 [Torrent]
 Home Help Search Login Register More
 Pages: [1]
 Author Topic: Proof of Work Question  (Read 846 times)
Arnold37
Newbie

Offline

Activity: 13
Merit: 0

 July 05, 2013, 10:29:25 PM

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.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1652973860
Hero Member

Offline

Posts: 1652973860

Ignore
 1652973860

1652973860
 Report to moderator
mustyoshi
Sr. Member

Offline

Activity: 287
Merit: 250

 July 05, 2013, 10:45:41 PM

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

Offline

Activity: 13
Merit: 0

 July 05, 2013, 11:35:21 PM

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
Donator
Legendary

Offline

Activity: 1218
Merit: 1031

Gerald Davis

 July 05, 2013, 11:52:05 PMLast edit: July 06, 2013, 12:03:34 AM by 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
Moderator
Legendary

Offline

Activity: 3668
Merit: 6162

 July 06, 2013, 01:19:43 AMLast edit: July 06, 2013, 01:34:04 AM by gmaxwell

Quote from: Arnold37
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)
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
Legendary

Offline

Activity: 1232
Merit: 1014

 July 06, 2013, 10:53:44 AM

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.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
 Pages: [1]