<[keybase] unseddd>: kenshamir: +1, thanks for the corrections, and in-depth answer

Hey, no problem

very interesting thanks kenshamir[m]

<[keybase] unseddd>: Isthmus: another paper for the reading list, 'Short Lattice-based One-out-of-many Proofs and Applications to Ring Signatures': eprint.iacr.org/2018/773.pdf

Thanks Unseddd - I'll check that out :- )

Unfortunately the signatures are quite large

<[keybase] unseddd>: sarang: I haven't dug into it much, but found it when reading this: eprint.iacr.org/2020/430.pdf

<[keybase] unseddd>: maybe the latter work helps with signature size?

Research meeting is today at 17:00 UTC (about two hours from now)

.time

Hey fam

Anything on the agenda?

I'm helping a Fellow with something, and will be sparsely or not available for the next few hours.

I'll talk a bit about a new key PR, but otherwise nothing of particular note this week

Was there anything you wanted to discuss?

Isthmus: I'll also talk a bit about Arcturus too

All righty! Time for the weekly research meeting

As always, we begin with GREETINGS

Hi

hi

hi

Let's move on to ROUNDTABLE

Any research of interest that folks wish to share?

I can share a few things, I suppose

I worked up a PR to update how keys are encrypted in memory

This has follow-on effects to how they're stored on disk, and I'm making some additional updates to improve the existing unit tests and add others

and I'm finishing up a test implementation of Arcturus, the extension of Triptych that offers better proof sizes

I'd like to determine exactly what the timing differences are, since initial estimates suggested that Arcturus and Triptych would be very close

Sorry if I've missed this; are there any comparisons for Arcturus, Triptych and CLSAG ?

hello

And kenshamir[m]: I have comparisons for CLSAG and Triptych, but this will add actual implementation data for Arcturus when finished

Oh right, very cool

The size data is already known, FWIW

But the Arcturus timing was always an estimate based on operation counts

It's different enough in how it handles transactions that I'd like to know for sure

concretely?

Is there a link for it?

The size/timing data?

Yeah, the size data

Yeah, let me pull it up

Probably may not be that helpful for Monero, but there is a new paper out on an endomorphism that allows you to compute aG + bH faster in variable time

Page 11: eprint.iacr.org/2020/312.pdf

Link : eprint.iacr.org/2020/454.pdf

Thank you

Anyway, that's what I wanted to share

Does anyone else have research of interest?

what's the gist of your encryption update?

The in-memory encryption of keys was being done with a chacha stream that was XORed with keys, instead of just encrypting the keys with chacha directly

This PR makes this change

The existing unit tests for wallet and key encryption also get some updates

ah interesting

It also transitions old encrypted keys to the new format, which needs better testing that I'm still working on

Seems pretty quiet today!

We could always end early if there isn't more that needs to be discussed...

I have nothing to add except to remind people that I still want coinbase outputs to be avoided entirely in non-coinbase-spend rings :p

You mean the idea that a ring containing a coinbase output must have all coinbase outputs, right?

sgp_: can you briefly recap your rationale, to ensure everyone is on the same page?

yes that idea

rationale is that no normal users spend coinbase outputs

even people who mine on mining pools never spend coinbase outputs

so the selection of these is markedly different from expected user spend behavior

When I thought about this earlier, I was concerned that it sort of kicks the can down the road one hop on the graph

separating these will increase the effective ringsize for most (>99%) users by 10-20%

sarang: it kicks the can down the road, but it's still MUCH better

Interesting

And that if a heuristic was "this coinbase probably isn't the true signer" previously, it would become "this output that came from a coinbase ring probably isn't the true signer" as a somewhat weaker heuristic

Yeah, I think it's better but doesn't totally eliminate it

If it were implemented, there would need to be a decision on what selection distribution to use, which should probably be based on a transparent-chain analysis at minimum

it's still essentially one set of transactions separated (one ring signature? I'm struggling to explain this simply and also accurately)

to see if it matches the overall distribution

The idea is that an ouput from a mining pool is far more likely to e spent by a normal user

basically the real spend of the after-coinbase output would look the same as several transactions that select this output as the decoys

Yeah

Does my statement about the analysis for a distribution make sense?

I agree it mitigates but does not completely eliminate the risk

but now this accounts for the behavior that the user could just be a miner on a mining pool, for example

which is hugely broader

But it is true that right now, the spend patterns of coinbase vs non-coinbase are assumed to be the same by the selection algorithm

It'll be very interesting to see that distribution for coinbase-only

only solo miners can spend coinbase outputs. Miners on mining pools can also spend from-coinbase outputs

right

so while it kicks the can down the road, in terms of practical behavior, it's a night and day improvement

I'll ping Isthmus here, since his group has access to this sort of data for other chains

discussion on this idea has been mixed for years. I'd like to see this actually done

10-20% better effective ringsizes just with smarter selection

It is a significant mitigation of the issue. I do not see a clear downside to this.

downside is to people that are running private pools. They effectively need to "churn" once by not directly sending the coinbase outputs to people

I think this is a small tradeoff

I think it's an improvement, provided it doesn't introduce unexpected or unintended consequences to the selection distribution, and is based on distribution data from known spends where reasonable (e.g. Bitcoin)

hoi, can someone evaluate how sound this ECDSA adaptor signature is? joinmarket.me/blog/blog/schnorrless-scriptless-scripts if these ECDSA adaptor signature works, it looks like the atomic swap can be done using a scheme similar to the suggested by andytoshi-sarang (equivalent discrete logs), mixed with the game theory from h4sh3d's proposal: all game theory on bitcoin script (forcing players to act or

I agree with that caveat, though I want to add my own caveat that I don't see how it can be worse

lose), and no need for monero refund. so it should work on monero today.

zkao: I didn't invent that cross-group discrete log idea; it was andytoshi

yes, i know, u proposed

sgp_: if the coinbase-only selection distribution ends up being very different to the overall distribution, it would introduce a heuristic for coinbase true signers

and for all we know, it could be a very different distribution in that miners/pools spend immediately or something

luckily then we can approach coinbase with its own algo

which we can't do now

The non-coinbase distribution could be easily modified to simply redraw if it chooses a coinbase

if these are actually very different spend patterns, then the possibility for increased privacy is even greater

since we can handle them separately, not together

The coinbase distribution would simply be some fixed selection distribution on block order, that doesn't need to do the shuffling method we do now

sgp_: right

my gut suggests coinbase spends are quicker on average

but Bitcoin data would be great for that ofc

Right

Hopefully someone like Isthmus's group can get that data, since they have easy access to the dataset AFAIK

I still support avoiding coinbase with the stupid method of re-selecting a coinbase is chosen, though improvements can make that better. I see even this stupid model as an incremental improvement

*if a coinbase is chosen

what I'm trying to say is that the data on Bitcoin should help make the selections better, but that they are not prerequisites to switch since it can't be worse than it already is in my eyes

If there were no known distribution from Bitcoin etc., what selection for coinbase-only would you suggest?

Reselect-on-coinbase seems reasonably for non-coinbase rings, but there still would need to be a chosen selection distribution for coinbase-only rings

same as current probably? I agree that's not ideal

Well, the current one takes block density into account, and that's not relevant for coinbase-only

keeping in mind most public pools publish this data openly anyway

so frankly the coinbase rings would be susceptible to a lot of public data causing a high proportion of heuristically dead outputs

in the worst of cases I say ~90% of of the hashrate accounted for by public pools sharing coinbase data, so ringsize 11 doesn't really help with that in the best of cases

*I saw ~90%

Well, at that point you could _almost_ suggest removing the requirement for nontrivial rings in coinbase-only at all

*altogether

If the thought is that analysis could reveal true signers in a huge number of cases anyway

there's a push for pools to not share this data, but I agree that in the current case, coinbase rings should be considered to offer near-zero protection

really any coinbase spend. in the current situation, they are still heuristically dead, just spread across normal users' transactions

Hmm, we're a bit over time

yeah we can end

Let's move to ACTION ITEMS and then continue discussion

I have some unit tests update to make for the key encryption PR, and hopefully can get Arcturus code working in C++ with the timing data that I want

Any other updates, action items, etc. before we adjourn?

If not, adjourned!

Logs will be posted shortly

sgp_: if there were a compelling argument for removing rings altogether for coinbase, I could see moving to a straightforward change in the non-coinbase selection algo

But if not, I think it's important to get distribution data on coinbase from elsewhere

Otherwise any selection algorithm is a shot in the dark

we can proceed with no rings for coinbase until we have an algo, sure

FWIW I'm not saying I am convinced of this yet :)

In my assumptions I basically considered them useless before triptych or something like that anyway

you've had two years to think about it, what more do you need? :p

Data on spend patterns

The argument about public pool data is much more compelling IMO

Because it shifts the question from "how do spends of coinbase or after-coinbase differ from general outputs" to "these outputs are mostly dead anyway due to pool data"

ultimately my concerns are about normal users having smaller effective ringsizes. Not only will they not realistically spend coinbase outputs, but they definitely won't spend coinbase outputs that are likely heuristically dead

Well, getting Bitcoin (or other transparent chain) separated data would help to tell us this

but that explains why I haven't cared a ton about the coinbase selection. Why care if it won't likely matter anyway haha

well I can tell you about a year ago, 90% of the hashrate was produced by pools that showed what blocks they mined. It might be slightly different now, but this is still common

Well, let's consider the case where that's still true but we do a better selection algo

Then at _worst_, there's an effective ring size of 1

But at best, there's still signer ambiguity

sure, which is why I assumed just leaving the coinbase selection the same anyway

Moving to a bad selection algo means that an adversary with good data could heuristically unmask signers much better

using coinbase age distribution data they obtain

And we should of course assume that good adversaries have done this

And so we should do it too :)

are you talking about coinbase-only rings still? I'm confused

I'm assuming the base case of the same algo as right now, but rerolling if 1+ coinbase are selected

If coinbase are removed, then the non-coinbase selection algorithm would probably be "the current thing, but re-draw on coinbase selection"

But the coinbase-only selection distribution is currently unknown, but obtainable from other chains

An analyst who has that selection distribution could use differences between it and whatever we might choose to heuristically unmask coinbase signers

And of course they could/should/would use any pool data they find

sure, so we can use an algo for non-coinbase, but honestly most of the time it will be useless with this ringsize, even if the selection is awesome

<sgp_> well I can tell you about a year ago, 90% of the hashrate was produced by pools that showed what blocks they mined. It might be slightly different now, but this is still common <--- Would this in fact be the downside. Only the most recent coinbase output is the real one

ArticMine: we may find people spend immediately, yes. But that's not incrementally worse with coinbase-only rings

sgp_: I think it's useful to maximize the benefit from the coinbase-only selection, even for a marginal benefit in case many decoys are dead by pool data

Otherwise, a bad selection algo might be as bad as no ring at all

(heuristically, at least...)

sure, I agree with you

point is that I don't consider this a reason not to implement

And it seems straightforward to obtain this data

consider it due diligence

I see it as a further area of improvement, but that the decision can be made even without this data

(I just don't want to keep moving the goalposts)

I see what you mean; that the decision of _whether_ to do it might be independent of the knowledge of a specific distribution to use if it were implemented

The cpoinbase spend pattern of pools is very predictable

ArticMine: sure, so we should find out what it is

ArticMine: yes, we're dealing with super public, predictable behavior here

Of course, not everyone mines in pools

hence why I've been concerned we're wasting 10-20% of decoys of transactions for years now

and then you have to weigh the likelihood of unmasking those signatures with the current scheme versus any new scheme

sarang: can you be specific about which type of signatures?

So the question becomes are there enough regular non coinbase txs to make it look like a real coinbase tx is a fake

sgp_ I am turning the argument on its head

The heuristic of "the coinbase is probably not the signer in this random transaction, because I don't think coinbase are selected this way" is different from "this coinbase in this coinbase-only transaction must be the signer, because of pool data and probably also this other heuristic I built"

So if you're not a pool miner, the latter means you're unmasked almost certainly

Whereas the former seems a weaker heuristic in practice

but a heuristic nonetheless

the short answer is that private miners will have a worse selection for their coinbase outputs than they have right now. They will need to churn once

The question I have is how can one tell in the current system a real from a fake coinbase output

ArticMine: most pools publish "real ones"

for private pools, them spending a real one will be pretty well-hidden among non-coinbase outputs (like as if they had churned once with this coinbase-only switch)

I wrote about all this in my "Let's Stop Using Coinbase Outputs" post a while back

So the issue becomes the tie lag between publication and spending of the output

time

ArticMine: a good heuristic is probably to determine if known coinbase spend patterns differ significantly from non-coinbase spend patterns

(they probably do)

Namely can the unspent coinbase be picked up by another normal transaction before it is spent

maybe but I think that's not the main focus here

I see it as critical since it would obfuscate if it is real or not

It's not about who spends first... it's about the spend-age distribution

The selection algo should match this

Yes the spend age distribution of the coinbase

If it turns out they're much different, then separating them with separate algos is reasonable in most cases (but harms private miners if pool lists kill all the decoys, as has been said)

note that spend-time distribution is only one (important) part

Yes, I don't mean to imply that it's the only factor

but they would still be included in the regular transaction only with a different algo

but it is one that used to lead to good heuristics

sarang: yeah, just clarifying :)

and it's something that is straightforward to get from other chains

(provided you're willing to use them as a proxy)

users not mining is another good heuristic

s/mining/mining directly

Solo miners or miners who spend or donate hashrate as opposed to those using a pool that pays out upon mining a block

Also the mining dynamics of Bitcoin and Monero are very different

Well, getting known spend data for Monero coinbase would require using published pool data or other external data

Using another chain is a proxy at best

Or using old Monero data where decoys can be removed using chain reaction etc.

as Miller et al. did for their ground-truth on spend distribution data (which matched Bitcoin trends reasonably well)

I may be talking out of my butt here, but it seems likely Bitcoin usage stayed at close to 0 for a few years, while monero did not.

Ethereum data would show a quicker uptake, though quicker than monero. But these probably give us min/max curves.

you can see number of txs per day for all three here: bitinfocharts.com/comparison/transactions-btc-eth-xmr.html#log

I mean, any assumption that Monero patterns match any others is essentially an extrapolation, maybe backed up by early known Monero data and then extrapolated to the present

But if you were trying to build a heuristic, it seems like the thing you'd do

hi , anyone have node-cryptonote-util for xmr RandomX ?

hi , anyone have node-cryptonote-util for xmr RandomX ?