A new algorithm by computing scientists at the University of Alberta could be the first step in reducing the massive amounts of energy and computing power it takes to mine cryptocurrencies like Bitcoin.
"Each new Bitcoin transaction must be validated in a process called Bitcoin mining-a computationally expensive problem," said Md Solimul Chowdhury, lead author of the study and PhD candidate in the Department of Computing Science.
"The computational difficulty of this task means mining programs need to run for long hours, sometimes even for days."
The difficulty of mining new Bitcoin is part of what makes it both scarce and valuable-currently valued at about C$13,600 per bitcoin.
Chowdhury explained that the electrical power needed to perform the computation has a massive carbon footprint-a growing concern for the Bitcoin mining industry.
"The traditional brute-force method of Bitcoin mining has a carbon footprint of between 22 and 22.9 megatonnes per year, on par with a big city like Vienna or Las Vegas," said Chowdhury, who is studying under the supervision of computing scientists Martin Müller and Jia You.
"One potential solution to this problem is to make the mining process faster."
New solution to a familiar problem
The researchers' new technique takes on a computational problem known as the Boolean satisfiability (SAT) problem, which is well known in computing science and has applications in hardware design, software testing and encryption-and Bitcoin mining.
"Our algorithm, expSAT, was evaluated against a series of tests to determine its strengths and what applications it is best suited for," said Chowdhury. "We found that it performs extremely well at tackling SATCoin benchmarks, which correspond to Bitcoin mining problems-outperforming standard solvers in this testing scenario."
Chowdhury noted the algorithm is still in its early stages and will need more research and tailoring before it can be used in the industry, but early results are promising.
"The initial success of the expSAT approach has been demonstrated in the latest SAT competition, SAT Race 2019, on a wide range of benchmarks. One of our submitted solvers made it to the top tier competing against other state-of-the-art approaches," he said.
"This performance gain with the SATCoin benchmark indicates that expSAT has the potential to become the next state-of-the-art method for Bitcoin mining via SATCoin, and in turn, potentially reduce the carbon footprint for the Bitcoin mining industry."
The study, "Guiding CDCL SAT Search via Random Exploration Amid Conflict Depression," was published in the proceedings of the 34th Association for the Advancement of Artificial Intelligence (AAAI) Conference on Artificial Intelligence.