10:27 UTC

< February 2019 > Su Mo Tu We Th Fr Sa 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

- Console
- #amber
- #arm-graphics
- #arm-netbook
- #bitcoin-wizards
- #bundler
- #cinch
- #coiniumserv
- #coiniumserv-dev
- #crystal-lang
- #cubieboard
- #datamapper
- #discferret
- #elliottcable
- #etnaviv
- #forth
- #glasgow
- #gridcoin
- #gridcoin-dev
- #homecmos
- #huawei-g300
- #imx6-dev
- #imx6-dongle
- #ipfs
- #jruby
- #libreelec
- #libreoffice-ru
- #lima
- #linux-amlogic
- #linux-exynos
- #linux-rockchip
- #linux-sunxi
- #lisp
- #litex
- #logarion
- #maglev-ruby
- #microrb
- #milkymist
- #mirage
- #mutant
- #nanoc
- #neo900
- #nextbsd
- #nmigen
- #ocaml
- #opal
- ##openfpga
- #panfrost
- #Paws
- #Paws.Nucleus
- #picolisp
- #ponylang
- #prjmistral
- #pypy
- #qaul.net
- #qi-hardware
- #racket
- #radxa
- #reasonml
- #rom-rb
- #rubinius
- #ruby
- #ruby-core
- #rubygems
- #rubygems-aws
- #rubygems-trust
- #ruby-lang
- #ruby-rdf
- #sandstorm
- #scopehal
- #skywater-pdk
- #slime
- #soletta
- #solvespace
- #stellar
- #stellar-dev
- #symbiflow
- #systemtap
- #teamhacksung
- #teamhacksung-support
- #tinyqma
- #trilema
- #wallaroo
- #xiki
- #xtompp
- ##yamahasynths
- #yosys
- #zig

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

<vfP56jSe>
sipa gmaxwell Thank you both for your patient explanations, sorry had to go afk but the above make things much more clear.

<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?

<nsh>
'Foundational Cryptography Framework for machine-checked proofs of cryptography in the computational model.' - https://github.com/adampetcher/fcf

<vfP56jSe>
sipa: I mean adding new information or linking to new information like how the residuosity of y equals that of YZ and such

<vfP56jSe>
nsh: I think it's residuoosity: https://en.wikipedia.org/wiki/Quadratic_residuosity_problem

<sipa>
vfP56jSe: the bip does mention that jacobi(y(P)) == jacobi(YZ) if Y and Z are jacobian coordinates of P

<vfP56jSe>
Why does not having elliptic curve operations inside the hash help with batch verification?

<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

<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

<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>
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

<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>
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

<vfP56jSe>
"that sum of EC multiplications" = the entire "r1*A + (-x*r1)*B + (-y*r1-w*r2)*C + r2*D + (-v*r2)*E" ?

<sarang>
https://github.com/bitcoin-core/secp256k1/pull/486 has a neat chart showing the difference between two algorithms

<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>
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>
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

<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?

<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>
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>
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>
the MuSig paper includes an explanation of an earlier version of the construction, and an attack based on wagner's algorithm against it

<nickler>
vfP56jSe: waxwings block https://joinmarket.me and his writeup "from zero (knowledge) to bulletproofs" https://github.com/AdamISZ/from0k2bp/blob/master/from0k2bp.pdf