secparam: I ran multiple simulations of get_outs in my client making sure to isolate the gamma outputs. Here were my results attempting get_outs 100k times

Where did you report that bug, jberman?

I don't see an issue or mention in #monero-dev:monero.social and want to make sure its appropriately shared and reviewed.

DM'd moneromooo, luigi and fluffy. Talked about it with moneromooo, and ran it by him before sharing it here. He suggested sharing in -dev too. Should I take it there also?

dev is a good place if you're making these PRs, yup :)

<jberman[m] "DM'd moneromooo, luigi and fluff"> Great! Yeah, that would be a good idea if moneromooo and co are game with it being public.

Sounds good

jberman that line in the code, "average_output_time = DIFFICULTY_TARGET_V2 * blocks_to_consider / outputs_to_consider;", calculates time in seconds so it should be ok with integer division

actually it depends on what range "outputs_to_consider" covers... Need to step through it in the debugger to find out

sech1 it is supposed to be computing the average rate that outputs were added to the chain over up to the most recent 1 year period

"DIFFICULTY_TARGET_V2 * blocks_to_consider" is definitely in seconds. The questionn is, what's the resulting value there (average_output_time)

It does feel a bit embarrassing that I didn't notice this integer division issue either

if it's 1 or 2 then it must be computed as double

but if it's ~164000 (1.9 days in seconds) then it's ok

outputs_to_consider should be the total number of outputs in the last year's worth of blocks

then it should be computed as double

How UkoeHB is reading it is how I read it too^

Using integer division, you end up rounding the true average of ~1.9 seconds per output over the past year down to 1 second, which is a significant difference from the true average, that then flows into the output selection in pick(). I can’t see why it would be expected to have such a large difference from the true average

Plus, just taking a step back, it wouldn’t make sense for average_output_time to be a double if the intent was to do integer division there

I think this algorithm was built when tx volume was way lower, so it must not have affected test runs

Ya the more outputs, the worse the impact on the calculation downstream

*the more often outputs appear

once it got sub 5 seconds per output on average, it got bad

hmm, won't we get 0 there eventually, if we have a lot of transactions for more than a year?

more than 120 outputs per block on average

Yep, probably would’ve been discovered naturally soon

Through normal use

division by zero on line 1031, classic

Ya seems clients would start failing to construct tx’s

should be easy to fix, right? was planning a new release anyway

Super easy: j-berman/monero #3/files

Waiting on repo rights to submit a PR, but I don’t care if it’s not me and you wanna release in the meantime

this will however change output selection algorithm and we'll have two different versions for quite a while. There will be probably privacy implications

two anonymity "puddles" instead of one

for quite a while = until next hardfork

That’s true, maybe it does makes sense to hold off

wrong output selection hurts privacy already now though

I think the benefits of the fix outweigh it

pools (miner payouts) and exchanges (deposits/withdrawals) will update quickly and then we'll have big enough anonymity set for the new output selection

besides, division by zero bug won't wait

so if I'm reading the code right, this bug makes all decoy outputs older than they should've been (1.9x older), which makes "newest output = real spend" heuristic work better

in this case, it should be fixed asap

hmm the odd thing is secparam[m] 's results which showed most decoys at 20 blocks, which jberman[m] seemed to corroborate

hmm, I read the code wrong. "uint64_t output_index = x / average_output_time;" -> here the bug makes it bigger, but...

"output_index = num_rct_outputs - 1 - output_index;" -> here it becomes smaller than it should've been, so it skews selection to newer outputs?

looks like it

average_output_time is underestimated -> x / average_output_time is overestimated -> num_rct_outputs - 1 - output_index lands you with an output index further back in the chain

are rct_offsets ordered from newer to older?

<UkoeHB "hmm the odd thing is secparam 's"> ya, I think more rigorous analysis taking this into account and comparing to observed distributions over block intervals since this was introduced could provide more clarity. was introduced ~April 2019

the final value of output_index is smaller because of the bug, so it chooses smaller index from rct_offsets

`average_output_time` is smaller (rounded down), which means `output_index` is larger on initial value (division), which means its final value is lower, so it causes the algorithm to select a lower block

that^

UkoeHB how are rct_offsets ordered? From lower (older) block to higher (newer)?

yea that's how they're ordered

I only found this code: github.com/monero-project/monero/bl…ryptonote_core/blockchain.cpp#L2304

which suggests it's in increasing height order

so after untangling all that, the bug skews to older outputs

if we were to get an on-chain distribution since this was introduced, and we observe something like dual peaks, one at ~10 blocks and one further right, then that would suggest the newest heuristic would work well and the left-most peak is likely from real outputs. But that's not the only cause of twin peaks. The less bad cause would be the point at which the average output time shifted from 2 to 1, that would cause twin peaks as

well

the fix is in PR 7798 and 7799

jberman[m]: can you redo your get_outs simulation post-fix?