Meeting in 20mins

Hello

Hello

meeting time

1. greetings

hello

Hello

Hello

Hello

agenda: monero-project/meta #808

Hello

Hi

Hi

Hi

Hi

2. today we have the authors of this significant new preprint eprint.iacr.org/2023/321 here to discuss their paper/answer questions

Hello

CasCremers[m]: do you want to briefly introduce your team and your paper?

Hi, we are three academics at the CISPA Helmholtz Center for Information Security in Germany

Our paper tries to give a more complete analysis of the security of Monero transactions as opposed to the isolated analyses previously

Any particular questions you might want to see answered?

(We're not terribly familiar with this format)

CC: First, thank you for the very nice work. It is nice to see research being done with Monero and I enjoyed reading it :)... (full message at <libera.ems.host/_matrix/media/v3/do…7ce76793de7899c44055b2d19c988410975>)

I can't be present throughout this meeting but I'd like to remind attendees of these meetings that they are welcome to submit a proposal to present at Monerokon in Prague in June, and to spread the message to other relevant researchers

CasCremers[m]: thanks, the format is fairly informal. I am currently reviewing your paper, it just came out so I am only ~1/4 through it. Did you find anything interesting/surprising during your research?

A1: We have a limitations section that describes part of the analysis that were not completed yet and that would interesting to investigate. (But we currently don't have a project tailored towards this)

A2: Our analysis tries to walk the fine line between theoretical and practical. We did check the code for several questions we had, but of course the analysis is theoretical.

A3: I briefly looked at the issues you linked. It seems that they are related to the fact that Monero uses Ed25519, i.e., a non-prime order group. As stated in the limitations, we assume that we have a prime order group. This is common in cryptography.

Thank you for joining us today. Do you want to get funding for studying Monero multisig? It is still considered experimental since there is not a formal security proof. You can get funding at monerofund.org/apply_research or ccs.getmonero.org/what-is-ccs

<UkoeHB> "CC: thanks, the format is fairly..." <- On the practical side, we did not find anything particularly surprising. That is to say, that we confirmed that Monero's transaction system is secure in our model, as expected. However, we encountered many technical obstacles during the proof due to the non-standard uses of the crypto in the Monero transaction system. These make our paper interesting from a theoretical point of view

also

CasCremers[m]: I noticed your ring signature analysis is > 20 pages, and I recall ring signatures have a history of difficult-to-assemble security models. How do you guys feel about your solution?

Wrt Ed25519: In a separate context, some of us actually actively worked on this problem: eprint.iacr.org/2020/823

but that is not directly used in the Monero proof

sorry, just sitting here ignoring this room, now present

Formal security proofs for Monero multisig are considered high-to-medium-priority, but there is not an active effort (that we are aware of) to create them.

Rucknium[m]: We would be interested in setting up a further project on Monero with PhD students, and would be happy to learn more about the opportunities. Maybe this is something for a dedicated conversation?

UkoeHB: The main aspect here is that the standard notions for linkable ring signatures are not enough: For example, the keys that an honest user uses are potentially derived by the adversary from the honest users address. This is why we have to analyze linkable ring signatures with respect to the key derivation. I think this is the main challenge here.

CC: Yes that sounds great. I am on the committee that approves grants for the MAGIC Monero Fund, so I can help you there.

<bewa_c[m]> "A3: I briefly looked at the..." <- Yes. One issue is about that. The other is that there are some wrong signatures that dont strictly obey the ring signature equations. I am pretty convinced that it is only a serialization problem but anyway it is always good to formally settle things down.

Thank you for the answers bewa_c CC !

We would be very interested in removing the limitations, and moving closer to the implementation. However, this is very challenging work and it is not always clear how to compose the results.

bewa_c[m]: I see, yeah your analysis might be the first to unify the consensus/proof side with the address side.

For example, we are not yet considering privacy in this work.

<CasCremers[m]> "We would be interested in..." <- Nice! I guess Rucknium is the man to talk to. From my side, to be honest, I would be happy also to dedicate 100% of my time to Monero and do a PhD :p

UkoeHB: I am not sure this is quite accurate. We treat the consensus layer as a black box (i.e., assume it is given and works correctly). Our analysis concerns only the security of transactions on the ledger

jlo[m]: by consensus I mean transaction validation rules checked by consensus (e.g. that proofs are valid)

jlo[m]: figure 3 VerTx() basically

Ok, in that case, I agree with your initial comment

What motivated you to write this paper? Why did you pick Monero to study?

Rucknium[m]: We had been been studying signatures and bip32, and we are interested in real-world constructions an d proof techniques for them

> <@rucknium:monero.social> What motivated you to write this paper? Why did you pick Monero to study?

* We had been been studying signatures and bip32, and we are interested in real-world constructions, and proof techniques for them

CasCremers[m]: This seemed like a sizeable challenge of scientific interest from a proof technique angle

It's certainly a very impressive paper, and a bit unexpected for me since I assumed the task was too large for anyone to tackle.

It took us over a year

UkoeHB and others are working on Seraphis, which is a planned next-generation transaction structure for Monero: github.com/UkoeHB/Seraphis I think we expect that the Monero Project will need help with creating formal security proofs for some of Seraphis.

wow no kidding

(wall clock time)

This sounds very interesting, but also a very substantial task.

Also extensive audit work will be required

I think this holistic analysis paper will be a very strong starting point for a security analysis of seraphis

Btw CC: better to not use fancy matrix features like threads. The irc people (koe between them) don't see it as you do...

Might (and probably did) create confusion on the ordering

So much for that DAG ;-)

Q: What is the intended timeline for Seraphis?

is the matrix protocol supposed to be a DAG?

CasCremers[m]: we'd like to get security proofs done this year. The implementation is already basically done, as is the addressing scheme gist.github.com/tevador/50160d160d24cfc6c52ae02eb3d17024 . There is also a parallel protocol Lelantus Spark that already has security proofs eprint.iacr.org/2021/1173

Hi sorry I’m late

the project is kind of bottlenecked on me, since I have been doing the implementation + migration + theoretical work

UkoeHB: Probably not, threads are rather new

If I am understanding this correctly, maybe UkoeHB & Rucknium and us should have a separate mail discussion about the options. We're definitely interested in further refining our proof techniques on modern applications.

Fantastic :)

CasCremers[m]: sounds good to me

CC: thanks for your work!

yes thank you very much :)

^, let's see if I can even try to read that thing, lol

It's very often just a combination of our theory knowledge and finding the project context for person power

Thank you

Thanks +1

CC: Would you prefer discussion in a separate Matrix room, discussion in this room after the meeting, email, or something else?

Thanks

Thanks +1

thanks for the kind words! feel free to reach out with more questions

We have to leave in 15 mins max; maybe continue over email in first instance?

Thank you for your work!

CC: Email sounds fine. Thank you.

3. for the remainder of the meeting, does anyone have a topic they want to discuss? There may not be enough time for the other agenda items.

MRL #100?

Is this #100?

monero-project/research-lab #100 "Exploring Trustless zk-SNARKs for Monero's payment protocol"

Oh ok

tevador: kayabanerve[m] can you guys summarize where #100 is heading?

I'm currently looking for curve cycles that are compatible with ed25519 and would work with Curve Trees.

I think the next step would be prototyping curve trees in sage with the seraphis key format.

tevador: is that different from the indirect cycle? monero-project/research-lab #100#issuecomment-1443923679

I'm looking for a better cycle that has 255-bit fields instead of 266 bits for obvious reasons (performance)

tevador: the membership proof piece only needs to work on public keys and generator G, it should be independent of seraphis key format

Yes, by seraphis key format I meant Ed25519 keys expressed as K + rG for some scalar r and K is in the accumulator.

gotcha

Will this approach require a transaction format change after Seraphis?

This is actually slightly different from curve trees as described in the paper because the "bottom layer" is on a different curve.

ArticMine[m]: it would require switching out the membership proof, and a bunch of implementation work to handle merkle trees

one thing that gets me excited is multisig should require zero changes

Any idea on tx size for 2 in 2 out?

idk, tevador ?

The Curve Trees demo was around 4 KB for 2/2, with 1 merged proof for both inputs.

Definitely doable from a scaling perspective, given the likely timeframe and Neilsen's vLaw

Note that this also has the range proof in the circuit, which will be separate for us.

we are at the end of the hour so I'll call it, thanks for attending everyone

Thanks UkoeHB !

Thanks

Thanks

Thanks

Thanks

Thanks

tevador: regarding indirect curve cycles, won't they always be less performant due to the ops needed to move over? Have you given any thoughts to the security proof difficulty of such an op (I think just a scalarmul)?

Yes, indirect cycles are less performant, but we don't know how much less.

I think we just won't be able to merge the bottom-most proof. For the higher tree levels, the recursive structure is preserved with the tower-cycle. I don't think the performance penalty will be huge.

Could someone ELI5 these curve cycles and why they are needed for the anonymity set to encompass the whole chain?

<xmrack[m]> "Could someone ELI5 these curve..." <- I'm still building my understanding of the math behind but moving from CLSAG to Grootle proofs means changing proof size from linear to logarithmic (which enables us to have more ring members with the same transaction size) though the verification time is still linear. So far I believe I understood the math behind. Now there are lots of hints indicating that a curve cycle

is the way to have a logarithmic (or even constant) verification time. Which means that we could have a huge anonymity set with very little impact on computation.

But maybe your question was more specific and I dont know how to answer :p

So the verification time is what’s holding us back

If I understood correctly, yes

Got it, thanks

Grootle proof verification time also scales at a much lower rate than CLSAG

you only need ~1 scalar mul per reference element in Grootle (optimized by multiexp), while CLSAG needs several unoptimized muls

Searching online for grootle proof doesnt return much. Is there a paper or article somewhere that I could read

I guess the best is to see the references from Koe's paper

I guess Koe coined this term. Grootle = Groth + Bootle

xmrack[m]: it is a simplified version of the proof used in Triptych and Lelantus Spark

I actually took the code from sarang's Triptych proof of concept

For the security proof I'm planning to copy the lelantus spark proof. It only needs some trivial modifications to match Grootle.