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
Emcy has joined #bitcoin-wizards
nba_btchip has quit [Ping timeout: 258 seconds]
Emcy_ has quit [Ping timeout: 244 seconds]
othe has quit [Ping timeout: 258 seconds]
nba_btchip has joined #bitcoin-wizards
othe has joined #bitcoin-wizards
Emcy_ has joined #bitcoin-wizards
Noldorin has joined #bitcoin-wizards
Emcy has quit [Ping timeout: 258 seconds]
Emcy has joined #bitcoin-wizards
Emcy_ has quit [Ping timeout: 265 seconds]
byteflame has joined #bitcoin-wizards
<nsh>
gmaxwell, what's the actual logical form of the statement proved in the rangeproof implementation? something about a bunch of digits base 4 and a mantissa?
<sipa>
it proves that the commitment equals some number times G plus a number in the range [0..2^32-1] multiplied by H, without revealing either
<sipa>
the range is configurable
<nsh>
yeah, but it actually proves a statement based around a deconstruction of the value in some weird way
<nsh>
or maybe i misunderstood something
<sipa>
yes, you pick some random points C0, C1, C2, ..., whose sum equals the commitment C
<sipa>
for each of them you pick 2 bits of the value, so v0 + 4*v1 + 16*v2 + ... = value
* nsh
nods
CrazyTruthYakDDS has joined #bitcoin-wizards
<sipa>
then you reveal C0 + v0*H, C1 + 4*v1*H, C2 + 16*v2+H, ...
<sipa>
you call those C0', C1', C2', ...
<nsh>
hmm
<sipa>
then for C0', it is true that you know the DLP for either C0' (if v0==0), C0'-H (if v0==1), C0'-2H (if v0==2) or C0'-3H (if v0==3)
<sipa>
(that DLP is just the DLP of C0)
<sipa>
so you give a ring sig of the message with the 4 pubkeys (C0', C0'-H, C0'-2H, C0'-3H)
* nsh
nods
<sipa>
which reveals you know the DLP for either of those, but not which one
<sipa>
then you do the same for C1', you know the DLP for either C1', C1'-4H, C1'-8H, C1'-12H
<sipa>
etc
<nsh>
right
<nsh>
ty
pro has quit [Quit: Leaving]
Ylbam has quit [Quit: Connection closed for inactivity]
Giszmo has quit [Quit: Leaving.]
proslogion has quit [Ping timeout: 244 seconds]
dnaleor has quit [Read error: Connection reset by peer]
Noldorin has quit [Quit: My MacBook Pro has gone to sleep. ZZZzzz…]
dEBRUYNE has quit [Quit: Leaving]
Alopex has quit [Remote host closed the connection]
Alopex has joined #bitcoin-wizards
proslogion has joined #bitcoin-wizards
dnaleor has joined #bitcoin-wizards
rusty2 has joined #bitcoin-wizards
blockzombie has quit []
roconnor has quit [Quit: Konversation terminated!]
byteflame has quit [Ping timeout: 244 seconds]
mryandao has quit [Changing host]
mryandao has joined #bitcoin-wizards
rusty2 is now known as rusty
btcdrak has joined #bitcoin-wizards
mdavid613 has quit [Quit: Leaving.]
<Cloudflare>
mryandao is not a proper bitcoin wizard
proslogion has quit [Ping timeout: 250 seconds]
Alopex has quit [Remote host closed the connection]
Alopex has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 240 seconds]
NewLiberty has quit [Ping timeout: 258 seconds]
wizkid057 has quit [Disconnected by services]
wizkid057 has joined #bitcoin-wizards
da2ce7 has quit [Ping timeout: 250 seconds]
wipogee has quit [Read error: Connection reset by peer]
Cloudflare has quit [Ping timeout: 250 seconds]
xissburg has quit [Ping timeout: 258 seconds]
draynium has quit [Ping timeout: 250 seconds]
wipogee has joined #bitcoin-wizards
liviud has quit [Ping timeout: 250 seconds]
ryan-c has quit [Ping timeout: 250 seconds]
go1111111 has quit [Ping timeout: 250 seconds]
mappum has quit [Ping timeout: 258 seconds]
draynium has joined #bitcoin-wizards
Cloudflare has joined #bitcoin-wizards
Cloudflare has quit [Changing host]
Cloudflare has joined #bitcoin-wizards
ThomasV has joined #bitcoin-wizards
ruby32 has joined #bitcoin-wizards
liviud has joined #bitcoin-wizards
ryan-c has joined #bitcoin-wizards
da2ce7 has joined #bitcoin-wizards
mappum has joined #bitcoin-wizards
ruby32 has quit [Client Quit]
go1111111 has joined #bitcoin-wizards
coup_de_shitlord has quit [Remote host closed the connection]
byteflame has joined #bitcoin-wizards
coup_de_shitlord has joined #bitcoin-wizards
coup_de_shitlord is now known as Guest88813
Guest88813 has quit [Client Quit]
byteflame has quit [Ping timeout: 244 seconds]
Chris_Stewart_5 has joined #bitcoin-wizards
NewLiberty has joined #bitcoin-wizards
atgreen has quit [Remote host closed the connection]
<proslogion>
can you interactively prove the knowledge of a solution to a CNF-SAT problem in zero knowledge?
<gmaxwell>
you can prove _non_ interactively any NP statement in Zk.
<gmaxwell>
so yes.
<proslogion>
gmaxwell: well the problem i have is the cost associated with NIZK
<proslogion>
the prover needs to do tons more work is it?
<gmaxwell>
the mental MPC based scheme linked to a day or so ago has a pretty fast prover.
<gmaxwell>
e.g. proving a sha1 hash took a few milliseconds.
murch has quit [Quit: Leaving.]
luke-jr has quit [Ping timeout: 244 seconds]
luke-jr has joined #bitcoin-wizards
<proslogion>
right, but isn't the point of ZKCP that the prover sells solutions for an income?
<gmaxwell>
yes? and?
<proslogion>
so ideally he should be able to perform the computations much faster than the verifier
<gmaxwell>
no no no
thesnark has quit [Remote host closed the connection]
<gmaxwell>
the work that the prover does at proof time is _NOT_ the coming up with the solution.
<proslogion>
oh, so he should have some trap doors that he computes in advance?
<gmaxwell>
It is only proving that it has one (and that the encryption keys and whatnot agree)
<gmaxwell>
which means that the prover is only running the verification (and some wrapper logic.)
<proslogion>
yeah, i think i get you
<gmaxwell>
by verification I mean code that the verifier would use to decide to accept the solution, if the task weren't being done in ZK.
<gmaxwell>
and in the case of zkcp since the buyer can bail out at any point (and not get the information); it is sutiable really mostly for information that the seller already has and could sell for little to no marginal cost.
<gmaxwell>
you wouldn't want to ZKCP for some task where you'd have to do a lot of work, because the buyer could walk without paying.
<gmaxwell>
(unless you thought you could get another buyer for the same data)
<proslogion>
yeah, but otoh you could be a server and the buyer could be a pathetic mobile device
thesnark has joined #bitcoin-wizards
mountaingoat has quit [Ping timeout: 265 seconds]
wipogee has quit [Read error: Connection reset by peer]
wipogee has joined #bitcoin-wizards
mountaingoat has joined #bitcoin-wizards
bildramer has quit [Ping timeout: 258 seconds]
bildramer has joined #bitcoin-wizards
ThomasV has quit [Ping timeout: 276 seconds]
molly has quit [Ping timeout: 276 seconds]
laurentmt has joined #bitcoin-wizards
laurentmt has quit [Client Quit]
ThomasV has joined #bitcoin-wizards
alan_ has joined #bitcoin-wizards
alan_ is now known as Alanius
dEBRUYNE_ has joined #bitcoin-wizards
dEBRUYNE has quit [Ping timeout: 250 seconds]
c0rw1n has quit [Read error: Connection reset by peer]
c0rw1n has joined #bitcoin-wizards
ThomasV has quit [Ping timeout: 240 seconds]
btcdrak has quit [Quit: Connection closed for inactivity]
BashCo has quit [Remote host closed the connection]
dEBRUYNE_ has quit [Ping timeout: 252 seconds]
Eliel_ has quit [Ping timeout: 264 seconds]
Myagui has quit [Ping timeout: 276 seconds]
Myagui has joined #bitcoin-wizards
Eliel has joined #bitcoin-wizards
dEBRUYNE has joined #bitcoin-wizards
cjcj has quit [*.net *.split]
jtimon has joined #bitcoin-wizards
ThomasV has joined #bitcoin-wizards
byteflame has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 264 seconds]
moli has joined #bitcoin-wizards
Chris_Stewart_5 has joined #bitcoin-wizards
ThomasV has quit [Ping timeout: 250 seconds]
btcdrak has joined #bitcoin-wizards
ThomasV has joined #bitcoin-wizards
jtimon has quit [Ping timeout: 260 seconds]
jtimon has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 258 seconds]
<waxwing>
nsh: not really one for me, but isn't that just a standard mathematical thing?
<waxwing>
oh right. it's on wikipedia.
<nsh>
raise to the power of the group order plus one divided by four instead of square rooting? not standard to me, but i'm incredibly uneducated
<nsh>
in which article?
<waxwing>
it's in the referred link [11]
<nsh>
ty
<waxwing>
cant remember where i read it, i think it was on bitcointalk or stackexchange, at least
<gmaxwell>
nsh: it's a well known result due to (IIRC lagrange) that if P is congruent to 3 mod 4 you can compute the sqrt as P+1//4.
<nsh>
larange aye
<nsh>
another due to legendre for n = 5 (mod 8)
<nsh>
neato
<gmaxwell>
there is a similar technique for the modular inverse (fermats little theorem)
<gmaxwell>
nsh: there are more recent solutions for other primes too that are somewhat more complex to compute.
<nsh>
cool
<nsh>
this lifting stuff [[Hensel's lemma]] looks fun too
<gmaxwell>
it's common for curves to be chosen so that P is congruent to 3 mod 4 in order to get access to this 'fast' sqrt. (not that it's all that fast... :) )
<waxwing>
yeah i need to go back and double check that. there's more than 1 possibility and i might have got the wrong one. was a long time ago.
<waxwing>
well there's at least 2 right, uncompressed etc.
* nsh
nods
<nsh>
if i ever break ECDLP i'll spent one satoshi+fees from that input just as a heads-up okay
<nsh>
pinkie promise
<waxwing>
heh. but, where did you get 1Ge.. ?
<nsh>
no i miscopied
<nsh>
1D8eDztgv79J59V7UBBpNGnRE6hjstqKb5
<nsh>
sorry
<waxwing>
oh i see :)
<waxwing>
uhh someone paid to that? interesting...
<waxwing>
looks like they used joinmarket :)
<nsh>
ritual burnt offering
<waxwing>
phi/10 (or Phi/100)?
Yogh has joined #bitcoin-wizards
<waxwing>
i think i know who did that :)
<nsh>
it's probably the final stage of cicada 2020
<nsh>
:P
<waxwing>
is that still going?
<nsh>
nah, i think it dried up last year
<proslogion>
what's this about
<nsh>
probably recruited all the weirdos they need to save humanity from a lack of appreciation for william blake and haikus or whatever
mdavid613 has quit [Quit: Leaving.]
<nsh>
.wik Cicada 3301
<yoleaux>
"Cicada 3301 is a name given to an enigmatic organization that on six occasions has posted a set of complex puzzles and alternate reality games to recruit codebreakers from the public. The first internet puzzle started on January 4, 2012, and ran for approximately one month." — https://en.wikipedia.org/wiki/Cicada_3301
<proslogion>
yeah but what does that have to do with that address
<waxwing>
nothing, he's just saying such eccentricity is vaguely suggestive of that kind of thing
arowser has quit [Ping timeout: 250 seconds]
* nsh
smiles
mdavid613 has joined #bitcoin-wizards
<nsh>
i don't recall they ever touched on anything elliptic, but i didn't pay close attention
arowser has joined #bitcoin-wizards
<waxwing>
huh, just yesterday, curious coincidence
Chris_Stewart_5 has joined #bitcoin-wizards
<waxwing>
no, doh, it was last year sorry. how did i read that so wrong? /facepalm
proslogion has quit [Ping timeout: 264 seconds]
<nsh>
dates are hard. #1country does them wrong as a matter of principle
Chris_Stewart_5 has quit [Ping timeout: 276 seconds]
Chris_Stewart_5 has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 250 seconds]
dEBRUYNE_ has joined #bitcoin-wizards
dEBRUYNE has quit [Ping timeout: 240 seconds]
Chris_Stewart_5 has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 250 seconds]
Chris_Stewart_5 has joined #bitcoin-wizards
iddo has quit [Quit: Lost terminal]
bitcoin-wizards8 has joined #bitcoin-wizards
<waxwing>
i couldn't help looking again, turns out i chose the wrong root :) compressed is 1CL6niRb19faMRnYSr4N135wp7YhP44mKd and uncompressed is 1Jp8T2cUdqfcq6P3wECKvcMJu27AByk2B
ThomasV has joined #bitcoin-wizards
bitcoin-wizards8 has quit [Ping timeout: 264 seconds]
<waxwing>
how does sage's "lift_x" choose the square root? couldn't find docs
Chris_Stewart_5 has quit [Ping timeout: 252 seconds]
Ylbam has joined #bitcoin-wizards
fractex has quit [Ping timeout: 258 seconds]
ruby32 has joined #bitcoin-wizards
fractex has joined #bitcoin-wizards
iddo has joined #bitcoin-wizards
molz has joined #bitcoin-wizards
moli has quit [Ping timeout: 258 seconds]
dEBRUYNE_ has quit [Quit: Leaving]
bitcoin-wizards1 has joined #bitcoin-wizards
bitcoin-wizards1 is now known as LefKok
LefKok has quit [Client Quit]
byteflame has quit [Ping timeout: 252 seconds]
laurentmt has joined #bitcoin-wizards
laurentmt has quit [Client Quit]
ThomasV has quit [Ping timeout: 260 seconds]
NewLiberty has quit [Ping timeout: 258 seconds]
ruby32 has quit [Remote host closed the connection]
MoALTz has quit [Ping timeout: 244 seconds]
ThomasV has joined #bitcoin-wizards
ThomasV has quit [Ping timeout: 258 seconds]
ruby32 has joined #bitcoin-wizards
danrobinson_ has joined #bitcoin-wizards
danrobin_ has joined #bitcoin-wizards
ruby32 has quit []
danrobin_ has quit [Client Quit]
danrobin_ has joined #bitcoin-wizards
danrobin_ has quit [Client Quit]
murch has quit [Quit: Leaving.]
danrobinson__ has joined #bitcoin-wizards
ThomasV has joined #bitcoin-wizards
Guyver2 has quit [Remote host closed the connection]
dnaleor has quit [Quit: Leaving]
droark has quit [Read error: Connection reset by peer]