This is a really insightful thread about Halo 2: forum.zcashcommunity.com/t/announcing-halo-2/37215

I had wondered about the nature of the recursion, and if/how it could apply to actual Zcash operations

Eran and Ian apparently share these questions, which don't appear to be answered by ECC here

So Monero does not use ECC either.

-___-

Anyway, it does sound like the press release is... a press release

and that the ways that Halo 2 could (if at all) be functional for practical Zcash operations has not been shown

nor described

s/operations has/operations have/

good bot

Another good lesson than press releases are often worth the air into which they are uttered

That being said, Halo-style recursion is very interesting, and I hope they work out actual details on this

sgp_ it takes random 7-day windows starting Jul 2020 onwards,then picks n poisoned outputs randomly from that window

and each pair or set of n poisoned outputs is from a different 7-day window

and btw 43% of txs since Jul 2020 had >=2 outputs, so there are no lack of merge transactions generally

i could the miner txs as being txs for that stat. 5.8% are miner txs.

s/could/count

also i meant to say 43% txs with exactly 2 outputs

51% have >=2 outputs

question - the issue with combining multiple outputs in the same transaction, is that it proves you have control over both/all of them? But this is somewhat probabalistic, as each are a part of an 11-member ring? So with 2 it could be random chance, but with say combining 100 small exchange withdrawals or miner payouts, it gets pretty obvious?

Basically, yes

Also it is kind of different if the observer knows which outputs belong to the user

If two poisoned outputs are combined, the chance of the actual owner combining them is higher

In comparison to, say, two random outputs appearing in a transaction (and the observer not knowing which belong to the user)

e.g. 100 inputs to a TX, and all 100 rings contain at least one output that can be connected to say a mining pool?

and that would make for a strong probabilistic flagging of all those 100 outputs as having been used, and reduce the anonymity of other later transactions using the same ring members ?

If you know an output is provably spent, it may reduce privacy of other's using that output, yes

Well, and if you have a heuristic, you can make some statistical inferences too

Weekly research meeting starts here at 17:00 UTC (about 90 minutes from now)

.time

good bot

First ROUGH DRAFT of vulnerability analysis with respect to quantum algorithms: github.com/monero-project/meta/file…63665/pqMonero_technical_draft1.pdf

a lot more has been written but we are editing it like mad rn

OK, let's start our research meeting

The usual agenda: monero-project/meta #502

Logs posted there after the meeting

First, greetings!

Hello

Hi

hihi

if we need eye protection for this meeting, i'm wearing open toed shoes so... uh...

OK, let's move to roundtable, where anyone is welcome to share research topics of interest

Isthmus: you had posted a paper draft on the agenda issue

Yep, just a rough draft of the audit portion of our research. It's a bit long to digest on the fly, but if y'all have any notes to share over the next few days we'd greatly appreciate it

This is great!

You said it's still being edited... would an edited version be posted separately, to make it easier for corrections?

Hm?

Or should proofreading/review wait until edits are finished?

Ohhhh

Yea, for the portions that I posted, please tear them apart

The parts that we're still editing were omitted from the draft shared above

Having edits criss-cross across versions and ongoing edits might get confusing

ok

Hi

I look forward to reading this Isthmus and suraeNoether

Any questions for Isthmus or suraeNoether?

Here is a link with EDIT access to the draft: overleaf.com/9835162385prbmyfckknyc

For anybody who finds it more convenient to drop notes in LaTeX

Are you comfortable having that link posted in the agenda issue logs?

This is a fork of the paper, so it's ok to futz around

oh ok

Yep, I'd just ask that people leave notes on what they edit, either as a comment with `%` or using the \anote{} feature which is a custom command to drop in little notes

You can also leave Overleaf comments on the side too

Oh yea, that'd probably be even better

Those have threading and resolution features

Thanks for the update Isthmus and suraeNoether!

I'll share a few things

overleaf appears to have recently bunked up their comments and review functionality a bit, and it's become temperamental for me

Oh boo, that sucks

heh /aside

So the Triptych preprint was accepted to the ESORICS CBT workshop recently

It'll be included in their proceedings, and I will also make a presentation on it later this month

I had to do a recording of this in the event of technical difficulties, so thanks to sgp_ for helping me work out the details on that

The preprint has been updated on IACR for corrections, the proceedings version has been prepared separately, the slides for the presentation are posted on GitHub, and I have the recording done as well

sgp_ and I also interviewed CipherTrace's CEO, Dave Jevans, about a press release they made that received a fair amount of media attention

That has occupied more of my time than I had expected

and finally, I've been working with grydz to help them get the Ledger CLSAG firmware integration working

Huge thanks to grydz for their hard work on this

Any questions or comments for me on these topics?

Thanks for pouring time & effort into the unexpected CipherTrace happenings

Kind of a big fire to disrupt your workflow out of nowhere

That interview was excellent

Appreciate the context switching and great handling of that situation

^ sgp too

Yeah, thanks to sgp_ for setting up that interview on such short notice

I think it was very helpful, even if there was little in the way of specific information

hi.. Sarang was solid and taking no shit.

It's worth notice that Dave _did_ confirm that his company makes their own transactions on chain as part of their analysis efforts

I regret not following up on this at the time, but did submit questions on this to him afterward in writing

I suggest going over it multiple time to get all the nuances. There is a lot of very valuable information there, that I really want to analyze

Here is a link to the interview: youtube.com/watch?v=w5rtd3md11g

Way more than meet the eye at a first glance

good bot

Dave also confirmed that the presence of a "flagged" output in a ring will raise the corresponding transaction's risk assessment

Even if the transaction otherwise has no particular reason for being identified as more "risky"

That is a big one even for Bitcoin

I ensured that he confirmed an understanding of the non-interactive nature of Monero signatures, which he did

Oh hi :)

Hi sgp_

Anyway, sgp_ and I wrote some very specific questions that sgp_ sent in writing to Dave (yesterday IIRC)

Dave also showed concern over the false positives and negatives in Bitcoin. A key weakness

Even so he confirmed they send poisoned outputs, likely against high-profile targets

The way he described the scope did not give me the impression they are "spamming" outputs

Perhaps. This was one of the questions I posed in our follow-up

Whether they do "general spam" or targeted spends only

Anyway, AFAIK there has been no response yet to the questions, but it hasn't been that long since we sent them

ArticMine: yeah, I was careful to point out concerns over false positives

I did not leave with confidence about whether/how they try to avoid these in a meaningful way

Tricky part about decoy-based anonymity... We add false positives, but there are no false negatives

I am more convinced than ever they cannot even on Bitcoin

I also remain skeptical about how they take (possibly many) heuristics and methods and try to distill to a single number with some arbitrary threshold

The tests have false negatives in practice though Isthmus

Namely, that what this _actually means_ is perhaps not meaningfully conveyed to their clients

I mean the transaction graph has no false negatives

The metrics that you put on top of them may

There is both sound math and compliance theatre

This is why I want to carefully analyze the interview

At any rate, I appreciate that Dave did the interview, though from a security perspective, making any design decisions based on the claims should be done extremely carefully

I don't have any particular reason to think Dave was not telling the truth, but I also have no particular reason to think he was being overly forthcoming

Yeah, this changes nothing ultimately based on the current info we have

This is, however, a good chance to review known methods

I actually think we gained a lot of information. Even more that Dave was willing to give up

How so?

Confirming a lot of suspicions

Well, again, these are all claims

He was very clear on the Monero part was not ready for AML

Without any evidence or details, everything is claims and speculation

Including anything said in the interview

The specific scenario speaks volumes

Anything we hear that sounds like a plausible threat, we should take into account. Anything we hear that sounds like reassurance, we should distrust

^ right on

I agree

The about helping Monero with exchanges is a good example of false reasurance

but as I mentioned this needs to be carefully analyzed

Well, I'm sure they'd rather sell their tool to exchanges that support Monero, rather than see no exchanges support Monero at all

(since they couldn't sell their tool in that situation)

So there's probably some kind of business incentive related to exchanges

but I'm no businesscritter

Maybe we can move on since this discussion isn't really related to research

Even the slightest dent in Monero's privacy is a huge win from a sales perspective for them

Yes lt move on

let

Fair enough

Anyway, I recommend the interview to anyone interested in this

Any other questions on the research topics I mentioned?

If not, does anyone else wish to share research of interest?

Is knaccc here?

Ah yes

hi

sorry been a busy day

knaccc: you had shared some interesting information yesterday

They published some test results to review yesterday

Care to summarize if interested?

i should take some time to think about it and do a writeup - my ability to summarize it now would be limited

OK, no problem

Can you at least set the scenario you are looking into?

sure

Even if you aren't ready to share results

Thanks!

so i have written a simple in-memory db that stores the blockchain graph

and i can ask questions about the blockchain much faster than if i needed to do 2 million calls to the daemon

Pulls from RPC calls?

Or directly from LMDB?

it loads everything in via rpc calls

got it

but then it's all stored in memory and cached to disk so it doens't have to be re-read each time

it's kinda like a very rudimentary LMDB, it's a memory mapped file

with an index for ultra fast output lookups

What's the analysis scenario?

well i write it so i could ask any kind of question i could think of. so if people have ideas, please let me know. i started with simply looking at the anonymity set sizes of outputs (going backwards in time)

to get an idea of how fast the anonymity set really grows when overlapping anonymity sets are involved

and to see whether the anonymity set size is limited when you limit the window during which you think someone may have tranascted

neat

I assume the code will also be made available?

and the other big question was: what is the probability that two outputs, chosen at random from the blockchain, are ever merged

fore sure

fure*

lol

Yeah, merging is something to keep in mind

for*

One simple merge would deal with outputs generated from the same transactions

not randomly-selected pairs

and so i can detect direct merges, and indirect merges if churn could have been involved

yeah some really high-quality questions need to be thought of, for this to be useful

I would like to see information initially on merging from common transactions, personally

great, i'm not sure exactly what you mean, but i'll ask you after the meeting and we'll figure it out

FWIW the CipherTrace "example" posted to r/Monero claimed to be from their tool (without details or explanation), and at first glance appeared to be some kind of merge analysis

yeah that's a big problem that their analysis flagged

To be fair, Dave Jevans later claimed in a comment that it was not a "simple merge analysis" (or some such wording), but during the interview wasn't able to provide any comment on this

if you give someone an output today, and another output a few days later, do you see them spend them together later? and if so, and if that spend is at an exchange, that's a big problem

Anyway, I am skeptical that it isn't just a merge analysis with external flagging, at least in that example

He needs that input correlations

Right

The correlations could come from known spends that flag outputs

yeah the key to most interesting insights is having off-blockchain data

but one long-claimed heuristic is about the source of transactions

where you flag outputs as being "in pairs" if they were generated in the same transaction

it's a much simpler analysis, but one that's long been used to hypothesize a useful heuristic

Getting at least this simple example understood better with chain data would be of value

sounds good

That requires adversary between the sender and receiver of the XNR

ArticMine: sure, but CipherTrace makes controlled spends

and is presumably working with exchanges

or getting exchange data from subpoenas

So one should assume this is a threat vector

Or more simply disgruntled customers

way easier

Anyway, this will be an interesting avenue of study

and no GDPR

I have also been working on scripting to do this analysis, but have not had a chance to complete it :(

Anything else of interest knaccc?

Or questions for knaccc?

not that i can think of. i think it'll be an interative process, where we ask questions, see results, and that prompt more interesting and important questions to explore

for sure

Does anyone else wish to share any research topics?

OK!

In that case, let's move to action items, where anyone is welcome to share their upcoming topics of research for the next week(s)

I will be returning to work on Bulletproofs+, Arcturus, and some additional analysis I wish to complete on chain data

Anyone else?

Righto, in that case, we can adjourn!

Discussion can of course continue, but I'll stop the logs here to post them

Thanks to everyone for attending today

Thanks

Thanks

gg

sarang whenever you have time, please could you explain that scenario you were interested in investigating, i still don't really understand. it sounded like you wanted to see if two outputs from a 2-out tx were ever later spent together, and i'm not sure what the idea behind that experiment would be

I read it as "What is the probability that two random outputs on the chain ever get merged". Probably a graph over time.

Not two random outputs

Two outputs that were generated in the same transaction

Or more than two outputs, fine

So really it's looking at how likely it is for such outputs to later appear in separate rings of a single transaction

Two random outputs means the false positive rate by chance, which is also useful.

Why two outputs generated in the same output? I would expect one to be change to sender, and one to be payment to recipient.

So I wouldn't expect them to rejoin unless they do a sloppy churn back into the same account

Isthmus: right, but this kind of merge analysis is a simple heuristic that's been brought up before and I think is an interesting precursor to the idea of arbitrary flagged outputs

If there's already interest in doing arbitrary flagging, taking care of this long-standing heuristic would be useful IMO

"false positive rate by chance." << This to me is the BIG question that I'm excited about knaccc's work answering

Yeah, of course

Sorry, I don't mean to assume this common-tx idea should in any way take the place of a general analysis

Only that it's been around for a long time and hasn't really been formally addressed with good on-chain distribution data

sarang i think i understand what you're asking, which is i just take some random tx, and see if the two outputs are ever spent together later, either directly or indirectly

i still don't really understand why yould take two from the same tx

i guess it makes sense when indirect

still not really clear though on the insight from getting two outputs from a single tx

I guess it detects splits.

Well, "detects".

knaccc: it's some version of the common-ownership heuristic in non-ambiguous tx graphs

I also don't think it's particularly useful given typical spend behaviors, but seems like a straightforward question to finally get answered

moneromooo oh you mean like a split to dice up change in your wallet, so you can spend later without waiting for change?

It would also happen in that case, true

sarang cool, i'll do that experiment and let you know

neat!

I assume (but only assume) so.

what's the easiest place online for me to use as a kind of experimenter's notepad to write down the results for sharing

i guess i could do gists

it'd be nice to had edit control

to keep things organized later and not just as a stream of thought

Gists have edit and history

They're a single-file git repo, basically

You can edit in-browser or using your favorite local editor w/ git tools

oh nice, cool that works

Yeah, can just make it a secret gist and share the URL as you see fit

edit control is still tied to your usual credentials anyway

perfect

:D

sarang i hope this code is right, this is an interesting result. gist.github.com/knaccc/78c691aa1c1e0710bb8264ef17b56768

i'm running it again, this time choosing two random outputs instead of outputs from the same 2-out tx

nice

Question: what parts of monero protocol *won't* leak, given advent of quantum computers?

^ Isthmus suraeNoether

(they are on the team studying this specifically)

cool

CipherTrace CEO person is active on Reddit again

though not much new information

How so?

posting comments again

Also: it's worth noting that there is sometimes a difference between "broken given a quantum computer" and "broken given a quantum computer and specific information as a hypothesis"

selsta: details welcome

sarang gist updated gist.github.com/knaccc/78c691aa1c1e0710bb8264ef17b56768

:D

i really didn't expect that result

that's quite amazing.

sarang: for example, destination wallet adresses

Inge-: AFAIK you can test this if you have a candidate address in mind

Otherwise you need to enumerate, which is an infeasible process

e.g. reddit.com/r/Monero/comments/il2c12/_/g3rhy41

i don't really believe the result to be honest, looks too good.

OK, that comment addresses nothing

FWIW, Dandelion++ is not intended to address targeted attacks

and was never claimed in this way

Dave claims new heuristics, but talk is cheap, and reddit comments are even cheaper

Kudos for engaging at all

outright lying seems like a bad move all round. Creatively applied wording more likely

I'm responding to several comments

I don't fault him for not knowing the math, but I'll talk details with any member of his team whenever they like

name the time

He sounds upset that I asked questions not on the prepared list

"We will not be discussing further technical approaches at this time"

They aren't under any kind of obligation to discuss anything

they're a private company

What I will not do is let him get away with "I am not the math person, therefore what can ya do"

He's free to refuse further questions, but not to say that it's because of the research community

My take is that the responses sound much more defensive than would otherwise be indicated from the tone of the interview

inge: a single one-time address won't be sufficient to go back to someone's whole key :)

Inge- rather

but basically everything falls apart with quantum

which isn't surprising, it's true of Wells Fargo and Amazon and Zcash and Bitcoin and... etc

and i'm still thinking about transaction linkability and suchlike

suraeNoether: so qc + wallet address = you can get to wallet private key? and also determine the actual destination address that wallet sent to, via only on-chain tx and sender private key?

QC can do arbitrary discrete logs

so any direct public -> private key map is trivial

Well you can't use the wallet private key to reconstruct old transactions by looking at the block chain. But you definitely own their private keys if you are a quantum adversary

In sqrt rather then linear though, right ? So doubling key length gets around that in theory ?

the sqrt thing is true for inverting hash functions or one-way functions using grover's algorithm. i'm not sure about the discrete log break with shor's

i will find out in a bit

ty

Doubling key length is an "effective" way to kick the can down the road with Grover's algorithm specifically.

Of course, "switching curves" is... nontrivial...

although twisted edwards curves targeting higher security levels absolutely exist

e.g. ed448

Kicking it down the road meaning it doesn't give you the same strength as before ?

Or that there might be better than Grover's suspected but not yet found ?

suraeNoether: but owning their private key still requires access to what first tho? wallet address?

Wallet private key? Or output private key?

I was thinking wallet private key

Well, at some level that's irrelevant

If you can compute DLs, you can get output private keys and sign with them

thereby spending arbitrary funds at will

Iwould distinguish between spending funds and unraveling privacy

Yes

But knowing wallet private keys does not necessarily equate directly to breaking privacy, whatever that is intended to mean

Inge-: yeah, public wallet address is sufficient.

Inge-: also, transaction amounts are still perfectly hidden

Under the assumption of hash function security?

Because if you can do shared secret, you can get amounts

There are threeish things that don't break. As long as you've *never* received funds twice to the same address, a QA who only has access to the public blockchain data cannot break stealth addresses, or decrypt amounts & encrypted payment IDs

But if you've received funds to the same address twice, then your private key can be extracted by a QA, which then enables them to calculate txn shared secret and decrypt the amount and payment ID

(^ still using nothing but data that is public on the blockchain)

Core wallet reuses change address though, right?

In the paper, we assume that the attacker only has access to public data on the blockchain, unless explicitly mentioned otherwise. But I'm going through now to add some more notes to make that clearer.

We always assume that the attacker is NOT a party in the transaction

So the only exceptions are when the attacker knows of an address (e.g. section on extracting k_s from K_s)

But I'll clarify within sections to avoid confusion

Yeah knowledge of a list of possible addresses is of interest to me too

Oops, there is one other exception - in the "Violate transaction balancing" we assume that the attacker is the sender