  Several emerging PoW blockchain protocols rely on a "parallel-chain"
architecture for scaling, where instead of a single chain, multiple chains are
run in parallel and aggregated. A key requirement of practical PoW blockchains
is to adapt to mining power variations over time. In this paper, we consider
the design of provably secure parallel-chain protocols which can adapt to such
mining power variations.
  The Bitcoin difficulty adjustment rule adjusts the difficulty target of block
mining periodically to get a constant mean inter-block time. While
superficially simple, the rule has proved itself to be sophisticated and
successfully secure, both in practice and in theory. We show that natural
adaptations of the Bitcoin adjustment rule to the parallel-chain case open the
door to subtle, but catastrophic safety and liveness breaches. We uncover a
meta-design principle that allow us to design variable mining difficulty
protocols for three popular PoW blockchain proposals (Prism, OHIE, and
Fruitchains) inside a common rubric.
  The principle has three components:(M1) a pivot chain, based on which blocks
in all chains choose difficulty, (M2) a monotonicity condition for referencing
pivot chain blocks and (M3) translating additional protocol aspects from using
levels (depth) to using "difficulty levels". We show that protocols employing a
subset of these principles may have catastrophic failures. The security of the
designs is also proved using a common rubric - the key technical challenge
involves analyzing the interaction between the pivot chain and the other
chains, as well as bounding the sudden changes in difficulty target experienced
in non-pivot chains. We empirically investigate the responsivity of the new
mining difficulty rule via simulations based on historical Bitcoin data, and
find that the protocol very effectively controls the forking rate across all
the chains.
