André François McKenzie on UnsplashA new algorithm developed by University of Alberta computer scientists could radically change approaches to computational problem-solving, with likely improvements in things ranging from artificial intelligence to bitcoin mining.
Md Solimul Chowdhury, a PhD candidate in the Department of Computer Science, is part of the team behind expSAT, a new algorithm looking to streamline approaches to solving the Boolean Satisfiability (SAT) problem. SAT is a complex computational problem that is at the heart of decision making in artificial intelligence, the encryption that process that gives bitcoins their value, software verification and a host of other computational problems.
With expSAT, Chowdhury and his team are hoping to optimize the problem solving process with an algorithm that spends less time in the computational “dead-zones” that make traditional methods so time-consuming.
“The existing set-solving algorithm goes through some sort of depression phase where it doesn’t find any fruits for what it is designed for,” Chowdhury said. “What our expSAT algorithm does is it performs randomized exploration in the solution space to find more promising actions that it can take.”
Chowdhury and his team — whose work is primarily focused on improving computational problem-solving with regards to artificial intelligence — tested expSAT against a variety of benchmarks and found that the algorithm was particularly adept at decoding encrypted bitcoins, a process known as “bitcoin mining.”
“We have our algorithm, and we have tested it in a diversity of benchmarks, and [it] turns out that bitcoin was the most efficient application for our algorithm,” Chowdhury said. “We never set out to design an algorithm to solve bitcoin efficiently.”
That being said, he is aware of how significant that added efficiency could be, especially in a field where the complexity of the mining process has led to the use of evermore powerful and consumptive supercomputers.
“For the bitcoin mining industry the current rate [of pollution] is like 22.9 megatons per year of carbon. That amounts to the carbon footprint of big cities like Las Vegas,” Chowdhury said. “What we have observed from the experiments is that our technique is extremely efficient for the bitcoin mining problem.”
Despite the potential for expSAT to save time, money and energy, Chowdhury recognizes that his team’s research is still in its preliminary stages. Chowdhury also acknowledges that certain barriers may stand in the way of widespread implementation of their algorithm.
“There’s currently some political impediments,” Chowdhury said. “Like current industries revolving around the brute force method and all the infrastructure is built around that. To replace that one and put SAT-based bitcoin mining would be a challenge, but I think that with more research people will start to see the potential of this technique in bitcoin mining [and] we may see some changes.”
The expSAT technique was first described in Chowdhury and his team’s article “Guiding CDCL SAT Search via Random Exploration amid Conflict Depression” which was published in the proceedings of the 34th Association for the Advancement of Artificial Intelligence (AAAI) Conference on Artificial Intelligence.
Ultimately though, Chowdhury and his team are confident in the capabilities of their algorithm.
“In my opinion, SAT solving should be more efficient for bitcoin mining than the brute force method because these algorithms explore the structure of a given problem while the brute force method doesn’t do it. I have the intuition that it has more potential for reducing the carbon footprint of the bitcoin mining industry.”
