NEAR Whiteboard Series with NEAR | Technical Deep Dive Sessions, 20 Oct 2020

Previous Meeting Next Meeting

⏯

youtube image

►

From YouTube: Whiteboard Series with NEAR | Ep: 40 Part 1, John Adler from Celestia (previously Lazy Ledger)

Description

John Adler, Chief Research Officer & Co-Founder of Celestia (previously Lazy Ledger) (https://twitter.com/CelestiaOrg) discusses with Alexander Skidanov, Co-Founder of NEAR Protocol (https://twitter.com/NEARProtocol) about the technology behind Celestia (previously Lazy Ledger)

------- About Whiteboard Series ---------

The Whiteboard Series with NEAR is a set of video interviews with Founders who are building scalable solutions for Blockchain. We deep dive into their story, what they're developing and how it is helping the ecosystem.

Follow the latest from NEAR Protocol on,

Website: https://nearprotocol.com/
Discord: https://near.ai/discord
Medium: https://near.ai/medium
Twitter: https://near.ai/twitter
GitHub: https://near.ai/github

#WhiteboardSeries #Blockchain #FutureIsNEAR

A

uh Hi everyone this is alex from near with me today is john adler, chief researcher and the co-founder of lazy ledger. We will talk about laser ledger today and john. Would you like to introduce yourself and give us an overview of what lazy, legendaries and technology behind it.

B

Sure yeah, so, as you said, I'm the chief research officer at lazyledger and I'm a co-founder. uh So I do protocol specification and applied research.

B

uh So I guess I can start with uh I'll move this over, and I guess I can start with a kind of a brief overview of what lazy ledger does and then we can start talking kind of about the techniques we use to get there. So lazy ledger is essentially a blockchain that is specifically designed and optimized just for data availability throughput. It doesn't do any execution at the base layer. Rather it just orders messages, in other words just zeros and ones.

B

It just orders them through the consensus mechanism and then uh applications can run on top of lazy ledger and execute over the ordered messages.

B

Okay, are we ready to start talking about the fundamentals.

A

Yes, absolutely.

B

Yeah, so this is a kind of a terribly drum drawn blockchain. uh We all know you know what the blockchain does. You know each each block header points to to the previous block uh and let's see if we can draw the pencil and each block is composed of two parts. So here is the block header.

B

So this is the.

C

B

And this is the body.

B

And the body consists of a list of transactions, you know transaction, one transaction, two and and so on, right uh in in in some in some order. uh Usually it's going to be in you know, particular some topological order.

B

uh Some other blockchains have proposed other things like you know, uh lexical ordering and stuff, but you know there's going to be some ordering of these transactions and there's going to be a block header and the block header uh usually consists of a pointer to the previous block and it'll have a route of transactions and a root of the state.

B

So, let's kind of add some text here. So this one here is going to be a transactions route and here you're going to have a state route.

B

And the text is tiny, I don't know, if is that big enough, or do you want me to make it bigger.

A

uh Let's make it bigger, I think bigger would be better.

B

Size bigger is that better, yes, transactions that makes this bigger state route. Here's your body- and this over here is your blockchain right. I don't know how do you, how do you move things just.

A

uh I use this select tool v.

B

Actually, okay, okay, this doesn't make sense great. So this is the state route, and this is the transactions route over here right and every block header has this. Now there might be some other some smaller routes in there. You know there might be a route of receipts. There might be some proof of work non, so there might be a list or a route of votes if you're using a proof of stake style protocol, but those are kind of not relevant to what we're going to discuss uh so in uh in a normal blockchain.

B

What will happen? Is you run a full node and the full node fully executes every single transaction in in the block body? Okay, it goes through the transactions well, one after the other, and it fully executes them, and then it uh make sure that you know the transactions in here match up with the transactions route and then make sure that the computed state at the end of the block matches up with the state route.

B

So you know it's fairly straightforward and let's pretend that you have an attacker, so an attacker will create a longer chain of blocks. Arrow.

B

Forget my very uneven arrows, but hopefully that'll suffice, uh oh so, let's undo this, this block should come from the side. There's a block over here. There's a block over here right. So the attacker, you know forks off of over here somewhere and he creates a longer chain of blocks, so the attacker has more than 51 percent or more than 50 of the hashrate.

B

uh If all of these blocks are valid, then the full nodes will follow this as the longest chain right they'll. Do a reorganization they'll follow this along this chain. Now, there's you know things that might happen there. You know penalties might be enforced. Some people might, you know, decide the coin price to drop, or you know the the cost of the the price of the the hashing hardware should drop stuff like that.

B

uh That's not really too important to to our discussion here, but you know the way that consensus protocol works is they'll, just follow the longest chain. So if all these blocks are valid, you know the the full nodes are going to follow this and the light nodes will also follow this chain right uh light nodes just check the proof of work, so they just follow the follow the longest chain and they don't validate transactions in the block body. Okay. So now this is where things get interesting.

B

What happens if, let's see if we can draw with a different color, let's use red right, so there's some transaction in here- that's invalid! uh The miner decides to insert you know, there's cool this collusion. That's these looting, miners that have you know more than 50 of the hash rate. They decide they're going to insert a transaction there that you know gives them a whole bunch of coins, like let's say a billion bitcoins, something like that right and so there's, obviously an invalid transaction.

B

You can't have a transaction that has a billion bitcoins, but they do it. So full nodes will reject this. This this fork here, obviously because this is an invalid transaction and full nodes will follow the longest valid chain, not the longest chain, uh but light nodes will still follow this chain. It's the because light nodes just follow the longest chain. They don't care about transaction validity right, so the the light nodes will follow, follow this chain.

B

So now you see that there is a problem, because if many users run light nodes and only a few users, a few user users run full nodes. That means the light nodes can be tricked by this attack, which is you know, especially dangerous.

B

So the reason that bitcoiners and the bitcoin philosophy is everyone should run a full node is because of an attack like this is that you know everyone who isn't running a full node could end up getting tricked, and if everyone and all those people get tricked, they could still continue using bitcoin, and we don't really have a way of enforcing a penalty to the miners that have done this.

B

Reorg right, like the miners, could just do a reorg and then, if the price of bitcoin doesn't drop, if the hashing hardware or if the hash function doesn't get changed in response to this attack, then the miners have just executed an attack and there's no penalty for it there's no cost of the attack, so they can. This means they would be able to attack bitcoin anytime. They wanted for free, which would obviously be a terrible conclusion.

B

So this is why they encourage everyone to run a full node, uh because bitcoin doesn't have a way of protecting against this. So can we do better? Do we have a way of protecting light nodes uh from this kind of attack? And the answer is: is yes and and two steps so we'll cover the first step. The first step is fraud proofs.

B

So, let's see, if I can.

A

So so before we dive in uh for me to understand the uh the without an ability to to insert an invalid transaction right- or I guess a more general case sense- it is not just an invalid transaction. It could be that all the transactions are valid right, but the state root uh does not correspond to the to the output of them right.

B

That would be data that would be like a block withholding.

A

No, no, what I mean is that the the block like let's say the block, contains 10 valid transactions. uh The state route is incorrect. Then the full node would also reject it right. They will validate it.

B

Yeah yeah yeah yeah yeah, but the light.

A

Client will still accept it right. Yes, yes, so the the miners they can attack. The previous attack you described with the longest chain uh does not contain invalid transactions. This is still a valid attack that the miners can execute right. Yeah.

B

I guess I said transactions.

C

Or transactions but.

B

Relationships, transactions plus the state route, because you know the state.

C

B

Defines the state and transactions just modify the state, so you know instead of having an invalid transaction, they can just directly modify the state in an invalid way by just changing the state again. So yes,.

A

But my question is more of so without so so, let's say everybody is running full node right. uh The attacker, which has 51 percent of hash power, can still attack the attack. You described first right, they will create a longer chain and they will double spend. For example,.

B

Oh yeah, they can still do that so fraud proofs, don't protect against that.

A

Yes, so so we have effectively we're saying that the attack with an invalid transition is way more dangerous, uh because it allows you to apply state transitions which are completely invalid, while the the longer the longer chain or like reward attacks, while they still dangerous, they're less dangerous, because it is still on the valid transactions that can go through. Is it the idea or why?

A

Why we're thinking that.

B

Yeah, so so the reason is that uh we want to move beyond the model if everyone has to run a full node for the system to be secure. That's that's essential. We want to move beyond uh if, if, let's say you know, 99 of bitcoin users and traders and investors and everyone you know involved in bitcoin ran spv knows ran light notes. You know if someone attacked the system, the full nodes wouldn't have any way of proving that an invalid transaction was included in a bitcoin block to any.

C

B

People, so you know the bitcoin economy would just continue the so the attacker essentially has you know minted himself, a bunch of bitcoins for free.

A

B

And they can do this, do do this whenever they want. So we need a compact way for people who are running light nodes to have some sort of guarantee of block validity.

B

Does that make sense? Yeah? Yes, what's david yeah? So now, let's see how do I? Okay there? We go so I'll push this up uh lion so line, which is red okay. So the first thing we need is one broad proofs and I'm going to talk about the specifically the state transition fraud proofs. There there's one other scheme for the utxo data model, but for here we're going to talk about the the state transition fraud, proofs, okay, so how do they work.

B

So we have our blockchain again, we have arrows and then we have again our block headers right. So our block headers have you know in here. They have the state route, here's another state route right and again the state route commits to or it's the merkel root of the state tree uh state trees can be represented. Multiple ways in ethereum you have the merkle patricia tree.

B

All those systems have a sparse, merkle tree and and so on, but you know essentially just the root of the state, uh and we want to make sure that uh going. We want we, so we want to have a way of proving that the state root of say the next block or this yeah. Let's say the state root of this block here this the state of the next block. We want to prove that this is invalid, assuming the previous one is valid right. So, let's draw some.

B

Let's draw some check marks, so this one here, the state road is good and this one here as they do. It is bad right. So you know they do they do they do an attack by either inserting an invalid transaction or the stage is just invalid and you know they've just given themselves a billion coins in the state. You know and then so did that as leaf in the state all right so so this is the kind of thing that we want to prove uh by induction we can by induction.

B

This is sufficient because we always know the state route at the genesis block. So as long as you as long as you can show this for one step, then then by induction, you can do this anytime, you want.

B

uh So how would we do this? uh The oh, let's see pencil, so this block has a bunch of transactions, so we know that we know that if we start at this stage root here and we execute these transactions, if this state route is not what we get, then that means this block is invalid. In some way, do we agree.

A

B

Great, uh so the name that the you know, the obvious naive way is saying: well just give someone a block and they just execute all the transactions and compare the state routes right. They have a pre-state and then there's a post state and the post state. That's committed to here in this block, doesn't match up with the post state they compute, then that's, that's! That's an invalid block right! There's your fraud proof, uh so this is kind of the native way of doing doing a fraud. Proof.

A

They don't have a pre-state right, a light. Node does not have the state.

B

Oh yeah yeah, so the light node is given the pre-state route over here right. uh So in order to in order for the light node to know so in order for the light node to be able to execute these transactions, the only thing it needs to know is the pre-state that is touched. It doesn't need to know the entire pre-state all right. So the first thing that you give, which is thank you for bringing that up.

B

So what do you need to give to the to the light now, so the light node get has previous state route. It's also given merkel branches to previous state elements that are touched.

B

And it's given the and it's given you know this this this. The well has given the entire block. So it's given you know the prostate route pro state route and you know all the transaction I'm using mark down here which ones okay and it's given the transactions right and in the in the nav case, uh and then you know if the miracle branches aren't sufficient, then you know, as it executes a transaction, it's going to say. Well, I'm touching a state that isn't part of part of this part of these merkel branches.

B

You know the proof you've given to me is insufficient right. So that means it's not a good proof right. So if it executes all the all the transactions successfully and then you know the merkle branches are sufficient. Then at least you know, the fraud proof itself is is correct. You don't know if it's uh it's correctly, formatted, okay, so essentially what you're doing is you know you run through all the transactions? Then you check to make sure you know is this: is this post date rule different?

B

uh So this works but there's an issue. uh What's the issue.

A

uh Well, it's it's heavy.

B

Well, yeah, it's heavy because you have to execute every single transaction right right.

A

Well, I guess the other issue is that when the access to transactions.

B

A

We might not have access to the transactions themselves.

B

That's part two, so in this case, let's assume that they have full access to the transactions.

C

B

B

So this works, but the problem is that, as you said, it's heavy executing all the transactions could be expensive, especially in a resource-constrained environment like a blockchain right. So can we do better? The answer is yes, so draw a line draw line. So can we do better? The answer is yes. So what we do is, uh let's see pencil, so here's our oh, I can write here's our transaction route.

B

Right, it's the merkle tree off some transactions right, so here's transaction one, here's transaction m right! There's a bunch of transactions in between.

B

Dots, uh so what we do is we say well what happens if, after this transaction, I also put inside this tree, I just put some enter, need yet state route and see. How do I select.

B

Select, let's move this over here yeah. So after every sun, every single transaction I'm going to insert an intermediate stage. This is the naiva you can you don't have to do it after every transaction? It could be after every some parameter number of transactions. It could be after a certain amount of gas, but in naive case we say after every transaction so enter immediate state root.

B

Right and then you commit to this into a tree so instead of a transactions route, now you have a data route, so this is a route of a route of where the leaves are. You know, transaction, then the intermediate stage after executing this transaction, then the next transaction, then the intermediate stage after executing that one and so on, right and intuitively. That makes sense, because each transaction is a state transition and a block is a group of state transitions. So when we're doing this, this naive fraud proof over here.

B

Let me fix this typo, but when we're doing this naive fraud proof we're essentially doing a state transition fraud proof, but over a block right, we're saying here's the previous state route, here's the next stage route execute a bunch of state transitions, and then you know the state routes at the end should not match up. So we can do the same thing it just. We include a state route after every transaction and then we do the same process, but instead of executing all the transactions in a block, you just execute one transaction.

B

Does that make sense.

A

Yeah that makes perfect sense.

B

Yeah so, and then you give exactly what you give here, except instead of a list of transactions, you just give one transaction right and then again you just run the transaction through. uh So this is when? Is there an eraser erase, let's erase this yeah? So this is how you do fraud proofs. uh So now you brought up a a very good point, which is what happens if these transactions here? What happens if the majority miners just hide them? What happens if they just don't show them to anyone right?

B

They show the block headers, so the block headers are still being sent out and light nodes will still follow the block headers, but no one can actually construct this fraud proof because no one knows what's inside the block right and in fact they don't even know if it's invalid, it could be a valid block, it just hidden right. So so how do we deal with this?

B

And this is where the more involved data availability proofs come in, uh which is where we're going to probably spend a bit more time and and the existence of data availability? Proofs is something that uh you know. The bitcoin research community has generally considered not possible and that's why they didn't consider. Fraud was possible exactly because of the problem of data withholding, but they are possible with with pretty decent guarantees with pretty weak assumptions, which is, which is what we're going to discuss here.

B

B

Data availability proofs, so this is the data availability proof scheme that was formally formalized by mustafa bassam and alberto sassini. I think and vintella buterin uh in a paper. I think it's around september, 2018 or yeah, so I think around september 2018 or october 2018 somewhere around there. So it's been, but you know the idea of you know doing this fraud and data availability proofs uh last formally has been has been around for a bit longer.

B

So this is the scheme that we're going to be using at lazy ledger. It's also the scheme that is used for serenity or that has been proposed for serenity. uh So how does it work?

B

So, let's start with kind of the most naive way. So this one here is going to be like, uh like a straw, man, the most naive way right straw, strong the data availability scheme right. So this is like as naive as as you can imagine.

B

So what we're going to say is: let's, let's draw a rectangle: let's take the block right. Let's say this is the block I'm going to draw it out in a nice rectangle so that you know we can. We can chunk it up and stuff okay, so let's say I chunk it up into eight pieces.

B

Like so, is there a way for me to copy this by any chance.

A

B

Select select, I can copy nice paste, this will come and this will be useful. Let's put this over. Let's put this over here. I'll need this later. Okay, so this is now this. Let's consider this to be our block, so the uh you know you have all the block headers, but you don't have the block bodies right. So let's consider this to be the the block body right of one of our blocks. So what you could do is you can say? Well, I'm going to I'm going to. Let's use blue blue is a good color.

B

All right. Let's say I'm going, I'm going to randomly sample like I'm a light node, uh not a full. This doesn't really apply to full nodes again, because full nodes fully fully download blocks right. They they don't have a problem with data withholding if they see a block, doesn't have a block body, then they say: okay, there's an invalid block. I reject it, so this is really only for for the purposes of light noise right.

B

So uh how can a light now can convince itself that the data is available so well, the light node can say. Well, I don't want to download the full block, because that would make me a full node. So what I'm going to do is I'm going to download just a small portion of the block right? You know and let's say, there's eight transactions in this block right. If there are eight transactions in this block, you know the and let's say the node randomly samples, three, the light, node right.

B

So it's going to sample this one and let's say this one, and then this one right uh right it just it just randomly samples three. This is again. This is the the naive naive case right, but now what happens if the attacker?

B

You know the let's say, there's a guy here with horns because he's an attacker right. The attacker hides just this one transaction right. If he hired just this one transaction, then a light node that does this data availability check has convinced himself. Yes, okay, I checked these three transactions. I've been given them they're valid. They seem to be valid transactions right.

B

uh Therefore, I assume the block data is available right and another line now is: do this too the chance that a light note asks for this one transaction and doesn't get it because you know the hacker's trying to hide this, the chance that I'd find the chance that uh it lands on this would be. You know what three three out of eight or whatever right, uh which is you know in this case you know we're using a very large number. It's like you're sampling, half the block, but you know imagine that you sample. You know.

B

Let's say it's a thousand transactions and you sample five right then in that case you can see the probability that a light node finds that you know this thing here is being hidden is very, very small right. uh So this is, you know, not a great scheme, because the attacker can only need to hide one transaction. In fact, they only need to hide one byte right. They just need to hide one thing and then the entire block.

B

You can't you can't you can if it's hidden, then you can't show that you know you can't show that this transaction is invalid. If it's hidden, if you don't know what the transaction is right, you can't construct one of these state transition fraud proofs, because the one of the point of the fraud proof is, you need to execute a transaction if the transaction's hidden, you can't execute it.

B

So uh so this you know this generally is not a great scheme, because the chance that a light node will actually find out that this block or that part of this block is hidden, is very, very small. So we want something better. So how how do we? How do we do it? Let's, let's do b, let's use a razor coating and again we'll make this naive.

B

uh I guess I could say we can say 1d. I want 1b 1d naive, so let me scoot this over a bit. Let me copy this because we'll need it again and move this here. Okay, so.

B

What we're going to do now is we're going to use a razor coating, so the the way razor coating essentially works is that with, while it uses math which we're not going to cover here, but essentially you can think of it. Like let's say these four are the original data that I have just just these four.

B

What I can do is, I can actually compute some parity shares. So here's my here's, my original data.

B

Red general beta and here's the parity.

B

So I'm I'm, given this original data I'll compute, some some parity data and how much parity data you get is dependent on some parameter. You can you can change it, so it doesn't in this case. As you can see, it's one to one. It doesn't have to be one to one. It can be, it can be different, uh but uh essentially you have this original parity data now right. uh So, as you can see, you're getting more data, so this is bigger. The original data is fours four chunks.

B

The parity di data is also four chunks. So total you have eight chunks uh and you know, depending on your parameter choice, uh essentially what uh what this gives you is. If you can recover four chunks out of these eight any four, you can recover the original data and, of course you can also recover the parity data because you just recompute the parity data right. So this is this seems like it's a it's kind of solves our problem, because now you no longer have the problem.

B

You no longer have the problem of the straw man scheme over here up here. uh The strongman scheme again. Is that an attacker could just hide one of these one of these chunks over here? One of these transactions- and you would have to the light node- would have to specifically request that transaction right. Otherwise, it wouldn't know that something is being hidden in this case.

B

If you have this, how let's say you have this example, where you have four and four: how many of these chunks does an attacker have to hide to be able to hide the block.

A

Yeah, they need to hide five. They.

B

Need to fire five right if they hide three, it doesn't matter which three they hide. If they still broadcast the other five then or they even let's say they even hide four and they broadcast the other four. It doesn't matter which four they broadcast, the entire block can be reconstructed right. The original data can be reconstructed and from there we can also recompute the parity data. So in the entire thing, so they need to hide more than half in this. In the symbol. Example, it's five right.

B

uh So we're going to draw draw that out. Let's say the same red right, so an attacker hides five. Five right, an attacker hides these five shares right uh and I didn't draw that properly. Let's undo this, that's one attacker hides one. Two, three, five like this yeah, that's better all right, so attacker hides five.

B

They broadcast out the other three right uh now, here's kind of where, where some of assumptions assumptions come into place, so one thing that's important: is we assume that there's at least one honest, full node in the network that the light nodes can connect to? And we assume that they can communicate with each other, so there's no eclipse attack.

B

The reason this is important is that you know the light nodes and the full nodes can't talk to each other. Then you know the full node can't even construct a fraud proof right, uh so the light node sample stuff, but you know, there's no fraud, proof random thing and then what are you doing right?

B

uh So we we do make that network assumption. So what this means is essentially, if the attacker broadcasts out any share. We assume that the entire network is eventually going to hear that share. It might take a bit of work, but we assume that the entire honest network will eventually hear of that share right right. So they can't, like you know. Oh, they can't hide.

B

They can't hide, say like these two over here for one full node and then they used to be for the other, full node and then for another full node hide these five. They very much have to hide the same five right.

B

uh Okay, so we have to say this construction. So now our light node comes along and the light node does some samples right so the first time it samples uh it will get tricked that the data is available if it lands on an available chunk right like if, if the light, node samples this trunk here, then it says: okay, that chunk is available. I've been given it right.

B

Oh oh! I guess. I guess one thing to be to be to make clear is this: uh this erasure coded version of the chunks of original and parody data gets committed to in the block header, so.

C

B

Yeah, this is a merkle root, so we marking this. Obviously, although if you just have the data floating around, then the light node samples, it doesn't know what it's happening right so, okay, so.

C

B

A light node samples, this chunkier, it has to get a merkle proof from the block header to to the trunk just over there. Okay, so you know if a light, node samples, this trunk, it says: okay, this trunk is available.

B

uh So if it stops there, then it would be convinced that the block is available and it would have gotten tricked right so the the first time on samples, what's the approximate probability that it got tricked.

A

It will get tricked with the three over eight right.

B

uh Yeah sure uh sure, well let can we let's simplify that a bit just.

A

Well then, perito minus one over two.

B

Let's assume yeah apparently minus one over total. Let's assume that the the large number of chunks it'll be it'll, be approximately.

A

Yeah then one one half.

B

Yeah one half right because it's uh we assume a large number of chunks, great so so round. One count one.

C

B

Have the probability b is approximately half right?

B

Okay, so now it does a second round of sampling because you don't stop there and one round of sampling is, is pretty terrible, so it does the second round of sampling uh without replacement. uh So what's what's the approximate probability that.

A

It has gotten tricked after k around, so it's going to be one over two to the k right.

B

Yeah, so this is one corner uh with with around with around m or k. Oh sure uh p is you know one over two two to the k right uh so, as you can see the probability of it getting trick decreases exponentially.

B

So you don't- and one thing that's interesting to note here this probability decreasing of getting tricked. Is it in any way related to the number of chunks.

A

It is well well, it is. It is important that parity is one to one with the original data right.

B

Oh yeah yeah, yeah, yeah yeah.

A

B

We assume the parameters, the system parameters set up, that the parity and original data are one to one yeah.

A

Yes, uh well, there are a couple of things, so so one is if you assume that the number is sufficiently large right. So one second is a good estimate. Then it should be independent of the number of chunks but yeah, but also, I guess something we didn't touch on. Is we assumed that the adversary decides on what to to to reveal in advance right which I guess it doesn't have to.

B

uh Well again, is that we we assume that the network set up that you know if, uh if a chunk is distributed to an honest, full node, it will get distributed to all honest full nodes. Eventually.

A

Right but if I'm a light, node right and I'm sampling- and I just happen to be connected to several non non honest nodes right- I will sample like- I- will start sampling uh and then adversary as they receive my request for for for for a share. They will decide to to reveal it right or.

B

Wrong, we assume that the light nodes are connected to a full node, an honest, full node.

A

I see and we're also saying that, if the so so, then I guess what is not uh one assumption we did not discuss is so so, let's say I'm a light. Client, I'm connected I'm a light node I'm connected to, let's say a dozen 12 12 full nodes right. So so I chose to sample a particular share and I chose a particular full node to sample it from so. If I fail to sample it from it, what do I say?

A

Do I say that the date is unavailable or do I try to sample from another full node.

B

You continue trying until some parameterizable timeout.

A

Right so, therefore, if I'm connected to any full node which is controlled by adversary, eventually, I will sample all my shares from that adversary. Adversarial, node, right and so adversary can choose uh to specific.

B

Sure but the shares oh well, we assume the light nodes aren't under eclipse attack if they're connected to at least one honest, full node, then they're not under an eclipse attack.

A

Right, but in this case I'm saying let's say I'm connected to exactly one malicious node and everybody else, I'm connected to is a full node, which is honest right. So I'm saying I want to sample. Let's say the parameter is five. I want to sample five five shares out of a thousand right, so I go to the full nodes uh and the full, and let's say that the uh so okay, so the way I see it is adversary. First sends me the hash of the block right yeah.

A

So at this point from someone I heard that the block exists, other full notes haven't heard about it. Yet so I try, I start sampling the shares and all other full notes tell me. Well I don't know the block, I'm not gonna tell you the share, so I keep on trying and I end up trying to download it from the malicious note and malicious note at that point decides for the first time to reveal the particular share right.

A

So so maybe it will not be able to check all the light client, because all the light clients collectively will probably hit all the shares, but it will be able to check one particular one. So let's say it wants to coinbase right. So there's specific in our coinbase is coinbase goes on and samples and ultimately coinbase ends up sampling from uh from the adversary. An adversary reveals specifically the shares. Coinbase wants to see.

B

uh So we also assume a network model where queries can be made anonymously.

B

As in you can you can't associate? Who is making the query uh in practice? The reason that this is an okay assumption, even if we don't use things like tor and whatnot, is that say a coinbase. They can run two full nodes or they can run 100 full nodes, and you might know one full node is coinbases, but you don't know all of them are operated by a single entity. Yeah.

A

Well, in behind the scene right we're checking the light clients.

B

So I guess this will not be running a light client. Well, they wouldn't be running a like line right uh but like an end, user is like an end user. Okay, they run one for one light client. But how do you know they're not running two like clients, one on the phone and one on their computer, that belong to the same person that can and they can the two nodes can communicate with each other off-chain, and you know the the the you know, the the.

C

Human is essentially.

B

A very good way of you know having private communication between two computers. Right, like that, you can't you get you can't you can't really it's pretty hard for a computer to spy on human.

C

B

And a keyboard here and then you know typing on the keyboard there.

C

A

Okay, so with those assumptions, uh because because I see you have the third one drawn right, so we we are about to find out something bad about this model. So yeah, oh yeah,.

C

A

At all obvious to me, what is wrong with it with the assumptions we discussed, so I'm I'm, uh I'm.

B

A

Hear what what is it.

B

We we we will, because you know this is that's the name yeah so so this is kind of a few and interesting things to note uh this. uh The chance that a light node can be tricked is completely independent of the block size. What this means is the number of rounds you need to do is constant. It is not. You know, big o of n, where n is the block side. There's not big.

B

O of you know some function of n, it's big o of one uh with respect to the number of transactions in the block, or you know the number of bytes, the number of gas or whatever, whatever you want right.

B

uh This is constant, uh which is pretty amazing, because it means that uh you, you can have you just have to do a constant number of samples and, and each of these sampling operations is, you know, logarithm logarithmic in the size of the size of the block, because it's a merkle, it's a merkle branch too, to the particular share right. uh So.

C

B

Is you know a very, very cheap operation uh which is great, but now here's kind of where the problem is. Let's say I have one light node right. I have one light now the light node samples three shares right. uh Well, this example is bad because then the number of shares is pretty small right, uh let's say let's say the lightning samples two shares just again, the the the small number, so it makes things a little disproportionate, but you know those light nodes. Samples two shares right. uh So let's say uh pencils use green right.

B

So let's say the light. Node samples, the share right uh and in fact the light node could sample the share right. Okay, you just have one light note. uh A bls green is a terrible color choice, because maybe a non-trivial number of our viewers are red, green color blind, but these x's here are green.

B

So you know the light. Note samples these these two shares uh just just as light now and there's not a single other note on that in the network. Let's say right or you know, this could be the full node right, because we assume there's one on a full node. uh So you know the full node tries it's best to by asking the network and everyone around. You know the full node tries to reconstruct the whole data.

B

Somehow, uh if it can't directly download the original data, it has to ask the network, for you, know the shares individually, but it should be able to reconstruct the block. So let's say this, you know this. This full node is, is you know, you know out there making requests, and you know it downloads these these two, these two, so that you know uh this is this is what it gets uh do. Can we reconstruct the block using only these two shares.

A

B

No right because you need four yeah, uh so the problem is that if we fix even if we fix this- let's say you know we set our k is the two at some in some fixed number. uh Okay, so you have one, you know a light, client or a full node or whatever you know they download these two there's no guarantee that you'll be able to reconstruct a block. If only one client does these requests right.

A

Right but wouldn't full node, uh the full node will try to fetch all the shares right. Yeah.

B

So the full node will try to fetch all the shares. Yes, uh but the problem is okay, the phone does, but the full node can't really prove to a live client that it hasn't been able to fetch all the shares.

A

Right but, but uh so the way I see it so far, is that the the chunk sorry, the block, could either be available, meaning that it does it did broadcast so so effectively, uh let's go through the timeline right, so the block was published for the first time. So so uh because we assume that if some message was sent over the network, it will eventually reach everybody. So eventually everybody learned that the block was at least uh announced, meaning that the header was announced.

A

Yes, so after that everybody will attempt to sample some shares and again we're saying that the sum share was published on the network. Eventually, everybody who tried to sample it uh will be able to to receive it right. So with this assumption, it seems to me that, with a sufficiently large key uh for every available block, every light, client and every full node in the system will know that it's available and, moreover, the full nodes will actually reconstruct it, because fullness.

B

No, no, so they can convince themselves as available, uh but there's a problem. You might not be able to reconstruct the original data right and okay, and this is very nice. This is like strongman example. Let's say you have exactly one node, that's doing this sampling right.

A

B

Sample these two shares.

A

Yes right, but even then is this not a light client or a full client.

B

It doesn't really matter.

A

Because if it's a full client uh it will not, it will not try to fetch case shares. It will try to fetch all the shares.

B

Right, the phone number will try to fetch all of them. Okay, so let's say there's a like line right, uh but.

A

If it's a light client, uh then then there's not a single honest, full note in the system.

A

B

Is still honest, it's trying to do its job, but it can't so so so there's another assumption here, uh the the the reason, the reason is confusing is because there's another assumption, which is what we're going to talk about. So let's say one. You know one honest phone, though that's trying to do its work and you have one like client, like client shop samples. These two shares it sees they're available and there's only two shares that are distributed right.

A

But sorry for interruption but consider the following model right: let's say that the full client will not distribute any shares until it has the full block right, so the full node does not have full block. I don't.

B

Know the full node the phone should all distribute shares, even if it's only seen a few of them.

A

Right yeah, right and in the in the model, but let's let's say we're changing the model right. We're saying the full note will not be distributing shares until it has the full block. Oh.

B

No but that'll be terrible, because then full mode would never be able to reconstruct the block unless they've been given a full block. So full nodes can obviously.

A

B

Individual shares.

A

The full nodes can gossip individual shares.

B

Like if the only way a full node would be able to broadcast anything out, outwards is if it.

C

B

A full block that means an attacker could just not ever show a full block and only do like right, only give out individual shares and then full nodes would never would ever send an outgoing message right. So.

A

Obviously, of course, of course, you cannot break every uh like it will not be a productive time if you will be breaking every every modal, so let's do the last one and and then we will proceed with the yeah.

B

A

So notes always send they brought they, they re gossip to other full nodes, but they would not respond to light clients unless they have all the shapes.

B

They can also respond to like clients too.

A

Right but I'm saying how will it break right so.

B

No, no! No! No! No! I think the reason is that the assumption seems very obvious. So can I go through the assumption? Yes,.

A

C

When I say it, they'll.

B

Seem very obvious because, like oh obviously, this happens in practice, so the.

C

B

The attack is is very contrived, but it's still an assumption that we have to make, because we have to make all our assumptions, let's assume, there's one full node and there's one like client like client samples. These two shares they're. This is this is bad. I shouldn't put this here.

B

I should like say, let's say, sample this share and then let's erase this just so we don't get confused now, the like client samples, these two shares it sees that these two shares are available right and, let's say, there's only this an imaginary world there's one like client samples. These two shares they're available right uh and then the full node tries to reconstruct the block.

B

Also seeing the full node can also only see these two shares, but the so the like client is convinced that the block is available, but the full node can't reconstruct the block right and that's the problem right. But now what happens if we have like 100 like clients 100 like clients, each sample two? So maybe one samples these two one samples these two one samples these two and so on, and then you know if the block isn't being hidden, then a full node can reconstruct it by asking around for the shares right.

B

So the trick is, we assume there's a minimum number of flight clients that are making these requests.

C

B

And those numbers can be fairly small. The the paper gives numbers, I think around 100 or something so you know it's a very it's a very weak assumption, uh obviously, in practice for any reasonably sized network, you're going to have 100 nodes right, especially light nodes. So this isn't a very strong assumption, but it is something that we have to point out is that you do need a a certain number of nodes proportional to the block size, uh doing doing random doing this random sampling.

B

Does that make sense.

A

Yeah that makes sense.

B

Yeah, so so yeah, so that's always confusing is because it's it's a. It is kind of a contrived thing that contrives thing that doesn't really happen in practice. So you know assumption here assumption uh some number of light nodes, and we know that this is going to be proportional to block size right.

A

Right and so is it specifically the number of light client nodes or is it the number of light or full nodes which are honest in the network? uh So let's have that many full nodes, but not a single light client will it work or we specifically need that many light clients.

B

uh If you have this number of full nodes, also doing they can pretend to be like clients and do it then do these.

C

B

It's sure the number of notes.

C

B

We can simplify the like number of nodes really.

A

Number of honest nodes.

B

Oh yeah, of course, yeah. This is yeah honestly number of honest notes, yeah, okay, great! So now why? Why doesn't this work? Why? Why is this on each game? uh Also, it seems to be we're running a bit out of time from the schedule. uh Is that an issue.

A

No, that's not an issue. Oh.

B

Yeah perfect, I I have some. I have some time so uh so what's the issue, the issue is: if this is erasure coded correctly, then we can do all this. But what happens if this is not erasure coded correctly, what happens if the block producer just doesn't they? You know they either don't erase or code it correctly or you know they commit to. They commit to something incorrect, because again, this has to be committed to in some merkle route. Would you mercalyze all these shares? What happens if they just don't commit to it correctly?

B

uh In that case, you can't do that. You can't do this right uh or or rather it's like. Even if you do this and then you know the block is available, you might not be able to reconstruct the data nicely. So what you have to do is if the razer coding is incorrect. You need a fraud proof.

B

So how do I prove that these parity shares are do not uh are like are not correct, based on the original data? How would I prove that.

A

So so here you would have to share at least uh at least four shares right.

B

A

That they can reconstruct the.

B

Data yeah: let's: let's assume that you know they reconstruct the data, so you know a full node reconstructs. The whole thing right well,.

A

I'm saying the proof would have to be the size of the number of.

B

Yeah right, yes right.

A

So the proof is essentially.

B

Yeah, the proof is, essentially you give the entire original data and you give the para the parity shares right or you give you know the merkle root and the original data or four of these right and then you just say: okay compute the parity shares and then you'll see that you know the merkle root doesn't match up. So the problem is that a fraud proof of this that this is the that this is being computed incorrectly, is the whole data which exactly you know.

B

This is basically saying just download the full block, and then then you can see that the data that the parity shares haven't been computed correctly, which is exactly what we're trying to avoid right. We're trying to avoid having to download the whole block uh because line nodes are resource constraint.

B

So uh what what? What do we do? So this is where the 2d scheme comes in so see this is razer coding duty.

B

Oh this. I realized that this thing here is probably not useful anymore, so I can probably erase it.

A

We can replicate it uh seven times.

B

I could, but it would still look. It would probably be way too big. So, let's, let's do this, let's do a smaller table. Let's do let's do like oops. Let's drag this down.

B

Okay, let's do a square and then some.

B

Lines- and this is this- is this: is it so? What we're going to do is we're going to arrange our original data in rows and columns so, instead of being just like a single, a single list, a single array we're going to arrange it in rows and columns. So this thing here is our original data right.

B

uh So what we're going to do is for each row we're going to compute the parity share the parity shares for that row, so we extend it this way right. So here's the parity shares of this row. I know there's supposed to be lines here, but I'll not draw them for simplicity, all right so again for this row we compute the parity shares and so on now, for each column, we're also going to compute the parity shares of this column.

B

This right and then you can do this. You know this, the third square, if you you know, if you copy one of these two or if you you, compute parity shares this way, it doesn't really matter right. Just this is kind of an implementation detail, but this is also going to be some sort of parity shares right. So.

A

This is important mentioning here, which is obvious for people with the background in math, but it is not as obvious otherwise is that it doesn't matter how you compute this fourth square, whether you erase your code, columns or azure code rows, you'll get the same values right.

C

A

So like a particular value.

C

A

Yeah so so that is not immediately obvious. I guess it requires understanding of some math behind.

B

Yeah, but like ultimately, this this doesn't matter. What really matters is that you know, as long as everything is, is a parody in some way, then that's all that all that matters.

C

B

Yeah, so even if it were different, it wouldn't matter just you know, you just say you know this is this. Is this is the direction I choose essentially? So this is your original data, so we note that uh the 1d scheme, our parity shares- are twice as big as our original data right here. Our parity shares are three times as big as our original data right. So each of the side here is like square root of block size, square root of block size, so the length of this big square would be.

B

You know, two square root of block size and two square root of block size right. So let's type this out, so this one here is, you know oof this one is square root and, let's say n is n. Is a block size right? This one here is also squared and there's also the square root of n, and this one here is also square root of n right.

B

So, in total, the length of these things is 2 square root of n, uh and then what we're going to do is we're going to commit to a merkle root for each row and each column, so in total, so with this one here we just need one one merkle root right: we just take these and we just microlight them right.

B

So one marker root here we need to mark the root for each row and each column, so in total our commitment here is going to be 2 times 2 times, 2 squared of n right, because this is 2. This is a two square root of n, and then we have. We have two of these right, so so in total, it's four is four square root of n oops per square event. So this is our commitment size. So this one here needs to go into the block header.

B

Now we can have like a super compact, commit commitment where you mercalize this, so you can kind of represent it as like. A two like two in two stages, but ultimately uh nodes that want to do these data availability checks need to download this four squared event commitment on commitments.

B

uh So what this means is that this does increase the size of the block header. uh It means that now the block header has some overhead, that's proportional to the square root of the block size, as opposed to just being constant sized right, and it's assumed that all light nodes will have to download this again. The super light nodes can just download the merkle root of these and not do data availability checks and just trust it on a majority.

B

uh But you know the the secure light clients or that do data availability checks uh will need to to download this four squared event. Commitment, okay, great! uh So now that we have this, uh how many? How many shares does an attacker have to hide to prevent uh to prevent someone from reconstructing this? The original data and therefore the full block, approximately.

A

Okay, so approximately it will be so to reconstruct everything we need approximately n right.

B

A

Of those little shares.

B

Yeah yeah, that's true yeah to reconstruct everything you need around n yeah, where n is the block size.

A

Right so so I will need to hide 3m right. Oh.

B

A

Or do I need to hit n.

B

You need to hide n.

A

So n is sufficient.

B

I know it's confusing. We can use ratios right here here. The attacker hide half plus one right.

A

Yes here here, they need to hide three three fourths, plus one right or like three fourths, plus plus.

B

Seven three chord for three three-fourths: uh they have to hide. Let me draw the rectangle in red. They have to hide this much right. So it's one quarter, plus one.

A

Oh yes, yes, that's correct!.

B

Yeah, so we, and we can see- is that if they hide let's, you know, let's say this is eight right. If they hide five from this row, you can't reconstruct the row if they hide.

C

B

From this row you can't reconstruct the row and so on for the columns right, but if they didn't hide these, you know if they left you. They left you a bit here. If they revealed this one, then you could compute the whole column and then from that, then you can compute the rest one by one right, so they kind of have to hide this uh for a further large enough for a large enough number. Now you know. If, if you have very light note- and it starts- you know random.

B

You know it starts rounding the sampling here here here uh for each round we'll do the same as before. uh So here's round one. What's the probability that a light node has been tricked that the data is available, but it's not.

A

uh It's uh one quarter right.

B

A

The light node.

B

Will get tricked if it lands on something.

C

That's being disclosed.

A

B

It's going to be three quarters, uh so our round two uh tries to sample again. What's the probability now.

A

uh Nine sixteenths.

B

Yeah, not nine or nine over 16 right so that so you you keep going right. uh So we see it, it doesn't decrease as sharply as the previous time. But you know it does still decrease exponentially, which is good. So you need to do more rounds of sampling to get the same guarantees, but it means you get a better guarantee elsewhere. So that's a better guarantee elsewhere.

B

If we have to prove that the whole thing is erasure coded incorrectly note that we only have to prove that a single erasure coding computation was done incorrectly right, which means the fraud proof is now a single row or a single column in size right.

A

B

A

Which is just square root, yep.

B

So now the fraud proof would be 2 square root of n, as opposed to being the as opposed to being n with, like the the.

C

B

Of the original data right so now so fraud proof is big, o of uh square root n. Where n is our block size right over here up top the naive scheme, the fraud proof is big, o of n right. So.

C

B

Is kind of this is kind of where, where we see the amazing thing is that we now have a fraud proof, that's sub, linear in size and again, if you only have the broadcast as fraud proof out, uh if there's a fraud proof in the happy case, uh the only thing you need to download is this commitment and then a fixed number of of samples, a fixed number of sampling right. uh So so this is kind of this is this is kind of the nice property?

B

Is that the number of samplings you have to do is is fixed, uh it's not related to block size at all. uh So how would you increase? Let's say.

A

While the number of samplings is not related to the size of the block, the uh the light header now is uh yes to the square root right. Yeah.

B

Yes, no, yes, it does so yeah. So one of the trade-offs is the light. Client headers are larger. uh So what this means is that, if you want to kind of take full advantage of this, you would want to have a smaller number of headers, each of which have larger blocks right, which means that generally you'd want to have slightly longer block times than what you would see in you know some changes that have really really fast block times right.

B

So, instead of going for the one second block time, maybe you want to go for the 30 second block time, uh which will allow you to take bet to take more advantage of of this factor here right.

B

So that's one potential downside, but you know the gains is that you have now secure light clients, which is amazing because as before, if the two choices are run, a full node or absolutely no security, uh that's not exactly a very good trade-off, especially if you want your base layer to process many transactions where full node could be potentially expensive.

C

B

Right so now we have a third choice, which is you can run a light client with data availability proofs and do this with sublinear cost and still be pretty damn secure so long as there's one honest, full node out there, which is a good choice right, no one's forced to use this. But now we have this option.

B

A

Well, it's one oldest full node among our peers right so.

B

We need to you.

C

B

No, no eclipse attack yeah, which, which is you know, clubs attacks are kind of hard to pull off, maybe maybe not but yeah. There's a is an assumption. So uh so one thing we know is that if let's say we want to keep some, we have some security guarantee parameter right.

B

Security purity guarantee right. So this is kind of like our guarantee that you know some. Some fixed fraction of light nodes aren't going to get tricked right. So this is. This is going to be proportional to the number of rounds right number of rounds that we set as a parameter times uh times the number of nodes, doing sampling right.

B

So, as the as the number of nodes increases, then our security guarantee increases right right.

C

B

As the number of rounds increases, so does our security guarantee right.

A

Yeah also, I don't see your text until you.

B

Continue, let me oh okay, uh so so you know we have. We have some relationship here. So if we want to keep our security guarantee fixed and we keep the number of rounds fixed right note that if we increase the number of nodes right, we can actually increase the block size and have the same guarantees.

C

B

All right, so this is kind of an amazing property that you know regular, like the we're not talking about lazy ledger yet, but just just this property. We have the amazing property that data availability checking uh allows you to have the same guarantees for larger blocks. As you increase the number of nodes right know in a regular blockchain. If you execute all the transactions, then okay, you increase the number of nodes. You don't get more throughput right, like every node still has to validate every transaction. Here.

B

Every node doesn't fully fully check the entire block right. Every light, node only checks, the uh only only checks, the fixed number of samples and you download the square root stuff. So, as the number of nodes increases, we can have the same security uh for larger block size, which is, which is a really nice property. Okay. So now now kind of the two pieces of the puzzle are together.

B

We have uh we have fraud proofs for any arbitrary state transition and we have a way for light nodes to make sure the data is available so that fraud proofs can be constructed right.

B

So there's kind of one additional side caveat here before we start talking about lazy ledger, which is uh note that blockchains always need to check for data availability.

B

You may have heard some people talk about say of one block chains right where, instead of using fraud proofs, you use validity proofs.

C

B

Know is like a succinct cryptographic proof that some computation is valid and you might think well. The only reason you need this is for religious for fraud boost right. You might say if you have validity proofs you, why do what do you care if the data is available or not right? uh The transactions are valid. The the miners can't create a billion coins.

A

Well, you know that some state is valid. It would be nice.

B

A

What exactly is the state that is valid.

B

That is the problem is that if a minor block producer in general makes a new block but doesn't tell anyone what the new state is like. Do you have a state route? But you don't know what the state is. Essentially, everyone's coins are burned, you they can move their coins because they don't know what the state is.

B

So there is no such thing as no one blockchain all blockchains to be secure need some way of solving data availability, and that means either have everyone run a full node and uh and like actually try to fully download the block. It means making an honest majority assumption at which point, what's the point of the validity proof, if you're, assuming that or it means doing these data availability checks right. So there's no such thing as one blockchain.

C