It has been argued that POW is ,in fact, *the only* solution to the byzantine generals problem:
You can't prove that without iteration through all possible alternatives. Even unknown yet.
You can prove that the average of all random numbers between 0 and 1 is exactly 0.5 without averaging every possible number. That is the definition of a 'proof'