I assume this BP verification speedup also applies to existing transactions? :)

I took a further look at the input timelock rangeproof this morning, and am a bit confused now at the construction. The prover has the original timelock t, his chosen auxiliary time t' and blind y as committed in (t,y) and does a range proof on (t'-t,y). The verifier as the commitment (t,y) and auxiliary time t' and verifies the proof (t'-t,-y). How do the signs between y and -y balance out?

"and verifies the proof (t'-t,-y)" where did -y come from?

Verifier has t' and C(t,y), computes C(t') = t'*H, and verifies range commitment on C(t') - C(t,y)

And isn't that t'*H-t*H-y*G?

sure, P = C(t') - C(t,y) = (t' - t)*H + (-y)*G; the range proof says that the component (t'-t) <= 2^64-1

If we talk about Monero range proofs, the verifier gets C(b,y) = b*H + y*G, sticks it into the bulletproof verifier alongside the bulletproof proof, and it outputs true/false depending on b?<2^64

The prover also uses P = C(t'-t, -y) when they make the bulletproof in the first place

"does a range proof on (t'-t,y)" this looks like your error

I think I got confused because the DLSAG papaer is using k' there in its proof, so RProve(t'-t,k')

but thanks, I think I understand now why it still works out.

mmh, so should that be -k' in the DLSAG paper?

I guess it depends on the commitment you want to do the range proof against.

not sure, haven't looked at the paper

oh I see on page 21 they are making a new commitment for some reason

there are multiple range proofs? why exactly idk

Yeah, I don't see a reason to range proof the original timelock commitment for each output. Only to spend an input do you need a range proof.

I think so too.

Looks like an algebra mistake at the top of pg21, COM(t,k)−COM(t′−t,k′)−t′·H = (k−k′)·G should be C(t,k) + C(t'-k,k') - t'*H = (k + k')*G

which aligns with the sign difference we were talking about

C(t,k) + C(t'-t,k') - t'*H = (k + k')*G where C(t,-k') is the pseudo output commitment

yes, that makes more sense.

selsta: yes, it applies retroactively

Reminder: meeting today at 17:00 UTC

.time

good bot

OK, let's get started with the meeting

The usual agenda: monero-project/meta #454

Logs posted there after the meeting

First, GREETINGS

Hello

Hi

Heya

hi

hi!

I'll wait a couple of minutes for anyone else to arrive

hello

All right, on to ROUNDTABLE

Who would like to share any research of interest?

<cankerwort> Howdy

Research is a big word, but there's an idea

It'd be possible for a recipient to miss spendable funds if this value weren't included properly

is there any potential issue if the sender does not play "nicely" (purposefully fail the scheme) but can nonetheless prove having sent some outputs to the recipient?

same is true for tx pub keys

If the sender doesn't follow the rules, recipient won't see a message showing receipt of funds.

So they'd just ask the sender to make a valid transaction

Yep

Really, the sender hurt themselves

It's similar to if a sender sent a bad commitment,e tc.

(except for the spendability property)

if there is a wallet that doesnt make view tags correctly, it will be a worthless wallet

Bingo

and quickly get patched

<cankerwort> Surely this would be a kind of "fast scan" and if the sender messed it up somehow it would still show up in a normal scan?

yes

They can "DoS" an exchange support easily

Probably hurt them more than the exchange

yeah cankerwort it would be trivial to have fast/normal scan differentiation; the technique is very simple

And wallets don't have to use the method to scan at all if they don't want to

how would fast scan work together with supercop EC ASM? would ASM still bring a scanning speedup?

would there be interesting tradeoff too with a bit more or a bit less than a byte? (changing the 1/256 chance)

The speedup is huge if you're looking for 1-2 addresses, but marginal if you're scanning for 20,000 transactions, right?

my thought is 1 byte is a very standard size, and going lower gets kinda hacky; more than that I can't imagine meaningful improvement

*1-2 transactions

which speedup?

if somehow you own 80% of all tx, then yeah the view tag only helps you for (255/256)*.2 of the rest

<cankerwort> So a scan under this system would scan (1/256 of all transactions) + (actually relevant transactions) - overlap

right

and 'scan' just means perform a few more ec operations

per output

it's actually 1/256 of all outputs, not tx

ah yea, ty

why only one byte? Are two bytes too revealing?

diminishing returns

the marginal scan change from 1 byte to 2 byte view tags is tiny

OK, noted

Any additional questions on this idea at this point?

any objections also?

I like it

yes :)

Hopefully this will reduce the "Y MONERO SO SLO TO SYNC" posts on reddit by 1/256 too

one can only dream

<cankerwort> I suppose generally speaking the fork when transactions get smaller anyway is a good time to introduce these QoL improvements

this looks great

Well, there doesn't seem to be a plan for whether or not to include Janus mitigations, which have been brought up repeatedly before

<cankerwort> or is any reduction in transaction sizes already earmarked for bigger ringsizes?

There is currently no concrete plan to increase the ring size with CLSAG

Note that the move from MLSAG to CLSAG will reduce the typical 2-2 transaction from 2.5 kB to 1.9 kB in size

(absent any other changes)

I think the discussion about Janus and tx extra has made some small progress

Sure, but small progress != PR

:D

Anything else you'd like to discuss UkoeHB_?

dont think so thanks sarang

OK thanks UkoeHB_

Does anyone else wish to share research of interest?

If not, I have a couple of things to share

Hmm, I’m still working on creating a graph formalism for fungibility defects. Made a little bit of progress since last week, but it’s still not quite coherent. Being rigorous is hard. Hopefully will have something to share in a week or two.

I’m cooking up some stuff with Insight too. One of the Fellows put together a patch to prevent coinbase underclaiming now that we’ve moved away from discretized outputs. I just looked at the code, will clean it up and submit for consideration/review.

I want to get more of Insight’s engineers working in our ecosystem! Insigght has been pouring a ton of R & D resources into Polkadot, ICON, Zcash, etc. I really want to leverage my team to contribute to the Monero community at this scale too.

Having a few internal syncs to match Fellows onto open challenges, based on their skills/passions/interests. Hopefully in the next week or two, I’ll be introducing new contributors. :- )

Nice

More details coming soon as those conversation proceed

What kinds of projects?

Meeting with the candidates this week to nail that down based on their skillsets

got it

<cankerwort> And now I need to go find out wtf is Polkadot and ICON all evening

Thanks Isthmus

This PR to speed up Bulletproofs is ready to go: monero-project/monero #6451

Applies retroactively, and has some pretty nice improvements

Saves 25% on a 64-batch of 2-output proofs

Feel free to review if you like

Excellent

<cankerwort> Fantastic news

Second, I've been working hard on a Triptych implementation in the codebase, for more accurate real-world testing

This is the branch: github.com/SarangNoether/monero/tree/triptych

(note that this code is not production-ready, and should not be used in anything important)

Size data comparison: usercontent.irccloud-cdn.com/file/KvolrThG/size.png

<cankerwort> Triptych = Tryptych 2? As in did one version supersede the other?

Verification timing comparison: usercontent.irccloud-cdn.com/file/4CATnXf6/timing.png

This is for Triptych, which requires separate proofs per input (much like MLSAG and CLSAG require)

The timing plot uses performance test data from this branch

The gray lines are centered at the 11-MLSAG point for visual reference

The timing data does _not_ include some unfinished optimizations, or batching, or common input sets within the same transactions

However, it provides an idea of how MLSAG, CLSAG, and Triptych compare generally

Noice

what's the gray line intersection with the Triptych line x axis value?

The vertical gray line is for ring size 11 across all constructions

The horizontal line is the size/time value for MLSAG at ring size 11

(again, just for visual reference)

To help you compare to what we have in place right now

What is the impact on tx size

Each transaction input (not ring element, spent input) requires a single signature, of whatever construction you prefer

Moving from 11-MLSAG to ~32-Triptych would result in no change to signature size

and would result in slightly faster verification

really impressive

<cankerwort> These are awesome improvements! But the plan is not to go straight for Triptych right?

The size data are final; but again, the verification data is still WIP

Triptych (and all other WIP next-gen constructions) require a modification to key images that requires new engineering work for multisig

It's very nontrivial

<[keybase] seddd>: sorry 4 late. just finishing review of CLSAG, will send draft report to sarang when done. no big findings :)

Thanks seddd, much appreciated

<cankerwort> seddd = surae?

<[keybase] seddd>: +1

<[keybase] seddd>: not by a long shot cankerwort

Finally, ledger/trezor support for CLSAG is getting finished

<[keybase] seddd>: (surae wayyyy smarter)

cslashm made a PR that'll be included in the test branch

and ledger has a PR on their side for firmware support that's been completed

<cankerwort> Nice that hw wallets are so proactive compared to how exchanges were with subaddresses

<[keybase] seddd>: ah, that's my next step. still haven't reviewed the ledger-side stuffs. looked at cslashm's PR tho

It's been very nice to see such quick work for ledger/trezor, that's for sure

The goal is to have support ready to go at network upgrade time

really cool numbers

Anyway, that's my report: BP speedup, Triptych WIP data, CLSAG device-specific support

Any other questions for me about those topics?

Are these numbers *likely* similar to Arcturus?

for non-bath

*batch

<cankerwort> what is Arcturus?

Ah, I renamed Triptych-2, both to reduce name confusion and because it operates differently

I never liked the name Triptych-2; it was more of a placeholder

<cankerwort> Noted and appreciated

I am not good at clever naming :/

Anyway, to answer sgp_'s question

Arcturus gives better size scaling

Verification timing will be very similar to Triptych

size already looks pretty good

Still if it can be made smaller then it is an improvement

With Arcturus, you only need one proof/signature per _transaction_ instead of per _input_

Ooooh

The magic of generator reuse means the verification would be similar (if you use common anon sets for Triptych for comparison)

(this difference is why I renamed it)

However, keep in mind that Arcturus relies on a nonstandard hardness assumption

What if any are the disadvantages?

^^

<cankerwort> Is the plan still to get CLSAG audited in time for the next fork? Which are now annually apparently?

This is my understanding

(but it's not my decision)

sarang what's your feeling about whether the multisig issue can be solved without foreign primitives?

As far as I know, we'd need support for general RSA groups for proper multisig with the next-gen constructions

This is for signing only, not verification

(even though it's RSA groups, there are no trusted setup problems, FWIW)

And you're confident about this being a requirement, or it's just that nobody found how to do without yet?

I did a writeup on the multisig question here monero-project/research-lab #72

If you can point out a homomorphic public-key scheme that can use arbitrary prime-order groups, I'm all ears

Yes, it links to code and a description that I worked out

right ^

Paillier encryption is not specifically required

but you need an additively homomorphic scheme

Anyway, I've taken a lot of time in this meeting

Was there anything else of interest to share here?

I made a Rust PoC for including timelock blinding and commitments in transactions. The PoC builds transactions and verifies them with CLSAG signing and the locktime blinding mechanism as described in DLSAG. It looks like the additional size requirements are: input and output commitments, auxiliary (dummy) plaintext locktime, locktime image and a range proof. Thanks to CLSAG, there is no further

increase in the signature size. Contrary to the locktime blinding desription in DLSAG, I think we can spare the range proof on the transaction's output locktime. The main size component therefore is the additional range proof. I also had a discussion about aggregating the locktime range proof in a transaction input with the amount range proof in the output with sarang yesterday (admittedly more

of a lesson from sarang, than a discussion). The gist of it is that in transactions with many outputs and inputs, aggregated range proof verification would become prohibitively slow.

<[keybase] seddd>: oh, awesome! please disregard then, sometimes I derp

TheCharlatan: there should be an additional 32 bytes to the signature

because of the use of an additional auxiliary linking tag

Ah, right I did not include tags in the description :P

However, adding 32 bytes per input is still pretty darn good

Note that verification will take a hit

I have a CLSAG test branch that shows the difference

(but I don't recall the numbers)

TheCharlatan: is your code public?

yes: github.com/TheCharlatan/rs-xmr-cryp/tree/master/timelock

Also: note that Triptych can be easily extended to support this as well, since it's also a d-LRS construction like CLSAG is

nice thanks

<[keybase] seddd>: TheCharlatan: that's awesome! was going to live-code CLSAG in Rust this Saturday. glad to have another reference impl :)

There's also another CLSAG rust implementation available too

<[keybase] seddd>: so nice! thanks sarang :)

(I didn't write that, FWIW)

<[keybase] seddd>: for sure, thanks for the link then :)

The crate-crypto implementation is much nicer, mine is more of a quick script.

TheCharlatan: what would be helpful from this group at this point?

so I don't have a good feel on the boundaries of bulletproof scaling yet. So I think some more data there would be helpful.

OK, I'm glad to help with that if you like

(probably best to save those questions for after the meeting)

yes :)

Thanks TheCharlatan

OK, we're just past the hour mark

Let's move on to ACTION ITEMS

What do folks plan to work on this week (that they wish to share)?

I plan to finish the last Triptych code optimizations, to finalize that timing data

as well as the CLSAG device-specific code integration

Others?

I think Ill write a brief proposal for Janus + view tag + extra field, a package update

The concept seems to be coalescing

<[keybase] seddd>: just working on finishing up testing/manual review of CLSAG, writing the draft report, etc

Yeah, and there are several related ideas there that could happen concurrently

<[keybase] seddd>: _cedes to UkoeHB__

Any last questions or comments before we adjourn?

ArticMine: how is the fee proposal coming along?

just wants to say that was a lot of impressive developments, feels like christmas

^

Still working on the fee part.

All right; we are adjourned! Thanks to everyone for participating

Lots will be posted shortly

Discussions can of course continue :)

I have the rest figured out namely how the LT medium and variable penalty free one will work

<[keybase] seddd>: thanks for the meeting <3

logs posted

medium.com/@j_10523/mobilecoin-code-release-2854ee2f9310 they are implementing a version of RCTTypeBulletproof2

<[keybase] seddd>: mobilecoin w/ new stuff + open-sourcing?! so much goodness, it really is like christmas binaryFate :)

I'm not particularly excited about mobilecoin - sgx powered consensus algorithm and all.

<[keybase] seddd>: yeah, secure enclave is a little meh. riscv also has secure enclave modules, open-hardware style (much better)

<[keybase] seddd>: mb with the PoC on SGX, future gens could be on open-hardware platforms

<[keybase] seddd>: I understand their SGX decision tho (wide deployment, proven tech)

it seems they have moved away from relying on SGX too much, Im not actually sure how critical it is

<[keybase] seddd>: me either UkoeHB_, they aren't using it like ShadowETH (for pseudo-FHE). Plus they do ringct inside the SGX

<[keybase] seddd>: consensus docs: github.com/mobilecoinofficial/mobil…/master/consensus/enclave/README.md

<[keybase] seddd>: federated SCP consensus seems more central/hard-to-change. be nice if there was a fast PoW(-like) consensus algo that met their design reqs

The preprint on hierarchical Groth-style one-of-many proofs has been publicly released: eprint.iacr.org/2020/430

<[keybase] seddd>: (*.*) *soexcite*