YT YouTube2Text

YouTube2Text → Transcripts → RLNC vs Reed-Solomon: Optimal Blockchain Data Coding Explained | MIT's Muriel Médard

RLNC vs Reed-Solomon: Optimal Blockchain Data Coding Explained | MIT's Muriel Médard — Transcript

by Optimum · 5,609 words · 1,002 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:06Hi Moritz. Uh good to have this chat
0:08with you today uh to talk about
0:11Reed-Solomon and random linear network
0:13coding RLNC. Uh
0:16you and I at this point I think we go
0:18way back
0:19uh but maybe let's introduce ourselves.
0:22Uh I'll start. Uh I'm Muriel Médard. I'm
0:25co-founder CEO of Optimum.
0:29I hold the NEC chair in software science
0:31and engineering uh
0:33in the
0:34electrical electrical engineering
0:35computer science department at MIT. Uh
0:39and that's actually uh how I met Moritz
0:42uh when he was visiting from uh
0:44Technical University of Munich and
0:46Moritz uh if you want to introduce
0:48yourself.
0:49Yeah, thank you. Um first of all,
0:51pleasure to have this chat. Um my name
0:53is Moritz Grundmann. I have been
0:56um working on coding for some time now
1:00at Technical University of Munich and uh
1:02visiting you at MIT where we worked on
1:05uh
1:06actually error correction coding
1:08together.
1:09Um and yeah, today we're going to talk
1:11about uh random linear network coding
1:14and Reed-Solomon coding and all of that
1:17sort of
1:18in the um in the context of blockchain
1:22and
1:23um I'm looking forward to our chat.
1:25Yeah, me too. Me too. So
1:27uh maybe for our listeners we can start
1:30with what is coding. Uh some of the
1:32people who will be listening to this
1:34uh know full well what it is, might um
1:37be specialists even. Uh some of the
1:40folks uh might just be coding curious.
1:43Uh
1:44and you know, you mentioned that we
1:46started working together on uh error
1:48correction errors
1:51uh which is data being corrupted, being
1:53wrong and erasures which is data
1:56missing, unavoidable in the real world.
2:00Um and you need to actually have ways to
2:03manage uh these potentially
2:07lethal consequences of having data being
2:10wrong or missing. And what does
2:14coding do? Coding actually splits the
2:17data into pieces
2:20often in blockchain we call them shards
2:23and then it adds some redundancy.
2:26Effectively, it creates equations.
2:29Um and with these equations which add
2:32extra
2:35uh redundancy or I I prefer calling it
2:37repair always rather than redundancy.
2:40Um then we can actually reconstruct the
2:42original data.
2:44Um I don't know. What do you prefer?
2:45Repair or redundancy? How do you like to
2:48call it, Moritz? So yeah, I mean I guess
2:50you were the first person who called I
2:52heard calling it
2:53repair. I like that that word a lot
2:56because it's a much more positive,
2:58right? It has a it has a positive um
3:01intention behind it. We want to preserve
3:03the information content or um in in the
3:06message actually. So I guess
3:09repair is a much better word. Yes. Yeah,
3:11but we we will
3:13slip back often into calling it
3:14redundancy which is more common
3:17terminology for it. You know, redundancy
3:20somehow sounds a bit superfluous.
3:22Repair, as you said, is much more
3:23positive. Like you have to fix it, you
3:25know, it's the code is there to fix the
3:28problem. You shouldn't think of it as
3:29superfluous.
3:31Um yeah, absolutely. So
3:33um
3:35Reed-Solomon or RS we hear a lot about
3:39it. You know, these codes have been
3:40around uh longer than you and I have
3:43been and even I have been on this earth.
3:46Um they're definitely widely used in
3:49storage uh
3:50in point to point communications.
3:54Um I'd love to hear how you described
3:57our we how you describe Reed-Solomon
4:00codes.
4:01Uh yeah. Um I mean Reed-Solomon codes in
4:04a sense uh
4:06they are sort of the prototypical code,
4:09like the first code probably you come
4:11across when you think about error
4:14correction coding or when you learn it
4:15in class, for example.
4:18So the idea is actually
4:19pretty simple, I would think. So
4:22um
4:23given that I have um
4:26given that I have a
4:28let's say let's say
4:30polynomial, let's say a a function. So
4:32the easiest representation probably
4:34everyone knows from school is
4:36is a line.
4:38Um I can describe this line by any two
4:41points on this line, right? So
4:44but um I can also say, "Okay, I'm going
4:46to not generate two points, but maybe
4:48four or six or eight points." And then
4:50when I give these
4:52two, four, six, or eight points to
4:53someone else
4:54they I can maybe drop two
4:57maybe two um maybe one point is going to
5:00um I'm going to mess something up and
5:02and the coordinates uh uh distorted. So
5:05um
5:06I can eventually re uh sort of
5:09recreate the original line out of any um
5:13any uh two um correct points in that in
5:17that sense. So I can I can drop um I can
5:20drop some. This is like the first and
5:23probably very simple way of creating
5:26uh redundancy and um
5:29therefore re
5:30uh regenerating or like uh
5:33getting the
5:34um the original information back
5:36um in set of lossy or also uh
5:40lossy environments. So
5:42um
5:44I like your description, by the way. I
5:45think that's much more intuitive. I I
5:46always use equations cuz I'm used to
5:49thinking in terms of equations, but I
5:51like your line much better. You know,
5:54it's like if you have a line
5:56all you need is two points. If you lose
5:58a few, you're okay.
6:00Uh
6:01Yeah, definitely.
6:02>> That's that's a much nicer way to to
6:04describe it, much more intuitive. I'm
6:06I'm going to borrow that one just so you
6:09know.
6:10>> [laughter]
6:11[gasps]
6:11>> Um yeah. And and you know, as as you
6:15said, you know, the core intuition is
6:17you're treating the message as a
6:18polynomial. I mean, a line is a
6:20polynomial. It's just a pretty simple
6:22polynomial of degree one.
6:25Uh my favorite polynomial for sure. Um
6:28and you know, as we said, you use this
6:31in so many different systems, whether
6:33it's storage um media
6:37um uh often this is called uh forward
6:40error correction. And we talked about
6:42errors and erasures. There's a little
6:44bit of a
6:45uh of an unfortunate coincidence of the
6:49E letter because sometimes people talk
6:51about FEC as forward error correction,
6:54sometimes they call it forward erasure
6:56correction, and there's a natural
6:58confusion that comes out of the fact
7:00that erasure and error both start with
7:02an E. Um and um
7:04it's you know, there's definitely
7:06connections, but they're trying to do
7:07different things, right? And and um if
7:10you think of Reed-Solomon codes, of
7:11course, they were originally
7:13designed for error correction with some
7:16properties in mind.
7:18Uh some of them are actually very
7:20constraining
7:22uh because they were
7:24designed for error correction. And uh
7:27wanted to, you know, hear about your uh
7:30how you view those constraints.
7:32Yeah, sure. I mean, I can I can share
7:34some um
7:36some image here. Let me give me a second
7:39to share.
7:40Um
7:42share my screen.
7:45So
7:46um basically what we see here
7:49um we just talked about we just talked
7:52about redundancy or repair, so to speak.
7:55Um
7:56when we think about Reed-Solomon codes
7:58and we see Reed-Solomon codes on the
8:00left side
8:02um we see that
8:04they don't um they don't allow you to
8:08combine any sort of
8:10um
8:12combination of how much information or
8:14how many many many many pieces you want
8:16to trans you want to transmit
8:19um either uncoded or encoded and the the
8:22rate at which you want to transmit it,
8:23like how much
8:25um how much uh redundancy you add to
8:27each one of those. So you can see, for
8:29example
8:30um you have a length uh length n code.
8:35So you have, for example, a 32 um a
8:39length n equals 32 code 32
8:42n equals 32 um code and you have
8:46um
8:47only specific
8:49um specific uh
8:52code rates, like redundancy rates you
8:54can add to this code. Like the
8:56core underlying reason for this is
8:58basically
9:00um
9:02the fact that we have to construct a
9:04polynomial in the first place
9:06um and we do that over a so-called um
9:09finite field which has inherent
9:11properties that sort of restrict the um
9:14the length or like the
9:16the two properties of the code that um
9:19that define that define its um
9:22its its repair.
9:24And we see on the other hand that
9:27um when we think about like purely
9:30random ways of um constructing codes,
9:33codes which are not defined by core
9:35polynomials we don't have these
9:37constraints, right? So
9:39um we see here that sort of any
9:42combination of um
9:45code length n and uh pair
9:48are possible which is um
9:51yeah, just just a very very illustrative
9:54thing that
9:56Reed-Solomon
9:57Yeah, yeah. It on the left-hand side and
10:00and just just to remind our listeners
10:02that the rate here
10:04indicates what percentage of the
10:07transmitted data is actually payload.
10:10So one means that the rate is
10:14including absolutely no repair slash
10:17redundancy.
10:19All of the data is payload
10:21and so as you have a lower rate, you
10:24have more redundancy. So you have more
10:26ability to fix as we've talked about,
10:29but on the other hand it comes at a cost
10:31of transmitting data which is not
10:34information bearing. And as you show,
10:37by the way, wanted to thank
10:39our colleague collaborator
10:41Ritson, my collaborator,
10:44Ken Duffy, who's the
10:46chair of the math department at
10:47Northeastern University here in Boston
10:49who who first came up with this very
10:51nice
10:53way to visualize
10:55what coding is doing. But yeah, what you
10:56see on the left-hand side is it's it's
10:58almost all white space. It's basically
11:01space that is not available to you for
11:04design, right? So it's a it's a really
11:06really constraining thing to be working
11:09with codes
11:10where you're artificially
11:13restricting yourself to
11:15basically giving up on most of the
11:17design space.
11:19Yes, totally. Yeah.
11:22So no, no, thank you. Thank you for
11:24walking us through through through that
11:26picture. Now, we've been talking right
11:29now about a Reed-Solomon which as we
11:31mentioned was really designed originally
11:34for point-to-point system meaning
11:36there's a single entity node,
11:41you know,
11:42user who does the coding and it sends it
11:45to one node that does the decoding that
11:50reconstruction fixing that we've talked
11:52about. But of course in the network,
11:56you don't just have one sender, one
11:58receiver. Well, you could, that's the
11:59world's simplest network formed by a
12:02single link. Not very exciting. Not
12:04exactly blockchain ready.
12:08And to be able to think about a network
12:11at large,
12:13um
12:14then you really need to figure out how
12:17the information is being managed within
12:21the node.
12:22Now, you could just, you know, put
12:25blinders on and pretend that the entire
12:27network is a single link. But you'd be
12:30losing so much because effectively
12:32you're
12:34pretending that the network is not there
12:37and you're not taking advantage of the
12:40potentially really rich topology and
12:42capabilities that the network is giving
12:44you, right?
12:45It's like you have this square peg which
12:48is a Reed-Solomon code, you have this
12:50round hole and you're just going to take
12:52a hammer and pretend it goes in, right?
12:54And
12:55and you know, we we know that that's
12:57that's not the best thing.
12:59And so, you know,
13:01again going back to restrictions, it's
13:03not just restrictions in terms of that
13:06design space that we just saw that's,
13:08you know, vast white space of, you know,
13:12unused design area,
13:14but it's also unused space inside the
13:17network because the intermediate nodes
13:19are not contributing
13:21to the overall repair, maintenance,
13:25effectively robustness, and efficiency
13:28of the data.
13:29And I wanted to hear how you describe
13:32how RLNC, which we mentioned at the
13:35beginning is randomly network coding,
13:36and of course you just showed
13:38in that figure some random coding. It
13:41was not network coding, it was at a
13:43single node. But how RLNC changes this,
13:46how how you explain it again to to your
13:49colleagues. Yeah.
13:51I mean I really I mean I think the point
13:53to start here if we start RS is that we
13:56really talk about um
13:58a different problem definition at this
14:00point, right? You mentioned it.
14:02We were talking also in the example that
14:04I gave about
14:06I'm going to give you data, I might drop
14:08some of it,
14:10some of it might get corrupted. That's
14:12the typical point-to-point link, right?
14:14DVDs
14:16or similar point-to-point channels we've
14:20seen in in in communication systems.
14:22Now,
14:23when we talk about networks,
14:27things get
14:29are different, right?
14:31Because the coding operation, we can
14:34still use we can in theory still use
14:36something like Reed-Solomon codes and we
14:38would
14:39only use coding at the edges.
14:41But we don't use all of the
14:45intermediate nodes which might also
14:48participate in the coding operation.
14:51And therefore might also help in sort of
14:55recovering recovering erasures. We
14:58network level we mostly talk about
15:00erasures.
15:01Packets being dropped, packets getting
15:04lost.
15:05And random linear network coding is a
15:09very unique kind of network code in that
15:13it just says
15:16the way we do coding
15:18at intermediate nodes, also at edge
15:21nodes,
15:22is basically random. Like
15:25we don't really give the nodes any
15:28instructions on what they do. They just
15:31form random equations, recombine them,
15:34and then send them along.
15:36Because you might think about, yeah,
15:37well, now if the whole network does
15:39coding, how does everyone even know what
15:42they what they have to do, right? But
15:45random linear network coding says just
15:47combine
15:49packets randomly and you're going to be
15:51fine in the end.
15:52And this is a huge saving in complexity
15:56and makes the makes the whole system so
15:58simple. But
16:00I guess
16:01you are the best person to talk about it
16:03in a sense because it's been
16:05one of your one of your, let's say,
16:08longest-standing works, random linear
16:10network coding, going back
16:12>> Yeah. to the early 2000s.
16:14Yeah, yeah, absolutely. And actually I
16:17remember when we were working on this
16:20along with, you know, wonderful
16:22collaborators
16:24including one from TU Munich, well, at
16:27the time it was University of Ulm, Ralf
16:28Koetter,
16:29and my student Tracy Ho and many other
16:34wonderful colleagues.
16:35Um
16:37I remember that we got so much pushback
16:38because people really thought that you
16:40had to be able to do better
16:42by being very very clever.
16:45And
16:46you know, that somehow if I had more
16:48information, if I had state information
16:50about what node was doing what, what
16:53shard was at which node, you know,
16:55surely you can do better than just
16:58choosing coefficients randomly. And you
17:01know, by randomly we don't mean
17:04with some sort of perfect pseudo noise
17:06sequence at all. Randomly really means
17:09just you know,
17:12not in weird constrained ways that might
17:15work wrong.
17:18Yes. And
17:20that did you know there was a lot of
17:22pushback because it seems
17:23counterintuitive as you say, it's very
17:25simple. It's kind of funny, it's very
17:27simple from a
17:30implementation perspective, it's
17:32definitely extremely suitable for
17:35something like
17:37blockchain which is decentralized,
17:41but conceptually it really requires a
17:43leap of faith.
17:45And
17:49you know, people tried so much to do
17:51things instead. Well, could you take a
17:52Reed-Solomon and change it? Could you
17:54take other kinds of codes? And we've
17:55talked about Reed-Solomon and of course
17:57there are many other, let's say,
17:59traditional codes like
18:02fountain codes, we transform codes, you
18:04know,
18:05Raptor codes and so on.
18:07Or to a little different in that they
18:10adapt on the fly how much redundancy or
18:13repair they put in.
18:15But all of those codes are still
18:17end-to-end as you say at the edges of
18:20the network.
18:21And I think to me what's most surprising
18:25is that
18:28RLNC is not just optimum, but that the
18:30difference between the optimum
18:33and the suboptimum
18:35like a Reed-Solomon, like a Raptor, is
18:38not, you know, 5%, 10%. I mean sometimes
18:40you're like, okay, it's not optimum, but
18:42who cares, right? I'm close enough. It's
18:45it's, you know, exponentially growing as
18:48the network gets larger.
18:50I'd love to hear how you describe the
18:52intuition for for why that is. You know,
18:56yeah, cuz I think you always have such
18:58good ways of describing that. Sure.
19:01I can share like another
19:03um
19:04another short
19:06image of that. So
19:09we've been talking about the difference
19:11of
19:12encoding end-to-end versus using
19:15leveraging the entire network
19:18to do coding.
19:20And and that is really where the core
19:24difference in especially in throughput
19:26is taking place.
19:28So
19:29we can look at like a very simple
19:31example, right? So
19:34we have two nodes which want to
19:36communicate
19:38a message and the message has to
19:40traverse through
19:43let's say two other nodes, right? So we
19:45have these two purple nodes.
19:48And in the one example we use a typical
19:51end-to-end encoding and in the other
19:53example, we use
19:55um
19:56network coding like random linear
19:58network coding, which actually uses
20:00these intermediate nodes to
20:02um do, let's say, uh additional coding
20:05or to to do coding themselves. So, what
20:08we see in the
20:09in the first um in the first
20:11instantiation when we have end-to-end
20:13coding is that
20:14losses compound, right? We talked about
20:17coding being this idea of adding
20:20um
20:22how do you say it? Adding repair. Um
20:24uh adding redundancy, and
20:27um
20:28this redundancy, if we uh think about
20:30erasures, is is getting lost along the
20:32way.
20:33So, that if I wanted to um securely
20:37transmit uh a message from A to B in an
20:40end-to-end coded setting, um I would I
20:44would have to account for the entirety
20:47of the losses that happen along the way
20:49to make sure that the message is
20:51arriving at the end.
20:52Now,
20:54what happens in um
20:57random linear network coding or um
20:59when when we use coding at intermediate
21:01nodes,
21:02call it recoding,
21:04um is that
21:06every one of those nodes
21:10um kind of
21:12uh does does its own coding operation in
21:15a sense. So, the
21:18quality
21:19or the the the losses don't compound
21:24path from source to sink,
21:27but
21:28so, the the um the overall quality is
21:31kind of the quality of the weakest of
21:34those of those links. So, in that sense,
21:36we have in the first example, we have uh
21:39um 37% of losses. Um in the second
21:43example, we only have 10% of losses.
21:46Um
21:47and this is really the um if you think
21:51about it, these
21:53if I make the chain even longer,
21:55then in one example, with each and every
21:58hop, I have to add more and more
22:00redundancy in the first place, while in
22:02the second example, um it doesn't
22:04matter, right? So, the chain can
22:07can stay
22:08uh can get as as long as it wants. Um
22:12I still um only have to add the same
22:15amount of redundancy up front if I
22:17really want to make uh uh a safe um
22:21a safe transmission here. And this is
22:23sort of where the one of the core
22:26um advantages where the random linear
22:28network coding lies, but um
22:31Yeah, yeah, absolutely. No, no, I think
22:33you you you you explained it
22:35beautifully, and I think you know, you
22:37mentioned compound. It's really the
22:38difference between simple interest and
22:40compound interest. Yes. Uh and and you
22:44know, they grow exponentially apart.
22:47That's That's the whole power of it. And
22:49so,
22:50with uh random linear network coding,
22:53you can do what you mentioned, that
22:54recoding, because you can basically
22:57create codes on the fly from whatever
23:02coded pieces, whatever equations you
23:04have, you can make equations out of all
23:06the equations without having to recover
23:08the original data.
23:09Uh whereas in traditional systems, uh
23:12traditionally coded systems like
23:14Reed-Solomon, you actually have to get
23:16back to the original data. So, you can
23:18either just forward along
23:21or you have to decode, recover the
23:24original data, and start over again.
23:26Um
23:28And you know, that separation, which
23:31looks almost like a subtlety, just a
23:33technical subtlety,
23:35is actually massively powerful. And so,
23:40you know, it's not like, "Oh, it's all
23:41close to as good." No, it's
23:43exponentially worse to do a Reed-Solomon
23:46code, you know.
23:48Uh and again, this was something which
23:49early on, I think a lot of people had
23:51trouble getting their heads around, you
23:53know.
23:54Um because it seems so counterintuitive.
23:58Um but you know, you can try it out and
24:00see see right away the the the the
24:03difference. Um it's you know,
24:07it kicks in. It kicks in very, very
24:09quickly. So, yeah, no, thank you. Thank
24:12you for for stopping us to this. So,
24:13okay, so we've we've talked about RLNC
24:15encoding, um Reed-Solomon coding. I
24:18should mention, you know, that you know,
24:20the the the recovery is often is what we
24:23usually call decoding. We talked about
24:24that repair. Um that actually is very
24:27simple for erasure
24:29uh erasure codes.
24:31Um and you can decode a Reed-Solomon or
24:34RLNC or anything else
24:36always in the same way. Um you basically
24:39just have this reconstruction from a
24:43bunch of equations, and it's very fast.
24:45It's very simple.
24:48And so, the the decoding itself for
24:50these erasures uh
24:52is actually quite universal, right? It's
24:54It's the same decoder that you can use
24:56for all of those. So, you can mix and
24:57match. Uh and and still keep the same
25:00decoder. So, we have just a few minutes
25:02left. Uh I want us to jump to uh the
25:05blockchain applications, right? So,
25:07we've talked about the fact that RLNC is
25:09decentralized,
25:10you know, a priori decentralization goes
25:13really well hand in hand with
25:14blockchain. Um but let's talk a little
25:17bit about where coding shows up right
25:19now. Um and um you know,
25:24of course, we're both at Optimum, and we
25:27are using Mom P2P, which is RLNC-based
25:30gossip. Um we're uh been working with
25:34Ethereum validators.
25:37Um and you know, we're going soon onto
25:40just a few weeks, uh we're going to
25:42mainnet, uh which is extremely exciting.
25:46Um but you know, um traditional
25:49uh you know, as we mentioned, suboptimal
25:51codes are used, for instance, in Solana
25:53with Turbine, um Rotor, which is the the
25:57next version that's coming up in Solana
25:59with um Alpenglow is also going to be
26:01using Reed-Solomon.
26:04Uh we mentioned Raptor codes. Monad uses
26:06those. Um and you know, wanted to hear a
26:11little bit your view of why this matters
26:14in blockchain.
26:15Yeah, I mean, the I think there's
26:17actually two interesting
26:20kind of uh
26:22sort of applications of of coding in
26:24blockchain that we've known uh so far.
26:26So, one is like really the obvious one,
26:28right? That we've just talked about,
26:30which is um
26:32propagation of of payloads.
26:34Um if we talk about Ethereum,
26:37um we think about uh either either
26:40blocks or also blobs,
26:42nowadays blob columns.
26:45Um
26:46and if we uh
26:47the the other kind of application is
26:49really what we call data availability
26:51sampling. Now, sticking with um
26:54sticking with uh block propaga- with the
26:57propagation uh so far,
26:59um I would think there is two kind of
27:02different um different systems. There's
27:05one um sort of the uh permissionless
27:09uh
27:10uh
27:10meshes, which is um all the
27:13network meshes, which is Ethereum would
27:15be would be an example for that. And the
27:17other one would be
27:19more of a structured uh broadcast
27:21architecture, where you have a
27:23permissioned set of nodes. Uh Ethereum
27:26Solana um
27:27or or Monad would be part of that. And a
27:30more, let's say, structured tree along
27:33which the messages are propagated. Um
27:36now, coding is useful in both of those
27:38cases, and um we have built with uh
27:44uh Mom P2P, the first um gossip protocol
27:47that uses RLNC, first for uh Ethereum.
27:51And
27:53um
27:54we have seen we've seen uh amazing gains
27:57in that sense. So,
27:59talked about with uh Zajida last time
28:01about the latency improvements that
28:03we've seen in Hoodie.
28:05Um
28:06and the reason why this is um why this
28:09is important is um
28:11severalfold. I mean, I guess you can
28:13uh talk about it from a commercial
28:15perspective much more
28:17than I can, but
28:18um we see especially in these last
28:21couple of months that um the Ethereum
28:24network has, for example, um
28:27been put under strain by
28:30um a lot of new messages being produced,
28:31especially in the context of Fusaka,
28:33with blob columns being propagated. So,
28:37um
28:38it needs faster um data propagation, and
28:41coding is uh the the number one tool to
28:44do that.
28:45And RLNC, the the optimal one.
28:47But um
28:49yeah, that's uh that's about the
28:52Yeah, no, that that that's that's great.
28:54That's a great description. And also, as
28:56you said, sort of it's it's inherent to
28:58the need for scaling, right? As we said,
29:01one is scaling,
29:04you know, in a way which is getting
29:06exponentially worse, and ours is
29:08scale-free, right? And you can't beat
29:10that, you know. You can't beat scaling.
29:12You can try.
29:14>> [laughter]
29:14>> Um you also mentioned uh DAS. I wanted
29:17to just spend a couple of minutes
29:18talking about uh the data availability.
29:21Yes. Uh
29:23this is like the second kind of
29:24application of
29:25>> Yeah. which is
29:27also like an interesting one. Um
29:29uh quite counterintuitive. So, the idea
29:33is that um I want to have a way to check
29:37if some data is available without
29:39actually downloading it.
29:41Which uh sounds kind of
29:43counterintuitive, because the easiest
29:44approach would be, let's say, you have
29:46some data, and I don't I just ask you if
29:49if you have it and if you do then I just
29:52then I just believe you but we in a
29:54trustless environment I need to get some
29:57confirmation right some sort of sort of
30:00proof for that.
30:01And the idea is that usually
30:04in the beginning people used
30:06erasure codes like also Reed-Solomon
30:09codes to say
30:10okay if I
30:12get just a bunch of just some
30:16coded pieces
30:17then I can be probabilistically sure
30:20that
30:22I could if I wanted to download the the
30:24entire thing.
30:26And um
30:28the the the basic premise behind this is
30:31that if enough people were to sample
30:34coded pieces then
30:37you would have to withhold at least a
30:40certain percentage of of pieces for me
30:43to be for for us to be unable to decode
30:46and therefore I would I wouldn't take
30:47that.
30:49So it's like
30:51I uh
30:53I'm asking I'm asking you for some
30:55information and I'm not asking you
30:58directly for it but for some encoded
30:59version of it and
31:02in order for you to not give it to me
31:04it's very unlikely
31:05that I'm not not going to catch you.
31:08So
31:09um
31:10Yeah I did just just to interrupt you
31:12know the the way I like to to describe
31:14it I don't know you know it's like so
31:15it's you know my mother was a history
31:17professor and you know suppose you had
31:19to do a history exam and rather than ask
31:21somebody what was the date of this
31:23battle and the date of this and the date
31:24of that you go just give me the sum of
31:27the dates. You know what is the
31:28likelihood unless they know each and
31:30every date that they're going to get the
31:32sum correct you know.
31:34Yeah yeah that's that's a pretty good
31:36description I mean
31:37>> It's like the one question exam.
31:40>> [laughter]
31:41>> Exactly so
31:43so so No partial no partial credit.
31:48Yeah
31:49I think it's actually a pretty good
31:50pretty good analogy so the
31:52if you think about and now we come back
31:54to Reed-Solomon and fixed rate coding
31:56again these kind of codes they give you
31:58sort of
31:59a fixed set of questions you can ask.
32:01>> That's right. You can only ask the sum
32:04of the
32:04the sum of the
32:06dates and that's it you know and
32:09of course pretty soon the the students
32:11will learn that you do that
32:12>> [laughter]
32:13>> and learn that one thing.
32:15Yeah definitely definitely. And and also
32:19here like one one thing that you we've
32:20also been looking into is what if you
32:23actually make that
32:25question space if you want to stick with
32:27that metaphor
32:28what if you make that flexible? Right.
32:32Now what happens if I actually tell you
32:35which
32:37dates of the battles you have to sum up
32:39and you have to answer me.
32:41And this is essentially what random
32:43linear network coding
32:45does.
32:47And I also have an illustration for that
32:50so
32:50>> Yeah yeah absolutely. Yeah it's like
32:52give me five times the
32:54the year of the treaty of X with you
32:57know two times the battle of Y and
33:00>> [laughter]
33:01>> Exactly exactly.
33:03So
33:04um
33:05the the idea here is
33:07now we have
33:09usually
33:11systems in in use today use use fixed
33:14rate codes we see systems with LDPC
33:16codes and also 2D Reed-Solomon codes.
33:20Um And by the way we we haven't talked
33:22about LDPCs with the yet another of
33:24these classical codes.
33:27Exactly. Yeah they were actually
33:29invented by my
33:32doctoral advisor Bob Gallager. It was in
33:34the 60s it was his doctoral thesis yeah.
33:38So yeah you can you can go like this is
33:4019 I think 1960 exactly Reed-Solomon
33:43code and this is 1967 or something like
33:45Uh 62.
33:47Uh 62 okay yeah that's uh
33:51Yeah yeah yeah and actually the kinds of
33:53codes that are used in
33:55um which are you know product {slash}
33:58tensor codes that are used for instance
34:01in Celestia and these systems are
34:03actually invented
34:05even though the the Reed-Solomon was
34:07invented later the general format of the
34:08code was invented by Bob Gallager's
34:11advisor also at MIT who was Peter Elias.
34:15Uh so there's yeah there's
34:18Yeah so it's
34:19>> line there. Yeah it's all inter
34:21intertwined RLC 2D and
34:23>> Yeah
34:24yeah it's it's all in the academic
34:25family yeah. Yes definitely definitely.
34:28So what we basically see here is that
34:32we're staying in our metaphor these are
34:33like the number of questions that I have
34:35to
34:36that I have to ask uh
34:39if I want to check data availability and
34:41this is the
34:42probability that I'm going to get that
34:45I'm going to get fooled right that I'm
34:46going to
34:47>> Yeah the student didn't actually know
34:48but gets lucky. Exactly just gets lucky
34:51that I answered a question correctly.
34:54Um
34:55And by the way this is a logarithmic
34:57scale right so you're multiplying by 10
35:00every time so
35:01a change here actually shows a huge gap.
35:05Yes so this would be
35:0710% probability this would be point 001%
35:12probability. Yeah.
35:15And what we see here is basically
35:17I can get to the same kind of certainty
35:22about data being available
35:25by just asking two questions
35:28as if I were to ask 70 questions from
35:30the predefined set or 150 from the
35:34from the other predefined set it's like
35:36I can either ask real novel questions
35:39and I have the student has to actually
35:41learn and understand the material or I
35:43ask like
35:45a huge amount of
35:48previously
35:49let's say preparable questions
35:52and and sort of my confidence in the
35:55student actually knowing what's going on
35:57is
35:58it's going to be it's going to be the
35:59same so
36:01I might be better off just asking two
36:04really novel
36:04>> two smart questions rather than a whole
36:07lot of not so well designed questions
36:10absolutely absolutely.
36:12We should probably wrap up we've gone
36:13way over because we've been having fun
36:16I don't know if you had any
36:18um parting thoughts I mean my my view is
36:21you know
36:22uh
36:24Reed-Solomon codes are excellent for the
36:26job they were designed to do a long long
36:28time ago.
36:29Um
36:31they were never meant to be used in
36:32networks they were never meant to be
36:34used in blockchain and never meant to be
36:36used in a decentralized way. Um and um
36:41you know
36:42there really is a good reason for using
36:45the best tech.
36:46You know
36:47um not just because it's cool and you
36:49know you you you want to be have the the
36:52nice and shiny thing but uh
36:55it's it's a big difference between
36:58approximately 1960s technology and doing
37:01the latest and greatest but you know I'm
37:04biased I guess you're biased too but
37:06I'll let you talk to
37:07>> [laughter]
37:08>> I'll let you share your bias I've shared
37:10my bias. Yeah but actually interesting
37:12to to to to see again the the kind of
37:15line that goes through
37:17RS or like product code um
37:20embedded RS
37:22LDPC and then RLC all developed kind of
37:24at the same chair by if I remember. And
37:27I think the the thing that we really
37:29need to
37:30that I would want to stress here is the
37:33thing about problem statements right I
37:35mean we really talking about
37:38different kind of problems that each one
37:39of those codes solves in the end and
37:43RLC is mathematically optimal for
37:48the problem of recovering erasures in
37:50networks and that's why we built Mumble
37:54P2P
37:56and that's why we can also why we expect
38:00why why the performance of RLC scales so
38:02well
38:04in in the networks that that we
38:06encounter in blockchain systems.
38:09Yes so when we say we're optimum it's
38:10actually provable.
38:12Yes. How often can you say that?
38:15No
38:15I really am optimum.
38:17Well it's that was so much fun. Thank
38:19you so much
38:21and I hope all listeners enjoyed this
38:24conversation as much as we enjoyed
38:26having it and will generate
38:29conversations locally and as always
38:32please follow us on X
38:35um
38:36go to our website to see some of the
38:38latest and greatest and stay tuned for
38:41Mainnet.
38:44Thanks all right.

About this transcript

This page contains the full transcript of RLNC vs Reed-Solomon: Optimal Blockchain Data Coding Explained | MIT's Muriel Médard by Optimum, generated from the public captions YouTube serves with the video. The transcript has 5,609 words across 1,002 segments, with the original timestamps preserved so you can click any line to jump to that moment in the embedded player.

What you can do with it

Use the transcript to take notes, quote the speaker, build a study guide, generate a summary with ChatGPT or Claude via the YouTube Summary tool, or export it as a timed subtitle file with YouTube to SRT. You can also re-open it in the transcriber to translate the transcript into 100+ languages.

Free YouTube transcript tool

YouTube2Text is a free YouTube transcript generator — no signup, no daily limit. Paste any YouTube link and get the full transcript instantly, with timestamps, click-to-jump, translation to 100+ languages, AI prompts for ChatGPT, Claude, and Gemini, and exports to TXT, SRT, VTT, or Markdown.