12020-01-24T02:08:19  <jeremyrubin> If I look at an arbitrary Taproot key K, can I test if the root is R without knowing anything else? No, right? I need to know Q such that Q tweaked with R is K?
  22020-01-24T02:09:37  <sipa> if K = Q + H(Q||R)G, and R is uniformly random, then K is computationally indistinguishable from uniformly random
  32020-01-24T02:10:21  <sipa> so not only can you not test for it, you can in fact not learn anything at all about R if you don't know Q
  42020-01-24T02:11:57  <sipa> this goes both ways; if either Q or R is unknown and uniformly random, K will be indistinguishable from uniformly random
  52020-01-24T02:12:02  <jeremyrubin> right. And vice versa -- you can't learn anything of Q only knowing R and K because you can't compute H(Q||R)G
  62020-01-24T02:13:03  <jeremyrubin> But it would be possible, in theory, were you to learn the midstate of H(Q||...) (and assuming some padding or something) then you could compute K-H(Q||R) G = Q without knowing Q
  72020-01-24T02:14:54  <jeremyrubin> (but Q is 32 bytes so for sha256 there is non midstate you could send without revealing Q)
  82020-01-24T02:15:55  <jeremyrubin> I don't have a use for this, just checking that my understanding is correct.
  92020-01-24T02:16:10  <sipa> all seems right
 102020-01-24T02:17:32  <gmaxwell> you could also do ZKPs over any of these values.
 112020-01-24T02:18:24  <jeremyrubin> Interestingly, there's sort of provably no use for having H(H(Q) || R) instead of  H(Q || R) because to send over the midstate so that you might compute Q from K, R you may as well just send Q.
 122020-01-24T02:19:49  <gmaxwell> in general learning H(Q) or midstate(Q) is also pretty close to equivilent to revealing Q.
 132020-01-24T02:20:47  <jeremyrubin> The thing I'm brainstorming a little in the ##ctv-bip-review channel is the case where a sender picks some random key K, encrypts it to your key  YG and includes it as op_return or whatever, computes a MusigKey(YG, KG), then you can do something like stealth addresses.
 142020-01-24T02:21:12  <jeremyrubin> The thing I was thinking of in particular, is if there was a way to put in the Tapscript an OP_CTV to paying your unencumbered key
 152020-01-24T02:21:21  <jeremyrubin> then you can skip encrypting K
 162020-01-24T02:21:33  <jeremyrubin> and just do opportunistic multisig for privacy
 172020-01-24T02:22:08  <jeremyrubin> But that *only* works if there's some way for the owner of key Y to see that their tapscript is for them without knowing K
 182020-01-24T02:22:37  <jeremyrubin> But as this seems to not be the case, you would still need to learn at least KG for this protocol to work
 192020-01-24T02:22:54  <sipa> not revealing any information about the scripts to someone who doesn't know the internal pubkey is an intentional privacy property
 202020-01-24T02:23:05  <jeremyrubin> Reasonable
 212020-01-24T02:23:56  <jeremyrubin> You'd have to encrypt it and include an op_return or communicate out of band, so there's not really an improvement (other than maybe in terms of API) from stealth addresses today
 222020-01-24T02:24:38  <jeremyrubin> Has anyone written up post-taproot stealth addresses?
 232020-01-24T02:25:44  <sipa> i don't think stealth addresses are interesting as they require putting unnecessary data onchain
 242020-01-24T02:26:05  <sipa> my best guess for solving the practical problem they solve is lightning
 252020-01-24T02:26:21  <gmaxwell> sipa: one could technically use one of the signature's Rs...
 262020-01-24T02:26:33  <gmaxwell> joinmarket donations work that way, IIRC.
 272020-01-24T02:27:03  <jeremyrubin> Clever -- so you spend, and then the R value is decrypted by the recipient to reveal the tweak?
 282020-01-24T02:27:30  <sipa> gmaxwell: have any reference?
 292020-01-24T02:28:06  <sipa> needing to do EC operations to detect incoming transactions is annoying too
 302020-01-24T02:28:21  <gmaxwell> jeremyrubin: the tweak is ECDH with a sender provided point and a recipent pubkey (which is part of their address)... reuse of r just uses R as the senders point.
 312020-01-24T02:28:45  <sipa> gmaxwell: where does the sender provide the point?
 322020-01-24T02:28:51  <jeremyrubin> That's different than stealth addresses though IIRC
 332020-01-24T02:28:57  <gmaxwell> jeremyrubin: no its not.
 342020-01-24T02:29:02  <jeremyrubin> For a stealth address isn't the point encrypted
 352020-01-24T02:29:20  <jeremyrubin> So that an adversary aware of recipient PK can't check who it belongs to?
 362020-01-24T02:29:46  <gmaxwell> jeremyrubin: DDH means they cannot check.
 372020-01-24T02:29:58  <jeremyrubin> ah ok
 382020-01-24T02:30:24  <gmaxwell> sipa: the R value of one of their signatures. (e.g. the first, or any and you just have to check all of them)
 392020-01-24T02:30:37  <jeremyrubin> But by picking R this way is there risk of revealing the senders SK?
 402020-01-24T02:30:46  <gmaxwell> sipa: you sign using a nonce generating function that returns k in the aux data.
 412020-01-24T02:31:00  <jeremyrubin> Need to re-read on DDH
 422020-01-24T02:31:03  <gmaxwell> R isn't picked in a special way.
 432020-01-24T02:31:10  <jeremyrubin> Gotcha!
 442020-01-24T02:31:20  <sipa> jeremyrubin: DDH means that given 4 points A,B,C,D you cannot check whether A/B = C/D
 452020-01-24T02:31:53  <gmaxwell> You could break security mishandling the returned k, for sure.  So don't mishandle it. :) any kind of cryptographic software is dangerous. :)
 462020-01-24T02:31:55  <sipa> or formulated alternatively, you cannot distinguish tuples (G,aG,bG,abG) from random 4-tuples
 472020-01-24T02:32:05  <jeremyrubin> So you send the funds to rKG basically?
 482020-01-24T02:32:27  <sipa> jeremyrubin: does not compute - you can't multiple two points
 492020-01-24T02:32:32  <jeremyrubin> Ah
 502020-01-24T02:32:34  <jeremyrubin> I mean
 512020-01-24T02:32:35  <jeremyrubin> rkG
 522020-01-24T02:33:06  <jeremyrubin> and the sender can compute that by mult kR
 532020-01-24T02:33:19  <jeremyrubin> but can't ever learn r this way since they just know R
 542020-01-24T02:33:35  <jeremyrubin> Wait but how do they then sign?
 552020-01-24T02:33:37  <gmaxwell> No, the user gives you two pubkeys. P1 and P2. (technically you can do one but then you can't delegate scanning).   you compute their address as H(kP1)G + P2.
 562020-01-24T02:34:10  <gmaxwell> and you pick k however you want, and use that k in your signature.
 572020-01-24T02:34:26  <sipa> ah, neat
 582020-01-24T02:34:34  <jeremyrubin> Sorry, I feel I'm sufficienly ill informed on stealth addresses mechanics that I just know the general concept but not the actual protocol. Thx for explaining
 592020-01-24T02:34:52  <gmaxwell> The recipent scans all transactions and yanks out their r's  and computes H(x1R)G + x2 and sees if that address got paid.
 602020-01-24T02:35:31  <gmaxwell> it's the same protocol, but instead of commuincating a point in an opreturn you abuse the fact that the signature already has a point in it.
 612020-01-24T02:35:40  <jeremyrubin> Neat
 622020-01-24T02:36:12  <gmaxwell> this does, however, require your wallet do ecdh with every transaction. but like a fast desktop can do 6000/sec/core or whatever, so not really an issue.
 632020-01-24T02:36:47  <sipa> can you scan for multiple P1/P2 pairs simultaneously any faster?
 642020-01-24T02:36:53  <gmaxwell> regular stealth addresses are exactly the same but use an op return and have some additional hash (optional?) you can use to skip irrelevant outputs at the expense of your privacy.
 652020-01-24T02:37:10  <sipa> seems not, apart from some batch inversion maybe
 662020-01-24T02:37:14  <gmaxwell> sipa: not really.
 672020-01-24T02:37:16  <gmaxwell> right.
 682020-01-24T02:38:14  <gmaxwell> Thats one of the reasons I liked the 'rerandomizable dual point pubkeys' idea, because it means you could give out lots of distinct addresses and stil scan them with one key. :)
 692020-01-24T02:38:33  <jeremyrubin> I like the idea that someone else could ZKP you are not the owner of a tx in a block tho
 702020-01-24T02:38:41  <jeremyrubin> s/tx/output/
 712020-01-24T02:38:50  <jeremyrubin> that would make the outsourcing better
 722020-01-24T02:39:26  <jeremyrubin> So then no outsourcer can lie to you about finding funds
 732020-01-24T02:41:16  <gmaxwell> I don't think outsourcing really makes a lot of sense, except in so far as that "outsoucrcing" lets you preserve a good online wallet/ offline wallet split.
 742020-01-24T02:41:43  <gmaxwell> The problem is that essentially anyone who would _offer_ outsourcing would inevitably be in the surveilance business. Because duh.
 752020-01-24T02:42:22  <jeremyrubin> Well...
 762020-01-24T02:42:29  <gmaxwell> (and indeed, we know from calling up tracking companies and pretending to be customers that they're getting data from existing things like that)
 772020-01-24T02:42:30  <jeremyrubin> You can share a P2 with a set of people!
 782020-01-24T02:42:51  <jeremyrubin> balancing out the "scan everything" v.s. "scan some things"
 792020-01-24T02:43:12  <gmaxwell> In any case, scanning everything is pretty cheap regardless.
 802020-01-24T02:43:20  <gmaxwell> Monero works that way inherently.
 812020-01-24T02:43:27  <gmaxwell> And it seems to work well enough.
 822020-01-24T02:43:31  <jeremyrubin> So another question:
 832020-01-24T02:43:39  <jeremyrubin> Given a known Taproot X
 842020-01-24T02:43:46  <jeremyrubin> Can someone  re-blind it?
 852020-01-24T02:43:59  <jeremyrubin> Or would that interfere?
 862020-01-24T02:44:47  <sipa> no, because the hash commits to all the inputs
 872020-01-24T02:45:00  <sipa> (and it has to)
 882020-01-24T02:45:07  <gmaxwell> you can make a version of that above scheme that works with taproot but the existance of the script cannot be hidden.
 892020-01-24T02:45:18  <gmaxwell> I mean, can't be hidden from the sender.
 902020-01-24T02:45:23  <jeremyrubin> right
 912020-01-24T02:45:28  <jeremyrubin> Because they need to tweak Q
 922020-01-24T02:45:29  *** notmandatory has joined ##taproot-bip-review
 932020-01-24T02:45:34  <jeremyrubin> Is that correct?
 942020-01-24T02:45:43  <gmaxwell> Right.
 952020-01-24T02:45:52  <jeremyrubin> Seems not the ~worst~ tradeoff
 962020-01-24T02:46:05  <jeremyrubin> Gain 1 privacy lose 1 privacy
 972020-01-24T02:46:56  <gmaxwell> of course, if you can interact with the recipent you can just ask them to generate you an address and the need for any of this stuff goes away.
 982020-01-24T02:47:35  <jeremyrubin> Well... sort of. I think stealth addresses are actually really useuful for interacting with cold wallets in a sense.
 992020-01-24T02:47:47  <jeremyrubin> When you don
1002020-01-24T02:47:59  <jeremyrubin> *don't want to / can't do public HD key derivation
1012020-01-24T02:48:14  <jeremyrubin> and you don't have a cache of pre-generated HD keys
1022020-01-24T02:49:19  <gmaxwell> I mean, this _is_ a public HD key derrivation... so whatever reason you have for not using that should apply here equally.
1032020-01-24T02:49:54  <jeremyrubin> The difference being that you're encoding the tweak param in the txn
1042020-01-24T02:50:07  <jeremyrubin> making it so you don't need to store the tweak, it's in the txdata
1052020-01-24T02:50:24  <jeremyrubin> Above just storing the blockchain that is
1062020-01-24T02:50:44  <gmaxwell> you don't need to store it in any case. It can just be some hash of your private key, for example.
1072020-01-24T02:51:22  <gmaxwell> And as far as scanning goes, yes you have to scan but thats true for the stealth address too and it's a much more expensive scan that also requires and ECDH with each transaction.
1082020-01-24T02:51:36  <jeremyrubin> fair pt
1092020-01-24T02:51:54  * jeremyrubin afk
1102020-01-24T02:52:36  <gmaxwell> I don't think they're useless, but I think their applicability is pretty narrow.  Essentially they're great for public donation addresses.  In most other circumstances you have two way communication.
1112020-01-24T02:53:02  <gmaxwell> There are great reasons to not use public derrivation unfortunately they all apply to stealth addresses equally.
1122020-01-24T03:08:09  <maaku> gmaxwell: most times in real life I make payments I don't have two-way low latency electronic communication available
1132020-01-24T03:15:06  *** notmandatory has quit IRC
1142020-01-24T03:20:58  <gmaxwell> you have two way communication available or how would you know you need to pay / know that the thing you've paid for is done.
1152020-01-24T03:21:24  <gmaxwell> You might not be paying electronically at all, sure, but the communication is kind of inherent in the whole act of 'paying'.
1162020-01-24T04:15:48  *** notmandatory has joined ##taproot-bip-review
1172020-01-24T04:24:27  <maaku> gmaxwell: instructions are often relayed one-way and/or reused
1182020-01-24T04:24:52  <maaku> e.g. "send a wire transfer with these routing numbers..."
1192020-01-24T04:26:07  <maaku> and what I am given is a generic PDF
1202020-01-24T04:26:41  <maaku> they know I paid not because of some memo field, which would count as 2-way communication, but because some human checks that the desired amount showed up
1212020-01-24T04:27:43  <maaku> I mean, tihs is a clunky brittle system and we can do better. But it's not exactly accurate to say that in most circumstances you have suitable two-way communication setup
1222020-01-24T04:29:55  <maaku> prior to payment
1232020-01-24T04:30:11  <maaku> which is communication itself, I suppose
1242020-01-24T06:39:21  *** notmandatory has quit IRC
1252020-01-24T09:23:19  *** potatoe_face is now known as _0x0ff
1262020-01-24T09:39:21  *** jonatack has quit IRC
1272020-01-24T09:44:56  *** _0x0ff has quit IRC
1282020-01-24T09:45:17  *** _0x0ff has joined ##taproot-bip-review
1292020-01-24T09:46:46  *** _0x0ff has quit IRC
1302020-01-24T09:47:11  *** _0x0ff has joined ##taproot-bip-review
1312020-01-24T10:51:49  *** jonatack has joined ##taproot-bip-review
1322020-01-24T13:25:23  *** jonatack has quit IRC
1332020-01-24T14:40:24  <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]`).
1342020-01-24T14:43:14  <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
1352020-01-24T14:43:14  <dr-orlovsky>  practices regarding that as a comments to the standard
1362020-01-24T15:05:02  <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 <pubkey>`)
1372020-01-24T15:05:59  <dr-orlovsky> harding: it's not about taproot, it's about tapscript branches
1382020-01-24T15:06:45  <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
1392020-01-24T15:11:52  <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 <hash> OP_CHECKEQUAL OP_CHECKSIG` rather than the shorter and simpler `<pubkey> OP_CHECKSIG`?
1402020-01-24T15:12:15  <dr-orlovsky> yes, it seems nothing prevents from doing this
1412020-01-24T15:13:05  <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?
1422020-01-24T15:14:15  <harding> Agree, nothing prevents them from doing it.
1432020-01-24T15:15:34  <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).
1442020-01-24T15:23:36  <dr-orlovsky> right. And I don't see how to introduce the non-use of hashes as a requirement at all
1452020-01-24T15:32:40  *** notmandatory has joined ##taproot-bip-review
1462020-01-24T15:37:27  <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.
1472020-01-24T15:38:28  *** notmandatory has quit IRC
1482020-01-24T15:39:16  <sipa> you can also create a script of the form OP_NOP OP_NOP OP_NOP OP_NOP ... OP_NOP <key> OP_CHECKSIG
1492020-01-24T15:39:31  <sipa> it's inherent in script that you can do things inefficiently
1502020-01-24T15:48:59  *** notmandatory has joined ##taproot-bip-review
1512020-01-24T16:05:12  <dr-orlovsky> yes, you are right, I do agree that there is no need in restricting scripting in Tapscript
1522020-01-24T16:23:58  *** notmandatory has quit IRC
1532020-01-24T16:57:04  *** fanquake has quit IRC
1542020-01-24T16:57:20  *** fanquake has joined ##taproot-bip-review
1552020-01-24T17:05:03  *** afk11 has quit IRC
1562020-01-24T17:06:26  *** jonatack has joined ##taproot-bip-review
1572020-01-24T17:07:53  *** afk11 has joined ##taproot-bip-review
1582020-01-24T19:12:23  *** bsm1175321 has joined ##taproot-bip-review
1592020-01-24T20:27:44  *** michaelfolkson has joined ##taproot-bip-review
1602020-01-24T21:09:57  <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?
1612020-01-24T21:13:49  <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
1622020-01-24T21:13:50  <gmaxwell> BIP32 public derrivation which is equivilent to reuse for this purpose.
1632020-01-24T21:13:50  <sipa> i expected some, but haven't really seen it
1642020-01-24T21:14:18  <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.
1652020-01-24T21:14:54  <belcher> didnt the quantum computer argument come up as a way to try to convince people not to reuse addresses for privacy?
1662020-01-24T21:14:56  <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
1672020-01-24T21:15:15  <bsm1175321> I'm familiar with sipa's analysis of already-vulnerable coins due to exposed pubkeys.
1682020-01-24T21:15:44  <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.
1692020-01-24T21:15:53  <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.
1702020-01-24T21:16:28  <sipa> bsm1175321: ?
1712020-01-24T21:16:39  <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.
1722020-01-24T21:17:17  <bsm1175321> sipa: maybe it was someone else? 30% or so of coins already have exposed pubkeys or something like that...
1732020-01-24T21:17:29  <sipa> bsm1175321: 5.5 M BTC at least
1742020-01-24T21:17:38  <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.
1752020-01-24T21:17:46  <bsm1175321> https://bitcoin.stackexchange.com/questions/91049/why-does-hashing-public-keys-not-actually-provide-any-quantum-resistance
1762020-01-24T21:18:07  <bsm1175321> Yeah, the argument has not been fully justified in my mind. :-/
1772020-01-24T21:18:12  <gmaxwell> that analysis is way too conservative because it ignores public derrivation use.
1782020-01-24T21:18:20  <sipa> bsm1175321: which argument?
1792020-01-24T21:18:31  <bsm1175321> sipa that hashing is somehow protective against a QC
1802020-01-24T21:18:57  <gmaxwell> It is in a vacuum. But we don't exist in a vacuum. :)
1812020-01-24T21:19:20  <bsm1175321> ping achow101 with a response on that stackexchange
1822020-01-24T21:20:09  <achow101> eh?
1832020-01-24T21:20:35  <gmaxwell> sipa: whats the recommended default derrivation for scriptless taproot?  is one that at least theoretically could be ZKPOK for the hash preimage?
1842020-01-24T21:22:05  <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.
1852020-01-24T21:22:21  <sipa> gmaxwell: the bip suggests H+P, i think, with H the hash-of-G-as-x-coord point, and P some public key
1862020-01-24T21:22:34  <sipa> which should be easy to prove if you have the private key to P
1872020-01-24T21:23:35  <gmaxwell> Sweet. yeah. so there you go.
1882020-01-24T21:23:40  <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
1892020-01-24T21:23:57  <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.
1902020-01-24T21:24:04  <bsm1175321> If it IS capable, then we should be discussing upgrade paths.
1912020-01-24T21:24:23  <sipa> of course we should be discussion upgrade paths
1922020-01-24T21:24:28  <sipa> taproot just isn't one
1932020-01-24T21:24:30  <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...
1942020-01-24T21:24:46  <bsm1175321> Not if a QC is incapable of breaking crypto, which I suspect is the case.
1952020-01-24T21:24:50  <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.
1962020-01-24T21:24:55  <sipa> bsm1175321: nobody knows
1972020-01-24T21:25:16  <bsm1175321> sipa: I claim it is knowable.
1982020-01-24T21:25:30  <sipa> bsm1175321: that seems presumptive
1992020-01-24T21:25:39  <bsm1175321> Yes I'm presumptive.
2002020-01-24T21:25:52  <gmaxwell> bsm1175321: QC isn't even _conjectured_ to do much for finding hash preimages.  Breaking ECC is an engineering question.
2012020-01-24T21:26:42  <bsm1175321> Well, you get a sqrt(N) speedup at least.
2022020-01-24T21:26:50  <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.
2032020-01-24T21:26:56  <bsm1175321> But I think stability of such a large computation may be physically impossible.
2042020-01-24T21:27:27  <gmaxwell> bsm1175321: yes, which isn't particularly interesting to this discussion. 2^128 is still an acceptable amount of security. :)
2052020-01-24T21:27:34  <bsm1175321> And it's that physically (im)possible-ness-ness that I want to weigh in on.
2062020-01-24T21:27:37  <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
2072020-01-24T21:28:10  <bsm1175321> sipa: that's exactly what I'm claiming, and I know how to find said reasons.
2082020-01-24T21:28:14  <sipa> iirc it would need around 2000 (logical) qbits and a few milliom gates
2092020-01-24T21:28:24  <gmaxwell> sipa: only if they're noiseless.
2102020-01-24T21:28:25  <bsm1175321> yep
2112020-01-24T21:28:32  <gmaxwell> which is an unphysical assumption.
2122020-01-24T21:28:34  <sipa> that's why i say logical qbits
2132020-01-24T21:29:24  <bsm1175321> noise kills. And, may kill the argument that QC will ever break any crypto.
2142020-01-24T21:29:43  <sipa> bsm1175321: i'm skeptical both ways
2152020-01-24T21:29:43  <gmaxwell> a cohearence time of around 2^32 operations. IIRC.
2162020-01-24T21:30:10  <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.
2172020-01-24T21:30:31  <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
2182020-01-24T21:30:42  <sipa> but i also don't think it is a given that we won't
2192020-01-24T21:31:00  <gmaxwell> It's anomalous how strong ECC appears to be.
2202020-01-24T21:31:05  <bsm1175321> sipa: I'm skeptical both ways too. The fact that I haven't answered the question for myself keeps me awake at night.
2212020-01-24T21:31:36  <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.
2222020-01-24T21:31:59  <sipa> switch to 15000-bit ECC
2232020-01-24T21:32:09  <gmaxwell> s/integers/multiplicative groups/ (to be pedantic)
2242020-01-24T21:32:31  <real_or_random> PQ-RSA
2252020-01-24T21:32:59  <real_or_random> tbh, I stopped having an opinion on the feasibility of quantum computing
2262020-01-24T21:33:32  <bsm1175321> The argument against QC is here: https://spectrum.ieee.org/computing/hardware/the-case-against-quantum-computing
2272020-01-24T21:33:47  <bsm1175321> which I think has not been sufficiently detailed in the academic literature, because they're paid to say QC will work.
2282020-01-24T21:33:56  <bsm1175321> But all practitioners I know express this skepticism
2292020-01-24T21:34:12  <sipa> skepticism is healthy
2302020-01-24T21:34:28  <sipa> but
2312020-01-24T21:34:36  <sipa> dismissal probably isn't
2322020-01-24T21:35:05  <bsm1175321> dismissal requires much stronger evidence than anyone has presented.
2332020-01-24T21:35:13  <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)
2342020-01-24T21:35:14  <real_or_random> I'm at least not qualified because I have no idea about QC
2352020-01-24T21:35:18  <bsm1175321> But, I think dismissal is possible.
2362020-01-24T21:35:45  <sipa> as a non-expert in the physical aspects of QC, all i can look at is actual progress made
2372020-01-24T21:35:46  <bsm1175321> Well, I am a physicist, so that's the angle I'm coming from.
2382020-01-24T21:36:04  <sipa> and the progress in QC has been impressive and faster than i expected a frw years ago
2392020-01-24T21:36:18  * bsm1175321 is unimpressed. :-P
2402020-01-24T21:36:21  <sipa> it has been a race to the start line and not more, but still
2412020-01-24T21:36:36  <bsm1175321> All they've really achieved is a super-expensive quantum RNG.
2422020-01-24T21:36:50  <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.
2432020-01-24T21:37:22  <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
2442020-01-24T21:37:57  <sipa> real_or_random: agree... but also not prioritize it above everything else
2452020-01-24T21:38:03  <real_or_random> sure
2462020-01-24T21:38:04  <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.
2472020-01-24T21:38:31  <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
2482020-01-24T21:38:42  <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.
2492020-01-24T21:38:45  <sipa> bsm1175321: that sounds like a pretty extreme opinion to me
2502020-01-24T21:39:20  <bsm1175321> sipa: maybe. It's definitely an opinion at present. But I can see a path to formalizing that statement.
2512020-01-24T21:39:59  <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
2522020-01-24T21:40:10  <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
2532020-01-24T21:40:11  <real_or_random> and it also depends on the primitive in question
2542020-01-24T21:40:29  <real_or_random> signatures/authentication vs encryption is an entirely different debate
2552020-01-24T21:40:30  <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.
2562020-01-24T21:41:04  <sipa> gmaxwell: how is it not?
2572020-01-24T21:41:15  <sipa> second "H" is Merkle tree
2582020-01-24T21:41:22  <gmaxwell> sipa: there is no second hash is right?  ... oh hm.
2592020-01-24T21:41:49  <sipa> even in case the merkle tree has 1 leaf there is an additional hash
2602020-01-24T21:41:57  <gmaxwell> Sweet. Well there we go.
2612020-01-24T21:42:51  <real_or_random> yep it's just a singe hash inside the NIZK proof
2622020-01-24T21:43:17  <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.
2632020-01-24T21:43:59  <real_or_random> ah you could even prove with the secret key, yep.
2642020-01-24T21:44:09  <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.
2652020-01-24T21:44:10  <real_or_random> by the way, all of this assumes that SHA256 is not broken
2662020-01-24T21:44:11  <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
2672020-01-24T21:44:23  <real_or_random> which people never consider for some reason
2682020-01-24T21:45:09  <sipa> real_or_random: imagine SHA256 was as broken as MD5 is today, would we have a problem?
2692020-01-24T21:45:28  <real_or_random> I have no idea
2702020-01-24T21:45:35  <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.
2712020-01-24T21:45:40  <real_or_random> but it's an interesting idea to think about it
2722020-01-24T21:45:58  <bsm1175321> gmaxwell: that's a good argument that perhaps should be made more formally?
2732020-01-24T21:46:01  <gmaxwell> real_or_random: our conclusion about that previously was largely no.
2742020-01-24T21:46:11  <gmaxwell> bsm1175321: well it's been pointed out before.
2752020-01-24T21:46:33  <gmaxwell> it's all still snakeoil, I'm disinclined to advance it much given my past expirence.
2762020-01-24T21:47:35  <real_or_random> gmaxwell: the thing is that also this holds only if people construct their ordinary UTXOs with a hash
2772020-01-24T21:47:49  <gmaxwell> thus "according to spec"
2782020-01-24T21:48:00  <real_or_random> I see
2792020-01-24T21:48:11  <sipa> at some point we removed the "you can use a pubkey directly as taproot output" from the bip for a related reason afaik
2802020-01-24T21:48:26  <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.
2812020-01-24T21:48:40  <bsm1175321> There's lots of hand-waving on #2 and at some point we might have to get serious about it.
2822020-01-24T21:49:11  <sipa> bsm1175321: the answer to #2 is: we have migrated to PQC signatures before #1 happens
2832020-01-24T21:49:58  <bsm1175321> Given the large size of PQC signatures, that would be very unpalatable to do prematurely. :-P
2842020-01-24T21:50:05  <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
2852020-01-24T21:50:22  <sipa> bsm1175321: exactly
2862020-01-24T21:50:54  <sipa> but even if sufficiently powerful QC ever becomes a reality, it seems very improbable that we won't see it coming
2872020-01-24T21:51:11  <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?
2882020-01-24T21:51:35  <sipa> i assume SHA256 remains secure
2892020-01-24T21:51:52  <bsm1175321> From my understanding, that's not a safe assumption...
2902020-01-24T21:52:02  <bsm1175321> And if it is, needs careful justification ;-)
2912020-01-24T21:52:04  <real_or_random> bsm1175321: do you have a better assumption?
2922020-01-24T21:52:24  <bsm1175321> Well I'd like to prove that a QC can break neither, and I think I can do it.
2932020-01-24T21:52:45  <sipa> bsm1175321: if you can find arbitrarily-structured SHA256 collisions, you can break *consensus*
2942020-01-24T21:53:15  <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
2952020-01-24T21:53:34  <bsm1175321> QC is magical thinking.
2962020-01-24T21:53:40  <sipa> real_or_random: agree
2972020-01-24T21:53:58  <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
2982020-01-24T21:54:03  <andytoshi> and maybe then randos would stop chiming in :P
2992020-01-24T21:54:18  <sipa> andytoshi: have you spent any time at all on the internet?
3002020-01-24T21:54:20  <andytoshi> similar to how we can usually make cryptographic decisions and nobody complains because nobody understands them
3012020-01-24T21:54:26  <andytoshi> sipa: hahah ok
3022020-01-24T21:54:32  <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.
3032020-01-24T21:54:45  <real_or_random> with >50% you can revert transactions and that's more realistic than a QC currently
3042020-01-24T21:54:53  <bsm1175321> And I'm not going to do that unless I find the time to convince myself one way or another.
3052020-01-24T21:55:03  <andytoshi> bsm1175321: oh, very cool, i hope to hear you speak about this at some point
3062020-01-24T21:55:11  <sipa> bsm1175321: if you can prove crypto-breaking QC is non-physical i suspect you can win a nobel prize :)
3072020-01-24T21:55:52  <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
3082020-01-24T21:55:55  <bsm1175321> sipa: No one wins Nobels for negative results. But an entire industry is dis-incentivized to write the proof.
3092020-01-24T21:56:10  <real_or_random> but then people talk about QC
3102020-01-24T21:56:17  <bsm1175321> But literally *every* physicist I've spoken to expresses that opinion informally
3112020-01-24T21:56:49  <sipa> bsm1175321: people also legitimately believed human flight was impossible at some point, with very well argued points
3122020-01-24T21:57:25  <sipa> the difference between "we currently don't see how it could ever happen" and "it can't happen" is enormous
3132020-01-24T21:57:45  <bsm1175321> sipa: this is pure math though. It comes down to a flaw in their arguments about error correction.
3142020-01-24T21:59:00  <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
3152020-01-24T22:00:14  <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
3162020-01-24T22:12:35  <sipa> ha
3172020-01-24T22:13:38  <bsm1175321> Well the good thing about physics is that you can get hard answers. You can't engineer physical reality away.
3182020-01-24T22:14:25  <bsm1175321> And tuning any physical state to a precision of 2^-256 is simply not physically possible.
3192020-01-24T22:14:54  <sipa> bsm1175321: do you believe that if we had perfect control over atom placement, you could not build a crypto-breaking QC?
3202020-01-24T22:15:15  <bsm1175321> If you did, you could. But you can't.
3212020-01-24T22:15:23  <bsm1175321> And that's the crux of the argument.
3222020-01-24T22:15:27  <sipa> sure, but you can't prove that we don't?
3232020-01-24T22:15:36  <sipa> as that is an engineering question
3242020-01-24T22:15:45  <bsm1175321> There's this annoying little thing called the uncertainty principle...
3252020-01-24T22:15:56  <bsm1175321> and it can't be engineered away
3262020-01-24T22:16:35  <sipa> just compensate by building it inside a car, and being really unsure about how fast it goes
3272020-01-24T22:16:39  * sipa hides
3282020-01-24T22:16:50  <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.
3292020-01-24T22:17:00  <bsm1175321> hahaaaa
3302020-01-24T22:18:16  <bsm1175321> high temperature systems collide with nearby atomic states, and decohere, destroying the quantum state. It's a Sisyphean challenge.
3312020-01-24T22:56:56  <andytoshi> bsm1175321: i'm unconvinced by this "precision of 2^-256 is impossible" argument, because it ignores how large/multidimensional the space is.
3322020-01-24T22:57:12  <andytoshi> certainly _classical_ computers can represent 256-bit numbers reliably without flipping
3332020-01-24T22:57:36  <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
3342020-01-24T22:58:00  <andytoshi> but in a high-dimensional space you can have 2^256 states and still have tons of space between them all
3352020-01-24T22:58:09  <andytoshi> i dunno. still reading (and sorry for the offtopicness)
3362020-01-24T23:22:19  <bsm1175321> andytoshi: I agree that argument is handwavy.
3372020-01-24T23:24:40  <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.
3382020-01-24T23:25: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.
3392020-01-24T23:25:39  <bsm1175321> So the argument comes down to how well the error correction argument holds up.
3402020-01-24T23:26:56  <bsm1175321> As the above article states, it only works "under certain assumptions" which I fear are unphysical.