Updated paper on recursive proof composition: eprint.iacr.org/2019/1021

What would be the privacy ramifications if we allowed txes to be created without a ring signature (or one member), but only for txes that occurred within the past 10 blocks (our current hard-coded limit that you can't respend within)

Which would of course allow clients to blacklist the now probably spent output and not use it in rings

Provably spent*

of course there are obvious privacy drawbacks for the specific transaction

are there efficiency limitations for searching for and avoiding these specific outputs?

If blacklisting the provably spent output handles the privacy issues, and efficiency isn't a concern, this would potentially allow for chained spends within 20 minutes

I suppose one ramification is that if these quick-spend transactions are removed from the typical decoy spend distribution, it would impact the distribution

decoy selection would need to be adapted for the change in user behavior (again)

Would it be worth it for the upside of quick spends?

possibly assuming it was clearly communicated

maybe use ringsize - 1 to be slightly more safe (chose exclusively from past 10 blocks)

the main drawback would be if this feature was widely used

Make it a prompt, but only in situations where there is no alternative

Just received from exchange, sending to Atm (for example)

is there a possibility of wallets stupidly only implementing this less-safe send method?

No available outs other than one within 10 blocks, 'Attempt quick spend? Blah blah reduced privacy, wait X blocks if you want to be safe'

Of course there is

that is a potential severe issue

It would require users to be using their wallet every 20 minutes to be a problem

open up a less-safe method, some idiots (or a system devised by idiots) will always use it

I don't think it's that much of a concern

oh here's a mitigation

if ringsize is (ringsize -1) [or whatever we set it to be identifiable], then consensus rule that all decoys must be within the last 10 blocks or so

I thought that was the assumption to begin with

probably with some padding for latency

No padding.

that's the assumption, but it would need to be a consensus rule

Hmmm

Txes become invalid fast if there's any contention.

so if I try to stupidly spend my output this way a month later, the nodes would reject

But maybe that's what you want if you need to meet a timer...

since at least 1 output will be old

we can also require that these transactions have high fees

Does this seem worth looking into?

but miners may disregard

You can force fees with block penalties, but thats also potentially dangerous

maybe use ringsize + 1 to make larger transactions lol

Then you can't do this if there's very few txes in the last 10 blocks.

Or the last 8. Since you want your tx not to become invalid before it has a chance to get mined.

I forget what the reasons for the 10 block thing are, beyond "reorgs make everyone's life harder". Since that one would be (mostly ?) fixed by signing for output keys rather than indices.

It was a privacy issue

Because people ended up using txes in mempool iirc

As ring members

I suppose it'd still be vulnerable to signig with an output that gets reorg'd out by a double spend...

Can you expand on that ? Unmined txes can't be used since you don't know their outputs' indices yet...

Or I guess you can guess and spray :P

🤔

They actually did that ?

I can't recall now

It's been so long since I last thought about the 10 block window

it was some privacy and reog combination

transactions can't be confirmed if they include outputs that don't exist on another chain

decoys complicate the process, so the window helps things settle down

(as far as I understand it)

Isthmus worked on some numbers for reorg lengths under "normal" network conditions

needmonero90: my gut feeling is that if this feature were implemented, the nodes would need to check that all outputs of this transaction type are from the last 20 blocks

and we can't overlap the windows, I suspect, so that would mean doubling the length of time before you can 'securely' spend

definitely a tradeoff

no I am assuming the windows overlap

hm

*ideally* a wallet would spend correctly after block 10

but due to latency, this would only be consensus-imposed after block 20-ish

in some ways, segregating user behavior into these classifications *may* improve privacy

just like I believe separating coinbase outputs will improve user privacy for >95% of users

but in this case I think the privacy benefits are less clear, since we would be permitting behavior that isn't currently allowed. How would it be used? How many people would use it? etc

I don't yet know if I want to be a champion for this idea and research, but obviously if the tradeoff is deemed to be acceptable, that would provide a huge UX improvement

Documentation write-up for transaction proofs, intended for Zero to Monero: gist.github.com/SarangNoether/99a24506772db5ce25e89500d9317e3e

Accounts for the new InProofV2 and OutProofV2 from monero-project/monero #6329

[keybase] <surae>: Hoooooo

Hello suraeNoether surae

When is your Triptych talk?

[keybase] <surae>: In about 40

[keybase] <surae>: I think

[keybase] <surae>: Oops, lunch first, then second talk after that

Neat! Are the talks recorded/posted/streamed?

Also, any last-minute questions or details you'd like clarified for the talk?

(I didn't review any further changes you made to the Overleaf presentation since we talked last)

nope, i'm good. i believe that the talks will be made available online...

allegedly at fields.utoronto.ca but I don't think they'll be posted today.

I'll be watching closely :)

[keybase] <surae>: National archives of Korea appears to have invented a rather convoluted blockchain scheme for official record keeping.

[keybase] <surae>: First few talks were on crypto protocols and quantum computing. These two are from librarians, then me again.

[keybase] <surae>: It's a curious scheduling choice

[keybase] <surae>: Wait: are these streaming??

is the korean blockchain PoW?

[keybase] <surae>: Not clear, I am going to ask why not use a DB with a public facing bulletin board

[keybase] <surae>: I would guess it's staked since it's governmental

[keybase] <surae>: Seems more like a chain of signatures instead of a blockchain, not sure what a fork means :/

[keybase] <surae>: I'm not going to ask my question because he has already gone over time

Initial timing estimates coming in for new protocols... running the numbers now

And the winner is... Triptych!

And the crowd goes wild!

The post-BP chain would take the following number of hours to verify (spend, balance, and range proofs only):

rct3-multi 4.12

rct3-single 4.60

triptych-multi 3.68

triptych-single 3.94

(this is for ring=11, as an initial test)

I need to get additional timing data to compare to estimates for CLSAG/MLSAG

very cool

let's just go all-in on triptych already

I need an excuse to visit that brewery

Interestingly, there are some changes at higher ringsize, where Triptych still wins but the RCT3 variants swap

The same chain region for ring=256 would take about 20 hours to verify

(verification is linear in the ring size)

This assumes per-block batching, BTW

can you do better than per-block?

Next up is to use larger fixed batches, and pull some operation timing data to compare to CLSAG/MLSAG (which use different ops)

^^ yes

The current default is per-block, so I coded that in

Once I have the added functionality, I'll post the code for the analysis tool

the linear verification time is not ideal :(

but this is still exciting

Yeah, can't do better than that (up to a logarithmic factor from multiexp)

You could get crazier and start factoring in common ring epochs across a batch due to the selection algorithm

sarang: What is the hardware for this kind of timing?

It's a 2.1 GHz Opteron

Same machine as all the timing data I've reported earlier

ok

It's straightforward to run perftests for multiexp and use those timings in the tool, though

at large N, an N-multiexp is quite linear

so the estimates are pretty reasonable

[keybase] <surae>: Agreed

Agreed to which part? =p

Anyway, I'll get some better comparison data and run plots over various ring sizes

I'm so excited for this data

Yeah, the tool is finished for all the Triptych and RCT3 variants already... it's just a matter of running it across the whole parameter space of interest

Which IMO is probably N=128 to N=1024

i.e. 1 and 2 orders of magnitude higher than current

I should have the plots ready to go by tomorrow's meeting

[keybase] <surae>: Agreed re: going hard on triptych

It doesn't win for size, but it wins for time

Heh, surae I thought you were agreeing to "at large N, an N-multiexp is linear"

I mean, sure

Given size tends towards constant with increasing ring size, I think time is the most important. Even discounting arguments about physics.

FYI this is the dataset, courtesy of n3ptune and friends: github.com/noncesense-research-lab/…ero_transaction_io/tree/master/data

Here is the tool (still WIP): github.com/SarangNoether/skunkworks/blob/sublinear/estimate.py

Todo: include CLSAG/MLSAG timing estimates

Todo: modify for arbitrary batch sizes

FWIW both Triptych variants are ~12% faster than RCT3-single at N=256

and ~30% faster than RCT3-multi at N=256

RCT3-multi really suffers at large ring size because of its padding requirements

hence the single and multi variants flipping

Anyway, anyone is welcome to play around with the tool and dataset if they like

It doesn't cache results for common transaction structures (for simplicity), so it's pretty slow

but it'll do a full-chain run in under a minute

Rather, a post-BP chain run (for better protocol consistency)

hooray triptych!

lemme make that PR and call it a day

Who knows? Perhaps a future version of Omniring will win

It's still under development

Triptych has the best name for marketing

well, that brings up the concern of the cutting edge.... there's always gonna be something in development

What about the mathematical difficulty / complexity of the protocols, are there obvious differences between the protocols?

RCT3 uses a proving system based on Bulletproofs

Triptych uses a proving system based on one by Groth and Kohlweiss

Neither is crazy complex

[keybase] <surae>: I feel like triptych is less prone to implementation problems

[keybase] <surae>: But that's not quantifiable

[keybase] <surae>: It's probably my own familiarity with it, not a comment on the complexity

Bigger batching shaves maybe an hour (out of 20) off full verification time for Triptych

so only about 5% over per-block

[keybase] <surae>: That's significant

[keybase] <surae>: Since we have an exponential trade-off between time and speed

Yeah, but not as significant as I'd hoped

[keybase] <surae>: Time and space*

*spacetime

batching code pushed

in case you're playing along at home

20hrs or 19hrs is quite a lot

[keybase] <surae>: Wait: sarang are you saying the entire chain as-is would take 19 hours to sync if it had been triptych the whole time?

The post bulletproofs chain

I've definitely synced full nodes recently in less than 20 hours. Am I comparing the wrong numbers?

Yes

One sec

good :)

sgp_: without checkpoints?

UkoeHB_: probably not

just default run and see

default is with checkpoints

how much faster is it with checkpoints? I thought Bitcoin removed them

significantly faster

lopp recently tested 1 day 2 hours 40 mins with `max-concurrency=12 fast-block-sync=0 prep-blocks-threads=12`

sounds right, AFAIK he used strong hardware

my computers are always limited by the CPU

--block-download-max-size might help, default is... 250 MB IIRC. If you have the RAM, setting it higher would allow early download.

how easy is it to test the available ram and increase that automatically?

Not easy.

You start getting in the way of the OS caching.

sgp_ etc: the numbers I gave are estimates about taking the entire existing post-BP chain's input-output distribution and applying it instead to different protocols

Notably, at higher ring sizes

They'll be useful for comparison, but I would not use them as hard-and-fast expectations for actual sync time

[keybase] <surae>: Sgp_etc would be a good v2.0 username

[keybase] <surae>: So uh anyone in Toronto bored?