Strategy: The probability that there exists a much higher-level superchain is negligible. So the levels of proofs are bound. The top level will have few blocks (close to m) whp. The probability that each level has much more than 2m supporting blocks for the one above is low. Therefore the number of blocks in the proof is ~(lgC)
dionyziz
commented
7 years ago
Theorem: NiPoPoWs are succinct whp.
Strategy: The probability that there exists a much higher-level superchain is negligible. So the levels of proofs are bound. The top level will have few blocks (close to m) whp. The probability that each level has much more than 2m supporting blocks for the one above is low. Therefore the number of blocks in the proof is ~(lgC)