sarang: possible avenue for publication? mdpi.com/journal/cryptography/special_issues/Preserve_Enhance_Privacy

or anybody else interested for that matter ^

I'll share this later at the meeting, but I completed an analysis comparing the spend-age distributions of deducible coinbase outputs to compare to non-coinbase outputs

Here's a plot: usercontent.irccloud-cdn.com/file/Wa3Y2Zrs/cdf.png

I also included the gamma distribution from Miller et al. (dashed line)

The distributions for coinbase/non-coinbase/all are extremely close; it's tough to differentiate the lines in this CDF

is that good or bad?

I think it's a good thing for the current selection algorithm; or at least pretty neutral

If the spend-age distribution was very different for coinbase, it could indicate the need for a change to that part of output selection

This doesn't necessarily remove the need to consider coinbase outputs differently; but it is good data to know

It's also a good confirmation of the Miller et al. parameters

and is reproducible

Getting recent data from a chain like bitcoin would still be useful, since all this data is from deducible transactions, the vast majority of which are quite old at this point

and the Miller et al. paper's look at the bitcoin chain found its spend patterns trended newer than for monero

I'll share some additional plots on transaction types and deducibility over time during the meeting

Weekly research meeting begins here at 17:00 UTC (about half an hour from now)

.time

good bot

sarang, over time does the distribution get stretched out? so more recent tx will tend to have older members than historical tx?

I'm running that but don't have windowed results just yet

my thought is the analytical 'gamma distribution' might be less accurate than a numerically generated 'pure selection distribution'

While it's not directly comparable, the Miller analysis did identify a shift from newer to older on the bitcoin blockchain when looking at more recent transactions

See page 11, figure 10: maltemoeser.de/paper/monerolink.pdf

Im referring to the decoy distribution, as in a gamma selection over 10k blocks will pick more recent tx than a gamma selection over 100k blocks

Yes, but there's a pretty sharp decay

which would imply no global 'gamma distribution' curve

I get what you mean though

it can't reasonably scale forever

There have been recommendations (anecdotal and in wallet) to avoid very old spends for this reason

Or rather, to carefully note that they may stick out

yes for sure, although my immediate concern is the graph you posted :p

FWIW that data is all old... there's no ground-truth data for after the CT transition except for old spends

But yes, I'm running time windows as well to watch the difference in distribution

There's also the meta-question of diminishing returns

Using any kind of reasonable approximation to spend patterns (like the current selection distribution) is of huge value over the previous iterations, but small tweaks may be of limited marginal value compared to other possible heuristics

e.g. output merging

etc.

OK, we'll start the meeting presently!

The usual agenda: monero-project/meta #474

Logs will be posted there after the meeting

Let's start with GREETINGS

Hello!

Hi

Greetings_

hello

Hi

Righto, on to ROUNDTABLE, where anyone is welcome to share research of interest

Isthmus_: noticed you just added to the agenda; care to go first?

If Isthmus_ isn't quite ready, I can share a few things

Ah come back to me in 5

juggling something else real quick

I've done some further analysis on transaction tracing

I'll post a few plots of interest here... one sec

All transactions, by date and type: usercontent.irccloud-cdn.com/file/Pqx68K2E/all.png

I like hidden, transition, denominated

The same data, scaled: usercontent.irccloud-cdn.com/file/Cm4J3FRc/all-scaled.png

Deducible transactions, by date and type (same scale as first plot): usercontent.irccloud-cdn.com/file/rcPhKQZ4/deducible.png

Note that "deducible" means "at least input deducible" for this analysis

From the deducible transactions, I ran spend age distributions and further categorized by coinbase and non-coinbase

"at least 1 input deducible"

The CDF of this distribution: usercontent.irccloud-cdn.com/file/teVxZrIe/cdf.png

s/input deducible/1 input deducible/

thanks sgp_

That CDF plot also includes the gamma distribution used for output selection, and first examined in the Miller et al. paper

yup, for transactions with multiple inputs rings (to the observer, sarang obviously knows this)

Notably, coinbase outputs have an essentially identically spend-age distribution to non-coinbase outputs

We didn't previously know if/how they might differ

A big disclaimer is that _zero_ "hidden"-type transactions are deducible, and don't factor in to this data at all

We have _no_ hidden-type transactions to use as a direct ground-truth dataset for this

Which is a good thing!

The fraction of all transactions (non-cumulative) that have at least one deducible input: usercontent.irccloud-cdn.com/file/jiDfKje2/proportion.png

I'm astonished they are so similar tbh

One guess as to when the CT crossover happened...

lol

UkoeHB_ had asked before the meeting about if/how this distribution changes over the time period of the dataset, which is data I'm presently running and should have later today

But at the very least, this is useful since it both shows that the Miller distribution is reasonable, as well as suggests that coinbase outputs do not require any particular special treatment from a spend-age perspective

This is not to say that's the only factor in selection

but it is one factor that we previously had no data for

but it gives me initial confidence that we should separate the ring types and shouldn't make the selection of a particular different selection algorithm a showstopper

I'm also updating a writeup that includes scripts and instructions for how to run this data yourself

BTC data would obviously be nice to confirm since it's more recent

as well as supporting incremental updates, to make it straightforward to produce these plots over time in a consistent way

I strongly encourage folks to review these scripts once posted and/or run them yourself to verify my conclusions

as will the over time data UkoeHB_ suggested, in the case that Monero coinbase outputs were spent later than average in its early history, for example

Unfortunately I don't have the proper setup to run the BTC data

I will of course have the time-based Monero data

it just takes time to run the deducibility analysis

how will you graph time-based? the average number of blocks after the generation of a coinbase output before it's spent?

I'll pull some windows within the dataset and overlay them

Using the spend transaction as the target for the window

Ages are always relative to the spend transaction

This should make it straightforward to see any substantive changes

okay, I'll let you know later if I have concerns or am confused

Aside from this, the CLSAG audit by JP Aumasson and his colleague Antony Vennard is continuing

That's what I wanted to share today; were there other questions on any of this, before I pass the baton to Isthmus_ or others?

Isthmus_: ready to go?

Sure

Have at it!

Here’s our first draft of the audit framework for post-quantum security. Thoughts on mechanisms or algorithms to add?

This is the same image as posted to the agenda?

How are you defining the concern types?

TL;DR of image is:

Adversary definition: {Shor's Algorithm, Grover's algorithm, Fourier Fishing/Checking, Simon's Algorithm, Deutsch–Jozsa algorithm, Bernstein–Vazirani algorithm (Hidden Linear Function Problem), Possibly vulnerable to a future method employed by a Quantum Computer but lacking any known algorithm}

Attack surface: {Ring Signatures, RingCT, One-time "Stealth" Addresses, Pubkey derivation, Forge amounts?, Bulletproofs, RandomX proof-of-work, Block / Transaction hashing, PRNG, Fiat-Shamir Transform, Schnorr Signature, ??}

Anything jump out that we're missing?

Does the secrecy/privacy of amount commitments fall under RingCT?

"RingCT" can be interpreted broadly

or not broadly

Yea, you could label it either way

The questions are essentially 1) forgery, 2) unmasking amounts

Perhaps payment IDs could be added as well, since they're intended to be private

Oh yea!

Also: how are you defining the "concern" types on the chart?

keccak, (our particular usage of) chacha20

Oh, those "concerns" are just our research notes to each other. Not formally part of the table

Isthmus_: related to mooo's notes... are you concerning yourself with only on-chain stuff, or local stuff too?

e.g. is local wallet encryption out of scope

sarang may want to add any new crypto primitive from triptych ?

I'd certainly welcome Triptych proof analysis from that

since it's heavily DL based

^^

"all DL stuff is toast" :/

RE on-chain vs local: Hmm, I had only been considering the on-chain stuff until now, but we could also glance at local :- )

I think the local stuff depends on the threat model

My #1 priority is attack vectors that enable retroactive deanonymization

Which would mostly be on-chain stuff

If someone gets on your machine, you have bigger worries

If you have ideas for local security mechanisms to check (e.g. local encryption) feel free to let me know and I'll add them to the list

Pubkey derivation is very general and is used in other feature/mech as a primitive, or is it more like account and subaddress?

Right now it looks like the biggest fundamental issue is that an adversary leveraging Shor’s algorithm can find private keys based on public keys. This means that if you give your public address to somebody, they could create a wallet with your private key and scan your entire account history (circumventing almost all privacy)

Yeah I also wondered what that term means

sounds like diffie-hellman

The proposed recipient encrypted data scheme in the rpd branch uses chacha20 fwiw.

:D

So neither keccak nor this are local only.

excellen

s/excellen/excellent

good bot

I'm really looking forward to the results of this analysis

Primary key to private key should be breakfast for Shor's algorithm

Will also look at subaddresses, etc

Isthmus_: do you know of other projects doing this kind of in-depth work? just curious

I expect an unfortunate whirlwind of "Monero is not quantum-safe! Run for it!" from this =p

But having a solid picture of the protocol relative to a hypothetical quantum adversary will be fascinating

Haha, yea we're going to add a lot of "this also applies to Bitcoin, Zcash, and anything else in your portfolio" disclaimers

The big question for me is whether stealth addresses are secure. If there’s a way to go from stealth addresses to private keys, we’re all toast.

As opposed to only toast if you've given somebody else your address

Isthmus_: is there anything you need from this group to assist with your current work on this?

Can I ask a silly question?

sure

If I send sarang a transaction, and then erase my computer, and restore from seed, will I be able to recover your address from the on-chain transaction?

Not without external information

*PHEW*

Okay, otherwise things were going to get scary recursive real fast

There have been ideas from time to time to encode this for precisely this reason

and you can do this in extra yourself, I suppose

It would be bad from this perspective, since if I get pubkeyA, then I derive privkeyA

It would

and it's certainly a design tradeoff, regardless of quantum considerations

Cool, that's all I have for today.

Thanks Isthmus_ !

Looking forward to future updates for this project

Were there other questions for Isthmus_?

I think that the likely conclusion is that a quantum adversary would be able to steal everyone's funds, but would not be able to link payments unless they also know your address

the "privacy" of stealth addresses shouldn't be obviously compromised by QC, but other far more catastrophic things would be

I am personally interested to see how the conclusions from this project compare to the risks of other protocols

Yea, I think we're going to look closely at QRL and quantum cryptocash for inspiration to address these fundamental issues first

you can't link blockchain to unknown address but you could link known addresses

That is, does the Monero protocol do better, worse, or about the same as other protocols with similar goals

luigi1111w: AFAIK this is also what Zcash has concluded about their quantum resistance

(as a comparison)

"you can't link blockchain to unknown address but you could link known addresses" < could you elaborate slightly?

given a particular address you could determine if it matches an output

but you couldn't derive that address from the output

Ah, gotcha

When you say "matches an output" do you mean created an output or received an output

received

although by extension also created because untraceability is compromised

Yep, that makes sense and matches our preliminary thining

s/ini/inki

OK, did anyone else wish to share research of general interest to this group?

Yesterday I published an updated version of the swap

Nice!

Anything in particular to comment on it here?

I corrected the one-time VES usage, and I confirm that it is now correct ; )

noted

thanks h4sh3d[m]

I'll add more details in the paper in the next days but the protocol is done

Before moving on, are there any other general questions, or other research topics to address today?

(from anyone)

OK, on to ACTION ITEMS

I'll get my analysis toolset updated and posted, as well as finalize that time-windowed spend-age distribution data and provide it on this channel

And continue working with the CLSAG audit team

I had to set aside the output merging algorithm design, but will return to it

Anyone else have action items they care to share?

I want some confirmation that we think coinbase-only rings make sense for the CLSAG update specifically

What data will/do you use to make this assessment?

obviously I support this as-is, even without more coinbase vs non-coinbase data

noted

Is there particular data you think would help assess this, that we currently do not have?

I see it as an incremental improvement either way, even more so if we can adjust to fit a different selection algo for each

Such an algorithm likely wouldn't need to separately account for spend age, as we now know

makes implementation even easier then

All right, our hour is just about up

Are there any last questions or comments before we adjourn?

I have a minimum-age aglorithm on a whiteboard that might help with this

but haven't ported over to data queries yet

What do you mean Isthmus_?

Every single monero output has a minimum plausible age. If you follow up the transaction tree far enough, you'll always encounter coinbases.

So I can point at any output and say, "it is no younger that N hops from this coinbase"

Ah, got it

Ah I'm late for another meeting crap

g2g

Yeah, would love to see what you come up with

OK, I suppose we can adjourn

Thanks to everyone for joining in!

is that necessary for this specific change, or is that mostly for a broader analysis?

Thanks for hosting

(I see it as the latter personally)

(waiting for people to join the call)

It's part of a bigger picture. Relating to coinbase-only, I like the idea of changing blockchain tracing capabilities from "came from *this* coinbase" to "came from *a* coinbase"

Ah call starting now :- /

Isthmus_: thanks, agreed on both counts there

Isthmus if tx private keys are produced deterministically (as has been suggested by some) then for subaddress recipients you could multiply the tx pub key by the inverse of the tx private key to see the recipient's spend key. Tx private keys are randomly generated by the core software atm.

and there may be a way to extract someone's private view key from transaction data if keccak preimages can be found, since output commitments can be brute forced if the DLP is broken

and if the view key is known then the spend key is trivially found

so keccak preimage is the stealth address line-of-defense

Time-windowed spend-age CDF, all deducible outputs: usercontent.irccloud-cdn.com/file/5EccXpmE/cdf_window.png

If anyone has trouble interpreting due to the colors, let me know and I'll see what I can do

^ UkoeHB_ in particular had been curious about this data

Note that all these CDF plots take into account the change in target block time, but do not otherwise take into account block timestamps

They assume fixed constant block targets specified by the protocol

yeah kinda lines up with my expectation

wait nvm those are all pre-ringct lol, so not referring to decoys at all

These are actual spend ages for those blocks

Nothing more, nothing less

it's actually slowed down over time? lol

my intuition is so wrong

still they are all mostly similar

<cankerwort> Sarang what is the "output merging" you mentioned?

Looks like an IRCCloud error

Any missed messages recently?

xmrmatterbridge> <cankerwort> Sarang what is the "output merging" you mentioned?

thanks scoobybejesus

cankerwort: suppose that (for some reason) a single transaction directed multiple outputs to you

no prob. that was the only one

If you later generate a tranasction where these outputs are spent, each such output will be contained within a different ring in the transaction

This may also occur by chance due to the selection process, of course

So an adversary may try to use these statistics to build a heuristic

This can be generalized through the graph as well

<cankerwort> Very interesting thank you