During the past two years, IEEE Spectrum has spotlighted several new approaches to solving combinatorial optimization problems, particularly Fujitsu’s Digital Annealer and more recently Toshiba’s Simulated Bifurcation Algorithm. Now, researchers at the Tokyo Institute of Technology, with help from colleagues at Hitachi, Hokkaido University, and the University of Tokyo, have engineered a new annealer architecture to deal with this kind of task that has proven too taxing for conventional computers to deal with.

Dubbed STATICA (Stochastic Cellular Automata Annealer Architecture), the processor is designed to take on challenges such as portfolio, logistic, and traffic flow optimization when they are expressed in the form of Ising models.

Originally used to describe the spins of interacting magnets, Ising models can also be used to solve optimization problems. That’s because the evolving magnetic interactions in a system progress towards the lowest-energy state, which conveniently mirrors how an optimization algorithm searches for the best—i.e. ground state—solution. In other words, the answer to a particular optimization question becomes the equivalent of searching for the lowest energy state of the Ising model.

Current annealers such as D-Wave’s quantum annealer computer and Fujitsu’s Digital Annealer calculate spin-evolutions serially, points out Professor Masato Motomura at Tokyo Tech’s Institute of Innovative Research and leader of the STATICA project. As one spin affects all the other spins in a given iteration, spin switchings are calculated one by one, making it a serial process. But in STATICA, he notes, that updating is performed in parallel using stochastic cellular automata (SCA). That is a means of simulating complex systems using the interactions of a large number of neighboring “cells” (spins in STATICA) with simple updating rules and some stochasticity (randomness).

In conventional annealing systems, if one spin flips, it affects all of the connected spins and therefore all the spins must be processed in the next iteration. But in STATICA, SCA introduces copies (replicas) of the original spins into the process. All original spin-spin interactions are redirected to their individual replica spins.

Diagrams comparing conventional and proposed spin-spin interactions

“In this method, all the replica spins are updated in parallel using these spin-spin interactions,” explains Motomura.” If one original spin flips, it affects its replica spin but not any of the other original spins because there is no interaction between them, unlike conventional annealing. And in the next iteration, the replica spins are interpreted as original spins and the parallel spin-update is repeated.

As well as enabling paralleling processing, STATICA also uses pre-computed results to reduce computation. “So if there is no spin-flip, there is nothing to compute,” says Motomura. “And if the influence of a flipped spin has already been computed, that result is reused.”

STATICA processor designImage: Tokyo Institute of Technology

For proof of concept, the researchers had a 3-by-4-mm STATICA chip fabricated using a 65-nm CMOS process operating at a frequency of 320 megahertz and running on 649 milliwatts. Memory comprises a 1.3 megabit SRAM. This enabled an Ising model of 512 spins, equivalent to 262,000 connections, to be tested.

“Scaling by at least two orders of magnitude is possible,” notes Motomura. And the chip can be fabricated using the same process as standard processors and can easily be added to a PC as a co-processor, for instance, or added to its motherboard.

STATICA chip mounted on a circuit board with a USB connection and connected to a laptop PC as proof of conceptPhoto: Tokyo Institute of Technology

“At the ISSCC Conference in February, where we presented a paper on STATICA, we mounted the chip on a circuit board with a USB connection,” he says, “and demonstrated it connected to a laptop PC as proof of concept.”

To compare STATICA’s performance against existing annealing technologies (using results given in published papers), the researchers employed a Maxcut benchmark test of 2,000 connections. STATICA came out on top in processing speed, accuracy, and energy efficiency. Compared with its nearest competitor, Toshiba’s Simulated Bifurcation Algorithm, STATICA took 0.13 milliseconds to complete the test, versus 0.5 ms for SBA. In energy efficiency, STATICA ran on an estimated 2 watts of power, far below the to 40 watts for SBA. And in histogram comparisons of accuracy STATICA also came out ahead, according to Motomura.

For the next step, he says the team will scale up the processor and test it out using realistic problems. 

Other than that, there are no more technology hurdles to overcome. 

“STATICA  is ready,” states Motomura. “The only question is whether there is sufficient market demand for such an annealing processor. We hope to see interest, for instance, from ride-sharing companies like Uber, and product distributors such as Amazon. Local governments wanting to control problems such as traffic congestion might also be interested. These are just a few examples of how STATICA might be used besides more obvious applications like portfolio optimization and drug discovery.”

The Conversation (0)

The Spectacular Collapse of CryptoKitties, the First Big Blockchain Game

A cautionary tale of NFTs, Ethereum, and cryptocurrency security

8 min read
Vertical
Mountains and cresting waves made of cartoon cats and large green coins.
Frank Stockton
Pink

On 4 September 2018, someone known only as Rabono bought an angry cartoon cat named Dragon for 600 ether—an amount of Ethereum cryptocurrency worth about US $170,000 at the time, or $745,000 at the cryptocurrency’s value in July 2022.

It was by far the highest transaction yet for a nonfungible token (NFT), the then-new concept of a unique digital asset. And it was a headline-grabbing opportunity for CryptoKitties, the world’s first blockchain gaming hit. But the sky-high transaction obscured a more difficult truth: CryptoKitties was dying, and it had been for some time.

The launch of CryptoKitties drove up the value of Ether and the number of transactions on its blockchain. Even as the game's transaction volume plummeted, the number of Ethereum transactions continued to rise, possibly because of the arrival of multiple copycat NFT games.

That perhaps unrealistic wish becomes impossible once the downward spiral begins. Players, feeling no other attachment to the game than growing an investment, quickly flee and don’t return.

Whereas some blockchain games have seemingly ignored the perils of CryptoKitties’ quick growth and long decline, others have learned from the strain it placed on the Ethereum network. Most blockchain games now use a sidechain, a blockchain that exists independently but connects to another, more prominent “parent” blockchain. The chains are connected by a bridge that facilitates the transfer of tokens between each chain. This prevents a rise in fees on the primary blockchain, as all game activity occurs on the sidechain.

Yet even this new strategy comes with problems, because sidechains are proving to be less secure than the parent blockchain. An attack on Ronin, the sidechain used by Axie Infinity, let the hackers get away with the equivalent of $600 million. Polygon, another sidechain often used by blockchain games, had to patch an exploit that put $850 million at risk and pay a bug bounty of $2 million to the hacker who spotted the issue. Players who own NFTs on a sidechain are now warily eyeing its security.

Remember Dragon

The cryptocurrency wallet that owns the near million dollar kitten Dragon now holds barely 30 dollars’ worth of ether and hasn’t traded in NFTs for years. Wallets are anonymous, so it’s possible the person behind the wallet moved on to another. Still, it’s hard not to see the wallet’s inactivity as a sign that, for Rabono, the fun didn’t last.

Whether blockchain games and NFTs shoot to the moon or fall to zero, Bladon remains proud of what CryptoKitties accomplished and hopeful it nudged the blockchain industry in a more approachable direction.

“Before CryptoKitties, if you were to say ‘blockchain,’ everyone would have assumed you’re talking about cryptocurrency,” says Bladon. “What I’m proudest of is that it was something genuinely novel. There was real technical innovation, and seemingly, a real culture impact.”

This article was corrected on 11 August 2022 to give the correct date of Bryce Bladon's departure from Dapper Labs.

This article appears in the September 2022 print issue as “The Spectacular Collapse of CryptoKitties.”

Keep Reading ↓Show less
{"imageShortcodeIds":[]}