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.