--- Day changed Fri Jan 24 2020 01:23 -!- potatoe_face is now known as _0x0ff 01:39 -!- jonatack [~jon@213.152.161.138] has quit [Ping timeout: 265 seconds] 01:44 -!- _0x0ff [~potatoe@2001:bc8:47b0:123::1] has quit [Quit: into the offlines] 01:45 -!- _0x0ff [~0x0ff@2001:bc8:47b0:123::1] has joined ##taproot-bip-review 01:46 -!- _0x0ff [~0x0ff@2001:bc8:47b0:123::1] has quit [Client Quit] 01:47 -!- _0x0ff [~potatoe_f@2001:bc8:47b0:123::1] has joined ##taproot-bip-review 02:51 -!- jonatack [~jon@109.202.107.15] has joined ##taproot-bip-review 05:25 -!- jonatack [~jon@109.202.107.15] has quit [Quit: jonatack] 06:40 < dr-orlovsky> sipa: sorry if I have missed that discussion before, but I do not see that Tapscript puts any requirements on pubkeys (for being/not being hashed). I assume it follows the general logic of bitcoin script that it does not care about this question unless the script evaluates to a success (i.e. for a hashed public keys one must use `OP_HASH160` command before `OP_CHECKSIG[VERIFY]`). 06:43 < dr-orlovsky> If this is true, it means that an arbitrary public key verification may be embedded into the Tapscript, like a non-standard verification of the public key against single SHA256 hash of the public key before `OP_CHECKSIG[VERIVY]` operation. While this presents no security threat, it may be nice to standartise the exact way of public key checking for Tapscript branches having a single signature - or at least to introduce some best 06:43 < dr-orlovsky> practices regarding that as a comments to the standard 07:05 < harding> dr-orlovsky: I don't understand what you're asking for. Are you aware that the pubkey is included directly in a taproot output? (E.g. `OP_1 OP_PUSH32 `) 07:05 < dr-orlovsky> harding: it's not about taproot, it's about tapscript branches 07:06 < dr-orlovsky> i.e. not about contents of `pubkeyScript`, but rather the script extracted from the witnessScript from witness stack in case of non-cooperative spending 07:11 < harding> So you think someone might add an unnecessary hash check into a witnessScript? E.g., their tapscript branch might be `OP_DUP OP_HASH256 OP_CHECKEQUAL OP_CHECKSIG` rather than the shorter and simpler ` OP_CHECKSIG`? 07:12 < dr-orlovsky> yes, it seems nothing prevents from doing this 07:13 < dr-orlovsky> so my question is this: is this correct (or I messed some part of the spec preventing this) and if yes, may be some best practices may be introduced here as a part of the spec? 07:14 < harding> Agree, nothing prevents them from doing it. 07:15 < harding> In the absence of a recommendation (or perhaps even with one), script creators will probably optimize for the lowest cost script (i.e. smallest size). 07:23 < dr-orlovsky> right. And I don't see how to introduce the non-use of hashes as a requirement at all 07:32 -!- notmandatory [~textual@cpe-76-169-37-102.socal.res.rr.com] has joined ##taproot-bip-review 07:37 < harding> I really don't think there's any need; people who want to maximize their fee savings won't use them. It's the same situation we have with P2SH and P2WSH---nobody adds extra hashes within their redeemScripts/witnessScripts. 07:38 -!- notmandatory [~textual@cpe-76-169-37-102.socal.res.rr.com] has quit [Quit: notmandatory] 07:39 < sipa> you can also create a script of the form OP_NOP OP_NOP OP_NOP OP_NOP ... OP_NOP OP_CHECKSIG 07:39 < sipa> it's inherent in script that you can do things inefficiently 07:48 -!- notmandatory [~textual@cpe-76-169-37-102.socal.res.rr.com] has joined ##taproot-bip-review 08:05 < dr-orlovsky> yes, you are right, I do agree that there is no need in restricting scripting in Tapscript 08:23 -!- notmandatory [~textual@cpe-76-169-37-102.socal.res.rr.com] has quit [Quit: notmandatory] 08:57 -!- fanquake [sid369002@gateway/web/irccloud.com/x-zkuwftvtortbmdik] has quit [] 08:57 -!- fanquake [sid369002@gateway/web/irccloud.com/x-zwtgccesrfcajxon] has joined ##taproot-bip-review 09:05 -!- afk11 [~afk11@gateway/tor-sasl/afk11] has quit [Ping timeout: 240 seconds] 09:06 -!- jonatack [~jon@2a01:e0a:53c:a200:bb54:3be5:c3d0:9ce5] has joined ##taproot-bip-review 09:07 -!- afk11 [~afk11@gateway/tor-sasl/afk11] has joined ##taproot-bip-review 11:12 -!- bsm1175321 [~bsm117532@unaffiliated/bsm117532] has joined ##taproot-bip-review 12:27 -!- michaelfolkson [~textual@2a00:23c5:be04:e501:39f5:978a:5b82:ba27] has joined ##taproot-bip-review 12:28 -!- michaelfolkson [~textual@2a00:23c5:be04:e501:39f5:978a:5b82:ba27] has quit [Client Quit] 13:09 < bsm1175321> People keep asking me to weigh in on quantum computing as it impacts bitcoin. With taproot putting pubkeys in outputs this (may) be a more pressing issue. Have any of you seen any pushback on taproot with a quantum computing argument? 13:13 < gmaxwell> I'm the originator of the idea that hashing is somehow protective, and it's a snakeoil claim. It was offered as an abstract, navel gazing idea, not actually a serious advantage. In practice it isn't one: A majority of circulating bitcoin is stored in reused addresses. An overwhelming majority of wallets including hardware wallets (essentially everything _except_ bitcoin core) force the use 13:13 < gmaxwell> BIP32 public derrivation which is equivilent to reuse for this purpose. 13:13 < sipa> i expected some, but haven't really seen it 13:14 < gmaxwell> It's come up a couple times, but people point out that the presumed protection is largely fictional and it seems to go away. 13:14 < belcher> didnt the quantum computer argument come up as a way to try to convince people not to reuse addresses for privacy? 13:14 < sipa> furthermore, it is effectively impossible to do anything interesting with bitcoin script (not a single key holder) without revealing your public keys to others 13:15 < bsm1175321> I'm familiar with sipa's analysis of already-vulnerable coins due to exposed pubkeys. 13:15 < gmaxwell> It would be totally cool to have quantum safe keys for long term cold storage... but there seems to have been pretty little interest in working on that. 13:15 < bsm1175321> But the argument that exposed pubkeys is somehow more or less vulnerable to a QC than hashes requires further detailed elaboration, to your point gmaxwell. 13:16 < sipa> bsm1175321: ? 13:16 < gmaxwell> belcher: I believe it originally just came up in a navel gazing discussion about the relative advantages of hashing keys instead of just sticking them in addresses. 13:17 < bsm1175321> sipa: maybe it was someone else? 30% or so of coins already have exposed pubkeys or something like that... 13:17 < sipa> bsm1175321: 5.5 M BTC at least 13:17 < gmaxwell> I certantly used it some to argue against reuse. I've regretted it ever since I saw people extending it to saying bitcoin was protected against quantum computers. 13:17 < bsm1175321> https://bitcoin.stackexchange.com/questions/91049/why-does-hashing-public-keys-not-actually-provide-any-quantum-resistance 13:18 < bsm1175321> Yeah, the argument has not been fully justified in my mind. :-/ 13:18 < gmaxwell> that analysis is way too conservative because it ignores public derrivation use. 13:18 < sipa> bsm1175321: which argument? 13:18 < bsm1175321> sipa that hashing is somehow protective against a QC 13:18 < gmaxwell> It is in a vacuum. But we don't exist in a vacuum. :) 13:19 < bsm1175321> ping achow101 with a response on that stackexchange 13:20 < achow101> eh? 13:20 < gmaxwell> sipa: whats the recommended default derrivation for scriptless taproot? is one that at least theoretically could be ZKPOK for the hash preimage? 13:22 < gmaxwell> if so that gives another option for quantum recovery. e.g. you can spend if you QCZKPOK knoweldge of the taproot hash preimage, along with the spend. This has the advantage of being an actual protection, in the sense that it doesn't just depend on racing. 13:22 < sipa> gmaxwell: the bip suggests H+P, i think, with H the hash-of-G-as-x-coord point, and P some public key 13:22 < sipa> which should be easy to prove if you have the private key to P 13:23 < gmaxwell> Sweet. yeah. so there you go. 13:23 < sipa> that's not particularly QC-NIZK friendly though, i think, but it's hard to know what to optimize for as every proof system has wildlh different cost metrics 13:23 < bsm1175321> Anyway I'm considering weighing in on this, have talked to Stepan about it who also has experience. If a QC was NOT capable of breaking hashes or ECC keys (which is my opinion -- but needs strong evidence), this is not something the academic community would generally say as it is not incentive compatible with their grants. 13:24 < bsm1175321> If it IS capable, then we should be discussing upgrade paths. 13:24 < sipa> of course we should be discussion upgrade paths 13:24 < sipa> taproot just isn't one 13:24 < bsm1175321> But I'll need to dig into the literature for a couple months, and ideally produce a paper at the end, and I'd like to figure out how to get paid for that work too... 13:24 < bsm1175321> Not if a QC is incapable of breaking crypto, which I suspect is the case. 13:24 < gmaxwell> So you get a different snake oil QC protection with taproot. It's snakeoilyness is orthorgonal: it can be used for better protection, but its viability depends on QC-NIZK efficiency which we don't have concrete figures for. 13:24 < sipa> bsm1175321: nobody knows 13:25 < bsm1175321> sipa: I claim it is knowable. 13:25 < sipa> bsm1175321: that seems presumptive 13:25 < bsm1175321> Yes I'm presumptive. 13:25 < gmaxwell> bsm1175321: QC isn't even _conjectured_ to do much for finding hash preimages. Breaking ECC is an engineering question. 13:26 < bsm1175321> Well, you get a sqrt(N) speedup at least. 13:26 < gmaxwell> You get the grover speedup for hashes, which is proved to be tight. So anything better at finding hash preimages would have to care about the hash function. 13:26 < bsm1175321> But I think stability of such a large computation may be physically impossible. 13:27 < gmaxwell> bsm1175321: yes, which isn't particularly interesting to this discussion. 2^128 is still an acceptable amount of security. :) 13:27 < bsm1175321> And it's that physically (im)possible-ness-ness that I want to weigh in on. 13:27 < sipa> it may be that there exist fundamental reasons why QC can't scale to the sizes/gates counta necessary to break 256-bit ECDLP... but i'm pretty sure we don't know if any such reasons exist 13:28 < bsm1175321> sipa: that's exactly what I'm claiming, and I know how to find said reasons. 13:28 < sipa> iirc it would need around 2000 (logical) qbits and a few milliom gates 13:28 < gmaxwell> sipa: only if they're noiseless. 13:28 < bsm1175321> yep 13:28 < gmaxwell> which is an unphysical assumption. 13:28 < sipa> that's why i say logical qbits 13:29 < bsm1175321> noise kills. And, may kill the argument that QC will ever break any crypto. 13:29 < sipa> bsm1175321: i'm skeptical both ways 13:29 < gmaxwell> a cohearence time of around 2^32 operations. IIRC. 13:30 < gmaxwell> in any case, it's not really relevant to us. Hardening against ECC breaks is also prudent on the basis of advances in number theory. 13:30 < sipa> i do not think it is at all a given that we'll ever be able to build a sufficiently powerful QC to break 256-bit ECDLP 13:30 < sipa> but i also don't think it is a given that we won't 13:30 < gmaxwell> It's anomalous how strong ECC appears to be. 13:31 < bsm1175321> sipa: I'm skeptical both ways too. The fact that I haven't answered the question for myself keeps me awake at night. 13:31 < gmaxwell> So it might well be that someone eventually finds a way to get DLP performance similar to integers for ECC and then woops, it's all totally insecure. 13:31 < sipa> switch to 15000-bit ECC 13:32 < gmaxwell> s/integers/multiplicative groups/ (to be pedantic) 13:32 < real_or_random> PQ-RSA 13:32 < real_or_random> tbh, I stopped having an opinion on the feasibility of quantum computing 13:33 < bsm1175321> The argument against QC is here: https://spectrum.ieee.org/computing/hardware/the-case-against-quantum-computing 13:33 < bsm1175321> which I think has not been sufficiently detailed in the academic literature, because they're paid to say QC will work. 13:33 < bsm1175321> But all practitioners I know express this skepticism 13:34 < sipa> skepticism is healthy 13:34 < sipa> but 13:34 < sipa> dismissal probably isn't 13:35 < bsm1175321> dismissal requires much stronger evidence than anyone has presented. 13:35 < gmaxwell> bsm1175321: I dunno. I suggest not listening to random academics on engineering questions. E.g. go look at the arguments about equihash's 'asic hardness' which were immediately laughed at by actual hardware engineers (and their laughing has been proved out) 13:35 < real_or_random> I'm at least not qualified because I have no idea about QC 13:35 < bsm1175321> But, I think dismissal is possible. 13:35 < sipa> as a non-expert in the physical aspects of QC, all i can look at is actual progress made 13:35 < bsm1175321> Well, I am a physicist, so that's the angle I'm coming from. 13:36 < sipa> and the progress in QC has been impressive and faster than i expected a frw years ago 13:36 * bsm1175321 is unimpressed. :-P 13:36 < sipa> it has been a race to the start line and not more, but still 13:36 < bsm1175321> All they've really achieved is a super-expensive quantum RNG. 13:36 < gmaxwell> probably the way a disproof will happen there, if ones comes, is from engineers attempting to build larger and larger QC and then hitting an inexplicable wall. The properties of the wall would be tested and new physical laws would be discovered. 13:37 < real_or_random> as a cryptographer, the only thing I can say that in the end we all don't know and we should work on post-quantum crypto. :P 13:37 < sipa> real_or_random: agree... but also not prioritize it above everything else 13:38 < real_or_random> sure 13:38 < bsm1175321> gmaxwell: there are no new physical laws to be found or inexplicable walls. Quantum mechanics is well understood and this question can be answered from first principles. 13:38 < real_or_random> but I think it's pretty common in cryptography to protect against attackers which are so powerful that we don't know if they exist, and there is nothing wrong with it 13:38 < gmaxwell> In any case for this subject wrt bitcoin, I think the NIZK gives at least similar (arguably better) flim flam protection as output hashing does. 13:38 < sipa> bsm1175321: that sounds like a pretty extreme opinion to me 13:39 < bsm1175321> sipa: maybe. It's definitely an opinion at present. But I can see a path to formalizing that statement. 13:39 < real_or_random> sipa: I think for timing the goal should be to have something usable on the shelf just in case. that's why it's good now to start writing standards etc 13:40 < sipa> gmaxwell: taproot adds another (hardly relevant, but perhaps more so) property: it will cause economocally relevant spendable outputs to be created, which if spent through the key path result in a transferable proof ECDLP is broken 13:40 < real_or_random> and it also depends on the primitive in question 13:40 < real_or_random> signatures/authentication vs encryption is an entirely different debate 13:40 < gmaxwell> sipa: too bad the taproot commitment isn't P + H(P || H(script)) because you could NIZK that Q is that for some undisclosed P and then provide the script. 13:41 < sipa> gmaxwell: how is it not? 13:41 < sipa> second "H" is Merkle tree 13:41 < gmaxwell> sipa: there is no second hash is right? ... oh hm. 13:41 < sipa> even in case the merkle tree has 1 leaf there is an additional hash 13:41 < gmaxwell> Sweet. Well there we go. 13:42 < real_or_random> yep it's just a singe hash inside the NIZK proof 13:43 < gmaxwell> We just need a pair of NIZK one where the prover provides either P and the root, or the other where they provide the private key and the root. 13:43 < real_or_random> ah you could even prove with the secret key, yep. 13:44 < bsm1175321> FWIW, I want to see taproot move forward and hope handwavy quantum arguments aren't a roadblock. If the topic heats up though, someone please ping me, it's on my mind. 13:44 < real_or_random> by the way, all of this assumes that SHA256 is not broken 13:44 < gmaxwell> And then if EC is broken, you do spending via the NIZK later. Bonus points, add a consensus rule where all transactions are blocked once someone proves knoweldge of a DL of a NUMS point. :P 13:44 < real_or_random> which people never consider for some reason 13:45 < sipa> real_or_random: imagine SHA256 was as broken as MD5 is today, would we have a problem? 13:45 < real_or_random> I have no idea 13:45 < gmaxwell> bsm1175321: arguably, based on the above, taproot provides a much stronger protection path for QC. Because _every_ taproot output, if constructed accoring to spec..will be possible to make spendable via a proof. 13:45 < real_or_random> but it's an interesting idea to think about it 13:45 < bsm1175321> gmaxwell: that's a good argument that perhaps should be made more formally? 13:46 < gmaxwell> real_or_random: our conclusion about that previously was largely no. 13:46 < gmaxwell> bsm1175321: well it's been pointed out before. 13:46 < gmaxwell> it's all still snakeoil, I'm disinclined to advance it much given my past expirence. 13:47 < real_or_random> gmaxwell: the thing is that also this holds only if people construct their ordinary UTXOs with a hash 13:47 < gmaxwell> thus "according to spec" 13:48 < real_or_random> I see 13:48 < sipa> at some point we removed the "you can use a pubkey directly as taproot output" from the bip for a related reason afaik 13:48 < bsm1175321> Yes, snakeoil. At some point I think someone will demand a careful document/paper answering (1) is QC going to break sha256 or ECC (and how, and when) and (2) what are our options if #1 is answered in the affirmative. 13:48 < bsm1175321> There's lots of hand-waving on #2 and at some point we might have to get serious about it. 13:49 < sipa> bsm1175321: the answer to #2 is: we have migrated to PQC signatures before #1 happens 13:49 < bsm1175321> Given the large size of PQC signatures, that would be very unpalatable to do prematurely. :-P 13:50 < real_or_random> we could force every 100th UTXO to reveal the script when spending, even in key-path spending :P that's sufficient incentive to stick to the spec 13:50 < sipa> bsm1175321: exactly 13:50 < sipa> but even if sufficiently powerful QC ever becomes a reality, it seems very improbable that we won't see it coming 13:51 < bsm1175321> Also the form of PQC depends on how QC will break things...did you assume sha256 remained secure while ECC was broken, or the opposite, in committing to the PQC mechanism? 13:51 < sipa> i assume SHA256 remains secure 13:51 < bsm1175321> From my understanding, that's not a safe assumption... 13:52 < bsm1175321> And if it is, needs careful justification ;-) 13:52 < real_or_random> bsm1175321: do you have a better assumption? 13:52 < bsm1175321> Well I'd like to prove that a QC can break neither, and I think I can do it. 13:52 < sipa> bsm1175321: if you can find arbitrarily-structured SHA256 collisions, you can break *consensus* 13:53 < real_or_random> for some reason the debate about QC seems to attract people magically. so far QC are really not our biggest issue when it comes to security 13:53 < bsm1175321> QC is magical thinking. 13:53 < sipa> real_or_random: agree 13:53 < andytoshi> i think maybe some of us should become QC experts so that the discussion among experts stops being similar to the discussion among laymen 13:54 < andytoshi> and maybe then randos would stop chiming in :P 13:54 < sipa> andytoshi: have you spent any time at all on the internet? 13:54 < andytoshi> similar to how we can usually make cryptographic decisions and nobody complains because nobody understands them 13:54 < andytoshi> sipa: hahah ok 13:54 < bsm1175321> andytoshi: I've been asked to be on a panel for exactly that purpose, but I need to dig into the literature to be credible. 13:54 < real_or_random> with >50% you can revert transactions and that's more realistic than a QC currently 13:54 < bsm1175321> And I'm not going to do that unless I find the time to convince myself one way or another. 13:55 < andytoshi> bsm1175321: oh, very cool, i hope to hear you speak about this at some point 13:55 < sipa> bsm1175321: if you can prove crypto-breaking QC is non-physical i suspect you can win a nobel prize :) 13:55 < real_or_random> but when I point this out, a lot of people will tell me that either this will never happen, we can hardfork to another hash, or it does not break bitcoin's security model 13:55 < bsm1175321> sipa: No one wins Nobels for negative results. But an entire industry is dis-incentivized to write the proof. 13:56 < real_or_random> but then people talk about QC 13:56 < bsm1175321> But literally *every* physicist I've spoken to expresses that opinion informally 13:56 < sipa> bsm1175321: people also legitimately believed human flight was impossible at some point, with very well argued points 13:57 < sipa> the difference between "we currently don't see how it could ever happen" and "it can't happen" is enormous 13:57 < bsm1175321> sipa: this is pure math though. It comes down to a flaw in their arguments about error correction. 13:59 < real_or_random> sipa: reminds of a discussion at the PETS conference. one person: we never manage to build privacy-preserving systems because we assume a way too strong attacker and then we can't protect against it 14:00 < real_or_random> other person: well I thought the same and then came snowden and suddenly a lot of "oversimplifying/too academic" threat models made sense 14:12 < sipa> ha 14:13 < bsm1175321> Well the good thing about physics is that you can get hard answers. You can't engineer physical reality away. 14:14 < bsm1175321> And tuning any physical state to a precision of 2^-256 is simply not physically possible. 14:14 < sipa> bsm1175321: do you believe that if we had perfect control over atom placement, you could not build a crypto-breaking QC? 14:15 < bsm1175321> If you did, you could. But you can't. 14:15 < bsm1175321> And that's the crux of the argument. 14:15 < sipa> sure, but you can't prove that we don't? 14:15 < sipa> as that is an engineering question 14:15 < bsm1175321> There's this annoying little thing called the uncertainty principle... 14:15 < bsm1175321> and it can't be engineered away 14:16 < sipa> just compensate by building it inside a car, and being really unsure about how fast it goes 14:16 * sipa hides 14:16 < bsm1175321> (Delta p)*(Delta x) >= hbar/2 --- so if you have perfect control over atom placement, you have no idea of the momentum, and therefore, you're talking about a high-temperature system. 14:17 < bsm1175321> hahaaaa 14:18 < bsm1175321> high temperature systems collide with nearby atomic states, and decohere, destroying the quantum state. It's a Sisyphean challenge. 14:56 < andytoshi> bsm1175321: i'm unconvinced by this "precision of 2^-256 is impossible" argument, because it ignores how large/multidimensional the space is. 14:57 < andytoshi> certainly _classical_ computers can represent 256-bit numbers reliably without flipping 14:57 < andytoshi> and there's some intuitive argument in this article that with QC you're not "flipping", you're adjusting continuous numbers, so ofc there will be noise and you can't maintain specific states 14:58 < andytoshi> but in a high-dimensional space you can have 2^256 states and still have tons of space between them all 14:58 < andytoshi> i dunno. still reading (and sorry for the offtopicness) 15:22 < bsm1175321> andytoshi: I agree that argument is handwavy. 15:24 < bsm1175321> Well, there's two problems, first is encoding the initial state in the first place. Cross-bit correlations and imprecision in that encoding. Second problem is thermal noise from the environment. 15:25 < bsm1175321> If you can encode a single state with a precision of 10^-3 which they claim, this would seem to imply the computation would break down after 1000 steps. 15:25 < bsm1175321> So the argument comes down to how well the error correction argument holds up. 15:26 < bsm1175321> As the above article states, it only works "under certain assumptions" which I fear are unphysical. 19:52 -!- afk11 [~afk11@gateway/tor-sasl/afk11] has quit [Ping timeout: 240 seconds] 19:55 -!- afk11 [~afk11@gateway/tor-sasl/afk11] has joined ##taproot-bip-review 20:37 -!- notmandatory [~textual@cpe-76-169-37-102.socal.res.rr.com] has joined ##taproot-bip-review 20:42 -!- notmandatory [~textual@cpe-76-169-37-102.socal.res.rr.com] has quit [Ping timeout: 272 seconds] 20:58 -!- notmandatory [~textual@185.236.200.174] has joined ##taproot-bip-review 21:03 -!- notmandatory [~textual@185.236.200.174] has quit [Ping timeout: 265 seconds] 21:03 -!- notmandatory [~textual@84.17.37.67] has joined ##taproot-bip-review 21:10 -!- notmandatory [~textual@84.17.37.67] has quit [Quit: notmandatory] 22:29 -!- afk11 [~afk11@gateway/tor-sasl/afk11] has quit [Ping timeout: 240 seconds] 22:31 -!- afk11 [~afk11@gateway/tor-sasl/afk11] has joined ##taproot-bip-review