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
pinheadmz has joined #bitcoin-wizards
Murch has joined #bitcoin-wizards
rh0nj has joined #bitcoin-wizards
jtimon has quit [Quit: gone]
Krellan_ has joined #bitcoin-wizards
Krellan has quit [Ping timeout: 246 seconds]
jtimon 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
bitcoin-wizards6 has joined #bitcoin-wizards
bitcoin-wizards6 has quit [Ping timeout: 256 seconds]
Murch has quit [Quit: Snoozing.]
sipa has quit [Ping timeout: 256 seconds]
sipa has joined #bitcoin-wizards
spinza has quit [Quit: Coyote finally caught up with me...]
spinza has quit [Quit: Coyote finally caught up with me...]
rusty has quit [Quit: Leaving.]
spinza has joined #bitcoin-wizards
triazo has quit [Ping timeout: 245 seconds]
stiell has quit [Ping timeout: 244 seconds]
davec has quit [Ping timeout: 245 seconds]
wxss has quit [Ping timeout: 245 seconds]
TheoStorm has joined #bitcoin-wizards
davec has joined #bitcoin-wizards
wxss has joined #bitcoin-wizards
stiell has joined #bitcoin-wizards
triazo has joined #bitcoin-wizards
spinza has quit [Quit: Coyote finally caught up with me...]
nephyrin has quit [Ping timeout: 264 seconds]
nephyrin has joined #bitcoin-wizards
spinza has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
arubi has joined #bitcoin-wizards
marcoagner has quit [Quit: WeeChat 1.0.1]
<luke-jr>
I wonder if there's a good way to make it so if you don't run a full node, your coins can be stolen trivially
<luke-jr>
maybe keeping a running UTXO-set-history hash that needs to be committed to in the tx somehow, and if it doesn't match, the outputs can be malleated?
TheoStorm has quit [Quit: Leaving]
riclas has joined #bitcoin-wizards
Guyver2 has joined #bitcoin-wizards
rafalcpp has quit [Ping timeout: 250 seconds]
TheoStorm has joined #bitcoin-wizards
setpill has quit [Quit: o/]
michaelsdunn1 has joined #bitcoin-wizards
michaelsdunn1 has quit [Changing host]
michaelsdunn1 has joined #bitcoin-wizards
rafalcpp has joined #bitcoin-wizards
rockhouse has quit [Quit: Leaving ... but you never know maybe I come back!]
victorSN has quit [Quit: Leaving ... but you never know maybe I come back!]
<sarang>
This explains both the transparent-pool requirement and the absurd transcript story
<waxwing>
heh, was jsut going to quote:
<waxwing>
"The Zcash Company adopted and maintained a cover story that the transcript was missing due to accidental deletion. "
<waxwing>
but what if that itself is another cover story? :thinks:
<sarang>
I had (have) many problems with the whole "turnstile" process and their handling of it...
* nsh
frowns
<nsh>
it'd be interesting to compare the process to bitcoin's recent inflation vuln and how that was handled
<nsh>
undoubtedly this will occur again
<sarang>
zooko had indicated a desire for another transparent migration at their next release
<waxwing>
why 'undoubtedly'?
<cjd>
probably because statistical blahblahblah no system is safe
<nsh>
well, i suppose there exist last-mistakes-of-a-class but they're rare
<cjd>
right
<nsh>
or sparse in the category of mistakes
<nsh>
it'd be nice to have an phylogenetic tree of zk cryptosystems so it'd be easy/easier to see which inherited the vulnerability
<nsh>
i suppose cite graph gives clues
<nsh>
also it's an interesting cost to this remediation that the MPC protocol transcript is now unavailable [unless you know someone who archived it]
<nsh>
oh no, misread; it's reposted after the fix
<waxwing>
this is why i've been leaning against blinding of amount based on hardness assumptions even though it's a heretical position, including against myself :) it's not the hardness assumpmtion or the QCs that get you, it's the implementation (likely).
<instagibbs>
cost being no one could validate the privacy of the setup, right?
<waxwing>
and even security proofs are unreliable unless they're really really simple. i think.
<nsh>
it seems [very] hard in general to prove that you haven't introduced fresh assumptions while implementing or adapting from previous results
<nsh>
"Ariel Gabizon, a cryptographer employed by the Zcash Company at the time of discovery, uncovered a soundness vulnerability. The key generation procedure of [BCTV14], in step 3, produces various elements that are the result of evaluating polynomials related to the statement being proven. Some of these elements are unused by the prover and were included by mistake; but their presence allows a cheating prover to circumvent a consistency check, and thereby
<nsh>
transform the proof of one statement into a valid-looking proof of a different statement. This breaks the soundness of the proving system."
<nsh>
point to whoever works this out in a SAGE notebook...
jungly has quit [Remote host closed the connection]
<nsh>
or something that can be followed precisely
<nsh>
so it was effectively a trusted setup leak through redundant parameters in transcript
<sarang>
I assume Peter Todd feels a certain amount of deserved smugness after this :D
<sarang>
(regarding the transcript)
<nsh>
aka pretty much a catastrophic failure of the ceremony
<sarang>
^
<nsh>
so i guess one thing to do is add a proof that a transcript of a protocol doesn't just satisfy the verifier but it also does so minimally, ie without any extraneous data whatsoever
<nsh>
which seems a harder task
pinheadmz has joined #bitcoin-wizards
<sarang>
Or, you know, avoid MPCs with secret-infused CRS/SRS...
* nsh
smiles
<sarang>
From a non-technical standpoint, I'm now interested in seeing how many company posts/statements/comments dance around the issue of a flaw without outright misleading, prior to disclosure
<sarang>
it'd be a fascinating study in maintaining the ruse
ddustin has joined #bitcoin-wizards
ddustin has quit [Read error: Connection reset by peer]
nephyrin has quit [Ping timeout: 240 seconds]
ddustin has joined #bitcoin-wizards
ddustin has quit [Read error: Connection reset by peer]
ddustin has joined #bitcoin-wizards
ddustin has quit [Read error: Connection reset by peer]
ddustin has joined #bitcoin-wizards
nephyrin has joined #bitcoin-wizards
<nsh>
okay wow i wasn't expecting the transcript to be 6.9GB...
<nsh>
i thought maybe large but not that large
<nsh>
if every result in known mathematics was encoded into coq theorems it would be significantly smaller
TheoStorm has quit [Quit: Leaving]
enemabandit has quit [Ping timeout: 240 seconds]
<jtimon>
nsh: what bitcoin's recent inflation vulnerability?
<nsh>
tl;dr codebase technical debt servicing is hard, even when you are doing your very best
<jtimon>
thanks
<jtimon>
oh, yeah, the consensus rule that was temporarily removed from bitcoin core by mistake, right?
<nsh>
over several pull requests and refactors a consensus check against doublespends was lost in translation
<nsh>
briefly
<jtimon>
yeah, sobody said it was duplicated and it seems most reviewers just believed it
<sipa>
jtimon: there was also a 0.8 thing where master briefly removed the subsidy limit check, but that was discovered before release
<sipa>
this is something else
<jtimon>
hmm, didn't know that one
Murch has joined #bitcoin-wizards
<jtimon>
this one is just the check that the inputs being spend haven't been spent already within the same block, right? we removed that thinking that was duplicated with analogous checks in the mempool, but they weren't the same checks so we put them back
<sipa>
jtimon: within the same *transaction* even
* jtimon
nods
<sipa>
or rather, two pieces of code whose authors believed the other part was responsible for checking within-block double spending
<sipa>
but both got optimized removing the check, leaving only a cross-tx assertion in place, and nothing for within-tx
<jtimon>
oh, I see, it was only the within a tx part that was missing?
<sipa>
right
enemabandit has joined #bitcoin-wizards
bildramer has quit [Ping timeout: 246 seconds]
bildramer has joined #bitcoin-wizards
<gmaxwell>
The zcash announcement is shocking. It appears to me that zcash basically spent months slandering Petertodd, who noticed the highly questionable disappearence of the mpc transcript, in an effort to cover up a total lack of soundness (unbounded undetectable inflation), and zcash company employees continued to double down on the integrity of their trusted setup even when they knew in fact that
ghost43 has quit [Remote host closed the connection]
vfP56jSe has joined #bitcoin-wizards
ghost43 has joined #bitcoin-wizards
<nsh>
missed the drama when it happened but if that's so, i'd say he's owed an apology at least
<nsh>
(and/or should have been brought into disclosure process)
<gmaxwell>
I could understand them not doing that, but they could have remained silent. Rather than vigourly doubling down in defense of a system that they had actual knowledge of an insecurity in.
<vfP56jSe>
Hello, I am reading about Taproot. In the cooperative case, what would the signature look like for P?
<vfP56jSe>
In the mailing list it says "one of them just needs to add H(C||S) to their private key", but if it's only one of them, then it isn't cooperative? Please help me understand.
<gmaxwell>
vfP56jSe: how is that not cooperative?
<vfP56jSe>
gmaxwell: Maybe the better question is: do both sides know C?
<gmaxwell>
vfP56jSe: of course.
rusty has joined #bitcoin-wizards
rusty has quit [Client Quit]
<vfP56jSe>
My understanding (which might be completely wrong)is that the signature looks like "a + H(C||S)", and since this is supposed to be cooperative, both parties need to agree to sign, so if Alice knows a, C, and S, in this completely wrong understanding, she would be able to sign for P by herself?
<gmaxwell>
that isn't the signature at all. that is the public key.
<gmaxwell>
The signature is just an ordinary signature, signed using a tweaked key.
<gmaxwell>
I now understand your misunderstanding.
<gmaxwell>
Now Alice and Bob-- assuming they are both online and agree about the
<gmaxwell>
resolution of their contract-- can jointly form a 2 of 2 signature for
<gmaxwell>
P, and spend as if it were a payment to a single party (one of them
<gmaxwell>
just needs to add H(C||S) to their private key).
<gmaxwell>
is the text from the post.
<gmaxwell>
It's not describing the signing algorithim. The signing algorithim is just a standard signing algorithim for 2 of 2 schnorr.
<gmaxwell>
With the only modification is that instead of signing with their private key, one of the signers needs to sign with a tweaked private key.
* vfP56jSe
reading intently
<gmaxwell>
(or, alternatively, treat it as a 3 of 3 schnorr, with the taproot commitment being one of the private keys, its equivient)
<vfP56jSe>
The "tweaked key" part isn't part of standard schnorr is it? And the tweaking is what is described by "one of them just needs to add H(C||S) to their private key"?
<sarang>
gmaxwell: zooko still claims in a tweet that this wasn't a flaw in the setup
<sarang>
And that it could just as easily happen in a trustless proving system
<gmaxwell>
sarang: thats a weird and distracting claim. Yes, any bleeding edge hardly reviewable cryptosystem could have unsoundness vulnerablities.
<gmaxwell>
It wasn't a violation of the trusted state, it was a flaw in the additional complex procedure that was needed to try to patch over the insecure setup.
<gmaxwell>
it's also weird that their disclosure does not make clear that they do not, and cannot know, if it was exploited. (only that the total funds that have exited from the unshielded addresses are below the maximum, so any inflation-- if their was any-- was instead converted into theft to parties that were slow to get their funds out of the old accumulator.
<gmaxwell>
)
<nsh>
hmm
<nsh>
so there are potentially bagholders
<nsh>
it would take some computation over all honest accumulator participants to prove there was no counterfeiting
<nsh>
(and that doesn't seem tractable)
michaelsdunn1 has quit [Remote host closed the connection]
<gmaxwell>
nsh: or all of the funds being exited from the old accumulator.
michaelsdunn1 has joined #bitcoin-wizards
Krellan has joined #bitcoin-wizards
Murch has quit [Quit: Snoozing.]
Murch has joined #bitcoin-wizards
* nsh
nods
<gmaxwell>
which is presumably impossible, since ~someone~ had to have lost their keys by now.
<nsh>
do coins in the old accumulator retain [migrateable] value indefinitely or is there some sunset period?
<nsh>
s/coins/funds/
CryptoDavid has joined #bitcoin-wizards
Krellan_ has joined #bitcoin-wizards
Murch has quit [Quit: Snoozing.]
michaelsdunn1 has quit [Remote host closed the connection]
Krellan has quit [Ping timeout: 272 seconds]
son0p has joined #bitcoin-wizards
michaelsdunn1 has joined #bitcoin-wizards
Murch has joined #bitcoin-wizards
michaelsdunn1 has quit [Remote host closed the connection]
michaelsdunn1 has joined #bitcoin-wizards
Murch has quit [Quit: Snoozing.]
<vfP56jSe>
Looking at the Schnorr BIP, in the generic description of Schnorr, does the signer pick R, e, and s?
<sarang>
nsh: for a while zooko indicated wanting a spend sunset for sprout
<sarang>
I hope this is not done
<andytoshi>
vfP56jSe: the signer picks R and s. e is forced
Guyver2 has quit [Quit: Going offline, see ya! (www.adiirc.com)]
<vfP56jSe>
andytoshi: Because when R is picked, we can get e from "e = H(R || m)" and s from solving "sG = R + eP"?
<sipa>
you pick k
<sipa>
from k you compute R = kG
<sipa>
and you compute s = k + H(R || m)x
<vfP56jSe>
P = xG too?
<vfP56jSe>
(just verifying assumptions)
<sipa>
yes, but long before (that's the creation of pubjey)
HitamSusu has joined #bitcoin-wizards
phwalkr has quit [Quit: Leaving...]
HitamSusu has quit [Client Quit]
<vfP56jSe>
sipa: That's very clear. I'm wondering, in the case where we don't consider k and just consider R, it's mentioned in the BIP that the signer can either reveal e or R, I'm curious why s can't be revealed
<sipa>
s is alwaya revealed
<vfP56jSe>
Sorry to make myself clear
<sipa>
the signature is either (R,s) or (e,s)
<vfP56jSe>
why can't it be (R, e)
<sipa>
you can't validate that
<andytoshi>
`s` can only be computed by the signer
* vfP56jSe
digesting
<vfP56jSe>
s can only be computed by the signer because only the signer has k and x, in which x is the signer's private key and k is picked by the signer
<sipa>
yes
Aaronvan_ has joined #bitcoin-wizards
<vfP56jSe>
I'm trying to see why (R, e) _necessarily_ can't be validated, my tentative answer is that since given m they HAVE to satisfy e = H(R || m) by definition, so that equation becomes unuseful...
<vfP56jSe>
because the satisfy conditions for both (e, s) and (R, s) combine "e = H(R || m)" and "sG = R + eP"
<sipa>
it's a strange question
<sipa>
i understand you're asking this from a perspective of "oh A and B are possible, why isn't C possible too?"
<sipa>
but on itself, it's already quite surprising there are two formulations of schnorr to begin with
<sipa>
typically there isn't some random transformation of this type that you can do on a cryptographic scheme without breaking it
AaronvanW has quit [Ping timeout: 272 seconds]
<vfP56jSe>
I see. Yeah I do admit it's more for my own curiosity.
* vfP56jSe
continues reading the BIP
Murch has joined #bitcoin-wizards
Newyorkadam has joined #bitcoin-wizards
<petertodd>
gmaxwell: they just told me "please shut up, we have a really good reason" I would have
<sipa>
you're mising an "if" there?
<petertodd>
gmaxwell: for the record, they never gave me any indication there was an issue... other than well after it was fixed being really weird about the missing transcript - zooko really didn't want the communication about it being made public. but that was after everything was fixed AFAICT so I don't see why
<petertodd>
sipa: sorry, if they just told me "please shut up, we have a really good reason" I would have
<sarang>
petertodd: FWIW calling them out at the time was the right thing to do IMO
<sarang>
The more I read about the timeline on this whole situation, the more upset I'm becoming
<petertodd>
sarang: thanks, though frankly I'm worried at whether or not I lost work over that - whisper networks suck
<sarang>
I noticed the Zcash Foundation is calling for an examination of Sprout address deprecation without defining what that means
<vfP56jSe>
For "Implicit Y coordinate," I understand why out of the 2 possible Y coordinates, one and only one is the quadratic residue, but I cannot find how "quadratic residue of the Y coordinate can be computed directly for points represented in Jacobian coordinates"
<petertodd>
sarang: it'd be because the old-style scheme is still allowed, albeit with a new proof system, so best to depreciate it asap
<sarang>
Is this supposed to imply eventual unspendability? Because zooko advocated for that, and it seemed bonkers to me
<sarang>
(of course, now I know that he was aware of the flaw when he said this)
<sipa>
vfP56jSe: the (affine) y coordinate is a quadratic residue if either both or neither the Y and Z jacobian coordinates are quadratic residue (but not if only one of them is)
<sipa>
because y = Y/Z^3; if you multiply with Z^4 (which is definitely a quadratic residue, so it doesn't affect the residuosity of the result), yiu get YZ
<sipa>
so the residuosity of y equals that of YZ
* vfP56jSe
in awe
son0p has quit [Remote host closed the connection]
esotericnonsense has quit [Remote host closed the connection]
Newyorkadam has quit [Quit: Newyorkadam]
esotericnonsense has joined #bitcoin-wizards
spinza has quit [Quit: Coyote finally caught up with me...]
<vfP56jSe>
So when we encode `R` for the signature, we only encode its x-coordinate (affine). But during verification we never reconstruct the y-coordinate from this affine x-coordinate, but rather, after we calculate R = sG - H(r || P || m)P, we check that the x-coordinate of R is r and that the y-coordinate of R is a quadratic residue?
<vfP56jSe>
When R is calculated from R = sG - H(r || P || m)P, is it in affine form or jacobian?
<sipa>
whatever you wa t
<vfP56jSe>
it seems that after calculating R = sG - H(r || P || m)P, we want 1. The affine x-coordinate of R, to check that it is the same as r 2. The jacobian y,z-coordinate of R, to check the residuosity of YZ ? Is that correct?
<sipa>
you can compare an affine coordinate pair with a jacobian one (to see if they refer to the same point) without converting from jacobian to affine
spinza has joined #bitcoin-wizards
pinheadmz has quit [Quit: pinheadmz]
Jackielove4u has joined #bitcoin-wizards
enemabandit has quit [Ping timeout: 240 seconds]
michaelsdunn1 has quit [Remote host closed the connection]
<vfP56jSe>
So, because, given a jacobian coordinate, it is cheap to
<vfP56jSe>
1. Check if it refers to the same point as an affine pair, 2. Check the residuosity of its affine equivalent's y-coordinate
<vfP56jSe>
BUT not cheap to
<vfP56jSe>
1. Check if its affine equivalent's y coordinate is in the lower half, 2. Check if its affine equivalent's y coordinate is even
<vfP56jSe>
this method is more efficient, correct?
<gmaxwell>
checking if the y is 'even' requires converting it to affine.
<gmaxwell>
which is expensive.
<vfP56jSe>
gmaxwell: I see! Do you have nits with my understanding above?
<gmaxwell>
your understanding is correct. Converting to affine is expensive because it requires a modular inversion. But you can do an exact comparsion by converting the affine value to jacobian with the same denominator, by multiplying.
<gmaxwell>
You can't, however, do an even/oddness test that way.
<gmaxwell>
Also really, QRness is really a much more natural tie breaker for point compression. Even/oddness is pretty non-algebraic but just happens to work because the field is prime.
Murch has quit [Quit: Snoozing.]
<sipa>
s/prime/odd/
<gmaxwell>
prime implies odd. :P except for 2... :P
<gmaxwell>
more natural in the sense that the _reason_ that there are even two possibilities is because the sqrt has two possibilities.
<sipa>
yes, but it'd also work for a field of size large-prime-squared e.g.
Murch has joined #bitcoin-wizards
<gmaxwell>
For characteristic-2 curves, there are also multiple possibilities, but you cannot use even/oddness for selecting points, instead you use the trace of the value, which is most similar to testing QRness in other characteristics.