12019-11-28T00:20:06  *** michaelfolkson has quit IRC
  22019-11-28T01:35:01  <sipa> no q&a?
  32019-11-28T01:35:06  <sipa> in half an hour?
  42019-11-28T01:52:51  <gmaxwell> sipa: you can ask me questions!
  52019-11-28T02:00:01  <moneyball> I’ve asked sipa before but I’ll ask again for clarity. Is it possible with taproot to use a trusted third party as an emergency backup key co-signer and retain privacy on your balance and spends as long as you don’t utilize their key? (Like a Casa 3of5 where they have one of the keys)
  62019-11-28T02:02:49  *** ZmnSCPxj_ has quit IRC
  72019-11-28T02:10:53  <gmaxwell> moneyball: the most straight forward way would be to put their key under a branch rather than at the top level.
  82019-11-28T02:11:59  <gmaxwell> moneyball: the normal way to make a schnorr threshold signature require interaction. The interaction doesn't actually break your privacy, but I assume for that application you also don't want the interaction.
  92019-11-28T02:12:23  <aj> gmaxwell: i think you'd want to pair it was an "OP_RETURN nonce" script, so that you'd never reveal the script hash even if you wanted to spend via some other script
 102019-11-28T02:12:30  <gmaxwell> (or at least the interaction doesn't necessarily break your privacy.)
 112019-11-28T02:13:00  <gmaxwell> aj: well normally what you do to hide a key is tweak it, which has no overhead.
 122019-11-28T02:13:37  <aj> gmaxwell: though you'd have to keep the merkle path to their script more redundantly than you kept your private keys
 132019-11-28T02:13:57  <gmaxwell> aj: well 3 of 5 right, so you put all the setup information with every copy of your keys.
 142019-11-28T02:14:11  <gmaxwell> (or a seed which is used to generate your setup info)
 152019-11-28T02:15:06  <aj> gmaxwell: yeah. if you tweak their key should be fine to be at the top level privacy-wise
 162019-11-28T02:15:43  <gmaxwell> aj: tweak works toplevel or in a branch, really there should never be a reason for a nonce in a branch that contains a pubkey.
 172019-11-28T02:16:22  <gmaxwell> instead you just compute some H(pubkey||chaincode||index)G+P and have that in the branch.
 182019-11-28T02:17:45  <gmaxwell> The top level has an additional storage complication though, since you have to do an interactive protocol and store the result.  E.g. casa couldn't just publish a pubkey which you can add as a backup without ever talking to them.
 192019-11-28T02:18:48  <aj> top level as in key path, do you mean?
 202019-11-28T02:19:21  <gmaxwell> FWIW, that kind of backup service could also be done so that it's private even when used.  Where you make a version of pubkey tweaked a commitment to your identity,  ... then if you want them to backup sign for you, you could prove your identity and ask them to blind sign, so they never see the txn they're signing for.
 212019-11-28T02:19:25  <gmaxwell> aj: yes.
 222019-11-28T02:19:44  <aj> ah, i was meaning top level as in when there was only one tapscript
 232019-11-28T02:20:29  <moneyball> gmaxwell: that’s interesting I didn’t realize that
 242019-11-28T02:21:19  *** rottensox_ has joined ##taproot-bip-review
 252019-11-28T02:22:29  <gmaxwell> Another way of doing the "never see the txn",  is that you ask them to generate a keypair for you, and give you the pubkey but you only use it in tweaked form so they can't see it being used.  Then later, if you need it in an emergency, you identify to them and then they give you the private key.
 262019-11-28T02:22:44  <gmaxwell> And that even works with ECDSA.
 272019-11-28T02:23:27  <gmaxwell> There was some 'blockchain oracle' service called reality keys that published pubkeys for events, and depending on the outcome published one or the other private keys... which worked with this sort of use.
 282019-11-28T02:23:52  <gmaxwell> The 'give away the private key' usage isn't compatible with public derrivation sadly.
 292019-11-28T02:24:14  *** rottensox has quit IRC
 302019-11-28T02:25:49  *** rottensox__ has joined ##taproot-bip-review
 312019-11-28T02:28:21  *** rottensox_ has quit IRC
 322019-11-28T02:30:23  *** ZmnSCPxj has joined ##taproot-bip-review
 332019-11-28T02:35:12  <gmaxwell> The right intution though is that _any_ key can be made private prior to its use by adding tweake*G to it, -- private to anyone that doesn't know that tweak value.  This is true for ECDSA just as well, e.g. BIP32 public derrivation is essentially that.
 342019-11-28T02:35:49  <gmaxwell> For schnorr you just also gain the ability to do thresholds, but it works the same there. Come up with some threshold key P,  and tweak it.
 352019-11-28T02:38:20  <gmaxwell> The 'interactive setup' for a threshold key is that each person generates an secret. Then each person N of M shares their secret using a verifyable secret sharing scheme. Everyone checks that the shares are all consistent.  Everyone adds up all the shares they recieved.   So the final result is each party learns an N of M share of the sum of everyone's secrets. Once you've done that, you can
 362019-11-28T02:38:20  <gmaxwell> go ahead and just tweak the result to keep it private from participants not knowing the tweak.
 372019-11-28T02:38:33  *** rottensox__ is now known as rottensox
 382019-11-28T02:39:19  <ZmnSCPxj> "_any_ key can be made private": just to be clear, this means "any published pubkey can be used to create an unpublished pubkey that the original published pubkey signer(s) can sign for"
 392019-11-28T02:40:02  <gmaxwell> And since the tweak is mathmathcically equivient to AND-ing knowledge of the secret in the policy. (so your N of M policy because ((N of M) AND TWEAK)) it should just drop right into the signing process-- by either just adding the tweak to one of the signers' keys or by adding a 'fake participant' that signs with the tweak key.
 402019-11-28T02:40:47  <gmaxwell> And the same also works w/ blind signing.
 412019-11-28T02:41:04  <ZmnSCPxj> Would adding just `e * tweak * G` to the summed final `s` be enough?
 422019-11-28T02:41:39  <gmaxwell> -tweak, I believe if you want to be pedantic.
 432019-11-28T02:41:44  <aj> ZmnSCPxj: you want to add "x" so they can't mention on the nonce they signed too
 442019-11-28T02:41:46  <ZmnSCPxj> ok
 452019-11-28T02:41:58  <aj> if you're doing blind sigs at least
 462019-11-28T02:42:02  <gmaxwell> If you're _blind_ signing you have to hide the nonce.
 472019-11-28T02:42:24  <gmaxwell> which means the signer can't see the input to e... and there are some additional security considerations.
 482019-11-28T02:43:44  <gmaxwell> [and anyone reading this log in the future should be aware that virtually all descriptions of blind signatures out there are insecure and ignore wagner's algorithim, but it's possible to securely do... which should be sufficient for discussing taproot functionality]
 492019-11-28T02:44:09  <gmaxwell> sipa: so you're not gonna ask me any questions? :(
 502019-11-28T02:44:24  <ZmnSCPxj> Hmmm why `-tweak`? bip-schnorr uses `k + ed`
 512019-11-28T02:45:15  <ZmnSCPxj> Or possibly based on whether it is square or not
 522019-11-28T02:46:25  <gmaxwell> ZmnSCPxj: ah right you are. (sorry thought without thinking much was "you added it to the key so you should subtract it in the signature" but here you want to be signing for the tweaked value, not having a tweaked signer sign for the original value :P)
 532019-11-28T02:47:08  <ZmnSCPxj> okay
 542019-11-28T02:47:28  <gmaxwell> in any case, I expect that a complete schnorr multisigning api will end up with some 'tweak input' which must be input as a scalar, and bypasses delinearization.  ... which you will need to sign with taprooted keys, and stuff like this.
 552019-11-28T02:47:40  <aj> gmaxwell: sipa just tricked you into asking him a question, i think that means he won
 562019-11-28T02:47:41  <gmaxwell> (I dunno what nickler's -zkp interface currently does)
 572019-11-28T02:48:16  <ZmnSCPxj> aj: Is that how high-level cryptographers play?
 582019-11-28T02:49:05  <gmaxwell> aj: it's a zero knoweldge protocol, we can't even tell if he's here or not.
 592019-11-28T02:50:26  <ZmnSCPxj> I believe I have seen elsewhere that blind Schnorr signing can be fixed somehow by requiring multiple blind signing attempts and then rejecting all except one that you randomly select, is that correct?
 602019-11-28T02:51:50  <gmaxwell> ZmnSCPxj: We don't have a security proof for that, but I believe that is secure.
 612019-11-28T02:52:54  <gmaxwell> Alternatively, you can only have exactly one signing session going at any one point in time, and begin a second only when the first finishes or times out.
 622019-11-28T04:29:21  *** shesek has quit IRC
 632019-11-28T04:29:46  *** shesek has joined ##taproot-bip-review
 642019-11-28T04:29:46  *** shesek has joined ##taproot-bip-review
 652019-11-28T05:08:49  <gmaxwell> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-November/017495.html  < wouldn't this require a lot more hashing?
 662019-11-28T05:10:30  <sipa> gmaxwell: you mean at signing time
 672019-11-28T05:10:33  <sipa> ?
 682019-11-28T05:11:54  <gmaxwell> at verification time
 692019-11-28T05:12:28  <sipa> i thought about responding that this woukd break scenarios where the signer acrually doesn't know the checksig execution time (bexause it may depend on which other signers are availavle)
 702019-11-28T05:12:47  <sipa> but i don't actually know any such scenario
 712019-11-28T05:12:53  <sipa> gmaxwell: no, 4 bytes
 722019-11-28T05:13:00  <sipa> per checksig
 732019-11-28T05:14:34  <gmaxwell> sipa: but it requires invoking the sha256 compression function for each checksig operation when otherwise they'd share them, no?
 742019-11-28T05:14:54  <gmaxwell> sipa: if there is a long checksig add sequence, you'll know which checksig you're signing for, but not which other ones will be used.
 752019-11-28T05:14:56  <sipa> gmaxwell: oh, yes, but only at the end
 762019-11-28T05:15:18  <sipa> so you could use midstate caching if you really wamted to
 772019-11-28T05:15:38  <gmaxwell> sure, but even if you do that it'll still be an extra compression function run per checksig.
 782019-11-28T05:16:29  <sipa> that seems a very marginal issue
 792019-11-28T05:16:42  <sipa> i'm more concerned about complicating implementation of  orrect signers
 802019-11-28T05:16:45  <sipa> *correct
 812019-11-28T05:18:36  <gmaxwell> The benefit of the change is unclear to me-- at least the example roconnor gives doesn't work AFAIK-- you already sign the script you're signing for, so you won't get substituted for a whole different script.
 822019-11-28T05:19:17  <gmaxwell> I mean, it essentially reitroduces a quadratic validation cost (though with a pretty small constant)
 832019-11-28T05:19:29  <sipa> no, it doesn't
 842019-11-28T05:19:40  <sipa> the cost per checksig is constant, with or without this change
 852019-11-28T05:20:02  <gmaxwell> okay, true _if_ you midstate cache.
 862019-11-28T05:20:19  <sipa> no, even if you do 't
 872019-11-28T05:20:47  <sipa> because all variable-length data fed to the sighash is precomputed per tx or per input
 882019-11-28T05:21:38  <sipa> midstate caching lets you reduce it from 200 ish bytes max to a few bytes (+ hashing of padding)
 892019-11-28T05:24:27  <sipa> if you know of an example where a signer in general wouldn't be able to predict the checksig position for a given signature he's producing, i'd very much like to hear it
 902019-11-28T05:24:57  <sipa> i'm also not convinced this change improves very much
 912019-11-28T05:25:02  <sipa> in practice
 922019-11-28T05:26:14  <gmaxwell> Some back of the envelope math suggests to me that this might asympotically slow validation by about 2%
 932019-11-28T05:26:49  <sipa> assuming you i.
 942019-11-28T05:27:06  <sipa> assuming you implement the caching of sighashes to begin with, you mean?
 952019-11-28T05:28:27  <gmaxwell> yes, and assuming batch validation is in use with ~infinite batch sizes... and assuming the transaction is all lots of checksigs in a single script. (ignoring the limits on scriptsize)
 962019-11-28T05:29:24  <gmaxwell> basically 2*sqrt+affine-add+2-fieldmul+sha2compression vs that plus one more sha2compression. (no sha-ni)
 972019-11-28T05:29:27  <sipa> it's only an average case performanxe reduction though, not a worst case one
 982019-11-28T05:29:51  <sipa> (as in the worst case you'd use codesep for every chechsig already?
 992019-11-28T05:30:17  <gmaxwell> ah. codesep... well thats why bluematt wants to get rid of codesep.
1002019-11-28T05:30:18  <gmaxwell> :)
1012019-11-28T05:30:36  <sipa> that's not really comparable
1022019-11-28T05:30:59  <sipa> the effect in legacy sighashes is much more significant
1032019-11-28T05:33:08  <gmaxwell> sipa: so my understanding of his concern is that you have a script leaf  where you have something like "if hash160 equalverify pubkey1 checksigverify else pubkey2 checksigverify endif",  and you're tricked into signing for the second clause when you think you're signing for the first.
1042019-11-28T05:33:42  <gmaxwell> as avoiding this rebinding would require doing stuff like making sure your pubkey only happens in the expected place and not someplace else.
1052019-11-28T05:36:47  <sipa> gmaxwell: it's primarily an issue if you reuse the same pubkey in multiple places in a script
1062019-11-28T05:37:56  <sipa> but (a) it's not even a full protection in that case (multiple code paths resulting in the same pubkey does not imply the checksig position will be different; ideally you'd sign all the if/then/else and other conditionals in the whole script
1072019-11-28T05:38:16  <gmaxwell> sipa: but the 'reuse' might be done by another user.
1082019-11-28T05:38:33  <gmaxwell> If you sign all the conditions that will absolutely break non-interactive checkmultisig like usage.
1092019-11-28T05:39:05  <sipa> yep.
1102019-11-28T05:39:09  <sipa> i agree with that
1112019-11-28T05:39:43  <sipa> i feel like this exact suggestions doesn't break much in practice,but also does 't protect aginst much in practice
1122019-11-28T05:39:54  <ZmnSCPxj> Would banning `OP_IF` and forcing every branch to use MAST work?
1132019-11-28T05:40:04  <gmaxwell> I think if you sign _which_ checksig you were executing (as in like it's byte position in the witness program) then thats sufficient for his concern.
1142019-11-28T05:40:15  <sipa> ZmnSCPxj: that woukd absolutely kill a whole bunch of interesting use cases
1152019-11-28T05:40:17  <gmaxwell> ZmnSCPxj: that would be tremendiously destructive.
1162019-11-28T05:40:24  <ZmnSCPxj> ok
1172019-11-28T05:41:31  <sipa> gmaxwell: that's exactly what he's suggesting
1182019-11-28T05:41:47  <sipa> (except it's opcode number, not byte position)
1192019-11-28T05:42:47  <gmaxwell> ZmnSCPxj: imagine your policy is like a 25 of 100... you can't build a MAST tree of that-- it would be about 2^80 hashing operations to do so.  Yet it's a fairly straight forward script otherwise, not even terribly expensive fees wise.
1202019-11-28T05:44:10  <gmaxwell> sipa: opcode number is maybe a little softfork hostile though, since it means the counting needs to be consistent in implementations with different rules.
1212019-11-28T05:44:26  <sipa> gmaxwell: i don't think that is hard
1222019-11-28T05:44:48  <gmaxwell> K.
1232019-11-28T05:44:55  <gmaxwell> (no strong opinion)
1242019-11-28T05:47:02  <gmaxwell> I guess there is no performance overhead (well depending on how much data is going into hashes) in the common case that there is only a single checksig in any case.
1252019-11-28T05:47:23  <gmaxwell> and no increase in the worst case, as you note.
1262019-11-28T05:47:25  <ZmnSCPxj> For 25 of 100, is not `OP_CHECKSIGADD` enough? There is still no need for `OP_IF`?
1272019-11-28T05:48:13  <gmaxwell> sipa: so, if the pubkey going into the checksig is decided by an earlier part of the script, you may not know your position.
1282019-11-28T05:48:55  <sipa> gmaxwell: yep, i see how that is the case in theory
1292019-11-28T05:48:56  <gmaxwell> ZmnSCPxj: if you want to be forced to have an extra 75 zero pushes for no good reason. :P
1302019-11-28T05:49:13  <gmaxwell> ZmnSCPxj: though replace my example with a bunch of hash preimages and your dodge goes away.
1312019-11-28T05:49:24  <sipa> gmaxwell: i wanted to bring that uo, but i can't actually come up with a useful script that needs this
1322019-11-28T05:49:41  <sipa> even the crazy 3-of-10000 wouldn't be affected
1332019-11-28T05:50:03  <gmaxwell> sipa: well if OP_CAT is reenabled then e.g. pubkey checked against a hashtree in the script is potentially such a case.
1342019-11-28T05:50:19  <sipa> gmaxwell: mmmmaybe
1352019-11-28T05:50:39  <gmaxwell> it could be controlled by a sighash flag...
1362019-11-28T05:50:46  <gmaxwell> :-/
1372019-11-28T05:52:47  <gmaxwell> so for example, a OP_CAT key tree that emerges a couple keys from the tree, and checks that they're distinct, then checksigs with them, -- like a way of doing the 4 of 10000 that doesn't include 10,000 pubkeys in the witness program.
1382019-11-28T05:53:12  <gmaxwell> you couldn't non-interactively sign for that, if the checksig positions are tagged (except via signing for each of the 4 possibilities)
1392019-11-28T05:57:50  <gmaxwell> (or change that to 4 of 65535 and then you even get a script that there is no other way to construct, yet is reasonably efficient to use, non-interactively signable, etc...)
1402019-11-28T05:58:47  <gmaxwell> If it somehow signed it's location in terms of which _branch_ rather than which checksig,  it wouldn't break that case anymore.
1412019-11-28T05:59:24  <gmaxwell> like the opcode location of the nearest enclosing if.
1422019-11-28T05:59:57  <gmaxwell> (so every 'if' acts like a codeseperator for this purpose)
1432019-11-28T06:00:30  <ZmnSCPxj> gmaxwell: "though replace my example with a bunch of hash preimages and your dodge goes away." `OP_SWAP OP_HASH160 <hash> OP_EQUAL OP_ADD`, which is equivalent to `OP_CHECKSIGADD` except for hashes?
1442019-11-28T06:01:37  <ZmnSCPxj> Or `OP_ADD` is not enabled yet?
1452019-11-28T06:03:58  <gmaxwell> that works, but consider-- you've removed IFs and now so any conditional operation people have to just accomplish using arithmetic thresholds..okay, but then roconnor's concern about your signing for the wrong checksig still applies.  The complaint I had about your original suggestion is that requiring all control flow to be precomputed in the hashtree is pratically limiting...
1462019-11-28T06:05:17  <gmaxwell> So: you can't replace "effectively conditional" logic in scripts with the tree because of exponential blowup in converting to disjunctive form.  And any workaround to preserve conditional behavior (e.g. by doing it with arithmetic) still has the 'you might sign the wrong place' issue.
1472019-11-28T06:06:42  <gmaxwell> sipa: an alternative that maybe people would hate is that checksig could reject any script that reuses a pubkey.
1482019-11-28T06:06:57  <gmaxwell> so leaving it on validation to catch those cases, instead of the signer.
1492019-11-28T06:06:57  <ZmnSCPxj> okay
1502019-11-28T06:12:38  *** achow101 has quit IRC
1512019-11-28T06:13:44  *** mryandao_ has quit IRC
1522019-11-28T06:14:02  *** achow101 has joined ##taproot-bip-review
1532019-11-28T06:14:03  *** mryandao has joined ##taproot-bip-review
1542019-11-28T07:38:11  *** belcher has joined ##taproot-bip-review
1552019-11-28T07:39:08  *** ZmnSCPxj has quit IRC
1562019-11-28T09:42:35  *** b10c has joined ##taproot-bip-review
1572019-11-28T10:01:00  *** jonatack_ has joined ##taproot-bip-review
1582019-11-28T10:05:02  *** jonatack has quit IRC
1592019-11-28T10:08:00  *** shesek has quit IRC
1602019-11-28T10:11:16  *** shesek has joined ##taproot-bip-review
1612019-11-28T10:35:17  *** rottensox_ has joined ##taproot-bip-review
1622019-11-28T10:36:51  *** rottensox__ has joined ##taproot-bip-review
1632019-11-28T10:37:58  *** rottensox has quit IRC
1642019-11-28T10:39:37  *** rottensox_ has quit IRC
1652019-11-28T10:41:00  *** rottensox__ is now known as rottensox
1662019-11-28T12:29:09  *** shesek has quit IRC
1672019-11-28T12:47:36  <nickler> ZmnSCPxj: it seems to turn out that fixing blind schnorr signing by randomly selecting challenges (which doesn't imply additional rounds just 128 times size blowup in 2 rounds) is plausible. https://eprint.iacr.org/2019/877 shows that in ROM+Algebraic group model blind schnorr signing is secure if one more discrete log and "modified ROS" is hard.
1682019-11-28T12:47:41  <nickler> modified ROS is the probabilistic version of the ROS problem that Wagner's algorithm solves in normal blind schnorr sigs. It's not clear if it's hard, but it certainly seems so.
1692019-11-28T13:11:09  *** b10c has quit IRC
1702019-11-28T13:11:52  *** b10c has joined ##taproot-bip-review
1712019-11-28T13:15:23  *** evoskuil[m] has quit IRC
1722019-11-28T13:15:34  *** b10c has quit IRC
1732019-11-28T14:40:24  *** evoskuil[m] has joined ##taproot-bip-review
1742019-11-28T15:47:47  *** davterra has quit IRC
1752019-11-28T15:50:32  *** davterra has joined ##taproot-bip-review
1762019-11-28T15:58:06  *** davterra has quit IRC
1772019-11-28T16:34:49  *** b10c has joined ##taproot-bip-review
1782019-11-28T16:38:43  *** b10c has quit IRC
1792019-11-28T16:38:54  *** b10c has joined ##taproot-bip-review
1802019-11-28T16:42:19  *** b10c has quit IRC
1812019-11-28T16:42:32  *** b10c has joined ##taproot-bip-review
1822019-11-28T17:11:37  *** dr-orlovsky has quit IRC
1832019-11-28T17:16:33  *** devrando1 has joined ##taproot-bip-review
1842019-11-28T17:50:29  *** devrando1 has quit IRC
1852019-11-28T18:29:02  *** b10c has quit IRC
1862019-11-28T18:29:15  *** b10c has joined ##taproot-bip-review
1872019-11-28T18:45:16  *** andrewtoth_ has quit IRC
1882019-11-28T18:56:53  *** andrewtoth_ has joined ##taproot-bip-review
1892019-11-28T19:10:46  *** andrewtoth_ has quit IRC
1902019-11-28T19:11:28  *** andrewtoth_ has joined ##taproot-bip-review
1912019-11-28T20:12:30  *** arik_ has joined ##taproot-bip-review
1922019-11-28T20:31:14  *** arik_ has quit IRC
1932019-11-28T20:49:38  *** arik_ has joined ##taproot-bip-review
1942019-11-28T20:57:16  *** arik_ has quit IRC
1952019-11-28T21:01:35  *** b10c has quit IRC
1962019-11-28T21:10:25  *** jonatack__ has joined ##taproot-bip-review
1972019-11-28T21:11:58  *** jonatack_ has quit IRC
1982019-11-28T21:24:36  *** jonatack__ has quit IRC
1992019-11-28T21:24:51  *** jonatack has joined ##taproot-bip-review
2002019-11-28T21:26:55  *** devrando1 has joined ##taproot-bip-review
2012019-11-28T21:27:31  *** jonatack has quit IRC
2022019-11-28T21:27:51  *** jonatack has joined ##taproot-bip-review
2032019-11-28T21:55:34  *** ghost43 has joined ##taproot-bip-review
2042019-11-28T22:01:16  *** jonatack_ has joined ##taproot-bip-review
2052019-11-28T22:04:34  *** jonatack has quit IRC
2062019-11-28T22:28:28  *** dr-orlovsky has joined ##taproot-bip-review
2072019-11-28T22:35:20  *** rottensox_ has joined ##taproot-bip-review
2082019-11-28T22:37:59  *** rottensox has quit IRC
2092019-11-28T23:16:49  *** andrewtoth_ has quit IRC
2102019-11-28T23:17:04  *** andrewtoth_ has joined ##taproot-bip-review
2112019-11-28T23:30:36  *** arik_ has joined ##taproot-bip-review
2122019-11-28T23:36:17  *** arik_ has quit IRC
2132019-11-28T23:55:22  *** arik_ has joined ##taproot-bip-review