--- Day changed Wed Apr 21 2021 00:08 -!- S3RK_ is now known as S3RK 00:35 -!- andrewtoth_ [~andrewtot@gateway/tor-sasl/andrewtoth] has joined #bitcoin-core-pr-reviews 00:37 -!- _andrewtoth_ [~andrewtot@gateway/tor-sasl/andrewtoth] has quit [Ping timeout: 240 seconds] 01:09 -!- musdom [~Thunderbi@202.184.3.8] has quit [Ping timeout: 268 seconds] 03:19 -!- jadi [~jadi@5.201.253.183] has quit [Remote host closed the connection] 03:20 -!- Akeem68Prosacco [~Akeem68Pr@static.57.1.216.95.clients.your-server.de] has joined #bitcoin-core-pr-reviews 03:38 -!- jadi [~jadi@5.201.253.183] has joined #bitcoin-core-pr-reviews 03:38 -!- biteskola [~biteskola@170.76.76.188.dynamic.jazztel.es] has joined #bitcoin-core-pr-reviews 04:02 -!- Akeem68Prosacco [~Akeem68Pr@static.57.1.216.95.clients.your-server.de] has quit [Ping timeout: 240 seconds] 04:40 -!- mol [~mol@unaffiliated/molly] has joined #bitcoin-core-pr-reviews 04:54 -!- biteskola [~biteskola@170.76.76.188.dynamic.jazztel.es] has quit [Ping timeout: 252 seconds] 06:39 -!- promag [~promag@188.250.84.129] has joined #bitcoin-core-pr-reviews 06:50 -!- evanlinjin [~evanlinji@218-35-179-62.cm.dynamic.apol.com.tw] has joined #bitcoin-core-pr-reviews 07:24 < jonatack> to anyone thinking of running ./test-exhaust.cpp in minisketch, it takes a while to run β˜• 07:36 -!- OP_NOP [OP_NOP@gateway/vpn/privateinternetaccess/opnop/x-41418994] has joined #bitcoin-core-pr-reviews 07:48 < jonatack> otoh, after building minisketch pr 33, ./test runs in 12 seconds: "Running libminisketch tests with complexity=4" 07:50 < jonatack> by "a while" wrt to the tests on master, after a couple of hours it was at "bits=29 count=1 below_bound=[1,536870911] above_bound=[] nodecode=[0]" when i stopped running it 07:59 -!- murchin [04355c72@4.53.92.114] has joined #bitcoin-core-pr-reviews 08:04 < jonatack> ah, in pr 33: "make tests not run forever (but controlled by command-line complexity argument)" 08:32 -!- OP_NOP [OP_NOP@gateway/vpn/privateinternetaccess/opnop/x-41418994] has quit [Ping timeout: 246 seconds] 08:33 -!- shesek [~shesek@unaffiliated/shesek] has quit [Remote host closed the connection] 08:33 -!- shesek [~shesek@164.90.217.137] has joined #bitcoin-core-pr-reviews 08:33 -!- shesek [~shesek@164.90.217.137] has quit [Changing host] 08:33 -!- shesek [~shesek@unaffiliated/shesek] has joined #bitcoin-core-pr-reviews 08:59 -!- jadi [~jadi@5.201.253.183] has quit [Remote host closed the connection] 09:04 < glozow> ping? 09:04 < pinheadmz> pong! ? 09:04 < pinheadmz> (55 min to go) 09:04 -!- biteskola [~biteskola@170.76.76.188.dynamic.jazztel.es] has joined #bitcoin-core-pr-reviews 09:05 < glozow> whew! had some internet troubles, wanted to make sure i could connect haha 09:05 < glozow> thanks pinheadmz 09:05 -!- manholo [bc4c4caa@170.76.76.188.dynamic.jazztel.es] has joined #bitcoin-core-pr-reviews 09:06 -!- biteskola [~biteskola@170.76.76.188.dynamic.jazztel.es] has quit [Read error: Connection reset by peer] 09:06 -!- biteskola [~biteskola@170.76.76.188.dynamic.jazztel.es] has joined #bitcoin-core-pr-reviews 09:07 -!- manholo [bc4c4caa@170.76.76.188.dynamic.jazztel.es] has quit [Client Quit] 09:24 -!- n7hacker_ [sid489839@gateway/web/irccloud.com/x-zwmvjjajxnaoamjy] has joined #bitcoin-core-pr-reviews 09:30 -!- jadi [~jadi@5.201.253.183] has joined #bitcoin-core-pr-reviews 09:31 -!- jadi [~jadi@5.201.253.183] has quit [Remote host closed the connection] 09:33 -!- evanlinjin [~evanlinji@218-35-179-62.cm.dynamic.apol.com.tw] has quit [Quit: Konversation terminated!] 09:35 -!- CubicEarth [~CubicEart@c-67-168-1-172.hsd1.wa.comcast.net] has quit [Ping timeout: 240 seconds] 09:35 -!- N3WB33 [4cdd98b9@76-221-152-185.lightspeed.clmboh.sbcglobal.net] has joined #bitcoin-core-pr-reviews 09:37 -!- CubicEarth [~CubicEart@c-67-168-1-172.hsd1.wa.comcast.net] has joined #bitcoin-core-pr-reviews 09:42 -!- lightlike [~lightlike@p200300c7ef13f900c0bd9cb5668835d9.dip0.t-ipconnect.de] has joined #bitcoin-core-pr-reviews 09:45 -!- Hernan [~Hernan@OL121-235.fibertel.com.ar] has joined #bitcoin-core-pr-reviews 09:45 -!- Hernan is now known as Guest54387 09:47 -!- wiscojabroni [5d2c50a9@93-44-80-169.ip96.fastwebnet.it] has joined #bitcoin-core-pr-reviews 09:48 -!- Guest54387 is now known as hernanmarino 09:53 -!- dictation [~dictation@195.181.160.175.adsl.inet-telecom.org] has joined #bitcoin-core-pr-reviews 09:54 -!- dkf [58a6b2e4@88.166.178.228] has joined #bitcoin-core-pr-reviews 09:56 -!- sipa [~pw@gateway/tor-sasl/sipa1024] has joined #bitcoin-core-pr-reviews 09:58 -!- svav [5245568f@82-69-86-143.dsl.in-addr.zen.co.uk] has joined #bitcoin-core-pr-reviews 09:59 -!- svav [5245568f@82-69-86-143.dsl.in-addr.zen.co.uk] has quit [Client Quit] 10:00 <@jnewbery> #startmeeting 10:00 < jeremyrubin> hi 10:00 <@jnewbery> hi folks! Welcome to Bitcoin Core PR Review Club. A club about review Bitcoin Core PRs. 10:00 -!- svav [5245568f@82-69-86-143.dsl.in-addr.zen.co.uk] has joined #bitcoin-core-pr-reviews 10:00 -!- pglazman [~pglazman@c-73-71-224-94.hsd1.ca.comcast.net] has joined #bitcoin-core-pr-reviews 10:00 <@jnewbery> *reviewing 10:00 < schmidty> gi 10:00 < gleb> hi 10:00 < glozow> hi 10:00 <@jnewbery> feel free to say hi to let everyone know you're here 10:00 < lightlike> hi 10:00 < pglazman> hi 10:00 < svav> hi 10:00 < michaelfolkson> hi 10:00 < emzy> hi 10:00 -!- jesseposner [~jesseposn@2601:645:200:162f:1de9:895b:e660:35bb] has joined #bitcoin-core-pr-reviews 10:01 <@jnewbery> anyone here for the first time? 10:01 -!- cls [26460be2@38.70.11.226] has joined #bitcoin-core-pr-reviews 10:01 -!- larryruane_ [uid473749@gateway/web/irccloud.com/x-elisawrkhzqhccwc] has joined #bitcoin-core-pr-reviews 10:01 < wiscojabroni> yes me! 10:01 -!- dulcedu [ac5ca63e@172.92.166.62] has joined #bitcoin-core-pr-reviews 10:01 -!- jadi [~jadi@5.201.253.183] has joined #bitcoin-core-pr-reviews 10:01 <@jnewbery> welcome wiscojabroni! 10:01 -!- ssd [~ssd@2804:29b8:50a4:6fbd:48cb:3566:8852:3358] has joined #bitcoin-core-pr-reviews 10:02 < wiscojabroni> thank you! 10:02 < dictation> hi 10:02 < larryruane_> hi everyone 10:02 < sipa> hi everyone and welcome 10:02 < ssd> hi 10:02 <@jnewbery> just a couple of reminders: the host is here to guide the discussion with some prepared questions (here https://bitcoincore.reviews/minisketch), but feel free to ask questions at any time 10:03 <@jnewbery> no need to ask if you can ask. Just ask away! We're all here to learn 10:03 <@jnewbery> ok, over to sipa 10:03 < andrewtoth_> hi 10:03 < sipa> hi everyone 10:03 < murchin> hey 10:03 < hernanmarino> hi ! First timer here 10:03 < murchin> Hi Hernan :) 10:03 < sipa> this is a bit of an unusual review club too, as we're nkt reviewing a PR 10:04 <@jnewbery> welcome hernanmarino! 10:04 < sipa> but an enture project/repository 10:04 < dulcedu> hola! 10:04 < hernanmarino> thanks 10:04 < sipa> that means we're obviously not going as deep 10:05 < sipa> and i've tried to make the questions/summary primarily about code organization 10:05 < svav> Is the main purpose of libminisketch being used in Bitcoin Core to provide efficiency gains to the relay protocol Erlay? 10:05 < sipa> svav: indeed 10:05 -!- Talkless [~Talkless@mail.dargis.net] has joined #bitcoin-core-pr-reviews 10:05 < sipa> that's the only reason (for now) why we'd want it in bitcoin core 10:06 < jeremyrubin> sipa: not sure if covered before or if you want the focus to be on the algo, but maybe you could set up the general problem we're trying to solve for 10:06 <@jnewbery> jeremyrubin: https://bitcoincore.reviews/minisketch-26 10:06 < sipa> jeremyrubin: we already did two review clubs on the algo 10:06 < svav> When you refer to "fields", how many fields is this, and are these just the common fields of a Bitcoin transaction? 10:06 -!- Gambo [bba25c19@187-162-92-25.static.axtel.net] has joined #bitcoin-core-pr-reviews 10:06 < sipa> svav: they refer to mathematical fields 10:07 -!- figs [ced9cd57@206.217.205.87] has joined #bitcoin-core-pr-reviews 10:07 <@jnewbery> We've gone over the high level concepts in a couple of previous review club sessions. I think it makes sense to focus on the c++ implementation here 10:07 < jeremyrubin> gotcha; will look at earlier notes! 10:07 < sipa> search for galois field on wikipedia, or read the transceipts of tbe previous review clubs 10:07 < jonatack> hi 10:07 < Gambo> hello! 10:08 < sipa> also i apologize for my slow and slightly erratic typing; i:m currently unable to do this from anywhere my phone 10:08 -!- jadi [~jadi@5.201.253.183] has quit [Ping timeout: 246 seconds] 10:08 < sipa> so let's dive in with the first question 10:08 < sipa> Why is there a separate instantiation of the PinSketch algorithm for every field? 10:08 < dictation> Why is there a separate instantiation of the PinSketch algorithm for every field? 10:09 < sipa> and again, this refers to the specific galois fields used in the algorithm 10:09 < larryruane_> is this a classic space-time tradeoff? Separate instatiations means the compiler can optimize better? 10:09 < glozow> I thought (1) composability and (2) performance 10:09 < sipa> erlay specifically only uses the 32-bit field 10:09 < glozow> The fields have been chosen so that some sketch algorithms work for all of our fields. However, some operations are optimized per field so that you can just say like `field.`multiply these elements or `field.`solve quadratic root. 10:09 < lightlike> Because various precomputed values are used, which are different for different-sized field 10:09 < jeremyrubin> Also i'd imagine type safety is nice 10:09 < sipa> but even for 32 bits, we have 2 or 3 different implementation of that field 10:09 -!- will [~will@dynamic-190-25-109-205.dynamic.etb.net.co] has joined #bitcoin-core-pr-reviews 10:10 < glozow> e.g. I think we have a table `QRT_TABLE_N` for each field so that during poly root finding, we can quickly look up the solution for x^2 + x = a for each element in the field? (is that right?) 10:10 < sipa> yeah, all good answers 10:10 -!- will is now known as Guest87833 10:10 < dkf> This is out of my domain but a thought: because due to linearity we need to be able to accumulate all the fields for certain checks? 10:10 -!- Guest87833 [~will@dynamic-190-25-109-205.dynamic.etb.net.co] has quit [Client Quit] 10:10 < sipa> glozow: that's correct, but it doesn't really require fulky instanticating the full algorithm fkr every fiekd 10:11 < sipa> it coukd just have a dispatch table too that says "if field_size == 32 use this QRT table" 10:11 < glozow> ah mhm 10:11 < sipa> but yes, in general the answer is just performance 10:11 <@jnewbery> What do SQR and QRT stand for in the precomputed values? 10:11 < sipa> we get an enormous speedup from being to inline everythig 10:11 < jonatack> istm it was for optimizing for some platforms 10:12 < svav> I've been told we are talking about mathematical fields, so if anyone needs a definition https://en.wikipedia.org/wiki/Field_(mathematics) 10:12 < glozow> jonatack: I think that's the templating by implementation 10:12 < larryruane_> jnewbery: I think square root and quadratic root 10:12 < jonatack> (and chip architectures) 10:12 < sipa> larryruane_: *square* and quadraric root 10:12 < sipa> not square root 10:13 < sipa> svav: indeed 10:13 < sipa> svav: but look at the previous two meetups 10:13 <@jnewbery> How long do those precomputed values take to calculate. Could it be done at compile time? 10:13 < sipa> jnewbery: they are primarily computed ar compile time, actually :) 10:14 < sipa> only a few constants are included in the source code 10:14 < sipa> they're generated using a sage script that takes a few minutes afaik 10:14 < glozow> is this the linear transformations of the tables in fields/*.cpp? 10:14 < sipa> with c++17 we could in theory do everything at compile time, but i don't know how slow it'f be 10:14 < glozow> oh the sage script 10:15 < sipa> i guess we're on question 2 nlw 10:15 < sipa> now 10:15 < larryruane_> very productive for me learning about fields was chapter 1 of Jimmy Song's book, Programming Bitcoin 10:15 < jeremyrubin> sipa: with incremental compilation should be a one-time cost if you put it in a depends-light header 10:15 <@jnewbery> any maybe less readable/reviewable to do it using c++ metaprograming than using a sage script? 10:15 < sipa> so: If you look at the fields/*.cpp files, you will notice there are large amounts of hardcoded linear transformation tables (with code for defining them in lintrans.h. Which tables do you see, and why are they useful? 10:15 -!- __grunch__ [~grunch@242-189-16-190.fibertel.com.ar] has joined #bitcoin-core-pr-reviews 10:15 < jeremyrubin> might be worth doing so so that it's "trust minimized" 10:16 < sipa> jeremyrubin: wut 10:16 < jeremyrubin> (carry on) 10:16 -!- maginkgo47 [b5e43997@181.228.57.151] has joined #bitcoin-core-pr-reviews 10:17 < glozow> I was confused what the `RecLinTrans` part does 10:17 < sipa> ok 10:17 < glozow> but I see: A table SQR_TABLE_N gives us a map from elem a -> square of a for the field GF(2^N). 10:17 < glozow> and A table QRT_TABLE_N gives us a map from a -> x such that x^2 + x = a for the field GF(2^N). 10:17 < sipa> correct 10:17 < sipa> also correct 10:17 < sipa> there are more 10:18 < glozow> There's also SQR2_TABLE_N, SQR4_TABLE_N, 10:18 < glozow> are those ^4 and ^8 or? 10:18 < sipa> close, but no 10:18 < sipa> SQR4 is a table going x -> x^(2^4) 10:19 < sipa> i.e. squaring 4 times 10:19 -!- maginkgo47 [b5e43997@181.228.57.151] has quit [Client Quit] 10:19 < sipa> why is it possible to have a table for that? 10:20 < glozow> why it's possible, like why we can calculate them ahead of time? 10:20 < sipa> maybe a better first question: what do these tables expand to at compile time? 10:21 < sipa> i'll give the answer, it's quite abstracted away 10:21 < glozow> compiler makes a `RecLinTrans<>` of the table -> makes a 2^N size array? 10:21 -!- jadi [~jadi@5.201.253.183] has joined #bitcoin-core-pr-reviews 10:21 < glozow> 1 slot for each element in the field? 10:22 < sipa> not a 2^N size array, that'd be a bjt big if N=64 10:22 -!- jadi [~jadi@5.201.253.183] has quit [Remote host closed the connection] 10:22 < sipa> it creates a series of tables of size 64 10:22 <@jnewbery> I only see SQR2_TABLE, SQR4_TABLE, etc in the clmul files. Is that right? 10:22 < sipa> jnewbery: correct 10:23 < sipa> jnewbery: they're used for computing inverses 10:23 < sipa> for clmul fields, multiplication is very fast, so fermat's little theorem is used 10:23 < sipa> well, i guess FLT doesn't actually apply here because it's not modulo a prime 10:23 < jeremyrubin> Is it so that we can factor an operation into a polynomial for inverse eqt and then do simpler operations? 10:23 < jeremyrubin> is that what you're asking? 10:24 < sipa> but for every field a constant a exists such that x^a is the inverse of x 10:24 < sipa> and for clmul fields, that is used tocinvert elememts 10:24 < sipa> and the SQTn tables are used for helping with that 10:25 < sipa> they let us "skip" a whole bunch of squarings at once 10:25 -!- luke-jr [~luke-jr@unaffiliated/luke-jr] has quit [Quit: ZNC - http://znc.sourceforge.net] 10:25 < sipa> for non-clmul fields, extgcd based inverses are used 10:25 < sipa> because it appears faster to do so 10:25 < glozow> just to clarify, are the fields not the same for clmul and non-clmul? 10:26 < sipa> the fields are mostly the same 10:26 < sipa> but the implementations differ 10:26 < sipa> so back to my earlier questions about the tables 10:27 < sipa> RecLinTrans expands to a compile-time *list* of tables, each with 64 entries 10:27 < jeremyrubin> because x^a = (y*z)^a, or x^a = x^b*x^c where a = b+c? so if we can get to known factored form we already have the ops done? 10:27 < sipa> and then actual evaluation looks at groups of 6 bits of the input field element, and looks up each in a different table 10:27 < sipa> and xors them (= adding in the field? 10:28 -!- luke-jr [~luke-jr@unaffiliated/luke-jr] has joined #bitcoin-core-pr-reviews 10:28 < sipa> jeremyrubin: not quite; the answer is simply that all these operations are 2-linear operations 10:28 < jonatack> groups of 8 bits? 10:28 -!- azorcode [be4aea69@190.74.234.105] has joined #bitcoin-core-pr-reviews 10:28 < sipa> jonatack: no, 6 10:29 < sipa> jeremyrubin: because in GF(2^n) it is the case that (a+b)^2 = a^2 + b^2 10:29 < jeremyrubin> ah ok; I could probably answer this by looking at the actual inverse algorithm what it factors to. Can you define "2 linear" 10:29 < sipa> jeremyrubin: can we written as a multiplication by a matrix over GF(2) 10:29 < glozow> GF(2)-linear 10:29 < jeremyrubin> sipa: that seems like an important/cool property, makes sense. sorry if this was answered in prev session 10:29 < sipa> jeremyrubin: yes 10:30 < sipa> interpret the input element as a vector of bits, apply a GF(2) square matrix, and reinterpret the result as a field element 10:30 < sipa> this can be do for anything that raises to a power that is itself a power of 2 10:30 < jonatack> sipa: 6 as is? e.g. typedef RecLinTrans StatTable57 10:30 < jonatack> ah no nvm 10:31 < sipa> jonatack: so that specfically means the 57-bit transformation is decomposed into 7 6-bit tables and 3 5-bit tables 10:31 < sipa> and that decomposition onjy works because the transformatjkn is linear 10:32 < sipa> otherwise we'd need a table entry for every field elememt 10:32 < sipa> which would be way too large 10:32 < sipa> does tbat make.sense? 10:32 <@jnewbery> it sounds like it makes sense :) 10:32 < sipa> haha 10:33 < jonatack> sipa: yes. i'm still looking for the 6 bit input though 10:33 < jonatack> :) 10:33 < sipa> jonatack: it's all generated at compile time 10:33 -!- sugarjig [040fea3e@WILLOWTREE.ear2.Washington1.Level3.net] has joined #bitcoin-core-pr-reviews 10:33 < sipa> in lintrans.h 10:33 < glozow> so when we're evaluating the square of an element in the 57-bit field, 10:33 < glozow> we split it into 7 groups of 6 bits + 3 groups of 5 bits, and we look it up in the table 10:33 -!- Anthony51 [491fa91b@c-73-31-169-27.hsd1.va.comcast.net] has joined #bitcoin-core-pr-reviews 10:33 < sipa> indeed 10:34 < jonatack> lintrans.h : "over 3 to 8 bits" 10:34 < glozow> and then xor the answers we get from these 10 tables 10:34 < sipa> jonatack: and here specifically 6 10:34 < glozow> and that gives us the square of the element? 10:34 < sipa> se all the 6es in the type definition 10:34 < sipa> glozow: indeed 10:34 < glozow> ahhhhhhh 🧠 10:35 < sipa> the Rec stands for recursive fwiw 10:35 < jeremyrubin> oh, thought it meant rectangular XD 10:35 < sipa> because it chops off M bits (5 or 6) evaluates them, and xors with a sub table which is again RecLinTrans, but for fewer bits 10:36 < jeremyrubin> Did I miss the justification for say 6 v.s. 7 bits? 10:36 < sipa> in c++14 i think there are cleaner ways of doibg so 10:36 < jeremyrubin> Experimentally picked? 10:36 < sipa> jeremyrubin: good questiion 10:36 < sipa> indeed, experimentally decided that mkre wasn't worth it 10:36 < sipa> on a few platforms 10:37 < sipa> ok 10:37 < sipa> Why are there instances of Sketch for different fields in separate .cpp files? Could all the generic ones be merged into a single file? Could the generic ones and the clmul ones be merged? 10:37 < jeremyrubin> gotcha. and it's a pure function so if that changes it can be adapter per platform 10:39 < sipa> hint: have you tried compiling the code? 10:39 < svav> Are there different instances of Sketch to account for different processors? 10:39 <@jnewbery> Can you build a version of this that only contains the field size that you want to use? 10:39 < jeremyrubin> https://github.com/sipa/minisketch/blob/93519923665787de63310e32d1188d7cd15cb4e9/src/minisketch.cpp 10:39 < jeremyrubin> this looks non conditional? 10:39 < sipa> jnewbery: i think i had a PR for that at some point 10:40 < sipa> jeremyrubin: what do you mean? 10:40 <@jnewbery> so that's not the reason for splitting them out into different files 10:40 < glozow> so i don't think it would make sense to merge clmul and non-clmul given that you'd only use 1 based on your architecture? 10:40 < sipa> glozow: exactly 10:40 < jonatack> (a) maybe, (b) no? in minisketch.cpp, the Construct functions depend on #ifdef HAVE_CLMUL, so they need to be separate 10:40 < jeremyrubin> as in if you use minisketch.cpp it pulls in all of the definitions 10:40 < sipa> you need separate compilation flags for building clmul code 10:41 < sipa> and the resulting code *cannot* be invoked unless you knkw yiu're on a clmul-supporting platform (at runtime) 10:41 < jeremyrubin> It's still not clear to me that the single file can't also ifdef? 10:41 < lightlike> when compiling, it seemt that the different types go into different libraries e.g. (libminisketch_field_clmul.la, libminisketch_field_generic.la) 10:42 <@jnewbery> Graph 4 in https://github.com/sipa/minisketch/blob/master/README.md seems to show that clmul is faster than generic for certain field sizes and slower for others 10:42 < sipa> so it would be possible to merge all the clmul_1byte clmul_2bytes ... etc into ome 10:42 < sipa> it's just split out so building is fadter and needs less ram 10:42 < sipa> it's pretty heavy already 10:42 < sipa> but the clmul_* and generic_* ones cannot be merged 10:43 < sipa> because they're built with strictly different compilation flags 10:43 <@jnewbery> because all this template instantiation use a lot of memory to compile? 10:43 < sipa> jnewbery: yeah, end user code should benchmark what is fastest 10:43 < sipa> jnewbery: indeed 10:44 < glozow> if you can use CLMUL implementation, why do you need both the CLMUL and CLMULTRI implementation for a field that has a `x^b + x^a + 1` modulus? 10:44 < sipa> glozow: either may be faster 10:44 < sipa> depending on tje hardware 10:45 < sipa> they're different algorityms and it's hard to say which one is faster when 10:45 < glozow> ah, okay 10:45 < sipa> i think for some fields it is clear, and those lack a CLMUL one 10:45 <@jnewbery> what would the advantage of just compiling just for a single field size? Smaller binary because of the precomputed tables and different template instantiations? Faster build? Anything else? 10:46 < sipa> jnewbery: API pain 10:46 < sipa> my goal is adding support for that 10:46 < sipa> but first adding a generic slow field implementation that works for all field sizes 10:46 -!- ssd [~ssd@2804:29b8:50a4:6fbd:48cb:3566:8852:3358] has quit [Quit: Leaving] 10:46 < sipa> so that you don't get a library which doesn't support part of the functionality 10:47 < sipa> e.g. if used as a shared library 10:47 < sipa> so then it becomes a compile-time choice which fields to include optimozed implementations for 10:47 < sipa> rather than which ones to support at all 10:48 < sipa> Do you notice any optimizations in sketch_impl.h that weren’t present in the Python code? 10:49 < glozow> question: Why isn't this `const T* QRT` instead of `const F* QRT`? https://github.com/sipa/minisketch/blob/f9540772fac3c1e840208db8c3fe6894526ec1da/src/fields/generic_common_impl.h#L19 10:49 < glozow> I only saw the obvious one, L140 in the root-finding: for deg2 polynomials, direct quadratic solver -> calls `field.Qrt(input)` 10:50 < jonatack> from the last session: https://bitcoincore.reviews/minisketch-26-2#l-225 10:50 < glozow> yeah, i used sipa's hint from last review club heh 10:50 < sipa> glozow: great question 10:51 < sipa> the size of runtime tables is different frkm compile-time tables 10:51 < sipa> these lookup tables are also created at runtime 10:51 -!- cguida [~Adium@205.209.28.54] has joined #bitcoin-core-pr-reviews 10:51 < sipa> e.g. when there are muktiple multiplications with the same value 10:51 < sipa> then we preprocess that value into a lookup table 10:51 < glozow> oh is that why they're called StatTable vs DynTable? 10:52 < sipa> because multiplication with a constant is also linear 10:52 < sipa> indeed 10:52 < glozow> oooooooh 10:52 < sipa> and the DynTable uses smaller lookup tables 10:52 < sipa> 4 bit iirc 10:52 < sipa> instead of 6 bits 10:52 < sipa> also experimentally determined 10:53 -!- jadi [~jadi@5.201.253.183] has joined #bitcoin-core-pr-reviews 10:53 < sipa> glozow: and yes, the direct quadratic solver is what i was goibg for in this question 10:53 < sipa> another possible answer is of course all the lookup tables 10:53 -!- jadi [~jadi@5.201.253.183] has quit [Remote host closed the connection] 10:54 < sipa> What is tested in test-exhaust.cpp? This may be clearer if you look at PR #33. 10:55 < jonatack> agree, the new test file is much clearer afaict 10:55 < sipa> yeah the old one was really unfinished 10:55 < sipa> (and clearly missed some bugs...) 10:56 < jonatack> iterating on things really works 10:56 <@jnewbery> If the answer to your question isn't "everything", then the file is misnamed 10:56 < sipa> it is also bekng rebamed in #33 10:56 < sipa> being renamed 10:56 < svav> Forgive the basic question, but is the reason for all this Minisketch stuff just to add efficiency to Erlay? Is it involved in more fundamental cryptographic calculations for Bitcoin? 10:57 < sipa> svav: it is the implementation of the sketch algorithm used by erlay 10:57 < sipa> that's it 10:57 <@jnewbery> svav: https://bitcoincore.reviews/minisketch-26 and https://bitcoinops.org/en/topics/erlay/ 10:57 < lightlike> svav: It is an integral part of Erlay, it doesn't add efficiency to it. Erlay adds efficiency to transaction relay. 10:57 < sipa> it's not "adding" efficiency; it is literally judt *the* implementation used for the sketching 10:58 < sipa> it is of course a highly optimized implementation, so that it ks efficient enough to be practically usable 10:58 < jonatack> sipa: before time is over, i'm keen to hear the answers to the last two questions 10:58 < svav> Thanks for the clarification 10:58 < sipa> For every field implementation Field there is a member type Field::Elem (which for all current fields is just an integer type), and invoking field operations goes through Field (e.g. multiplying two field elements a and b is done through field.Mul(a,b). A more intuitive design would be to make Field::Elem a separate class for each field, with its own member functions for finite field 10:58 < sipa> arithmetic (so that the above could be done... 10:59 < sipa> simply using a*b for example). Any idea why this approach is not used? 10:59 < glozow> any thoughts of f u z z ing the minisketch code? heh 10:59 -!- figs [ced9cd57@206.217.205.87] has quit [Quit: Connection closed] 10:59 < sipa> i'll just give the andwer 10:59 < sipa> if we'd do that, you'd get vectors with different types for every field 10:59 < michaelfolkson> Running a bit low on time so random question. Are there any specific code segments (C++) that demonstrate the speed and memory efficiency of the C++ code over the Python code segment and would be worth analyzing? 11:00 < glozow> i figured you'd need the tables to be static since they're field-wide 11:00 <@jnewbery> sipa: I've got to run now, but I'm curious is there's anything people here can do to help progress this? Would it help if someone opened the PR to add this to the Bitcoin Core repo? 11:00 < sipa> you'd have vector and vector etc 11:00 < jonatack> haaaah 11:00 -!- pglazman [~pglazman@c-73-71-224-94.hsd1.ca.comcast.net] has quit [Quit: Textual IRC Client: www.textualapp.com] 11:00 < sipa> and all that vector code, along with all suppoting functions, woukd be ~1 MB of executable code 11:01 -!- sugarjig [040fea3e@WILLOWTREE.ear2.Washington1.Level3.net] has quit [Quit: Connection closed] 11:01 < sipa> with the vurrent approach they're all just std::vdctor 11:01 -!- azorcode [be4aea69@190.74.234.105] has quit [Quit: Connection closed] 11:02 < sipa> Bonus question: what is special about field size 58 (look at fields/clmul_8bytes.cpp)? 11:02 < sipa> jnewbery: i'm planning to PR it soon (after #33 and maybe a few follow-ups? 11:02 < glozow> sipa: is it specific to 58 only or are there other field sizes with the special property? 11:03 <@jnewbery> LOAD_TABLE/SAVE_TABLE ? 11:03 < sipa> glozow: for larger fields than 64 bit there would be more with this property 11:03 <@jnewbery> https://github.com/sipa/minisketch/blob/53757f736d4e75faf6c4127e8fb452b6a69c4626/src/fields/clmul_8bytes.cpp#L33-L34 11:03 < sipa> but so far, only 58 has it 11:04 -!- cls [26460be2@38.70.11.226] has quit [Ping timeout: 240 seconds] 11:04 < jonatack> jnewbery: indeed 11:04 < sipa> jnewbery: yes, LOAD/SAVE 11:04 -!- Anthony51 [491fa91b@c-73-31-169-27.hsd1.va.comcast.net] has quit [Quit: Connection closed] 11:04 < sipa> yet another answrr to question 2? 11:04 < sipa> jnewbery: what do those do? 11:05 < jonatack> conversion tables? 11:05 < sipa> indeed 11:05 < sipa> convert from/to what? 11:06 < jonatack> something about bistream modulus for the impl 11:06 < sipa> yeah 11:06 < svav> Something to do with StatTableTRI58 ??? 11:06 < jonatack> gen_params.sage#L252 11:06 < glozow> oh different modulus but isomorphic? so you're permuting the elements? 11:07 < sipa> so what is happening here is that for field size 58 there exists a trinomial (x^58 + x^a + 1) irreducble modulis 11:07 < sipa> which is used for clmultri 11:07 < sipa> but there is also another modulus, which is shorter 11:07 < sipa> and the other field implementation uses that one 11:07 < sipa> yet, we want a stable API 11:08 < sipa> which consistently interprets bits on the wire the same way, regardless of imllementation 11:08 -!- cls [5b95f425@91.149.244.37] has joined #bitcoin-core-pr-reviews 11:08 < glozow> and we want both because it's not clear which one would be faster? 11:08 < sipa> indeed 11:08 < sipa> but even if not, the API specifies the interpretation used publicly 11:09 < jonatack> thanks! 11:09 -!- cls [5b95f425@91.149.244.37] has quit [Client Quit] 11:09 < sipa> if we"d for whatever reason decide to ise a different represnetation internally, we need to convert 11:09 < sipa> and why is thjs worth it? we do quadratically many operations internally 11:09 < sipa> but only linear work for conversion 11:10 < sipa> this was a surprising discovery for me that this conversion was so cheap (just another linear transformation) 11:10 < glozow> i gotta run but thank you sipa!!! peak nerd snipe 11:11 < sipa> i'm done as well 11:11 < jonatack> πŸ‘πŸ‘πŸ‘ 11:11 < sipa> thank you all for coming! 11:11 < svav> Thanks 11:11 < jesseposner> Thanks! 11:11 < larryruane_> thank you for presenting, sipa! really interesting! 11:11 < lightlike> Thanks! 11:11 < wiscojabroni> thanks! 11:11 < jeremyrubin> thanks! 11:12 < sipa> and apologies for the many typos, i"m a bit restricted right nlw 11:12 < jonatack> fantastic sesson, thank you sipa 11:12 < sipa> yw 11:13 -!- wiscojabroni [5d2c50a9@93-44-80-169.ip96.fastwebnet.it] has quit [Quit: Connection closed] 11:15 -!- svav [5245568f@82-69-86-143.dsl.in-addr.zen.co.uk] has quit [Quit: Connection closed] 11:15 -!- dkf [58a6b2e4@88.166.178.228] has quit [Quit: Connection closed] 11:17 -!- dictation [~dictation@195.181.160.175.adsl.inet-telecom.org] has quit [Ping timeout: 268 seconds] 11:23 < jonatack> Meeting log is up at https://bitcoincore.reviews/minisketch#meeting-log 🧠 🍰 11:23 < sipa> thanks? 11:23 < sipa> thanks! 11:24 -!- jadi [~jadi@5.201.253.183] has joined #bitcoin-core-pr-reviews 11:25 -!- jadi [~jadi@5.201.253.183] has quit [Remote host closed the connection] 11:29 <@jnewbery> sipa: thank you so much. Sorry I had to run at the end 11:30 -!- sanket1729 [~sanket172@ec2-100-24-255-95.compute-1.amazonaws.com] has joined #bitcoin-core-pr-reviews 11:32 -!- sanketcell [~sanketcel@ec2-100-24-255-95.compute-1.amazonaws.com] has joined #bitcoin-core-pr-reviews 11:34 < andrewtoth_> thank you sipa 11:40 -!- sanket1729 [~sanket172@ec2-100-24-255-95.compute-1.amazonaws.com] has quit [Remote host closed the connection] 11:40 -!- sanketcell [~sanketcel@ec2-100-24-255-95.compute-1.amazonaws.com] has quit [Remote host closed the connection] 11:41 -!- sanketcell [~sanketcel@ec2-100-24-255-95.compute-1.amazonaws.com] has joined #bitcoin-core-pr-reviews 11:41 -!- sanket1729 [~sanket172@ec2-100-24-255-95.compute-1.amazonaws.com] has joined #bitcoin-core-pr-reviews 11:56 -!- jadi [~jadi@5.201.253.183] has joined #bitcoin-core-pr-reviews 11:57 -!- jadi [~jadi@5.201.253.183] has quit [Remote host closed the connection] 12:00 -!- dulcedu [ac5ca63e@172.92.166.62] has quit [Quit: Connection closed] 12:03 -!- promag [~promag@188.250.84.129] has quit [Read error: Connection reset by peer] 12:03 -!- promag_ [~promag@188.250.84.129] has joined #bitcoin-core-pr-reviews 12:14 -!- hernanmarino [~Hernan@OL121-235.fibertel.com.ar] has quit [Quit: Leaving] 12:16 -!- Talkless [~Talkless@mail.dargis.net] has quit [Quit: Konversation terminated!] 12:20 -!- murchin [04355c72@4.53.92.114] has quit [Quit: Connection closed] 12:29 -!- jadi [~jadi@5.201.253.183] has joined #bitcoin-core-pr-reviews 12:30 -!- jadi [~jadi@5.201.253.183] has quit [Remote host closed the connection] 12:45 -!- Gambo [bba25c19@187-162-92-25.static.axtel.net] has quit [Ping timeout: 240 seconds] 13:00 -!- jadi [~jadi@5.201.253.183] has joined #bitcoin-core-pr-reviews 13:06 -!- jadi [~jadi@5.201.253.183] has quit [Ping timeout: 268 seconds] 13:35 -!- N3WB33 [4cdd98b9@76-221-152-185.lightspeed.clmboh.sbcglobal.net] has quit [Quit: Connection closed] 13:49 -!- mol_ [~mol@unaffiliated/molly] has joined #bitcoin-core-pr-reviews 13:51 -!- mol [~mol@unaffiliated/molly] has quit [Ping timeout: 240 seconds] 14:24 -!- lightlike [~lightlike@p200300c7ef13f900c0bd9cb5668835d9.dip0.t-ipconnect.de] has quit [Quit: Leaving] 14:55 -!- andrewtoth_ [~andrewtot@gateway/tor-sasl/andrewtoth] has quit [Remote host closed the connection] 14:55 -!- andrewtoth_ [~andrewtot@gateway/tor-sasl/andrewtoth] has joined #bitcoin-core-pr-reviews 14:57 -!- biteskola [~biteskola@170.76.76.188.dynamic.jazztel.es] has quit [Ping timeout: 252 seconds] 15:19 -!- __grunch__ [~grunch@242-189-16-190.fibertel.com.ar] has quit [Remote host closed the connection] 15:35 -!- jadi [~jadi@5.201.253.183] has joined #bitcoin-core-pr-reviews 15:39 -!- jadi [~jadi@5.201.253.183] has quit [Remote host closed the connection] 15:47 -!- musdom [~Thunderbi@202.184.3.8] has joined #bitcoin-core-pr-reviews 16:07 -!- cguida [~Adium@205.209.28.54] has quit [Quit: Leaving.] 16:10 -!- jadi [~jadi@5.201.253.183] has joined #bitcoin-core-pr-reviews 16:15 -!- jadi [~jadi@5.201.253.183] has quit [Ping timeout: 265 seconds] 16:26 -!- sanket1729 [~sanket172@ec2-100-24-255-95.compute-1.amazonaws.com] has quit [Ping timeout: 240 seconds] 16:27 -!- sanketcell [~sanketcel@ec2-100-24-255-95.compute-1.amazonaws.com] has quit [Ping timeout: 240 seconds] 16:27 -!- jonatack [jon@gateway/vpn/airvpn/jonatack] has quit [Ping timeout: 252 seconds] 17:00 -!- sanket1729 [~sanket172@ec2-100-24-255-95.compute-1.amazonaws.com] has joined #bitcoin-core-pr-reviews 17:01 -!- sanketcell [~sanketcel@ec2-100-24-255-95.compute-1.amazonaws.com] has joined #bitcoin-core-pr-reviews 17:01 -!- belcher_ [~belcher@unaffiliated/belcher] has joined #bitcoin-core-pr-reviews 17:04 -!- belcher [~belcher@unaffiliated/belcher] has quit [Ping timeout: 240 seconds] 17:05 -!- belcher_ is now known as belcher 18:03 -!- jb55 [~jb55@gateway/tor-sasl/jb55] has quit [Remote host closed the connection] 18:03 -!- jb55 [~jb55@gateway/tor-sasl/jb55] has joined #bitcoin-core-pr-reviews 18:05 -!- jadi [~jadi@5.201.253.183] has joined #bitcoin-core-pr-reviews 18:06 -!- jadi [~jadi@5.201.253.183] has quit [Remote host closed the connection] 18:36 -!- jadi [~jadi@5.201.253.183] has joined #bitcoin-core-pr-reviews 18:37 -!- jadi [~jadi@5.201.253.183] has quit [Remote host closed the connection] 19:08 -!- jadi [~jadi@5.201.253.183] has joined #bitcoin-core-pr-reviews 19:09 -!- jadi [~jadi@5.201.253.183] has quit [Remote host closed the connection] 19:40 -!- jadi [~jadi@5.201.253.183] has joined #bitcoin-core-pr-reviews 19:45 -!- jadi [~jadi@5.201.253.183] has quit [Ping timeout: 240 seconds] 20:10 -!- mol [~mol@unaffiliated/molly] has joined #bitcoin-core-pr-reviews 20:13 -!- mol_ [~mol@unaffiliated/molly] has quit [Ping timeout: 265 seconds] 20:17 -!- jadi [~jadi@5.201.253.183] has joined #bitcoin-core-pr-reviews 20:18 -!- musdom [~Thunderbi@202.184.3.8] has quit [Quit: musdom] 20:18 -!- musdom [~Thunderbi@202.184.3.8] has joined #bitcoin-core-pr-reviews 20:18 -!- jadi [~jadi@5.201.253.183] has quit [Remote host closed the connection] 20:49 -!- jadi [~jadi@5.201.253.183] has joined #bitcoin-core-pr-reviews 20:50 -!- jadi [~jadi@5.201.253.183] has quit [Remote host closed the connection] 21:21 -!- jadi [~jadi@5.201.253.183] has joined #bitcoin-core-pr-reviews 21:22 -!- jadi [~jadi@5.201.253.183] has quit [Remote host closed the connection] 21:51 -!- musdom [~Thunderbi@202.184.3.8] has quit [Ping timeout: 268 seconds] 21:53 -!- jadi [~jadi@5.201.253.183] has joined #bitcoin-core-pr-reviews 21:54 -!- jadi [~jadi@5.201.253.183] has quit [Remote host closed the connection] 22:25 -!- jadi [~jadi@5.201.253.183] has joined #bitcoin-core-pr-reviews 22:27 -!- jadi [~jadi@5.201.253.183] has quit [Remote host closed the connection] 22:40 -!- jadi [~jadi@5.201.253.183] has joined #bitcoin-core-pr-reviews 22:57 -!- jeremyrubin [~jr@024-176-247-182.res.spectrum.com] has quit [Ping timeout: 240 seconds] 22:59 -!- jeremyrubin [~jr@024-176-247-182.res.spectrum.com] has joined #bitcoin-core-pr-reviews