--- Day changed Tue Jul 28 2020
00:55 -!- jonatack [~jon@2a01:e0a:53c:a200:bb54:3be5:c3d0:9ce5] has quit [Ping timeout: 246 seconds]     
03:56 -!- sipa [~pw@gateway/tor-sasl/sipa1024] has quit [Ping timeout: 240 seconds]     
04:03 -!- sipa [~pw@gateway/tor-sasl/sipa1024] has joined ##miniscript     
04:33 -!- jeremyrubin [~jr@2601:645:c200:f539:45c6:b423:5c6a:9d2f] has quit [Ping timeout: 260 seconds]     
06:10 -!- shesek [~shesek@unaffiliated/shesek] has quit [Remote host closed the connection]     
06:11 -!- shesek [~shesek@164.90.217.137] has joined ##miniscript     
06:11 -!- shesek [~shesek@164.90.217.137] has quit [Changing host]     
06:11 -!- shesek [~shesek@unaffiliated/shesek] has joined ##miniscript     
07:02 < shesek> I released Minsc, a compile-to-Miniscript scripting language with some additional features and syntactic sugar, including variables, functions, infix notation, and more. Documentation and a live compiler are available on https://min.sc/, source code is at https://github.com/shesek/minsc
07:02 < shesek> on twitter: https://twitter.com/shesek/status/1288111748432576512
07:28 -!- jonatack [~jon@37.172.150.191] has joined ##miniscript     
08:05 -!- Davterra [~Davterra@104.200.129.213] has joined ##miniscript     
08:07 -!- Davterra [~Davterra@104.200.129.213] has left ##miniscript []     
08:11 -!- jonatack [~jon@37.172.150.191] has quit [Read error: Connection reset by peer]     
08:35 < sipa> h     
08:47 -!- jonatack [~jon@2a01:e0a:53c:a200:bb54:3be5:c3d0:9ce5] has joined ##miniscript     
09:38 -!- jb55 [~jb55@gateway/tor-sasl/jb55] has quit [Remote host closed the connection]     
09:55 -!- jeremyrubin [~jr@2601:645:c200:f539:149c:f818:6125:256e] has joined ##miniscript     
09:55 -!- jb55 [~jb55@gateway/tor-sasl/jb55] has joined ##miniscript     
10:07 < shesek> would it make sense to tweak repeated pubkeys by the positions of the OR branches they appear in to avoid malleability? so something like (pseudocode in minsc notation) `(pk(A) && pk(B)) || (pk(A) && older(6))` => `(pk(tweak(A, [0])) && pk(B)) || (pk(tweak(A, [1])) && older(6))`
10:10 < shesek> I guess it doesn't really have to care specifically about the OR position, could use a simple incrementing counter as the tweak derivation index for each pk appearance
10:11 < sipa> or add support for codeseparators
10:12 < sipa> or enable better common subexpression elimination
10:12 < sipa> or wait for taproot
10:23 < sipa> without support for a standardized way of doing key tweaking in psbt, it's hard to practically support this
10:25 < jeremyrubin> you could theoretically enforce that the signatures are at least distinct?
10:25 < jeremyrubin> would mess with deterministic nonces i guess
10:27 < sipa> i doubt that's any easier than just supporting common subexpression elimination
10:27 < sipa> both interfere with the composability of scripts
10:32 < shesek> reading some of the previous discussions, I was under the impression that you didn't consider common subexpression elimination as something that you would want to pursue. if that's a practical option then it does seem better, more elegant and cost efficient
10:33 < sipa> no, my point is mostly that they're all impractical :)
10:36 < shesek> couldn't tweaking be done in psbt using the existing bip 32 derivation support? I thought that it should be possible to do this with existing psbt-compatible signer impls without requiring any special changes
10:37 < jeremyrubin> shesek: no way to tell the key in a BIP32 one
10:38 < sipa> shesek: errrr i wasn't asssuming that you could just change the keys
10:39 < sipa> applications can have derivation path requirements for change/input detection, or be unable to do derivation except for provided keys
10:39 < sipa> i think it would be bad for compilation-to-descriptor to do anything but just straight pass through the keys
10:41 < gwillen> shesek: I had made a proposal for CSE in a private conversation awhile ago that I'm happy to describe here but it's pretty messy (it involves the altstack, and if it works it still involves a number of ops that's linear in the number of other common subexpressions you have to 'reach past' to get the one you want)
10:42 < gwillen> (not directly on topic but since you asked about it ;-) )
10:43 < sipa> hmm     
10:43 < gwillen> I would not call it especially practical, but I think for small numbers of large common subexpressions it does give significant size reduction
10:43 < gwillen> (but I'm not aware of specific use cases where this matters a lot)
10:44 < sipa> thinking about this back... "no reuse of keys" is probably too strong
10:53 < sipa> or(and(pk(A),pk(B)),and(pk(A),pk(C))) isn't malleable (but it's silly for other reasons for course)
10:54 < sipa> or(and(pk(A),pk(B)),and(pk(A),after(T))) however is malleable
10:54 < sipa> (if A&B sign the left branch, and then T passes, a 3rd party can construct a spend for the right branch)
10:55 < sipa> i wonder what the exact criterion is
10:55 < sanket1729> It's a corner case right? The signer should always prefer to sign with right branch. Unless, this happens exactly around time ~T
10:56 < sipa> actually, i'm being silly
10:56 < sipa> this isn't true
10:56 < sipa> because A's signature signs the locktime/sequence value of the spending transaction
10:56 < sipa> so a 3rd party can't transmute things
10:57 < sipa> either the tx's locktime is in the past, and the right branch would have been signed
11:04 < sipa> i'm now wondering in what cases reused keys actually do result in malleability
11:04 < sipa> i'm not convinced anymore there are any...
11:04 < sipa> oh, i guess when there is a spendability condition that's an exact subset of another
11:06 < sipa> i suspect that's hard to detect in general, except by enumerating them all (which may be intractible)
11:07 < sipa> *intractable
11:08 < sipa> and interestingly, if that's the case, then CSE doesn't solve anything even
11:44 < shesek> fyi, because miniscript policies are also valid minsc expressions, the web editor ui could potentially be useful for writing bare policies too
11:45 < shesek> you'll get syntax highlighting, parentheses matching, real-time compilation (in a web worker so the browser doesn't freeze) and better error reporting
11:45 < shesek> (or any error reporting, really :p)
11:47 < sanket1729> sipa: I think or(and(pk(A),pk(B)),(and(pk(A),sha256(H))) would be malleable after seeing a satisfaction to the left branch. 
11:58 < sipa> hmm, if the preimage is known, then picking the left branch would be an overcomplete choice
11:58 < sipa> but you're right, our current reasoning can't tell that it is
12:01 < jeremyrubin> I think notably reuse isn't really the only issue here right? and(pk(A), or(pk(B), sha256(H)) would also suffer from similar issues no?
12:03 < sipa> no     
12:04 < sipa> if the preimage is available there, the right branch has to be taken
12:04 < jeremyrubin> hm?     
12:04 < sipa> "If instead exactly one does not have the HASSIG marker, return that solution because of reason 2."
12:04 < sipa> from the non-malleable signing algorithm explained on http://bitcoin.sipa.be/miniscript/
12:05 < sipa> if there is a choice between two branches, and one includes signatures and the other does not, the non-signature one has to be taken
12:05 < jeremyrubin> hmm     
12:05 < jeremyrubin> that seems confusing?
12:05 < sipa> why?
12:06 < sipa> it's perfectly well defined i think
12:06 < jeremyrubin> Because then why do you need key B there at all if it can't be used?
12:06 < sipa> it can be used, if the preimage of H is not available
12:07 < jeremyrubin> so if H is not available, then you sign with B, and then H becomes available?
12:07 < jeremyrubin> maybe I'm missing something
12:08 < sipa> the attacker is assumed to only see one satisfying witness
12:09 < sipa> and not have access to hash preimages that honest users don't hav
12:09 < jeremyrubin> this is a concrete problem in cross chain swaps tho
12:10 < sipa> yes, there are inherent limits to what can be made nonmalleable
12:11 < jeremyrubin> fair. 
12:12 < sipa>  Because of these reasons, Miniscript is actually designed to permit non-malleable signing. As this guarantee is restricted in non-obvious ways, let's first state the assumptions:
12:12 < sipa>     The attacker does not have access to any of the private keys of public keys that participate in the Script. Participants with private keys inherently have the ability to produce different satisfactions by creating multiple signatures. While it is also interesting to study the impact rogue participants can have, we treat it as a distinct problem.
12:12 < sipa>     The attacker only has access to hash preimages that honest users have access to as well. This is a reasonable assumption because hash preimages are revealed once globally, and then available to everyone. On the other hand, making the assumption that attackers may have access to more preimages than honest users makes a large portion of scripts impossible to satisfy in a non-malleable way.
12:12 < sipa>     The attacker gets to see exactly one satisfying witness of any transaction. If he sees multiple, it becomes possible for the attacker to mix and match different satisfactions. This is very hard to reason about.
12:13 < sipa>     We restrict this analysis to scripts where no public key is repeated. If signatures constructed for one part of the script can be bound to other checks in the same script, a variant of the mixing from the previous point becomes available that is equally hard to reason about. Furthermore this situation can be avoided by using separate keys.
12:13 < jeremyrubin> right
12:28 < sanket1729> andytoshi, sipa: I want to implement policy entailment in rust-miniscript. I recollect that andytoshi mentioned some algorithm that could do better than brute forced one
12:28 < sanket1729> something basis
12:29 < sipa> grobner basis?
12:36 < sanket1729> yeah, yeah
12:37 < sanket1729> From the description, there is no obvious translation to the policy entailment. 
12:38 < sipa> we need roconnor here
12:39 -!- roconnor [~roconnor@host-184-164-2-204.dyn.295.ca] has joined ##miniscript     
12:42 < sipa> 12:28:11 < sanket1729> andytoshi, sipa: I want to implement policy entailment in rust-miniscript. I recollect that andytoshi mentioned some algorithm that could do better than brute forced one
12:42 < sipa> 12:28:17 < sanket1729> something basis
12:42 < sipa> 12:29:32 < sipa> grobner basis?
12:42 < sipa> 12:36:54 < sanket1729> yeah, yeah
12:42 < sipa> 12:37:58 < sanket1729> From the description, there is no obvious translation to the policy entailment.
12:42 < sipa> 12:38:50 < sipa> we need roconnor here
12:42 < roconnor> i am here
12:43 < sanket1729> Welcome. I am reading https://en.wikipedia.org/wiki/Gr%C3%B6bner_basis and I can't directly translate the problem to policy logic entailment. 
12:43 < sanket1729> I will try and understand the complete algorithm and than maybe it will be clearer
12:43 < sipa> i'm not sure that groebner basis as the right tool
12:46 < sanket1729> For starters, I considering the following: Let C be the list of all leaf satisfactions. C consists of all timelocks, hashlocks and pks in policy. 
12:47 < sipa> i don't think you need to know the algorithm for finding groebner bases in order to reason about why they may be useful
12:49 < sanket1729> eq(A,B): eq(A1,B1) and eq(A2,B2) where A1 is in A with first element in C set to true, A2 is A with first element set to false. 
12:49 < sanket1729> As roconnor correctly pointed out, entailment is same of equality. 
12:49 < sipa> if A entails B, and B entails A, they are equal
12:50 < sanket1729> I mean deciding entailment is same as deciding equality. 
12:50 < sanket1729> A entails B. We set all leaf constraints in B that not present in A to false. 
12:50 < sanket1729> And then check for A == b
12:55 < sanket1729> I think I jumbled implication and entailment
13:03 < sanket1729> entailment means all possible set of satisfactions for both polices should be same?
13:13 < roconnor> entailment is a form of implication.
13:13 < roconnor> A |- B means every sasifaction of A also satifies B.
13:17 < roconnor> (the word implication is usually reserved for a policy.  The policy "A imples B" is the weakest policy C such that C AND A |- B.
13:18 < sipa> (A => B) is defined as (B or not(A)) right?
13:18 < sipa> at least in boolean logic
13:18 < roconnor> right, but polices are not a boolean algebra because there is no negation.
13:19 < sipa> right
13:19 < roconnor> So if we wanted the "implication" policy we'd have to look at Heyting Algebras.
13:19 < roconnor> I'm not certain we satify the requirement for that though.
13:20 < roconnor> if you did have negation that (B OR NOT A) would be the weakest policy C such that C AND A |- B.
13:21 < sipa> right
14:15 < elichai2> Might be of interest to some people here https://twitter.com/shesek/status/1288111748432576512?s=19
14:16 < elichai2> Ops, I see that shesek is already here and posted, sorryyy
15:01 < andytoshi> sanket1729: oops just getting this
15:01 < andytoshi> i do not recommend trying to use grobner bases
15:02 < sanket1729> let me write down what I am thinking of doing
15:03 < andytoshi> kk. meanwhile let me try to find the paper i used to translate policies into polynomial equations..
15:03 < sanket1729> https://gist.github.com/sanket1729/d86b84b58ef4240c7760c353d79b8b04
15:04 < andytoshi> reading. meanwhile i forwarded you (to your blockstream email) some correspondence between me and some grobner basis researcher doing similar stuff
15:05 < andytoshi> but i reiterate that grobner bases took a *long* time to implement and turned out to be a dead end, i think, so i discourage you from pursuing this :)
15:06 < andytoshi> sanket1729: i don't understand what you posted
15:07 < sanket1729> It is recursive formulation that essentially works by setting one of witness to true/false and recursing it. 
15:07 < andytoshi> with grobner bases, what you do is translate one policy into a basis for an polynomial ideal ... specifically the ideal generated by all polynomials that vanish on the set of valid spending conditions
15:08 < andytoshi> (here you have many variables, each one representing e.g. the presence/absense of a particular signature)
15:08 < andytoshi> then you translate the other policy into a giant polynomial (hopefully not expanding it all the way out!) and try to determine whether this polynomial is in the ideal
15:08 < andytoshi> if it is, then the first policy entails the second one
15:09 < andytoshi> grobner basis algorithms give you a way to answer this "is a given polynomial in an ideal?" question
15:09 < andytoshi> sanket1729: ah! so like, "entail(false,B) = true" means that false implies everything
15:09 < andytoshi> ok     
15:10 < andytoshi> so line 3, "entail(false,false)=true" is redundant
15:10 < andytoshi> and line 4 is wrong in the specific case that _ is false :)
15:10 -!- roconnor [~roconnor@host-184-164-2-204.dyn.295.ca] has quit [Ping timeout: 240 seconds]     
15:11 < andytoshi> but yes, lines 6/7/8 look good and (usually) this should be way faster than grobner basis techniques
15:29 -!- roconnor [~roconnor@host-45-58-209-205.dyn.295.ca] has joined ##miniscript     
17:57 -!- Netsplit *.net <-> *.split quits: Aleru, RubenSomsen, midnight
18:01 -!- RubenSomsen [sid301948@gateway/web/irccloud.com/x-gasdhhiyorhasrtn] has joined ##miniscript     
18:01 -!- Aleru [sid403553@gateway/web/irccloud.com/x-bzlawewlmjbhxtqv] has joined ##miniscript     
18:01 -!- midnight [~midnight@unaffiliated/midnightmagic] has joined ##miniscript     
18:59 -!- midnight [~midnight@unaffiliated/midnightmagic] has quit [Ping timeout: 244 seconds]     
19:01 -!- midnight [~midnight@unaffiliated/midnightmagic] has joined ##miniscript     
19:15 < sanket1729> I think roconnor describes the multi-party constraints pretty well. In general, there are two kinds of constraints that must be satisfied. 
19:15 < sanket1729> 1) Authorization constraints: The constraints under which the parties must be able to spend the funds
19:16 < sanket1729> 2) Control constraints: If the funds are spent by anyone, the control constraints must be satisfied. 
19:34 < sanket1729> Authorization constraints must entail the policy and the policy must entail the control constraints for every party.
23:19 < sanket1729> andytoshi, can you look at #70. Having iterators would be helpful for me to implement policy entailment. 
23:52 -!- midnight [~midnight@unaffiliated/midnightmagic] has quit [Ping timeout: 272 seconds]