1 2011-11-15 00:00:57 <roconnor> intersting, you can have multipel OP_ELSE's in one OP_IF statement.
  2 2011-11-15 00:01:34 <cjdelisle> which gets eval'd? first, last or all?
  3 2011-11-15 00:02:16 <luke-jr> or it could be more interesting
  4 2011-11-15 00:02:28 <luke-jr> iff true, it could be every odd block
  5 2011-11-15 00:02:32 <luke-jr> and iff false, every even block
  6 2011-11-15 00:02:40 <roconnor> luke-jr is right
  7 2011-11-15 00:02:45 <luke-jr> ie, the 2nd else could negate the 1st
  8 2011-11-15 00:03:23 <luke-jr> that could be actually useful behaviour, potentially& maybe
  9 2011-11-15 00:03:33 <luke-jr> can you do an ELSE after the ENDIF?
 10 2011-11-15 00:03:46 <roconnor> luke-jr: Not really
 11 2011-11-15 00:03:52 <luke-jr> IF <A-code> ELSE <B-code> ENDIF <common> ELSE <A-code> ELSE <B-code> ENDIF
 12 2011-11-15 00:03:54 <luke-jr> aww
 13 2011-11-15 00:04:15 <Mqrius> avast antivirus detects a threat in cgminer... is this normal behaviour?
 14 2011-11-15 00:04:15 <roconnor> maybe I should break down and make a wiki account
 15 2011-11-15 00:07:57 <roconnor> actually the wiki is wrong about OP_IF ... if the top stack value is NOT 0, the statements are exectued ...
 16 2011-11-15 00:09:02 <roconnor> acutally mistaking true for 1 is problematic throughout the article
 17 2011-11-15 00:09:45 <gavinandresen> roconnor: nice catch.  Did you fix it already?
 18 2011-11-15 00:09:59 <roconnor> nope; I don't have a wiki account
 19 2011-11-15 00:10:11 <gavinandresen> I'll pay for it.
 20 2011-11-15 00:10:17 <gavinandresen> ... just send me the bill.
 21 2011-11-15 00:13:37 <phantomcircuit> gavinandresen, http://instantrimshot.com/
 22 2011-11-15 00:14:14 <roconnor> WTF
 23 2011-11-15 00:14:26 <roconnor> it says it as no loops or nesting ''if'' statements
 24 2011-11-15 00:14:32 <roconnor> ... but it does have nesting if statements
 25 2011-11-15 00:16:25 <roconnor> I'm pretty sure it has nesting if statements
 26 2011-11-15 00:16:45 <roconnor> otherwise my life would be simpler :)
 27 2011-11-15 00:18:48 <gavinandresen> yes, it definitely has nesting ifs
 28 2011-11-15 00:19:38 <etotheipi_> this is why I haven't tried implementing OP_IF in my scripting engine yet... just not worth the effort atm
 29 2011-11-15 00:20:49 <roconnor> block 00000000009c304ccfb10c84f26bea6b3b245c146c16bb8d22a9e3848ee866a0 in testnet has an OP_IF :(
 30 2011-11-15 00:21:02 <etotheipi_> what??? I don't remember that
 31 2011-11-15 00:21:16 <roconnor> :O
 32 2011-11-15 00:21:34 <etotheipi_> oh yeah
 33 2011-11-15 00:21:37 <etotheipi_> there are 3 such scripts
 34 2011-11-15 00:22:51 <roconnor> luke-jr: alternating OP_ELSE's could have been more useful if IF statements could span across siganture-pubkey script boundaries.
 35 2011-11-15 00:23:11 <roconnor> alas that cannot happen
 36 2011-11-15 00:24:47 <gavinandresen> Why is OP_IF such a pain for you to implement?  It's less than 20 lines of SatoshiCode...
 37 2011-11-15 00:25:25 <etotheipi_> gavinandresen, I can write a neural-network back propagation routine in 20 lines of code (I've done it)
 38 2011-11-15 00:26:13 <gavinandresen> Of all the things you have to implement to get an alternative bitcoin implementation right, the scripting seems like something that is reasonably straightforward.
 39 2011-11-15 00:26:26 <etotheipi_> I do agree with that, besides OP_CHECKSIG
 40 2011-11-15 00:26:34 <roconnor> I'm pretty sure neural-network back propagation is easier than OP_IF :D
 41 2011-11-15 00:26:42 <gavinandresen> Yes, besides CHECKSIG...
 42 2011-11-15 00:26:55 <etotheipi_> OP_IF may be simpler than I originally thought... I was just confused looking at the satoshi code
 43 2011-11-15 00:27:05 <etotheipi_> maybe I should've spent more than 5 minutes trying to decode it
 44 2011-11-15 00:27:20 <roconnor> gavinandresen: the fact that the alternate stack is cleared between script calls and if statements cannot span script calls caught me off guard
 45 2011-11-15 00:28:10 <roconnor> there are about 1000 implicit design decisions in Satoshi's script code that you have to get exactly right
 46 2011-11-15 00:28:19 <gavinandresen> I asked Satoshi why allow anything besides "Push data" in the scriptSig, but never got an answer out of him.
 47 2011-11-15 00:28:36 <roconnor> Hostestly reimplementing Bitcoin is probably 10x or 100x harder than implementing bitcoin.
 48 2011-11-15 00:28:39 <gavinandresen> ... if it were up to me....
 49 2011-11-15 00:28:45 <etotheipi_> this makes me very happy I'm not aiming for full scripting/blockchain verification
 50 2011-11-15 00:28:54 <roconnor> because when implementing bitcoin the arbitrary choices can be made arbitrarily
 51 2011-11-15 00:29:17 <roconnor> but when reimplementing bitcoin the arbitrary choices must be made exactly the same way
 52 2011-11-15 00:29:43 <gavinandresen> roconnor: I dunno, Satoshi said he worked on it for a couple of years before the first release.  He had to think through a ton of details
 53 2011-11-15 00:30:15 <gavinandresen> roconnor: ... so 10x harder would mean it'll take you 20 years to re-implement
 54 2011-11-15 00:30:22 <roconnor> so you cannot choose to disallow improperly formed DER encoded ECDSA signatures (to give an example that Satoshi gave exactly 0 thought to).
 55 2011-11-15 00:30:56 <sipa> satoshi was no crypto expert - he seems to have used off-the-shelf encodings and routines
 56 2011-11-15 00:31:07 <gavinandresen> roconnor: it is what it is.  It would have been astonishing if he'd managed to get everything 100% right the first time.
 57 2011-11-15 00:31:25 <roconnor> gavinandresen: Intersting question: how long will it take for my code to be fully compatible with bitcoin?  probably never.
 58 2011-11-15 00:31:30 <roconnor> well, I worry about it at least
 59 2011-11-15 00:31:45 <sipa> roconnor: are you that far off?
 60 2011-11-15 00:31:52 <etotheipi_> but I totally understand about reimplementing:  that's basically my real job:  intermediary between big gov't contractor ... and the contractor:  we have to implement their code/design and tell the gov't whether it works
 61 2011-11-15 00:32:00 <theorbtwo> roconnor: If I understand your objection correctly, then you could always disallow such signatures in the future, or on a rolling basis.
 62 2011-11-15 00:32:14 <Eliel> gavinandresen: it took years to design bitcoin, but the time spent implementing the design can't be that big :P
 63 2011-11-15 00:32:16 <gavinandresen> I don't want you to stop worrying, I worry too... (which is why I plan on getting back to the cross-implementation testing project when I can)
 64 2011-11-15 00:32:17 <etotheipi_> (*** between contractor and gov't)  my life is reimplementing other peoples' designs
 65 2011-11-15 00:32:56 <etotheipi_> fortunately, the result is not as "picky" about details as the Bitcoin protocol is
 66 2011-11-15 00:33:03 <gavinandresen> etotheipi_: there's plenty of design left to "build out" bitcoin infrastructure
 67 2011-11-15 00:33:04 <roconnor> sipa: It is really hard to tell; I'm constantly surprised by the things I get wrong
 68 2011-11-15 00:33:12 <roconnor> sipa: like this DER encoding issue.
 69 2011-11-15 00:33:23 <sipa> true; it's the details that bite
 70 2011-11-15 00:33:35 <roconnor> and there are sooo many of them.
 71 2011-11-15 00:33:44 <etotheipi_> gavinandresen, I agree with you, except there's quite a bit of initial hurdle to get over
 72 2011-11-15 00:33:53 <gavinandresen> ... like berkeley db not deleting data when you ask it to....
 73 2011-11-15 00:34:07 <roconnor> gavinandresen: :D
 74 2011-11-15 00:34:12 <etotheipi_> 4 months later and I'm still trying to get the base for a light client working
 75 2011-11-15 00:34:35 <etotheipi_> I can tell you what I'm *not* using to store ECDSA keys :)
 76 2011-11-15 00:35:15 <roconnor> It's quite pleasing that, TD, etotheipi_ and I are really working in reimplementing different aspects of bitcoin
 77 2011-11-15 00:35:38 <roconnor> I think
 78 2011-11-15 00:35:58 <sipa> however, none of them will ever be combined
 79 2011-11-15 00:36:10 <sipa> as they are in 3 different languages
 80 2011-11-15 00:36:18 <roconnor> :D
 81 2011-11-15 00:36:21 <etotheipi_> what is TD doing it in?
 82 2011-11-15 00:36:26 <roconnor> etotheipi_: Java
 83 2011-11-15 00:36:34 <sipa> Java, he's the author of BitcoinJ
 84 2011-11-15 00:36:44 <etotheipi_> ahh
 85 2011-11-15 00:36:44 <sipa> and genjix's libbitcoin in C++ is a fourth
 86 2011-11-15 00:36:55 <roconnor> BitcoinJ doesn't implement scripting
 87 2011-11-15 00:36:56 <etotheipi_> well to be fair... I have a a fairly expansive C++ code base
 88 2011-11-15 00:36:58 <cocktopus> HASKELL 4 EVAR
 89 2011-11-15 00:37:15 <roconnor> which is fine; it isn't designed to
 90 2011-11-15 00:37:23 <roconnor> I don't have any wallet anything
 91 2011-11-15 00:37:49 <etotheipi_> I don't think there's any other way to do the bulk processing of the blockchain in python
 92 2011-11-15 00:37:57 <etotheipi_> or maybe I'm just not very good at python
 93 2011-11-15 00:38:00 <etotheipi_> :)
 94 2011-11-15 00:38:46 <sipa> it was a discussion on #haskell-blah, almost a year ago, that brought me here :)
 95 2011-11-15 00:39:52 <roconnor> sipa: copumpkin is a bitcoiner
 96 2011-11-15 00:40:08 <copumpkin> probably wasn't me
 97 2011-11-15 00:40:19 <copumpkin> I only started bitcoining in juneish
 98 2011-11-15 00:40:36 <sipa> i believe EvanR was here as well back then
 99 2011-11-15 00:41:41 <cjdelisle> 20:40 < sipa> satoshi was no crypto expert - he seems to have used off-the-shelf encodings and routines <-- using well reviewed well understood routines is the mark of a professional
100 2011-11-15 00:42:11 <sipa> cjdelisle: absolutely
101 2011-11-15 00:42:32 <roconnor> cjdelisle: and that is why we don't have key recovery :(
102 2011-11-15 00:42:46 <sipa> but he wouldn't have chosen DER encoding for signatures, which is 72 bytes instead of 64
103 2011-11-15 00:43:21 <sipa> and we wouldn't been using 279-byte serialized private keys, when 32 bytes suffice
104 2011-11-15 00:43:29 <sipa> and indeed, key recovery
105 2011-11-15 00:43:31 <cjdelisle> indeed, that does sound like a quickly made decision
106 2011-11-15 00:43:32 <roconnor> sipa: apparently we can start droping leading 0x00's now
107 2011-11-15 00:43:58 <roconnor> save a byte or two on signatures :)
108 2011-11-15 00:44:00 <sipa> roconnor: great; 72-1/255 bytes
109 2011-11-15 00:45:29 <roconnor> cjdelisle: as of yet, OP_CHECKMULTISIG ... makes no sense to me.  Then again neither does CODESEPARATOR.
110 2011-11-15 00:45:46 <sipa> nobody understands CODESEPARATOR, it seems
111 2011-11-15 00:46:07 <cjdelisle> is it used in the chain?
112 2011-11-15 00:46:08 <sipa> it seems i joined #bitcoin-discussion on november 17th, 2010
113 2011-11-15 00:46:15 <roconnor> oh wait, I just understood OP_CHECKMULTISIG
114 2011-11-15 00:46:17 <sipa> can't believe it's been a year
115 2011-11-15 00:46:30 <cjdelisle> happy birthday
116 2011-11-15 00:46:34 <sipa> not yet
117 2011-11-15 00:46:46 <cjdelisle> ahh well you can open your present anyway
118 2011-11-15 00:47:49 <cjdelisle> If you're interested in light clients, I have written a proposal which hashes out gmaxwell's "unspent transaction tree" plan http://btc.pastebay.com/144544
119 2011-11-15 00:47:56 <luke-jr> I joined #bitcoin-dev on Jan 1, 2011
120 2011-11-15 00:47:57 <luke-jr> :p
121 2011-11-15 00:49:13 <gavinandresen> CODESEPARATOR I can't figure out, either.  CHECKMULTISIG isn't hard-- just <m sigs> m <n pubkeys> n OP_CHECKMULTISIG, the signatures must be in the same order as the public keys, there have to be exactly m of them.  And there's a bug, so you have to put something extra on the stack before everything if you want it to work...
122 2011-11-15 00:49:55 <gavinandresen> ... oh, and all m of the signatures must validate.
123 2011-11-15 00:50:07 <roconnor> gavinandresen: ya, I just figured out CHECKMULTISIG.  :D
124 2011-11-15 00:50:25 <roconnor> the "must be in the same order" was missing in my head
125 2011-11-15 00:50:30 <sipa> ow, it seems it was december 17, not november; excuse me!
126 2011-11-15 00:50:40 <gavinandresen> let me know if you figure out what CODESEPARATOR is good for.  (I know how it works... but can't see how it could be useful)
127 2011-11-15 00:51:50 <cjdelisle> can't call satoshi on the secret phone and ask "what the hell was that for?"?
128 2011-11-15 00:52:01 <sipa> nobody will answer
129 2011-11-15 00:52:52 <gavinandresen> secret phone seems to have a permanent busy signal
130 2011-11-15 00:52:56 <cjdelisle> I had always assumed he was aroundish, kind of guiding development from a distance, able to warn about dangerous ideas erc..
131 2011-11-15 00:53:21 <roconnor> cjdelisle: If he was he'd be warning about OP_EVAL :D
132 2011-11-15 00:53:47 <sipa> he disappeared somewhere in march?
133 2011-11-15 00:53:56 <cjdelisle> Yea, I kind of have second thoughts about op_eval given how stupifyingly complicated the scripting system really is.
134 2011-11-15 00:54:28 <gavinandresen> ... that's like having an objection to #include because C++ is complicated...
135 2011-11-15 00:54:48 <sipa> OP_EVAL does have some very nice use cases
136 2011-11-15 00:55:11 <cjdelisle> The only thing is this is running untrusted code so any kind of a buffer overflow or a crashbug -> ruin
137 2011-11-15 00:55:35 <sipa> we're already running untrusted code
138 2011-11-15 00:55:40 <gavinandresen> yup
139 2011-11-15 00:55:55 <gavinandresen> if OP_EVAL will crash you, then you will probably crash without it, too
140 2011-11-15 00:56:10 <cjdelisle> yup, that's why adding anything to the programming language is scary...
141 2011-11-15 00:56:39 <cjdelisle> but then as a hanger on, I am in no position to bitch about it.
142 2011-11-15 00:56:57 <iddo> 279 bytes for private keys is the format of wallet.dat? why not change it to 32 bytes if it's private data that doesn't affect the protocol?
143 2011-11-15 00:56:59 <gavinandresen> removing stuff or leaving it exactly the way it is... is scary, too....
144 2011-11-15 00:57:20 <sipa> iddo: in encrypted wallets it is changed
145 2011-11-15 00:57:31 <iddo> cool
146 2011-11-15 00:57:45 <iddo> what was the advantage of 279 byte choice?
147 2011-11-15 00:58:10 <sipa> using openssl's default serialization function
148 2011-11-15 00:58:11 <denisx> luke-jr: you added the prev-hash code to pushpool, right?
149 2011-11-15 00:58:30 <iddo> ok
150 2011-11-15 00:58:46 <denisx> luke-jr: do have also a changed version of poclbm which gets fresh work when it gets that message?
151 2011-11-15 00:59:10 <luke-jr> denisx: I recently hacked my local copy to get new work when it gets any error
152 2011-11-15 01:13:05 <denisx> luke-jr: smart move
153 2011-11-15 01:15:18 <denisx> you should push that change
154 2011-11-15 01:24:30 <luke-jr> denisx: m0mchil doesn't seem to accept contributions
155 2011-11-15 01:27:49 <denisx> luke-jr: some month ago he was very open to me
156 2011-11-15 01:29:23 <denisx> I asked for "greater precision for rejected shares percentage" and he did it
157 2011-11-15 01:30:09 <denisx> ok, thats 4 month ago
158 2011-11-15 01:38:51 <luke-jr> yeah, but he wrote it too :p
159 2011-11-15 02:34:39 <gribble> ThomasV was last seen in #bitcoin-dev 2 days, 18 hours, 21 minutes, and 31 seconds ago: <ThomasV> Mqrius: you here?
160 2011-11-15 02:34:39 <Mqrius> !seen ThomasV
161 2011-11-15 02:34:40 <spaola> ThomasV (~ThomasV@unaffiliated/thomasv) was last seen quitting from #mtgox 4 hours, 17 minutes ago stating (Ping timeout: 244 seconds).
162 2011-11-15 02:57:02 <roconnor> it looks like a CODESEPARATOR that isn't executed in an IF block isn't activated
163 2011-11-15 03:00:05 <roconnor> ooh, the wiki gets this right :D
164 2011-11-15 03:14:28 <etotheipi_> maybe I'll try to find ways to use OP_CODESEPARATOR on testnet....
165 2011-11-15 03:14:33 <etotheipi_> *useful ways
166 2011-11-15 03:15:23 <roconnor> etotheipi_: be sure to use it with an IF statement :)
167 2011-11-15 03:16:07 <etotheipi_> roconnor, I made this diagram (http://dl.dropbox.com/u/1139081/BitcoinImg/OpCheckSigDiagram.png) based on various descriptions of how OP_CHECKSIG works... please let me know if I got the OP_CS wrong
168 2011-11-15 03:17:11 <etotheipi_> though, I can't really illustrate interactions with OP_CS and OP_IF, that would probably muddy the hell out of the diagram
169 2011-11-15 03:17:28 <roconnor> create a subscript from the last *executed* OP_CODESEPARATOR
170 2011-11-15 03:17:45 <roconnor> (ya I would bother illustrating it)
171 2011-11-15 03:18:11 <etotheipi_> so my interpretation is that CHECKSIG would include the opcodes *after* this script chunk, but not before
172 2011-11-15 03:18:17 <etotheipi_> i.e. script_part4
173 2011-11-15 03:20:40 <roconnor> you are missing several steps based on the value of the HashType  ... perhaps that is on purpose
174 2011-11-15 03:22:59 <roconnor> Step 10 makes it sounds like the result of each signature check is pushed onto the stack wheras in reality only one bool is pushed onto the stack indiciating if all the signatures check or if some signature failed.
175 2011-11-15 03:23:29 <etotheipi_> the title of the diagram is (OP_CHECKSIG (SIGHASH_ALL only)
176 2011-11-15 03:23:42 <etotheipi_> I was just trying to get the simple, standard case down
177 2011-11-15 03:23:55 <roconnor> ah okay
178 2011-11-15 03:24:05 <etotheipi_> oooh, good point about the pushing
179 2011-11-15 03:24:35 <etotheipi_> I actually never quite understood the other hashcodes
180 2011-11-15 03:25:18 <roconnor> I've implemented the other hashcodes ... but I've never tested it :/
181 2011-11-15 03:26:24 <etotheipi_> can you give me the gist of what they're supposed to accomplish?
182 2011-11-15 03:26:41 <etotheipi_> it looks like you can sign an input without locking in the other inputs
183 2011-11-15 03:28:42 <roconnor> etotheipi_: it mostly controls weather the outputs are included in the signature or not
184 2011-11-15 03:29:29 <roconnor> etotheipi_: so sigHashNone clears all the outputs
185 2011-11-15 03:29:48 <roconnor> etotheipi_: and sigHashSingle clears all the outputs but one
186 2011-11-15 03:30:13 <etotheipi_> so sigHashNone is like making a blank check
187 2011-11-15 03:31:17 <roconnor> I'm not certain, but I think so
188 2011-11-15 03:32:07 <etotheipi_> but does it require all the inputs to be in place when you sign it?
189 2011-11-15 03:32:30 <roconnor> everything but the scripts for the inputs
190 2011-11-15 03:32:48 <etotheipi_> I'm having a tough time thinking of use-cases for this... except maybe manually constructing partial transactions, that you want to give to others to sign and distribute the outputs how they decide to
191 2011-11-15 03:32:53 <roconnor> AnyoneCanPay means all the other inputs are eliminated
192 2011-11-15 03:33:33 <roconnor> so I guess SigHashNone plus AnyoneCanPay is like a blank check
193 2011-11-15 03:35:33 <etotheipi_> oh wait, not a blank check....
194 2011-11-15 03:35:42 <etotheipi_> output value is fixed, recipient isn't
195 2011-11-15 03:35:54 <roconnor> bearer cheque
196 2011-11-15 03:37:32 <cjdelisle> that doesn't make a whole lot of sense since evil miners could replace the output in a sighashnone tx with their own.
197 2011-11-15 03:38:04 <etotheipi_> roconnor, you are making me really glad I'm not trying to replicate the BTC protocol... just the pieces I need for a functioning client
198 2011-11-15 03:38:06 <roconnor> cjdelisle: I think you are right
199 2011-11-15 03:38:12 <etotheipi_> cjdelisle, that's partially true
200 2011-11-15 03:38:27 <etotheipi_> cjdelisle, it's possible for the miners to do that if ALL the inputs are signed using sighashnone
201 2011-11-15 03:38:38 <etotheipi_> but it's possible to have multiple inputs with different sighashes
202 2011-11-15 03:39:04 <cjdelisle> ofc the miner could throw out the input that doesn't use sighashnone
203 2011-11-15 03:39:05 <roconnor> etotheipi_: sure but an evil miner to drop the transaction entirely and make a new transaction that they output to themselves. ... it seems
204 2011-11-15 03:39:18 <roconnor> oh wait, no they cannot
205 2011-11-15 03:39:30 <roconnor> I see
206 2011-11-15 03:39:43 <cjdelisle> ahh only if you use sighashnone | anyonecanpay
207 2011-11-15 03:39:47 <roconnor> but if you has AnyoneCanPay and
208 2011-11-15 03:39:54 <etotheipi_> right
209 2011-11-15 03:39:54 <roconnor> cjdelisle: right, exactly
210 2011-11-15 03:41:16 <etotheipi_> sometimes I wonder if I throw out a transaction script that anyone can redeem, or something crazy like this... how long would it take for someone else to find, recognize it, and redeem it
211 2011-11-15 03:41:44 <roconnor> some people do that for fun
212 2011-11-15 03:41:56 <roconnor> though usually they announce it on the forum
213 2011-11-15 03:42:16 <etotheipi_> well, I know I would've found quite a few while debugging my blockchain reader
214 2011-11-15 03:42:28 <roconnor> :)
215 2011-11-15 03:42:30 <etotheipi_> any non-standardness got some thorough attention from me
216 2011-11-15 03:43:11 <roconnor> etotheipi_: are you using openssl (indirectly)?
217 2011-11-15 03:43:27 <etotheipi_> haha, it's funny you ask that
218 2011-11-15 03:43:46 <etotheipi_> I just had an epic battle with Crypto++ and almost switched to openssl... yesterday
219 2011-11-15 03:44:05 <roconnor> does everyone use the same wrong DER decoding as openssl?!
220 2011-11-15 03:44:22 <roconnor> oh wait, maybe you parse DER yourself?
221 2011-11-15 03:44:26 <etotheipi_> so I actually have a pure-python implementation, which manually parses the script
222 2011-11-15 03:44:30 <cjdelisle> do you have a converter for the openssl encoding of bignumbers to something else?
223 2011-11-15 03:44:32 <etotheipi_> right, I don't use the DER
224 2011-11-15 03:44:51 <etotheipi_> I spent some time picking apart the DER scripts
225 2011-11-15 03:45:18 <etotheipi_> since they are so consistent, I was able to figure out how they're typically encoded (which isn't a lot of different ways in BTC)
226 2011-11-15 03:45:40 <etotheipi_> though, I know it's going to come back and bite me sometime in the future... some strange DER encoding will show up in the blockchain and my code will croak
227 2011-11-15 03:46:03 <roconnor> etotheipi_: there is no problem
228 2011-11-15 03:46:10 <roconnor> DER is only used for ECDSA signatures
229 2011-11-15 03:46:12 <roconnor> that is it
230 2011-11-15 03:46:33 <cjdelisle> that's kind of strange
231 2011-11-15 03:46:45 <cjdelisle> I'd have expected the sig to be represented as X . Y
232 2011-11-15 03:46:46 <roconnor> cjdelisle: it is openssl's fault
233 2011-11-15 03:46:47 <etotheipi_> cjdelisle, it isn't too difficult to pull out the (r,s) values from the DER
234 2011-11-15 03:47:00 <etotheipi_> in fact, I illustrated it here:  https://bitcointalk.org/index.php?topic=29416.0
235 2011-11-15 03:47:12 <etotheipi_> you have to zoom in to see the individual bytes, though
236 2011-11-15 03:47:45 <etotheipi_> (bottom left of the first image)
237 2011-11-15 03:48:11 <etotheipi_> there's a boatload of size bytes...
238 2011-11-15 03:48:24 <cjdelisle> ahh that's very simple
239 2011-11-15 03:48:31 <cjdelisle> 0x04 . X . Y
240 2011-11-15 03:48:43 <roconnor> this reminds me; I need to set if compressed public keys can be accepted
241 2011-11-15 03:49:16 <etotheipi_> roconnor, is that where you put only the signature in the script?
242 2011-11-15 03:49:40 <roconnor> nope, that is key recovery
243 2011-11-15 03:49:49 <roconnor> compressed public keys look like:
244 2011-11-15 03:50:05 <roconnor> 0x02 . X  or 0x03 . X  depending on the parity of Y
245 2011-11-15 03:50:20 <roconnor> I conjecture that they work fine in bitcoin
246 2011-11-15 03:50:22 <etotheipi_> oh because there's only 1 or two possible y values for a given X
247 2011-11-15 03:50:24 <cjdelisle> and that is accepted in the chain?
248 2011-11-15 03:50:33 <roconnor> cjdelisle: I conjecture so
249 2011-11-15 03:50:36 <roconnor> but haven't tired
250 2011-11-15 03:50:38 <cjdelisle> neato
251 2011-11-15 03:50:52 <cjdelisle> patents be damned, that is cool
252 2011-11-15 03:51:14 <etotheipi_> I thought the key recovery was cool:  only include the sig, then back-solve for the public key
253 2011-11-15 03:51:20 <roconnor> I guess etotheipi_ hasn't found any of these in the wild
254 2011-11-15 03:51:32 <roconnor> ya, this only cuts the key size in half
255 2011-11-15 03:51:42 <roconnor> key recovery cuts the key size to 2 bits
256 2011-11-15 03:52:04 <cjdelisle> you can derive a public key from a sig?
257 2011-11-15 03:52:26 <roconnor> cjdelisle: from a sig and the data being signed
258 2011-11-15 03:52:32 <etotheipi_> I've been waiting for some day when I get stuck in an airport for a delayed flight... to try to do the key recovery problem.... I refuse to look up the solution because I want to see if I can figure it out
259 2011-11-15 03:52:39 <etotheipi_> :)
260 2011-11-15 03:52:42 <cjdelisle> heh
261 2011-11-15 03:52:44 <roconnor> cjdelisle: well that only narrows it down to at most 4 publick keys
262 2011-11-15 03:53:22 <roconnor> and almost always at most 2 public keys
263 2011-11-15 03:54:12 <cjdelisle> so you test each and figure out which works or are they both actually valid? sorry for the dumb question..
264 2011-11-15 03:54:22 <roconnor> I forget
265 2011-11-15 03:54:52 <roconnor> Originally I was thinking you would add 2 bits to secify which of the upto 4 keys you want
266 2011-11-15 03:55:19 <roconnor> but maybe you could just try all 4 and see if any match the hash ... I'm not sure what the security implications of this would be.
267 2011-11-15 03:55:26 <etotheipi_> well only one of them will match the Hash160 on the TxOut script
268 2011-11-15 03:55:26 <roconnor> I think it would be okay
269 2011-11-15 03:55:50 <roconnor> but sipa and I weren't 100% certain this was okay
270 2011-11-15 03:55:54 <roconnor> maybe only 90% certain
271 2011-11-15 03:56:25 <cjdelisle> but if there are actually 2 or 4 valid keys then there are 2 or 4 valid keypairs and that means ecdsa256 is really more like 255 or 254
272 2011-11-15 03:56:50 <etotheipi_> not really... a public key is 64 bytes
273 2011-11-15 03:56:50 <roconnor> closer to 255
274 2011-11-15 03:57:06 <etotheipi_> not 32
275 2011-11-15 03:57:23 <roconnor> but yes, there are often two public keys that would yield the same signature on the same data.
276 2011-11-15 03:57:29 <roconnor> IIRC
277 2011-11-15 03:58:18 <etotheipi_> right, reducing it to 510 or 511 bits of public key
278 2011-11-15 03:58:24 <cjdelisle> I had no idea
279 2011-11-15 03:58:46 <etotheipi_> there are:  115792089237316195423570985008687907852837564279074904382605163141518161494337
280 2011-11-15 03:58:55 <etotheipi_> points on the secp256k1 curve
281 2011-11-15 03:59:07 <etotheipi_> which is "0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141" in hex
282 2011-11-15 03:59:24 <etotheipi_> each one of those points is public key
283 2011-11-15 03:59:36 <etotheipi_> which is really f***ing close to 2^256
284 2011-11-15 03:59:53 <cjdelisle> well, it's 1/2 of 2^256
285 2011-11-15 04:00:16 <cjdelisle> if every other key is a collision
286 2011-11-15 04:00:43 <etotheipi_> oh, now I'm getting the nature of your question
287 2011-11-15 04:00:45 <iddo> doesn't really matter for bitcoin because there are collisions of different keys for same 160 bit hashed address?
288 2011-11-15 04:00:59 <roconnor> etotheipi_: I forget but I think identity element isn't allowed to be a public key
289 2011-11-15 04:01:05 <roconnor> etotheipi_: so subtract one
290 2011-11-15 04:01:06 <etotheipi_> iddo, you're absolutely correc,t but I"m still interested in the answer to this
291 2011-11-15 04:01:18 <iddo> ok
292 2011-11-15 04:01:48 <etotheipi_> so I guess the question then, is, it looks like given a signature, there are sometimes up to 4 points on the curve (4 public keys) which could've produced that signature
293 2011-11-15 04:02:50 <cjdelisle> so ecc256 is slightly less strong than 255 bits
294 2011-11-15 04:03:10 <etotheipi_> so you're probably right...
295 2011-11-15 04:03:37 <etotheipi_> except that if two different people ended up with those two public/private keypairs... they could sign for each others' TxOuts, but they wouldn't realize it
296 2011-11-15 04:04:18 <etotheipi_> actually... that's not *necessarily* true... the fact that four different public keys could've created that sig doesn't mean that all four keys are the *same*
297 2011-11-15 04:04:30 <etotheipi_> it could be different four keys depending on which random number was used during signing
298 2011-11-15 04:04:35 <cjdelisle> yea, it's just a theoretical interest, I'm sure *real* cryptographers have looked it over and took it into account.
299 2011-11-15 04:05:01 <etotheipi_> damnit, you might've just nerd-sniped me
300 2011-11-15 04:05:11 <roconnor> :D
301 2011-11-15 04:05:12 <etotheipi_> (or I sniped myself...)
302 2011-11-15 04:06:18 <iddo> are you saying that given signature where are 4 privkeys, or given a pubkey there are 4 privkeys?
303 2011-11-15 04:07:08 <roconnor> there is a bijection between private and public keys
304 2011-11-15 04:07:14 <etotheipi_> I'm not positive:  we know that a signature may have up to four private/public keypairs that signed for it... but I don't know if those are actually "identical" keys... in fact I'm fairly certain they aren't
305 2011-11-15 04:07:50 <etotheipi_> in fact, I would guess that the four different public keys that you find... would be different if the signer picked a different random number, but that's just a hypothesis
306 2011-11-15 04:07:51 <roconnor> how can different keypairs be "identical"?
307 2011-11-15 04:08:18 <iddo> roconnor: is it bijection or just 1-1 from sk to pk?
308 2011-11-15 04:08:28 <roconnor> iddo: bijection
309 2011-11-15 04:09:17 <iddo> well if it's bijection then you should get 256 bits of security
310 2011-11-15 04:09:21 <etotheipi_> the question I want to know is:  you look at a signature and find two possible public/private keypairs that created that signature... if you now sign a new message with those two keypairs, are you going to get the same signature?
311 2011-11-15 04:09:44 <iddo> i.e. given pubkey you have to guess 256 bits if you use brute force
312 2011-11-15 04:10:16 <roconnor> iddo: there are 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 public key / private key pairs
313 2011-11-15 04:10:35 <etotheipi_> I'm just saying theoretically... if you could magically recover the public-private key pairs of the two keys that could've signed that message... are they actually the same?  I don't think so
314 2011-11-15 04:10:37 <roconnor> iddo: one less if you don't count the infinity / 0 pair
315 2011-11-15 04:11:20 <roconnor> etotheipi_: of course they wouldn't be the same; that is the definition of having two keys
316 2011-11-15 04:11:22 <roconnor> :)
317 2011-11-15 04:11:26 <iddo> ah that's less than 2^256 ? how much is that hex num?
318 2011-11-15 04:11:56 <roconnor> iddo: what do you mean "how much"?
319 2011-11-15 04:11:59 <etotheipi_> Number of keys:  115792089237316195423570985008687907852837564279074904382605163141518161494337  2^256 = 115792089237316195423570985008687907853269984665640564039457584007913129639936
320 2011-11-15 04:12:12 <iddo> thanks:)
321 2011-11-15 04:12:24 <roconnor> iddo: is is about 2^256 - 2^128
322 2011-11-15 04:12:43 <roconnor> little more
323 2011-11-15 04:13:09 <etotheipi_> yeah, I realize that was a pretty useless message with those numbers
324 2011-11-15 04:13:39 <cjdelisle> just checked
325 2011-11-15 04:13:53 <cjdelisle> it works by trying one then trying the other
326 2011-11-15 04:13:59 <iddo> it's not true that for any signature and any unrelated privkey, you can find plaintext message that if you sign with that privkey you get that signature?
327 2011-11-15 04:14:05 <cjdelisle> if one doesn't verify it flips the sign
328 2011-11-15 04:14:12 <roconnor> etotheipi_: I had a computer checked proof of primality drawn up for that number :)
329 2011-11-15 04:14:53 <roconnor> iddo: I think it is (almost) true
330 2011-11-15 04:15:01 <etotheipi_> I hope it's prime
331 2011-11-15 04:15:05 <roconnor> iddo: I think you can do it about 50% of the time
332 2011-11-15 04:15:23 <roconnor> etotheipi_: the order of elliptic curves don't have to be prime, but it is quite nice when they are.
333 2011-11-15 04:15:39 <etotheipi_> It's a G(p) curve... where p is prime
334 2011-11-15 04:15:54 <iddo> roconnor: so what was the point about having 4 possible keys given a signature? isn't it true that there are about 2^255 keys instead of just 4 ?
335 2011-11-15 04:16:41 <iddo> or was it given signature+plaintext hmm..
336 2011-11-15 04:16:59 <roconnor> iddo: for a given signature *and given data* there are at most 4 public/private key pairs that could have made that signature
337 2011-11-15 04:17:11 <iddo> ok ok
338 2011-11-15 04:17:41 <roconnor> and you can easily compute the 4 public keys
339 2011-11-15 04:17:52 <roconnor> or however many there are (could be 0 keys)
340 2011-11-15 04:17:56 <lfm_> yes it would be vanishingly unlikly the other 3 correspond to any actual key
341 2011-11-15 04:17:59 <roconnor> not so easy to compute the private keys :D
342 2011-11-15 04:18:05 <cjdelisle> roconnor: I checked the document, you can narrow it down by testing them using the verification routine so ecc256 is apparently truely ecc256
343 2011-11-15 04:18:48 <lfm_> ping lfm
344 2011-11-15 04:18:51 <etotheipi_> * 2^256-epsilon
345 2011-11-15 04:19:49 <cjdelisle> But then saving a little space in the chain at the cost of increasing processor cost looks like a bad deal
346 2011-11-15 04:20:03 <iddo> i don't think it affect the security, if you find one of the other 4 privkeys given the signature then it won't help you sign new messages if the privkey you found doesn't correspond to the right pubkey
347 2011-11-15 04:20:32 <cjdelisle> better idea is to work on an unspent tx tree so we don't need to cart the chain around with us everywhere
348 2011-11-15 04:20:35 <roconnor> cjdelisle: I'm moderately sure the key recovery is only slightly more expensive than normal signature verification.
349 2011-11-15 04:21:15 <etotheipi_> I haven't seen the proof, but any ECC arithmatic operations are pretty expensive
350 2011-11-15 04:21:36 <etotheipi_> especially if it has a x^-1 in it... which most of them do
351 2011-11-15 04:21:59 <roconnor> yes, but the key recovery operation is, I think, the same work as verification
352 2011-11-15 04:22:06 <etotheipi_> oh, I see
353 2011-11-15 04:22:06 <roconnor> is is basically verification run backwards
354 2011-11-15 04:22:13 <roconnor> *it is
355 2011-11-15 04:22:26 <cjdelisle> even if it's the same cost and 1/2 of the time you get the wrong one, it is still expensive
356 2011-11-15 04:22:27 <etotheipi_> oh yeah, I guess you don't need to verify the pub key if you just derived it from the sig
357 2011-11-15 04:23:01 <roconnor> all the 2 or 4 keys are easy to compute from each other
358 2011-11-15 04:23:13 <cjdelisle> mmhmm
359 2011-11-15 04:23:27 <etotheipi_> gah, I gotta go to sleep...
360 2011-11-15 04:23:28 <roconnor> first of all we can discount the 4 key problem
361 2011-11-15 04:23:42 <roconnor> since that isn't likely to come up in this universe's lifetime
362 2011-11-15 04:23:47 <cjdelisle> well unspent tx tree would allow a client to be running in like 3 minutes from a cold start so that's way way more important IMO
363 2011-11-15 04:24:07 <etotheipi_> btw, to answer the earlier question, my code has a pure-python ECDSA implementaiton, which is slow as dirt... but I also added a C++ call, via Crypto++ and SWIG... just so I can have a fast, secure method availble if SWIG is around
364 2011-11-15 04:24:13 <roconnor> and I think the 2 keys are like the negation or each other, or some other trivial operation.
365 2011-11-15 04:24:27 <roconnor> etotheipi_: and DER?
366 2011-11-15 04:24:38 <roconnor> etotheipi_: always decoded in python?
367 2011-11-15 04:25:03 <roconnor> cjdelisle: I'd be more interested in using compresed public keys
368 2011-11-15 04:25:18 <roconnor> which I expect can be used right now with no protocol changes
369 2011-11-15 04:25:49 <cjdelisle> I have a proposal for unspent tx trees with no breaking protocol changes
370 2011-11-15 04:26:19 <etotheipi_> crypto++ handles the DER for me
371 2011-11-15 04:26:27 <cjdelisle> you just link them into the merged mining hashtree and clients which don't support them don't notice
372 2011-11-15 04:26:37 <cjdelisle> basicly all it affects is the coinbase
373 2011-11-15 04:26:38 <roconnor> etotheipi_: really, the same way openssl does?
374 2011-11-15 04:26:42 <etotheipi_> oh crap... no it doesn't
375 2011-11-15 04:26:45 <roconnor> oh
376 2011-11-15 04:26:47 <roconnor> whew
377 2011-11-15 04:27:01 <etotheipi_> that's right, I just remembered I had to mangle it to make it work
378 2011-11-15 04:27:15 <etotheipi_> it has to be 64 bytes, unsigned, big-endian (x,y) pair
379 2011-11-15 04:27:24 <roconnor> cjdelisle: how do you stop miners from lying about the tree?
380 2011-11-15 04:28:01 <cjdelisle> each tree references the last tree, if a miner lies you know because there are more transactions in the tree which didn't happen in between
381 2011-11-15 04:29:17 <cjdelisle> If you hold the entire tree on your desktop, verifying it is trivial because it references the last tree so you just look at the blocks in between the latest and the one before
382 2011-11-15 04:29:33 <etotheipi_> roconnor, so you're on your own with the DER... I picked apart the bytemap and manually entered the (x,y) pair as large integers, either to a python module, or crypto++
383 2011-11-15 04:29:34 <cjdelisle> you can decide how many trees back you want to go depending on your paranoia level
384 2011-11-15 04:29:55 <etotheipi_> (one nice benefit of python is the arbitrary-length integers:  2**2000 returns a valid [very long] result)
385 2011-11-15 04:30:18 <roconnor> etotheipi_: no problem.  I'm good;  I just wanted to know what others were doing
386 2011-11-15 04:30:21 <cjdelisle> ahh nice of python to do that
387 2011-11-15 04:30:46 <etotheipi_> it means you can implement EC math without importing any modules
388 2011-11-15 04:31:20 <etotheipi_> actually... any of these assymetric encryptions... it's slow, but it's ridiculously portable and no dependencies :)
389 2011-11-15 04:31:51 <cjdelisle> here's the full unspent tx tree proposal http://btc.pastebay.com/144544
390 2011-11-15 04:32:12 <cjdelisle> there are a few missing details such as how a tree makes reference to the tree before it.
391 2011-11-15 04:32:31 <lfm_> so its not full then
392 2011-11-15 04:33:22 <cjdelisle> but I went out of my way to make sure it would function without any one node holding the entire unspent tx tree since that could easily grow to gigabytes of size.
393 2011-11-15 09:27:34 <gmaxwell> oh my god
394 2011-11-15 09:27:48 <gmaxwell> slashdot headline on the msft red ballons paper
395 2011-11-15 09:27:49 <gmaxwell> "Researchers Locate Flaw In Bitcoin Protocol"
396 2011-11-15 09:29:19 <coderrr> lol
397 2011-11-15 09:29:23 <coderrr> shit
398 2011-11-15 09:29:31 <coderrr> should i add a note to my post
399 2011-11-15 09:42:35 <edcba> what ?!
400 2011-11-15 09:45:30 <edcba> potential flaw in summary
401 2011-11-15 09:45:46 <edcba> i guess when i read the paper it will be some stupid assumption
402 2011-11-15 09:45:59 <edcba> "The flaw pointed out in the paper is that there is a negative incentive for miners to forward Bitcoin transactions"
403 2011-11-15 09:46:03 <edcba> ok
404 2011-11-15 09:46:59 <gmaxwell> edcba: thats not something new in the paper though, it's been rehashed many times.
405 2011-11-15 09:47:05 <edcba> solution no fee
406 2011-11-15 09:47:18 <edcba> of course it still costs bw to miners
407 2011-11-15 09:47:35 <edcba> but p2p part of bitcoin still sux
408 2011-11-15 09:47:41 <gmaxwell> The people who wrote the paper didn't claim that was new.
409 2011-11-15 09:48:04 <coderrr> edcba, let me know if you want me to change someting
410 2011-11-15 09:48:27 <edcba> i didn't read the whole thing yet
411 2011-11-15 09:48:42 <edcba> but now it's on /. i guess it's a bit late to redact many thing :)
412 2011-11-15 09:50:50 <edcba> i don't yet understand the proposed solution :)
413 2011-11-15 09:51:13 <Edward_Black> edcba actually, the fee mechanic of BTC is due to long-term economical plans for subsidy removal, and forcing miners to subsist on fees
414 2011-11-15 09:51:37 <edcba> yes but i still don't know if it's a good idea
415 2011-11-15 09:51:41 <gmaxwell> They hardly describe it what they're talking about is how you should figure out the rewards in a system which incentivizes forwarding by paying forwarders. They don't talk about how to construct such a system.
416 2011-11-15 09:51:47 <Edward_Black> Nobody knows edcba