--- Log opened Tue Sep 24 00:00:09 2013
07:29 < warren> I'm not sure how to respond to https://github.com/bitcoin/bitcoin/pull/3008
07:32 < warren> truthful response? "I think you're backwards in reasoning on every part of your explanation. Your existing spam solution is terrible and entirely insufficient, and dropping the 0.01 size limit will make spam worse.  And the part about a zero fee 26KB tx... is impossible."
07:34 < warren> also "This 10KB -> 1KB change will mean how many extra wasted bytes in the permanent blockchain for dust combiners?  Previously they could combine 67 inputs in one output.   This kind of user DOES care about fees and is willing to wait many blocks for their 10KB tx to sneak in."
10:27 < petertodd> warren: the 0.01 thing makes it not much more expensive to put data in the UTXO set, think about it
10:27 < petertodd> warren: also, do the math for how many extra wasted bytes that actually is, it's not much...
10:53 < gmaxwell> warren: I don't think the 0.01 thing matters pretty much at all, after looking at the txn.
10:54 < gmaxwell> people will pay their 0.0001 BTC fee, and then make a minimum size output. No one is going to make a 0.01 output to avoid the fee and then use it on an unspendable output, as that would cost more.
10:55 < gmaxwell> 0.01 = >$1 now, ... the new anti-dust rules are more compariable to the original 0.01 intent.
11:53 < adam3us> is there a proposed method to work around mutability of ECDSA signatures for the purposes of making dependent transactions (that depend on one or more of the outputs of a previous transaction)?
11:54 < adam3us> eg broadcast the dependent transaction twice once with each mutation txid=H(msg,r,s) and txid'=H(msg,r,-s)?
11:55 < adam3us> and can you on an output with zero value?
11:57 < gmaxwell> adam3us: There are more mutabilities than that one sadly.
11:58 < gmaxwell> We're slowly fixing them. E.g. bitcoin(d/-qt) git will now only produce the smaller possible S value. We'll also no longer relay varrious forms of garbage DER encoding that openssl still accepted.
12:42 < adam3us> that may be a slightly fragile approach - if they re notionally all fixed, and people start relying on that for big transactions/high value contracts, and just one more DER openssl bug is found boom
12:43 < adam3us> what about as a one fix instead saying validation must be done (any sigs valid etc) but the txid = H( msg, pub-key ) instead of H( msg, sig )
12:43 < gmaxwell> adam3us: our proposal to fix it is to rigidly parsing so openssl is irrelevant.
12:43 < adam3us> as msg includes locktime, sequence, and inputs
12:44 < adam3us> ok
12:44 < gmaxwell> adam3us: getting the sig out of the txid could help but that would be a very deep hardforking change, .. and it's actually tricky to make secure. E.g. what happens when you first get one with a bad signature?
12:44 < adam3us> reducing use of openssl to bare crypto is probably for the best, its defect rate is not fantastic
12:46 < adam3us> i guess my robustness comment is you then have a new security assumption - that there is no signature or encoding mutuability remaining
12:46 < adam3us> (well that assumption is already there except the mutability bugs are deterring reliance on such scripts for now)
12:46 < gmaxwell> adam3us: right, we're still a long way from that in any case.. right now we're just slowly moving towards it.
12:47 < gmaxwell> but I agree that before you can take it for granted you really need to do a lot of final review.
12:48 < midnightmagic> jgarzik: Can you tell your employer that it would be really helpful if a user could request more than one payment address for a single transaction? :-)
12:49 < midnightmagic> :-(
12:51 < adam3us> cant say i like that direction very much - dsa itself is devoid enough of security proofs, and how do we prove the signature is immutable (once the encoding and known mutations are addressed) - it a novel security assumption that the mathematical crypto guys have not spent the last decade+ thinking about unlike basic dsa or schnorr
12:53 < gmaxwell> adam3us: it's just software engineering. How do you know your buffers don't overflow. :)
12:54 < gmaxwell> oh you mean just inside DSA. point.
12:54 < adam3us> yes dsa mathematical assurance
12:54 < adam3us> i do buy your rigid non openssl based deterministic encode/decode argument
12:54 < gmaxwell> It's worse because if you give me a discrete log solving oracle I know I can give you infinite signatures.
12:55 < gmaxwell> but I don't know that I can reduce it to that being sufficient, almost certantly not since DSA itself has no such reduction.
12:55 < adam3us> i am for example thinking of a DSA attack i made on a server compute offload system for DSA by markus jakobsson
12:56 < adam3us> it was surprisingly malleable
12:56 < adam3us> despite the unknown k^-1 values
12:56 < adam3us> (slightly different situation, but...)
12:57 < gmaxwell> There are other signing algorithims which I except would be easiy to prove where unique. E.g. I think a pairing short signature only has one signature just on information theoretic grounds... no such joy for DSA.
12:58 < adam3us> do you mean weil pairing based? zss? i wouldnt touch it with a barge pole ;)
12:59 < adam3us> weil pairing is too new, people are finding special curves to be avoided, fresh news now and then so i am scared of the parameter choices, people maybe making bad ones that'll get mathemtically broken presently
12:59 < adam3us> but yes non-malleability would be nice
13:00 < adam3us> i think schnorr is otherwise a rather nice signature scheme as its more flexible for eg k of n threshold, brands style boolean formulae, limited show even
13:01 < adam3us> limited show is very nice - you can force the signer to make one signature only ever on a given document (on pain of disclosing his private key via simultaneous equation)
13:02 < adam3us> of course disclosing private keys is less critical than usual in bitcoin as you only have to get there first, subsequent signatures are ignored
13:02 < gmaxwell> and because your private key has low value or at least can have low value.
13:03 < gmaxwell> since our privacy requires that you can have more for free. :)
13:03 < adam3us> eg re weil paring dangers, http://ellipticnews.wordpress.com/2013/05/22/joux-kills-pairings-in-characteristic-2/
13:03 < gmaxwell> adam3us: Yea, well, I wasn't recommending it, but just saying... :)  It's not so bad with curves though, I mean, most of the stuff being broken is the low embedding degree stuff that was known to be not a great idea.
13:03 < adam3us> he pretty much destroyed some parameters that people actually proposed not that long ago
13:04 < gmaxwell> adam3us: yea, but you can find publications eons ago about characteristic 2 being weak... ::shrugs::
13:05 < adam3us> the danger is this isnt the end of the story we dont know how far new mathemtical attacks go towards currently considered secure parameters
13:05 < adam3us> anyway kind of a tangent :)
13:05 < adam3us> what are the known mathematical mutabilities? is r,-s it?
13:05 < gmaxwell> Sure. though, as you noted— DSA is not provable secure in the standard model. :)
13:06 < gmaxwell> adam3us: r,-s is the only mathmatical one I know of.
13:06 < adam3us> yes and in that sense the best we can do is use old conservative assumptions that are secure in the sense only that no one broke them yet
13:07 < gmaxwell> My confidence in that class of assumption goes down every day. :)
13:07 < gmaxwell> (there are a lot of weaknesses we've fixed in bitcoin that could easily have been exploited— even profitably in some cases— but just no one did!)
13:08 < adam3us> maybe the interest would go up if we had zerocoin levels of privacy
13:08 < gmaxwell> e.g. I don't think anyone has used the r,-s malleability yet, they've used DER encoding ones.. confusingly one is where you code s as a _negative number_ e.g. not the same as -s mod order but just a sign bit that openssl ignores.
13:09 < gmaxwell> adam3us: I think that part of it is that if the attacks are sophicated, the people smart enough to pull them off can find better things to do with their time that they can still brag about. :P but who knows.
13:12 < adam3us> i think mostly that is true, though there are a few grey hats i've come across with the "if its broken it deserves to be exploited" mentality, that they seem to deeply internalize and see no moral problems with
13:14 < gmaxwell> Yea, but even those can find more interesting things to do, I think? Dunno I'm waving my arms, I can only say that I've observed a lot of stuff not getting exploited.
13:15 < gmaxwell> E.g. there is a lot of people using unconfirmed txn that would be jammed up by someone just making mutants in order to jam things up.. and no one seems to be doing that _generally_, only against satoshi dice, and I dunno if thats happening anymore.
13:19 < adam3us> maybe the bets are too smal
13:19 < adam3us> ok i think i have a mathematical argument for you;)
13:20 < adam3us> if (r,s) is a signature, then so is (2r,2^-1s) because that is (r',s') = dsa with k replaced with k'=2k which you can do even though you dont know k
13:21 < adam3us> and you can replace 2 with any invertible number in the range of n
13:21 < adam3us> so there are probably 2n or thereabout possible mutations
13:21 < sipa> with n = ?
13:22 < adam3us> order of curve
13:22 < sipa> ouch
13:22 < gmaxwell> I was trying to think about that before and thought there was some issue with it because Xr may not even be on the curve.
13:22 < adam3us> i think it works because (r,s)=([-kG]x,k^-1(H(m)+rd)
13:23 < adam3us> sorry that should be (r,s)=([kG]x,k^-1(H(m)+rd)
13:23 < sipa> gmaxwell: even if now, justbelow 2^255 values are
13:23 < sipa> so the odds of hittinga valid r are almost 50%
13:24 < gmaxwell> easy enough to try.
13:24 < adam3us> so  (r',s')=([kG+kG]x,2^-1*k^-1(H(m+rd)
13:24 < sipa> this sounds like malleability is unsolvable?
13:24 < adam3us> eek not quite.. internal r
13:24 < adam3us> retract
13:25 < gmaxwell> yea, I don't think this is true.
13:25 < adam3us> (let me try some more tinkering)
13:25 < gmaxwell> If its true we just broke DSA
13:26 < gmaxwell> because we would have created a way of recovering K that looks like a collision search on a K multiple sequence, like how you solve the discrete log.
13:26 < adam3us> well not necessarily because you can only create a new signature of a known value (except that you cant so far othe than (r,-s)
13:27 < adam3us> i'm not sure about that... some of the other DL algorithms are reblindable or whatever you call it
13:27 < adam3us> eg elgamal
13:27 < adam3us> thats a related encryption algorithm version of near infinite mutuability
13:37 < gmaxwell> I don't think this works because the order is prime. But I'm in a meeting right now and haven't been able to just try it.
13:45 < adam3us> I think the EC version of elgamal will still be publicly reblindable
13:49 < adam3us> another interesting question would be if you have (r,s) and (r',s') two different signatures with different k values but on the same H(m) can you create a third signature (r",s")   (ignoring the (r,-s) approach)
13:51 < gmaxwell> well I don't mind create two different signatures the signers could always create infinite more.
13:51 < gmaxwell> "Don't sign the same message multiple times" is simple enough, esp if people switch to derandomized dsa. (As I think all should)
13:53 < sipa> i don't see how you could compute s"
13:53 < sipa> unless the two k values are related
13:59 < adam3us> what's your email address sipa?  i'll send you an unpublished attack relating to a server offload version of DSA which shows mathematically how manipulable this is
13:59 < gmaxwell> sipa: the idea there is to blindly swap K values on a signature.
14:00 < adam3us> note i said two real signatures (diff k values) on the same H(m)... thats going to be more manipulable
14:01 < sipa> adam3us: pieter.wuille@gmail.com
14:01 < sipa> gmaxwell: hmm, i'll have to think longer about it
14:02 < gmaxwell> I'm not saying it works, but I see vaguely how it might. I'd want to just try it.
14:03 < warren> petertodd: I'm in favor of getting rid of free tx's entirely.
14:06 < adam3us> sent mail
14:07 < adam3us> who's going to bitcoin in amsterday thurs-sat?
14:08 < sipa> i'm not, this time
14:09 < adam3us> the lesson from that server aided DSA attack is knowing any relation at all about k values is usually fatal
14:09 < MoALTz> warren: one suggestion i've said in passing before is to have a new field in the block header: minimum accepted fee; the block is only valid if all the tx contained with-in have at least that fee. on it's own that doesn't seem helpful, but consider the effect: if you want to know how long a tx will take to get onto the blockchain you look back over an arbitary number of blocks and see how many it would have made it int
14:09 < MoALTz> o (%age-wise)
14:10 < MoALTz> avoids hardcoded values too
14:11 < gmaxwell> MoALTz: people pay fees to miners in many different ways, not just tx fees.
14:11 < gmaxwell> e.g. today people will pay fees via child transactions that have high fees, or via special txouts paying a specific miner, or via external agreements.
14:12 < gmaxwell> MoALTz: so in your model miners would keep signaling 0 but then actually imposing higher fees.
14:13 < MoALTz> hmm. suggests some other contraint is needed as well
14:15 < MoALTz> for the "in-kind" payments i could see refunding the tx fee being done (coinbase). but yeah, it still needs more incentive for miners be give correct values for the mintxfee
14:18 < gmaxwell> MoALTz: refunding doesn't work becuase it may not be the in-kind miners block who ultimately has the transaction
14:18 < gmaxwell> (consider reorgs)
14:48 < adam3us> gmaxwell: "well I don't mind create two different signatures the signers could always create infinite more." well its a little different - if the users client created two signatures, maybe he has it in his state, but if a third party can then create a third signature algebraicly from the two signature that would be yet one more thing to watch out for, eg what if your computer crashes part way, and he signature is recalculated but the message
14:49 < adam3us> not that i so far see a way to do even that somewhat contrived mutability
14:52 < gmaxwell> adam3us: It's true— but thats just yet another argument to use drandomized DSA.
14:52 < adam3us> absolutely :)
15:01 < gmaxwell> (2r,2^-1s) doesn't appear to work.
15:03 < gmaxwell> (obviously that doesn't mean that no such issue exists, but at least the simplest possible attempt didn't work)
15:05 < gmaxwell> e.g. in sage, http://0bin.net/paste/tGoT890fHgUhmhxT#YvA84LJPZQBrCNSP3msD0NM1m2lK2iFE5PyzDWMyzv0=
15:06 < adam3us> no that was broken there is an r in the s calculation s=k^-1(H(m)+rd)
15:06 < adam3us> so can correct k, but not r so far
15:08 < amiller> apparently there will be a dedicated Bitcoin workshop at the Financial Cryptography conference next year
15:08 < amiller> they'll accept papers by november 24
15:09 < amiller> nicolas cristin is the leader of it
15:09 < amiller> that's pretty cool, it's about time, and also that's a good venue
16:37 < adam3us> re manipulation of r,s other than r,-s this way of expressing the sig verification process looks more plausibly malleable than the s definition (r,s)r=([kG]x, k^-1(H(m)+rd) might suggest
16:38 < adam3us> k=s^-1*r*Q - s^-1*H(m)*G
16:39 < adam3us> sorry kG = s^-1*r*Q - s^-1*H(m)*G
16:40 < adam3us> or r = s^-1(r*Q - h(m)*G)
16:40 < sipa> .x
16:41 < adam3us> r.x yes
16:41 < sipa> well, no, but i see what you mean :)
16:41 < sipa> r = ... .x
16:41 < adam3us> ok;)
16:45 < adam3us> which can also be written rs = rQ-H(m)G
17:13 < gmaxwell> r = s^-1(r*Q - h(m)*G) < with r on both sides of the equation this makes it sort of hard to changes S to solve for r
17:20 < sipa> r = (r/s*Q - h*G).x
17:21 < sipa> R = R.x/s*Q - h*G
17:22 < sipa> oh
17:22 < sipa> R = (R.x*Q - h*G)/s
17:41 < gmaxwell> (you lost me on the Q, unless its the order, but I don't follow that)
17:47 < sipa> Q is the public key
17:48 < sipa> the tricky thing is that R is both used as an EC point, and its x coordinate as a scalar
17:52 < adam3us> i think its easier to work with (non EC) DSA notation but alternatively one can work with the point
17:52 < adam3us> eg i am thinking about hostile R values such that [R]x = H(m)
17:54 < adam3us> you dont need to know k' such that k'G = R with that property just choose R = (H(m),f(H(m))) for example
17:55 < adam3us> then the hard part try to solve for s
--- Log closed Tue Sep 24 19:47:20 2013
--- Log opened Tue Sep 24 19:47:38 2013
23:17 < petertodd> warren: same, although child-pays-for-parent would be good to implement first, that is implement the relaying changes so that groups of transactions are relayed at once
23:18 < warren> petertodd: that sounds helpful
23:18 < warren> petertodd: would there be any arbitrary limit of how deep the unconfirmed chain can be?
23:19 < petertodd> gmaxwell: *effectively* getting the sig out of the txid is a very easy change: just make signatures be on the scriptPubKey's or even scriptPubKey:value's your spending rather than txid:n
23:21 < petertodd> warren: doesn't have to be beyond the limit of "how much data I'm willing to accept from a peer in one go"
23:21 < petertodd> warren: 32MiB is that limit in some places
23:26 < gmaxwell> petertodd: no, that leaves you with all the really @#$#@ non-uniqueness problems.
23:26 < gmaxwell> "Am I spending this output or that?"
23:27 < petertodd> gmaxwell: if you don't re-use addresses there's no issue... and if you do, that's your own fault (and including value mitigates that somewhat)
23:28 < petertodd> gmaxwell: soft-forking change too, because it can be done as a new signature type
23:28 < petertodd> gmaxwell: you'd still want to keep txid's, but they're only a hint really (and for backwards compatibility)
23:39 < petertodd> gmaxwell: oh, brainfart, scriptPubKey:value is the only way to do it because of fees, so yeah, do that and you're set. from the transaction's point of view, who cares what exact txid was used to satisfy the input?
23:40 < gmaxwell> petertodd: ...
23:40 < petertodd> gmaxwell: obviously creating two scriptPubKey:value's is unwise in this scheme, but don't do that...
23:40 < gmaxwell> You don't control that.
23:40 < petertodd> gmaxwell: don't control what?
23:40 < gmaxwell> Other people paying you.
23:40 < gmaxwell> This basically reintroduces the duplicate txid problem.
23:41 < petertodd> gmaxwell: sure you do: new system is that when you give someone an address, you actually give them a way to generate scriptPubKey's on your behalf, be it ECC or something as dumb as a nonce
23:42 < gmaxwell> petertodd: but then they pay you twice from non-strongly seralized systems.
23:42 < petertodd> gmaxwell: heck, failing that, do scriptPubKey:value:block:tx#...
23:42 < gmaxwell> can't spend unconfirmed outputs, which then defeats the whole issue with worrying about the malleability, nothing is malleable once confirmed.
23:43 < petertodd> gmaxwell: fair enough
23:44 < petertodd> gmaxwell: then just make it possible to leave out the txid in the signature hash calculation, usually it'll be there, but for special applications hash something else to be sure malleability doesn't bite you
--- Log closed Wed Sep 25 00:00:12 2013