Preprint on cross-input correlations: arxiv.org/abs/2001.04827

Reminder that the research meeting is today at 18:00 UTC (about an hour from now)

Haha I thought it was now

#footgun

negatory

Plenty to discuss?

[keybase] <surae>: Nope just clsag edits are coming to a close, and I am looking into a route that *may* but is unlikely to give a speedup

With CLSAG?

Oh, no: triptych

I need about two hours at my whiteboard but it's currently occupied by matching coding notes

roger

Basically there are some standard approaches using the sumcheck protocol that can securely offload verification costs to the prover

I want to see what I can see

Worst case, it's something to keep in mind for future protocol design post-triptych, even if it isn't applicable to triptych at all

suraeNoether: is a monkey see monkey do kinda guy

Spartan uses it, and I was considering implementing Spartan to ensure I understand how it works, and then compare triptych-style proofs within the Spartan framework compared to vanilla triptych

rehrar: I would have a lot more publications if research proceeded that simply for me.

sgp_: let's just have it now

?

rehrar: wrong chat? lol

oof. Sorry.

I....meant.....a research party!!

heh

o_O?

remember, it can take a month for drug tests to come back negative rehrar

OK, it's just about time to start the meeting

Indeed

Please take the lead sarang~

Righto

GREETINGS

hello

Hi.

Hi

hi

hi

Wow what a turnout!

Hello

hi

Let's continue with ROUNDTABLE discussion

suraeNoether: anything of research interest to share?

<ajs> ajs archived the channel.

um.... is the channel now gone on Mattermost?

not yet... Right now I'm just copy editing CL sag, working on matching code, and looking into possible speedups for triptych

?

I expect about an hour before clsag is done

I thought it was just for me

I noticed it disappeared too.

it's gone

lol

give me a sec

Hmm. Who was running it?

sorry for derailing, something to fix later

Oh

Moving along :) what about you, Sarang?

Sure

for those who want to access logs later: monerologs.net

lol

The Triptych preprint has been updated with new efficiency data and some minor typo corrections (IACR 2020/018)

It will appear on monero-site as MR 1197

The DLSAG paper is being revised for its publication in the FC 2020 proceedings

and we're working on updating the security model for later journal submission

I have a monero-site MR ready to go for the CLSAG updates (MR 1202) as soon as suraeNoether's review is complete

(and I get it updated on IACR)

I did some major overhauls on the curve libraries that I use for ed25519 and ed448 testing (for prototyping only; don't use them in production)

That included porting them to a bunch of other research projects

I also did some updates on my Lelantus code to fix some Fiat-Shamir transcript issues

And that's about it

Does anyone else have research to share?

We can also have any questions as well

Currently I have been just familiarizing myself with Monero Research

I have read quite a bit of Zero to Monero, and I also looked at the bipartite matching project: github.com/b-g-goodell/mrl-skunkwor…ks/tree/matching-buttercup/Matching

I did have some questions, but I can go through them later with surae perhaps?

Sure, now is fine with me too

It's on topic :P

Sure, go ahead

speaking of ZtM, thanks to Articmine the dynamic fee section has been greatly elaborated; anyone curious about all the justifications and derivation and analysis can find it in the latest draft; all that remains before I can publish are multisigs, bulletproofs, and proofreading (each of which will take a long time admittedly)

Ok cool, well can you briefly give a high level description of this project? From what I understand so far is that this project will be used for user analysis along with statistical models, but hearing an overview from in your words would be nice.

it's good to see ZtM getting the update :)

Gotcha okay so first think about the Monero blockchain using two columns. List all of the one-time output keys from coinbases and from other transactions on the left and list all ring signatures or if you like key images on the right-hand column

You can then go and draw edges between one time keys and ring signatures indicating ring membership. So if I publish a ring signature with ring members a b and c, my ring signature on the right would have edges connecting it to the outputs a, b, and c on the left

These are what I call red edges in my code, and I also indicate blue edges connecting ring signatures on the right with the new fresh transaction one time keys that are output from their respective transactions on the left

koe: I asked this before, but how detailed are you looking to get with bulletproofs?

I fear you may end up essentially rewriting their entire paper, with little benefit to the typical reader

So the Monero blockchain can be visualized as this two-colored bipartite graph with one-time keys on the left, ring signatures on the right, red edges indicating ring membership, and blue edges indicating output relationships

Hey @koe I owe you an email. I have some protocol notes, but have just been super swamped.

Cool cool, I

I'll try to get the email out in the next few days

I'm with you*

i am sort of busy, but wanted to throw out a question (in other words, don't let this question interrupt the current line of talk). a response anytime would be great, though

I was thinking about how people complain about outputs getting locked up for 10 blocks. Consequently one must send to themself a multi-out txn to prevent that from happening. What if we made the standard tx 2-in and 3-out (2 change)? And maybe set them to send to different accounts, so they take on independent/divergent decedent txn histories. Was curious if MRL had thoughts/impressions

I also got halfway through updating Big Bang paper, but then got distracted. Hoping to finish that this weekend or next.

The ground truth of the situation is that each ring signature has a ring member that is the true signer of the signature, so for every ring signature with a bunch of red edges leading to a bunch of one-time output keys, somebody who's trying to track transactions is trying to pick the true spender from these red edges

And this is called the matching problem in the graph theory world, sometimes also called the assignment problem, sometimes called the assigned marriage problem lol

So somebody who is trying to track transactions on the Monero blockchain is really trying to find a maximum matching on the Monero blockchain, linking signatures to true spenders

scoobybejesus: I'd rather find ways to reduce the lock time

no worries Isthmus :); sarang that's a valid concern and Im really not sure since I don't actually understand bulletproofs yet; I think if the bulletproofs paper is clear enough it will be fine to point people in that direction; I dislike the idea of leaving things open ended, but maybe it's just a useless hangup ^.^

The signatures themselves give nothing away about which edge is supposed to be the true spender, so without any additional information the attacker just has to guess, and so every possible maximum matching is equivalently good in this world

Ah okay, I see. It seemed as if you were trying to find out if there was a way to trace back transactions.

I am kinda

So my graph theory python code allows you to build a graph, and then find maximum matchings, and if you wait the edges, it'll find the heaviest weight matching so that somebody using extra metadata can do better than just guessing at random

Weight*

How do you assign weights?

Right so that's outside of the scope of graph theory and in the scope of my simulations...

Ah. Are they probabilities?

Is this where statistical models come into play/

Yep. The way that I'm trying to do this is I'm simulating an economy between Alice, Eve and exchange with KYC information, and Bob representing all background players in the Monero economy. I'm even telling Eve the information about the Markov chain from the beginning, which models eves perfect ability to learn your habits.

So this Eve is able to wait the graph using some null hypothesis about user behavior

once she does this, even though she doesn't know the ground truth reality of the blockchain, she can find a maximum likelihood estimate which corresponds to a maximum weight matching

s/wait/weight/ ?

Weight* sorry I'm on voice to text

So the simulator simulates an economy, strips information out of the graph that Eve doesn't know, hands the blockchain to Eve, Eve weights the graph and compute some maximum likelihood estimate, and this maximum likelihood estimate is compared to the simulators ground truth

When things are working I get preliminary data that suggests that Eve is really really bad at this game Even though she's given perfect information about Alice's habits

But that's all preliminary because my code is only intermittently working and I am currently in the midst of refactoring it to be simpler.

That's encouraging.

Quite interesting surae. I understood about half of it before, but given you're description I see the goal of the project now.

In a way you are trying to see: given the current information can we figure who sent the transaction given previous user habits.

[keybase] <surae>: These results are encouraging, but I want to emphasize that these are all preliminary results and are not at all trustworthy yet

[keybase] <surae>: Atoc in particular I want to assess the goodness of these approaches that everybody has been using for linkability... I get the suspicion that the false positive rates are unacceptably high, but since previous papers like Monero link never properly constructed their experiments, they were never able to tease that out

Have others ran linkability tests on Monero previously?

[keybase] <surae>: Yes, monerolink was one of the first. that paper is actually the inspiration for using simulations in order to tease out various performance rates

Good to know. I will take a look at that.

[keybase] <surae>: I have a lot of respect for the people who contributed to the MoneroLink paper, and it made Monero a lot better despite the fact that it was perceived by our community as very adversarial... But, the paper did suffer from a couple of bad scientific design issues that made some of their claims more sensational than supported by the evidence

Ah I see, was MoneroLink done by the Monero community or third-party?

[keybase] <surae>: The fact that it was written by people who had a financial interest in succeeding compared to Monero was viewed as very suspicious by a lot of folks.

suraeNoether have you collected a list of tracability analysis papers? for example sarang mentioned a preprint earlier; or maybe Isthmus has that list

[keybase] <surae>: Andrew Miller from Zcash and a couple of other folks who were involved with Zcash were authors

[keybase] <surae>: Actually you know, Sarang may have a better list than I would... A paper came out last year describing a game not dissimilar from my graph theory game and they named it after sun tzu. But I can be more helpful in finding background papers. Basically any papers on the traceability of anonymous communication networks has some degree of applicability to the Monero blockchain

[keybase] <surae>: "perfect matching disclosure attacks" is a general paper that was critical in the construction of the matching stuff

I see I see. So I see a couple of todos listed (unity tests and another). What are some important priorities for this project? I feel I can contribute to this project as a start.

Just a little background about myself: I'm an academic researcher in theoretical computer science (neural algorithms).

[keybase] <surae>: Let's talk about that after the meeting

sure

<Isthmus> Dang, I got bumped off IRC

<Isthmus> Can't log back in

[keybase] <surae>: speaking of the meeting, isthmus tells me that he has lost access to IRC... And I also happened to lose access to IRC and I'm just using the keybase bridge

<Isthmus> *IRCcloud

[keybase] <surae>: it looks to me like IRC cloud has gone down which means the vast majority of the people in this room are probably not here anymore

<Isthmus> @atoc nice to meet you, excited to contribute

<Isthmus> *to collaborate

<Isthmus> Sorry, I'm in a meatspace meeting too

[keybase] <surae>: So we'll give it a few more minutes and if I receive cloud doesn't come back or if nobody else speaks up, I say we adjourn the meeting

[keybase] <surae>: If irccloud*

<Isthmus> So I just realized that we aren't fully utilizing the archival network data. But I'll wait for our IRCcloud comrades to return

<sgp_> yes, irccloud seems to be down for everyone

[keybase] <surae>: I had a question for isthmus about the archival network and lock times

<Isthmus> sup

[keybase] <surae>: I want to know the distribution of fork lengths observed so far, and I also want to know the distribution of forklengths experienced by a new node syncing

isthmus nice to meet you as well.

hmm okay and sorry what do you mean fork lengths?

[keybase] <surae>: As in Nakamura consensus resolving a fork

[keybase] <surae>: Nakamoto

[keybase] <surae>: WTF that was autocorrect too not voice to text

It should be correcting the other way.

I see, alright I will begin looking into this.

[keybase] <surae>: Isthmus actually specifically I want an estimate of the parameter r under the null hypothesis that fork lengths are negbinom(p, r)

[keybase] <surae>: I think lock time has to be proportional to r to protect most transactions from most rollbacks

[keybase] <surae>: Okay since irccloud is now fartcloud, I say this meeting is adjourned.

good meeting! happy day to yall

[keybase] <surae>: Good seeing you around koe

<sgp_> thanks

Thanks. Good meeting.

<sgp_> surae: meeting in #monero-konferenco starts shortly if you can come

[keybase] <surae>: Omw

[keybase] <surae>: Atoc the code you are looking at is suffering at least one big problem. Eve is not getting or not using all her kyc info appropriately when she weights and matches.

[keybase] <surae>: And I believe someone of my unit tests for the simulator are failing

Hmm I see.

I will try looking at the unit tests again and see if I can get Eve to use all her info. What you mean not using it appropriately though?

I may see it in the code, but incase I don't lol.

[keybase] <surae>: The simulator writes the ledger to file correctly and in human readable format, and Eve also outputs her guesses in human readable format. But Eve is an idiot, forgetting her own transactions for example and assuming them to Alice or Bob

[keybase] <surae>: There are also other stupid problems

[keybase] <surae>: Since it's human readable, it's a little like solving a mystery. "Hmm now why did Eve think *that?*

I see. Well should I try fixing these first or get the distribution of fork lengths?

Also, does isthmus work on this project too? Or is it mainly you?

[keybase] <surae>: Oh I think the fork lengths thing Isthmus can most easily help with

[keybase] <surae>: That's separate

Ah I see.

[keybase] <surae>: Not directly related to matching

[keybase] <surae>: I'm primary on matching

Oh alright. Well then I can look into the other issues you mention and contribute further if there is other work left.

[keybase] <surae>: My code is unnecessarily complicated, and I am in the midst of refactoring it into something much simpler... But that is actually probably an equivalently large task compared to debugging the current code base... So there's a decent chance that you actually beat me because the vast majority of the infrastructure is already written for your end of the project

[keybase] <surae>: Look at me saying you're into the project like you've been sucked in already

All good lol. I would like to be sucked into a project. I actually talked with Sarang first and he mentioned a couple other projects

but this one seemed like it would best suit me.

as I feel I can contribute a fair amount to it. I can also give hints on making it simpler once I go through it.

[keybase] <surae>: Yeah, endogenic and I have had discussions about it already... My current refactoring is basically the current code base, but with the functions broken down into smaller and smaller fundamental pieces that are easier to individually test

[keybase] <surae>: I may end up pushing to a new branch named plutonium later today. Could be that more hands during refactoring makes less work. Let me know how much of my code is more like spaghetti to you than code

[keybase] <surae>: The simplification is small enough to fit on my whiteboard front and back which I alluded to earlier

Will do. I will take a look at it later today and get you feedback.

[keybase] <surae>: That sort of prompts me to just push what I have... Give me a few hours though cuz I need to finish clsag

Sure no problem

btw you can reach me at: at0c⊙pc (if I'm not here)

note: the 0 is a zero not 'o'

[keybase] <surae>: gotcha

[keybase] <surae>: i'm surae.noether⊙pc or surae⊙go

what voice to text are you using?