i have been reading through these curve trees

question 1 : what is an NP-Relation?

this and the next week i am on holidays, so i will be here all the time;)

I dunno, but... does "non polynomial" make sense in this context ?

eprint.iacr.org/2022/756.pdf, page 5 When expressing an NP relation R(x, w)

dunno

<c​ompdec:matrix.org> I think moneromooo is right with the non-polynomial suggestion. The definition seems to require a selection from a subset, NP-relations often arise when a function is defined over sets of subsets. '2-nd order logic' perhaps from what I can gather reading the paragraph in isolation

thx!

question 2 :

in Monero, how many outputs (commitments) are to be proven within a single curve tree ?

<g​hostway:matrix.org> Monero doesn't use curve trees yet. Anyway, you don't necessarily "prove" all outputs, you prove for the path you took in the children

thx!

question 2 :

I know that monero does not use curve trees yet. Now per output we have 15 decoys. Do we have one output per curve tree or?

<g​hostway:matrix.org> Nope, curve trees have a lot more. Fcmp = full chain membership proofs

thx!

question 2 :

Ok, is there supposed to be one curve tree per tx?

MRL meeting here in two hours

<g​hostway:matrix.org> From what I understood and remember, yes, but not exactly. You can see their suggested protocol at the end

Meeting time! monero-project/meta #890

1) Greetings

Hello

<e​ndor00:matrix.org> Hello

hi

<g​hostway:matrix.org> Hello

hi

2) Updates. What is everyone working on?

me: Working on nonstandard fee analysis. Working with endor00 on calculating the security budgets of PoW chains that have experienced malicious deep block re-orgs.

Ive still got at least one bug in the peerlist sharing for ssl. And I may have to drop the ssl auth mode (for now), because I don't see how the peerlist binary file can be updated easily to contain auth values

actually I post the latter to monero-dev, and hopefully get some comments from moneromoo

3) Discussion. What is there to discuss?

endor00, do you want to share your work in progress?

<e​ndor00:matrix.org> Sure: gist.github.com/endorxmr/a13dce62ae1ba4676a1ed0311d96bf07

<g​hostway:matrix.org> That sounds interesting!

<e​ndor00:matrix.org> So far we've looked at a bunch of attacks on different chains to compare the mining incentive [$/s] (aka. "security budget") at the time of the attack

$/s is USD per second

<g​hostway:matrix.org> Measuring what? The mined blocks in in the fork?

<e​ndor00:matrix.org> Some of the coins are pretty small, but the attacks on ETC and BCH (though the latter did not involve a double-spend) happened in spite of their relatively bigger mining incentives

<e​ndor00:matrix.org> Notably, the ETC and BCH attacks had budgets greater than Monero's current budget (also included in the gist)

me: It has been 2 months since I said I would go on a 2-month hiatus. The hiatus has been good to me, I am a lot more productive and motivated these days. Therefore, I am extending my hiatus indefinitely. That does not mean I have abandoned Monero or the Seraphis project, but it does mean my open CCS will take a while to complete (there are about 150 hrs remaining).

I will report in again in 2 months about my status.

Thanks, koe

<p​lowsof:matrix.org> Scared me for a moment there, great to hear koe!

I don't understand, you are on hiatus but still improved productivity?

<e​ndor00:matrix.org> Another important aspect to note, imo, is the fact that both BCH and ETC are both forks of other coins, which had significantly larger (10-100x) mining incentives

^ UkoeHB

<1​23bob123:matrix.org> Yeah hmmm

<e​ndor00:matrix.org> Which meant that they had a significantly larger pool of hashrate that could be redirected at any time to attack them

<1​23bob123:matrix.org> Hiatus means no work

<1​23bob123:matrix.org> Sorry too interrupt

<e​ndor00:matrix.org> Monero, on the other hand, is the largest RandomX coin around - though it does have to deal with the other side of the asic-resistant coin: there is always a massive amount of "potential hashrate" that could be turned on at any time (i.e. all the cpus currently doing anything other than mining)

Maybe looking at the PoW algorithms of these coins is essential? If somebody can just stop to mine BTC for a while and attack BCH, that's very easy to do.

But yeah, you don't have idle supercomputers lying around that you could use to mine RandomX

<e​ndor00:matrix.org> For its budget though, Monero is still a rather big network, for its budget. My "reasonable guesstimate" is that there are ~50k-500k cpus actively mining, right now. Which is still a significant number, considering that we have nearly 1/300th of BTC's budget

The security budget is relevant for the 10 block lock analysis. That's what made me want to compare the security budgets.

a recent estimate was 2 million CPU cores. dunno how many cores per CPU.

<g​hostway:matrix.org> Depends, university students do have that access, and they're humans too... Also, I know of an Alibaba cloud provider that actually does not care if people use his machines to mine

Michele Orru via zksecurity has expressed interest in the Seraphis paper(s) tasks (when scope is confirmed, hopefully a quote can be obtained)

<e​ndor00:matrix.org> if we assume ~10 cores/cpu as a rough order of magnitude, that fits my estimate quite well

plowsof: How do we get scope confirmed?

I do not know, nobody has complained it has approval of koe/jberman/kayaba gist.github.com/plowsof/8cb33e2efe4bf0239927ad3bd92326e0

hyc: I mean more productive in general, on my other stuff.

IIRC, with some of these deep block re-orgs, it is suspected that renting hashpower was involved. There is (was) a lot of spare GPU hashpower up for renting to use against ETC, for example, than there is for using CPUs to run RandomX against Monero.

plowsof: I guess getting tevador's approval would get us to loose consensus. What do you think?

That is what confuses me a bit: How to factor in how *easy* it is for somebody to come up with the security budget, so to say

There have been a few sudden 20-30% overnight increases in total hashpower over the last year. I don't know where that is coming from.

<e​ndor00:matrix.org> > how easy it is for somebody to come up with the security budget

<e​ndor00:matrix.org> ?

Maybe I misunderstand, but isn't that security budget related with the cost of an attack? More security budget, the higher the cost of an attack?

<e​ndor00:matrix.org> Indirectly. The mining incentive/security budget tells us how much money there is on the table for miners. The greater the incentive, the more room there is for more miners to join

<e​ndor00:matrix.org> And we can calculate the maximum size of the network that can be supported for a given budget, assuming a given electricity cost and knowing the highest efficiency mining hardware available

<e​ndor00:matrix.org> If we assume that the attacker doesn't control any hashrate prior to the attack, we can look at rental services such as Nicehash to see if there is enough available to match the network - and if so, how much it will cost to keep up the attack for a certain length of time

My preliminary conclusion: Monero's security budget is uncomfortably close to the contemporary security budget of these coins with these historical PoW deep block reorgs. That suggests setting the tx output lock at 10 blocks isn't an excessive safety margin. (But the 10 block lock doesn't protect against double spend attacks based on block

re-orgs.)

<e​ndor00:matrix.org> Or, alternatively, we can estimate how much it would cost to buy enough mining rigs - but buying hardware quickly becomes a rather prohibitive upfront cost

<e​ndor00:matrix.org> Rucknium also showed me a few papers that calculate the probability of reorging a small number (<10) of blocks, assuming the attacker has *less* than 51% of the nethash

We can do the calculations for more than 10 blocks. Just have to apply the formula. The papers have <10 blocks in tables that are nice to look at

<e​ndor00:matrix.org> i.e. what if a chain analysis company wanted to actively reorg a few blocks to kick someone's tx off and force them to re-spend an output, potentially revealing their true spend?

Interesting scenario, if a bit improbable, seems to me ...

<e​ndor00:matrix.org> And from there, calculate how much it would cost to perform such an attack at different nethash levels

rbrunner: IMHO, that's almost the only scenario that the 10 block lock protects users from.

Becuase "benign" re-orgs haven't been greater than 3 blocks deep. So there would have to be a malicious incentive to cause a deeper re-org.

Yeah, in the abstract. I meant the idea that out of all possible parties a chain analysis company is doing that, for the stated reason of "demasking"

<e​ndor00:matrix.org> According to the papers, causing a reorg of a 1-3 of blocks is not *that* unlikely, even for an entity with 10-20% of the nethash (which is available on Nicehash)

Not with any direct financial gain in mind

Maybe re-read the two MRL issues about the 10 block lock.

<e​ndor00:matrix.org> While attacking a specific tx/output is less likely, there's also the option for a "dragnet" type attack where they just perform this as often as possible to cause as many reorg events as possible and reduce the effective ringsize for other people down the line too

I see

<e​ndor00:matrix.org> I don't have any hard numbers on that yet, but imo 10 blocks is a reasonable number, and reducing that might get us significantly closer to the danger zone

I was hoping that the trend goes toward "10 blocks look excessive", but that does not seem to be the case

<e​ndor00:matrix.org> According to the papers, reorging blocks becomes exponentially harder for every additional block - which means that the reverse is also true: the more we lower the limit, the more exponentially easier it becomes to pull it off

rbrunner: If you look at the minority hashpower share attack success probability tables, you can see the argument for "10 blocks look excessive". But only because if you have enough hashpower share to have a good chance at re-orging, e.g. 8 blocks, then you also have enough to have a good chance at re-orging 10 blocks.

<e​ndor00:matrix.org> For reference: moneroresearch.info/index.php?actio…OURCEVIEW_CORE&id=191&browserTabID=

<e​ndor00:matrix.org> arxiv.org/abs/1912.06412

<e​ndor00:matrix.org> (You can find the probability table on page 10 of the first paper)

If you have 30% of hashpower, an attack will re-org 8 blocks with 10% probability. With the same hashpower, you can re-org 10 blocks with 6.5% probability.

If you have 10% hashpower, attack success probability is 0.007% and 0.001% for 8 and 10 blocks, respectively.

<e​ndor00:matrix.org> Current availability on Nicehash is ~0.16 GH/s for rx, which is ~7.2% of the current nethash

The relationship isn't truly exponential, but it is a concave function.

It is...a regularized incomplete beta function.

<e​ndor00:matrix.org> Plus another 0.4-0.6 GH/s mining on ZEPH, of which some amount is probably from NH (or at least, it was at the beginning when the coin launched)

<g​hostway:matrix.org> Why?

The Rosenfeld (2014) paper doesn't have the regularized incomplete beta function. It has an equivalent formula with a summation. Another paper has the regularized incomplete beta function.

ghostway: Was that "why" meant for me?

<g​hostway:matrix.org> Yep

Grunspan & Perez-Marco (2018). "Double spend races." provides the math proofs if you really want to know why.

<e​ndor00:matrix.org> Should be in the second paper I linked

<g​hostway:matrix.org> Okay, Ill read that, thanks

Satoshi was slightly wrong in his original analysis in the bitcoin white paper

We also have to wonder if 9 months of 1 woman gestating is the same as 9 women gestating for 1 month each.

In other words, if an attacker can acquire 10% of the hashpower for 5 hours, can they also acquire 50% of the hashpower for 1 hour.

<g​hostway:matrix.org> Thanks

We've reached the end of the hour. Let's close the meeting.

<g​hostway:matrix.org> Thank you