That's almost exactly my off the cuff suggestion. Of course my brain is seeded by both bitcoin (finding a hash as proof of work) and HLL (which counts leading hash digits to estimate set cardinality).