Just to drop a paper: eprint.iacr.org/2022/1070

Post-quantum ring signatures with peer review

kayabanerve: Want to add to MoneroResearch.info?

I wonder how rigorous the ESORICS review process is. Hm.

Ooh that's neat, lattice-based ring signatures have been coming along the last few years

Might be also worth adding MatRiCT & MatRiCT+

To the lit list

Wasn't SIDH lattice based ? That got broken recently AIUI. Though might not apply here.

Nah, that supersingular isogeny stuff is based on a completely different hardness assumption

SIKE getting pwned on one core in an hour was pretty epic

Hey, it's post-quantum, nobody had said anything about pre-quantum!

Rucknium[m]: I'm still unsure how to tackle the huge difference between the empirical PDF from the transparent blockchains and the current gamma DSA in the first 2 hours or so: i.ibb.co/SsvyYdH/xmr-btc.png

tevador: gist.github.com/tevador/50160d160d2…ment_id=4274612#gistcomment-4274612

tevador: the xmr DSA is shifted 20 minutes because we have 10-block-lock (not a comment on your problem, but one thing to keep in mind)

that's not true, source code clearly says that the distribution is placed at the chain tip

actually, my chart is wrong because it doesn't take into account the "RECENT_SPEND_WINDOW" rule, but the discrepancy is too big to be explained by this

tevador: If the gamma selector would pick an output that is less than the 10 block lock, then it is re-allocated to the RECENT_SPEND_WINDOW section of the distribution due to fixes by jberman:

How to tackle the difference? Do you mean "how to fix the current decoy selection algorithm"?

Arguably, there are three levels of increasing complexity:

tevador: oh I guess I forgot about this PR monero-project/monero #7821

1) Use a single, more appropriate and more flexible parametric probability distribution. I have demonstrated this with the Right Pareto Log-normal (rpln) distribution, which seems to be a more appropriate fit and is technically slightly more flexible since it has three parameters compared to gamma's two.

I'm even the one who wrote the comment explaining it... whoops

2) Use a mixture of parametric distributions. So, for example, let f_1 and f_2 be two parametric probability density functions (PDFs) and then the overall PDF could be f(x) = alpha * f_1(x) + (1 - alpha) * f_2(x). I do this here: github.com/Rucknium/OSPEAD/blob/mai…imate-div-target-L_FGT-flavor-1.png

"Log-gamma + F Mixture" is such a mixture that mixes the Log-gamma and F (Fisher) distribution. Maybe this is easier to see the fitted distributions:

3) Use a nonparametric estimate of the distribution through kernel density estimate. The main example of kernel density is this gem: github.com/Rucknium/misc-research/tree/main/Statistical-Monero-Logo

A nonparametric estimate is guaranteed to converge to the true distribution, whatever its shape (even if it is the Monero "M" logo), given sufficient sample size and "tuning parameter" appropriately chosen. For kernel estimation, the tuning parameter is the bandwidth.

??

For OSPEAD I have restricted myself to parametric distributions, which would include (1) and (2) above. The "P" in OSPEAD stands for "parametric".

This is because (1) nonparametric distributions can have greater risk of "overfitting" the true distribution and (2) it is much easier to drop a parametric distribution into the existing Monero code base. A nonparametric approach could be implemented with further research.

If the real-spend-age distribution of XMR is close to the BTC distribution, then our DSA is way off. The BTC data show that 50% of outputs are spent in ~7 hours or less. For our DSA it's over 30 hours.

This is the fixed plot btw: i.ibb.co/QHm2Tnw/xmr2-btc.png

includes the reallocated decoys

Nice to see an independent look at the problem. I arrived at your conclusion a year ago now.

However, Fig. 11 of Moser et al. shows a similar dicrepancy between the BTC and XMR data.

What is needed is a good estimate of Monero's current true spend distribution, which OSPEAD will provide. Looking at the other blockchains helps form modeling strategies, especially for dynamic risk, i.e. forecasting.

“nobody had said anything about pre-quantum!” LOL @mooo

Hmm, in terms of spend distribution representativeness, the question is which blockchain has most similar users, applications, and scale.

For example, Ethereum is probably not as representative because the DeFi applications drive some users to very frequent transacting to poke smart contracts, arbitrage instantaneous inefficiencies, etc.

TBH, I wouldn’t expect Bitcoin to be the closest. That ecosystem has a 5 years head start with a greater number of applications, and additional user demographics, e.g. institutional buy-in for Bitcoin probably orders of magnitude above that of Monero.

What about analysis of spend times in the Zcash transparent pool? Roughly the same age as Monero. Also targets privacy-focused applications and users. Also has less exposure than Bitcoin and Ethereum.

It’s not a perfect proxy, but it might be the least different of available data sets.

Zcash is rarely used as a means of payment.

More places around me that take Zcash than Monero :- P

According to payment processors

Regardless, the project profile difference between Zcash and Monero is probably less than Monero and Bitcoin

The reason I produced the data on BTC&BCH&LTC&DOGE was to see variability across time within each blockchain.

Makes sense, I wonder about interchain correlation too

I thought about DASH, too. But that requires some additional coding due to the coinjoins

Probably not worth the effort

isthmus: I covered that in the doc I linked

Moderated correlation with the tail-oriented summary statistics

Which link? Haven't been following the docs on mobile

3rd and 4th moments :)

This one: rucknium.me/html/spent-output-age-btc-bch-ltc-doge.html

Under "Cross-blockchain correlations of summary statistics across time"

The embodiment of the statistical concept of Kurtosis has been summoned 👀

:- P

Is there a control case for the forecasting?

Like just assuming next observation same as current observation

This is a great writeup btw

Upvote for the cross-chain analysis too

Yes. It is labeled "forecast.accuracy.naive.final.week"

Thanks :)