Bitcoin Forum

I just read up about Non-Interactive Proofs of Proofs of Work from this white paper: https://eprint.iacr.org/2019/226.pdf .

Just wondering what the current thoughts them is and if they are likely to be implemented into Bitcoin at any point in the future.

I see one big problem with implementing this super-light client verifier and it's that since this algorithm only requires O(log(n)) block headers to be downloaded (to the base e I assume) applying it to Bitcoin's block height of around 650K will result in FlyClient retrieving only 13 or 14 blocks. It's far too little to assume the validity of a chain with them, especially if the blocks are spaced in equal intervals. There's going to be just one block header downloaded for every 50,000 blocks.

O(log n) can be anything of the form a + b * log n.
In the case of flyclient a could be over 1000, and b over 10.
It also requires a bitcoin header to commit to a merkle tree of all previous headers,
and perhaps the cumulative difficulty.

This makes me feel relieved, as I had applied the run-time function literally.

Still there's another hurdle, maybe even two, to overcome. It uses a probability distribution with the difficulty as input and returns the chance that it's block will be used in the proof. First off the difficulty of bitcoin mining is ever-increasing and this distribution takes difficulties on a scale from 0 to 1. It means every time the mining difficulty breaks a high, each and every full node has to compute the new difficulty "percentage" (a terrible name but let's just call it that) for all of the blocks, and I imagine this is not going to take as much time as transaction verification but you are still processing 650K+ blocks so... that's going to take a few hours on average.

If the difficulty breaks a new high during that period this reassignment has to be aborted and it has to start all over again.

The second hurdle is choosing a probability distribution for choosing the blocks. Even if there are no major hot spots in the blockchain that may need more verification (because of user-developer drama so theoretically are the first targets by rouges) such as the blocks around the segwit and taproot activation blocks, as I mentioned above the difficulty is ever changing so choosing a new probability distribution that mostly corresponds to the blocks it previously selected will be challenging because you keep having to compute it again.

This also assumes that there's a 1-to-1 mapping between the difficulties and blocks, which shouldn't be a problem except maybe for the earliest blocks with near-zero difficulty.