Innovating the Main Chain: a Polygon PoS Study in Parallelization

Polygon Labs

December 1, 2022

polygon_pos_parallel_evm_campaign|polygon_pos_parallel_evm_campaign_1|polygon_pos_parallel_evm_campaign_2|polygon_pos_parallel_evm_campaign_3

The Polygon Proof-of-Stake (Polygon PoS) chain has become a major destination for Web3 projects, users, and enterprises since it launched in 2020, thanks to the chain's ability to deliver lower gas fees and higher transaction speeds.

Now researchers of Polygon PoS are excited to announce an innovation that will make the Polygon PoS chain up to twice as fast: the Parallel EVM upgrade.

Year-over-year since inception, the Polygon PoS chain has grown to become one of the most used protocols in the world. The network has tens of thousands of dApps, more than 3 million average daily transactions, and $3.5 billion in total locked value. Integrations by traditional and Web3 companies alike have made the network a go-to solution for businesses looking to leverage the security and decentralization of Ethereum with the speed, lower-cost, and community of Polygon PoS.

Even as researchers of Polygon work on Layer 2 solutions for scaling–like Polygon zkEVM–the team is also improving the Polygon PoS chain, to make what is already fast even faster.

Over the last six months, we have been researching and testing pioneering new ways to increase performance. And now, with the Parallel EVM upgrade, we’re closer than ever–because even the mainnet is bleeding edge.

A Parallelizing Engine: What It Means, Why It Matters

The goal of a parallelizing engine is the ability to process multiple transactions at the same time.

But for years, it’s been difficult to find a way to do that. There is a bottleneck in nearly every existing blockchain. When it comes to transactions, block proposers and validators need to know what dependencies exist as they build a block.

What is a dependency? It’s a situation such that one transaction relies for its execution on the data of another, in some logical order.

Suppose, for example, you need to pick up groceries. First, you have to drive to the store. Then, you find what you need. Then, you buy the groceries. A dependency for buying groceries is getting in the car and starting the engine in the first place.

Every transaction in a block must be executed by a block proposer or validator in a correct, logical order. Otherwise, consensus breaks, and logic fails. You’d find yourself at the store before you even arrived–which is nonsense.

That’s why, until recently, block proposers and validators verify every transaction sequentially to ensure there are no dependencies. The system doesn’t want to produce nonsense. Traditional blockchain designs, therefore, result in a bottleneck, meaning slow transaction times, because ordering correctly takes time.

For years, researchers have been wondering: is there a way to execute different transactions in parallel, and if so, are there different ways to go about doing it?

To address this issue, Aptos Labs developed the Block-STM engine, leveraging long-standing research behind Software Transactional Memory (STM). Block-STM detects and manages dependencies when executing transactions and smart contracts concurrently. It’s dynamic, which means the engine permits validation and revalidation of transactions after execution.

Here’s how it works. Block-STM grabs a batch of transactions and executes them in parallel. It operates under the assumption that none of the transactions conflict, i.e. no dependencies. Instead, the Block-STM treats smart contacts and all transactions as if they are independent of one another.

Because transactions read and write from fixed memory locations, the core idea behind Block-STM, and STM specifically, is that you can execute transactions as if no other transactions existed. Then you record what memory locations are actually read and written from.

When you have a dataset of all these locations, it’s easy to compare: did any of these read or write from any of the same data? If so, you have a dependency! You have to get in the car before you go to the grocery store. The Block STM parallel engine catches these, takes note, and then reschedules the transactions for revalidation.

So Aptos’s innovation is a big step in parallelizing execution–and it’s also wicked smart.

Using Block-STM promises to widen the bottleneck that has long challenged the space. Many transactions can be executed in parallel! But the Aptos network is written in the Move programming language, and the Block-STM engine is written in Rust.

What about a Block-STM for a parallel Ethereum Virtual Machine (EVM) engine, written in Go and on Polygon PoS? Is that possible?

The Minimal Metadata Approach: Parallel EVM on the Polygon PoS Chain Accelerates What’s Already Fast

Inspired by the work at Aptos, researchers of Polygon PoS decided to experiment.

Over months of development, the researchers devised a way to deploy a parallelizing engine for the Polygon PoS chain’s EVM. This came with a few insights.

First, upgrading a live mainnet is tricky. The Polygon PoS chain already boasts incredibly fast throughput, plus a daily transaction volume that’s in the millions. So the network’s APIs already provide enough data that can feed a parallelizable engine. And no API changes were required to test out an EVM-specific Block-STM. This was an important consideration, as it made implementation easier.

Second, due to the incredible volume of transactions, the researchers understood that in an already living, hugely adopted system like the Polygon PoS chain, acting as if there were no dependencies anywhere, in any block, just wasn’t feasible.

It would be like saying that on any given day, no casual or dependent events were going to occur.

Without recording metadata, Block-STM as it was designed simply batches transactions together, then executes them. Whenever there’s a conflict, for each validator building a block, there could be many, many nodes that end up re-executing a block to validate it. In such a scenario, this creates redundancy, not to mention requires a bunch of compute and I/O.

In an active, buzzing network like Polygon PoS, a starting assumption of no conflicts wasn’t feasible. Even when Block-STM works well, there is overhead.

So researchers of Polygon PoS took a slightly different approach.

Implementing Block-STM on the Polygon PoS chain works by first reading and writing all transactions, and then recording them in a data structure known as a "DAG,” a directed acyclic graph. The validation process checks for dependencies, and crucially, takes note.

With all the dependencies recorded, the information is appended as metadata to the block.

We call this the minimal metadata approach.

By appending conflicts as metadata in a block, downstream nodes and validators are not required to revalidate any conflicts. There’s no reason every node in the system should do that. Once the block builder has executed transactions, then they can just record the metadata, and no one else needs to. And whereas Aptos performs both execution and validation simultaneously, the parallel EVM system on the Polygon PoS network executes transactions before validating, so that the metadata with deduced dependencies can be easily executed.

Think of the minimal metadata approach as a useful map. All dependencies are noted in the metadata, providing the most efficient way to execute transactions in a block. Once the map has been made, nodes and validators can see all the dependencies and navigate accordingly.

Speedy Results

What does this parallel EVM engine afford the Polygon PoS network?

The parallel engine significantly increases the throughput of the Polygon PoS chain, as the Polygon PoS network can now handle multiple transactions at the same time. Researchers were able to successfully implement Block-STM for Bor Nodes–but for Erigon, work is still ongoing.

Still, the results have pleased us immensely.

We noted a 1.6x increase in gas throughput when using the minimal metadata approach, with a clear path to a 2x speed-up, significantly boosting the already lightning-fast Polygon PoS network.

Part of the parallel line of research has been to pick apart some of the blocks in production and see what kinds of dependencies exist. These lines of inquiry turned out to be just as valuable as actually doubling the network speed.

We found that on mainnet, around 55% of the transactions in most blocks were parallelizable. This makes sense. On a large network like Polygon PoS, there are a handful of popular applications that are called all the time–think Uniswap, Sushiswap, etc.–so it’s intuitive that there would be a lot of dependencies. A benefit and a potential downside of a network with many big applications.

These data also open up new approaches to how the blockchain space considers building blocks.

Block builders can and should optimize critical paths by taking dependencies into account. Once those are noted, they can propose blocks with fewer transactions that conflict, filling blocks for maximum efficiency.

There are still areas of research to consider going forward, but finding critical paths will be a huge component of the minimal metadata approach. Needless to say, we’re excited to continue innovating. The concept of parallelism ends up being important for zero knowledge research, as well.

The Polygon PoS research into Block-STM and parallelization has been inspired by the open-source, publicly available work done by Aptos Labs. A big shout out to them for their innovations, and keeping the spirit of Web3 alive by building in public.

In the same spirit, the work our team has done will be public and open for other researchers to pour over, either to suggest their own paths forward or improve our results. Check it out here. Keep your eyes on the Polygon Blog for the latest news on cutting edge technology.

Let’s bring the world to Ethereum!