Is this just fud?

Thats from tevador

Not fud

Ok so we looked at the updated preprint

And unfortunately this is difficult to estimate how much time it will take.

On first read of the updated preprint, there appear to be areas where they generically offload parts of arguments

So we have a couple of options here.

We can do a partial audit, in the sense that we assume offloaded arguments are safe and correct, and proceed with those assumptions.

Or a full one wherein we go and check each of these offloaded arguments which would be a non-trivial effort.

Are the offloaded arguments unconventional/new?

It is certainly possible to do such a partial audit. And while overall safety can never be guaranteed, in such a case it can _absolutely_ not be guaranteed. And there is a possibility that this nuance would be lost to most. And we predict there would be several areas in the audit whose conclusions would end up being "we are not fully confident in the correctness of this argument or line of reasoning"

A full audit would be necessary in the long run

What do you mean by "offload"? Maybe the full arguments are in the unreleased "full" version: libera.monerologs.net/monero-research-lab/20230419#c238808

So maybe we wait to see the full version then?

Everyone complains about page limits with these conferences. Haven't they figured out appendices yet? 😑

DiegoSalazar[m]: did you mean the offloaded arguments have not been written yet?

yeah let's wait until the full paper is available

What's the time complexity of the multisig?

O(n!) ? O(n(n+1) / 2) ?

I assume UkoeHB is the best to answer

*where n is the amount of missing participants

... well, that defines each sign round as 1, where each sign round is O(n) to amount of participants...

'the multisig'?

The multisig implementation in the Monero codebase

It looks like O(n) sign, with key gen being the issue

the implemented signing is also O(n) since it's round robin

or O(M) I guess

key gen is O(N - M + 1)

UkoeHB: I see it does t rounds, yet what's the complexity of reach round?

*each. Is each round n**2? There's no way this is linear.

key gen is not time-linear per round but signing is time-linear (but not space-linear since you are accumulating partial sigs)

well hmm maybe not

it's some n choose k complexity..

Right. I see key gen does t rounds. In each round, it does n ecdhs.

But it can't be n**2 as that wouldn't be so inperformant. It has to be doing n**2 ecdhs, or relevant to the n choose k function which I'm still interpreting

are you talking about key gen or signing now?

Key gen. Sorry for any confusion. I do believe signing is O(n), but I'll take contradictions.

Key gen appears to do n-t+1 rounds, where each round is an ECDH involving n*round_num keys. I believe it's cubic accordingly.

key gen requires an n choose k pyramid

the most complex round is round N - N/2

Overtly simplified, it's n**3, right?

well N-of-N requires no ecdh, N-1 of N requires N-1 ecdh, N-2 of N requires.. something

Where it's actually

N-T rounds

round_num * n pieces of data

For an actual run time of (n-t+1) * ((n-t/2)+1) * n, I think

For n-of-n, that evaluates to 1 * 1 * n

I'm just looking for a rough complexity to include in a list of details. I'm not going for an academic publication :p If that formula looks right, I'm fine handwaving it as cubic.

... ` n! / (k!(n-k)!)`

Oh god

That's what the boost function returns

Signers! / (round!(signers-round)!)

boost function?

The lambda internally calls boost::math

boost::math documents its binomial coefficient function as following the above formula

well that's the standard formula yep

Tens of thousands of elements 0_o

Thanks for helping me piece it together

I guess complexity would be the largest round

that's why I hardcoded a limit of 16 group members

Yep. I get that

Thanks again for the help :)

sure :)