Is there an "additive" proof-of-work? I'm trying to find a proof-of-work algorithm with the following properties:


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.
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.
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.