  Most concurrent blockchain systems rely heavily on the Proof-of-Work (PoW) or
Proof-of-Stake (PoS) mechanisms for decentralized consensus and security
assurance. However, the substantial energy expenditure stemming from
computationally intensive yet meaningless tasks has raised considerable
concerns surrounding traditional PoW approaches, The PoS mechanism, while free
of energy consumption, is subject to security and economic issues. Addressing
these issues, the paradigm of Proof-of-Useful-Work (PoUW) seeks to employ
challenges of practical significance as PoW, thereby imbuing energy consumption
with tangible value. While previous efforts in Proof of Learning (PoL) explored
the utilization of deep learning model training SGD tasks as PoUW challenges,
recent research has revealed its vulnerabilities to adversarial attacks and the
theoretical hardness in crafting a byzantine-secure PoL mechanism. In this
paper, we introduce the concept of incentive-security that incentivizes
rational provers to behave honestly for their best interest, bypassing the
existing hardness to design a PoL mechanism with computational efficiency, a
provable incentive-security guarantee and controllable difficulty.
Particularly, our work is secure against two attacks to the recent work of Jia
et al. [2021], and also improves the computational overhead from $\Theta(1)$ to
$O(\frac{\log E}{E})$. Furthermore, while most recent research assumes trusted
problem providers and verifiers, our design also guarantees frontend
incentive-security even when problem providers are untrusted, and verifier
incentive-security that bypasses the Verifier's Dilemma. By incorporating ML
training into blockchain consensus mechanisms with provable guarantees, our
research not only proposes an eco-friendly solution to blockchain systems, but
also provides a proposal for a completely decentralized computing power market
in the new AI age.
