Sharding at Near Protocol Min Zhang

hi everyone my name is minh i'm a core developer from the nier protocol and i help develop develop sharding so if you don't know about nir already first you should go check it out second we are a proof-of-stake fully sharded and user-friendly blockchain and this is why i'm here to talk to you about today about sharding how it works in general and how we implement it and near before we delve into any technical details let's first talk about what sharding is and why we think it's important sharding refers to the partitioning of data and processing in a shorted blockchain we divide the whole account space into multiple charts and each chart only process transactions and store data for its own shard so transactions from different shards can be processed in parallel to each other in a way this is similar to dividing a one-lane traffic into a multi-lane traffic by doing so we can increase both the speed and the throughput of the system and to talk about why sharding is important i want to first mention something called the scalability trilemma some of you might already know it it's like a concept first brought up by vitalik and it says it's very hard for any blockchain to achieve all of the three properties scalability decentralization and security in a traditional non-started blockchain every node in the blockchain has to process all transactions and store data for the whole chain so the performance of the whole blockchain no matter how many machines there are is still limited by the performance of every single machine so if you want to make the blockchain process more transactions faster we can either use better algorithms or optimize our code but ultimately the physical processing limit of the whole chain is still limited by the physical processing limit of every single machine so to make the blockchain faster we can either make every node in a system wrong on better machines which will make the blockchain less accessible and less decentralized because we're increasing the entry barrier for anyone to run a node and join the network or we can offload some of the processing off chain by using layer two solutions but then we divide the part of on-chain and off-chain security and we risk attacks that's specifically targeting on the option component which is not safeguarded by on chain security now sharding solved this dilem trilemma by not requiring every node to process all transactions and do all the work by themselves by spreading the load among different shards so the more shards we have in a system the more processing power you have in the blockchain so the blockchain becomes scalable it is also more decentralized because we're not requiring everybody to run on super high performance machines and ideally we can run a node with just a personal laptop and lastly our blockchain is as secure because each shard in the blockchain is still safeguarded by the whole chain so every chart is as secure as the whole blockchain okay now you might be wondering how is this still a trauma if there exists a readily available solution already and here's the catch there's no free launch in the world right so the cost we have to pay for sharding is its complexity comparing to a non-charted blockchain a charlotte blockchain has more horsepower it's more powerful it's more faster it can process more transactions but it's also much more complex to build and to make it right we have to solve a lot of challenges and some of these challenges as you will see will impact developer experience for user experience directly and some of these challenges will make the internal implementation of the blockchain harder and this is what i'm here to talk to you about for the rest of this presentation what are these kind of what these challenges are and how we and near are going to solve but before that let me first give you a very high level overview for near's sharding approach a near with starting we still only has one chain and the chain produces one block at a time and this block itself doesn't include any actual transactions sharding is implemented through a concept called chunks so each chunk include transactions from each chart so in a way chunks for each chart is similar to blocks in a non-charted blockchain blocks and chunks are produced separately but blocks contain chunks by storing chunk headers as part of the block content note here not the full chunk just the chunk header so our block is scalable to the number of shards in the system right every block can contain one chunk from each chart and now we're ready to talk about the first challenge and that is crosstalk transactions so crosstalk transactions are transactions that involve accounts on different charts think about this simple example alice wants to send 10 years to bob but alice account is at shar zero and bob's account is at sha1 and here's how this transaction will be processed and near at first this transaction will be sent to shar0 where alice's account is at and char zero the machines in charge zero will verify alice's signature on this transaction and charges alice account by ten year and convert this transaction into something we call a receipt now shar zero has done everything it can regarding to this transaction and the rest of the work has to be done by chart one so shar zero will send this transaction to char one this receipt to show one and the receipt will be included as part of the next block so when char one sees process the next block we'll see this receipt and put tenure to bob's account and this is the end of this transaction so i want to talk about how this transaction is processed here and near comparing to how it would have been processed in a non-sharded blockchain so first you'll notice that this transaction is actually processed in two blocks not one block right and second in theory uh and in practice um there could be another transaction that comes in also included as part of the second block and it also changes alice's account state and this will actually happen even before the first transaction is completely finished so in other words this transaction is actually processed asynchronously and near in a non-started blockchain transactions are processed sequentially one at a time the next transaction won't start before the previous one is finished however and near transactions are processed asynchronously that means transactions they can actually overlap with each other and two transactions they can modify the same account state even before each other is finished so that means developers they have to write their contracts in a way that is safe to be accessed concurrently now concurrent processing or concurrent programming is not something easy right especially for developers from from a web 2 background so this is definitely not ideal it adds a lot of complexity and difficulty to death experience and that is what's something that is something we are actively working on we're thinking about adding synchronous uh support for synchronous transaction processing in our blockchain but like this asynchronous nature is what happens behind the scene right and if a developer wants to truly realize the high performance brought up by this uh by a shorted blockchain this asynchronous processing is at least for now unavoidable and that is the first challenge the second challenge i want to talk about is related to security in a sharded system a started blockchain transactions are verified and no longer verified by all validators in the blockchain they're only verified by validators in each chart so it is possible for a malicious actor to gain control in the majority of validators in a single chart without having more than 50 percent of total stakes in a whole system and that is called single shard takeover and this is a serious problem because if a if one shard becomes invalid the invalid state other shards can actually be corrupted too because invalids they can travel from one char to another via cross charge transactions and note here like this the other shards the validators in the other shards they can all be honest like but other shots can still be corrupted too because the shard the state of the other child could depend on the state of like this corrupted shard to solve this problem one solution that we use and near is by randomly assigning validators to individual shards at the beginning of something we called a epoch and an epoch is a duration of time or blocks that approximately lasts for 12 hours so every 12 around about every 12 hours we reshuffle our validators and assign them to different charts and because in this randomized assignment validators cannot control which charts they're assigned to so it's very hard for them to coordinate with each other to be assigned to the same chart so in fact the probability that the single shard takeover happens decreases exponentially to the number of validators in a single chart so if we have enough validators in every chart the probability can be very very small like 10 to the negative 26 and negligible however that is only a partial solution and the reason for that is this chart assignment information is actually public and is released at the beginning of every epoch right so during this duration of every epoch an adaptive attacker could actually take this information and deliberately choose a chart to bribe and corrupt and the more shards there are in this blockchain the easier or the less resource it needs for this adaptive attack to happen again there's multiple solutions to this problem and one solution we use and near is called fishermen a fisherman can be any node in the system they don't need to be validators in fact they don't even need to be they don't even need to announce their roles in events so there's no way for the militias attacker to know all of their existence and contact each one of them and bribe all of them so when a fisherman sees an invalid transaction it will create a message called a challenge which will include a proof for why this transaction is invalid and it will then broadcast this challenge message to the whole network including every validators including validators in other charts and when the other validators see this challenge they need to verify whether it is true or not because fishermen itself could be malicious too right so and here's the beauty of this algorithm here's the magic the this that uh this challenge the proof included in the challenge can be verified without the original state of the original chart so even the validators that track other shards not the original chart they can verify this challenge very quickly without needing to download the state the whole state of that chart and after the validators verify this challenge they will slash the malicious validators take away their stakes and revert all blocks happening after the invalid block and restore the blockchain state back to a valid state so with this fisherman technology if there is at least one that honest honest node not validator honest no tracking each chart the whole system will be secure however this is still only a partial solution there's one subtle but important requirement for this fisherman technique to work and that is any node must be able to see the full content of a chunk in order to verify or challenge it and remember when i said it before each block only includes chunk headers they don't actually include the whole like the full content of a chunk so it is possible for a malicious chunk producer to produce a to produce a chunk and only publish the chunk header to be included in a block and withhold the full content of the chunk so there's no way for other nodes at the validators for non-validators in the system to verify whether the chunk content is valid or not and this is called the data availability problem the solution we use to solve the data ability availability problem we use something called erasure code and erasure code is an algorithm that split the full a full piece of data into multiple parts so the original data can be reconstructed from only a subset of these parts so when a chunk is first produced and near at the near blockchain the chunk producer the validator who is responsible for producing this chunk has to divide this chunk into multiple parts using erasure code and there are equal number of chunks to number of validators in a system so this chunk parts will be distributed to all validators one for each validator and when validators sees the block that contain the chunk they will only sign on this block if they have received their own chunk parts so if the block is signed by the majority of validators in a system that is more than half of the validators in the system and we assume there are less than one-third of valid malicious validators that's like a common assumption we usually make in blockchain that okay oh okay that means there um there are there are at least one six of validators who have signed on this block and have received their chunk parts so when another node wants to request the original chunk they only need to gather these chunk parts from these validators and the original chunk content can be recovered and that is because of the way how erasure code works as a tldr the power of a shouted blockchain comes from the fact that not every node doesn't need to process all the work doesn't need to like it doesn't it doesn't need to process all transactions and they spread the and uh they spread the word to other nodes right but there's a problem with that because they don't do all the work it has to be they have to be able to trust the work done by others so we have to build these additional technologies like fishermen or data availability to ensure that this trust is not being abused as a final recap sharding is a very powerful technology it is very simple but can be very complicated to implement and there's a lot of challenges we just described to be able to make it right and we have to design it very carefully to avoid any problem happening to the whole ecosystem building on top of the blockchain but at the end of the day and year we strongly believe that sharding is essential to achieve the mass adoption of blockchain and that is the goal for near finally i want to give you some updates on uh the sharding timeline and near last year we deliver we migrate our mainnet from one shard to four shards and in fact there is the first blockchain that operates on multiple shards and very soon this year we're going to deliver chunk only producer which will increase the number of validators in a system and also decrease the cost or requirement for running one and later this year we're going to make our blockchain fully sharded that means there's no need for any node in the system to track all shards and sometime next year we're going to enable dynamic resharding where the different loads loads among different shards will be rebalanced automatically and dynamically on chain according to live traffic so the full power of sharding will be fully unlocked and the near blockchain will become limitless and that is the end of my talk unfortunately do i still have time for questions okay okay sorry but here's some resources if you want to if you're interested in becoming a validator here's like some pages you can go to if you want to try out near and we have you can you can get a pre-loaded near wallet and with your name at this address and if you're a developer and you want to build an interesting project and earn some price for that you can also do that thank you