  Proof of Work (PoW) is a Sybil-deterrence security mechanism. It introduces
an external cost to a system by requiring computational effort to perform
actions. However, since its inception, a central challenge was to tune this
cost. Initial designs for deterring spam email and DoS attacks applied overhead
equally to honest participants and attackers. Requiring too little effort did
not deter attacks, whereas too much encumbered honest participation. This might
be the reason it was never widely adopted.
  Nakamoto overcame this trade-off in Bitcoin by distinguishing desired from
malicious behavior and introducing internal rewards for the former. This
solution gained popularity in securing cryptocurrencies and using the virtual
internally-minted tokens for rewards. However, in existing blockchain protocols
the internal rewards fund (almost) the same value of external expenses. Thus,
as the token value soars, so does the PoW expenditure. Bitcoin PoW, for
example, already expends as much electricity as Colombia or Switzerland. This
amount of resource-guzzling is unsustainable and hinders even wider adoption of
these systems.
  In this work we present Hybrid Expenditure Blockchain (HEB), a novel PoW
mechanism. HEB is a generalization of Nakamoto's protocol that enables tuning
the external expenditure by introducing a complementary internal-expenditure
mechanism. Thus, for the first time, HEB decouples external expenditure from
the reward value.
  We show a practical parameter choice by which HEB requires significantly less
external consumption compare to Nakamoto's protocol, its resilience against
rational attackers is similar, and it retains the decentralized and
permissionless nature of the system. Taking the Bitcoin ecosystem as an
example, HEB cuts the electricity consumption by half.
