<UkoeHB> "midipoet: github.com..." <- I must have missed this but this appears on the surface to be a fantastic idea

Is it interactive though? How would it work for donations to static addresses for example?

Interactive? It is just a simple optimization

In about two hours there will be a MRL meeting in this channel

ArticMine: Will you be able to attend the MRL meeting at 17:00 UTC today?

meeting time ( monero-project/meta #622 )

1. greetings

hello

Salutations

Hello

Hi

hi

Hi everyone! It looks like MRL meeting time

hello :)

Please see suggested agenda items & useful links in the github issue

If Koe is not around I can work through the agenda items

This concludes the greetings, moving to point 1 on the agenda "Further analysis of July-Aug 2021 tx volume anomaly "

is the matrix bridge broken?

1. Greetings

monerobull[m]: just kidding lmao

You are coming through clear koe

carrington[m]: you didn't see my messages 2 mins ago

The matrix bridge is acting wonky

ive noticed matrix bridge is intermittently dropping things

From observations it seems like the IRC --> Matrix bridges sometimes needs to wake up from sleep or something. Your first message, koe, didn't come through to the Matrix side

Ah no those didn't come through. I see them on monerologs site though

sigh

I will keep an eye there and let people know if messages drop

anyway, I think the first item today is isthmus wanted to discuss an idea he had

:wave

Lemme pull over some notes from logs

I’ve been continuing to dig into the July 2021 txn flood. The anomaly has been a fantastic case study for ring signature deanonymization due to high volume and extreme transaction homogeneity.

Since doing recursive searches over ring signatures is grossly inefficient, i.e. O(R^H) for ring size R and number of hops H, I’ve been working on efficient encodings for analyses in O(# Txns) by working from genesis to head (which is presumably how any adversary with basic CS skills would approach it)

The data features may take a few days or weeks to build, but you only need to do it once, and then you can read in basically O(1).

One cool application is marking all of the outputs upstream of a given ring signature, which you can think of like an N-1 length bitstring attached to the Nth output, where a 1 at the jth index indicates that output J was a parent of output N.

(You can also imagine this as a triangular matrix with ((# outputs)^2)/2 nonzero entries)

I think the bridge has been woken up :eyes:

oops I just got booted

It’s a windowable method, for example our first application is identifying which (pre-flood) outputs were used to set up the transaction volume excess this summer. Since we can narrow our focus to a few months leading up to the anomaly, each tag is only a few kB, so we don’t need much computational power or disk space to pull it off.

It’s also surprisingly viable to apply this to the entire blockchain if you have a bit of patience for the first build. Back of the envelope estimation is that all edges in the Monero transaction tree could be naively encoded into this matrix / bitstring formalization in just over 100 TB

(which is very small from a big data industry perspective, where good data engineers are expected to sling around PB’s of dataefficiently.)

There are methods for encoding this more efficiency ( e.g. succinct posets: arxiv.org/abs/1204.1957 ), but honestly since the naively encoded data set is only ~100 TB it probably wouldn’t be worth the effort of implementing all the fancy math.

With the data in this shape, output recombination analysis becomes trivial, so we’ll be able to answer conclusively whether the transactions in the anomaly had two >0 outputs (amount + change) or only one valued output and one dummy (0-value) output.

The reason it becomes so simple is this: the way that we built the matrix means that it’s already sorted (both in terms of rows and columns). So now we can test hypotheses extremely quickly by slicing out columns then simply working top to bottom until you encounter the first [1,1]

For example, if a transaction created the xth and x+1th outputs, we 1) simply pull out xth and x+1th columns, then 2) throw out all the 0s before the xth index, then 3) only search as far as we need to to find the first [1,1].

It’s extremely efficient, which is pretty cool, and it doesn’t matter if there are 3 or 30 or 300 hops between when the second output gets folded in downstream of the first one.

For a given output, let delta be the height difference between output creation and the first recombination, with delta(x,x+1)=inf (or nan) if never recombined. The interesting thing is not how often recombinations occur, but how quickly.

There will always be spurious recombinations due to decoy selection, but when we look at the distribution of deltas, the baseline distribution (in a sense, the control case) will have a longer expectation value than what we observe during the anomaly if both outputs were valued.

It’ll take some time to code up the tags and build the data features, but I expect that our next report(s) on the flood will be able to deanonymize most of the ring signatures, conclusively answer whether the anomaly was producing dummy outputs or change outputs, and hopefully identify which transactions before the anomaly created the thousands of ‘mise en place’ outputs that were consumed when it began).

In terms of guessing true spends, we actually have 3 heuristics to combine:

1) timing, usually 10-15 blocks old

2) only interested in ring members that have the same fingerprint: 2 outputs, unlock_time = 0, fee matching core wallet, tx_extra length 44 bytes, etc

3) above linking analysis

Oh and 4) throw out fresh off the coinbase

I think that even without #3 the other heuristics will knock it down to 1-2 plausible members per ring

hello, a bit late

Note also that even for normal wallets without recombination, #2 and #4 apply to change output chains

I was thinking that for analyzing the volume anomaly, we can probably just look at the ~500,000 inputs leading up to the start of the excess volume

(a few weeks)

That leaves us with few kB scale tags which will be easy to manipulate without much memory or computational power

And if we don't find the origin outputs in that window, we can just rerun it another 500k indices further back

This analysis method seems powerful. Do you anticipate that chain analysis companies will already have been using something similar? Or does it lose most usefulness when we don't have homogeneous transactions and all the heuristics?

Probably and yes

Well, it's more useful in some situations than others. It'd also be a fast way to check EABE attacks (if you're eve) but there would be faster ways to look at small subgraphs

For example, if you collude with an exchange which holds many outputs. If that is the case I think we need to develop some mitigation strategies

isthmus: Should we also consider deploying my statistical attack on top of those 3? We probably wouldn't want to include results from that in what we publish, but it could be interesting.

Yea could be a validation method, albeit under limited circumstances (high volume and homogeneity)

I have to say, this transaction volume anomaly has been such a gift for trying out a bunch of analyses and visualizations where they can gain more traction than usual

Almost as if that was their intention 😟

are we guinea pigs in an alien experiment? :p

@UkoeHB I assume this to be the case

isthmus: So in a way if this was a genuine attack attempt, it may have backfired, as it may have increased our MRL technical capabilities 🤔

LOL yea I've probably gotten as much novel analysis out of this as they did

Anywho that's the update from me. It's all pen and paper right now but will hopefully move towards implementation in upcoming weeks/months

carrington[m]: probably was one of you guys anyways /s

I'd be really interested to know what impact even simple binning would have on this technique

Cool thanks isthmus. Hopefully within the next couple hardforks we can reduce the range of fingerprintability.

Because the "delta" would always have multiple links simultaneously

isthmus: Do we plan to employ gingeropolous 's up-and-coming research computing server? Also, I think it would be good to fund that server via CCS

Next, let's revisit the 16-ring member recommendation from last meeting. There were a couple comments on the github issue (starting here: monero-project/research-lab #79#issuecomment-948198584).

Anyone have anything they want to say about this?

16 is fine. I personally prefer to keep it as low as possible tho. Weight is in the blockchain forever and all that

general community supports 16 rings

i think it would be informative if we could dig up the reasons ringsize 11 was selected, as noted in that comment

@Rucknium[m] that could be great - will chat with you / ginger / neptune offline about this (neptune handles most DB dev and ops)

Seems like 16 has broad support, I propose we call it there

did we get an input from core about it?

on the topic of binning, nearly everyone supports deprecating timelock reddit.com/r/Monero/comments/q0oiln…ce=share&utm_medium=web2x&context=3

Yes please

are there alternative timelock schemes worth thinking about?

erciccione[m]: IIRC in the most recent dev meeting, UkoeHB brought up 16 and then agreed to take it to MRL for input. That input was given last MRL meeting.

e.g. the bitcoin one seems pretty popular

-dev is not Core, of course, but that's some info ^

> <@rucknium[m]:libera.chat> > <@erciccione[m]:libera.chat> did we get an input from core about it?

>

> IIRC in the most recent dev meeting, UkoeHB brought up 16 and then agreed to take it to MRL for input. That input was given last MRL meeting.

i know, i was asking if anybody from core commented publicly about it, just to make sure you are onboard

Articmine wanted it higher in the GH issue, but I can see no other comments from core members

but there has been an open issue for some time i'm assuming they wrote something there. I don't recall at the moment

ah ok. Then maybe getting an input from them wouldn't be bad

The btc version of time locks is certainly more useful

But comes with the same privacy concessions as our current timelock, right?

Plaintext, fingerprintable, tec

s/tec/etc

UkoeHB: IIUC, to get the bitcoin version requires a way to have refundable tx's, which the research into DLSAG explored: eprint.iacr.org/2019/595.pdf

`<monerobux>` isthmus meant to say: "Plaintext, fingerprintable, etc"

bitcoin-style, as in "don't mine into block until blockheight x" ?

Unless encrypted, which has scalability drawbacks

ErCiccione: Check this meeting log for some statements from Core members about ring size:

I was thinking bitcoin style = HTLC's, which essentially allow a recipient to claim an output as theirs before a certain time, and if they do not, the output is refunded to the sender, which seems to require a larger structural change to the tx protocol to support in Monero

> <@rucknium:monero.social> ErCiccione: Check this meeting log for some statements from Core members about ring size:

> monero-project/meta #614

Thanks for the link. It's enough for me to know they are onboard with 16

i dont think discussing this productive at this point, what would happen to timelocked transactions after a fork changing addresses?

* discussing this is productive at

monerobull[m]: nothing. All old outputs need ‘transition’ tx to spend them, which is a tx type that must be supported indefinitely.

DLSAG might be worth revisiting in the context of seraphis

🤔

Is that the one that has hidden colored coin support?

IMO timelock features can wait for some post-bigring hardfork, unless there is a technical reason to decide earlier

isthmus: It's a building block for bidirectional atomic swaps + payment channels

carrington[m]: well if it is easy to implement, might be worth considering

jberman[m]: afaik bidirectional swaps just needs tx chaining; payment channels need the timelock thing

tx chaining is part of present seraphis, yes?

Serpahis plans*

one variant yes

indeed

anyway, we can move on; anyone have something to discuss? maybe from the agenda

Well if DLSAG and Seraphis can easily be smooshed together then that would be lovely. I seem to remember some sort of big drawback with DLSAG from ancient MRL logs though, can't remember what

doubletxs?

Decoy Selection Algorithm is next on the agenda. I have updates. jberman, do you have updates?

Nah double txns was lelantus I think

This past week I hardened flaky decoy selection algo unit tests (PR 8024) + finished up working on restructuring the wallet-side binning algo to account for the flaw mentioned in MRL issue 86

An update to MRL issue 86 is coming, hopefully today

The gist of the change is that bins span a fixed number of blocks, instead of a fixed number of outputs

In order to avoid an edge circumstance where one can deduce an output in a ring must actually be a decoy

Spanning a fixed number of blocks is a terrific idea.

jberman[m]: Will your update to MRL 86 explain how such an edge case could occur?

Are you requiring the bin width (in blocks) to be >= the bin size (so if they are all empty, miner tx will be the bin members)?

It's way easier to reason through and the algo is much simpler this way

Rucknium[m]: This comment explains the edge case in full: monero-project/research-lab #88#issuecomment-947481223

Also apologies, I meant MRL issue 88, not 86

UkoeHB: This is something I've been thinking about

Is it possible to make a miner tx without any outputs? moneromooo

I can double check that later if we don't get an answer

ok, just a small detail

thanks for picking up the ball on binning jberman[m] :)

Looking forward to the binning update, I think I have managed to grokk issue 88 so far

Yea tyty

But in any case, I've been debating including a bin width (in blocks) to be relatively small, potentially allowing even smaller than bin size. I'm not sure what the ideal parameter choice is there. The smaller the bin width, you protect against a certain circumstance where users may be spending outputs extremely close. The wider the bin width, the fewer issues there may be in the implementation

Surely the best protection against spending close outputs is to increase the "bin members"?

I.e. if we eventually have bins with 10 decoys each with seraphis the problem is basically negligible

definitely, but assuming we have limited number of ring members to work with, not so trivial to do

My main update is that ArticMine has examined my HackerOne submission, which included a rough outline to develop OSPEAD. He gave me some feedback. I believe that he will say something about it publicly soon.

In the next day or two I will start a, uh, viral marketing campaign for OSPEAD 😂

The main component is an animated gif of the Monero logo that illustrates statistics...

And then I may release a version of "Document A", which is a fairly precise mathematical definition of a key component of OSPEAD. So the community can see what I intend to do.

I have seen this logo and I can confirm it is the bees knees. Looking forward to digging into the HO report and OSPEAD when released

Then hopefully community consensus will be attained and my CCS proposal can go to "needs funding".

That is my update. Questions?

Ah I meant to review the CCS proposal closer and leave a comment, will do that in the next 24h

Honestly if you have not received any negative feedback I don't see why not move it to funding right away. If in the intermediate time it is determined that OSPEAD is flawed, the funds would just go back to the general fund in the end

I'd rather wait to see what we're buying first.

I think that the main negative feedback is that my suggestion that part of OSPEAD should not be made public was quite controversial. That's not going to be a Rucknium-level decision, however. It is somewhat besides the point when it comes to whether the research should be funded, I think.

one-horse-wagon[: So you want to see Document A first? That would be fine. isthmus, jberman, ArticMine, Syksy, and mj-xmr have seem it so far. I will get a version ready for release in the next 4-5 days or so.

* have seen it_

I'm fine with it being shared, fwiw. I'd bet that at least one chain analysis company has figured this out already, and the rest will be able to connect the dots with how the solution is approached. So confidentiality might be hindering us more than them.

isthmus: What is "it" in you statement? Not that I disagree.

* your

ArticMine has his own views on disclosure.

The concepts / ideas in general, wasn't referring to any particular document

Well I guess we await this Doc A. I have a question on seraphis before we finish up here. Does this "supercop" stuff fall within the scope of the seraphis PoC? Seems it sped up CLSAG a lot, although I can't say I really understand how it works or relates to seraphis

one-horse-wagon: Could you answer my question above ^ ?

carrington[m]: it is not in-scope. Supercop is optimized crypto libraries, which can be implemented at a later date if appropriate.

Could you remind me what supercop stuff is?

ohh optimized crypto libraries

nvm

Ty. So all seraphis timing estimates should have a footnote that there are significant crypto optimizations not being accounted for

hmm I suppose so

afaict CLSAG is not using supercop, maybe someone can correct me

Refresher on the view tag: basically it's a 1-byte addition to tx's that would speed up scanning by 50-70%, and just needs someone to implement, ya?

1 byte addition per output*

Rucknium. What question are you talking about?

<Rucknium[m]> "So you want to see Document A..." <- ^ This one. What standard would I have to meet, according to your standard, for "see[ing] what we're buying first"?

<jberman[m]> The smaller the bin width, you protect against a certain circumstance where users may be spending outputs extremely close. <<>> spending the outputs from mining on p2pool currently triggers the wallet warning that outputs are close

Maybe SGPs suggestion that we have coinbase-only rings should be revisited if p2pool takes off

"Document A" is explained in the logs here. Just search "Document A". I am terrible at naming things lol

nioc: yep, it would provide protection in that kind of circumstance

jberman[m]: More or less. There is some fiddly logic around tx pub keys, and I'm not sure the best way to actually derive view tags. Using a truncated sender-receiver secret leaks bits of that secret, but using a hash adds ~1-3% to scan times (in my tests).

coinbase-only rings also a solid idea I think

There are no standards I have in mind. I would just like to see Document A that's all.

Also, max reduction should be only 40%

one-horse-wagon: Ok great. Yes, I will prepare Document A for public release. This will include removing a few things and making it slightly more understandable for laypeople. I warn that it is a technical document and will remain so, however.

Also, if isthmus, jberman, or mj-xmr could give me some feedback on Document A before release, that would be good, too. Not necessary, however.

Rucknium on the meta agenda item, I seem to remember you mentioning that there was someone interested in doing a CCS for reviewing Monero papers. Am I misremembering, and if not do you think this person will go ahead with that plan?

Rucknium. Very good.

I'll take a look at Document A, and run if I don't understand it.

carrington It's me.

There is no one in particular. I think we should be reviewing Monero papers, it may make sense to have one person be spearheading it, and it's important enough that it should probably be funded.

Rucknium[m]: Been meaning to, will do

Oh, oops, I guess coinstudent2048 was that person.

Yea, I'd love to see a survey of recent literature relevant to ring signature deanonymization. Even just a collection of relevant papers would give me a weekend of fascinating reading.

jberman: Ok great. Thank you.

We are past the hour on the meeting, so I will call it here for the logs. Continue discussing if you wish

I think it is a valuable idea! I tried to look through papers with Monero keywords and the volume/variety was quite overwhelming. There has to be at least a few easy wins from those

carrington: I am not sure though anymore, I fear personal stuff gets creeping in gradually.

It is a big task for sure. Maybe a bounty could be created for a bonus payout to whoever takes it on

<UkoeHB> "jberman: More or less. There..." <- sounds like hash is the way just going off this snippet. it's a pretty significant optimization regardless, losing ~1-3% after gaining ~40% doesn't seem so bad, so seems like the safer conservative approach is sensible

UkoeHB: I think new test runs for the modified/refined multisig PR code are a good idea. I am ready to do them, just let me know somehow when time has come

Hey I have no idea WTF any of you are saying but I just want to thank everyone involved for the hard work and dedication. Thank you very much. The future of the human species is in your hands. No pressure tho ❤️

Logs are posted

I'll make a new issue for next week, same agenda items for now. I'll add links to any updates which drop through the week

cute note on quantum computing vs crypto metzdowd.com/pipermail/cryptography/2021-October/037465.html

A thought on coinbase-only rings: they give an observer knowledge of the max amount spent in a tx, and therefore reveal the max value of the RingCT outputs created in the tx in which coinbase-only outputs are used

sounds like a good reason not to sequester them to coinbase-only rings

Currently, the coinbase tx must give the miner the exact amount allowed, so this requires at least one output. This is fairly new role though. Other than that, I see no reason why a coinbase tx could not have no outputs.

if the coinbase tx has no outputs, then what happens to the expected coin emission?

It gets shifted by 2 minutes into the future.

Does a coinbase txn with no output pass this check? github.com/monero-project/monero/bl…ote_core/blockchain.cpp#L1410-L1418

Does this happen often? github.com/monero-project/monero/bl…ote_core/blockchain.cpp#L3782-L3786

`MERROR("Failed to determine block reward, using placeholder " << print_money(BLOCK_REWARD_OVERESTIMATE) << " as a high bound");`

`#define BLOCK_REWARD_OVERESTIMATE (10 * 1000000000000)`

Probably and no, resp.

It doesn't look like `base_reward` in that first check can be 0, because `get_block_reward` doesn't seem like it can set `base_reward` to 0 (since reward is calculated based on already generated coins & expected time). So a coinbase txn with 0 outputs shouldn't pass that check (since `money_in_use` calculated based on amounts included in outputs must be == non-0 `base_reward + fee`)

Unless there's something in here I'm missing that can set `base_reward` to 0: github.com/monero-project/monero/bl…cryptonote_basic_impl.cpp#L112-L126

ah wasn't there a hard fork preventing coinbase tx from accepting less than the block reward + fee?

`HF_VERSION_EXACT_COINBASE`

So that things like this don't happen 🤦

No, in Monero taking less than the full reward did not burn XMR, it just made the leftovers available to future miners. It was originally implemented to so miners could chop off the lower bits of block rewards, which reduced dust creation back before hidden amounts were added.

ZtM2 section 7.3.3 footnote 26 ^

afair that change was reverted when ringCT was deployed

miners are no longer allowed to take less than the scheduled block reward

tho I may well be misremembering

it was reverted in 2020 I think

yeah, HF 13

#define HF_VERSION_EXACT_COINBASE 13

so yeah, you can't have a zero-output coinbase tx

after I brought it up iirc

that was the last hardfork we had in October 2020

wow, a year without hardfork already?

seems like nobody missed them ;)

Not sure if anyone has brought this up, but perhaps something like this would be good to add in around the same time (or perhaps before... or perhaps after) as Seraphis if there going to be a significant change in address format: monero-project/monero #6639

crypto_grampy[m]: I think seraphis addresses would not require any changes to mnemonics (although this feature would definitely be helpful).

I think the notion of encoding restore height would have been great if starting a new system from scratch

too late now for Monero ecosystem

also, it's sufficient to write down the date of wallet creation

the wallet can eventually ask the daemon for height-associated-with-date

and that code already exists in the wallet

It's definitely a problem that gets worse as time goes on.... I don't think it's the worst thing in the world today, and light wallet server could address much of it from a one-wallet experience, but moving between wallets, or restoring from scratch/seeds is only going to get worse