1 2013-02-15 01:15:46 <jaakkos> how about making the bitcoin client first download block headers and asking merkle branches from a full neighbour to provide "full" functionality, then download merkle trees in the background?
2 2013-02-15 01:16:11 <jaakkos> so that there will always be a good chance that you have full neighbors
3 2013-02-15 01:26:31 <Eliel_> jaakkos: That's the long term plan, as I understand. It requires someone to take up the task and actually do it to happen though.
4 2013-02-15 01:39:30 <sipa> jaakkos: no need for merkle branches, just the headers in the best chain suffices
5 2013-02-15 01:39:34 <sipa> and indeed, that's the plan
6 2013-02-15 01:39:47 <jaakkos> sipa: how do you know your balance then
7 2013-02-15 01:40:02 <sipa> you don
8 2013-02-15 01:40:08 <sipa> 't
9 2013-02-15 01:40:54 <jaakkos> well you can't even pay because you don't know the outputs
10 2013-02-15 01:41:00 <jaakkos> that kind of sucks?
11 2013-02-15 01:41:20 <sipa> wait
12 2013-02-15 01:41:24 <sipa> there's two different ideas
13 2013-02-15 01:42:11 <sipa> 1) download headers first, and then sync block data in the background, only having wallet functionality after the second step
14 2013-02-15 01:42:45 <jaakkos> (... sowhy bother the first step at all?)
15 2013-02-15 01:43:19 <sipa> that's already extremely useful, as it means you know the best chain in advance, can do sigcheck skipping without hardcoded checkpoints, do load spreading of the actual block data downloa (as it's known what needs to be downloaded), ...
16 2013-02-15 01:43:38 <sipa> it's just an optimization for synchronizing a full node, like we have now
17 2013-02-15 01:44:21 <sipa> the other idea, "headers only mode", is starting as an SPV node, which downloads headers and transactions interesting to the user's wallet first; and in the background upgrade to a full node if resources allow it
18 2013-02-15 01:44:38 <sipa> that's probably what you were referring to
19 2013-02-15 01:47:27 <jaakkos> yes
20 2013-02-15 01:47:44 <sipa> imho, we should just disconnect both entirely
21 2013-02-15 01:47:50 <sipa> wallet == spv node
22 2013-02-15 01:47:59 <sipa> blockchain == full node
23 2013-02-15 01:48:10 <sipa> run both if you want the security of a full node + a wallet
24 2013-02-15 01:48:15 <Luke-Jr> :D
25 2013-02-15 01:48:52 <sipa> (it can still be the same codebase, or even the same binary)
26 2013-02-15 01:49:08 <Luke-Jr> sipa: or better, a shared library <.<
27 2013-02-15 01:49:17 <sipa> sure
28 2013-02-15 01:49:39 <sipa> there is currently nothing in bitcoin-qt that relies on having the full block data present
29 2013-02-15 01:49:51 <sipa> (afaik)
30 2013-02-15 01:50:28 <Luke-Jr> ACTION kicks 1BmFHTUM7Dtfyo15SaXHs2EoMWLKMBbfTe
31 2013-02-15 11:22:48 <ciphermonk> How do you determine the transaction ordering used to compute the merke tree? Is it just the order in which you received the transactions in a block using "getdata" ?
32 2013-02-15 11:24:30 <ciphermonk> I'm confused because some dumps hint an the existence of a vMerkleTree ( ex: here: https://en.bitcoin.it/wiki/Dump_format#CBlock ) but I can't find any reference to such a structure in the protocol itself
33 2013-02-15 11:25:06 <Luke-Jr> ciphermonk: correct
34 2013-02-15 11:25:43 <Luke-Jr> ciphermonk: vMerkleTree is just a cache of all the hashes used in the calculation
35 2013-02-15 11:26:31 <ciphermonk> ah ok! thanks a lot :)
36 2013-02-15 11:36:01 <sipa> ciphermonk: the order of transactions in a block is fixed (and meaningful)
37 2013-02-15 11:39:12 <ciphermonk> ok, I wasn't sure if I missed an additional structure or protocol message that would specify the ordering. It's good to know that the order they are sent on the wire is fixed and this order is used to compute the merkle root
38 2013-02-15 11:48:12 <ciphermonk> thanks for the clarification!
39 2013-02-15 13:48:25 <Jouke> When I want to get the public hash of a standard transaction, can I just remove "76a914" from the beginning and "88ac" from the end?
40 2013-02-15 13:49:23 <jgarzik> Jouke: Your question does not make sense. Each transaction is constructed, and then a hash is performed over all its data.
41 2013-02-15 13:49:28 <sipa> what is a 'public hash' ?
42 2013-02-15 13:50:09 <sipa> the txid of a transaction is the double-sha256 hash of its serialized form
43 2013-02-15 13:50:11 <Jouke> Damn it, I am not comfortable with all the terminology
44 2013-02-15 13:50:51 <sipa> i still have no idea what you're asking :0
45 2013-02-15 13:50:57 <Jouke> I basically want to get a bitcoinaddress out of a standard transaction.
46 2013-02-15 13:51:18 <sipa> a transaction doesn't have an addres
47 2013-02-15 13:51:26 <sipa> transaction outputs have output scripts
48 2013-02-15 13:51:37 <sipa> and some output scripts correspond to an address
49 2013-02-15 13:51:38 <Jouke> Sorry, the output svript
50 2013-02-15 13:51:42 <sipa> (in practice, most)
51 2013-02-15 13:52:08 <sipa> ah
52 2013-02-15 13:55:30 <sipa> Jouke: if the script starts with those 3 bytes, and ends with those 2, you can indeed drop them to obtain the hash160 of the pubkey (which, when encoded in base58, is the address)
53 2013-02-15 13:55:31 <gavinandresen> Jouke: if it is 25 bytes long, begins with 76a914, and ends with 88ac??? then yes, the 20-byte hash is the other 20 bytes
54 2013-02-15 13:56:05 <Jouke> Thanks :)
55 2013-02-15 13:58:36 <gavinandresen> just be careful, that is not the only way to encode a standard transaction (you can replace the 0x14 byte with OP_PUSHDATA opcode plus extra bytes)
56 2013-02-15 13:59:38 <Jouke> Does the bitcoinclient at this moment produce such transactions gavinandresen?
57 2013-02-15 13:59:54 <gavinandresen> no
58 2013-02-15 14:00:22 <Jouke> Ok, thanks for the info.
59 2013-02-15 14:00:32 <gavinandresen> When I say "be careful", I mean: think about if an attacker might be able to cause trouble if they encoded it differently
60 2013-02-15 14:00:58 <sipa> gavinandresen: are you ok with the comments in #2310?
61 2013-02-15 14:02:55 <gavinandresen> sipa: next time we add a checkpoint, how do we get: total number of transactions between genesis and last checkpoint
62 2013-02-15 14:03:18 <sipa> gavinandresen: look at debug.log (the SetBestChain line tells you tx=...)
63 2013-02-15 14:03:40 <gavinandresen> ah-- that is non-obvious, would be nice if the comment said so
64 2013-02-15 14:03:44 <sipa> ack
65 2013-02-15 14:04:21 <gavinandresen> other than that, looks great
66 2013-02-15 14:06:05 <sipa> i'm afraid about people complaining "oh my, this is SO much slower! 0.8.0rc1 did like 50% in a few minutes, and it's taken an HOUR already here!"
67 2013-02-15 14:07:07 <gavinandresen> if we do our job right, we'll be in exponential growth, and we'll have a lot more new customers than old customers. So new customer experience is more important....
68 2013-02-15 14:14:01 <sipa> gavinandresen: update pushed
69 2013-02-15 14:36:43 <discrete> ;;genrate 600
70 2013-02-15 14:36:44 <gribble> The expected generation output, at 600.0 Mhps, given difficulty of 3275464.58657, is 0.0921224766392 BTC per day and 0.00383843652663 BTC per hour.
71 2013-02-15 14:36:51 <discrete> ;;genrate 700
72 2013-02-15 14:36:53 <gribble> The expected generation output, at 700.0 Mhps, given difficulty of 3275464.58657, is 0.107476222746 BTC per day and 0.00447817594774 BTC per hour.
73 2013-02-15 14:37:02 <discrete> ;;genrate 900
74 2013-02-15 14:37:03 <gribble> The expected generation output, at 900.0 Mhps, given difficulty of 3275464.58657, is 0.138183714959 BTC per day and 0.00575765478995 BTC per hour.
75 2013-02-15 14:42:50 <jgarzik> ;;genrate 11.2
76 2013-02-15 14:42:51 <gribble> The expected generation output, at 11.2 Mhps, given difficulty of 3275464.58657, is 0.00171961956393 BTC per day and 7.16508151638e-05 BTC per hour.
77 2013-02-15 14:43:36 <jgarzik> so CPU mining would gross US$16.75/year
78 2013-02-15 14:45:30 <jgarzik> ACTION compresses his coins down to a single coin
79 2013-02-15 14:49:40 <helo> neutron coin
80 2013-02-15 14:57:31 <MC1984> eh
81 2013-02-15 15:24:10 <gavinandresen> sipa: I've got a reproduceable crash-at-shutown, running bitcoin against an intentionally-corrupt leveldb datadir
82 2013-02-15 15:24:28 <gavinandresen> sipa: crash is caused by deleting CCheckQueue after exit???.
83 2013-02-15 15:25:40 <gavinandresen> sipa: https://gist.github.com/gavinandresen/4961485
84 2013-02-15 15:26:17 <gavinandresen> I wonder if interrupting all of our boost::threads in Shutdown would be an easy fix...
85 2013-02-15 15:32:12 <sipa> gavinandresen: deleting CCheckQueue? it's statically allocated?
86 2013-02-15 15:33:21 <gavinandresen> right, destructors are being called after exit() ...
87 2013-02-15 15:34:20 <sipa> hmm, and why is that a problem? sounds very expected
88 2013-02-15 15:34:24 <gavinandresen> ??? in some random order, which might be the issue with random crashes at exit
89 2013-02-15 15:34:49 <gavinandresen> I'm seeing some weirdness, recompiling Bitcoin-Qt to rule out a bad build
90 2013-02-15 15:35:05 <TD> shutdown in a threaded program is known to be a surprisingly hard problem
91 2013-02-15 15:35:46 <TD> sipa: fyi some core google libraries (like bigtable) don't actually support clean shutdown at all. they are written on the assumption that they'll only ever be cleanly killed by the kernel
92 2013-02-15 15:35:52 <TD> for exactly this reason
93 2013-02-15 15:35:59 <TD> we don't have that luxury, i guess
94 2013-02-15 15:36:17 <sipa> yeah, crash-only software is a nice idea
95 2013-02-15 15:36:47 <gavinandresen> does Windows have a "kill me right now" signal/whatever ?
96 2013-02-15 15:39:44 <TD> _exit
97 2013-02-15 15:39:47 <TD> it bypasses shutdown handlers
98 2013-02-15 15:39:49 <broomkorn> http://serverfault.com/questions/151196/how-is-the-windows-kill-process-works
99 2013-02-15 15:40:04 <broomkorn> http://support.microsoft.com/kb/178893
100 2013-02-15 15:40:04 <TD> i believe _exit is a standard thing, actually
101 2013-02-15 15:40:19 <TD> http://msdn.microsoft.com/en-us/library/6wdz5232(v=vs.80).aspx
102 2013-02-15 15:40:43 <TD> note that exit() also flushes stream buffers, which is probably useful for logging. so if you switch to _exit it'd be needed to do it manually
103 2013-02-15 15:40:51 <TD> though for software of the complexity of bitcoin clean shutdown should be achievable
104 2013-02-15 15:41:36 <TD> the other possibility of course is to not allocate CCheckQueue statically and then delete it yourself, which achieves a predictable ordering
105 2013-02-15 15:41:49 <TD> the problem is ThreadScriptCheck is still waiting on it
106 2013-02-15 15:42:37 <TD> so the final possibility is to deliberately leak CCheckQueue and suppress valgrind warnings
107 2013-02-15 15:44:03 <gavinandresen> Here's a radical idea: have Shutdown wait only on the wallet.dat-flushing thread, then _exit().
108 2013-02-15 15:47:28 <TD> could work
109 2013-02-15 15:48:09 <sipa> gavinandresen: i think we'll forget things, and cause more problems
110 2013-02-15 15:48:13 <TD> though i wonder what happens if you _exit in the middle of leveldb doing things
111 2013-02-15 15:48:19 <TD> clean shutdown does seem very much preferable
112 2013-02-15 15:48:35 <TD> i'd just leak the CCheckQueue. no biggie.
113 2013-02-15 15:50:30 <gavinandresen> TD: yes, that's probably the right answer for now. That's what we do for the logging mutex in our OutputDebugStringF(), which has to work after exit()
114 2013-02-15 15:50:32 <sipa> in theory, ConnectBlock cannot exit while the checkqueue is active still
115 2013-02-15 15:50:49 <TD> what about leveldb shutdown?
116 2013-02-15 15:50:53 <TD> i don't remember writing any code for that
117 2013-02-15 15:52:37 <gmaxwell> oh hey, did someone else hit that CCheckQueue mutex deallocation hang?
118 2013-02-15 15:52:59 <sipa> TD: there's a sync flush to both leveldb databases, at least
119 2013-02-15 15:53:01 <gavinandresen> gmaxwell: crashes reproducibly for me on a corrupt datadir
120 2013-02-15 15:53:06 <TD> ok
121 2013-02-15 15:53:29 <sipa> TD: and a delete of the db, and the env
122 2013-02-15 15:54:22 <gmaxwell> gavinandresen: that sounds similar to my reproduction case too??? re-coin-indexing a blktree that had been zzufed. Sipa and I spent a while banging our heads on it and.. It wasn't reliably reproducable for me??? would take about 100 tries or so.
123 2013-02-15 15:54:36 <gavinandresen> I looked hard at the shutdown code a long time ago, came up with a plan to make it better, then got busy with other things.
124 2013-02-15 15:54:38 <TD> ok
125 2013-02-15 15:54:52 <gmaxwell> gavinandresen: interestingly, making the mutex inside the CCheckQueue a global made the problem 'go away'.
126 2013-02-15 15:55:35 <gmaxwell> still, it makes no sense. All of the validators should be stopped long before anything exits.
127 2013-02-15 15:56:19 <gavinandresen> gmaxwell: it's not a normal exit in this case, I think it is still somewhere in AppInit2
128 2013-02-15 15:56:22 <sipa> all validators should be stopped before ConnectBlock _can_ exit
129 2013-02-15 15:56:49 <sipa> though that doesn't mean they're necessary exited
130 2013-02-15 15:58:00 <sipa> i'll try to have a look at the shutdown cases for ccheckqueue this weekend
131 2013-02-15 15:59:09 <esreskkesketske> hi
132 2013-02-15 15:59:12 <esreskkesketske> need help
133 2013-02-15 16:00:51 <gavinandresen> sipa: order of events for the crash I'm seeing is: ??? Step 4 in init.cpp spawns threads. Step 7: load the block chain exits with InitError(). exit() called, crash in mutex destructor.
134 2013-02-15 16:02:00 <gavinandresen> TD: you asked about paymentrequest work yesteday: yes, I've started plowing through the "client" side of the TODO list. I bit the bullet and read a couple books about Qt programming...
135 2013-02-15 16:02:11 <TD> cool. Qt is a pretty nice API.
136 2013-02-15 16:02:15 <TD> it shouldn't prove too hard.
137 2013-02-15 16:02:22 <gavinandresen> yes, I'm really liking Qt
138 2013-02-15 16:02:23 <TD> i have some java code for validating requests, but i never finished it
139 2013-02-15 16:02:53 <TD> there are still higher priorities around correctness and performance, but i guess i'll see how quickly you make progress
140 2013-02-15 16:03:49 <gavinandresen> TD: we never nailed down details of mime types, or if we're going to extend bitcoin: URIs for payment requests
141 2013-02-15 16:03:56 <TD> that is true
142 2013-02-15 16:04:06 <TD> those should be fairly simple and uncontroversial things though?
143 2013-02-15 16:04:12 <TD> application/x-bitcoin-payment-request
144 2013-02-15 16:04:41 <TD> bitcoin:address?value=1.23&req=https://merchant.com/req/1a2b3c
145 2013-02-15 16:04:44 <gavinandresen> I did: applications/x-btc-signed-payment-request and x-btc-payment-request
146 2013-02-15 16:05:10 <gavinandresen> (blah, application/.???)
147 2013-02-15 16:05:27 <TD> oh yeah. i remember us debating whether it was better to have two mime types or just make pki_data optional
148 2013-02-15 16:05:45 <gavinandresen> ah, right-- with a pki_type of "none" ?
149 2013-02-15 16:06:25 <TD> sure, or missing also
150 2013-02-15 16:06:27 <gavinandresen> do you think the bitcoin clients will always pull the payment request from the server?
151 2013-02-15 16:06:52 <TD> no. i expect some to fetch it via bluetooth, NFC, load them from email attachments, receive them via Android intents and other things
152 2013-02-15 16:07:08 <TD> but for opening a wallet app from a web browser, it seems ideal. and if you have something that contains a URL you probably have a server also
153 2013-02-15 16:07:18 <TD> so we may as well start there
154 2013-02-15 16:07:23 <gavinandresen> and it fits in a QR code nicely.
155 2013-02-15 16:07:38 <TD> a URL does. a fully blown payment request might not.
156 2013-02-15 16:07:57 <TD> at least not one that scans quickly and reliably. but you want a server anyway, really, otherwise you end up re-using addresses
157 2013-02-15 16:08:03 <gavinandresen> right-- the alternative is : click on a link, and the server serves up the payment request data directly
158 2013-02-15 16:08:16 <TD> i'm sure there'll be cheap hosting services that generate payment requests for you
159 2013-02-15 16:08:16 <TD> yeah
160 2013-02-15 16:08:24 <gavinandresen> ??? although I can't figure out how to make my Mac Do The Right Thing with a payment request sent directly
161 2013-02-15 16:08:30 <TD> that also works. extending a bitcoin: uri has the nice advantage of backwards compatibility
162 2013-02-15 16:09:19 <TD> otherwise you'll get websites giving uses complicated instructions
163 2013-02-15 16:09:21 <TD> which would kinda suck
164 2013-02-15 16:09:37 <TD> and more importantly, set low UI standards for the community.
165 2013-02-15 16:09:51 <TD> so i like extending the custom URI. it also works quite nicely with mobile platforms.
166 2013-02-15 16:17:00 <gavinandresen> TD: I'm still fuzzy on if or how a webwallet would handle bitcoin: URIs. And even fuzzier on if or how a webwallet could handle the click-and-get-paymentrequest-data ???.
167 2013-02-15 16:17:19 <TD> HTML5 allows websites to register themselves as URL handlers and it's now fairly widely supported
168 2013-02-15 16:17:50 <gavinandresen> mime type handlers, too? or just new URL schemes?
169 2013-02-15 16:18:12 <TD> https://developer.mozilla.org/en-US/docs/DOM/navigator.registerProtocolHandler
170 2013-02-15 16:18:16 <TD> just new URL schemes AFAIK
171 2013-02-15 16:18:39 <gavinandresen> TD: mmm: http://dev.opera.com/articles/view/html5-custom-protocol-and-content-handlers/ ???. says mime types, too....
172 2013-02-15 16:19:23 <TD> cool
173 2013-02-15 16:24:12 <TD> gavinandresen: btw what's the current ETA for 0.8 final?
174 2013-02-15 16:24:47 <gavinandresen> darn good question. I'm waffling on whether or not we can live with the random-crash-on-exit bug
175 2013-02-15 16:25:33 <TD> *shrug* you can always follow up with a 0.8.1
176 2013-02-15 16:26:16 <gavinandresen> true. besides that bug, and some reports of db corruption (that might just be flaky hard drives), 0.8 feels very solid
177 2013-02-15 16:26:55 <TD> good. it's time to get it out there then.
178 2013-02-15 16:27:19 <Arnavion> Make the application safe to crash! Then "crashing the application to quit it super fast" can be a feature!
179 2013-02-15 16:27:29 <TD> i want to get new MultiBit and android wallet releases out maybe a week after 0.8, so there are enough nodes to not get smacked by every client trying to use bloom filtering at once
180 2013-02-15 16:27:43 <TD> assuming people upgrade fairly fast of course
181 2013-02-15 16:28:35 <TD> which i am skeptical about ???. i bet 90%+ of people running nodes have no way to find out about new ones
182 2013-02-15 16:28:38 <TD> an alert might be appropriate
183 2013-02-15 16:30:48 <gmaxwell> An alert would be crying wolf here.
184 2013-02-15 16:31:13 <gmaxwell> Uptake of new versions has been reasonably quick in the past.
185 2013-02-15 16:31:21 <TD> yeah. i guess we can see how it goes.
186 2013-02-15 16:31:45 <gmaxwell> ... though not 'a week' quick, even with alerts.
187 2013-02-15 16:32:40 <TD> ACTION -> home
188 2013-02-15 16:32:59 <dhill> latest boost didn't fix my issue.. now trying db 4.8.30 .. instead of 4.6.21
189 2013-02-15 16:33:36 <gmaxwell> Causing fast uptake would vastly increase risk in any case. It will be good for 0.8 to roll slowly. We had previously discussed explicitly discouraging miners and merchants from running it. I don't think we'll need to do that now... but still, no need to rush in.
190 2013-02-15 16:38:29 <sipa> ;;bc,tslb
191 2013-02-15 16:38:30 <gribble> Error: unexpected EOF while parsing (<string>, line 1)
192 2013-02-15 16:44:58 <jgarzik> gmaxwell: in the current state, I think encouraging miners to use 0.8 is nice
193 2013-02-15 16:45:05 <jgarzik> and full nodes
194 2013-02-15 16:48:08 <andytoshi> dumb question: is there any firewall setup needed to run a full node properly?
195 2013-02-15 16:48:40 <sipa> unless your firewall by default blocks all incoming and outgoing traffic, no
196 2013-02-15 16:49:44 <andytoshi> thx, i'm good then
197 2013-02-15 17:07:33 <dhill> um, i don't want to jinx myself, but i am thinking db 4.8 is working
198 2013-02-15 17:07:53 <dhill> only to block 132000 so far, but we shall see
199 2013-02-15 17:08:19 <andytoshi> congrats :)
200 2013-02-15 17:08:26 <dhill> DONT JINX IT!!
201 2013-02-15 17:08:30 <dhill> :)
202 2013-02-15 17:09:41 <dhill> will keep you posted
203 2013-02-15 17:09:45 <andytoshi> ACTION holds his breath
204 2013-02-15 17:09:59 <gmaxwell> jgarzik: it's nice unless there is another lurking fork creating bug, and then it's not nice. ??? I'm not opposed to it now, but I do think that I'd be opposed to using alerts for it.
205 2013-02-15 17:32:08 <sipa> ;;bc,nethash
206 2013-02-15 17:32:11 <gribble> 26960.757628215793
207 2013-02-15 18:22:52 <dhill> so, if test/wallet_tests.cpp fail .. is that something to be concerned about?
208 2013-02-15 18:23:24 <gmaxwell> Yes.
209 2013-02-15 18:24:13 <dhill> test/wallet_tests.cpp(107): error in "coin_selection_tests": check setCoinsRet.size() == 3 failed [4 != 3]
210 2013-02-15 18:24:16 <dhill> test/wallet_tests.cpp(146): error in "coin_selection_tests": check nValueRet == 18 * CENT failed [19000000 != 18000000]
211 2013-02-15 18:24:19 <dhill> test/wallet_tests.cpp(158): error in "coin_selection_tests": check nValueRet == 11 * CENT failed [14000000 != 11000000]
212 2013-02-15 18:24:22 <dhill> those 3 lines just repeat over and over
213 2013-02-15 18:24:28 <Luke-Jr> BSD?
214 2013-02-15 18:24:31 <dhill> yup
215 2013-02-15 18:27:03 <Luke-Jr> dhill: pretty sure it's known-broken on BSD. interested in becoming the BSD dev? :P
216 2013-02-15 18:27:52 <andytoshi> these are weird bugs.. setCoinsRet.size() should be algorithmically determined, no?
217 2013-02-15 18:28:51 <andytoshi> it's the number of inputs needed to get some value, given a crappy set of availble inputs
218 2013-02-15 18:30:04 <dhill> there are warnings when compiling wallet_tests.cpp
219 2013-02-15 18:30:38 <dhill> comparison between signed and unsigned integer expressions
220 2013-02-15 18:31:42 <dhill> /usr/local/include/boost/test/test_tools.hpp:536: warning: comparison between signed and unsigned integer expressions
221 2013-02-15 18:32:17 <Luke-Jr> dhill: I'd start looking there
222 2013-02-15 18:32:23 <dhill> predicate_result equal_impl( Left const& left, Right const& right )
223 2013-02-15 18:32:23 <dhill> { return left == right;
224 2013-02-15 18:32:23 <dhill> template <class Left, class Right>
225 2013-02-15 18:32:35 <dhill> }
226 2013-02-15 18:32:45 <Luke-Jr> almost certainly the bug is higher-up
227 2013-02-15 18:33:46 <dhill> http://gbpaste.org/Lbj6g
228 2013-02-15 18:34:04 <andytoshi> can you check if sizeof (int64) is 8 on your BSD?
229 2013-02-15 18:34:10 <andytoshi> it is typedeff'd to long long iirc, so it should be
230 2013-02-15 18:34:44 <Luke-Jr> gavinandresen: have you run test_bitcoin on OS X btw?
231 2013-02-15 18:34:49 <Scrat> he was on openbsd/i386 iirc
232 2013-02-15 18:35:05 <Scrat> that combo gotta be 1 in a million :p
233 2013-02-15 18:35:30 <dhill> yes, it is 8
234 2013-02-15 18:35:47 <Luke-Jr> ACTION thinks it's pretty reasonable to expect someone running obscure platforms to submit and support pullreqs to fix them <.<
235 2013-02-15 18:36:59 <andytoshi> at the start of wallet_test.cpp, we have typedef set<pair<const CWalletTx*,unsigned int> > CoinSet;
236 2013-02-15 18:37:38 <dhill> unsigned int is of course 4
237 2013-02-15 18:37:44 <dhill> is that the 4 != 3 ?
238 2013-02-15 18:37:54 <Luke-Jr> ??? no
239 2013-02-15 18:38:33 <andytoshi> no, the .size() is not a datatype size
240 2013-02-15 18:40:05 <dhill> any debug statement i can throw in to see how it gets to 4?
241 2013-02-15 18:40:05 <gavinandresen> Luke-Jr: yes, I run test_bitcoin regularly on my mac
242 2013-02-15 18:40:09 <andytoshi> it is the number elements in the set returned from CWallet::SelectCoinsMinConf in setCoinsRet
243 2013-02-15 18:40:49 <Luke-Jr> dhill: FWIW, the bug is almost certainly in SelectCoinsMinConf
244 2013-02-15 18:41:05 <Luke-Jr> looking at wallet_tests is not really likely to find anything
245 2013-02-15 18:41:23 <dhill> right
246 2013-02-15 18:41:55 <andytoshi> dhill: one sec, i'll throw a patch up
247 2013-02-15 18:41:57 <andytoshi> on pastebin
248 2013-02-15 18:42:00 <dhill> ok
249 2013-02-15 18:43:27 <dhill> make sure it is against 0.7.2
250 2013-02-15 18:43:37 <dhill> or i can figure it out if it isn't
251 2013-02-15 18:44:38 <andytoshi> dhill: yep, i'm doing so
252 2013-02-15 18:44:52 <andytoshi> your line numbers are wrong for git anyway :)
253 2013-02-15 18:45:29 <andytoshi> ..sorry, build is very slow..
254 2013-02-15 18:45:56 <andytoshi> i have new RAM backordered at NCIX
255 2013-02-15 18:47:34 <andytoshi> okay, printf does not work? where is bitcoin_test magic documented?
256 2013-02-15 18:47:44 <andytoshi> oh, i got it, stderr works..
257 2013-02-15 18:51:38 <andytoshi> OK, this is a start..
258 2013-02-15 18:52:11 <andytoshi> diff of wallet.cpp
259 2013-02-15 18:52:17 <andytoshi> http://gbpaste.org/6Ygp4
260 2013-02-15 18:52:34 <andytoshi> but that dumps several hundred lines
261 2013-02-15 18:53:24 <dhill> hmm
262 2013-02-15 18:54:13 <dhill> how do i apply that?
263 2013-02-15 18:54:18 <dhill> i am used to patch
264 2013-02-15 18:54:41 <dhill> git diff
265 2013-02-15 18:54:43 <andytoshi> patch doesn't work?
266 2013-02-15 18:55:09 <andytoshi> oh, right, i can use git..
267 2013-02-15 18:55:28 <dhill> thx
268 2013-02-15 18:56:06 <andytoshi> http://gbpaste.org/JRmfi
269 2013-02-15 18:56:39 <andytoshi> sorry, i was using the 0.72 download, forgot i could just checkout a git tag :}
270 2013-02-15 18:57:25 <dhill> ok, that applied
271 2013-02-15 18:58:37 <andytoshi> alright, i dunno how to make it run that specific line 107 test
272 2013-02-15 19:00:06 <andytoshi> but my RAM just came in, so i'm gonna bike over to NCIX, be back in an hour
273 2013-02-15 19:38:06 <dhill> 104 // try making 34 cents from 1,2,5,10,20 - we can't do it exactly
274 2013-02-15 19:38:09 <dhill> 105 BOOST_CHECK( wallet.SelectCoinsMinConf(34 * CENT, 1, 1, vCoins, setCoinsRet, nValueRet));
275 2013-02-15 19:38:12 <dhill> 106 BOOST_CHECK_GT(nValueRet, 34 * CENT); // but should get more than 34 cents
276 2013-02-15 19:38:15 <dhill> 107 BOOST_CHECK_EQUAL(setCoinsRet.size(), 3); // the best should be 20+10+5. it's incredibly unlikely the 1 or 2 got included (but possible)
277 2013-02-15 19:38:18 <dhill>
278 2013-02-15 19:38:18 <dhill> Insert at line 1129 (coin value ``0.01'')
279 2013-02-15 19:38:18 <dhill> Insert at line 1129 (coin value ``0.05'')
280 2013-02-15 19:38:18 <dhill> Insert at line 1129 (coin value ``0.10'')
281 2013-02-15 19:38:18 <dhill> Insert at line 1129 (coin value ``0.20'')
282 2013-02-15 19:38:21 <dhill> SelectCoins() best subset: 0.20 0.10 0.05 0.01 total 0.36
283 2013-02-15 19:38:33 <dhill>
284 2013-02-15 19:38:38 <dhill> wonder why the 0.01 is in there too
285 2013-02-15 20:07:37 <i2pRelay> <code@i2p> is this like western union
286 2013-02-15 20:11:01 <MC1984> ...no
287 2013-02-15 20:12:47 <i2pRelay> <KillYourTV@i2p> some of the visitors make me sad about humanity..
288 2013-02-15 20:21:40 <i2pRelay> <K1773R@i2p> what a worthless life... waste of organic material
289 2013-02-15 20:22:00 <sipa> ?
290 2013-02-15 20:22:52 <i2pRelay> <K1773R@i2p> these trolls/idiots
291 2013-02-15 20:23:45 <i2pRelay> <KillYourTV@i2p> i was referring to "join <code> is this like western union part"
292 2013-02-15 20:23:57 <i2pRelay> <KillYourTV@i2p> sorry for the noise over there :/
293 2013-02-15 20:24:30 <K1773R> as i said, lets make all the relay chans moderated ;)
294 2013-02-15 20:24:32 <i2pRelay> <KillYourTV@i2p> </ot>
295 2013-02-15 20:25:31 <kytv> t'aint my channels, /me no haz that power
296 2013-02-15 20:25:43 <i2pRelay> <K1773R@i2p> ah well, i forgot we have no OP here
297 2013-02-15 20:25:55 <i2pRelay> <K1773R@i2p> qry
298 2013-02-15 20:25:59 <kytv> ACTION just runs the bot (and hangs his head in shame when the morons come)
299 2013-02-15 20:36:46 <andytoshi> wow! i upgraded my laptop to 4gb RAM and it's twice as fast
300 2013-02-15 20:36:58 <dhill> riiight
301 2013-02-15 20:37:51 <andytoshi> firefox + clang were constantly fighting over the last 100mb of RAM before
302 2013-02-15 20:42:11 <dhill> andytoshi: SelectCoins() best subset: 0.20 0.10 0.05 0.01 total 0.36
303 2013-02-15 20:42:24 <dhill> when testing the 34cents
304 2013-02-15 20:42:34 <dhill> dunno why it adds in that extra 0.01
305 2013-02-15 20:42:40 <dhill> hunting still
306 2013-02-15 20:42:44 <andytoshi> hmm
307 2013-02-15 20:43:43 <K1773R> maybe it needs em to be used as fees?
308 2013-02-15 20:44:06 <andytoshi> K1773R: no, this is in the test suite
309 2013-02-15 20:44:09 <andytoshi> and only dhill is seeing this behavior
310 2013-02-15 20:44:28 <K1773R> ok
311 2013-02-15 20:44:40 <sipa> is there perhaps something wrong with rand()?
312 2013-02-15 20:45:19 <dhill> is there any srand?
313 2013-02-15 20:45:39 <dhill> The rand_r() is a thread-safe version of rand().
314 2013-02-15 20:45:52 <dhill> DESCRIPTION These interfaces are obsoleted by random(3).
315 2013-02-15 20:45:57 <dhill> let me switch it
316 2013-02-15 20:46:30 <andytoshi> it would be nice if we could just seed the RNG in the test suite and that fixed it..
317 2013-02-15 20:46:30 <dhill> sipa: you are talking about rand() in ApproximateBestSubset, right?
318 2013-02-15 20:46:38 <sipa> dhill: yes
319 2013-02-15 20:46:41 <dhill> ok, sec
320 2013-02-15 20:48:54 <andytoshi> but i guess, even with a seed, BSD and linux might do different things
321 2013-02-15 20:51:30 <dhill> um
322 2013-02-15 20:51:33 <dhill> i think it worked
323 2013-02-15 20:51:37 <dhill> no way
324 2013-02-15 20:52:04 <dhill> Insert at line 1102 (coin value ``1.00'')
325 2013-02-15 20:52:04 <dhill> Running 70 test cases...
326 2013-02-15 20:52:06 <dhill> *** No errors detected
327 2013-02-15 20:52:09 <dhill> HAHAHAHA
328 2013-02-15 20:52:11 <dhill> !!!!!!!!!!
329 2013-02-15 20:52:12 <gribble> Error: "!!!!!!!!!" is not a valid command.
330 2013-02-15 20:52:16 <sipa> LOL
331 2013-02-15 20:52:17 <andytoshi> loll
332 2013-02-15 20:52:35 <K1773R> gribble dosnt like u being happy dhill ;)
333 2013-02-15 20:53:21 <andytoshi> dhill: can you post a patch? it would be nice to check on linux and mac
334 2013-02-15 20:53:41 <sipa> you just changed rand() to random()?
335 2013-02-15 20:54:23 <dhill> no, i used openbsd's arc4random .. which is prolly on linux and freebsd and mac.
336 2013-02-15 20:54:28 <dhill> but, let me try with random
337 2013-02-15 20:54:37 <dhill> i think we need to seed
338 2013-02-15 20:54:51 <gmaxwell> I'm still somewhat concerned that the subsetsum is failing on such a trivial problem.
339 2013-02-15 20:54:52 <andytoshi> line 1020? also, don't have a manpage for arc4random here..
340 2013-02-15 20:55:24 <dhill> oh, arc4random on linux is in libbsd .. so we don't want another dependancy
341 2013-02-15 20:55:28 <dhill> let me try random()
342 2013-02-15 20:55:37 <gmaxwell> seems very improbable to me.
343 2013-02-15 20:56:08 <gmaxwell> moreover, changing the random function shouldn't change anything except stir around where the failure happens.. unless rand() is outright broken.
344 2013-02-15 20:56:29 <sipa> gmaxwell: that's my guess, that it returns a constant number or so
345 2013-02-15 20:56:39 <gmaxwell> Yea, that would do it.
346 2013-02-15 20:56:47 <sipa> gmaxwell: turning the "exceptionally unlikely" case into a "always or never"
347 2013-02-15 20:56:53 <dhill> is it seeded anywhere?
348 2013-02-15 20:56:59 <dhill> i don't see an srand() call
349 2013-02-15 20:57:03 <sipa> there is none, no
350 2013-02-15 20:57:21 <gmaxwell> dhill: shouldn't matter.
351 2013-02-15 20:57:32 <andytoshi> random() passes tests over here fwiw
352 2013-02-15 20:57:56 <sipa> on linux, rand and random have the same implementation, afaik
353 2013-02-15 20:57:59 <gmaxwell> can you instrument the test where it fails and print out rand() ?
354 2013-02-15 20:58:20 <gmaxwell> I'm going to guess that your rand() is some busted LCG that always gives even results or something totally insane like that.
355 2013-02-15 20:58:30 <gmaxwell> or maybe gives an even/odd sequence.
356 2013-02-15 20:59:00 <K1773R> random(0, 1) lol
357 2013-02-15 20:59:02 <dhill> so, without the seed, rand() _always_ returns 1103527590 on my machine
358 2013-02-15 20:59:14 <gmaxwell> thats throughly busted.
359 2013-02-15 20:59:36 <dhill> from the manpage
360 2013-02-15 20:59:37 <dhill> If no seed value is provided, the functions are automatically seeded with
361 2013-02-15 20:59:40 <dhill> a value of 1.
362 2013-02-15 20:59:50 <gavinandresen> broken randomness on some platform is a catastrophic, insidiuous, "might not notice it is broken until my coins are gone" problem for bitcoin
363 2013-02-15 20:59:50 <gmaxwell> But in any case, it's not unusual for random functions to be busted.
364 2013-02-15 21:00:09 <gmaxwell> IIRC thats the only place we use the system rand()
365 2013-02-15 21:00:23 <gmaxwell> we don't use the good random because the good random is slow and it makes a visible difference there.
366 2013-02-15 21:00:39 <sipa> dhill: does changing it to random() help?
367 2013-02-15 21:01:04 <dhill> no
368 2013-02-15 21:01:40 <sipa> in that case, i would suggest adding a srand(time()) somewhere in init
369 2013-02-15 21:01:48 <gmaxwell> I suggest we replace that with http://git.xiph.org/?p=opus.git;a=blob;f=tests/test_opus_common.h;h=d1e6b452918ed0e29c8208fcb7682bf174973b49;hb=HEAD#l55 or the KISS99 random, and seed it with the real RNG.
370 2013-02-15 21:01:50 <sipa> oh, and in test_bitcoin
371 2013-02-15 21:02:18 <gmaxwell> sipa: if rand() can return a constant without seeding that must mean it is broken and can go constant in other cases.
372 2013-02-15 21:02:30 <sipa> true
373 2013-02-15 21:02:38 <sipa> that random looks simple enough
374 2013-02-15 21:02:52 <sipa> what period does it have?
375 2013-02-15 21:03:12 <andytoshi> maybe we should write our own shit RNG just to make it consistent?
376 2013-02-15 21:03:26 <dhill> can you use openssl somehow instead?
377 2013-02-15 21:03:31 <andytoshi> we don't need much, and if speed is a concern..
378 2013-02-15 21:03:49 <andytoshi> we've already got an openssl dependency for pretty-much everything else, so that'd be my first response
379 2013-02-15 21:04:11 <sipa> dhill: we do use openssl's random, for almost everything
380 2013-02-15 21:04:14 <sipa> dhill: but it is slow
381 2013-02-15 21:04:31 <gmaxwell> sipa: about 2^60
382 2013-02-15 21:04:52 <sipa> better not initialize it to Rz=0, Rw=0
383 2013-02-15 21:06:50 <gmaxwell> Wikipedia article on that kind of generator: http://en.wikipedia.org/wiki/Multiply-with-carry Main attraction is that they're as fast as LCGs and generally much better.
384 2013-02-15 21:07:59 <dhill> also, not sure if it matters, but rand_r() is for threaded apps
385 2013-02-15 21:08:11 <gmaxwell> dhill: it doesn't matter.
386 2013-02-15 21:08:21 <dhill> linux manpage says
387 2013-02-15 21:08:22 <dhill> If no seed value is provided, the rand() function is automatically seeded with a value of 1.
388 2013-02-15 21:08:26 <dhill> same as openbsd
389 2013-02-15 21:08:40 <gmaxwell> dhill: can you find the source do your openbsd rand() I'm interested to see how they screwed this up. :)
390 2013-02-15 21:09:17 <sipa> the unit test runs (almost) single-threadedly
391 2013-02-15 21:09:34 <dhill> gmaxwell: http://www.openbsd.org/cgi-bin/cvsweb/~checkout~/src/lib/libc/stdlib/rand.c?rev=1.9;content-type=text%2Fplain
392 2013-02-15 21:10:15 <andytoshi> interesting numbers
393 2013-02-15 21:10:29 <dhill> truly random would be to use arc4random
394 2013-02-15 21:10:32 <dhill> but that is bsd
395 2013-02-15 21:10:45 <sipa> that is not truly random
396 2013-02-15 21:10:50 <sipa> just less predictable
397 2013-02-15 21:10:54 <gmaxwell> lol. It's also irrelevant.
398 2013-02-15 21:11:05 <gmaxwell> And I don't see how that code could give a constant result.
399 2013-02-15 21:11:21 <andytoshi> if RAND_MAX is zero somehow..
400 2013-02-15 21:11:33 <andytoshi> though, that should flip 0,1,0,1 then
401 2013-02-15 21:11:40 <dhill> return (*seed % ((u_int)RAND_MAX + 1));
402 2013-02-15 21:11:45 <dhill> seed is 1
403 2013-02-15 21:11:45 <K1773R> dhill there is no random in our universe...
404 2013-02-15 21:11:50 <gmaxwell> dhill: ...
405 2013-02-15 21:11:52 <dhill> yea yea yea yea
406 2013-02-15 21:12:04 <sipa> if RAND_MAX is 0, the output is always zero
407 2013-02-15 21:12:09 <gmaxwell> dhill: The function increments seed. With a seed of 1 it should return
408 2013-02-15 21:12:25 <dhill> ohhh
409 2013-02-15 21:14:08 <gmaxwell> 1103527590 2524885223 662824084 3295386429 4182499122 ... for seed 1.
410 2013-02-15 21:15:01 <jcv> K1773R: not really usable for any reasonable cases, but all you need is radioactive decay and you do have truely random numbers
411 2013-02-15 21:15:23 <andytoshi> dhill: can you use gdb to step into rand()?
412 2013-02-15 21:15:23 <jcv> just saying, there is random in our universe, just probably not something you want to be using
413 2013-02-15 21:15:30 <dhill> oh
414 2013-02-15 21:15:36 <dhill> 1 sec
415 2013-02-15 21:15:45 <K1773R> why should it be random? just because we dont know the rules yet?
416 2013-02-15 21:15:53 <sipa> jcv: whether or not that is random is a philosophical question
417 2013-02-15 21:15:59 <sipa> but it doesn't matter to us
418 2013-02-15 21:16:20 <Luke-Jr> K1773R: it's random as a simple attempt to improve privacy
419 2013-02-15 21:16:22 <gmaxwell> nor to the subset sum algorithim.
420 2013-02-15 21:16:39 <dhill> wait
421 2013-02-15 21:16:41 <Luke-Jr> K1773R: a predictable algorithm would make it more likely someone can deduce your wallet from your transactions
422 2013-02-15 21:16:44 <dhill> you are right
423 2013-02-15 21:16:45 <dhill> for (i = 0; i < 10; i++)
424 2013-02-15 21:16:45 <dhill> printf("%d\\n", rand());
425 2013-02-15 21:16:50 <gmaxwell> Luke-Jr: actually no??? the subset sum algorithim actually only produces good results if the sequence is 'random'.
426 2013-02-15 21:17:26 <gmaxwell> (so independant of private, the rand there needs to be randomish)
427 2013-02-15 21:17:40 <Luke-Jr> gmaxwell: 1,2,3,4 is perfectly valid as a random output :P
428 2013-02-15 21:17:45 <Luke-Jr> or even 1,1,1,1,1
429 2013-02-15 21:18:04 <sipa> 1,1,1,1,1 would result in a very bad subset sum approximation
430 2013-02-15 21:18:14 <andytoshi> Luke-Jr: i think that -is- our output, and it causes a test failure :)
431 2013-02-15 21:18:21 <Luke-Jr> >_<
432 2013-02-15 21:18:22 <K1773R> yes, as i said. there is no random. i dont need a TRNG (hardware based RNG) for BTC anyway, still this wouldnt be random too
433 2013-02-15 21:18:35 <gmaxwell> not just a test failure, but an objectively bad subset sum solution.
434 2013-02-15 21:18:48 <Luke-Jr> K1773R: without some kind of TRNG, you can't practically have a Bitcoin wallet
435 2013-02-15 21:18:55 <Luke-Jr> K1773R: see that embedded wallet fiasco
436 2013-02-15 21:19:28 <K1773R> fiasco? well if you believe/use deprecated stuff its already programmed to happen :P
437 2013-02-15 21:19:42 <Luke-Jr> ACTION ponders if HD wallets "solve" that dependency
438 2013-02-15 21:19:52 <gmaxwell> K1773R: you're confused.
439 2013-02-15 21:19:56 <Luke-Jr> K1773R: deprecated? the problem was solely a lack of TRNG IIRC
440 2013-02-15 21:20:14 <gmaxwell> Luke is talking about signing with constant K values.
441 2013-02-15 21:20:22 <K1773R> ah, well thats stupid
442 2013-02-15 21:20:29 <Luke-Jr> gmaxwell: or even predictable, I'd think
443 2013-02-15 21:20:45 <gmaxwell> K1773R: and openbsd doesn't get to "deprecate" C89.
444 2013-02-15 21:21:10 <sipa> technically, the ECDSA K value can be generated deterministically from Hash(message + privatekey)
445 2013-02-15 21:21:14 <K1773R> wasnt talking about openbsd
446 2013-02-15 21:21:36 <sipa> so combined with deterministic wallets, you can reduce the generation of randomness to just the wallet seed
447 2013-02-15 21:21:56 <sipa> but IANAC, so don't trust me :)
448 2013-02-15 21:22:09 <Luke-Jr> sipa: well, you certainly know better than me :P
449 2013-02-15 21:22:22 <gmaxwell> In any case, we still have a mystery here. The openbsd source pretty clearly can't produce a constant output unless miscompiled.
450 2013-02-15 21:22:29 <Luke-Jr> but either way, you always need a TRNG for the wallet seed
451 2013-02-15 21:22:43 <sipa> what's the T in TRNG?
452 2013-02-15 21:22:47 <Luke-Jr> sipa: True?
453 2013-02-15 21:22:57 <Luke-Jr> ie, non-pseudo
454 2013-02-15 21:23:01 <K1773R> TRNG (hardware based RNG)
455 2013-02-15 21:23:15 <sipa> ideally, sure
456 2013-02-15 21:23:19 <sipa> but you can do without
457 2013-02-15 21:23:34 <Luke-Jr> ???
458 2013-02-15 21:23:46 <K1773R> the T is somewhat stupid, since its not really "True Random"
459 2013-02-15 21:23:56 <Luke-Jr> sipa: without a TRNG, you can't properly seed a PRNG
460 2013-02-15 21:24:10 <sipa> Luke-Jr: apparently people do :)
461 2013-02-15 21:24:15 <gmaxwell> can the random philosophy stuff go elsewhere? I'm going to miss it if dhill figures out why his random is constant.
462 2013-02-15 21:24:15 <Luke-Jr> sipa: who?
463 2013-02-15 21:24:27 <andytoshi> dhill: if you're still here, can you use gdb to step into rand()?
464 2013-02-15 21:24:29 <dhill> no, i am wrong
465 2013-02-15 21:24:33 <dhill> for (i = 0; i < 10; i++)
466 2013-02-15 21:24:33 <dhill> printf("%d\\n", rand());
467 2013-02-15 21:24:33 <sipa> Luke-Jr: afaik, I have no hardware based random number generator
468 2013-02-15 21:24:37 <andytoshi> oh?
469 2013-02-15 21:24:38 <dhill> that prints a different number each time
470 2013-02-15 21:24:43 <Luke-Jr> #bitcoin-mining is idle, move TRNG chat there?
471 2013-02-15 21:24:57 <dhill> but i have no idea why switching rand() to arc4random() makes the tests pass
472 2013-02-15 21:25:18 <andytoshi> dhill: what was that pastie site you used?
473 2013-02-15 21:25:23 <andytoshi> pastebin is blocking my tor node
474 2013-02-15 21:25:26 <dhill> http://gbpaste.org
475 2013-02-15 21:25:42 <midnightmagic> I have a hardware-based random number generator..
476 2013-02-15 21:25:59 <gmaxwell> dhill: how did you get the result that rand was the same every time?
477 2013-02-15 21:27:04 <andytoshi> you can check your RNG is at least uniform with http://gbpaste.org/dKOeK
478 2013-02-15 21:27:06 <sipa> dhill: can you just annotate the rand() in ApproximateSubSetSum, and print out the values it generates?
479 2013-02-15 21:27:09 <andytoshi> well, crudely uniform anyway
480 2013-02-15 21:27:19 <sipa> dhill: for the failing case
481 2013-02-15 21:27:23 <dhill> sec
482 2013-02-15 21:36:17 <gmaxwell> andytoshi: uniform by that metric isn't relevant here.
483 2013-02-15 21:36:53 <gmaxwell> andytoshi: because that rand is a plain LCG over 2^32-1 its outputs will be an even odd sequences.. which is not going to be good for us.
484 2013-02-15 21:37:20 <gmaxwell> There is basically no entropy in the least significant bit, which is the only one we're using.
485 2013-02-15 21:37:28 <andytoshi> ah, gotcha
486 2013-02-15 21:37:35 <gmaxwell> So no??? his rand isn't constant, but its almost as bad.
487 2013-02-15 21:38:17 <andytoshi> well, maybe RAND_MAX is some big prime
488 2013-02-15 21:38:50 <andytoshi> though, the choice of numbers there suggests this RNG was supposed to be flagrantly bad
489 2013-02-15 21:39:01 <andytoshi> to avoid anybody using it unwittingly for secure things
490 2013-02-15 21:39:50 <dhill> #define RAND_MAX 0x7fffffff
491 2013-02-15 21:39:57 <dhill> anyways, let me get the rand() values
492 2013-02-15 21:40:04 <dhill> sorry, had to take a phone call
493 2013-02-15 21:40:10 <gmaxwell> andytoshi: those aren't bad parameters. They'll produce a maximum period output for that kind of generator.
494 2013-02-15 21:40:56 <andytoshi> yeah, i did factor them -- but having a default sequence of 1, 12346, ..., seems like a purposeful indicator, that's all
495 2013-02-15 21:41:18 <gmaxwell> andytoshi: thats not the sequence with a seed of 1.
496 2013-02-15 21:41:51 <gmaxwell> 1103527590 377401575 662824084 1147902781 2035015474 368800899 1508029952 486256185 1062517886 267834847 is...
497 2013-02-15 21:42:04 <andytoshi> oh :P never mind, i'm just illiterate
498 2013-02-15 21:42:24 <gmaxwell> In any case, that RNG will make our subsetsum make the same decisions on every iteration no matter what the seed is when the problem has an even number of coins.
499 2013-02-15 21:42:38 <gmaxwell> so there is no mystery.
500 2013-02-15 21:43:08 <andytoshi> maybe we should just use higher bits to extract entropy then
501 2013-02-15 21:43:33 <gmaxwell> no, we should use the RNG that I linked to or one like it. And never again risk getting screwed by a system RNG.
502 2013-02-15 21:44:02 <andytoshi> yeah, i guess that's for the best
503 2013-02-15 21:44:19 <andytoshi> it's sad that the C standard has those functions and allows things like this, seems like a waste
504 2013-02-15 21:44:41 <gmaxwell> meh, randomness is hard.
505 2013-02-15 21:45:08 <jrmithdobbs> the standard says that rand() isn't required to have the properties crypto systems think a rng should have
506 2013-02-15 21:45:11 <gmaxwell> The mistake here is ours, a LCG is the classic implementation of rand().
507 2013-02-15 21:45:12 <jrmithdobbs> it's pretty straight forward
508 2013-02-15 21:45:21 <gmaxwell> jrmithdobbs: we're not using it in a cryptosystem.
509 2013-02-15 21:47:17 <dhill> ok, so
510 2013-02-15 21:47:20 <jrmithdobbs> gmaxwell: yes, but you were relying on bad assumptions about rand() that you would normally be able to rely on with a cryptographically strong prng
511 2013-02-15 21:47:27 <dhill> rand:1099508847 rand%2:1
512 2013-02-15 21:47:28 <dhill> rand:1070329212 rand%2:0
513 2013-02-15 21:47:28 <dhill> rand:1809127002 rand%2:0
514 2013-02-15 21:47:28 <dhill> rand:1981289989 rand%2:1
515 2013-02-15 21:47:28 <dhill> rand:2049319051 rand%2:1
516 2013-02-15 21:47:30 <dhill> rand:380134760 rand%2:0
517 2013-02-15 21:47:48 <dhill> it is always 0,1,0,1,0,1
518 2013-02-15 21:48:17 <gmaxwell> For some definition of you, :P at least in theory I knew that rand() would do this.
519 2013-02-15 21:48:28 <jrmithdobbs> yes not you as in gmaxwell ;p
520 2013-02-15 21:48:42 <gmaxwell> (well lot of good my hypothetical knoweldge did here)
521 2013-02-15 21:49:03 <sipa> gmaxwell: ACK on putting that 64-bit MWC rand() in bitcoin :)
522 2013-02-15 21:49:14 <gmaxwell> sipa: yea working on a patch.
523 2013-02-15 21:49:57 <dhill> ACTION just happy that is fixed
524 2013-02-15 21:50:01 <dhill> now i can use it :)
525 2013-02-15 21:50:08 <andytoshi> thx for your help dhill
526 2013-02-15 21:50:16 <gmaxwell> sipa: think I should just stick it inside selectcoins?
527 2013-02-15 21:50:26 <gmaxwell> (and seed it every run with the regular rand functions)
528 2013-02-15 21:50:37 <Luke-Jr> why not just use OpenSSL random for selectcoins?
529 2013-02-15 21:50:43 <gmaxwell> because its visibly slow
530 2013-02-15 21:51:00 <Luke-Jr> even if you just use it once to seed rand()? <.<
531 2013-02-15 21:51:03 <andytoshi> i think it should be a separate bitcoin_fast_shit_rand() function, for things like this
532 2013-02-15 21:51:08 <andytoshi> and seeded from openssl on first run
533 2013-02-15 21:51:11 <gmaxwell> Luke-Jr: !@#!@#!@#!@#!@#!
534 2013-02-15 21:51:26 <gmaxwell> Luke-Jr: ahem. I mean. it doesn't matter how you seed it. on dhill's machine it will fail.
535 2013-02-15 21:51:38 <Luke-Jr> gmaxwell: BSD sucks that bad? :P
536 2013-02-15 21:51:45 <gmaxwell> andytoshi: insecure_rand()
537 2013-02-15 21:51:56 <dhill> i'd steal arc4random from libbsd
538 2013-02-15 21:51:58 <gmaxwell> Luke-Jr: the sequence that kind of LCG will produce is even-odd.
539 2013-02-15 21:52:01 <gmaxwell> dhill: NO
540 2013-02-15 21:52:04 <dhill> :)
541 2013-02-15 21:52:07 <sipa> using rand() / (RAND_MAX/2) would also work
542 2013-02-15 21:52:15 <sipa> instead of rand() % 2
543 2013-02-15 21:52:18 <andytoshi> yeah, insecure_rand() is better :P
544 2013-02-15 21:52:18 <gmaxwell> jesus. it's actually important that this one is fast.
545 2013-02-15 21:52:44 <gmaxwell> it gets 1000 * the number of coins in your wallet random numbers per run.
546 2013-02-15 21:52:57 <Luke-Jr> int insecure_rand() { return 6; /* chosen by dice roll, guaranteed to be random */ }
547 2013-02-15 21:53:02 <Luke-Jr> kthx
548 2013-02-15 21:53:09 <sipa> Luke-Jr: xkcd fail; it's 4
549 2013-02-15 21:53:15 <Luke-Jr> sipa: my dice said 6
550 2013-02-15 21:53:21 <dhill> arc4random is extremely fast
551 2013-02-15 21:53:47 <sipa> dhill: still ridiculously slow compared to gmaxwell's MWC
552 2013-02-15 21:53:48 <gmaxwell> dhill: it is three orders of of magnitude slower??? at least??? than the LCG.
553 2013-02-15 21:54:28 <dhill> ok
554 2013-02-15 21:54:33 <sipa> even though it's probably very fast compared to OpenSSL's
555 2013-02-15 21:54:35 <dhill> well, i will look for it and test it out
556 2013-02-15 21:55:26 <jrmithdobbs> gmaxwell: why not just use salsa8 with the privkey of the last used key in the last transaction or if there are none then the newest/last privkey in the memory pool as the key and it's compressed/truncated pubkey as the starting nonce, and it reseeds itself
557 2013-02-15 21:55:54 <sipa> there's really no need for a cryptographic random function here
558 2013-02-15 21:56:02 <sipa> if we need one, use openssl's random
559 2013-02-15 21:56:20 <jrmithdobbs> or chacha8, it's almost as fast as mwc on sse4/neon hardware
560 2013-02-15 21:56:25 <gmaxwell> because of performance reasons one is undesirable. If we are okay with subsetsum being slower??? we should run more iterations, not use a 'better' rng.
561 2013-02-15 21:57:14 <andytoshi> maybe we should use the bits of the input hashes as a RNG :P
562 2013-02-15 21:57:47 <sipa> andytoshi: do not invoke the wrath of Sergio
563 2013-02-15 21:57:51 <jrmithdobbs> gmaxwell: which impl did you link I missed it
564 2013-02-15 21:58:15 <Luke-Jr> sipa: lol
565 2013-02-15 21:58:18 <andytoshi> http://git.xiph.org/?p=opus.git;a=blob;f=tests/test_opus_common.h;h=d1e6b452918ed0e29c8208fcb7682bf174973b49;hb=HEAD#l55
566 2013-02-15 21:58:55 <Luke-Jr> sipa: as unimportant as some of his exploits might seem at times, I think Sergio is an important part of the team ;)
567 2013-02-15 21:59:04 <sipa> agree
568 2013-02-15 22:07:03 <gmaxwell> andytoshi: I think I'm going to opt against insecure_rand() simply because the requirements for an insecure_rand() could be pretty application specific, and right now this is the only one I'm aware of in the codebase.
569 2013-02-15 22:08:13 <andytoshi> yeah, that's a good point
570 2013-02-15 22:12:06 <gmaxwell> https://people.xiph.org/~greg/random.patch but I wonder if I shouldn't just make it constant instead of rand_bytes seeded.
571 2013-02-15 22:15:47 <andytoshi> IMHO constant
572 2013-02-15 22:15:52 <gmaxwell> sipa: your opinion on just making the random sequence constant for every run of ApproximateBestSubset? it would make the tests more determinstic.
573 2013-02-15 22:16:50 <sipa> gmaxwell: for unit tests that makes sense; for actual usage i'm less sure
574 2013-02-15 22:17:08 <sipa> gmaxwell: as Luke-Jr said, there is a chance that it reveals something about your wallet
575 2013-02-15 22:17:25 <gmaxwell> IIRC the inputs to approximate best subset are already securely randomly ordered, no?
576 2013-02-15 22:17:30 <gmaxwell> ACTION checks
577 2013-02-15 22:18:08 <sipa> they're sorted from low to high
578 2013-02-15 22:18:15 <gmaxwell> yea, okay. right.
579 2013-02-15 22:18:18 <gmaxwell> fine enough.
580 2013-02-15 22:19:05 <sipa> before the ApproximateSubSetSum refactor/rewrite by dooglus, they were randonly ordered i think
581 2013-02-15 22:19:17 <bitmarco> 16:51 < Luke-Jr> gmaxwell: BSD sucks that bad? :P
582 2013-02-15 22:19:19 <bitmarco> haha
583 2013-02-15 22:19:25 <bitmarco> linux doesnt suck at all!
584 2013-02-15 22:20:05 <sipa> iirc, the algorithm used is a very traditional PRNG algorithm, and there's even a traditional advise not to rely on its low-order bits :)
585 2013-02-15 22:21:52 <gmaxwell> yea, this behavior is well know.. hasn't stopped it from causing a lot of problems. (google for TCP ISN prediction)
586 2013-02-15 22:52:50 <Luke-Jr> bitmarco: I'm no fanboy; there are many ways Linux (and GNU) sucks, but still..
587 2013-02-15 22:55:29 <gmaxwell> Luke-Jr: Apparently Linux (really GLIBC) sucks because it made its rand() unusually good, and as a result we got away with non-portable code. :P
588 2013-02-15 23:00:24 <midnightmagic> ..!
589 2013-02-15 23:00:58 <gmaxwell> hm?
590 2013-02-15 23:01:12 <midnightmagic> Where's the use of srand?
591 2013-02-15 23:01:26 <gmaxwell> There isn't one, and doesn't need to be one.
592 2013-02-15 23:01:49 <Luke-Jr> gmaxwell: would be nice if glibc were more standards-only and gnulib were available as a shared object
593 2013-02-15 23:02:22 <gmaxwell> And use of srand would not have mattered for the case being discussed. :P
594 2013-02-15 23:10:44 <midnightmagic> gmaxwell: This is a subset-finding issue on platforms that don't have Linux' rand(), correct? wallet.cpp:986 ?
595 2013-02-15 23:14:11 <gmaxwell> midnightmagic: the particular degenerate behavior would happen on anything using one of the common LCG implementations of rand(). Persumably there could even be linux systems meeting this description (e.g. libc5 ones).
596 2013-02-15 23:15:43 <andytoshi> could be newlib or whatever android uses as well
597 2013-02-15 23:15:51 <midnightmagic> gmaxwell: Deterministic subset-finding it doesn't seem to me would be much of an issue.
598 2013-02-15 23:16:33 <gmaxwell> midnightmagic: I'm not sure I understand?
599 2013-02-15 23:16:34 <andytoshi> midnightmagic: naively, it would be exponential complexity
600 2013-02-15 23:17:38 <andytoshi> midnightmagic: this is (almost) the classic optimization "knapsack problem"
601 2013-02-15 23:18:11 <gmaxwell> (I mean I don't understand if you're saying you don't know why there would have been an issue in the first place (which is what andy seems to have read); or if you were agreeing with my suggestion to just use a constant random sequence.)
602 2013-02-15 23:18:59 <midnightmagic> I'm saying it seems to me it wouldn't matter if rand() were returning random numbers, or just numbers. Like who cares if it's random or not for that specific function?
603 2013-02-15 23:19:50 <gmaxwell> midnightmagic: ha. Somehow you failed to clarify things for me!
604 2013-02-15 23:19:59 <gmaxwell> I still don't know which of those two things you're talking about.
605 2013-02-15 23:20:19 <andytoshi> midnightmagic: the optimization process searches a small subset of the space, and needs a random nudge to keep moving
606 2013-02-15 23:20:36 <andytoshi> and these are binary nudges, 0 or 1...
607 2013-02-15 23:21:00 <andytoshi> and our bad RNG would alternate these, so for an even number of inputs it wouldn't accomplish anything new with each pass
608 2013-02-15 23:21:35 <midnightmagic> I understand that BSD rand() is weird and shitty, and Linux' isn't. From my reading of the function, who cares if it's properly random or not? It doesn't seem to me to be a security or even an algorithmic *flaw* such that I, for example, magically give up the fact I'm running on BSD or I am part of a subset of BSD-using people.
609 2013-02-15 23:22:32 <midnightmagic> gmaxwell: Not the first one. I am agreeing with your second statement. Yes, right.
610 2013-02-15 23:22:36 <midnightmagic> aaargh lagged
611 2013-02-15 23:22:53 <andytoshi> np, i've been having 30-60 second drops all day..
612 2013-02-15 23:23:15 <gmaxwell> yea, it doesn't matter. So long as it's not so simplistic that the algorithim gets stuck.
613 2013-02-15 23:24:15 <gmaxwell> midnightmagic: luke and sipa's point was that if it's totally determinstic that it does potentially leak more data about the composition of coins in your wallet.
614 2013-02-15 23:24:52 <midnightmagic> hrm..
615 2013-02-15 23:25:30 <gmaxwell> though it's sort of an insane corner case??? most of the time the result doesn't depend on the random sequence at all.
616 2013-02-15 23:25:42 <gmaxwell> (or at least with unique values it doesn't)
617 2013-02-15 23:26:13 <andytoshi> sipa mentioned a "refactor/rewrite by dooglus", before which he thought the inputs had been randomly ordered
618 2013-02-15 23:26:19 <andytoshi> was the algorithm deterministic then?
619 2013-02-15 23:26:45 <gmaxwell> IIRC it called the openssl rand then.
620 2013-02-15 23:27:30 <gavinandresen> can I get a quick ACK or two on: https://github.com/bitcoin/bitcoin/pull/2311
621 2013-02-15 23:27:42 <midnightmagic> I guess in the odd case where I'm confounded with a Linux-user then, the subselect if it did come down to the rand() being predictable might be another line between me and the other confounding identity..
622 2013-02-15 23:28:59 <midnightmagic> I'm pretty sure the fact I use raw transactions everywhere is already doing a good job of giving me away though..
623 2013-02-15 23:29:44 <midnightmagic> gmaxwell: Kind of a neat problem, thanks.
624 2013-02-15 23:30:03 <Luke-Jr> gavinandresen: I'll test it here.. 1 sec
625 2013-02-15 23:30:04 <andytoshi> i thought it was really cool
626 2013-02-15 23:30:27 <dhill> uname -a
627 2013-02-15 23:30:40 <dhill> oops
628 2013-02-15 23:30:44 <gmaxwell> midnightmagic: say you produce two transactions one after another. The first uses inputs q,w,e,r,t the second uses inputs a,s,d then there is a third third transaction which uses z,x,c with a deterministic algorithm I can say that z,x,c is not you because if z,x,c had been in your wallet you would have used its inputs in an earlier transaction.
629 2013-02-15 23:31:15 <gavinandresen> gmaxwell: RE: rand() replacement: ACK on the algorithm, although I think the code should be in an insecure_rand() method in util.h, so it is slightly less likely new code that needs a fast rand() won't just use rand() and bring back a similar bug
630 2013-02-15 23:31:26 <Luke-Jr> gavinandresen: db/builder.cc:5:24: fatal error: db/builder.h: No such file or directory
631 2013-02-15 23:31:37 <gmaxwell> gavinandresen: yea, I wasn't sure there. Mostly fine either way.
632 2013-02-15 23:31:57 <gavinandresen> Luke-Jr: can you pastebin your make?
633 2013-02-15 23:32:32 <midnightmagic> gmaxwell: Hence the line between me and the Linux-user. So I guess in the worst case it does help collapse identities. Really neat portability problem. Windows is also secure-ish?
634 2013-02-15 23:32:51 <Luke-Jr> gavinandresen: that's building bitcoind without Bitcoin-Qt
635 2013-02-15 23:32:53 <Luke-Jr> make -f makefile.unix BDB_INCLUDE_PATH=/usr/include/db4.8/ CXXFLAGS="-O0" DEBUGFLAGS='-ggdb' USE_DBUS=1 USE_QRCODE=1 USE_SSL=1 LDFLAGS="" USE_IPV6=1 USE_UPNP=- -j4 bitcoind test_bitcoin
636 2013-02-15 23:33:30 <Luke-Jr> gavinandresen: if I build Bitcoin-Qt first, it works since bitcoind reuses leveldb.a
637 2013-02-15 23:33:42 <midnightmagic> dhill: NetBSD ra 5.1.2_PATCH NetBSD 5.1.2_PATCH (ra-new) #1: Mon Dec 20 20:28:06 PST 2012 root@build:/usr/src/sys/arch/i386/compile/ra-new i386 :-)
638 2013-02-15 23:34:44 <Luke-Jr> gavinandresen: I think you need to tell leveldb's makefile to ignore environment CXXFLAGS
639 2013-02-15 23:34:56 <gmaxwell> midnightmagic: uh. What a great! question.
640 2013-02-15 23:35:21 <Luke-Jr> (I'm not sure quite how to do that..)
641 2013-02-15 23:35:29 <gavinandresen> Luke-Jr: ??? or you need to set your CXXFLAGS to include the leveldb -I's
642 2013-02-15 23:35:36 <gmaxwell> midnightmagic: get this: rand() and mingw32 here: 41 18467 6334 26500 19169 15724 11478 29358 26962 24464
643 2013-02-15 23:35:47 <gmaxwell> midnightmagic: so??? this means that windows is broken too!
644 2013-02-15 23:35:54 <gmaxwell> ACTION facepalm
645 2013-02-15 23:35:54 <midnightmagic> gmaxwell: Awesome.
646 2013-02-15 23:36:01 <Luke-Jr> gavinandresen: that's not a reasonable expectation; users shouldn't need to know how the build works internally
647 2013-02-15 23:37:08 <gavinandresen> Luke-Jr: I really don't like the edit-every-other-line-of-somebody's-upstream-Makefile solution, that's fragile
648 2013-02-15 23:37:09 <gmaxwell> midnightmagic: so now I want to know why no one has run test_bitcoin on windows.
649 2013-02-15 23:37:34 <andytoshi> i bet test_bitcoin would've still worked, the ones' bit doesn't alternate
650 2013-02-15 23:37:38 <Luke-Jr> gavinandresen: yeah, I agree.
651 2013-02-15 23:38:28 <gavinandresen> ??? could do: unset CFLAGS CXXFLAGS && $(MAKE) ???etc???.
652 2013-02-15 23:38:28 <gmaxwell> andytoshi: apparently I'm being a bit blond today, I only looked at the first three values. :)
653 2013-02-15 23:39:20 <midnightmagic> gmaxwell: or OS/X.. :-/ yikes. Pretty cool how the test suite just proved itself again though.
654 2013-02-15 23:39:39 <gmaxwell> midnightmagic: it's apparently fine on OSX.
655 2013-02-15 23:39:57 <midnightmagic> that's surprising.
656 2013-02-15 23:40:03 <Luke-Jr> gavinandresen: hmm, that should work, but doesn't seem to. I'll dig around more
657 2013-02-15 23:40:26 <andytoshi> gmaxwell: having said that, having a 32K range is pretty bad
658 2013-02-15 23:41:28 <andytoshi> midnightmagic: yeah, i was impressed that we found a RNG problem with a test suite
659 2013-02-15 23:43:10 <gavinandresen> speaking of which, util_tests.cpp should test the openssl-based GetRand() methods for some level of sanity.
660 2013-02-15 23:44:16 <Luke-Jr> gavinandresen: make is sneaking them in via MAKEFLAGS env :/
661 2013-02-15 23:46:45 <gavinandresen> So??? for now I think we should recommend using DEBUGFLAGS instead of CXXFLAGS to build. After 0.8 I think we should have a make-the-makfiles-sane-again party.
662 2013-02-15 23:47:03 <gavinandresen> Or maybe the configure project will get done....
663 2013-02-15 23:48:00 <jaakkos> whose branch (block) is preferred if two blocks are generated at the same height?
664 2013-02-15 23:48:08 <gavinandresen> mine
665 2013-02-15 23:48:19 <gmaxwell> jaakkos: the first you heard.
666 2013-02-15 23:48:32 <gmaxwell> "you only switch to a longer chain"
667 2013-02-15 23:48:39 <Luke-Jr> lol
668 2013-02-15 23:48:40 <jaakkos> gmaxwell: ok, why not smallest hash?
669 2013-02-15 23:48:51 <gmaxwell> jaakkos: because that would hurt convergence.
670 2013-02-15 23:49:08 <Luke-Jr> gavinandresen: MAKEOVERRIDES='' $(MAKE) ??? <-- works
671 2013-02-15 23:49:16 <gavinandresen> smallest hash would give miners an incentive to keep mining on the older block
672 2013-02-15 23:49:19 <Luke-Jr> I think, build almost finished but usually it errors sooner
673 2013-02-15 23:49:48 <gavinandresen> ACTION wonders what the heck is MAKEOVERRIDES, goes to look???.
674 2013-02-15 23:50:13 <jaakkos> gmaxwell: hmm, makes sense
675 2013-02-15 23:50:57 <Luke-Jr> yep, build finished
676 2013-02-15 23:51:02 <gavinandresen> Luke-Jr: ah, great, MAKEOVERRIDES is exaclty what we want
677 2013-02-15 23:51:34 <Luke-Jr> hrm
678 2013-02-15 23:51:41 <Luke-Jr> clean and retry fails now
679 2013-02-15 23:51:44 <Luke-Jr> ACTION scratches head
680 2013-02-15 23:52:33 <Luke-Jr> oh, I guess it can't be part of the command itself
681 2013-02-15 23:52:54 <Luke-Jr> http://codepad.org/FI4mj6mX
682 2013-02-15 23:54:10 <Luke-Jr> not sure we want to be passing all xCXXFLAGS down (like -DUSE_UPNP=*), but it doesn't seem to hurt
683 2013-02-15 23:54:46 <Luke-Jr> re makefile party, hopefully CodeShark's automake stuff will make that easier ;)
684 2013-02-15 23:55:49 <andytoshi> i bet CodeShark has thrown his computer out by now
685 2013-02-15 23:55:58 <Luke-Jr> >_<
686 2013-02-15 23:56:02 <CodeShark> lol
687 2013-02-15 23:56:24 <gavinandresen> Luke-Jr: pushed MAKEOVERIDES fix to
688 2013-02-15 23:56:34 <gavinandresen> ??? to the pull request
689 2013-02-15 23:57:01 <Luke-Jr> gavinandresen: retesting
690 2013-02-15 23:59:55 <Luke-Jr> bitcoind-only build success