13404422 ring signatures generated by version 2 transactions

Whoops, wrong channel

Well, you can probably guess who I meant to send that to

Avg ~1 tx every 20secs

One ring sig*

Reminder that weekly research meeting is today @ 18:00 UTC (about 3 hours from now)

why do i keep thinking these meetings are 17:00 UTC?

They used to be 17:00

.time

.dementia

too bad that doesn't work here. works in #monero-community

so, good news everyone: i now have two full days of sleep, with a calorie defecit smaller than 500 calories, for the first time since xmas. finally freaking feeling better

:D

suraeNoether: that's great news!

How do we get the timebot here?

back in my day we wound our watches

Now we have robots to do that

Anybody have anything they want to specifically add to today's agenda?

nioc: i'm still winding my watch :)

my question is, what is the status of the matching project and how will is be used going forward to help select an appropriate ringsize?

Curious as well

Great question for the meeting, or for right now

+1

As I stated before, I don't think there are strong reasons to increase ringsize with clsag unless there's a justification other than "larger is better" or "it could theoretically help with churning"

I agree

Some forms of analysis are easily mitigated by small increases, and those have been done already

this was maybe fine a few years ago when the ringsize was MUCH smaller and this was the best analysis we had, and when we were dealing with more basic attacks

sarang: beat me to it :)

Other more targeted forms of analysis would be difficult to mitigate without very large increases that are not feasible right now without bloat

easy attacks are effectively covered

But marginal increases at the current size seem unnecessary without a good rationale, likely related to churn as sgp_ says

We'll start our meeting in just a few minutes

my hope is that the matching results come out in time to make a good decision regarding ringsize in the clsag update

The usual agenda, with an addition from Isthmus: monero-project/meta #434

^^ agreed

plus this project has been ongoing for what, a year or two now?

OK, let's get started

Logs from this meeting will be posted to the agenda issue shortly after the meeting

First, GREETINGS

hello

hello

good mroning

hiya

On to ROUNDTABLE, where anyone is free to share interesting research

I'll go first, since I have a small assortment of things

I worked up code and examples for doing hidden data storage within Bulletproofs and Triptych, suitable only for the prover

I,m kinda here, but on a conference call

Several ongoing projects/issues have been moved to monero-project/research-lab issues for comment and discussion

The CLSAG code on my monero fork (clsag-plumbing branch) has been cleaned up; thanks to UkoeHB_ for helpful suggestions and comments

It includes, among other things, hash function domain separation that we hope to roll out elsewhere for a more robust overall codebase

There is also CLSAG Python sample code showing how to do signer index extraction in a clever way, which I assume UkoeHB_ may wish to discuss when he shares

I've written up material for ZtM about transaction proofs/assertions

And have worked up some new C++ code that updates transaction in/out proofs to have correct Schnorr challenges

(still need to write tests for this)

That's my update; any particular questions before the baton is passed?

quick question: iirc you had done work on encrypted timelocks

yes

i've been chatting with both isthmus and TheCharlatan about them

do you have any notes prepared any place for later reading?

On what in particular?

alternatively: can we schedule a discussion in this room that will end up in the logs for later this week?

Sure

Let's table for now, and address at the end

if we implement them regardless of if we are using mlsag, clsag, or triptych, there's going to be a cost. i want to see how it's all going to fit into future monero dev

word, word, i can go next

OK, go ahead suraeNoether

last week i spent a lot of time on CLSAG and linkable ring signatures security definitions

there are a lot of definitions out there and they don't all relate to each other in a clean taxonomy, and it wasn't clear which ones we needed to use, and so on

so i started writing this rather large technical note summarizing all this with the intention of writing a second paper about it, but sarang and i have decided to merge the two into a new draft

the reason is that even definitions of unforgeability miss absolutely critical stuff becuase they are taken from "ring signatures" and mapped over to "linkable ring signatures" wholesale without regard for linking properties

so now the paper will be proposing a new definition of unforgeability specifically for linkable ring signatures that subsumes more than one security definition, and this is going to set the standard for a few years on how unforgeability is considered for all applications of linkable ring signatures.

this is good news(tm) for MRL

sweet

congrats :)

thanks :D

It makes the preprint all the more valuable

In addition to that, I have been preparing my talk for the Blockchain Tech Symposium at the Fields Institute in two weeks, and debugging my matching code.

i'm extremely grateful to the peer reviewer who "gently" pointed us towards the backes' paper actually

Having both improvements to security models _and_ a new construction seems to be the gold standard these days

they did us more of a favor than maybe they realized

my work for the week will include finishing up this new draft of CLSAG, and to begin large-scale data collection on matching

Thanks suraeNoether

Any questions for suraeNoether?

if you want more CLSAG work, it's possible to increase the number of linkable keys up to the total number of pub keys considered :p

Sure, but that's not useful for our particular application

which is why we didn't consider it

I believe there was an earlier question from nioc about matching

for suraeNoether

12:46 <nioc> my question is, what is the status of the matching project and how will is be used going forward to help select an appropriate ringsize?

^ was the question

ah, great question: the matching project is *what appears to be* a single-line bug away from correctly generating simulated ledgers. it already appears to generate correct confusion matrices; once this bug is cleared up, it's a matter of executing a big block of code for a large period of time to get all the sample data, and then analyzing the data that's dumped to file.

so... if this bug, just like all the others, is a hydra, then I don't have a good answer, but i suspect i've narrowed down the problems to the source

Is the purpose of the matching project to produce the ledgers?

there are several purposes, but here's the main thing

we want to estimate how well an adversary can do at finding the "real" history of a monero ledger, given some hints (like it's a KYC exchange)

i have a method of computing a maximum likelihood estimate of the real history given some obscured ledger, and all that code works

and i have a method of taking an estimate and comparing it to the ground truth, producing a confusion matrix, and all that code works

i have a simulator that generates simulated ledgers, and the vast majority of that simulator is working just fine, too

the origin of the project came from the idea of developing a game-theoretic description of traceability on the monero ledger: you hand me an obscured ledger and some hints, I hand back to you my best guess, and then success is judged by you comparing the best guess to the ground truth you kept from me the whole time

so, the hope is: graph performance against ring size, and see if getting larger than 11 is a waste of space/time or not

in the meantime, we hope to also get good data for zcash-style ledgers, so that we can actually rigorously compare the two ledgers against each other, instead of tweeting at each other about fragility

but that last bit is farrrrr down the line

Oh yea, I just remembered that ginger and I talked about generating synthetic blockchains forever ago insight-decentralized-consensus-lab/CryptoNote-Blockchain-GAN #1

OK, any follow-up questions on this?

unfortunately, i've not worked on matching since mid-January because CLSAG's security models are critically important

and CLSAG needs to get out the door

Anything else to share, suraeNoether?

Does anyone else wish to share relevant or interesting research?

I'm taking a break from blockchain logs analysis to do some chat log analysis, analyzing recurring logical fallacies in this space

Nope

isthmus lol really?

?

Yeah, actually doing a formal analysis

Isthmus: if you are, i have a friend to hook you up with at the university of exeter

This channel in particular?

Or more broadly in cryptography?

Somewhat broady

There's 7 common ones that show up in -lab

go on...

But they break down into combinations of red herrings and something that is *similar* to the slippery slope argument, but not quite the same and I'm still nailing down its technical logical structure

dude, please elaborate

Like when we're debating fixing a tractable privacy leak, and somebody points out that there are other privacy leaks

:O

ah yeah

or comparing everything to 50% attack costs

Another one is the hashrate code control fallacy

?

Confusing a 51% attack on longest chain with a 51% attack on the code

This came up a few weeks ago actually

aaaah

i smell some medium articles

Like why should we bother working on the protocol and code, when one day, somebody might run their own version on a bunch of their own miners

Based on what you've analyzed so far, any particular recommendations to avoid such flaws in discussion/thinking?

That one can be disproven by contradiction

If 50% of BTC hashrate moved to BCH, does that make BCH the official bitcoin?

"why should we patch little leaks in info here and there" styled privacy nihilism/despair

Oh shit, I gotta be in a meatspace meeting

ciao!

-__-

Very interesting stuff

Erm, not by contradiction. I mean by example demonstrating absurdity

We have plenty of time left... does anyone else wish to share anything?

lol 😆

lol "i'm going to use machine learning to watch all of your conversations and find out who repeats fallacies most zealously BAIII GOTTA GO GRAB A FREE SLIZE OF 'ZZA FROM THE CORPORATE OVERLORDS" amiright

Here's mine. Worked on write-ups of different ideas -> now Research repo Issues, with good feedback from sarang improving viewspent approach. TxTangle (aka my monero coinjoin protocol) is mostly done and just needs questions answered about network-layer anonymity. Current draft of ZtM2 is here pdf-archive.com/2020/02/05/zerotomo…0-23/zerotomoneromaster-v1-0-23.pdf and current

‘koe’s Ideas’ is here pdf-archive.com/2020/02/05/moneroid…skoe020520/moneroideaskoe020520.pdf

Yeah, the original view/spent idea was broken, but there's a better approach

It ties in with the CLSAG index extraction that I mentioned earlier

If the signer generates all non-signing scalars via a PRNG `s_i := H(seed,i)` (with appropropriate seed data), then it can be asserted privately what the signing index is

It removes the need to add anything to the chain, and hence is good for indistinguishability

I dig it, provided the UX is sufficient for reasonable use cases

yeah if view key can regenerate those scalars, it can know when an output has been spent with certainty

of course, it only works if tx author generates scalars like that

The problem is still that it's opt-in, so even an accidental use of a non-participating wallet ruins the account balance computation for good

So you'd have to be super-clear about presenting that to the user

hmm

Of course, a wallet could be doing that right now for all we know

it's non-consensus and can't be detected if done properly anyway

it does leave open questions about data stored by nodes, since signature scalars are pruned; perhaps only full nodes, or view-spent enabled nodes can be used

IMO that's a completely reasonable trade-off

sounds reasonable to me too

it also may greatly increase data transmitted to view-only wallets by remote nodes

Bloating the network for optional functionality benefitting only a single user seems unnecessary

But this approach means you can run a full node (good for the network) and have the functionality for your wallets safely

UkoeHB_: I think that's a good thing to point out but probably isn't a showstopper

might need to receive a gigabyte of data to read through a year's worth of tx

hmmm

i'm a little worried about this in the following sense

I still think that is okay for view-only wallets

you are selecting the non-signing scalars deterministically from a PRNG

anyone using them for critical stuff, or viewing multiple wallets, should run their own node

one thing we all know about schnorr signatures is that if nonces are selected deterministically, it's possible to extract the private keys

at least, under certain constraints

suraeNoether: yes, which is why seed selection is very important

so my question is

UkoeHB_ and I discussed this a bit already earlier

if the seed is chosen from a high entropy distribution and kept secret, it's computationally hard to detect that these are computed deterministically

i would prefer a method that is more than computationally hard

Presumably the seed is a combination of the view secret key, the index, the key image, etc.

suraeNoether: how would that even work?

Data extraction requires that only the designated parties be able to construct the "expected" output value

pfeh, we use PRNGs because statistical RNGs don't really exist :P so ... it wouldn't

Well, right now we operate on the assumption that the user has access to something behaving as an RNG

this moves to an honest-to-goodness PRNG

(and has to)

You can't do data extraction with a true RNG AFAICT

that... is... true.

Anyway, this is an interesting topic that could be useful for a future release

but has subtle aspects to seed selection and UX that need further review

Let's move on, for the sake of time

Any other topics you wish to share, UkoeHB_?

well, I hope people can leave feedback on the repo issues

Yes, please do

Much easier than only doing IRC comments =p

sorted TLV is probably most important for next hardfork

TBH that's probably going to be better for -dev discussion

More of an engineering question than a math question :)

true

I'd bring it up at a dev meeting, or just in -dev whenever

Get a sense of the work involved

ok

I know people have brought up tx_extra parsing before, and it's a hot topic

Does anyone else wish to discuss other research topics?

ah, CLSAG section was added to ZtM2 for anyone curious

excellent

uh i saw vtnerd's push on dandelion++

Yes

Most excellent

It's on my list to review later this week

Speaking of which

Let's briefly move to ACTION ITEMS to respect everyone's time

I'll be reviewing the D++ PR, working through some additional transaction assertion/proof stuff, updating sublinear tx protocol MPCs, and writing up examples of RCT3 hidden data storage

yes. Mine: Finish CLSAG, start collecting matching data. Also, of primary importance: provide updates twice or three times a day in here until both of these are finished.

As well as getting tests written for the new tx in/out proofs

i'll be reviewing the D++ pr also once those are both off my plate

Yes, looking forward to the CLSAG stuff (will review when ready)

Anyone else have action items planned for the week?

To do: focus on multisig all week, hopefully finish txtangle (need a network anonymity expert for advice, any takers?)

The most knowledgeable person is probably vtnerd

I hear if you say his name 3 times, he gets 3 separate notifications...

=p

Any last-minute items, questions, etc. before we formally wrap up?

(I'm happy to discuss timelocks after we adjourn)

Going once...

twice...

Adjourned! Thanks to everyone for attending; logs will be posted shortly on the agenda issue

Feel free to continue discussions, of course

suraeNoether: timelocks

What do you wish to know

well, first question: is there a github issue or something describing any proposed methods of implementing them?

second question assuming no: is there a document anywhere describing any proposed method of implementing them?

I have some example code showing how they operate

What details do you want?

If you want timing information, that's separate (depends on performance timing)

and that doesn't address the engineering work required to integrate the timelock range proofs (used for inputs) with the existing bulletproofs (used for outputs)

It seems pretty nontrivial to do

Issue #65 I did a short explanation of how it works

uh #65?

UkoeHB_ means monero-project/research-lab #65

I opened an issue describing the basic idea

oh!

i was in monero-project/monero :P

ok, this was *all* i wanted before i had more questions

thank you

The gist: requires each input to have an additional auxiliary commitment added; still a cleartext auxiliary time included; CLSAG verification complexity increases; range proofs basically unaffected if done properly

First-order estimate is that the MLSAG-CLSAG verification benefits go away with CLSAG-based timelocks

Although: I should note that range proofs currently have a cap on the number of commitments included... with timelocks, this cap would incorporate both input timelock commitments _and_ output value commitments

I mean unaffected since we already pad to the next power of 2 for size and time purposes

Increasing the limit would of course change this

*nod*

So there are still size benefits from the MLSAG-CLSAG transition, but the time benefits disappear

May be slower overall by a bit... there's always variance in the test numbers

Seemed like a wash during my initial testing

sarang: i have a weird notion of unframeability, or non-slanderability i wanna run by ou

but it requires out of the box thinking

if you are aroudn

I am around

ok so

firstly, unforgeability is a version of soundness, which is a matter of the existence of a witness extraction algorithm. when we prove unforgeability, we prove such an extractor exists and use it to violate a hardness assumption

secondly, if A is an algo that can produce a valid signature, then it can be rewound by the extractor to get the witness, so if A produces some (m, R, \sigma), we can wrap it without harming its advantage and output instead ((m, R, \sigma), w) for a witness w

follow me so far?

Ideally

this is an amped up definition of linkability. I suspect it's distinct both from Backes' and the older Tsang-style definitions, also

but i haven't proven proper containment of the securiyt models yet.

actually: this is a very strong definition of linkability that says two signatures will link if and only if their witnesses match

which implies Backes' definition for sure

hmm, yeah, actually i think this definition also implies tsang's definition

suggesting this is stronger than those

i... suspect htere's a problem with my thinking, though, other htan the fact that it assumes the scheme is unforgeable to start.

How do you frame this in a challenger-player scenario?

The challenger can't naively extract the witness itself

Back by popular demand

^@koe

@UkoeHB_

Wow, we've had some transactions with a lot of inputs... 1187, 1086, 1067, ...

Ah is this the chain analysis I had asked for?

sarang: same way backes' linkability defines it as player-challenger

suraeNoether: this is a good conceptual example of linking unforgeability to (special) soundness by Groth and Kohlweiss: link.springer.com/content/pdf/10.1007/978-3-662-46803-6_9.pdf

oooh

taking a lunch break, and then sarang, i'm at the point where i'm copy-pasting proofs over... so i think i'll be done later today and passing a new draft along to you, but i'll do an update in a bit

Roger

Want to see 800 obviously spent outputs?

Our ring signatures and decoy selection algorithm are simply statistically incompatible with spending a large number of temporally-correlated outputs in a single transaction

I can automate this too

Yup

Collapse the ring member ages of all 1000 ring into a histogram, find cluster centroids, flag every output within 1 stddev as spent. Loop this over all of the 500+ input transactions, and mark thousands and thousands of outputs as known to be spent.

Interesting, it seems like the amount of pool payouts is less than 1% of all tx

i haven't coded it up yet, but it could take a single pass through our database and identify >10,000 spends

Isthmus: *highly suspected* to be spent

Known for a long time :/

Tricky to avoid without sufficient cluster/bin selection AFAICT

Which in turn is tricky without larger overall anon set sizes

And of course revealing 10,000 spends also reveals 50,000 decoys

I'm a statistician, not a court of law. For the purposes of commercial chain-analysis those are considered spent.

:- P

Sure, and I don't know a good way to avoid this beyond clustering and/or wallet warnings

All high input count inputs are pre-ringct

Or, alternatively, such a large-input transaction followed by a properly-executed self-spend

Since max tx size limit

to return the single output into the "recent pool"

" Or, alternatively, such a large-input transaction followed by a properly-executed self-spend" < protects the sender, but laces the chain with weak decoys

An on-the-fly analysis followed by a churn wallet warning might useful as a stopgap

Ah right, can you flag every tx with >1 input if it used RCTTypeFull?

Isthmus: right, but in general it's not possible to fully avoid

Or add a count column to that data set with #tx with rcttypefull

Yea it is, we just need to cap the number of inputs to force multiple transactions. A little bit of computational and fee overhead, but allowing insanely large numbers of inputs basically defeats the point of ring signatures

I'm not saying to cap it at 5

But it needs to be not 1000

And another flag if the first referenced input offset is pre-ringct (implies all inputs are pre-ringct)

Ah interesting

I think rcttypefull could get up to around 600 inputs, maybe more with smaller ring sizes

Pre-bulletproofs

Anyways, good lunch break but I gotta get back to the work

gg

Isthmus: the sharp dropoff for decoy selections means that the temporal effects may be reduced somewhat

but it'd be interesting to see to what extent this is the case

I'm guessing all those inputs from the same block are denominated pre-ringct outputs being swept

I still very much advocate for eventually moving to a bin/cluster selection approach, but I also think it only has maximal benefit when used with a large overall ring size

Isthmus multiple transactions doesn't work either, since with a little extra effort you can compare the input rings of adjacent tx for clusters

Well helps a little, and moreso as the time spread rises, but not a huge improvement

Larger clustered bins shared across all inputs seems to mitigate this

Yeah

True, in that sense transactions are kind of arbitrary boundaries around branches of the tree, but it's still the same tree

Even if you gain knowledge of the bin used across inputs, that doesn't necessarily identify all spends within the bin

Very mature graph analysis erases the boundaries from both blocks and transactions, to focus on the pure topology

and the presence of identical bins on all txns means you can longer use only cross-input techniques to guarantee a single set of spent inputs

Isthmus and UkoeHB_: suppose we can do ringsize 128 or 512

How would you structure selection?

I've thought a lot about this

but surely there are factors at play that I am missing :)

For starters, inputs should share the same anon set

(this is generally also very efficient)

Binning is also a good idea (Miller et al. show how to do deterministic shuffled binning to avoid miner shenanigans)

I think maintaining the gamma distribution as foundation is important, although I have some thoughts on how to make sure it ages decently

What else?

Yes, I assume the bin selection follows a reasonable spend distribution

with the rule that when you select a bin, the ring includes that entire bin

I feel that reveals too much about the spend timing

I need to clear my mind and think on that for a while. There are 3 concrete research strategies that I believe should inform selection

UkoeHB_: bear in mind one of the key reasons the Miller paper advocated binning (at least in the single-input simplified case) was to reduce the adversarial advantage from heuristically identifying the spent bin because of a bad distribution choice

At that point, the signer ambiguity is still at the level of the bin size

(1) What does the spend time distribution look like for other multiple other cryptocurrencies like BTC and transparent Zcash. Why multiple? I don't just want to see the distribution for one, I want to understand how representative it is and how much it varies across different coins

as opposed to a single output

(2) use the egregious decoy transactions (exhibit 1: uniform selection, exhibit 2: cached decoys, exhibit 3: links from by MonKon talk) to identify real spend times in Monero

There's enough obviously spent outputs (from a statistician's perspective) that we should be able to generate a pretty large data set

Isthmus: are you familiar with the data presented in the Miller paper?

Oh yea, I read it like once every 6 months

haha ok

Now, we don't know for sure whether these sore thumbs representative of general activity

I was gonna say, 1+2 is basically "do Miller again"

but with more sources

Yea, I just have more heuristics with more teeth :- )

We've advanced chain analysis significantly since then

Because I wonder if, even armed with this extra data, there are good general rules beyond "build shuffled bins, select them using an estimated spend distribution, and that's it"

So the last strategy (3) is to take the transactions that appear to have the correct decoy algorithm matching core wallet implementation (assessed by offset-corrected median ring member age) and then subtract those from the observed distribution

(and reuse all bins across inputs)

This won't tell us anything about a *particular* ring, but across 13404422 ring signatures, the difference should paint a pretty accurate picture of the real Monero spend time distribution

OK, so assume you have that distribution in hand

What do you want to pull from it?

Our decoy selection algorithm should mimic the ground truth spend time

Sure, but we already know that doesn't play well across inputs

So now we also have the hypothetical advantage of 128-512 rings

Also assume that reusing inputs/decoys across rings is more efficient to verify (it is)

Oh I'm tacking theory for single ring before cross-ring stuff xD

I guess that's bad of me

Anyways, gotta bounce back to work stuff, will meditate on large rings laater

roger

Earlier I figured out how to hide the true distribution inside another distribution, but that only works if the true distribution is unknown.

only hides if the true dist is unknown to analyst*

We should assume a reasonably-accurate distribution is known (at least its general form, if not parameters)

The parameters we use in practice are from Miller, assumed to be "nothing-up-my-sleeve" values (or something reasonably so)

i still think it'd be worth it to have those values updated every 6 months or so

the market today is not the market in 2017, and the velocity of money largely determines spendtime...

one of the stupid things about spendtime is that it's sensitive to economic conditions

a depression is when spendtimes are long, and a bubble occurs when spendtimes get shorter; picking a single distribution to capture both regimes is not a smart way around the problem

but ya gotta pick *some* spendtime

The methods should also be consistent and reproducible

All NUMS values