Nightshade — NEAR’s Ultimate Sharding Technique

Imagine the entire kitchen staff at a restaurant working on one single order. They are well-staffed but they wouldn’t start working on another order before completing the current one.

How long do you think it’ll take to serve everyone at the restaurant?

That’s what’s happening in most blockchains today.

All validators process all transactions and they process them one at a time. This slows the speed at which transactions get executed and drives up gas fees. Transactions get lined up and if you want yours to be considered first, you’ll have to shell out more.

One of the solutions to these problems is sharding.

And the NEAR protocol is crushing it with Nightshade, their unique sharding technology that allows process around 10,000 transactions per second.

What is Sharding?

As mentioned above, currently all validators in a blockchain process all transactions, one transaction at a time and store the entire history of the network data up to the most recent transaction.

As the total number of transactions increases so does the pile of data. Every time the validators need to process a transaction, they’d have to go through the entire transaction history inside this mountain of data.

So, how does sharding solve this problem?

In simple terms, sharding is a way to divide the total workload into small tasks and have several people work on several tasks at the same time. More work gets done this way.

Sharding divides a block into shards and assigns a set of validators to each shard.

These validators only have to store and maintain the data in the shard, instead of the entire network data and process only the transactions in their shard.

Once all the individual parts of a transaction are processed, all the shards are assembled to form a block. Thus, several validators can process several transactions at the same time thereby increasing scalability.

However, sharding too comes with some undesired issues.

And to fully appreciate NEAR’s sharding technology, we’ll need a take a quick glance at what these issues are.

Current Issues with Sharding

Blockchain technology is in its infancy. And so are all the technologies around it like PoW, PoS, sharding etc.

There are 3 prime roadblocks to effective implementation of sharding:

1. Safeguarding Inter-Shard Transactions

2. Preventing Malicious attack

3. Ensuring Data Availability

Safeguarding Inter-Shard Transactions

Suppose you send 20 tokens to Joe. Since the blockchain is now split into shards, two possibilities arise.

If both your and Joe’s accounts are in the same shard, the nodes can process the entire transaction end to end by themselves.

On the other hand, multiple problems might arise if the two accounts are in different shards.

- There could be a miscommunication between shards.

- The entire blockchain could be forked.

- How would the nodes in shard 2 know whether the nodes in shard 1 have completed their end of the transaction?

- Your account might get debited but Joe’s account might not get credited leading to a partially complete transaction.

Additionally, since shards can process multiple transactions parallelly, two separate transactions could overlap.

Let’s say your account balance is 40 and you send 20 tokens to Joe and 10 tokens to Ben.

Ideally, the system should:

Step 1 — Reduce your account balance by 20

Step 2 — Increase Joe’s account balance by 20

Step 3 — Transfer 10 tokens to Ben.

However, sharding doesn’t require the completion of one transaction before initiating another one.

Thus both the transactions stand a chance of going live at the same time and alter your account balance even before either of these transactions is complete.

Thus, your account balance would be reduced by 30 tokens even though neither of the transactions has been completed fully.

In other words, without accurate communication between two shards, processing a transaction could cause a ton of confusion and wrong network states (account balances, transaction history, etc.).

Preventing Malicious Attack

While 51% attack is a popular case of concern, it’s quite difficult to acquire 51% of a network’s total supply. Networks usually have hundreds of millions of tokens in total supply which can amount to tens of billions of dollars.

Plus, blockchains put several safeguards in place to ensure no single validator can ever acquire and hold 51% or more of all voting power.

But do you know what’s easier than trying to hijack 51% of a network? Hijacking 5% of it.

You see, sharding divides the entire block into smaller parts. And all the validators are divided into these shards.

So, if there are 100 validators and 10 shards, each shard gets 10 validators.

Now, the malicious validator might not be able to corrupt 51 nodes and hijack the entire network.

But they could very well corrupt 6 nodes and hijack a single shard.

And we just discussed the importance of accurate communication between two shards.

Do you see where this is going?

This is the direct cause of the next issue.

Ensuring Data Availability

In sharding, often different shards contain different pieces of a single transaction.

After all the separate pieces of the transaction are processed, all the shards are combined to form a block. This block also contains a block header holding the summary of all transactions instead of the transactions themselves.

It is only the block header that is broadcasted across the network, thereby reducing the time taken to verify the block.

But what if a node wants to dig deep and check the validity of a transaction?

It would simply ask all the nodes in the block to reveal the transaction data.

Now here’s the issue — a malicious actor might refuse to release the portion of transaction data within its shard.

Remember, this actor has hijacked an entire shard and controls it.

What’s more? It might have processed an invalid transaction thus turning the whole block invalid.

However, since it refuses to share its portion of the data with the nodes across the network, there’s no way for them to challenge the validity of the block.

Here’s the good news.

NEAR has developed a unique sharding technology that reduces, if not eliminates, these issues to a great extent.

Enter Nightshade

Nightshade is NEAR’s very own sharding technology that allows it to process up to 10,000 transactions per second and potentially even more.

So, how does it achieve such massive throughput? And how does it squash the challenges with sharding?

Let’s find out.

Nightshade is chunky

Nightshade divides each block into shards, each of which produces a batch of data called chunks. It is these chunks that contain transactions.

Also, each block contains the chunk headers, which are the summary of transactions in each chunk.

Here’s what the whole setup looks like.

Now, let’s take a look at how this set-up allows us to navigate the challenges associated with traditional sharding.

Improving Inter-Shard Transactions

Let’s go back to you sending 20 tokens to Joe.

Remember, your account is in shard 1 while Joe’s account is in shard 2.

In Nightshade, once your side of the transaction is verified and executed in shard 1 (and your account gets reduced by 20), the nodes in shard 1 convert this portion of the transaction into something called a ‘Receipt’.

This Receipt is sent to shard 2. Only then do the nodes in shard 2 proceed to verify and execute Joe’s side of the transaction and increase his account balance by 20. This ensures that both sides of the transaction are complete.

Next is the challenge of overlapping transactions.

That is one piece being worked out. Ability to process several transactions simultaneously is one of the key features of NEAR. Thus, it is figuring out ways to minimise the overlaps without any data related compromises.

Minimising Chances of Shard Hijack

Nightshade reduces the risk of a malicious validator hijacking an entire shard by randomly reassigning the nodes across the network to different shards after every epoch, which generally last for 12 hours.

This random shuffling of nodes doesn’t allow a single node to spend the time required to hijack a shard.

However, the information about reassigning different nodes to different shards is publicly released at the beginning of every epoch.

An adaptive attacker could take this information and choose a shard to corrupt by bribing its nodes.

And the more shards there are, the easier it would be for the attacker to hijack a shard because it has to bribe fewer nodes (a higher number of shards = fewer nodes in each shard).

This brings us back to the data availability problem. A shard is hijacked. The malicious actor refuses to share his portion of the transaction for other nodes to verify.

Ensuring Data Availability

Have you noticed that when you are fluent in reading a language, you don’t actually need to read every word in a sentence to read and understand the whole sentence?

You just skim through a piece of text, jumping between random words. And yet, your brain fills in the missing words automatically and makes complete sense of what you are reading.

Nightshade does something similar to solve the data availability problem.

Just like your brain fills in missing words, Nightshade uses the erasure coding algorithm to fill in missing pieces of data.

With erasure coding, you can split an entire sequence of data into multiple parts in a way that allows others to reconstruct the entire sequence with only a few of these parts.

Here’s a layman’s breakdown of how it’s used in Nightshade.

The validator who produces a chunk divides it into multiple parts using erasure code.

It divides the chunk into as many parts as the number of validators in a shard. So, if there are 100 validators in the network, the chunk is divided into 100 parts.

These 100 chunk parts are then distributed to these validators with each getting one.

Validators sign the block only when they have received their respective chunk part.

This way, once more than half of the total number of validators sign a block, the data availability problem gets solved.

Here’s how.

Let’s say out of the 100 validators in the network, 30 are malicious who refuse to release their chunk.

However, thanks to the erasure coding algorithm, the node can reconstruct the full chunk data with just 70 of these chunk parts. It doesn’t need to obtain all 100 of them.

This way an honest node that has not processed a transaction, can still verify its validity even if a few malicious validators try to prevent it from doing so.

Let’s wrap up

Nightshade is the first network to run multiple shards at the same time.

While it’s still not perfect, Nightshade is arguably one of the best sharding technologies in operation today.

And the developers at NEAR are working tirelessly to brainstorm and innovate solutions that’ll improve Nightshade further and further.

It wouldn’t come as a surprise to see a far potent and advanced Nightshade in the coming days.

We at Stader are trying to demystify NEAR blockchain and explaining it in ways a 5 year old would understand. If you liked our work, do follow us to stay updated on the latest posts. Share this article with friends and family to help them learn.