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
Murch has quit [Quit: Snoozing.]
Murch has joined #bitcoin-wizards
spinza has quit [Quit: Coyote finally caught up with me...]
spinza has joined #bitcoin-wizards
vpb has quit [Quit: Leaving]
Newyorkadam has joined #bitcoin-wizards
bitcoin-wizards8 has quit [Quit: Page closed]
Murch has quit [Quit: Snoozing.]
Murch has joined #bitcoin-wizards
oopsydanger has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
AaronvanW has quit [Client Quit]
Aaronvan_ has quit [Ping timeout: 245 seconds]
Murch has quit [Quit: Snoozing.]
Newyorkadam has quit [Quit: Newyorkadam]
Murchone has joined #bitcoin-wizards
Murchone has quit [Client Quit]
jcorgan has joined #bitcoin-wizards
borlando has joined #bitcoin-wizards
oopsydanger has quit [Quit: My MacBook has gone to sleep. ZZZzzz…]
<vfP56jSe>
sipa gmaxwell Thank you both for your patient explanations, sorry had to go afk but the above make things much more clear.
Krellan_ has quit [Ping timeout: 268 seconds]
pinheadmz has quit [Quit: pinheadmz]
drexl has quit [Quit: drexl]
<midnightmagic>
:-o
<sipa>
vfP56jSe: yw
rh0nj has quit [Remote host closed the connection]
rh0nj has joined #bitcoin-wizards
ddustin has quit [Remote host closed the connection]
ddustin has joined #bitcoin-wizards
ddustin has quit [Ping timeout: 250 seconds]
_whitelogger has joined #bitcoin-wizards
pinheadmz has joined #bitcoin-wizards
pinheadmz has quit [Quit: pinheadmz]
pinheadmz has joined #bitcoin-wizards
_whitelogger has joined #bitcoin-wizards
pinheadmz has quit [Quit: pinheadmz]
ppisati has quit [Quit: leaving]
bildramer has joined #bitcoin-wizards
jtimon has quit [Ping timeout: 268 seconds]
bildramer1 has quit [Ping timeout: 268 seconds]
ghost43 has quit [Remote host closed the connection]
ppisati has joined #bitcoin-wizards
ghost43 has joined #bitcoin-wizards
go1111111 has quit [Ping timeout: 240 seconds]
pinheadmz has joined #bitcoin-wizards
Krellan has joined #bitcoin-wizards
Krellan_ has joined #bitcoin-wizards
Krellan has quit [Ping timeout: 268 seconds]
go1111111 has joined #bitcoin-wizards
pinheadmz has quit [Quit: pinheadmz]
warren has quit [Ping timeout: 240 seconds]
warren has joined #bitcoin-wizards
rodolfo912 has joined #bitcoin-wizards
Livestradamus has joined #bitcoin-wizards
Livestradamus has quit [Quit: WeeChat 2.2]
elichai2 has joined #bitcoin-wizards
mn3monic has quit [Ping timeout: 252 seconds]
mn3monic has joined #bitcoin-wizards
wildermind has joined #bitcoin-wizards
mn3monic has quit [Ping timeout: 250 seconds]
mn3monic has joined #bitcoin-wizards
setpill has joined #bitcoin-wizards
enemabandit has joined #bitcoin-wizards
mn3monic has quit [Ping timeout: 250 seconds]
mn3monic has joined #bitcoin-wizards
mn3monic has quit [Changing host]
mn3monic has joined #bitcoin-wizards
Belkaar has quit [Read error: Connection reset by peer]
Belkaar has joined #bitcoin-wizards
Belkaar has joined #bitcoin-wizards
Belkaar has quit [Changing host]
TheoStorm has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
spinza has quit [Quit: Coyote finally caught up with me...]
mn3monic has quit [Ping timeout: 252 seconds]
mn3monic has joined #bitcoin-wizards
mn3monic has quit [Ping timeout: 250 seconds]
mn3monic has joined #bitcoin-wizards
spinza has joined #bitcoin-wizards
nephyrin has quit [Ping timeout: 268 seconds]
CryptoDavid has quit [Quit: Connection closed for inactivity]
nephyrin has joined #bitcoin-wizards
AaronvanW has quit [Remote host closed the connection]
drexl has joined #bitcoin-wizards
mn3monic has quit [Ping timeout: 250 seconds]
mn3monic has joined #bitcoin-wizards
zekk has joined #bitcoin-wizards
midnightmagic has quit [Ping timeout: 264 seconds]
KobeShaq has joined #bitcoin-wizards
KobeShaq has quit [Client Quit]
midnightmagic has joined #bitcoin-wizards
Livestradamus has joined #bitcoin-wizards
Livestradamus has quit [Changing host]
Livestradamus has joined #bitcoin-wizards
zekk has quit [Remote host closed the connection]
zekk has joined #bitcoin-wizards
Livestradamus has quit [Quit: WeeChat 2.2]
Livestradamus has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
zekk has quit [Remote host closed the connection]
TheoStorm has quit [Quit: Leaving]
Deinogalerix21 has joined #bitcoin-wizards
davec has quit [Ping timeout: 244 seconds]
davec has joined #bitcoin-wizards
Deinogalerix21 has quit [Quit: WeeChat 2.3]
zekk has joined #bitcoin-wizards
zekk has quit [Remote host closed the connection]
Jackielove4u has quit [Quit: Connection closed for inactivity]
jaromil has quit [Ping timeout: 246 seconds]
zekk has joined #bitcoin-wizards
AaronvanW has quit [Remote host closed the connection]
zekk has quit [Remote host closed the connection]
zekk has joined #bitcoin-wizards
zekk has quit [Remote host closed the connection]
riclas has joined #bitcoin-wizards
zekk has joined #bitcoin-wizards
zekk has quit [Ping timeout: 244 seconds]
zekk has joined #bitcoin-wizards
zekk has quit [Remote host closed the connection]
zekk has joined #bitcoin-wizards
zekk has quit [Remote host closed the connection]
Guyver2 has joined #bitcoin-wizards
_whitelogger has joined #bitcoin-wizards
zekk has joined #bitcoin-wizards
jtimon has joined #bitcoin-wizards
zekk has quit [Remote host closed the connection]
zekk has joined #bitcoin-wizards
zekk has quit [Read error: Connection reset by peer]
zekk has joined #bitcoin-wizards
Jackielove4u has joined #bitcoin-wizards
zekk has quit [Remote host closed the connection]
zekk has joined #bitcoin-wizards
setpill has quit [Quit: o/]
zekk has quit [Remote host closed the connection]
DAM has joined #bitcoin-wizards
zekk has joined #bitcoin-wizards
zekk has quit [Client Quit]
DAM has quit [Quit: Page closed]
zekk has joined #bitcoin-wizards
zekk has quit [Client Quit]
NicknameNickname has joined #bitcoin-wizards
racoonslug has joined #bitcoin-wizards
NicknameNickname has quit [Quit: Page closed]
TheoStorm has joined #bitcoin-wizards
michaelsdunn1 has joined #bitcoin-wizards
michaelsdunn1 has quit [Changing host]
michaelsdunn1 has joined #bitcoin-wizards
pinheadmz has joined #bitcoin-wizards
pinheadmz has quit [Client Quit]
Logicwax has quit [Quit: rm -rf /]
Logicwax has joined #bitcoin-wizards
pinheadmz has joined #bitcoin-wizards
pinheadmz has quit [Client Quit]
dEBRUYNE has quit [Ping timeout: 252 seconds]
pinheadmz has joined #bitcoin-wizards
<vfP56jSe>
sipa: Just realized you were the author of the BIP, an honor! Are additional footnotes expanding a bit on the convo above welcome contribution to the BIP or is it fixed in stone already?
dEBRUYNE has joined #bitcoin-wizards
bildramer1 has joined #bitcoin-wizards
<nsh>
'Foundational Cryptography Framework for machine-checked proofs of cryptography in the computational model.' - https://github.com/adampetcher/fcf
bildramer has quit [Ping timeout: 246 seconds]
<riclas>
bip's are never fixed. you can always suggest improvements vfP56jSe
<sipa>
vfP56jSe: you mean improve the wording, or change the semantics?
<sipa>
riclas: bip-schnorr isn't published yet, we can change anything
<riclas>
yeah i know
<riclas>
his question applies either way
enemabandit has quit [Ping timeout: 272 seconds]
Murch has joined #bitcoin-wizards
<vfP56jSe>
sipa: I mean adding new information or linking to new information like how the residuosity of y equals that of YZ and such
<sipa>
vfP56jSe: the bip does mention that jacobi(y(P)) == jacobi(YZ) if Y and Z are jacobian coordinates of P
<vfP56jSe>
sipa: I see! In the Optimizations section
jaromil has joined #bitcoin-wizards
jaromil has quit [Changing host]
jaromil has joined #bitcoin-wizards
pinheadmz has quit [Quit: pinheadmz]
jtimon has quit [Ping timeout: 240 seconds]
pinheadmz has joined #bitcoin-wizards
TheoStorm has quit [Quit: Leaving]
wildermind has quit [Quit: Connection closed for inactivity]
AaronvanW has joined #bitcoin-wizards
Aaronvan_ has joined #bitcoin-wizards
AaronvanW has quit [Ping timeout: 245 seconds]
Murch has quit [Quit: Snoozing.]
Murch has joined #bitcoin-wizards
elichai2 has quit [Quit: Connection closed for inactivity]
Aaronvan_ has quit []
mint_ has joined #bitcoin-wizards
<vfP56jSe>
Why does not having elliptic curve operations inside the hash help with batch verification?
<sipa>
how would you batch it? :)
<sipa>
batching works by combining multiple equations to test into a single equation which can be verified faster
<sipa>
but if you need to compute e1 = H(EC operations), and e2 = H(EC operations), you can't combine the two sets of EC operations
<sipa>
as it's not just an equation to check, you need the exact output to feed it into the hash
<vfP56jSe>
Ah, I think the part that I'm missing is that you can combine sets of EC operations so that they take less time than if executed individually then added together
<vfP56jSe>
Where can I read up more about that/see examples of that
<sipa>
say you have to check A = xB + yC, and D = vE + wF
* vfP56jSe
listening
<sipa>
and you're given all the points and scalars (including A and D)
<sipa>
you come up with two random number r1 and r2, and instead compute r1*(A - xB - yC) + r2*(B - vE - wF), or r1*A + (-x*r1)*B + (-y*r1)*C + r2*D + (-v*r2)*E + (-w*r2)*F
<sipa>
and check whether the result is 0
<sipa>
with unpredictable values r1 and r2, this will only be true whenever both equations hold
<sipa>
(except with negligable probability)
rh0nj has quit [Remote host closed the connection]
<sipa>
agree?
<vfP56jSe>
agreed!
<sipa>
there is a small extra optimization that you can actually choose r1 or r2 equal to 1; only the ratio between the two needs to be unpredictable
rh0nj has joined #bitcoin-wizards
<vfP56jSe>
right
<sipa>
if some of the points A/B/C and D/E/F overlap (usually the generator occurs in both), it compacts even further, because you'll just sum the relevant scalars
<sipa>
say C=F, then the equation is r1*A + (-x*r1)*B + (-y*r1-w*r2)*C + r2*D + (-v*r2)*E for example
<sipa>
so
<sipa>
then you can use a "multi-exponentiation" algorithm to compute that sum of EC multiplications faster than computing the individual multiplications and summing them
<sipa>
there are various algorithms to do this (quite remarkably), but the most known ones are probably Strauss' algorithm (also known as Shamir's trick), Bos-Coster, and Pippenger's algorithm
<sarang>
It's such a simple and elegant way to go about it
<sipa>
in particular Bos-Coster is quite elegant and accessible
<vfP56jSe>
The BIP doesn't specify which algorithm so people can choose freely?
<sipa>
of course
<sarang>
They all have to give the same result
<sipa>
it also doesn't explain how to do EC multiplication
<sipa>
and it doesn't explain group theory
<sipa>
:p
<vfP56jSe>
"that sum of EC multiplications" = the entire "r1*A + (-x*r1)*B + (-y*r1-w*r2)*C + r2*D + (-v*r2)*E" ?
<sipa>
if you want to write a production-ready version of this you want a whole set of optimizations (more than you can reasonably explain in a BIP), plus development and testing practices that probably take years of engineering time
<vfP56jSe>
So this way, we get the benefit of 1. Being able to sum the relevant scalars like "(-y*r1-w*r2)*C" 2. Use a "multi-exponentiation" algorithm to calculate the sum of EC multiplications like "r1*A + (-x*r1)*B + (-y*r1-w*r2)*C + r2*D + (-v*r2)*E"?
<vfP56jSe>
sarang: Thanks for the link!
<vfP56jSe>
In the BIP, "(s1 + a2s2 + ... + ausu)G" on the LHS of the equality we're testing is an example of #1, and the RHS is an example of #2 as I described above, correct?
<sipa>
correct
<vfP56jSe>
Wow cryptography isn't that intimidating afterall...
<vfP56jSe>
Esp. with help from you guys haha
<sipa>
i think the important part is realizing that you're certainly smart enough to design a system you can't break yourself - but others may
<vfP56jSe>
Any way to mitigate against attacks from others?
<sipa>
yes
<sipa>
peer review
<sipa>
:)
* vfP56jSe
looks forward to the day when he can peer review Schnorr implementations
<sipa>
i mean: never assume that something is secure because it looks safe to you
<vfP56jSe>
Very true
<sipa>
and provable security can help, but despite the name, security proofs don't actually prove something is secure - more accurately they teach you under exactly what sets of assumptions something is secure
<vfP56jSe>
Do people here have any recommendations for other things to read that are as accessible as this BIP?
maluk has quit [Ping timeout: 272 seconds]
<sipa>
vfP56jSe: waxwing has a number of pretty readable guides to several constructions used in cryptocurrencies
<vfP56jSe>
sipa: Right, yeah it doesn't prove anything absolute but at least you can reduce to a set of assumptions that might be simpler
<sipa>
vfP56jSe: yes, but even then - many things can go wrong that circumvent the proof
<sipa>
especially when composing different pieces of cryptography
<vfP56jSe>
Right... sipa do you have links to what specifically you're talking about from waxwing?
<vfP56jSe>
Also I've been trying to understand MuSig... Any prereqs to understanding that?
schmidty has quit [Read error: Connection reset by peer]
schmidty has joined #bitcoin-wizards
<sipa>
understanding that MuSig *works*... you probably know enough if you can read the schnorr BIP
<sipa>
an intuition for why it is secure means you need to be familiar with the style of attacks against these constructions, and see it avoids them
<sipa>
proving why it is secure.... i don't know enough for that
<sipa>
(the paper has a proof, but it's beyond my skill)
maluk has joined #bitcoin-wizards
<sipa>
by "works" i mean: show that if honest users follow the signing protocol, they end up with a signature that the verification eq accepts
<vfP56jSe>
What should I read to "be familiar with the style of attacks against these constructions"
<sipa>
"A Generalized Birthday Problem"
<sipa>
by D Wagner
<sipa>
the MuSig paper includes an explanation of an earlier version of the construction, and an attack based on wagner's algorithm against it