Rucknium[m] it would be interesting to see how the 10-block decoy selection bug interacted with pools not picking up transactions immediately in the past. Maybe these two bugs canceled out each other?

The reason I ask, is wallet doesn't let user to send a transaction unless it's 10 blocks old, and mining pools didn't mine it for one more block until their update frequency was fixed

so 10 block old decoys should've been very rare until recently

because wallet didn't pick them as decoys, and real spends waited for one more block

Unless an observer was actively monitoring/logging the mempool

yes

but still, blockchain doesn't have this data. So future attackers will not have it.

Right

sech1: I guess p2pool sidechain did collect transactions in mempool in the shares provided

as those get baked in, tho pruned by normal nodes

oh my monero-project/monero #7807

This issue just keeps coming back to haunt us :D

yea, I was definitely in physical pain when I realized I missed this. I thought it was one of the first things I checked, but evidently still missed it

sech1: Maybe. My thought process was:

1) Same as yours.

2) Wait, that just causes a one-block delay in confirmation. So instead of the youngest real spend being 10 blocks old and the youngest decoy being 11 blocks old, it would be 11 and 12 blocks of age, respectively. An adversary could just adjust their analysis by one block.

3) Wait, different blocks are mined by different pools and solo miners. So some transactions could be confirmed "on time" (with 10/11 youngest real/decoy ring member) and some with a one block delay (11/12 real/decoy). That introduces uncertainty about the youngest possible age of the real spend and decoy output.

4) Wait, mining pools declare which blocks they mine. And the block template update config of each pool could be known. That would mostly eliminate the uncertainty suggested in point (3).

I agree with endor00 's point that mempool logging would probably remove most of the uncertainty anyway.

If you look at jeffro256 's line chart: monero-project/monero #8872 the green line increases a lot at about the time that most of the major mining pools changed their configurations (Jan/Feb of this year).

Yes, the mining pool delay config "hid" the 10/11 split, but there would probably be a 11/12 split that an adversary could use. jeffro256 could rerun the chart (or I could do it, too)

Like jeffro256 said, nonstandard decoy selection algorithms may have not had the same off-by-one error in decoy selection. That introduces uncertainty for an adversary. If those decoy selection algorithms are _very_ different from the wallet2 one, however, maybe an adversary could tell that the ring was not constructed by wallet2, which would eliminate the uncertainty again.

How different would it have to be (at 11 and 16 ring size)? Not an easy question to answer without putting in a lot of research time. I want to look into ways to classify individual on-chain rings into different decoy selection algorithms eventually.

Looks like relevant research for possible Seraphis curve change for global membership proofs: magicgrants.org/Aram-Jivanyan-to-Research-Firo-Curves

^ UkoeHB , kayabaNerve, tevador

Meeting 20mins

meeting time monero-project/meta #841

1. greetings

hello

hi

Hello

Hi

2. updates, what's everyone working on?

Hi

me: slowly working on escrowed multisig design for monerokon.

I like that - I'm slowly working on bulletproof++ - github.com/ElementsProject/secp256k…zkp/files/10130246/BP_PP_proofs.pdf

Experimented with cluster computing software on Monero Research Computing server and settled on an R native solution for now. Developing and testing some R code at scale on the cluster to make sure there is no RAM blowup.

I previously thought the linked pdf was just a copy of the eprint, but its actually just the math equations for the protocol

I have no idea how to do a batched proof like we had previously, so I will focus on just getting the single case

I also got the new serialization pushed out, but that is less of a MRL task

batching should be possible wherever generators can be shared

ah ok, yeah that makes sense, but I feel like i will still botch it lol

we previously only batched per tx ?

nvm, I can find that in the code easily enough

Sorry for my ignorance about bulletproofs, but how does batching work there? Is it clever maths and/or not recomputing stuff or using simd instructions (or all together because the first part can be precomputed before the parallel part)?

Anyway, probably tomorrow I'll start to do some wallet work

ah there's batched verification and aggregated proving which are different; batched verification is easy but idk how the aggregated proving works

Did I stump the meeting?...

ghostway[m]: batched verification is possible because proofs are verified by summing EC points and checking they equal identity. You can combine multiple proof verifications in one large multiexponentiation (adding all proofs together at the same time) by multiplying the elements of each proof with a random verifier-selected number (ensuring no proof cross-talk is possible). You get perf gains from the

multiexponentiation algorithm and from sharing generators between proofs.

s/stump/disrupt/

Matrix<>IRC bridge is having problems again.

I think it's working fine

Matrix users can see all IRC messages here: libera.monerologs.net/monero-research-lab/20230524

"ah there's batched verification and aggregated proving which are different; batched verification is easy but idk how the aggregated proving works" This message didnt come through to Matrix AFAIK

I am using matrix. Liberalogs are no different so far.

It is for me, thanks!

Any chance we can allow fast N-of-N multisig setup?

I think I should just come to irc. I have to find my tor config lol

The post-kex round is unnecessary because all keys are involved in the signing.

This will make the 2/2 multisig setup a single round-trip long, simplifying it greatly in a stateless API context.

Alex|LocalMonero: that's kind of a dev question

Got it, apologies.

I thought it was relevant to research in case there are security risks related to bypassing the post-kex round.

Just wanted to make sure it's clear.

On this recent off-by-one error in decoy selection: IMHO, treating Monero's statistics like its cryptography is treated would be a good idea. For cryptography, formal specifications are written. Then code is independently audited to make sure that the specification is executed properly.

This would apply at least to the decoy selection algorithm and Dandelion++ implementation.

I have heard people, e.g. kayabaNerve, say that wallet2's decoy selection algorithm is difficult to port to another language or implementation. If there was a formal specification, maybe it would be less so.

Hmm, but then, if you implement a spec, code in other languages would maybe audits as well, at least in principle

*maybe need audits

writing a spec does imply some cost

not a bad thing to have though, of course

That would be a good thing IMHO.

We could start by reverse-engineering a spec from the current code.

Or, we look forward, and start a spec based approach with Seraphis.

I'd agree, I don't think it would require audits, it would only lessen the impact of bad coding

A crude simple test is to take some alternative code and generate thousands or millions of (unused) rings against the mainnet blockchain and test statistical equivalence.

That's what I did (except no actual blockchain, just the output indices) to validate the Python and R ports of parts of wallet2's decoy selection algorithm here: github.com/mj-xmr/monero-mrl-mj/tree/master/decoy

Maybe stupid question, but why didn't this unearth some hints about the recent one-off bug?

I guess you didn't have that in your alternative implementations?

it's a small hard-to-see edge condition

(the statistical test code isn't in the repo, but the implementations are there)

Not enough cases randomly generated that hit it, then?

So no difference sticks out

Not a stupid question. I think this piece of the code was isolated from the part that decided which outputs werwe eligible for decoy selection

There are two more things: a KS test, which is what I did has "low power". That means that it can be hard for it to detect very small differences. A KS test is very general, which is why it's used. And:

R is indexed from 1. C++ is indexed from zero. Like I said, I think this code that I worked on was isolated from the main problem, so I would not have caught it anyway. But even if I saw it, I may have assumed it was an off-by-one error in my own code because of the R port. Or maybe I would hav erealized it.

Interesting, thanks

This is why with an audit or more complete test you would want to test using the actual mainnet blockchain to make sure there is "100% code coverage" of the test

A good place to start would be writing an MRL research issue outlining the algorithm that we have.

If someone writes that issue: Rucknium[m] jberman[m] jeffro256[m] then I will review it.

Reverse-engineering a spec is on my to-do list. But it's much easier to work with someone who can read the original C++, e.g. jeffro256

UkoeHB: Thanks.

Are there any other topics we should touch on before the end of the meeting?

ok I think that wraps it up, thanks for attending everyone

Ty ukoehb

My memory has been jogged a bit. mj and I worked on that repo about a year ago. We did have an off-by-one issue in one of the first versions that my KS statistical test caught. One of my messages to mj was: "Preliminary findings: I think there may be an off-by-one error in the Python implementation."

We eventually fixed it. I don't know if it was related to this recent finding.

I remember that I put the number of random samples into the millions since I knew the KS test had low power. A larger sample size can fix the low power issue. Power of all good valid hypothesis tests converge to 1 as sample size increases to infinity.