15:28:46 <sarang> Reminder that the usual research meeting is today at 17:00 UTC (about 90 minutes from now)
16:00:38 <endogenic> roger
16:24:05 * Isthmus puts on goggles and a lab coat
16:53:48 * endogenic puts on v for vendetta mask
16:53:59 <endogenic> guess it's a guy fawkes mask, technically
16:54:16 <Isthmus> +1
16:56:52 <sarang> Righto, we'll get started in a few minutes
16:57:00 <sarang> The usual agenda: https://github.com/monero-project/meta/issues/419
16:58:32 <suraeNoether> good morning
16:58:43 <suraeNoether> who brought the masks
16:58:52 <suraeNoether> are these made in china
16:59:56 <sarang> Shall we get started?
16:59:58 <sarang> GREETINGS
17:00:35 <suraeNoether> howdy!
17:02:30 <suraeNoether> suppose we should move onto the roundtable?
17:02:42 <sarang> Might as well
17:02:47 <sarang> Who shall begin?
17:03:23 <suraeNoether> I'm going to ping isthmus
17:03:36 <suraeNoether> in the hopes that he can describe a bit of the data science work he's currently doing
17:03:58 <Isthmus> n3ptune and I have been looking at block rewards
17:04:11 <Isthmus> Lots of funky stuff going on
17:04:18 <sarang> How so?
17:04:46 * Isthmus is digging up figures
17:05:43 <Isthmus> Here's a bad figure, and I'll try to have a nicer one by the end of the meeting
17:05:45 <Isthmus> https://usercontent.irccloud-cdn.com/file/f9F4XDd3/image.png
17:05:49 <Isthmus> x-axis is block height
17:05:56 <Isthmus> y-axis is the total reward claimed by the miner
17:06:00 <Isthmus> (fresh + fees)
17:06:24 <Isthmus> The trend is basically our emission curve (the bottom of the traces)
17:06:44 <Isthmus> The data points above the trend are miners who made good blocks with fees on top of reward
17:06:53 <suraeNoether> exponential decay shape of the graph comes from our emission curve (fees are related to block reward). is the piecewise break from bulletproofs?
17:06:59 <Isthmus> The anomalies below the line are what's interesting
17:07:28 <Isthmus> There's a few distinct events that happened
17:07:38 <Isthmus> For each, we can tell a few things:
17:08:12 <Isthmus> Exactly which blocks were mined by that miner/pool/software
17:08:14 <Isthmus> (linkability)
17:08:28 <Isthmus> And exactly how long it took them to notice that they were making suboptimal blocks, and fix the software
17:09:03 <Isthmus> You can tell a bit more by adding size as the color
17:09:06 <Isthmus> https://usercontent.irccloud-cdn.com/file/HUoctx7I/image.png
17:09:08 <Isthmus> Scale is blue to yellow
17:09:20 <Isthmus> So there I've zoomed into a small section
17:10:31 <Isthmus> Looking at the band from 1225000 to 1275000ish
17:10:58 <Isthmus> It looks like the blocks claiming *less* reward than empty blocks are about the same size as those produced by others
17:11:05 <suraeNoether> that graph is gorgeous bro
17:11:13 <Isthmus> thx :- )
17:11:36 <sarang> Odd behavior
17:11:51 <sarang> The definition of suboptimal, you might say...
17:11:55 <Isthmus> Yeah, because their sizes are about the same as the surrounding blocks, here are two guesses for what might be happening
17:12:24 <Isthmus> Maybe other miners are making high-fee big blocks, and the ones below the trend are the suckers that make big blocks after the mempool has been tapped out for high-fee txns
17:12:51 <Isthmus> But based on how bounded the second (anomalous) trend is, I think it might just be a software bug?
17:13:04 <Isthmus> I just discovered this like 20 hours ago, so I haven't done full exploration
17:13:14 <Isthmus> I'll be able to drill down into the blocks and actually figure out what was going on
17:13:30 <Isthmus> (that's about where it's at right now)
17:14:43 <sarang> It's really interesting to see it mapped out so clearly
17:16:16 <suraeNoether> thanks so much, isthmus; it seems to me like i've read at least one paper about purposely claiming smaller rewards for a variety of game-theoretic reasons...
17:16:20 <suraeNoether> i'm going to try to dig up at least one of htem
17:18:06 <suraeNoether> i have so many questions about this
17:18:45 <sarang> It would be good to know which particular software (if it's specific) leads to this, due to how common it appears to be
17:20:02 <sarang> suraeNoether: your roundtable?
17:21:08 <suraeNoether> yeah, sure: Matching. I *think* i'm *one* bug away from getting all the data i want. and I'm talking to Insight Data Science to throw a fellow at the simulation results to help me come up with best-practices recommendation
17:21:59 <suraeNoether> my current bug is silly and strange, in that i'm not adding the number of nodes and edges my software is expecting. initially i thought this was a problem with computing the number of available ring members or something like that, but i'm still trying to figure it out
17:22:47 <sarang> Do you have code ready that can reproduce it?
17:23:14 <suraeNoether> it occurs in a random test in testSimulator.py, not any of my deterministic tests
17:23:33 <suraeNoether> so i'm still hunting down exactly the conditions that lead to the bug, and attempting to isolate it as a new unit test
17:24:10 <suraeNoether> the graph theoretic component is working perfectly, the analysis component exploring parameter space is working perfectly, but the simulator keeps hitting this snag and then we're off to the races
17:24:16 <endogenic> oops, here
17:24:20 <suraeNoether> welcome
17:24:29 <endogenic> suraeNoether: you dont think V could make all those masks by himself even in 20 years though?
17:25:22 <sarang> suraeNoether: is the currently-pushed code the version you're working with?
17:27:03 <suraeNoether> yes, the commit i pushed this morning
17:27:18 <suraeNoether> to matching-buttercup branch
17:28:27 <suraeNoether> so, someone brought up by sidechannel the question about whether i should re-implement the sims in rust in the hopes that the improved explicit references of rust would help find the errors
17:28:57 <sarang> Do you suspect that could be the origin of the errors?
17:29:14 <suraeNoether> i think refactoring the whole codebase is a last-ditch effort for finding the bugs, though
17:29:19 <sarang> If they're simply algorithmic mistakes, switching to Rust might not do anything
17:29:49 <suraeNoether> no; i literally think i'm merely predicting the number of nodes and edges incorrectly based on the total nodeset as opposed to only the nodes that can be spent.
17:30:00 <endogenic> have you tried log statements?
17:30:06 <endogenic> secret weapon
17:30:10 <suraeNoether> and i'm in the midst of tracking that down
17:30:14 <Isthmus> Could you tweak the simulation to be 3 blocks long, 2 transactions per block, with spend pattern & ring member selection algorithm = pull from previous block
17:30:23 <Isthmus> Would the issue persist and be easy to spot by eye?
17:30:38 <sarang> endogenic: your suggestion reminded me of https://xkcd.com/451/ =p
17:31:20 <endogenic> except that i am
17:31:23 <endogenic> :P
17:31:48 <sarang> Nono, the statement about logs!
17:31:56 <sarang> Sorry, digression
17:32:11 <suraeNoether> isthmus unfortunately i believe the problem may be in the ring selection algorithm i have written (which is only uniform at this point), so that would reduce the problem away
17:32:36 <suraeNoether> but i'm attempting something similar next
17:32:45 <suraeNoether> right now, debugger is my friend
17:33:21 <suraeNoether> sarang, how about you?
17:33:27 <endogenic> log statements are nice because you can let the whole thing run
17:33:38 <sarang> Several things to mention
17:33:40 <endogenic> debugger is also nice.
17:34:18 <sarang> I modified the linkability and non-frameability definitions in Triptych, and would like to see if they can be directly used in CLSAG as well
17:34:38 <sarang> I've come around on Backes' definition of linkability
17:34:58 <sarang> I updated the CLSAG linkable anonymity definition, as well as its proof
17:35:27 <sarang> Reviewed a paper by the Zcoin folks on hierarchical Groth commitment proofs
17:35:51 <sarang> Looked over some changes that Zcoin made to fix a problem they had relating to Groth proofs (doesn't apply to Triptych)
17:36:23 <sarang> Worked out some example code for doing inversion via an MPC for use in computing certain linking tag constructions
17:36:43 <sarang> and wrote out some simple draft MPC ideas for RCT3 and Triptych, which for now assume honest-but-curious players
17:37:50 <suraeNoether> nice!
17:37:57 <sarang> The good news on MPC is that it's certainly possible to collaboratively compute the inverse-based key images used in those proving systems
17:38:21 <sarang> The bad news is it requires something akin to Paillier encryption, which leads to some computational overhead
17:39:11 <suraeNoether> hmmm are you looking into the MPC stuff for linking tag constructions due to the constructions and usage of linking tags in Triptych?
17:39:19 <sarang> (note that my example code should _not_ be taken to be a secure Paillier implementation)
17:39:33 <sarang> Yep, the MPC is to handle linking tags in Triptych, RCT3, and Omniring
17:39:55 <sarang> Even though Omniring can use traditional linking tags, even that construction still requires an underlying inversion
17:40:24 <sarang> There are also affine quantities to compute, but those are understood
17:42:12 <suraeNoether> refresh my memory: which, if any, of those 3 require self-sends?
17:42:24 <sarang> None of them
17:42:40 <sarang> DLSAG and Lelantus would require this
17:44:26 <endogenic> LELANTUS
17:44:27 <suraeNoether> okay, so what, in your heart of hearts, are you hoping for from linking tags?
17:45:01 <sarang> The problem, previously, was that it was not clear how to enable multisig support when the linking tags require a secret key inversion
17:45:17 <suraeNoether> aaaaah
17:45:19 <sarang> Now that there's an understood MPC to compute this, it means multisig support is feasible
17:45:25 <suraeNoether> gotcha gotcha
17:45:31 <suraeNoether> you had questions about multisig for me
17:45:38 <sarang> The downside to the MPC is that Paillier can't take advantage of the efficient curve libraries we all know and love
17:45:38 <suraeNoether> we can address them now or after the meeting if you like
17:45:40 <silur> hoi sorry for being late
17:45:46 <Isthmus> holla
17:45:46 <suraeNoether> long time no see silur
17:45:52 <endogenic> whatup silur
17:46:09 <sarang> Paillier requires RSA modulus stuff (but there aren't issues with trusted setup etc.)
17:47:08 <sarang> Encryption and decryption require exponentiation with variable modulus
17:47:36 <sarang> So computationally-constrained devices would need to able to support this
17:47:57 <sarang> s/to able/to be able
17:48:24 <suraeNoether> so are we hoping for an MPC to compute inversion-based key images... such that the MPC is more consistent with the development history of monero/cryptonote? ie based on the DL setting in Ed25519 instead of RSA?
17:48:54 <suraeNoether> or at least, one of the items on our "wish we had" list?
17:49:06 <sarang> Such a thing would be great, but as you pointed out, getting the required homomorphicity would imply a DL break, or some such thing
17:49:12 <silur> can you elaborate on "inversion based key images"?
17:49:23 <silur> or shall I just review it from the log?
17:49:43 <sarang> Key images / linking tags in newer proving systems use the form `(1/x)*U`
17:49:55 <suraeNoether> rather than x*H(X)
17:49:59 <suraeNoether> U is fixed, yes?
17:50:11 <sarang> Here the division is an inverse, `x` is the secret key, and `U` is either globally fixed or depends on the proof statement
17:50:17 <sarang> but it's public
17:50:36 <suraeNoether> uhmmmm wait a moment:
17:50:37 <sarang> It's globally fixed in the more efficient versions of the proving systems
17:50:56 <suraeNoether> my comment had to do with an efficient group-to-scalar map that had any sort of homomorphicity built in
17:51:41 <suraeNoether> oh oh oh
17:51:44 <suraeNoether> i get what you are saying
17:51:56 <sarang> For context: https://github.com/SarangNoether/skunkworks/tree/inverse-mpc
17:52:37 <sarang> The inverse.py script shows how the process works, and the markdown documents describe one possible use for RCT3/Triptych (again, with many assumptions on the players)
17:53:14 <sarang> The encryption homomorphicity is important for the MPC method that Gennaro and Goldfeder introduce
17:54:13 <suraeNoether> so most generally, each person has a secret x_i and there is a function f such that you want to compute f(x_1, ..., x_n)*U with some friends. you were using f(x_1, ..., x_n) = 1/sum(x_i) ?
17:54:26 <suraeNoether> you know what: let's talk about this after the meeting
17:54:33 <sarang> Yeah, better for after meeting
17:55:06 <suraeNoether> so, isthmus, myself, and sarang have all brought the room up to speed. does anyone else want to talk about any monero-related research they are doing?
17:56:05 <silur> can't we somehow exploit the bootle inner-product encryption with a killian randomization here somehow? the killian randomization preserves linear combinations so everything before multiplying with U is the same
17:56:10 <silur> but individual inputs are useless
17:56:36 <silur> and at the last step the same inner-product for the last vector reduces into a Z_p element?
17:57:40 <sarang> I don't see how to directly apply that to the share derivation in Gennaro
17:57:54 <sarang> The multiplicative-share to additive-share method, I mean
17:58:05 <sarang> (which is the point of their Paillier-based protocol)
17:58:33 <silur> Oh the Genaroo-Goldfeder method IS a hard requirement
17:58:41 <silur> then we can't inded :)
17:58:47 <silur> I wasn't aware it's a must-have
17:59:01 <sarang> Well, we don't _need_ to use Gennaro-Goldfeder
17:59:41 <sarang> but it seems reasonably efficient and useful if you can accept the homomorphicity requirement
18:01:43 <sarang> In the interest of time, let's move to ACTION ITEMS
18:01:55 <sarang> Mine are to continue work on the MPC stuff, get CLSAG definitions ported as necessary (would like to discuss with suraeNoether as well), and get final review on the Triptych draft to get posted to IACR
18:03:05 <silur> triptych? O.o
18:03:14 <sarang> ?
18:03:22 <suraeNoether> mine is to hunt down and kill my final bug, work on the churn report, review the triptych draft (finally) and continue chatting with isthmus about getting a data science fellow working with me on matching/churn
18:03:23 <silur> I was not familiar with that, will look into
18:03:32 <suraeNoether> it's a paper sarang is presently writing
18:03:32 <silur> too much meetings missed :D
18:03:51 <sarang> silur: Triptych is a linkable ring signature construction based on Groth 1-of-many commitment proofs
18:04:05 <silur> <3
18:04:07 <sarang> Preprint draft forthcoming
18:04:22 <sarang> There's a super-efficient version for which I can't reduce soundness to a known hardness assumption
18:04:28 <sarang> If you want to take a look silur, most welcome
18:04:36 <sarang> The less-efficient version does reduce nicely
18:04:54 <silur> yea I'd be more than happy to look into
18:04:58 <sarang> neat
18:05:07 <sarang> OK, I suppose we can formally adjourn and continue discussions as desired
18:05:35 <sarang> Oh, side note... I've posted my research funding proposal: https://repo.getmonero.org/monero-project/ccs-proposals/merge_requests/110
18:05:41 <sarang> Comments needed/welcomed
18:05:55 <suraeNoether> okay sarang: i'm think we are making too strong a statement about inversion computation and homomorphicity
18:06:13 <suraeNoether> namely
18:06:24 <sarang> If you look at those markdown files, you'll see that Gennaro uses homorphicity when doing share construction
18:07:33 <sarang> The relevant modification from their paper (https://eprint.iacr.org/2019/114) is in Section 3
18:08:06 <sarang> (note that I've excluded the zk proofs, due to player assumptions)
18:08:33 <suraeNoether> i need to do some reading before i say something dumb
18:08:35 <suraeNoether> again
18:09:32 <sarang> The overall method is basically Section 4.2, but they use additional share derivations for DSA that we wouldn't need
18:10:04 <sarang> See https://github.com/SarangNoether/skunkworks/blob/inverse-mpc/inverse.py#L121 for example
18:10:13 <suraeNoether> my question is: if you want to compute f(x_1, ..., x_n)*U with secrets x_i for players i = 1, ..., n, then aren't there general MPC-in-the-head based ZK protocols available to do that, subject to some constraints on f?
18:10:24 <suraeNoether> i'm going to shut up and do some reading
18:10:32 <suraeNoether> i'm going to retract my statement for now
18:10:33 <sarang> Probably
18:10:36 <suraeNoether> or... question*
18:10:55 <sarang> But Gennaro has good communication efficiency
18:12:44 <silur> we could ask help from kzen ppl on the matter maybe?
18:13:13 <silur> they excel in this topic, and afaik goldfeder is part of the group :D
18:13:58 <sarang> Oh nice
18:15:49 <sarang> I suspect if they knew of a non-Paillier method with similar efficiency, they would have used it
18:16:26 <silur> will reach out to them (y)
18:23:06 <sarang> So, suraeNoether
18:23:41 <sarang> The Backes linkability definition (requiring the player to produce too many non-linked signatures) could be moved to CLSAG... do you think it would be useful?
18:26:37 <sarang> If you use unforgeability and properties of the key-to-tag map, it should boil down nicely to a pigeonhole principle problem
18:34:17 <rottensox> sarang: was your wcc presentation recorded by chance?
18:34:36 <sarang> I'm not sure
18:35:20 <suraeNoether> Sarang yes
18:35:42 <sarang> What do you think for unforgeability that I'm using in Triptych?
21:42:34 <Isthmus> https://usercontent.irccloud-cdn.com/file/B7urMH9y/image.png
21:42:41 <Isthmus> A lot less variability in block reward as of late
21:45:06 <Isthmus> The hook around 60000 is interesting, maybe that's the [mining software's] tolerance for altruistically accepting an overweight penalty.
21:45:33 <sarang> Yeah, it would be nice to see what different methods software uses to determine this
21:49:05 <Isthmus> Lemme get a zoomed in view. Often you can see a few distinct txn-picking strategies
21:49:26 <Isthmus> Strategic, altruistic, empty-blockers, and whoops
21:50:41 <Isthmus> The empty blockers just take home the baseline payout, let's call it A = {formula for allowed emission in the code}
21:52:02 <Isthmus> Strategic miners add sets of transactions such that fees are greater than any incurred mining penalty. So their payout > A
21:52:26 <Isthmus> Astruistic miners make big blocks and take a penalty even if the fees don't totally offset it. So their payout < A
21:52:51 <Isthmus> Then whoops miners just have a bug in the software that claims less than the allowed payout for no clear reason
21:53:25 <moneromooo> At some point (pre rct), the block reward was quantized to save outputs.
21:54:08 <moneromooo> It was like sub 1% difference though I expect, not sure if tht's what you're seeing.
21:54:26 <moneromooo> Probably even sub 0.01%.
21:55:23 <moneromooo> Oh, there's also a bug where if you have lots of tx fees (more than the block reward itself), you can't take them all without a penalty.
21:55:49 <moneromooo> I'm chicken though so I did not touch it, lest I break it.
21:56:22 <moneromooo> Actually I might have fixed it in a branch...
21:57:47 <moneromooo> Yes, I did. Chicken though.
21:58:17 <moneromooo> We might need to do it before tail emission though.
21:59:05 * suraeNoether taps chin
22:01:26 <Isthmus> "if you have lots of tx fees (more than the block reward itself), you can't take them all without a penalty." < interesting, can you elaborate? Which layer is this bug in? (block generation or validation?)
22:01:54 <moneromooo> Validation.
22:02:12 <moneromooo> I'll paste the patch (which might be buggy).
22:03:18 <moneromooo> https://paste.debian.net/hidden/02de12c8/
22:03:37 <suraeNoether> is there a threshold or something?
22:03:43 <moneromooo> the block reward itself
22:03:48 <suraeNoether> wait
22:04:18 <suraeNoether> are you saying there's a bug where taking any fees above the block reward leads to .... a smaller reward? or am I misunderstanding?
22:04:56 <moneromooo> No, it plateaus I think ? I don't recall exactly.
22:05:22 <moneromooo> Basically you add fees, but the block reward decreases to compensate.
22:05:40 <Isthmus> Can the mining penalty be greater than the baseline payout for an empty block?
22:05:50 <moneromooo> No.
22:06:07 <Isthmus> What's the bug?
22:06:22 <Isthmus> (I thought that was desired behavior)
22:06:51 <moneromooo> I think it's: Block reward is 1. You add fees worth 1.5. You'll get 2 coinbase.
22:06:59 <suraeNoether> iirc in cryptonote you would get a block reward penalty that grew more slowly than the fees you were taking
22:07:04 <moneromooo> But as I said I did this a while back, I'm not sure the details exactly.
22:07:17 <suraeNoether> which sort of uses txn fees to subsidize block rewards, in a certain sense
22:08:07 * Isthmus pinches bridge of nose
22:08:38 <moneromooo> (in my example above, the block is assumed to still be in the no-penalty size range)
22:11:09 <Isthmus> Waaaait what
22:19:44 <Isthmus> ping @SerHack - will have to update 5.5.3.2 in Mastering Monero
22:19:48 <Isthmus> Current version is
22:19:55 <Isthmus> https://usercontent.irccloud-cdn.com/file/qDddihlV/image.png
22:20:25 <Isthmus> I thought that only the base reward could be penalized, definitely didn't realize that the fees could be penalized even under the no-penalty size threshold
22:21:00 <Isthmus> Where's the ground truth documentation for desired behavior? I need to read up.
22:21:35 * scoobybejesus wonders if ArticMine's spidey sense is tingling
22:30:34 <Isthmus> Oh derp ignore the plot with the hook, that was on a subset of data where it's not surprising
22:39:36 <Isthmus> https://usercontent.irccloud-cdn.com/file/3UPZkg9j/image.png
22:40:01 <Isthmus> Color = block size density heatmap. Blue is small, going towards yellow is big
22:40:41 <Isthmus> There's a pretty clear dark trace through the baseline payout, and then you can see miners on both sides (taking home more with fees above the line, and creating suboptimal blocks below the line)
22:41:29 <Isthmus> Has tightened up significantly as of late