sipa changed the topic of #bitcoin-wizards to: This channel is for discussing theoretical ideas with regard to cryptocurrencies, not about short-term Bitcoin development | http://bitcoin.ninja/ | This channel is logged. | For logs and more information, visit http://bitcoin.ninja
adams__ has joined #bitcoin-wizards
runeks has joined #bitcoin-wizards
PsychoticBoy has joined #bitcoin-wizards
rusty has joined #bitcoin-wizards
Ylbam has quit [Quit: Connection closed for inactivity]
ananteris has quit [Ping timeout: 258 seconds]
ananteris has joined #bitcoin-wizards
PaulCapestany has quit [Ping timeout: 240 seconds]
PaulCape_ has joined #bitcoin-wizards
pro has quit [Ping timeout: 268 seconds]
Alina-malina has quit [Ping timeout: 255 seconds]
Alina-malina has joined #bitcoin-wizards
Onee has joined #bitcoin-wizards
Noldorin has quit [Quit: My MacBook Pro has gone to sleep. ZZZzzz…]
<yoleaux>
[POLL] Perfectly hiding vs perfectly binding : Mailing list archive : mimblewimble team in Launchpad
juscamarena_ has joined #bitcoin-wizards
harrymm1 has joined #bitcoin-wizards
harrymm has quit [Ping timeout: 260 seconds]
rmwb_ has joined #bitcoin-wizards
rmwb has quit [Ping timeout: 240 seconds]
molz_ has quit [Ping timeout: 240 seconds]
moli_ has joined #bitcoin-wizards
tromp has quit [Remote host closed the connection]
DougieBot5000_ has joined #bitcoin-wizards
rmwb has joined #bitcoin-wizards
nikuhodai_ has joined #bitcoin-wizards
Onee has quit [Ping timeout: 240 seconds]
Dyaheon- has joined #bitcoin-wizards
Belkaar_ has joined #bitcoin-wizards
Belkaar has quit [*.net *.split]
rmwb_ has quit [*.net *.split]
DougieBot5000 has quit [*.net *.split]
Dyaheon has quit [*.net *.split]
sn0wmonster has quit [*.net *.split]
instagibbs has quit [*.net *.split]
Madars has quit [*.net *.split]
nikuhodai has quit [*.net *.split]
Imelda has quit [*.net *.split]
aem has quit [*.net *.split]
andytoshi has quit [*.net *.split]
chjj has quit [*.net *.split]
Hunger- has quit [*.net *.split]
aem has joined #bitcoin-wizards
aem has quit [Changing host]
aem has joined #bitcoin-wizards
instagibbs has joined #bitcoin-wizards
andytoshi has joined #bitcoin-wizards
nikuhodai_ is now known as nikuhodai
qpm has quit [Ping timeout: 264 seconds]
chjj has joined #bitcoin-wizards
Madars has joined #bitcoin-wizards
qpm has joined #bitcoin-wizards
aem is now known as aem
tromp has joined #bitcoin-wizards
sn0wmonster has joined #bitcoin-wizards
tromp has quit [Ping timeout: 260 seconds]
talmai has joined #bitcoin-wizards
DougieBot5000_ is now known as DougieBot5000
legogris has quit [Remote host closed the connection]
legogris has joined #bitcoin-wizards
benthamshead has quit [Remote host closed the connection]
tromp has joined #bitcoin-wizards
TwoFiveSuited has joined #bitcoin-wizards
TheSeven has quit [Disconnected by services]
[7] has joined #bitcoin-wizards
tromp has quit [Remote host closed the connection]
rusty has quit [Ping timeout: 240 seconds]
Giszmo has quit [Quit: Leaving.]
anon616 has quit [Remote host closed the connection]
rmwb_ has joined #bitcoin-wizards
Dyaheon- has quit [Ping timeout: 264 seconds]
anon616 has joined #bitcoin-wizards
Dyaheon has joined #bitcoin-wizards
rmwb has quit [Ping timeout: 264 seconds]
bildramer1 has quit [Quit: "I suspect that in general big mistakes cause defeat much more often than excellent moves cause victory." -Dominic Cummings]
PaulCape_ has quit [Quit: .]
PaulCapestany has joined #bitcoin-wizards
UnrealLife has joined #bitcoin-wizards
TwoFiveSuited has quit []
mol has joined #bitcoin-wizards
moli_ has quit [Ping timeout: 240 seconds]
talmai has quit [Quit: mining]
tromp has joined #bitcoin-wizards
RubenSomsen has joined #bitcoin-wizards
tromp has quit [Ping timeout: 260 seconds]
rmwb has joined #bitcoin-wizards
Ylbam has joined #bitcoin-wizards
rmwb_ has quit [Ping timeout: 260 seconds]
mn3monic has joined #bitcoin-wizards
mn3monic has joined #bitcoin-wizards
mn3monic has quit [Changing host]
afk11 has quit [Remote host closed the connection]
afk11 has joined #bitcoin-wizards
Alina-malina has quit [Changing host]
Alina-malina has joined #bitcoin-wizards
Onee has joined #bitcoin-wizards
harrymm1 has quit [Remote host closed the connection]
harrymm has joined #bitcoin-wizards
cluckj has quit [Ping timeout: 240 seconds]
harrymm has quit [Remote host closed the connection]
<oleganza>
Do i understand that ECDSA requires to publish `s` value, but it's never used, only `s^-1` is actually used? So verifiers must do the scalar inversion each time?
<sipa>
indeed
<oleganza>
How much slower ECDSA is compared to libsecp256k1's Schnorr signature verification (in whichever form it is right now)? Meaning, how much overhead scalar inversion adds?
<sipa>
within a few %
<sipa>
as the inversion is on the verifier side, it can be done with a variable-time algorithm
<oleganza>
btw, how many schnorr sigs per second libsecp256k1 verifies right now?
<sipa>
on typical x86_64 hardware a verification is around 250k cycles
<sipa>
so around 13000 verification per core, at 3GHz
<gmaxwell>
oleganza: zero because there is no schnorr signature code in the codebase anymore (we dropped that expirement after realizing we needed a different construction).
<oleganza>
different than vanilla Schnorr?
<sipa>
there is no 'vanilla' Schnorr
<oleganza>
well, i mean, "simplest one"
<gmaxwell>
oleganza: the difference from the inversion was mostly introduced because the construction we had eliminated another inversion avoidance optimization that our ecdsa code has.
<oleganza>
gmaxwell: i'm sorry, i probably confused you with inversion question
<gmaxwell>
No, I don't think you did.
<sipa>
oleganza: performance wise, none of this matters
<oleganza>
i know there's no inversion required in schnorr sig, i asked about ECDSA vs Schnorr
<gmaxwell>
oleganza: That isn't true.
<sipa>
Schnorr and ECDSA are approximately the same performance
<oleganza>
gmaxwell: how so? verification is `e =?= Hash(s*G - e*P)`, no?
<sipa>
oleganza: 'our' Schnorr construction publishes R and s
<gmaxwell>
oleganza: A normal construction of a schnorr signature has a modular inversion (wrt P) in the reprojection of the R' back to affine coordinates.
<oleganza>
R being s*G-e*P, right?
<sipa>
because that's batch verifiable
<gmaxwell>
e,s = moronic schnorr mostly.
<gmaxwell>
:P
<oleganza>
gmaxwell: why? :)
<sipa>
oleganza: the (e,s) version cannot be batch verified
<gmaxwell>
the only reason you generally see people use e,s is because of earlier incorrect security reasoning that said that e could be half size. Amongh other downsides it makes it infeasable to do batch validation.
<oleganza>
ah, i see.
laurentmt has joined #bitcoin-wizards
<oleganza>
half size == 128 bits vs 256 bits?
<andytoshi>
gmaxwell: the (e,s) form can be extended to a proof-of-equality-of-DL with no additional space requirement
<sipa>
in non-EC Schnorr, the (e,s) version is smaller
<sipa>
because e is a hash rather than a group element
<gmaxwell>
andytoshi: for the same reason it's useful in the borromean ring signature, right.
<oleganza>
sipa: got it
<oleganza>
easy to forget there is life before ECC
<oleganza>
(j/k)
<sipa>
oleganza: QC is going to hurt.
<gmaxwell>
In any case regardless of all this verification normally has an inversion in the reprojection of the point. But our ECDSA does not have that inversion. But the trick we use to eliminate it would permit signatures which are not batch verifyable.
<sipa>
gmaxwell: it does
<sipa>
gmaxwell: oleganza is talking about a different inversion
<gmaxwell>
jesus please
ratbanebo has joined #bitcoin-wizards
<oleganza>
i was talking inversion 1/k modulo group order, not in the undelrlying field
<gmaxwell>
Stop telling me that I don't know what I'm talking about for a freeking minue!
<sipa>
the naive ECDSA verifier has 2 inversions (a scalar one and a field one)
<sipa>
we eliminated the field inversion but not the scalar one
<gmaxwell>
If you don't stop I am parting the channel.
<sipa>
ok.
<gmaxwell>
Oleg is asking about the relative perfomance of schorr vs ecdsa, and noting that schnorr can avoid the input inversion... so it should be faster.
<sipa>
yes
<gmaxwell>
And I was _trying_ to explain that there are two inversions to talk about: and our ECDSA eliminates the output one. While the schnorr construction natrually didn't have the input one.
<gmaxwell>
The result is that the performance is very close to identical.
<gmaxwell>
If our schnorr construction eliminated the output too (which was incompatible with batch verify) then it would be about 4% faster-ish than the ECDSA.
<sipa>
ok, agree with all that :)
<gmaxwell>
Though we also now have another construction that can replace that inversion with checking for quadratic residuosity which should be in between.
<gmaxwell>
(so again, faster than ECDSA but maybe only 2% faster)
<sipa>
except it requires a complicated algorithm to implement
<gmaxwell>
yea yea. well if you want it to be fast. :P
<sipa>
and the naive implementation of quadratic residue checking is similar in speed to the naive inversion
<gmaxwell>
right.
<sipa>
in any case:
<sipa>
21:43:29 < sipa> Schnorr and ECDSA are approximately the same performance
ratbanebo has quit [Ping timeout: 268 seconds]
<gmaxwell>
in any case, thats all I wanted to point out. Thats why they are the same performance, even though it seems surprising because the schnorr has one less inversion, the batchability gives it one more. If you didn't care about that (you usually should since it's a large speedup), then the schnorr would be faster by the speed of an inverse, which is perhaps 4%.
<gmaxwell>
so hopefully this should answer why we're saying the schnorr was not faster though intuition says it should be. :P
UnrealLife has joined #bitcoin-wizards
MaxSan1 has quit [Ping timeout: 246 seconds]
<sipa>
actually, iirc, it's worse even
<sipa>
because to have batch-verifiability you need to report the full R point
<sipa>
which either means 32 bytes extra for the Y coordinate, or an extra square root for computing Y from X
<sipa>
and a square root is even slower than an inverse
UnrealLife has quit [Client Quit]
<gmaxwell>
no one wants the extra 32 bytes, so you get the sqrt in the batch verifier but you don't have it in the non-batch verifier.
<gmaxwell>
in the non-batch verifier you construct R' and then convert to affine and check it's sign agress with the signature. (or in the code we had, that its sign had a particular value)
<oleganza>
gmaxwell: because you can just say "i don't care about Y coordinate" in non-batch?
<oleganza>
ah, i see
<sipa>
gmaxwell: right!
<gmaxwell>
oleganza: if you don't care about it in non-batch someone can give you an invalid signature that a batch validator would reject but you wouldn't. so you have to check agreement.
<oleganza>
makes sense
<oleganza>
that's a pretty deep explanation, thanks sipa & gmaxwell.
<gmaxwell>
sipa: the reconstruction of R still only takes one inversion due to the montogomery trick but two more field multiplies.
MaxSan has joined #bitcoin-wizards
MaxSan has quit [Read error: Connection reset by peer]
MaxSan has joined #bitcoin-wizards
Nightwolf has quit [Remote host closed the connection]
tromp has joined #bitcoin-wizards
tromp has quit [Ping timeout: 268 seconds]
Nightwolf has joined #bitcoin-wizards
ratbanebo has joined #bitcoin-wizards
ratbanebo has quit [Ping timeout: 240 seconds]
ratbanebo has joined #bitcoin-wizards
ratbanebo has quit [Remote host closed the connection]
MaxSan has quit [Ping timeout: 260 seconds]
MaxSan has joined #bitcoin-wizards
renlord has joined #bitcoin-wizards
renlord has quit [Client Quit]
juscamarena_ has quit [Ping timeout: 268 seconds]
jannes has quit [Quit: Leaving]
superkuh has quit [Remote host closed the connection]