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
Newyorkadam has joined #bitcoin-wizards
Newyorkadam has quit [Client Quit]
jtimon has quit [Ping timeout: 240 seconds]
dnaleor has quit [Quit: Leaving]
dnaleor has joined #bitcoin-wizards
mxg has joined #bitcoin-wizards
d_t has joined #bitcoin-wizards
mxg has quit [Quit: afk]
DougieBot5000_ has joined #bitcoin-wizards
DougieBot5000 has quit [Killed (orwell.freenode.net (Nickname regained by services))]
huntingcryptos has quit [Ping timeout: 240 seconds]
DougieBot5000 has joined #bitcoin-wizards
rusty has quit [Quit: Leaving.]
daszorz has joined #bitcoin-wizards
JackH has quit [Ping timeout: 248 seconds]
JackH has joined #bitcoin-wizards
d_t has quit [Ping timeout: 250 seconds]
huntingcryptos has joined #bitcoin-wizards
daszorz has quit [Read error: Connection reset by peer]
huntingcryptos has quit [Remote host closed the connection]
huntingcryptos has joined #bitcoin-wizards
daszorz has joined #bitcoin-wizards
dnaleor has joined #bitcoin-wizards
packetsmurf has joined #bitcoin-wizards
coinsmurf has quit [Ping timeout: 248 seconds]
rusty has joined #bitcoin-wizards
meshcollider has joined #bitcoin-wizards
dnaleor has quit [Quit: Leaving]
laurentmt has joined #bitcoin-wizards
laurentmt1 has joined #bitcoin-wizards
laurentmt has quit [Ping timeout: 268 seconds]
leonidaz0r has quit [Ping timeout: 240 seconds]
laurentmt1 has quit [Ping timeout: 240 seconds]
leonidaz0r has joined #bitcoin-wizards
laurentmt has joined #bitcoin-wizards
Ylbam has quit [Quit: Connection closed for inactivity]
rusty has quit [Quit: Leaving.]
Guyver2 has joined #bitcoin-wizards
rusty has joined #bitcoin-wizards
rusty has quit [Ping timeout: 252 seconds]
AaronvanW has joined #bitcoin-wizards
dnaleor has joined #bitcoin-wizards
jtimon has joined #bitcoin-wizards
dnaleor has quit [Quit: Leaving]
dabura667 has quit [Remote host closed the connection]
huntingcryptos has quit [Remote host closed the connection]
jannes has joined #bitcoin-wizards
arubi has quit [Remote host closed the connection]
huntingcryptos has joined #bitcoin-wizards
dnaleor has joined #bitcoin-wizards
betawaffle has quit [Quit: Oh noes, my ZNC!]
betawaffle has joined #bitcoin-wizards
bildramer has joined #bitcoin-wizards
coinsmurf has joined #bitcoin-wizards
packetsmurf has quit [Ping timeout: 248 seconds]
coinsmurf has quit [Ping timeout: 250 seconds]
coinsmurf has joined #bitcoin-wizards
arubi has joined #bitcoin-wizards
Noldorin has joined #bitcoin-wizards
JackH has quit [Ping timeout: 260 seconds]
Chris_Stewart_5 has joined #bitcoin-wizards
huntingc_ has joined #bitcoin-wizards
huntingcryptos has quit [Ping timeout: 250 seconds]
sammi` has quit [Ping timeout: 248 seconds]
sammi` has joined #bitcoin-wizards
daszorz has quit [Read error: Connection reset by peer]
JackH has joined #bitcoin-wizards
Murch has joined #bitcoin-wizards
meshcollider has quit [Quit: Connection closed for inactivity]
thrmo has joined #bitcoin-wizards
thrmo has quit [Remote host closed the connection]
thrmo has joined #bitcoin-wizards
jb55 has quit [Ping timeout: 260 seconds]
Ylbam has joined #bitcoin-wizards
huntingc_ has quit [Remote host closed the connection]
huntingcryptos has joined #bitcoin-wizards
dnaleor has quit [Quit: Leaving]
AR-AI has joined #bitcoin-wizards
kgk has quit [Quit: WeeChat 1.9.1]
thrmo has quit [Ping timeout: 248 seconds]
d4de has quit [Quit: This computer has gone to sleep]
harrymm has quit [Ping timeout: 240 seconds]
dnaleor has joined #bitcoin-wizards
jb55 has joined #bitcoin-wizards
harrymm has joined #bitcoin-wizards
thrmo has joined #bitcoin-wizards
jtimon has quit [Ping timeout: 240 seconds]
Noldorin has quit [Quit: My MacBook Pro has gone to sleep. ZZZzzz…]
jtimon has joined #bitcoin-wizards
dnaleor has quit [Quit: Leaving]
oleganza has joined #bitcoin-wizards
hdevalence has joined #bitcoin-wizards
akrmn has quit [Ping timeout: 255 seconds]
dnaleor has joined #bitcoin-wizards
<nsh>
does anyone feel they can give a [somewhat] layman's sketch of how the bulletproofs rangeproofs work conceptually yet?
huntingc_ has joined #bitcoin-wizards
huntingcryptos has quit [Ping timeout: 250 seconds]
daszorz has joined #bitcoin-wizards
laurentmt has quit [Quit: laurentmt]
<andytoshi>
nsh: it breaks the value into bits, and proves that each bit satisfies X*(1-X)=0, i.e. it is a bit, and that sum_i 2^i X_i = v, i.e. these are the right bits, by multiplying all n+1 of those equations by random hash challenges (1, y, y^2, ..., y^n, z) which are hashes of (a) commitments to the bits, (b) commitments to blinding factors. this can be expressed as a dot product <{x_i}, {1 - x_i +
<andytoshi>
z*2^i}> which should equal z*v
<andytoshi>
to hide everything, the prover chooses random blinding factors s_i for each bit (actually two of them, one for the bit and one for the complement) and adds these times yet another hash challenge x. there are two pedersen commitments that are added, ane for the bits (and their complements) and one for the blinding factors
<andytoshi>
then the sum (weighted by the appropriate hash challenges) of all the blinding factors of these pedersen commitments is revealed in two halves, each containing at least 2 blinding factors to ensure that none of them are actually revealed
<andytoshi>
which is sufficient for the verifier to add the original pedersen commitment to the weighted-by-hash-challenges aux pedersen commitments, and it expects to get g^t where t is a sum of all the garbage cross-terms from the original dot product equation
<andytoshi>
the proof is constructed so that `t` is a pure function of the hash challenges so the verifier knows what it should be
<andytoshi>
in addation, the prover provides an inner-product proof showing that this `t` came organically from doing the original inner-product equation, and the prover didn't just make it up to pracate the verifier
<andytoshi>
that's roughly it
<andytoshi>
i don't know if that provided any clarity :P
<andytoshi>
s/pracate/placate/
<nsh>
thank you kindly andytoshi! will ponder and see if i grok :)
<waxwing>
have you 'finished' coding the range proof part yet andytoshi ? at least non-aggregated
<andytoshi>
waxwing: i have a prover but no verifier, and i haven't tested the prover to see if it barfs on its own sanity checks
<andytoshi>
so.. no :P
d_t has joined #bitcoin-wizards
<waxwing>
how can we boil down the explanation ... non trivial exercise ... basically make the t0 (constant term in t = l.r) have no dependency on the vector of bits in the value, if and only if the vector of bits is exactly bits (ones and zeros)
<waxwing>
and then leverage the compactness of the inner product proof
rusty has joined #bitcoin-wizards
<andytoshi>
that's roughly it. but you have to mix in the original pedersen commitment and you also have to make the higher-order terms go away without revealing the whole polynomial
<andytoshi>
the former is easy enough, t0 does actually have the value in it multiplied by z^2, so the verifier adds z^2*V to the verification equation
<waxwing>
right, was gonna say, you also have to commit to the other coefficients and .. i guess you can say, leverage the homomorphism ... but whichever way i look it i find it hard to understand it as a whole.
<andytoshi>
and for the latter there are these extra points T_1 and T_2 that you reveal and you reveal a weighted sum of their blinding factors (which does not reveal either individual blinding factor)
<andytoshi>
to understand it i basically had to implement it, and every time something was hard to code or slow i tried to remove it from the protocol and spent a while figuring out what broke each time
<waxwing>
right :) i'm writing it in python, the inner product wasn't hard at all really, but the range proof .. ;) and yes i am completely ignoring the hard stuff (e.g. just recursive no unrolling).
<nsh>
waxwing, online or offline? (wouldn't mind a peek to facilitate my comprehension)
<waxwing>
i'll probably throw it on gh if i get it sorta kinda working. it won't be pretty though. note both benedikt and andytoshi have code on github already.
<waxwing>
needless to say it's just for self-education :)
<nsh>
sure :) trying not to resort to reading java
* nsh
nods
<waxwing>
heh, well apart from some non-orthodox spelling, benedikt's code isn't that hard to read :)
<nsh>
ah, ok
thrmo has quit [Ping timeout: 248 seconds]
jannes has quit [Ping timeout: 248 seconds]
rusty has quit [Ping timeout: 268 seconds]
victorSN has quit [Excess Flood]
victorSN has joined #bitcoin-wizards
worstadmin has joined #bitcoin-wizards
d_t has quit [Ping timeout: 268 seconds]
rusty has joined #bitcoin-wizards
Belkaar has quit [Read error: Connection reset by peer]
d4de has joined #bitcoin-wizards
aem has quit [Quit: Ciao!]
oleganza has quit [Quit: oleganza]
oleganza has joined #bitcoin-wizards
Belkaar has joined #bitcoin-wizards
Belkaar has quit [Changing host]
Belkaar has joined #bitcoin-wizards
aem has joined #bitcoin-wizards
aem is now known as aem
d4de has quit [Quit: This computer has gone to sleep]
jb55 has quit [Ping timeout: 240 seconds]
dcousens has quit [Ping timeout: 240 seconds]
dcousens has joined #bitcoin-wizards
rusty has quit [Ping timeout: 248 seconds]
daszorz has quit [Read error: Connection reset by peer]
akrmn has joined #bitcoin-wizards
Giszmo has quit [Ping timeout: 250 seconds]
<akrmn>
so I read about SNARKs. They provide proofs of length in the few hundred bytes, nice and short but relies on ECC so I assume not safe for proving no inflation is coming from sidechains. Then there's STARKs, can't find much info but from what I read they are quantum resistant and no trusted setup required, and proofs in the hundreds of kilobytes. While this may seem like a lot of data to put for segwit data, can't you just put
<akrmn>
Have each sidechain generate one proof, then have a proof that shows that those proofs were verified?
geo2020 has joined #bitcoin-wizards
akrmn has quit [Ping timeout: 240 seconds]
Giszmo has joined #bitcoin-wizards
Aaronvan_ has joined #bitcoin-wizards
Mutter has joined #bitcoin-wizards
Aaronva__ has joined #bitcoin-wizards
Mutter is now known as benehsv
AaronvanW has quit [Ping timeout: 240 seconds]
Aaronvan_ has quit [Ping timeout: 248 seconds]
benehsv has quit [Client Quit]
akrmn has joined #bitcoin-wizards
Aaronva__ has quit [Ping timeout: 255 seconds]
oleganza has quit [Quit: oleganza]
<nsh>
curious about the 'correction factor' which is introduced by applying the iterative inner-product protocol to vectors in parallel...
<andytoshi>
where is that mentioned?
<nsh>
p13
<nsh>
'' Additionally,we show in Protocol 1 that this can also be done for two vectors in parallel suchthat the inner product of the two vectors does only changes by a correctionfactor which the verifier again can compute himself from the challenge'
<nsh>
typo seemingly where "does not change" was changed :)
<nsh>
some kinda rounding figure to keep during aggregation i assume
<Chris_Stewart_5>
Does anyone have a concrete test vector of this clause in BIP32: "In case parse256(IL) ≥ n or Ki is the point at infinity, the resulting key is invalid, and one should proceed with the next value for i."
<Chris_Stewart_5>
the bip says it happens when deriving a child pubkey from a master pubkey
<andytoshi>
nsh: not sure what is meant by that tbh
<andytoshi>
i think it's supposed to be a description of protocol 1
<nsh>
kk
<sipa>
Chris_Stewart_5: it's impossible to construct a test vector for that
<sipa>
at least on secp256k1
<sipa>
on secp256r1 you could, due to the ratio between field size and group size being much larger
<sipa>
*difference between
<nsh>
what do we win if we find one?
<Chris_Stewart_5>
sipa: So basically secp256k1 will cause a failure if you try and parse something >= n ?
jb55 has joined #bitcoin-wizards
laurentmt has joined #bitcoin-wizards
<sipa>
Chris_Stewart_5: libsecp256k1?
<Chris_Stewart_5>
ah i filled in the lib
<sipa>
the tweak_add functions (which you'd normally use for bip32 derivation) will fail in the case of overfloe, yes
AaronvanW has joined #bitcoin-wizards
<Chris_Stewart_5>
so bip32 is meant to be generalized for any curve
<Chris_Stewart_5>
and that is why that clause needs to be there?
laurentmt has quit [Quit: laurentmt]
<akrmn>
So no one knows or I should ask on the mailing list? I don't see much discussing on starks in the logs, but at least I would like to know if it is possible to prove supply consistency with starks & sidechains assuming they do what they claim.
Guest54516 has joined #bitcoin-wizards
<andytoshi>
akrmn: there is no general-purpose zk proof system that can handle proving validity of a whole blockchain
Guest54516 is now known as blarney
<sipa>
Chris_Stewart_5: i added it at the time because of a recommendation by a cryptographer, but i assume he wasn't aware of the fact that it is infeasible to hut that case
laurentmt has joined #bitcoin-wizards
laurentmt has quit [Client Quit]
<akrmn>
andytoshi: ok...well if you have links to proof of that or more reading so that I can understand, that would be great. I guess it is trivial for you but not so obvious for me
<akrmn>
because I'm not talking about proving validity of a whole blockchain in one proof, just validity of sidechain transfers for one block
<andytoshi>
there's no difference
sammi`_ has joined #bitcoin-wizards
thrmo has joined #bitcoin-wizards
sammi` has quit [Quit: Lost terminal]
<sipa>
akrmn: to prove a move back from the sidechain was legal, you need to prove that its entire history in the sidechain was legal
thrmo1111 has joined #bitcoin-wizards
thrmo has quit [Ping timeout: 248 seconds]
satwo has joined #bitcoin-wizards
Guyver2 has quit [Quit: Going offline, see ya! (www.adiirc.com)]
thrmo1111 is now known as thrmo
<akrmn>
hmm more things to think about. I guess the problem is that with each new block for the sidechain, there is an extra computational step to do, so the amount of steps/ cpu power needed keeps growing with time. My initial thinking is just to set a limit for the height of the sidechain, and force everyone to settle back at that time, but need to think some more, thanks.
AaronvanW has quit [Remote host closed the connection]
AaronvanW has joined #bitcoin-wizards
JackH has quit [Read error: Connection reset by peer]
JackH has joined #bitcoin-wizards
AaronvanW has quit [Ping timeout: 248 seconds]
<akrmn>
so maybe it will not be exactly a textbook definition of a blockchain, but I think anything that involves mining bitcoins without merge mining would provide more miner decentralization (not just scaling by adding the ability to spend smaller amounts on the sidechain)
AaronvanW has joined #bitcoin-wizards
meshcollider has joined #bitcoin-wizards
rusty has joined #bitcoin-wizards
<nsh>
i guess the correction factor is k(y,z) which you must update/collate as/when you aggregate rangeproofs
deusexbeer has quit [Ping timeout: 240 seconds]
deusexbeer has joined #bitcoin-wizards
rmwb has joined #bitcoin-wizards
<andytoshi>
that could be it
Chris_Stewart_5 has quit [Ping timeout: 248 seconds]
da2ce7 has quit [Ping timeout: 252 seconds]
Hunger- has quit [Ping timeout: 252 seconds]
Hunger- has joined #bitcoin-wizards
da2ce7 has joined #bitcoin-wizards
AaronvanW has quit [Remote host closed the connection]
<akrmn>
If there's any useful applications with these ideas, I want to try to code them with testnet (I already have experience working with Bitcoin Core code). Just I am thinking it may be useless without some library for starks available, also want to make sure I am not wasting my time, that's why I'm asking here first. I know sipa mentioned snarks as a solution to this problem earlier so would be good to also know what kind of snar
<andytoshi>
no library exists which can do what you want
<kanzure>
"use a snark" might be part of the ansewr but it's a long way from the point where someone can sit down and write relevant code
daszorz has joined #bitcoin-wizards
oleganza has joined #bitcoin-wizards
Giszmo has quit [Ping timeout: 240 seconds]
daszorz2 has joined #bitcoin-wizards
d4de has joined #bitcoin-wizards
daszorz has quit [Ping timeout: 268 seconds]
daszorz2 has quit [Read error: Connection reset by peer]