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.