  We propose an application for near-term quantum devices: namely, generating
cryptographically certified random bits, to use (for example) in proof-of-stake
cryptocurrencies. Our protocol repurposes the existing "quantum supremacy"
experiments, based on random circuit sampling, that Google and USTC have
successfully carried out starting in 2019. We show that, whenever the outputs
of these experiments pass the now-standard Linear Cross-Entropy Benchmark
(LXEB), under plausible hardness assumptions they necessarily contain
$\Omega(n)$ min-entropy, where $n$ is the number of qubits. To achieve a net
gain in randomness, we use a small random seed to produce pseudorandom
challenge circuits. In response to the challenge circuits, the quantum computer
generates output strings that, after verification, can then be fed into a
randomness extractor to produce certified nearly-uniform bits -- thereby
"bootstrapping" from pseudorandomness to genuine randomness. We prove our
protocol sound in two senses: (i) under a hardness assumption called Long List
Quantum Supremacy Verification, which we justify in the random oracle model,
and (ii) unconditionally in the random oracle model against an eavesdropper who
could share arbitrary entanglement with the device. (Note that our protocol's
output is unpredictable even to a computationally unbounded adversary who can
see the random oracle.) Currently, the central drawback of our protocol is the
exponential cost of verification, which in practice will limit its
implementation to at most $n\sim 60$ qubits, a regime where attacks are
expensive but not impossible. Modulo that drawback, our protocol appears to be
the only practical application of quantum computing that both requires a QC and
is physically realizable today.
