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
cpow has quit []
tromp has joined #bitcoin-wizards
jeremyrubin has joined #bitcoin-wizards
tromp has quit [Ping timeout: 252 seconds]
jonatack has quit [Ping timeout: 250 seconds]
CryptoDavid has joined #bitcoin-wizards
fkinglag has joined #bitcoin-wizards
ddustin has quit [Remote host closed the connection]
ddustin has joined #bitcoin-wizards
ddustin has quit [Ping timeout: 250 seconds]
tromp has joined #bitcoin-wizards
Chris_Stewart_5 has joined #bitcoin-wizards
tromp_ has joined #bitcoin-wizards
AaronvanW has quit [Remote host closed the connection]
Iriez has quit [Remote host closed the connection]
ferringb has joined #bitcoin-wizards
pinheadmz has quit [Quit: pinheadmz]
<andytoshi>
i'm musing on whether there's an actual attack you could come up with, where you're creating a script with a counterparty, and you use your counterparty's keys in your own part of the policy to somehow create a spending condition they didn't expect to exist
<andytoshi>
the idea being, they sign for some branch, then you can copy their sig and cause a different branch to be taken
<andytoshi>
i don't think there is anything .. unless you consider "taking a different branch" to be an attack in itself, for auditability reasons or something
<andytoshi>
because if someone signs a tx, conceptually that means they ACK the tx, so it doesn't matter what weird shenanigans are used
<andytoshi>
maybe you can change the feerate out from under somebody, but this is a small part of a larger problem of worst-case fee estimation
kabaum has quit [Ping timeout: 250 seconds]
<Chris_Stewart_5>
well isn't the problem in that you can't commit to a scriptSig so if you have n possible branches you can never be certain which one will be taken?
<Chris_Stewart_5>
while i agree conceptually that is what a current tx is now -- an ACK -- it seems it would be better if we commit to a specific branch?
<Chris_Stewart_5>
maybe you aren't rotating your keys in multiple branches for some security reason?
davispuh has joined #bitcoin-wizards
pinheadmz has joined #bitcoin-wizards
setpill has quit [Quit: o/]
Chris_Stewart_5 has quit [Ping timeout: 246 seconds]
roconnor has joined #bitcoin-wizards
<roconnor>
andytoshi: The scenario is where you wish to sign a tx under the condition that some hash-preimage is revealed (in the witness data) or some other similar constraint.
TheoStorm has quit [Quit: Leaving]
<roconnor>
It isn't even a necessarily a matter of rotating your public keys. Your public keys are public and anyone can use them in a protocol as if they were their own.
moo13 has joined #bitcoin-wizards
moo13 has left #bitcoin-wizards [#bitcoin-wizards]
Chris_Stewart_5 has joined #bitcoin-wizards
nirved has joined #bitcoin-wizards
tromp has quit [Remote host closed the connection]
ferringb has quit []
henrikbjorn has joined #bitcoin-wizards
pinheadmz has quit [Quit: pinheadmz]
ddustin has joined #bitcoin-wizards
tromp has joined #bitcoin-wizards
tromp has quit [Ping timeout: 276 seconds]
tromp has joined #bitcoin-wizards
tromp has quit [Remote host closed the connection]
<andytoshi>
roconnor: can you construct a specific attack?
<andytoshi>
like, suppose i want to sign but only if a preimage is revealed
<andytoshi>
and then somebody copies my signature over to a different branch without that preimage
<andytoshi>
what did i think that other branch was doing??
<andytoshi>
if i put my pubkey over there then i was obviously asking for trouble; if a counterparty put my pubkey there, oh well, it sounds like i thought that branch was controlled by the counterparty
<andytoshi>
which would also have been a vulnerability
<andytoshi>
like, i'm confused as to what plausible belief i could've had about this script, such that i was willing to participate in the protocol and then subsequently got burned by it
Zenton has quit [Ping timeout: 268 seconds]
<roconnor>
You might be right about this. I was only thinking along the lines of if I have a script and I want to prove that my signature ensure that a hash preimage is revealed, I need to do a whole program anaysis to conclude this rather than a local anaysis.
pinheadmz has joined #bitcoin-wizards
shush has joined #bitcoin-wizards
<roconnor>
But maybe if someone copies my pubkey, all they are doing is hampering their ability to sign under their conditions.
<andytoshi>
i think the difference there is that the coinjoin example violates the "one signature one utxo" invariant of bitcoin
<roconnor>
what invariant is that?
<andytoshi>
in bitcoin today, if you sign a transaction, this signature can only be used to spend at most one utxo
<andytoshi>
so you can e.g. make blind signatures if you know that all the UTXOs you control have the same value, and you are willing to transfer that much value
<andytoshi>
or alternately you can participate in a coinjoin without checking other inputs, provided you are sure to sign only the inputs you intended
<roconnor>
yes but a signature after a hash preimage reveal funciton isn't saying "you are willing to transfer that much value." It has more intension than that.
<andytoshi>
right. so in this case what you want to say is "i will not allow these coins to be spent unless the hash preimage is revealed". and so what you need to check is that (a) you are necessary, i.e. your key appears in all branches; (b) all branches containing your key have a hashlock condition
<andytoshi>
at least, at time 0
<andytoshi>
ah, i suppose you might instead check "(b') some branch containing your key has a hashlock condition"
tromp has joined #bitcoin-wizards
pinheadmz has quit [Quit: pinheadmz]
<roconnor>
Right given (a) you become responsible for ensuring you aren't subsitituting your own key. I'm willing to accept that (even though it is a little bit of a foot gun); for this argument I'm only worried about checking other people haven't reused your keys (a la https://bitcoin.stackexchange.com/a/85665).
<roconnor>
And if there is a branch that you don't control, it doesn't matter that your key gets reused there because you have not control over it...
<roconnor>
well those other branches you don't control could have their own requirements attached.
<andytoshi>
sure, but you don't control them
<andytoshi>
oh, i see... maybe you sign, expecting some condition to be met
<roconnor>
This seems like a problem that I should be either able to convince myself it is never a problem or come up with a concrete (if even contrived) example of the issue.
<andytoshi>
then unexpectedly a -different- condition is met instead
<andytoshi>
and maybe you're in some complicated protocol where this matters to you
<sipa>
but signatures sign the script being executed
shush has quit []
<sipa>
and if someone puts your key in a branch unbeknownst to you without the hashlock, you'd know this at signing time
<sipa>
and refuse to sign
<sipa>
oh, by branch you mean conditional branch inside a script, rather than merkle branch?
<andytoshi>
yeah .. but i don't think it matters
<roconnor>
yes this is all within a single Script.
<andytoshi>
so, suppose you have a script like or( and(your_pk, hashlock1), and(other_pk, hashlock2) )
<andytoshi>
so absent your cooperation, hashlock2 needs to be met
<roconnor>
the tapleaf branches themselves are already signed, so there is no issue there.
<sipa>
roconnor: right, i see; single script ok
<sipa>
this is already an issue today
<andytoshi>
out of band, somebody convinces you that hashlock2 is no longer valuable to you, but hashlock1 *is*
ddustin has quit [Remote host closed the connection]
<andytoshi>
so you say, sigh, fine, i'll sign, so you have to release hashlock1
<roconnor>
yes it is an issue today. It is a much worse problem in legacy script.
<roconnor>
only tempered by the fact that legacy script is so inexpressive.
<andytoshi>
oh, no, ignore me
ddustin has joined #bitcoin-wizards
<roconnor>
(I mean, assuming my issue is actually a real problem)
<andytoshi>
i already would refuse to participate in this example because and(other_pk, hashlock2) is always (in my view) available for the counterparty to take
<andytoshi>
so by signing, i'm changing the spend condition from "hashlock2 necessary" to "hashlock2 not necessary". but i can't assume anything about hashlock1.
ddustin has quit [Ping timeout: 245 seconds]
<roconnor>
andytoshi: I'm not sure that is the right way to look at it. The issue is that when you sign any policy your signature doesn't endorse any particular branch of that policy.
<roconnor>
But usually your intention is to endorse a particular branch (aka clause) of that policy.
<roconnor>
usually gaps like this between what you sign and what your intention is is enough to cause a security issue. I'm a bit frusterated that I cannot quite construct a coherent example of a security issue.
<sipa>
my biggest reason for not wanting to make checksig-position always signed is that there may be cases where this dramatically increases signing complexity, because there are many potential sets of signers and you don't actually care which ones sign off, but the different branches have a single key verified by a different checksig operator
<sipa>
however, i also can't actually construct an example of this
<roconnor>
It would probably be best to have a sighash flag to disable signing of the position.
<sipa>
on the other hand: the only reason in taproot to even have multiple branches in a script is probably because the alternative is intractable (combinatorial explosion of branches)
<roconnor>
That and I agree that signing the enclosing OP_IF/OP_NOTIF/OP_ELSE position is better.
<sipa>
roconnor: but then you might think (i know, far hypothetical) that every kind of branching is covered and you don't need to worry about this class of attack at all anymore
<sipa>
and you're bitten by a branch that determines the key the verify against, but only has a checksig
<roconnor>
That's a one of those anti-seatbelt-law type arguments. :)
<roconnor>
I mean you aren't wrong.
<sipa>
yeah, i know
<sipa>
i think my only argument is that if we had a solution that categorically solved all these classes of problems, it would be much easier to argue for
<sipa>
that doesn't mean seatbelts are a bad idea
<roconnor>
I mean we do. we can sign the trace of the computation. ^_^
<roconnor>
But that actually seems likely to be problematic.
<sipa>
or sign the set of all hashlocks/timelocks that are enforced by the branch... if only those were explicit
* sipa
proposes OP_MINISCRIPT
<roconnor>
we could redesign script to be declaritive.
<roconnor>
right
<roconnor>
just replace script with miniscript.
<gmaxwell>
roconnor: in the taproot channel I had suggested that it sign the enclosing IF, -- moving in the computation trace direction. But as pieter mentioned it's really important to preserve 0 interaction signing, esp since tapscript is the solution for multisig when you need zero interaction so you can't use a schnorr threshold.
<sipa>
gmaxwell: yeah i agree, but i can't come up with a useful example where either signing op_checksig position or enclosing op_if position would actually increase signing interaction
<sipa>
even the 3-of-10000 multisig script we came up with a while ago isn't affected
justan0theruser has quit [Ping timeout: 276 seconds]
jonatack has quit [Ping timeout: 268 seconds]
<sipa>
(as the position where a signature with any given key is verified doesn't change depending on the set of signers)
<gmaxwell>
sipa: signing the whole transcript certantly would.
<sipa>
oh yes, that's not going to happen :)
<gmaxwell>
I had another idea... associate a monotone-incrementing counter with every push onto the stack... and include the counter of the relevant pubkey in the signature.
<gmaxwell>
since roconnor's attack is more of a "you think you're signing for this one key, but you're really signing for this copy over there" you can think of this as some kind of pubkey malleability.
<sipa>
gmaxwell: i thought about that too, but that only affects scripts where the same pubkey is pushed twice... something that you'd generally try to avoid for cost reasons anyway
<sipa>
ah i see
<gmaxwell>
Other than maybe being easy to implement it leaves open leaving which checksig is used malleable so long as you're sure to only push the pubkey once.
<gmaxwell>
sipa: as far as what it breaks... imagine a policy where your key is common subexpression that occurs more than once.
<sipa>
gmaxwell: define it
<sipa>
(we've been talking about 4 different ideas here)
<gmaxwell>
signing the checksig or if position.
<gmaxwell>
Like an ((A or B) and C) or (A and D)
<sipa>
right, but you'd very much try to rewrite that in a way such that a is only pushed/checked once
<sipa>
though for sufficiently complex things that may indeed not be possible
<gmaxwell>
(it takes a little twiddling to get one that isn't remappable to a simple threshold)
<gmaxwell>
well miniscript for example can't eliminate common subexpressions, ever.
<sipa>
in this example you'd expand it out to tree leaves, of course
<gmaxwell>
Tree expanding doesn't help when A doesn't know who else is signing.
<gmaxwell>
since we sign which branch we're using. (I mean ignoring when it's small enough that its reasonable to concurrently sign a bunch of branches)
<sipa>
?
<sipa>
since we sign the merkle leaf we're executing, there shouldn't be a problem
<gmaxwell>
The problem in that case is that knowing which one we're executing is interaction. I'm assuming A had no idea who the other signers will be when they sign.
<sipa>
oh i see, yes of course tree expanding means either more interaction or doing multiple signing attempts in parallel... which may become infeasible
<gmaxwell>
now for that concrete example, sure you could make it branches and just simultaniously sign every branch including A, but that doesn't work if there would be many.
<sipa>
yes, that was my point: this example is sufficiently simple that expanding wouldn't be a big issue
<sipa>
but with more complex examples i can imagine that is not an option
<gmaxwell>
yes, though because you can't always expand and parallel sign there is less reason for software to support doing it.
justan0theruser has joined #bitcoin-wizards
<sipa>
for nontrivial cases, branches inside a script may be annoying for other reasons
<sipa>
like having a witness size that depends on the branch taken, and thus needing to know which one will be taken in order to do fee estimation for the transaction
<gmaxwell>
I dunno, even in those cases the size differences are usually not the large, so you can estimate the size rounding up and potentially end up overpaying a bit.
<sipa>
agreed
<gmaxwell>
thus is the price of non-interaction.
<gmaxwell>
Though it's interesting to note that "parallel sign all possibilities" also lets you adjust the fees.
<andytoshi>
semi-relatedly -- given that you have to sign the tapbranch, if i'm doing a noninteractive 2-of-3 with three branches, as a signer, do i need to produce 3 signatures to sign noninteractively?
<sipa>
andytoshi: yep
<andytoshi>
and is the plan simply to bite the bullet, regarding the scaling of this
<gmaxwell>
Yes.
<andytoshi>
ok, just checking
slivera has joined #bitcoin-wizards
<gmaxwell>
for 2 of 3 thats totally reasonable, and probably just as efficient as anything else you might do (like an interactive byzantine robust threshold signature)
<sipa>
it is one of the reasons why tree expansion isn't always desirable
justan0theruser has quit [Ping timeout: 265 seconds]
justan0theruser has joined #bitcoin-wizards
Jackielove4u has joined #bitcoin-wizards
pinheadmz has joined #bitcoin-wizards
henrikbjorn has quit []
TheoStorm has joined #bitcoin-wizards
ddustin has joined #bitcoin-wizards
Kiminuo has quit [Ping timeout: 268 seconds]
ddustin has quit [Remote host closed the connection]
Zenton has joined #bitcoin-wizards
Guyver2 has quit [Quit: Going offline, see ya! (www.adiirc.com)]
davterra has joined #bitcoin-wizards
jonatack has joined #bitcoin-wizards
Iriez has joined #bitcoin-wizards
pinheadmz has quit [Read error: Connection reset by peer]
pinheadmz has joined #bitcoin-wizards
kermit1 has joined #bitcoin-wizards
mdunnio has quit [Remote host closed the connection]
koshii has quit [Quit: bye]
davterra has quit [Ping timeout: 250 seconds]
davterra has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 240 seconds]