What is Erasure Coding? Blockchain Data Protection Explained | RLNC vs Reed-Solomon — Transcript

Full transcript

1. 0:01Hi everybody. Uh I'm Yuriel Medard, uh
2. 0:04co-founder of Optimum and I'm here to
3. 0:07tell you a little bit about coding
4. 0:08today. Uh this is a small piece to go
5. 0:11along with our uh little research paper
6. 0:14uh with Nicholas and Kishori. Uh Kishor
7. 0:18is one of my co-founders. Um so this is
8. 0:21just a very brief introduction to uh
9. 0:24erasia correcting code. So let's look at
10. 0:26what erasers are. are so welcome by the
11. 0:29way to my messy board. You can see I've
12. 0:30made a little bit of space here uh so
13. 0:33that we can uh uh we can chat together.
14. 0:37So um coding is about sending data and
15. 0:40imagine I have
16. 0:43three pieces of data here x1 x2 x3 and
17. 0:47I'm transmitting all three. Problem is
18. 0:50one of them might get lost. Uh so
19. 0:53suppose for the time being that x2 gets
20. 0:55lost. So we get x1 and x3 but you know
21. 0:58we can't make sense of the actual data
22. 1:01because there's a missing piece. Okay
23. 1:04you might say well you know I have a
24. 1:05problem because x2 gets lost. Uh what
25. 1:08I'll do is uh any which piece of data
26. 1:12gets lost um when the receiver tells me
27. 1:15that they didn't get it I shall resend
28. 1:18it. That's fine but there's a delay
29. 1:20there. The data has to get to someplace.
30. 1:22is the place has to realize that the
31. 1:24data didn't get there, then it has to
32. 1:26request the data didn't get there.
33. 1:28There's a lot of delay, you might want
34. 1:30to be proactive and add what's called
35. 1:32redundancy. I like to call it repair.
36. 1:35And instead of doing that, you might
37. 1:37say, well, look, if I'm worried that X2
38. 1:38might get lost, why don't I send two
39. 1:40copies of X2?
40. 1:42So, if one copy of X2 gets lost, no
41. 1:45problem. You get X1, X3, X2. You just
42. 1:47need to reorder them at the receiver.
43. 1:50Uh, what happens though if this time
44. 1:52instead X3 gets lost? Well, we have a
45. 1:56problem there because we have two copies
46. 1:58of X2. That doesn't do me any good. I'm
47. 2:00still missing X3. So, I have X1 and X2,
48. 2:02but X3 is missing. In order to remedy
49. 2:06this, what people will do is the
50. 2:08following.
51. 2:09They will create a code. That's to say,
52. 2:11they will take an equation, generally a
53. 2:14linear equation, maybe x1 + x2 + x3.
54. 2:20So let's look at what happens here. If
55. 2:22any one of these goes missing, I can
56. 2:25still reconstruct the original x2, x1,
57. 2:28and x3. So if x1 gets missing, I have
58. 2:32x2, x3, and thanks to this last
59. 2:34equation, I'm able by subtracting x2 and
60. 2:37x3 to recover X1. So this is eraser
61. 2:42coding. It basically makes up correct
62. 2:45for erasers.
63. 2:48All right, so far so good. So there's
64. 2:51this different types of eraser that you
65. 2:54can coding that you can do. So let's
66. 2:56look at traditional block codes or fixed
67. 2:59rate codes like read solvent that many
68. 3:01of you may have heard of because they're
69. 3:03used for instance for hash functions um
70. 3:05in data availability in web 3. So um
71. 3:10what does it mean to have a rate? Well,
72. 3:12let's see here. I have three units of
73. 3:15data and one unit of repair. So my
74. 3:20overall rate is three units of payload
75. 3:22over four units of transmission. So my
76. 3:26overall rate is 3 over4. That's my rate.
77. 3:29So this is a code with a fixed rate.
78. 3:32Now um whenever I don't get a loss, I've
79. 3:36basically paid for this extra
80. 3:41effectively insuranceed and not gotten
81. 3:43any benefit of it. And if instead I have
82. 3:45two losses, then actually I still can't
83. 3:47recover all of the data. So I only have
84. 3:51made that my code is either sufficient
85. 3:54so not too many losses or not wasteful a
86. 3:59number of losses that's below the level
87. 4:01of repair um every so often really. So
88. 4:06most you know most of the time this is
89. 4:08going to be wasteful and some portion of
90. 4:10the time it's not going to be
91. 4:11sufficient.
92. 4:12So this is a code with a fixed rate.
93. 4:16In order to remedy this, uh, they have
94. 4:19been rateless codes. So in weightless
95. 4:21codes, I don't decide ahead of time that
96. 4:24I'm going to send equations. I'm just
97. 4:26going to keep sending equations as many
98. 4:29as needed until uh I know that all of
99. 4:32the data has gotten there. Now, of
100. 4:34course, if I did that on a single unit
101. 4:36at a time, it gets back to the case we
102. 4:38bu we discussed before where, you know,
103. 4:41I have to transmit, wait to see if it
104. 4:44got there or not, then retransmit.
105. 4:46Instead, if people are looking at
106. 4:49transmission for a chunk of data, say
107. 4:52here are these three numbers, then what
108. 4:54they'll do is they'll just keep sending
109. 4:55equations as many as needed until the
110. 4:58receiver says, hey, you know, I got all
111. 5:00of the data I need. um those are called
112. 5:03weightless codes. So examples of
113. 5:05readless codes are raptor codes.
114. 5:10All right. So we have two kinds of
115. 5:12codes. Now what's the problem with these
116. 5:16codes? You know they look like both a
117. 5:18good idea
118. 5:20and they are good ideas. The problem is
119. 5:23that you basically need all of the
120. 5:25original data to start out to make the
121. 5:29code. So the code is sort of like a
122. 5:31one-time only used code. You make the
123. 5:34code once and you use it for that one
124. 5:37event.
125. 5:38Uh this is not suitable for web 3 where
126. 5:42things need to be decentralized.
127. 5:45In particular,
128. 5:47traditional codes that are either block
129. 5:50codes or weightless codes have a
130. 5:53particular way of creating these
131. 5:56equations. So they have particular
132. 5:59coefficients for creating these
133. 6:00equations. Now what happens if instead
134. 6:05I allow more general coefficients? So
135. 6:08maybe I'm going to have alpha 1 x1
136. 6:12plus beta
137. 6:161 x2
138. 6:19plus gamma 1 x3 be my first equation.
139. 6:24Maybe my next equation is alpha 2 x1
140. 6:29plus beta
141. 6:322 x2
142. 6:35plus gamma 2
143. 6:39x3 and then I'll have alpha 3 beta 3
144. 6:43gamma 3 and so on and so forth. Okay. um
145. 6:47if I allow these equations to happen
146. 6:51over a set of numbers generally called a
147. 6:54field that's rich enough I actually have
148. 6:56a lot of possible chases for these alpha
149. 6:58beta gamas and in particular I don't
150. 7:02need to predetermine them read Solomon
151. 7:05codes or um codes like uh you know or uh
152. 7:09traditional rateless codes like raptor
153. 7:11codes predetermine what these alphas
154. 7:13betas and gamas are going to
155. 7:16uh but in general I don't need to. I can
156. 7:18make them however I want. In particular,
157. 7:19I can make them randomly as long as I
158. 7:22choose them over a rich enough set of uh
159. 7:26uh of choices. Uh so basically this is
160. 7:30what a random linear network code is.
161. 7:34You can choose to use it as a block
162. 7:36code. So for instance here I could do
163. 7:38three
164. 7:39data pieces and two equations for a rate
165. 7:43three fifths if I wanted to or I can
166. 7:47choose to do this in a rateless fashion
167. 7:49and just keep generating equations until
168. 7:52enough equations have been received.
169. 7:54It's really up to me. Now one of the
170. 7:57things that's very um interesting about
171. 7:59RLNC is that I can actually create
172. 8:02equations from equations. So here I
173. 8:05created those equations from the
174. 8:07original data. But what if I did not
175. 8:09have access to the original data and I
176. 8:11had only access to these two equations.
177. 8:14Well, I can actually combine these two
178. 8:16equations. Okay? And let me combine them
179. 8:18using here
180. 8:21delta 1 delta 2. So I'm going to take
181. 8:24these two equations. I'm going to take
182. 8:26delta 1 times this expression. Delta 2
183. 8:30times this expression. So I get delta 1
184. 8:33alpha 1
185. 8:36plus delta 2 alpha 2 x1
186. 8:45plus
187. 8:47delta 1 beta 1 + delta 2 beta 2 x2 plus
188. 8:58delta 1 gamma 1 plus delta 2 gamma 2 x3.
189. 9:07So basically what I've managed to do
190. 9:09here is I've made an expression directly
191. 9:13out of other expressions without having
192. 9:15access to the original data. So why is
193. 9:19this important? Why is this interesting?
194. 9:22Well, now throughout the network, I can
195. 9:25generate
196. 9:27new expressions, new codes from any
197. 9:32piece of code, and I don't need to go
198. 9:34back to the original
199. 9:36uh to the original data. So, if you look
200. 9:39at this
201. 9:42expression here, delta 1 alpha 1 plus
202. 9:46delta 2 alpha 2, that's basically just a
203. 9:49new alpha. that is the coefficient that
204. 9:52is mapped to x1. So that's basically how
205. 9:56RNC works. So if you think of read
206. 9:59Solomon, if you think of traditional
207. 10:03uh weightless codes like Rapto code, all
208. 10:07they are is effectively a constrained
209. 10:11not general version of our an RLNC. So
210. 10:14the RLNC is inherently
211. 10:17more general and more powerful. I look
212. 10:21forward to receiving questions on this.
213. 10:23Thanks.