Reminder that the usual research meeting is today at 17:00 UTC (about 90 minutes from now)

roger

guess it's a guy fawkes mask, technically

+1

Righto, we'll get started in a few minutes

The usual agenda: monero-project/meta #419

good morning

who brought the masks

are these made in china

Shall we get started?

GREETINGS

howdy!

suppose we should move onto the roundtable?

Might as well

Who shall begin?

I'm going to ping isthmus

in the hopes that he can describe a bit of the data science work he's currently doing

n3ptune and I have been looking at block rewards

Lots of funky stuff going on

How so?

Here's a bad figure, and I'll try to have a nicer one by the end of the meeting

x-axis is block height

y-axis is the total reward claimed by the miner

(fresh + fees)

The trend is basically our emission curve (the bottom of the traces)

The data points above the trend are miners who made good blocks with fees on top of reward

exponential decay shape of the graph comes from our emission curve (fees are related to block reward). is the piecewise break from bulletproofs?

The anomalies below the line are what's interesting

There's a few distinct events that happened

For each, we can tell a few things:

Exactly which blocks were mined by that miner/pool/software

(linkability)

And exactly how long it took them to notice that they were making suboptimal blocks, and fix the software

You can tell a bit more by adding size as the color

Scale is blue to yellow

So there I've zoomed into a small section

Looking at the band from 1225000 to 1275000ish

It looks like the blocks claiming *less* reward than empty blocks are about the same size as those produced by others

that graph is gorgeous bro

thx :- )

Odd behavior

The definition of suboptimal, you might say...

Yeah, because their sizes are about the same as the surrounding blocks, here are two guesses for what might be happening

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

But based on how bounded the second (anomalous) trend is, I think it might just be a software bug?

I just discovered this like 20 hours ago, so I haven't done full exploration

I'll be able to drill down into the blocks and actually figure out what was going on

(that's about where it's at right now)

It's really interesting to see it mapped out so clearly

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...

i'm going to try to dig up at least one of htem

i have so many questions about this

It would be good to know which particular software (if it's specific) leads to this, due to how common it appears to be

suraeNoether: your roundtable?

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

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

Do you have code ready that can reproduce it?

it occurs in a random test in testSimulator.py, not any of my deterministic tests

so i'm still hunting down exactly the conditions that lead to the bug, and attempting to isolate it as a new unit test

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

oops, here

welcome

suraeNoether: you dont think V could make all those masks by himself even in 20 years though?

suraeNoether: is the currently-pushed code the version you're working with?

yes, the commit i pushed this morning

to matching-buttercup branch

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

Do you suspect that could be the origin of the errors?

i think refactoring the whole codebase is a last-ditch effort for finding the bugs, though

If they're simply algorithmic mistakes, switching to Rust might not do anything

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.

have you tried log statements?

secret weapon

and i'm in the midst of tracking that down

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

Would the issue persist and be easy to spot by eye?

endogenic: your suggestion reminded me of xkcd.com/451 =p

except that i am

:P

Nono, the statement about logs!

Sorry, digression

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

but i'm attempting something similar next

right now, debugger is my friend

sarang, how about you?

log statements are nice because you can let the whole thing run

Several things to mention

debugger is also nice.

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

I've come around on Backes' definition of linkability

I updated the CLSAG linkable anonymity definition, as well as its proof

Reviewed a paper by the Zcoin folks on hierarchical Groth commitment proofs

Looked over some changes that Zcoin made to fix a problem they had relating to Groth proofs (doesn't apply to Triptych)

Worked out some example code for doing inversion via an MPC for use in computing certain linking tag constructions

and wrote out some simple draft MPC ideas for RCT3 and Triptych, which for now assume honest-but-curious players

nice!

The good news on MPC is that it's certainly possible to collaboratively compute the inverse-based key images used in those proving systems

The bad news is it requires something akin to Paillier encryption, which leads to some computational overhead

hmmm are you looking into the MPC stuff for linking tag constructions due to the constructions and usage of linking tags in Triptych?

(note that my example code should _not_ be taken to be a secure Paillier implementation)

Yep, the MPC is to handle linking tags in Triptych, RCT3, and Omniring

Even though Omniring can use traditional linking tags, even that construction still requires an underlying inversion

There are also affine quantities to compute, but those are understood

refresh my memory: which, if any, of those 3 require self-sends?

None of them

DLSAG and Lelantus would require this

LELANTUS

okay, so what, in your heart of hearts, are you hoping for from linking tags?

The problem, previously, was that it was not clear how to enable multisig support when the linking tags require a secret key inversion

aaaaah

Now that there's an understood MPC to compute this, it means multisig support is feasible

gotcha gotcha

you had questions about multisig for me

The downside to the MPC is that Paillier can't take advantage of the efficient curve libraries we all know and love

we can address them now or after the meeting if you like

hoi sorry for being late

holla

long time no see silur

whatup silur

Paillier requires RSA modulus stuff (but there aren't issues with trusted setup etc.)

Encryption and decryption require exponentiation with variable modulus

So computationally-constrained devices would need to able to support this

s/to able/to be able

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?

or at least, one of the items on our "wish we had" list?

Such a thing would be great, but as you pointed out, getting the required homomorphicity would imply a DL break, or some such thing

can you elaborate on "inversion based key images"?

or shall I just review it from the log?

Key images / linking tags in newer proving systems use the form `(1/x)*U`

rather than x*H(X)

U is fixed, yes?

Here the division is an inverse, `x` is the secret key, and `U` is either globally fixed or depends on the proof statement

but it's public

uhmmmm wait a moment:

It's globally fixed in the more efficient versions of the proving systems

my comment had to do with an efficient group-to-scalar map that had any sort of homomorphicity built in

oh oh oh

i get what you are saying

For context: github.com/SarangNoether/skunkworks/tree/inverse-mpc

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)

The encryption homomorphicity is important for the MPC method that Gennaro and Goldfeder introduce

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) ?

you know what: let's talk about this after the meeting

Yeah, better for after meeting

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?

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

but individual inputs are useless

and at the last step the same inner-product for the last vector reduces into a Z_p element?

I don't see how to directly apply that to the share derivation in Gennaro

The multiplicative-share to additive-share method, I mean

(which is the point of their Paillier-based protocol)

Oh the Genaroo-Goldfeder method IS a hard requirement

then we can't inded :)

I wasn't aware it's a must-have

Well, we don't _need_ to use Gennaro-Goldfeder

but it seems reasonably efficient and useful if you can accept the homomorphicity requirement

In the interest of time, let's move to ACTION ITEMS

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

triptych? O.o

?

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

I was not familiar with that, will look into

it's a paper sarang is presently writing

too much meetings missed :D

silur: Triptych is a linkable ring signature construction based on Groth 1-of-many commitment proofs

<3

Preprint draft forthcoming

There's a super-efficient version for which I can't reduce soundness to a known hardness assumption

If you want to take a look silur, most welcome

The less-efficient version does reduce nicely

yea I'd be more than happy to look into

neat

OK, I suppose we can formally adjourn and continue discussions as desired

Oh, side note... I've posted my research funding proposal: repo.getmonero.org/monero-project/ccs-proposals/merge_requests/110

Comments needed/welcomed

okay sarang: i'm think we are making too strong a statement about inversion computation and homomorphicity

namely

If you look at those markdown files, you'll see that Gennaro uses homorphicity when doing share construction

The relevant modification from their paper (eprint.iacr.org/2019/114) is in Section 3

(note that I've excluded the zk proofs, due to player assumptions)

i need to do some reading before i say something dumb

again

The overall method is basically Section 4.2, but they use additional share derivations for DSA that we wouldn't need

See github.com/SarangNoether/skunkworks/blob/inverse-mpc/inverse.py#L121 for example

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?

i'm going to shut up and do some reading

i'm going to retract my statement for now

Probably

or... question*

But Gennaro has good communication efficiency

we could ask help from kzen ppl on the matter maybe?

they excel in this topic, and afaik goldfeder is part of the group :D

Oh nice

I suspect if they knew of a non-Paillier method with similar efficiency, they would have used it

will reach out to them (y)

So, suraeNoether

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?

If you use unforgeability and properties of the key-to-tag map, it should boil down nicely to a pigeonhole principle problem

sarang: was your wcc presentation recorded by chance?

I'm not sure

Sarang yes

What do you think for unforgeability that I'm using in Triptych?

A lot less variability in block reward as of late

The hook around 60000 is interesting, maybe that's the [mining software's] tolerance for altruistically accepting an overweight penalty.

Yeah, it would be nice to see what different methods software uses to determine this

Lemme get a zoomed in view. Often you can see a few distinct txn-picking strategies

Strategic, altruistic, empty-blockers, and whoops

The empty blockers just take home the baseline payout, let's call it A = {formula for allowed emission in the code}

Strategic miners add sets of transactions such that fees are greater than any incurred mining penalty. So their payout > A

Astruistic miners make big blocks and take a penalty even if the fees don't totally offset it. So their payout < A

Then whoops miners just have a bug in the software that claims less than the allowed payout for no clear reason

At some point (pre rct), the block reward was quantized to save outputs.

It was like sub 1% difference though I expect, not sure if tht's what you're seeing.

Probably even sub 0.01%.

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.

I'm chicken though so I did not touch it, lest I break it.

Actually I might have fixed it in a branch...

Yes, I did. Chicken though.

We might need to do it before tail emission though.

"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?)

Validation.

I'll paste the patch (which might be buggy).

is there a threshold or something?

the block reward itself

wait

are you saying there's a bug where taking any fees above the block reward leads to .... a smaller reward? or am I misunderstanding?

No, it plateaus I think ? I don't recall exactly.

Basically you add fees, but the block reward decreases to compensate.

Can the mining penalty be greater than the baseline payout for an empty block?

No.

What's the bug?

(I thought that was desired behavior)

I think it's: Block reward is 1. You add fees worth 1.5. You'll get 2 coinbase.

iirc in cryptonote you would get a block reward penalty that grew more slowly than the fees you were taking

But as I said I did this a while back, I'm not sure the details exactly.

which sort of uses txn fees to subsidize block rewards, in a certain sense

(in my example above, the block is assumed to still be in the no-penalty size range)

Waaaait what

ping @SerHack - will have to update 5.5.3.2 in Mastering Monero

Current version is

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

Where's the ground truth documentation for desired behavior? I need to read up.

Oh derp ignore the plot with the hook, that was on a subset of data where it's not surprising

Color = block size density heatmap. Blue is small, going towards yellow is big

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)

Has tightened up significantly as of late