2
$\begingroup$

I'm trying to find a proof-of-work algorithm with the following properties:

  1. If A(1) is a proof of work with Difficulty(A(1))=n (requires n basic operations on average), then one can find a proof of work A(2)=F(A(1)) with Difficulty(A(2))=Difficulty(A(1))+n by performing approximately n operations.

  2. The size of A(i) is be bounded by the logarithm of Difficulty(A(i)) (the accumulated difficulty).

One way to achieve this is to choose a problem which allows approximating the solution that also has a fast method to find out the approximation error. Then performing the proof of work consist of refining the best previous solution.

For example, approximating the real square root of 2 may satisfy property 1, but it does not satisfy property 2. In some finite groups finding a non-trivial root is hard, and the proof is bounded in size, but property 1 is not satisfied.

I was also thinking that maybe a variant of Very smooth hash may work, or a group-theoretic hash function, buy I haven't figure out how.

The idea is that if such function is used for PoW of a block-chain, then comparing the difficulty of two competing chains is reduced to comparing the difficulties of two blocks.

There is a solution in Bitcoin involving using Merkle trees of previous blocks and SPV proofs, but I'm looking for a proof whose size is strictly bounded.

Improve this question
$\endgroup$
6
  • $\begingroup$ Are you looking for a challenge-response or a solution-verification algorithm? Is it okay for the proof of work to also inherently allow extending the solution? As in, anyone you prove your work to can use it as a starting point with no extra information. $\endgroup$
    – John Meacham
    Commented Nov 20, 2014 at 0:18
  • $\begingroup$ How about take a random IV and put it through a cryptographic hash, take the hash result and use it to construct a random weighted graph via a deterministic algorithm. proof of work is the IV and a minimum spanning tree of the graph constrained to 2 edges per node (travelling salesman), work done is how close your minimum is to the statistically expected minimum. It will eventually 'run dry' and you are relying on assumptions about how to estimate the minimum and maximum spanning trees of random graphs, but those seem surmountable. $\endgroup$
    – John Meacham
    Commented Nov 20, 2014 at 0:29
  • $\begingroup$ oh, once it 'runs dry' you can use the hash of the best solution to seed a new bigger graph to keep it going indefinitely. Not sure how to evaluate how fast this grows but i think it can be made to be within your bounds. $\endgroup$
    – John Meacham
    Commented Nov 20, 2014 at 0:32
  • $\begingroup$ The proposal has some merits, but fails to satisfy the requeriments in several aspects: the proof size is unbounded, as long as the graph expands. Also the additive propery is lost when a new graph needs to be created, since you need to verify all previous graphs. Last, it would be very hard to set the difficulty increments in such a way that every increment corresponds to a predefined work. $\endgroup$
    – SDL
    Commented Nov 21, 2014 at 2:03
  • $\begingroup$ No, the proof is a bitset that never grows. it simply has a single bit for every pair of nodes for whether it is in the spanning tree or not. You need not include the graph or its weight because it is generated algorithmically via a hash of the IV. the proof of work is constant in size. Completely random graphs have fairly predictable qualities so i think you should be able to get a useful measure of work out of it. The only time the proof of work grows is when you completely exhaust a graph in which case it becomes the IV for the next one, but you can delay that indefinitely by going bigger. $\endgroup$
    – John Meacham
    Commented Nov 21, 2014 at 21:35

1 Answer 1

Reset to default
2
$\begingroup$

Your property of what I would call "improvable" is actually considered undesirable for PoWs. It would allow a prover to make continuous progress toward a solution that satisfies the difficulty threshold. Which would mean that a prover that's twice as fast as another, has more than double the chance to win the race, which is considered unfair. Being twice as fast should just double your expected wins.

So in fact a PoW should be what is known as "progress free", which would seem to require not having your property.

Improve this answer
$\endgroup$
3
  • $\begingroup$ It's still progress-free, because each PoW A(i) is progress-free, and each block would need a single proof step (from A(n) to A(n+1)) and not many steps. $\endgroup$
    – SDL
    Commented Oct 26, 2015 at 16:28
  • $\begingroup$ Your original description suggested to me that you intend for many consecutive improvement steps. Otherwise "comparing the difficulty of two competing chains is reduced to comparing the difficulties of two blocks" makes no sense to me, as the PoW of the blocks you compare would need to be cumulative over the whole chain. $\endgroup$
    – John Tromp
    Commented Oct 27, 2015 at 17:34
  • $\begingroup$ That's the idea. For example, the High-Value-Hash Highway (bitcointalk.org/index.php?topic=98986.msg1083483#msg1083483) allows one to build a cumulative proof-of-work, over the whole chain, but its size is not bounded by the logarithm of the difficulty, but bounded by the logarithm of the chain length. $\endgroup$
    – SDL
    Commented Dec 9, 2015 at 22:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.