Brown CS News

Click the links that follow for more news about Maurice Herlihy and other recent accomplishments by Brown CS faculty and alums.

Looking back on the past few years, it’s difficult to remember a month or even a week when blockchains weren’t making news. But in the wake of various cryptocurrency crashes, have we reached Peak Blockchain? Not even close, say three computer scientists whose work may help fuel considerable speed increases for the technology as its reach expands far beyond Bitcoin and its competitors.

“With blockchains,” says Maurice Herlihy, An Wang Professor of Computer Science at Brown University, “we have a Volkswagen engine because that’s the way things evolved out of necessity. Our research is trying to replace it with a Maserati.”

That speedup, he says, is particularly important when we consider the many industries looking to benefit from blockchain’s reliability and decentralization. “Most people aren’t going to become cryptocurrency speculators, but blockchains could someday be used for everything from monitoring the freshness of produce to trading stocks to tracking items that move through the planet’s biggest supply chains. They’re conceivably a good fit for any interaction in which parties have a discussion process and are interested in coming to a conclusion.”

But first, there’s a big hurdle to overcome: there’s only one bathroom, so to speak, and one key.

“If we use Bitcoin as an example,” says Assistant Professor Eric Koskinen of Stevens Institute of Technology, one of Maurice’s collaborators, “it’s simple: you have some money, you can break it into smaller pieces, and you can transfer those pieces to other people. Other cryptocurrencies, such as Ethereum, have built on this by offering smart contracts.” 

Smart contracts are small programs associated with transactions, he explains, so you could have your money transfer automatically when the moon is full on a Thursday. Because they don’t require functionaries to get involved, they add a great deal of versatility. Unfortunately, they also present a massive bottleneck. To avoid conflicts, all smart contracts, even unrelated ones, only operate one at a time.

“In the beginning,” Maurice explains, “blockchains worked that way for simplicity’s sake, because it was easier to program. For an analogy, think of a thousand people wanting to buy concert tickets at the same time, and the software doesn’t want two people getting the same seat. When you’re picking your seat, you have a lock on the database, just like a bathroom lock that only lets one person in at a time.”

So, how to get around that limitation? Inspiration came in the form of transactional memory techniques, which allow for easier and faster development of programs that operate simultaneously. Maurice and Eric had collaborated on some of these methods, such as transactional boosting, as far back as 2008. 

“We felt like the ideas that went into transactional memory would be a good fit for adding concurrency to smart contracts,” says Eric. Ethereum data, he explains, is stored in a structure known as a hash table, and Ethereum transactions are built by reading from and writing to the hash table. “Our work detects when simultaneous transactions might try to access the same part of the hash table, and pauses smart contracts to ensure that they proceed carefully. In this way, you can make high-level statements like ‘X and Y are independent’ and then the system finds a way to let them happen at the same time.” A bit of advance planning and coordination, in other words, can ensure that smart contracts interact with minimal fuss. 

This idea led to a paper (and a patent application) with Thomas Dickerson (Brown CS PhD '19, advised by Maurice with Eric also on his committee) and Paul Gazzillo.

Maurice and Eric needed to evaluate the effectiveness of their methods, but implementing them across the entire Ethereum virtual machine would have required a massive effort. The next best option? A simulation, which could model the effect that transactional memory techniques and concurrency might have. That’s where Vikram Saraph (now at Facebook, he earned his PhD from Brown with Maurice as his advisor) entered the picture.  

“A blockchain’s transactional data is never thrown out,” he says, “which makes it a historian’s paradise. So to evaluate how concurrent execution techniques might work in the future, I applied them to smart contracts from earlier in Ethereum’s history.” 

It was a bit of archaeology in the service of better engineering, focusing on the period of time from July of 2016 to December of 2017. After looking at the Ethereum source code, Vikram thought about what he wanted to re-execute in parallel and then created his simulation, which walks through the instruction sets of the smart contracts to see what would affect simultaneous execution. The goal was to see a speed increase.

“But in simulations,” he explains, “you don’t have an obvious measure for time. As a proxy, you can think about what instructions cost, because certain instructions require a payment to Ethereum. It’s a hypothetical way of evaluating the speedup.”

The results were striking: in the earliest part of the simulation, when conflicts were minimal, speed increased eightfold. But then the adorable kittens interfered.

Initial coin offerings (ICOs) are the blockchain version of stock offerings, and one of the most popular was CryptoKitties, which let users trade virtual cats. Due to the amount of contention as the same smart contracts were used again and again, some ICOs reduced the speedup from eight times to two times. But workarounds were still possible: by ignoring a small set of high-contention contracts and focusing on running others concurrently, Vikram was able to increase the speedup back to four or five times.

“That showed us a possible way forward,” Maurice says. “In the future, we can take steps to mitigate high-contention activity and add instructions to the Ethereum instruction set to allow some operations that otherwise wouldn’t be able to run in parallel to do so. For example, instead of two contracts trying to increment the same variable, the contracts could communicate with each other beforehand, so the database is only accessed once.” 

Eric and Maurice are looking forward to refining their techniques in the days ahead. Historical code, they explain, doesn’t provide a complete understanding of what was actually going on, so there’s more work to be done to evaluate whether a perceived conflict actually is one. It’s that idea of replacing a Volkwagen engine with the Maserati, says Maurice: making things run faster with a minimum of fuss. And to do it transparently, in a way that will work for any blockchain that uses smart contracts.

As time goes by, Maurice sees the importance of blockchains growing in parallel with the expansion of machine learning and an increasing interest in personal data ownership. “Blockchains could provide a more explicit and transparent way for people to control their data,” he says. “For example, they could serve as a data market where you selectively sell data from your smart devices to insurance companies.”

And more and more, the researchers believe, the public’s need for speed will motivate their work and those of their colleagues in the years to come. “As blockchain usage continues to grow,” Eric says, “people will be less and less happy to wait for someone else’s transaction to finish. Over time, speed will only become more important.”

For more information, click the link that follows to contact Brown CS Communication Outreach Specialist Jesse C. Polhemus.