A new algorithm by UAlberta researchers could help speed up the computation problem that makes Bitcoin mining so time-consuming, making it more energy-efficient. Photo credit: André François McKenzie (Unsplash)
The same difficulty of calculation that gives cryptocurrencies like Bitcoin their value is posing a problem: a massive carbon footprint in energy consumption. But a new algorithm by University of Alberta computing scientists could be the first step in developing faster, greener solutions to a computational problem behind it—with other industry applications, as well.
“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 paper 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 $13.6K CDN per Bitcoin. Chowdhury explained that the electrical power required to perform this computation has an associated carbon footprint—one that’s a growing concern.
“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, studying under the co-supervision of Martin Müller, DeepMind Chair in Artificial Intelligence, and Jia You, both professors in the Department of Computing Science. “Such a carbon footprint is a serious concern, and how to reduce this prohibitively large carbon footprint is a big challenge for the bitcoin mining industry. One potential solution to this problem is to make the mining process faster.”
And the researchers have done just that, with a new technique they’re calling expSAT, which takes on the Boolean Satisfiability (SAT) problem, a well-known hard computational problem with applications not only in bitcoin mining, but hardware design, software testing, and encryption.
“SAT has significant applications in many fields of computer science and artificial intelligence. 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.”
Those promising results could have a big impact on the mining industry and reducing its energy consumption—but Chowdhury notes that the algorithm is still in its early stages, and will require more research and further tailoring before being used in industry.
“The initial success of the expSAT approach has been demonstrated in the latest SAT competition, SAT Race 2019 on a wide range of benchmarks, where one of our submitted solvers made it to the top tier competing against other state-of-the-art approaches,” said Chowdhury. “This extremely high 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 paper “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.