  Nakamoto consensus underlies the security of many of the world's largest
cryptocurrencies, such as Bitcoin and Ethereum. Common lore is that Nakamoto
consensus only achieves consistency and liveness under a regime where the
difficulty of its underlying mining puzzle is very high, negatively impacting
overall throughput and latency. In this work, we study Nakamoto consensus under
a wide range of puzzle difficulties, including very easy puzzles. We first
analyze an adversary-free setting and show that, surprisingly, the common
prefix of the blockchain grows quickly even with easy puzzles. In a setting
with adversaries, we provide a small backwards-compatible change to Nakamoto
consensus to achieve consistency and liveness with easy puzzles. Our insight
relies on a careful choice of \emph{symmetry-breaking strategy}, which was
significantly underestimated in prior work. We introduce a new method --
\emph{coalescing random walks} -- to analyzing the correctness of Nakamoto
consensus under the uniformly-at-random symmetry-breaking strategy. This method
is more powerful than existing analysis methods that focus on bounding the
number of {\it convergence opportunities}.
