# Is there an "additive" proof-of-work?

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.

• 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. Nov 20, 2014 at 0:18
• 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. Nov 20, 2014 at 0:29
• 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. Nov 20, 2014 at 0:32
• 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.
– SDL
Nov 21, 2014 at 2:03
• 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. Nov 21, 2014 at 21:35