# Add Python implementation of Minisketch, part 2 (math and cryptography)

Host: sipa  -

This week, we’ll continue our review of the Python implementation of Minisketch.

See the notes from our previous review club on Minisketch.

## Questions

1. (previously question 6) To actually find the roots, the Berlekamp Trace Algorithm is used. It uses the trace function ```t(x) = x + x^2 + x^4 + ... + x^(fieldsize/2)``` which maps every element of a field of size `2^n` to `0` or `1`. In our 8-bit field that means ```t(x) = x + x^2 + x^4 + x^8 + x^16 + x^32 + x^64 + x^128```. This means that for any non-zero field element `p`, `tr(p*x)` also has this property, and every choice of `p` will map a different subset of field elements to 0 (and the others to 1). How is this property used to recursively split the polynomial into smaller and smaller ones?

## Meeting Log

 1 18:00 #startmeeting
 2 18:00 hi folks!
 3 18:00 hi
 4 18:00 hi
 5 18:00 hi
 6 18:00 yoooo
 7 18:00 hi
 8 18:00 hi!
 9 18:00 feel free to say hi to let everyone know you're here
 10 18:00 anyone here for the first time?
 11 18:00 hi-new here-first time
 12 18:00 hi, my third review
 13 18:01 tkc: welcome!
 14 18:01 first time of 2021 ;)
 15 18:01 hi
 16 18:01 Today we'll be continuing the discussion about Minisketch from two weeks ago
 17 18:01 thanks-initial steps in learn to program the core-long road ahead. :)
 18 18:01 Notes, questions and logs from that meeting are here: https://bitcoincore.reviews/minisketch-26. We got up to question 5 last time I think.
 19 18:01 ok, over to sipa!
 20 18:02 ℹ ma is now known as Guest8267
 21 18:02 sorry, laptop troubles!
 22 18:02 be right there
 23 18:02 hi, my third review
 24 18:02 anyone know any good minisketch puns while sipa sorts out his laptop?
 25 18:03 since i warned about flakey internet, it will probably work flawlessly this time
 26 18:03 ok!
 27 18:03 I know this many miniskettch puns: x^6 + x^5 + x^4 + x^3 + x^2 + x
 28 18:04 i heard there are an infinite number of papers to write about real analysis, but today we don't need to worry about that because we're working in a finite field
 30 18:04 so
 31 18:04 when u trying to solve polynomial it can get kinda berlekamp messy
 32 18:04 everybody awake?
 33 18:05 *g*
 34 18:05 let's go over where we were
 35 18:05 minisketch helps every bitcoiner to get a GF(2)!
 36 18:06 we're working in a finite field, which is like numbers, but addition and subtraction multiplication and division are all defined in a weird way
 37 18:06 i was in the minisketchy part of town and someone made me do a set reconciliation with the bills in my wallet
 38 18:06 a+b and a-b are the same thing
 39 18:07 XOR
 40 18:07 lets all just pay attention to sipa. if you miss anything, its really easy and fast to get whatever you missed from someone else
 41 18:07 and then we define "sketches" of a set {a,b,c} as just the list {a+b+c, a^3+b^3+c^3, a^5+b^5+c^5, ...}
 42 18:07 up to its capacity
 43 18:07 welcome to the frobenius hospital, we only treat odd syndromes because the even ones can be cured by squaring the odd ones
 44 18:07 thanks glozow
 45 18:07 ok sorree i'm done now
 46 18:08 🤣
 47 18:08 today we'll let Berlekamp be our guide in tracing a euclidean ring through the galois fields, in the hope of finding some hidden roots...
 48 18:09 and in general set reconciliation works by sending such a sketch, letting the other side "add" (or subtract, same thing) from it their own sketch
 49 18:10 which results in a sketch of the symmetric difference of the two parties' sets
 50 18:11 as you can see that say Alice has {a,b} and Carol has {b,c}, the sketches are {a+b,a^3+b^3,...} and {b+c,b^3+c^3,...} and pairwise adding those gives you {a+c,a^3+c^3,...}, the sketch of {a,c}
 51 18:11 makes sense?
 52 18:12 👍
 53 18:12 very cool yes
 54 18:12 now, the hard part is... given this {a+c,a^3+c^3,...} sketch, find {a,c} again
 55 18:13 so (a+b) + (b+c) = a+2b+c = a+c ?
 56 18:13 larryruane_ yes bc + and - cancel out like XOR!
 57 18:13 we've already used the Berlekamp-Massey algorithm to turn this sequence into a polynomial that generates the sequence, which in our case would be (1+ax)*(1+cx)
 58 18:13 er I shoudl say +b and +b cancel out
 59 18:13 larryruane_: yes, characteristic 2 field, so a+a = 0
 60 18:14 but of course we don't get the polynomial in that form, we get just the coefficients of it: [1, a+c, ac]
 61 18:15 and if we had more terms, it'd be even more complex
 62 18:16 for 3 terms it'd be [1, a+b+c, ab+bc+ac, abc] etc
 63 18:16 Berlekamp-Massey turns this: {a+c,a^3+c^3,...} into this: (1+ax)*(1+cx) ?
 64 18:16 indeed
 65 18:16 and it does so regardless of how big your sketch was
 66 18:17 that polynomial defines the pattern underlying the infinite sequence of {a+c,a^3+c^3,a^5+c^5,a^7+c^7,...}
 67 18:18 so we work in the "sketch" form because there it's easy to use the cancelling-out property
 68 18:18 and that's what we send
 69 18:18 but we then use BM to discover the pattern behind it, and that pattern (the polynomial) helps us find what the actual input terms are
 70 18:19 (1+ax)*(1+cx) = 1 + cx + ax + ac(x^2) ?
 71 18:19 there is a bit deeper explanation here: https://github.com/sipa/minisketch/blob/master/doc/math.md
 72 18:19 yes, 1 + (a+c)x + (ac)x^2, so BM finds the coefficients [1,a+c,ac]
 73 18:19 what are our next steps?
 74 18:19 oh right (a+c)x
 75 18:20 assuming we actually want to find a and c
 76 18:20 factor it
 77 18:20 yeah, of course
 78 18:20 check that it has n roots and can be completely factored
 79 18:21 indeed, that too
 80 18:21 we could use a fully-fledged factoring algorithm like cantor-zassenhaus, but we don't actually care about factoring it
 81 18:21 we want to find its roots
 82 18:21 which is the same as saying: factoring into 1st degree factors
 83 18:22 but if the polynomial somehow can't be factored fully into 1st degree factors, or those factors aren't all unique, we don't really care at all
 84 18:22 because it can't be fully decoded
 85 18:22 all or nothing
 86 18:23 right, we know that if that polynomial is the result of BM on a sketch of sufficient size, it will be factorizable into distinct 1st degree factors
 87 18:23 and so we can actually use a significantly simpler algorithm that just finds the roots, and we can even use one that only works if all roots are distinct
 88 18:24 but we do need to check ahead of time that this is the case, as the algorithm we'll use would run into an infinite loop or otherwise behave incorrectly if it isn't
 89 18:24 how did we do that?
 90 18:24 we briefly discussed it last time
 91 18:24 if we find that the polynomial isn't factorizable, can we deduce that the sketch size was too small? or could that have other causes as well?
 92 18:24 sipa: under what circumstances would BM give you a polynomial with duplicate roots that live in the field?
 93 18:25 lightlike: yeah, it must mean that
 94 18:25 use `poly_frobeniusmod` - compute x^{2^b} mod poly, which should be exactly x if it has unique roots
 95 18:26 I was able to generate a sketch(8,4) that decodes 5 numbers. whats the origin of this?
 96 18:26 sdaftuar: if the list (sketch) appears to have a polynomial with repeated roots as shortest LFSR that generates it
 97 18:27 i believe that e.g. [1,0,1,0,1,0,1,0,...] has (x^2 + 1) as LFSR
 98 18:27 which has double root 1
 99 18:27 thanks, will ponder
 100 18:27 given that we start from a set where every element can only occur once, that must mean our sketch was just too small
 101 18:28 glozow: indeed, why?
 102 18:29 sipa guess: some element wrapped around the modulus? and repeated some lower element?
 103 18:29 in an order q galois field, x^q - x always has every field element as roots, so if the polynonmial does too, then x^q = x mod poly
 104 18:29 right, or in other words: we want to know if poly is a divisor of x^q - x
 105 18:30 and if that's the case, (x^q - x) mod poly = 0
 106 18:30 and if poly has degree > 1, that's the same as x^q mod poly = x
 107 18:30 because (x^q - x) = x*(x+1)*(x+2)*(x+3)*...*(x+(q-1))
 108 18:30 (i.e. it's the product of all possible 1st degree factors, and thus has every element of the field exactly once as root)
 109 18:31 ok, moving on!
 110 18:31 yeet
 111 18:31 actually finding the root
 112 18:31 s
 113 18:31 again: we're really trying to find 1st degree factors of our polynomial, but we *know* ahead of time that it factors completely, without any duplicates
 114 18:32 do we do this check only as an optimization to save time, or because the root finding algorithm could run indefinitely?
 115 18:32 both?
 116 18:32 lightlike: done naively, it could run indefinitely
 117 18:32 ok
 118 18:32 what's the trace function?
 119 18:32 (because it's the Berlekamp Trace algorithm, there must be a trace, right?)
 120 18:34 tr(x) = x + x^2 + x^4 + x^8 + ... + x^(q/2)
 121 18:34 is the trace function for our field, w.r.t. GF(2)
 122 18:34 in general, a trace function is a function that maps elements of some bigger structure to a smaller one
 123 18:34 I'm not 100% clear on this. So the Trace function gives us a GF(2)-linear map from the polynomials to GF(2)?
 124 18:35 it maps every GF(2^b) element to a GF(2) element, in our case
 125 18:35 and more precisely, it maps exactly half of them to 0 and the other half to 1
 126 18:35 right, it'd have to
 127 18:35 you can see that this is the case by computing what tr(x) * (1 + tr(x)) is
 128 18:37 this also means that for any field element a (not 0), tr(a*x) also has this property
 129 18:37 it maps half of the elements to 0, and the other half to 1... but which half that is depends on a
 130 18:38 so we start by picking a random a, and trying to separate the roots from poly(x) into the ones for which tr(a*x)=0 and the ones for which tr(a*x)=1
 131 18:38 and then do that recursively with different a values, until everything is split into 1st degree factors
 132 18:39 what do you know about poly(x) mod tr(a*x) ?
 133 18:39 wait sorry, so the Trace function is defined on GF(2^b), how do we apply it to the polynomial itself?
 134 18:39 we'll get there
 135 18:40 tr(a*x) is a polynomial in x
 136 18:40 if you think about it symbolically
 137 18:40 it's a*x + (a^2)*x^2 + (a^4)*x^4 + ...
 138 18:41 right?
 139 18:41 right, mhm
 140 18:41 now: think about what a modulus means:
 141 18:41 if r(x) = poly(x) mod tr(x), that means that r(x) equals poly(x) + somefunction(x)*tr(x)
 142 18:42 in the same way that 19 mod 8 = 3 means that 3 = 19 + (some number)*8
 143 18:42 (where some number here specifically is -2)
 144 18:42 for polynomial modulus it's the same, except it's now some unknown polynomial
 145 18:43 plz ask questions if things aren't clear :)
 146 18:43 is that polynomial = gcd(poly, trace)?
 147 18:43 no no, no gcd yet
 148 18:43 just a simple modulus
 149 18:43 this is the definition of a modulus
 150 18:44 okok ye
 151 18:44 or even the definition of division as you learned it in high school probably: when computing a/b, you find a-q*b=r
 152 18:44 quotient and residue
 153 18:45 the modulus operation is finding the residue and ignoring the quotient
 154 18:45 ye
 155 18:45 so!
 156 18:45 if r(x) = poly(x) mod tr(x), that must mean that r(x) = poly(x) + quotient(x)*tr(x)
 157 18:46 but we know tr(x) is 0 for half of the field
 158 18:46 (now thinking about concrete x values)
 159 18:46 this means that r(x) must have all roots that poly(x) has which coincide with roots of tr(x) (and that's half the field)
 160 18:47 because evaluating r(x) = poly(x) + quotient(x)*tr(x) in such an x just gives r(x) = 0 + quotient(x)*0
 161 18:47 r(x)'s roots = shared roots of poly(x) and tr(x)
 162 18:47 ?
 163 18:47 it must have _at least_ those roots
 164 18:47 it can have others
 165 18:48 mm okay
 166 18:48 but to weed those out, you use a gcd
 167 18:48 the (polynomial) gcd of r(x) and poly(x) gives you something which exactly has the shared roots of poly(x) and tr(x)
 168 18:49 gcd for polynomials = literally a way to computing the polynomial consisting of all shared factors
 169 18:49 if tr(x) is 0, how do we know that poly(x) is 0?
 170 18:49 amiti: we don't, we're trying to find that
 171 18:50 oh, I see
 172 18:50 it's just the case that for all values v for which tr(v)=0, we know that poly(x) mod tr(x), evaluated in v, also gives 0
 173 18:51 if v is a root of poly(x)
 174 18:51 and thus poly(x) mod tr(x) must be a polynomial with v as root if it's a root of both tr(x) and poly(x)
 175 18:51 what does tr(x) mean?
 176 18:51 trace function evaluated on x
 177 18:51 09:34:02 < sipa> tr(x) = x + x^2 + x^4 + x^8 + ... + x^(q/2)
 178 18:52 we don't know anything about the other roots of (poly(x) mod tr(x)), though
 179 18:52 but after doing a gcd with poly(x), you get a polynomial with exactly the shared roots of poly(x) and tr(x)
 180 18:52 gcd?
 181 18:52 greatest common divisor
 182 18:53 is it greatest common denominator?
 183 18:53 no
 184 18:54 we're not working with numbers but with polynomials
 185 18:54 divisor is generic
 186 18:54 i am? ;P
 187 18:54 hahaha
 188 18:54
 189 18:55 so: we're almost done!
 190 18:55 we have f1(x) = gcd(r(x),poly(x)), which is the polynomial with all shared roots of poly(x) and tr(x)
 191 18:55 and f2(x) = poly(x) / f1(x), which has all the other roots
 192 18:55 f1,f2 are a factorization of poly
 193 18:56 f1 has all the roots for which tr(x)=0, f2 has all the roots for which tr(x)=1
 194 18:57 so then you can repeat the process, but with a different a (i've been writing tr(x) everywhere, but i really meant tr(a*x))
 195 18:57 to split f1 and f2 up further
 196 18:57 until you hit 1st degree polynomials, and if you have a 1st degree polynomial (x+m), its root is kind of obvious
 197 18:58 ok, question! what would happen if there was a duplicate root?
 198 18:58 and you'd naively do this?
 199 18:59 you'd never hit the 1st degree polynomial, but you'd keep repeating the process tryna get there?
 200 18:59 you wouldn't end up with linear factors?
 201 18:59 yeah, say you have x^2+1, which has duplicate root 1
 202 18:59 if tr(a*1)=0, you'd always get f1(x)=x^2+1 and f2(x)=1
 203 19:00 if tr(a*1)=1, you'd always get f1(x)=1 and f2(x)=x^2+1
 204 19:00 so both factors would always land on the same side of the split
 205 19:00 since you use a special lookup for quadratics anyway, this would only be an issue if you had a triple (or more) root -- is that right?
 206 19:00 indeed
 207 19:00 why doesn't the loop halt after trying 2^field_size times? would that do anything?
 208 19:00 glozow: ah!
 209 19:01 well, if you pick the a values randomly, you can't ever stop
 210 19:01 it turns out, you can do much better than picking them randomly
 211 19:01 is this the randv = gf.mul2(randv) line?
 212 19:01 yeah
 213 19:01 if you pick (a, 2a, 4a, 8a, 16a, ..., {q/2}a), you'll always find every root
 214 19:02 set {2^i*a for i=0..fieldsize-1}
 215 19:02 which just needs b (=log2(q)) steps
 216 19:02 and you could indeed just stop after recursing b times
 217 19:02 and if you do that, the frobenius check at the start just becomes an optimization
 218 19:03 those a values are optimally orthogonal in a way
 219 19:03 i discovered that, and was very proud of it, because i couldn't find any implementations of BTA that used this
 220 19:03 until i learned that it's actually mentioned in berlekamp's 1967 paper that introduced the algorithm
 221 19:04 =P
 222 19:04 ⚡ sdaftuar is still impressed
 223 19:05 another optimization we have: if you've computed tr(a*x) mod poly(x), you can compute x^q mod poly(x) from that too
 224 19:06 if r(x) = tr(a*x) mod poly(x), then r(x)*(r(x)+1) = (a*x)^q i believe (or (a*x)^q + (a*x), something like that
 225 19:07 and in the C++ code we use that to do the frobenius check simultaneously with the first recursion level of the factoring algorithm
 226 19:08 sdaftuar: and yeah, with the explicit formula for 2nd degree polynomials, duplicate roots specifically is not a problem (we'd detect them when trying to solve the 2nd factor)
 227 19:09 but you could have irreducible 3rd degree polynomials too, for example
 228 19:09 it's not just duplicate roots that form a problem
 229 19:09 right, makes sense
 230 19:09 ⚡ jonatack clapping 👏
 231 19:09
 232 19:10 that explains how to do the frobenius check simultaneously with splitting
 233 19:10 randv there is what i've called a here
 234 19:11 whats randv stand for?
 235 19:11 random value
 236 19:11 :)
 237 19:11 ok
 238 19:11 what is BCH?
 239 19:12 eoin: Bose–Chaudhuri–Hocquenghem
 240 19:12
 241 19:12 probably good to add this link to the log too: https://en.wikipedia.org/wiki/GF%282%29
 242 19:13 oh, i guess one last thing: we started from the polynomial (1+ax)(1+cx), and found its roots 1/a and 1/c
 243 19:13 but we want a and c
 244 19:13 a very simple trick helps with that: reverse the coefficients of polynomials before trying to find the roots
 245 19:14 roots of (a*x^3 + b*x^2 + c*x + d) = inverses of roots of (d*x^3 + c*x^2 + b*x + a)
 246 19:14 woah nice
 247 19:14 there also exists something called a batch inverse, where with 1 inverse + 3*n multiplications you can find the inverses of n elements at once
 248 19:14 but we don't even need it here
 249 19:15 inverses are many times more expensive than multiplications, fwiw
 250 19:15 so... any questions? :)
 251 19:15 sipa: trick used here? roots = poly_find_roots(list(reversed(poly)), self._gf)
 252 19:15 jonatack: yes
 253 19:16 wait why is the roots of reversed = inverses of roots?
 254 19:16 aha!
 255 19:16 ok
 256 19:16 substitute y = 1/x
 257 19:17 so you start with a*x^3 + b*x^2 + c*x + d
 258 19:17 and get a*y^-3 + b*y^-2 + c*y^-1 + d
 259 19:17 now multiply everything with y^3
 260 19:17 ohhhhhhhh
 261 19:17 and you get a + b*y + c*y^2 + d*y^3
 262 19:17 and doing so doesn't change the roots
 263 19:18 nice
 264 19:19 this is true in general for polynomials?
 265 19:19 yes
 266 19:19 why didn't they teach this in school
 267 19:19 jeez
 268 19:19 haha
 269 19:20 what if 0 is one of the roots?
 270 19:20 no constant term?
 271 19:20 indeed
 272 19:20 probably shouldn't do that trick til you factor it out
 273 19:20 it still works actually
 274 19:20 but you get a polynomial of degree one less
 275 19:21 which excludes the infinity root
 276 19:21 thankfully, not a problem for us, because we know all our roots are nonzero
 277 19:21 oh, question: why did we need the property that we encode our set elements as nonzero field elements?
 278 19:21
 279 19:22 so in the C++ code: std::reverse(poly.begin(), poly.end());
 280 19:22 jonatack: indeed
 281 19:24 if they're zero,
 282 19:24 what would the sketches be for sets {a} and {a,0} ?
 283 19:24 they'd be the same :O
 284 19:24 same
 285 19:24 exactly
 286 19:25 adding 0 is a NOP
 287 19:25 and it's kind of related to this inversion at the end: in the BM representation, the elements become inverses of the roots
 288 19:25 but 0 can't be the inverse of a root
 289 19:26 it'd be possible to just add 1 bit to every sketch to indicate "contains 0", and xor that along with everything else
 290 19:26 but just avoiding 0 is easier
 291 19:26 sipa: so are you saying it's impossible for BM to spit out a polynomial with 0 as a root? or just that it means the sketch obviously won't decode?
 292 19:26 the sketches would still work, but you wouldn't be able to reconcile an element represented as 0?
 293 19:27 sdaftuar: i believe that's the case yes, BM
 294 19:27 iirc BM will always produce a polynomial with constant term 1
 295 19:28 not entirely sure, but even if not, it can't even have a constant term 0
 296 19:28 because then by definition it's not a minimal LFSR
 297 19:28 ah
 298 19:29
 299 19:29 is that everything for today sipa? :)
 300 19:30 seems like a good place to end :)
 301 19:30 #endmeeting

…/…

 302 19:37 minisketch started as an attempt to get an implementation of NTL's algorithms needed for erlay that wasn't GPL
 303 19:37 NTL is sort of the library people use for low-level finite field arithmetic stuff
 304 19:38 (and it was used by the authors of the PinSketch paper for their implementation)
 305 19:38 so i learned most of this just from reading the NTL source code...
 306 19:38 you can't find much about BTA online
 307 19:39 the standard algorithm for factoring polynomials over finite fields is https://en.wikipedia.org/wiki/Cantor%E2%80%93Zassenhaus_algorithm but as described there, it doesn't work for GF(2^b) fields