Useful Bitcoin Mining with a Matrix-based Puzzle

Cryptocurrency and blockchain technologies are increasingly gaining adoption since the introduction of Bitcoin, being distributed, authority-free, and secure. Proof of Work (PoW) is at the heart of blockchain’s security, asset generation, and maintenance. In most cryptocurrencies, and mainly Bitcoin, the “work” a miner must do is to solve a cryptographic puzzle: to find a random nonce that once (cryptographically) SHA-256 hashed with a perspective block header, returns a 32 Bytes number having a leading pre-defined number of zeros (called difficulty). This puzzle represents the PoW, and lives forever in the blockchain (together with the block), allowing for future verifications. The main property of this puzzle is being very hard to solve, but easy to verify. Unfortunately, solving the puzzle is a very controversial being computation-hungry process that manifests in very high energy consumption (e.g., similar to the total electricity consumption of Denmark in 2020). Although other environment-friendly solutions are being suggested, e.g., Proof of Stake, the Bitcoin community has no plans to change the mining method using cryptographic puzzle. Shutting done the Bitcoin network is not an option either because it can disrupt the global economy with a market cap of around half trillion dollars as per today. Proof of eXercise (PoX) is an alternative puzzle that is getting more acceptance in academia. PoX suggests a matrix-based puzzle, e.g., matrix product and determinant calculation, that has close security properties to the cryptographic puzzle, but has at the same time useful benefits for the community, e.g., DNA and RNA sequencing, protein structure analysis, im-age processing, data mining [16], computational geometry, surface matching, space model analysis, etc. While computing the matrix product is very hard (which is required by design), its verification is also hard, making it infeasible. PoX proposes a probabilistic verification protocol that challenges the miner to only give the results of selected columns x rows multiplication for verification, thus making verification easy. Since selection is random, the miner cannot guess the columns x rows apriori, and thus must have computed the matrix correctly.

The goal of the project is to experiment the feasibility of this matrix-based puzzle empirically on the Sheheen super computer at KAUST. The intern will work with RC3 experts and Shaheen engineers to realize the experiments. The objectives of the project are to present to the community evidences that the proposed PoX puzzle is a reasonable alternative to the cryptographic puzzle from the security and monetization perspectives (e.g., the miner has more incentives since it gets paid by the problem proponent as well and by getting the coins while mining). The results of the project will be published or commercialized.