Blockchains have recently gained popularity thanks to their ability to record
"digital truth". They are designed to keep persistence, security, and avoid
attacks which is useful for many applications. However, they are still
problematic in their energy consumption, governance, and scalability Current
solutions either require vast computing power via Proof-of-Work (PoW) or cannot
directly utilize computing power as a resource in virtual mining. Here, we
propose incentive-based protocols that use competitions to integrate computing
power into blockchains. We introduce Proof-of-Accumulated-Work (PoAW): miners
compete in costumer-submitted jobs, accumulate recorded work whenever they are
successful, and, over time, are remunerated. The underlying competition
replaces the standard hash puzzle-based competitions of PoW. A competition is
managed by a dynamically-created small masternode network (dTMN) of invested
miners. dTMNs allow for scalability as we do not need the entire network to
manage the competition. Using careful design on incentives, our system
preserves security, avoids attacks, and offers new markets to miners. When
there are no costumers the system converges into a standard protocol. Our
proposed solution improves the way by which the blockchain infrastructure works
and makes use of its computing power. We also discuss how the protocol can be
used by fields that require solving difficult optimization problems, such as
Artificial Intelligence and Pattern Recognition in Big Data.