1 2014-08-11 01:06:37 <BlueMatt> ahmed_: yep, thats me
2 2014-08-11 01:24:33 <ahmed_> BlueMatt: any advicr/help on starting my own ppa
3 2014-08-11 01:27:34 <BlueMatt> ahmed_: why?
4 2014-08-11 01:29:41 <ahmed_> BlueMatt: mainly just incase you stop coming out with new versions and because I have a personal copy of bitcoind with sn empty testnet to save me redownloading always so a ppa makes it easier for me
5 2014-08-11 01:29:50 <ahmed_> When spinning up vms
6 2014-08-11 01:30:26 <BlueMatt> meh, up until the latest release the ~bitcoin ppa has been up-to-date within a day or so of release
7 2014-08-11 01:30:49 <BlueMatt> and its officially supported, so that should continue to be the case
8 2014-08-11 01:31:01 <ahmed_> BlueMatt: yeah thats just one of the reasons tho like I said
9 2014-08-11 01:31:04 <BlueMatt> ofc if you really want your own, just copy contrib/debian to debian and use standard debian release tools
10 2014-08-11 01:31:22 <ahmed_> Okay thanks :)
11 2014-08-11 01:31:42 <BlueMatt> ofc if you're doing this because you want your own, I highly recommend against a ppa (using launchpad) and suggest you run your own
12 2014-08-11 01:31:52 <BlueMatt> or make your own .deb via debuild and then scp it around
13 2014-08-11 01:32:04 <BlueMatt> because that would be much more secure than trusting launchpad's build infrastructure
14 2014-08-11 01:32:13 <ahmed_> Ahh not too bad of an idea
15 2014-08-11 01:32:19 <ahmed_> Much easier too
16 2014-08-11 01:32:41 <ahmed_> Thanks :)
17 2014-08-11 01:40:15 <Luke-Jr> did we break boost compat? why is https://gist.github.com/janx/10465121 telling people to build their own boost? :/
18 2014-08-11 01:42:23 <BlueMatt> maybe its useless?
19 2014-08-11 01:42:28 <BlueMatt> have you asked janx?
20 2014-08-11 01:45:24 <Luke-Jr> dunno who janx is :P
21 2014-08-11 04:14:56 <iwilcox> Sorry to repeat, but is there an obvious explanation for why higher mem use caused by higher checkblocks/checklevel should persist past the initial check?
22 2014-08-11 04:15:05 <iwilcox> http://0bin.net/paste/TJFBbprrUO7rPV8Y#iDuZBJa2KCD9FckfPhONUD2TBcfccgK+aoCg3CsSAs0
23 2014-08-11 04:16:23 <iwilcox> cb=200 ran into bad_alloc @~450s so might not be representative. I'm just thinking that if it's cached, I wouldn't be triggering bad_allocs because bitcoind would just throw something out.
24 2014-08-11 04:18:03 <iwilcox> Maybe if I just let cb=25 run for hours it'd eventually climb to RSS ~500k anyway.
25 2014-08-11 04:19:15 <iwilcox> That was with addrindex but Amphibian got very similar numbers without: http://pastebin.ubuntu.com/8013660/
26 2014-08-11 04:19:55 <gmaxwell> iwilcox: wrt throw something out, absolutely not.
27 2014-08-11 04:21:51 <gmaxwell> iwilcox: basically all 'general computer' software is written assuming that the computer has infinite memory/swap. There may be _some_ facility for handling a failed allocation, but those code paths often don't work rightâ worse on many operating systems the system overcommits, allocations will be successful even if there isn't enough memoryâ and then only when you try to write to some of that allocation will the OS tell you (by ...
28 2014-08-11 04:21:57 <gmaxwell> ... killing the process)
29 2014-08-11 04:22:36 <Luke-Jr> (or killing another unrelated process)
30 2014-08-11 04:23:07 <gmaxwell> (the reason for overcommit is because there are many cases where a process may reasonably allocate a bunch of additional memory that it doesn't need, never write to it, and drop it later. The canonical example being the whole extra copy of the current process when you fork() only to throw it out a moment later when you exec())
31 2014-08-11 04:23:29 <iwilcox> Sure. Makes sense, overoptimistic of me :)
32 2014-08-11 04:24:59 <gmaxwell> (personallyâ having spent too much time working on codecs and realtime systemsâ I like to write software where the memory usage is determinstic, allocated all up frontâ so no surprises. Unfortunately, thats not compatible with the "safe C++" style that uses dynamically allocated container objects everywhere)
33 2014-08-11 04:25:38 <iwilcox> So what's the determining factor for a bitcoind instance?
34 2014-08-11 04:25:58 <gmaxwell> iwilcox: determining what factor?
35 2014-08-11 04:26:14 <iwilcox> Memory use doesn't just grow, unbounded.
36 2014-08-11 04:27:44 <iwilcox> bitcoind is stable at ~0.5G, but presumably if there's no inbuilt cap on use then it depends on some aspect of the chain or mempool or something.
37 2014-08-11 04:28:04 <gmaxwell> There is no cap though nothing that grows over time uses much memory.
38 2014-08-11 04:29:22 <gmaxwell> most of the usage is death by 100 cuts. Every thread uses an 8mb for stack plus some amount of per-thread heap thats allocated to it. A lot of this isn't mapped in until its used, but if its used once it doesn't get released. At startup checkblocks checks the database in a very sound way by undoing a bunch of recent blocks and redoing them (like a reorg), it does this in memory to avoid writing anything to disk, this creates a memory ...
39 2014-08-11 04:29:28 <gmaxwell> ... usage peak, for some reason not all of this gets released (there may be some fragmentation contributing to that).
40 2014-08-11 04:30:12 <gmaxwell> now that we don't have huge per-peer buffers there really isn't a reason for bitcoind to be using a bunch of ram, just no one has successfully tracked down the main depynessnesses.
41 2014-08-11 04:31:39 <gmaxwell> Malloc profiling only explains about half the allocations, and a lot of what it does explain is things like the per-thread overheads which can be reduced with some amount of work. The unexplained parts are unclear.
42 2014-08-11 04:33:21 <iwilcox> OK, probably no easy gains then. I'm just looking at this from the PoV of "how long can this hardware keep running a node", generally.
43 2014-08-11 04:35:26 <iwilcox> sipa said on bitcointalk "The primary reason for -checkblocks ... is preventing accidental disk corruption of the block chain file, which could result in rejecting the best chain."
44 2014-08-11 04:35:49 <iwilcox> How would that happen? How would the check prevent that?
45 2014-08-11 04:36:11 <iwilcox> Just wondering what I'd be trading off by less thorough/less deep checks.
46 2014-08-11 05:23:23 <wumpus> iwilcox: during the checkblocks two CCoinsViewCaches grow to enormous size
47 2014-08-11 05:24:27 <wumpus> iwilcox: one of those is released immediately after, but the other (pcoinsTip) persists for a while, until it is flushed at some point, probably in WriteChainState
48 2014-08-11 05:24:46 <iwilcox> What triggers that flush?
49 2014-08-11 05:25:14 <wumpus> if (pcoinsTip->GetCacheSize() > nCoinCacheSize || (!IsInitialBlockDownload() && GetTimeMicros() > nLastWrite + 600*1000000))
50 2014-08-11 05:25:27 <wumpus> src/main.cpp, line 1869
51 2014-08-11 05:26:24 <iwilcox> So at least every 10m?
52 2014-08-11 05:27:31 <wumpus> anyhow the initial growth is what causes memory usage, this could be becuase lots of little records are being allocated, so the memory space gets fragmented, which makes it harder to return to the OS
53 2014-08-11 05:28:32 <wumpus> one solution would be to limit the size of a CCoinsViewCache w/ a mru cache, for example
54 2014-08-11 05:30:10 <wumpus> but I noticed it too, the coinsviewcache is what causes the large memory usage, after loading the block index only ~80MiB of heap is used, during the check it's ~500MiB, and afterwards about ~250
55 2014-08-11 05:32:15 <wumpus> so you can save a lot of memory on a stable node by reducing the checkblocks size
56 2014-08-11 05:32:48 <wumpus> on a node that is reindexing the ccoinsviewcache will never hit that size due to the regular flush
57 2014-08-11 05:37:07 <wumpus> nCoinsCacheSize is 5000, which is supposed to be a limit, the actual size that those monsters grow to is 77711 and 157546
58 2014-08-11 05:40:39 <iwilcox> So what's the risk introduced by tuning checkblocks down? I don't quite grasp what sipa is saying in that quotation above.
59 2014-08-11 05:41:08 <wumpus> the 77k one is pCoinsTip, it will get a BatchWrite() at some point, which possibly will generate a very large leveldb batch (I haven't verified this, though)
60 2014-08-11 05:41:28 <iwilcox> A previous instance crashes out, trashes only recent blocks but <checkblocks, ...?
61 2014-08-11 05:44:44 <wumpus> a previous instance may not have processed recent blocks yet or updated the database for them
62 2014-08-11 05:48:08 <fr0sty> hey guys, i have a question about bitcoin mining, can anyone help me out?
63 2014-08-11 05:48:33 <iwilcox> Try #bitcoin-mining, but start by asking the actual question!
64 2014-08-11 05:48:43 <fr0sty> thanks!
65 2014-08-11 05:52:49 <wumpus> cfields: I didn't do that yet; I've been mostly focused on the ccoinsviewcaches issue, so I don't need that level of type detail yet
66 2014-08-11 05:56:07 <sipa> iwilcox, wumpus, gmaxwell: the memory intensive part of checkblocks (level 3 and 4) are only done as far as the coin cache size allows
67 2014-08-11 05:56:46 <sipa> which is limited in terms of how many txid entries, not in bytes (it uses some fixed conversion rate between them)
68 2014-08-11 05:56:57 <wumpus> sipa: well the stages before that seem plenty memory intentive as well
69 2014-08-11 05:57:06 <sipa> huh?
70 2014-08-11 05:57:17 <sipa> that shouldn't be
71 2014-08-11 05:57:24 <wumpus> please read back
72 2014-08-11 05:57:28 <sipa> they just load blocks from disk and throw them away
73 2014-08-11 05:57:29 <sipa> ok
74 2014-08-11 05:58:07 <wumpus> during the check there are two coinsview caches, one grows to 77k and one to 157k
75 2014-08-11 05:58:16 <wumpus> (entries)
76 2014-08-11 05:58:27 <wumpus> this is about 500MiB of memory
77 2014-08-11 05:58:53 <sipa> yes, but that is all because of chrcklevel 3
78 2014-08-11 05:58:59 <sipa> ot should be
79 2014-08-11 05:59:35 <sipa> if you set -dbcache higher or lwer, checklevel 3 and 4 will be performed for more or less blocks
80 2014-08-11 05:59:57 <sipa> for as many transactions as fit in the coin cache limit
81 2014-08-11 06:00:49 <wumpus> I'll try with checklevel=2
82 2014-08-11 06:01:29 <sipa> level 1 and 2 are indepdent consistency checks for blocks
83 2014-08-11 06:01:43 <sipa> level 3 is a rollback of the chainstate in memory
84 2014-08-11 06:01:55 <wumpus> but my tests above were all at the default checklevel and checkblocks as well as dbcache size, so maybe one of those should be toned down a bit
85 2014-08-11 06:02:40 <sipa> no, the conversion between dbcache and number of ccoins entries is probably off
86 2014-08-11 06:02:57 <sipa> level3 rolls back until the coin cache is full
87 2014-08-11 06:03:21 <sipa> (and not more than -checkblocks says)
88 2014-08-11 06:03:56 <iwilcox> So level 3 is constrained but the level 2 checks always go back by <checkblocks>?
89 2014-08-11 06:04:01 <sipa> yes
90 2014-08-11 06:04:05 <wumpus> maybe it forgets that there are two coin caches being filled up?
91 2014-08-11 06:04:50 <sipa> wumpus: one is the 'master' coin cache pcoinsTip, which is backed by the database - reading things from it will cause the cache to grow
92 2014-08-11 06:05:08 <sipa> the other is one in which all modifications are made
93 2014-08-11 06:05:25 <wumpus> ok, indeed, with checklevel=2 the total heap usage stays at 77MiB after the blocks verification
94 2014-08-11 06:05:46 <sipa> so the first has all original coins entries, the second has all the changed ones due to the rollback
95 2014-08-11 06:06:04 <sipa> iirc, the second one's size (in nunber of entries) is constrained
96 2014-08-11 06:06:15 <sipa> as it's always larger than the first one
97 2014-08-11 06:06:22 <wumpus> yes it's about twice as large
98 2014-08-11 06:06:54 <sipa> ideally, caches would account for their size accurately
99 2014-08-11 06:06:59 <iwilcox> The fact that there are so many levels and it's seen as worth doing at every start, tells me I'm still missing something about how easily this should be spotting problems.
100 2014-08-11 06:07:19 <iwilcox> "a previous instance may not have processed recent blocks yet or updated the database for them" â under what sort of circumstances?
101 2014-08-11 06:07:31 <sipa> a crash
102 2014-08-11 06:07:35 <wumpus> iwilcox: when it crashes!
103 2014-08-11 06:07:39 <wumpus> like in any database program
104 2014-08-11 06:08:28 <sipa> wumpus: the check shoukd probably be done on pcoinsTip->size + the size of the roll back cache
105 2014-08-11 06:08:38 <sipa> but that won'y change that much
106 2014-08-11 06:08:39 <wumpus> the fact that it runs is not a problem, but it should probably use less memory
107 2014-08-11 06:09:30 <sipa> we could do a flush on pcoinstip after the consistency check to make it release the memory ut used
108 2014-08-11 06:09:41 <iwilcox> What point could bitcoind crash at that had hundreds of blocks unprocessed?
109 2014-08-11 06:09:50 <wumpus> sipa: btw will the flush write all those touched records to disk?
110 2014-08-11 06:10:01 <sipa> but that's just temporary... it shouldn't change peak usage
111 2014-08-11 06:10:14 <sipa> wumpus: yes, which is why it needs to get dirtyness tracking
112 2014-08-11 06:10:28 <wumpus> then it builds a 77k leveldb batch :(
113 2014-08-11 06:10:29 <sipa> so undirty old records can judt be deleted rather than written
114 2014-08-11 06:10:45 <sipa> it *always* builds such a batch when flushing
115 2014-08-11 06:10:50 <wumpus> 77k entires that is... leveldb builds huge std::strings internally
116 2014-08-11 06:11:04 <sipa> not only after checkblocks
117 2014-08-11 06:11:08 <sipa> yes, i kbow
118 2014-08-11 06:11:22 <sipa> i've been planning to improve that cache behavior since forever
119 2014-08-11 06:11:38 <wumpus> but always that size?
120 2014-08-11 06:11:44 <sipa> yes
121 2014-08-11 06:11:49 <wumpus> nCoinCacheSize defaults to 5000, so I expected it to be more around that
122 2014-08-11 06:11:59 <sipa> ugh, wait
123 2014-08-11 06:12:22 <sipa> nCoinCacheSize defaults to some formula based off dbcache
124 2014-08-11 06:12:23 <wumpus> that's just the default in the source code though, it is updated in init
125 2014-08-11 06:12:28 <wumpus> yes
126 2014-08-11 06:12:35 <sipa> yes, ignore that static defauly
127 2014-08-11 06:14:04 <sipa> pcoinsTip should not grow in number of entries over nCoinCacheSize
128 2014-08-11 06:14:22 <sipa> and whenever it does reach that, the entire cache is flushed
129 2014-08-11 06:14:52 <sipa> which is silly, as the entries could be kept, but in a nondirty state that allows them to be removed from the cache without risk
130 2014-08-11 06:16:19 <wumpus> nCoinCacheSize is 171267
131 2014-08-11 06:16:33 <wumpus> okay, that explains something
132 2014-08-11 06:17:49 <wumpus> my rough computations says that the memory usage per coin is more like 2000 bytes than 300
133 2014-08-11 06:18:18 <wumpus> (based on the total extra memory usage during the check)
134 2014-08-11 06:18:40 <sipa> strange that it seems to work fine duting sync
135 2014-08-11 06:20:40 <sipa> oh it does use both cache sizes
136 2014-08-11 06:20:51 <wumpus> indeed, during the sync the behavior is ok
137 2014-08-11 06:20:59 <sipa> but limits them to "2 * nCoinsCacheSize + 32000"
138 2014-08-11 06:21:06 <wumpus> up until now I always did memory profiling while reindexing so I never noticed this
139 2014-08-11 06:21:40 <sipa> let's just start by changing that to nCoinsCacheSize
140 2014-08-11 06:21:51 <wumpus> ok!
141 2014-08-11 06:25:28 <wumpus> profiling...
142 2014-08-11 06:26:44 <BlueMatt> hmm...making a shared library exposing a useful VerifyScript was easier than I thought
143 2014-08-11 06:28:17 <BlueMatt> ofc it weighs 10x what it should, but for minimal code-moving its not bad
144 2014-08-11 06:28:47 <wumpus> BlueMatt: yeah, usefulness is a much bigger concern here
145 2014-08-11 06:29:07 <BlueMatt> it exposes a VerifyScript that only takes byte arrays (and does deserialization itself)
146 2014-08-11 06:29:09 <BlueMatt> so its useful
147 2014-08-11 06:29:23 <wumpus> that's also how I imagined it
148 2014-08-11 06:29:36 <sipa> cool
149 2014-08-11 06:29:47 <BlueMatt> ACTION plans to hack bitcoinj to use it tomorrow
150 2014-08-11 06:29:55 <BlueMatt> and then clean up the code moves and pull req
151 2014-08-11 06:30:10 <BlueMatt> https://github.com/TheBlueMatt/bitcoin/tree/libscript
152 2014-08-11 06:30:51 <wumpus> passing around only byte arrays on the interface avoids the discussion about what should be exposed on the interface
153 2014-08-11 06:31:00 <BlueMatt> indeed
154 2014-08-11 06:31:07 <sipa> but you need the spending transaction too
155 2014-08-11 06:31:08 <BlueMatt> its also more generically useful
156 2014-08-11 06:31:16 <sipa> you pass that in serialized form as well?
157 2014-08-11 06:31:17 <BlueMatt> yea, you pass in a serialized spending transaction
158 2014-08-11 06:31:18 <BlueMatt> yes
159 2014-08-11 06:31:33 <wumpus> and you can even use it trivially with python ctypes and such
160 2014-08-11 06:31:36 <BlueMatt> not idea, but probably better than any other alternative
161 2014-08-11 06:31:46 <BlueMatt> ACTION -> out
162 2014-08-11 06:34:04 <wumpus> sipa: changing that single line changed peak memory usage from 500+ MiB to the normal 250MiB which it can grow to anyway
163 2014-08-11 06:35:20 <sipa> cool
164 2014-08-11 06:45:18 <wumpus> iwilcox, sipa: https://github.com/bitcoin/bitcoin/pull/4675
165 2014-08-11 06:46:53 <gmaxwell> wumpus: was it correctly freeing the memory after the verification was complete?
166 2014-08-11 06:47:23 <wumpus> gmaxwell: yes; the temporary ccoinsviewcache is completely freed, the pcoinsviewtip lingers around until the next regular flush
167 2014-08-11 06:47:37 <wumpus> (which is expected)
168 2014-08-11 06:48:04 <wumpus> it's not a memory leak
169 2014-08-11 06:48:42 <wumpus> sipa suggested adding a flush right after the verification, we might as well do that too
170 2014-08-11 06:48:57 <wumpus> although it shouldn't make a difference for peak memory usage
171 2014-08-11 06:50:07 <gmaxwell> right. I wasn't sure if you were addressing peak or sustained (maybe not a leakâ e.g. peak could be high and it could keep the memory around but still use it again)
172 2014-08-11 06:50:50 <sipa> the reason for keeping it is assuming that the last blocks' outputs are likely to be consumed soon
173 2014-08-11 06:51:12 <wumpus> sipa: yes, agreed, it makes sense to keep it
174 2014-08-11 06:51:48 <wumpus> there is no problem with the verification 'priming' the cache
175 2014-08-11 06:52:21 <wumpus> so let's not add a flush
176 2014-08-11 06:52:33 <sipa> and with proper dirtyness tracking, all of them would be 'clean'
177 2014-08-11 06:53:05 <wumpus> indeed
178 2014-08-11 06:59:46 <HideousSquid> Heya all
179 2014-08-11 07:00:26 <HideousSquid> Have a question, anyone ever try to use the bitsafe device?
180 2014-08-11 07:00:42 <wumpus> #bitcoin please
181 2014-08-11 07:00:57 <HideousSquid> I'm deving software for it
182 2014-08-11 07:01:41 <HideousSquid> Was wondering if anyone was familiar with the header format of the input for the transaction packets
183 2014-08-11 07:02:36 <wumpus> that's more on-topic
184 2014-08-11 07:03:24 <HideousSquid> ;-) I can't seem to make sense of the 3 bytes that come after the address handle
185 2014-08-11 07:03:58 <HideousSquid> For example: 2323000a0000017f080112fa020101000000
186 2014-08-11 07:04:28 <HideousSquid> 2323 magic 000a command 0000017f payload size then payload begins...
187 2014-08-11 07:04:37 <HideousSquid> 0801 address handle
188 2014-08-11 07:04:57 <HideousSquid> 12fa02 <---- what the heck is this?
189 2014-08-11 07:05:49 <HideousSquid> 01 is is_ref=input then 01000000 is the output number
190 2014-08-11 07:06:09 <HideousSquid> (after that is the parent transaction etc. in standard hex)\
191 2014-08-11 07:07:02 <sipa> you'll have to talk to the hardware manufacturers about that
192 2014-08-11 07:07:17 <sipa> the transaction serialization itself isnontopic here
193 2014-08-11 07:07:25 <sipa> *is on topic hete
194 2014-08-11 07:10:57 <HideousS_> I'm building the hardware myself. Was interested if anyone had tried the software out before. It's the someone42 hardware wallet code
195 2014-08-11 08:07:21 <wumpus> I've added some instrumentation to the loop in VerifyDB with checklevel=3, I log the size of the caches along with the total amount of allocated heap memory (allocated-freed)
196 2014-08-11 08:07:24 <wumpus> 2014-08-11 07:30:04 caches: 0 0 (total 0, limit 171267): memory in use 77MiB
197 2014-08-11 08:07:36 <wumpus>
198 2014-08-11 08:07:36 <wumpus> 2014-08-11 07:39:29 caches: 113393 58197 (total 171590, limit 171267): memory in use 428MiB
199 2014-08-11 08:07:38 <wumpus> at the end
200 2014-08-11 08:09:19 <wumpus> so a simple computation (428-77)*1048576/171590 would make me believe that the usage per cache entry is 2144 bytes
201 2014-08-11 08:09:46 <wumpus> (although it scaled sub-linearly, but not by much)
202 2014-08-11 08:10:25 <wumpus> I'll make a plot
203 2014-08-11 08:12:03 <gmaxwell> thats ... awful big, esp since utxo demonstratiably take nowhere near that much on disk.
204 2014-08-11 08:12:04 <wumpus> but this is quite far away from our estimate of 300 bytes per coin in init.cpp
205 2014-08-11 08:13:55 <jgarzik> Parting thought for the night: would valgrind's heap profiler (massif) be useful?
206 2014-08-11 08:14:18 <wumpus> if you provide the default of dbcache=100 it's supposed to use about 50MiB for the coinsdb cache
207 2014-08-11 08:14:32 <wumpus> jgarzik: I'm using the gperftools heap profiler
208 2014-08-11 08:16:35 <wumpus> jgarzik: which only hooks the allocation functions, so it causes less slow-down than valgrinds tools, I'm not sure how it compares apart from that
209 2014-08-11 08:18:09 <wumpus> for every allocation it tracks where it was allocated, this is somewhat useful
210 2014-08-11 08:19:14 <wumpus> at least for looking at the bigger picture: it can't answer questions like 'why does this data structure use so much memory'
211 2014-08-11 08:20:32 <gmaxwell> I wish bitcoin were P2SH only, utxo could be constant size. :P
212 2014-08-11 08:20:33 <wumpus> or even what data structure takes the memory; for the VerifyDB loop it's clear that all the memory is allocated under DisconnectBlock, but we could have guessed that
213 2014-08-11 08:20:55 <wumpus> gmaxwell: heh indeed!
214 2014-08-11 08:25:43 <wumpus> the cache contains a map from uint256 to CCoins ... a CCoins is just a bool, a vector<CTxOut>, and two integers
215 2014-08-11 08:26:03 <wumpus> a CTxOUt is a 64-bit integer and a CScript
216 2014-08-11 08:28:08 <wumpus> and CScript is a vector<unsigned char> with some helper methods, no extra fields
217 2014-08-11 08:29:10 <jgarzik> how much map overhead? IIRC it has internal leave in a tree due to btree sorting method?
218 2014-08-11 08:29:14 <jgarzik> *leaves
219 2014-08-11 08:29:14 <wumpus> I wonder how much overhead is caused by us, and how much is just inherent to c++'s data structures and extra pointers and so
220 2014-08-11 08:29:59 <wumpus> well we switched to a boost::unordered_map recently, which uses a hash table instead of a tree, so that should help
221 2014-08-11 08:30:38 <jgarzik> wumpus, is that a single array (the hash table) + linked list for buckets with >1 member?
222 2014-08-11 08:30:57 <wumpus> jgarzik:you'd suppose so - but I don't know how it's implemented in boost
223 2014-08-11 09:18:40 <wumpus> I added very naive GetMemorySize() accounting to CCoinsViewCache, but it seems pretty close 2014-08-11 09:17:41 caches: 113398/164MiB 58277/167MiB (total 171675/332MiB, limit 171267): memory in use 431MiB
224 2014-08-11 09:19:27 <wumpus> so starting memory use is 77MiB, final memory use is 431MiB, it counts the total size of the data structures as 332MiB
225 2014-08-11 09:20:36 <wumpus> for 171675 records there is only 22MiB unaccounted for, so part of boost::unordered_map or vector that we don't know of
226 2014-08-11 09:21:33 <gmaxwell> wumpus: but where is the actual size going? it's surely not the data.
227 2014-08-11 09:21:36 <wumpus> so the next thing would be to limit the CCoinsViewCache based on memory size instead of # entries
228 2014-08-11 09:22:35 <gmaxwell> might be better to first get rid of the n-fold overhead though. The cache has a large impact on performance.
229 2014-08-11 09:22:50 <wumpus> well it's possible to combine it with an increase of the default size
230 2014-08-11 09:23:00 <wumpus> so that overall behavior stays exactly the same
231 2014-08-11 09:23:15 <wumpus> but we don't lie about dbcache size anymore :P
232 2014-08-11 09:23:20 <wumpus> but sure, solving the overhead would be even better
233 2014-08-11 09:29:16 <sipa> wumpus: i have a branch which adds a GetMemoryUsage templated function for many of our data structures, and standard containers (including a constant for accounting for malloc overhead)
234 2014-08-11 09:29:30 <wumpus> oh, so I'm doing duplicate work again :/
235 2014-08-11 09:30:41 <sipa> don't have access to it right now; but i can polish it a bit tonight
236 2014-08-11 09:31:20 <wumpus> btw, why does it need a templated function?
237 2014-08-11 09:31:42 <sipa> to make it work automatically for containers
238 2014-08-11 09:32:00 <sipa> i
239 2014-08-11 09:32:25 <wumpus> ok, makes sense
240 2014-08-11 09:32:53 <sipa> it's similar to serialize.h; it has default implementations for many standard data structures, and allows implementing your own method for classes
241 2014-08-11 09:33:16 <hearn> why do we have CCoinsViewCache, again? leveldb has its own cache as does the kernel
242 2014-08-11 09:33:45 <gmaxwell> hearn: because leveldb alone is very slow.
243 2014-08-11 09:33:54 <sipa> hearn: which only has serialized data; not directly updatable c++ data structures
244 2014-08-11 09:34:24 <wumpus> hearn: try running with a very small -dbcache to find out
245 2014-08-11 09:34:25 <sipa> the idea is to batch many changes before issuing a write, to avoid deserializing and reserializing all the time
246 2014-08-11 09:34:37 <hearn> ah ok
247 2014-08-11 09:34:51 <hearn> right, serialization overhead is pretty big
248 2014-08-11 09:34:59 <sipa> it may be that if we changed the leveldb structure to be per-txout rather than per-tx, it would be different
249 2014-08-11 09:35:12 <sipa> as it would make the in-db entries immutable - just create and delete
250 2014-08-11 09:35:23 <hearn> or maybe used a serialization format for the database that's memcpyable, a la cap'n proto
251 2014-08-11 09:35:35 <hearn> from the perspective of leveldb it doesn't make much difference i think
252 2014-08-11 09:35:44 <hearn> an overwrite looks the same internally as a create/delete
253 2014-08-11 09:35:47 <sipa> there's a factor 10 at least in memory usage between in the in-memory form and the serialized form
254 2014-08-11 09:36:05 <hearn> yes because of the compression
255 2014-08-11 09:36:18 <sipa> mostly because of std:;vector overhead
256 2014-08-11 09:36:20 <wumpus> we don't use compression
257 2014-08-11 09:36:36 <gmaxwell> and the leveldb compression isn't helpful for us.
258 2014-08-11 09:36:36 <wumpus> at least not the leveldb compression
259 2014-08-11 09:37:03 <wumpus> I'm trying to figure out what exactly the overhead is
260 2014-08-11 09:37:11 <sipa> hearn: yes, but if it was only create-delete, there would be much less use for an in-memory updatable structure
261 2014-08-11 09:37:29 <hearn> wumpus: yeah i meant the special sipa hand-rolled compression
262 2014-08-11 09:37:35 <sipa> though it would still need deserialization at least
263 2014-08-11 10:05:51 <wumpus> it looks like the main source of overhead are the CTxOut structs themselves, they take up 32 bytes a piece
264 2014-08-11 10:08:31 <wumpus> the scriptPubKeys on average take about 12.4 bytes
265 2014-08-11 10:14:16 <wumpus> so the minimum size of a TxOut would be 8 bytes (nValue) plus the size of the script, ie ~20 bytes on average total, whereas now it takes 32 + 12.4=44 per txout + extra malloc overhead
266 2014-08-11 10:19:22 <hearn> wumpus: alignment padding too? also i wonder if we should store nValue as a varint. those top bytes will basically always be zero
267 2014-08-11 10:19:40 <hearn> unless the bitcoin economy becomes totally fucked and one output ends up owning half the wealth the entire economy :-)
268 2014-08-11 10:20:35 <wumpus> well on disk it is encoded as a sort of varint, in memory that's less practical
269 2014-08-11 10:23:11 <wumpus> and indeed the reason why a structure with a int64 and a vector would be 32 bytes must be alignment
270 2014-08-11 10:23:35 <wumpus> there are some gcc pragmas for affecting that
271 2014-08-11 10:23:49 <gmaxwell> wumpus: 44 bytes isn't a big deal. I still don't see how we're getting to 2000 bytes per cache entry.
272 2014-08-11 10:26:38 <wumpus> Dump: Total 170 MiB: uint256 3 MiB (112953 * 32.0), CCoins 4 MiB (112953 * 40.0), CTxOut 118 MiB (3881766 * 32.0), scriptPubKey 44 MiB (3881766 * 11.9)
273 2014-08-11 10:27:11 <wumpus> 3881766 times 44 is a lot
274 2014-08-11 10:32:50 <wumpus> ohh sizeof(CScript) is 24 (same as sizeof(std::vector<unsigned char>) )
275 2014-08-11 10:33:25 <wumpus> so on average the vector struct itself is larger than the data stored in it :p
276 2014-08-11 10:33:42 <wumpus> (which is allocated separately)
277 2014-08-11 10:33:45 <Luke-Jr> XD
278 2014-08-11 10:38:17 <wumpus> huh does this make sense - for pcoinsTip, after verification is complete, the average number of CTxOuts per CCoins is 68
279 2014-08-11 10:51:20 <wumpus> ehh 0811168291a1adc418509d42b37679fe006a3fc3d24b2f39b392e6c8abc2a39e 2328
280 2014-08-11 10:51:43 <wumpus> ugh, *2328* outputs
281 2014-08-11 10:52:35 <wumpus> so yes, the 68 is correct -- most transactions by number have 0/1/2 outputs, but quite a few have extremely large numbers of outputs, pulling up the average
282 2014-08-11 11:03:55 <wumpus> eh, pcoinsTip doesn't have transactions with 0 outputs
283 2014-08-11 11:04:56 <wumpus> (the temporary CCoinsViewDB in VerifyDB has, thus that one has a lower average txouts/tx)
284 2014-08-11 11:35:06 <wumpus> distribution of scriptpubsizes in the CCoinsViewCache: http://www.hastebin.com/ipagonafol.md 99.9% of the outputs are sizes 0 (spent) and 25, so it makes sense to optimize for those, sizes >25 are extrememly uncommon as expected
285 2014-08-11 11:36:26 <sipa> that sounds like a medicin...
286 2014-08-11 11:36:31 <sipa> (ipagonafol)
287 2014-08-11 11:36:56 <gmaxwell> you'd think there would be some optimization for size zero vectors...
288 2014-08-11 11:37:33 <sipa> gmaxwell: there should be
289 2014-08-11 11:37:45 <sipa> they shouldn't use any dynamic memory
290 2014-08-11 11:38:00 <wumpus> well, size zero vectors probably don't allocate any memory, they 'only' take the 24 bytes overhead
291 2014-08-11 11:38:07 <sipa> yup
292 2014-08-11 11:38:10 <wumpus> (12 on 32-bit)
293 2014-08-11 11:38:18 <sipa> (note that vector.clear() does _not_ release memory though)
294 2014-08-11 11:38:47 <wumpus> right, that clears size() but not capacity()
295 2014-08-11 11:39:05 <sipa> you need vector.swap(std::vector<bla>()) for that...
296 2014-08-11 11:40:52 <wumpus> sipa: hmm CTxOut::SetNull() just uses clear()
297 2014-08-11 11:42:06 <sipa> CCoins::Cleanup() does release memory though
298 2014-08-11 11:43:06 <sipa> but that CTxOut::SetNull() could be improved
299 2014-08-11 11:43:19 <wumpus> yes, if the txout vector itself is empty it's swapped with an empty vector
300 2014-08-11 11:43:25 <gmaxwell> probably results in more memory usage when txouts get spent during the reorg test, no?
301 2014-08-11 11:43:29 <gmaxwell> ah. okay.
302 2014-08-11 11:44:12 <wumpus> I don't think it can ever result in more memory usage
303 2014-08-11 11:44:45 <gmaxwell> It might just be prudent to swallow the testing overhead and have a -lowmem=1 option that ruthlessly reduces memory usage at the expense of performance.
304 2014-08-11 11:45:10 <gmaxwell> wumpus: I meant more compared to what I would have anticipated (just the vector overhead)
305 2014-08-11 11:45:35 <sipa> wumpus: basically that means that spending an output does not release any memory until that tx is entirely spent
306 2014-08-11 11:46:10 <sipa> wumpus: i don't think there is any reason not to release the script vector in CTxOut::SetNull
307 2014-08-11 11:46:30 <gmaxwell> oh it isn't releasing it. cool.
308 2014-08-11 11:46:41 <gmaxwell> that will probably have a nice impact.
309 2014-08-11 11:51:35 <lewellyn> blarg.
310 2014-08-11 11:51:42 <lewellyn> https://github.com/bitcoin/bitcoin/blob/master/src/addrman.h#L304 is upsetting my gcc. :(
311 2014-08-11 11:52:03 <sipa> lewellyn: why?
312 2014-08-11 11:52:35 <lewellyn> it thinks there's a const_iterator and i can't figure out why.
313 2014-08-11 11:52:47 <lewellyn> error: conversion from 'std::_Tree<std::_Tset_traits<int, std::less<int>, std::allocator<int>, false> >::const_iterator' to non-scalar type 'std::set<int>::iterator {aka std::_Tree<std::_Tset_traits<int, std::less<int>, std::allocator<int>, false> >::iterator}' requested
314 2014-08-11 11:53:28 <lewellyn> i assume i'm not the first one to be compiling this on not-x86 and/or not-linux :P
315 2014-08-11 11:53:36 <lewellyn> (and yes, that's a gcc error)
316 2014-08-11 11:53:54 <sipa> non-linux happens all the time
317 2014-08-11 11:54:04 <lewellyn> figured so much. and i assumed arm, as well.
318 2014-08-11 11:54:10 <wumpus> you're trying to convert a const_iterator to an iterator
319 2014-08-11 11:54:16 <wumpus> yes, ARM happens a lot
320 2014-08-11 11:54:19 <lewellyn> wumpus: i didn't touch that file :P
321 2014-08-11 11:54:31 <lewellyn> i can't figure out where the const_iterator is.
322 2014-08-11 11:55:03 <lewellyn> er. iterator.
323 2014-08-11 11:55:06 <lewellyn> whatever. it's late :D
324 2014-08-11 11:55:07 <wumpus> probably you're using XX::iterator on field in a method marked const
325 2014-08-11 11:55:14 <sipa> no
326 2014-08-11 11:55:32 <sipa> it's a vector of sets
327 2014-08-11 11:55:47 <sipa> the vector iterator type wraps a set iterator type i suppose
328 2014-08-11 11:56:08 <gmaxwell> lewellyn: gcc version?
329 2014-08-11 11:56:59 <lewellyn> 4.6.3
330 2014-08-11 12:01:18 <gmaxwell> not hideously old, though older than what I use on arm.
331 2014-08-11 12:02:38 <lewellyn> yeah. apparently i get a newer gcc if i target a later os release than i want to target. :(
332 2014-08-11 12:03:02 <lewellyn> i might end up sleeping on it and figuring out how to handle it.
333 2014-08-11 12:57:02 <michagogo> We should be about 27 hours away from hitting 7 days since https://bugs.launchpad.net/ubuntu/+source/bitcoin/+bug/1314616/comments/5
334 2014-08-11 12:57:57 <michagogo> Tomorrow night I should be able to poke Chris Halse Rogers (RAOF) or Chris Arges (arges) and finally get 0.3.24 removed from Ubuntu Precise 12.04 LTS
335 2014-08-11 13:01:02 <wumpus> wasn't that impossible for some reason?
336 2014-08-11 13:01:33 <wumpus> or do you mean replaced with a dummy package?
337 2014-08-11 13:02:11 <michagogo> wumpus: yes, I do mean that
338 2014-08-11 13:02:25 <wumpus> ok!
339 2014-08-11 13:03:38 <michagogo> wumpus: https://i175917225.restricted.launchpadlibrarian.net/175917225/b75b8604-df93-11e3-968c-002481e91f22.txt?token=8aa196fa08c3bd1f11b392cf0bc1e72d
340 2014-08-11 13:19:36 <gmaxwell> sipa: So I either made secp256k1 verification 1.6% faster, or introduced a cryptographic weakness that the tests are unable to detect. (considering that I'm not feeling well and haven't slept, the latter is probably more likely)
341 2014-08-11 13:20:44 <sipa> gmaxwell: code?
342 2014-08-11 13:22:10 <gmaxwell> sipa: knowing that modular inversions are slow, I was thinking about batching the inversions in verification. But before I got that far, I thoughtâ oh one of these is just the conversion from the jacobian to get the x for comparison to r, so why not instead multiply r by pr.z^2 and compare that way?
343 2014-08-11 13:22:23 <gmaxwell> seemed like too easy an optimiztion to work.
344 2014-08-11 13:24:03 <sipa> ha!
345 2014-08-11 13:25:12 <sipa> i don't see why that would be a problem
346 2014-08-11 13:25:26 <gmaxwell> yea nor did I, tests pass.
347 2014-08-11 13:25:32 <gmaxwell> I just monkey patched it in to see if it would work.
348 2014-08-11 13:26:26 <gmaxwell> first invert could still benefit from batching.
349 2014-08-11 13:26:31 <sipa> yup
350 2014-08-11 13:26:43 <sipa> and may well make it acceptable to use a naive inversion implementation
351 2014-08-11 13:26:49 <sipa> (which doesn't need gmp)
352 2014-08-11 13:27:08 <gmaxwell> right, this was most of why I was even thinking about this.
353 2014-08-11 13:28:02 <gmaxwell> as a principle in general any place in _verification_ where there is a division its best to try to work backwards so you can multiply instead. :)
354 2014-08-11 13:36:45 <gmaxwell> sipa: in any case you're welcome to my monkey patch code, though I'll send a proper pull later once I've slept and can figure out how I ought to properly be coercing this num into a field element. http://0bin.net/paste/7xAu-+EeN-1Rk5AA#T32S3NGUWJ3y9Ku39x4WCl1cPKnkb+IoVclT7ua0XtW
355 2014-08-11 13:37:19 <sipa> you need to convert to a 32-byte array using set_bin and get_bin
356 2014-08-11 13:37:24 <sipa> intermediary
357 2014-08-11 13:39:14 <gmaxwell> sipa: thats what the aformentioned monkey patch is doing, which seemed kinda hideous. So perhaps I need to add a convert function or deseralize the signature differently.
358 2014-08-11 13:45:56 <sipa> r is already constrained to be in [1,n-1], so modulo n r*s == zG + rQ should be equivalent to r == (z/s)G + (r/s)Q
359 2014-08-11 13:53:10 <gmaxwell> hah
360 2014-08-11 13:53:43 <sipa> ?
361 2014-08-11 13:54:21 <sipa> wait; r == [(z/s)G + (r/s)Q].x
362 2014-08-11 13:55:02 <sipa> you can't multiply both sides by s
363 2014-08-11 13:55:39 <gmaxwell> yea, alas, that was my ha but seems we can't totally eliminate the inversions.
364 2014-08-11 13:56:05 <sipa> why did the tests work?
365 2014-08-11 13:56:14 <gmaxwell> sipa: ah you've misunderstood what I did! :)
366 2014-08-11 13:57:09 <sipa> ah, no
367 2014-08-11 13:57:14 <gmaxwell> There are two inversions in the verification. S is inverted, and there is an inversion used in the conversion of the sum back to affine.
368 2014-08-11 13:57:35 <gmaxwell> I got rid of the latter one.
369 2014-08-11 13:57:39 <sipa> oh!
370 2014-08-11 13:58:46 <gmaxwell> since to convert back you do Z^-1^2 * pr.x == r and instead I compute r*Z^2 == pr.x.
371 2014-08-11 13:58:51 <sipa> so we need a secp256k1_gej_compare_x
372 2014-08-11 13:59:02 <sipa> which takes a gej and a field element
373 2014-08-11 14:05:37 <sipa> gmaxwell: oh, no, it doesn't neatly fit within the field element code, as it's a comparison modulo the curve order...
374 2014-08-11 14:05:53 <sipa> which you already noticed of course
375 2014-08-11 14:40:12 <HideousS_> Hey all, I tried to send the output of my signing device into the network (sendrawtransaction) but it spewed an error 64: non-canonical (code -26)
376 2014-08-11 14:40:37 <HideousS_> The decoderawtransaction doesn't show any obvious errors
377 2014-08-11 14:41:04 <sipa> your signature isn't following the canonical encoding
378 2014-08-11 14:41:10 <HideousS_> (I'm coding the routines to use the signing device)
379 2014-08-11 14:41:19 <sipa> see https://github.com/bitcoin/bips/blob/master/bip-0062.mediawiki#DER_encoding
380 2014-08-11 14:42:02 <HideousS_> Ok, let me check. I'm familiar with the coding...I may have dropped a bit
381 2014-08-11 14:42:09 <HideousS_> Thanks!
382 2014-08-11 14:44:33 <gmaxwell> HideousSquid: if you're building your own signer, do be careful that your nonce is cryptographically random or created according to RFC6979.
383 2014-08-11 14:44:55 <gmaxwell> several times people have leaked their private keys with errors there.
384 2014-08-11 14:45:17 <HideousSquid> Thanks. I'm doing a hardware device. I'm adding an atsha204 for the RNG
385 2014-08-11 14:45:50 <HideousSquid> Thanks for the advice
386 2014-08-11 14:50:07 <HideousSquid> Bah, the DER address is correct, size of the think is correct (8b/48/41)... anything else that error refers to? Or is there an error table somewhere?
387 2014-08-11 14:50:48 <HideousSquid> s/think/thing/
388 2014-08-11 14:52:39 <sipa> can you paste the full hex signature?
389 2014-08-11 14:52:54 <HideousSquid> sure
390 2014-08-11 14:53:11 <HideousSquid> 04B083E60A048BEED23542B736E7EB10980139EB97095BABE1E025D1BB5F32CD82F1C4D59173BEA2BAA56D8C6367F57AF2ECCF89A22F8C1DB82BCE8179EFD7C32A
391 2014-08-11 14:53:40 <HideousSquid> Checks out the ripe160 and full to the base58 address
392 2014-08-11 14:53:46 <sipa> that's a public key, not a signature5
393 2014-08-11 14:53:52 <sipa> and please use compressed keys
394 2014-08-11 14:53:55 <HideousSquid> Whoops, hold a sec
395 2014-08-11 14:55:22 <HideousSquid> Sorry which one is the compressed? I'm generating raw transactions. You mean the ripe160?
396 2014-08-11 14:55:31 <sipa> ...
397 2014-08-11 14:55:56 <sipa> compressed public keys: 0x02 + 32-byte X coordinate or 0x03 + 32-byte Y coordinate
398 2014-08-11 14:56:13 <sipa> instead of the normal ones, which are 0x04 + 32-byte X coordinate + 32-byte Y coordinate
399 2014-08-11 14:56:22 <sipa> it's a waste of space to use uncompressed ones
400 2014-08-11 14:56:46 <sipa> the 0x02 or 0x03 identifies the odd/evenness of the Y coordinate
401 2014-08-11 14:56:57 <HideousSquid> Doesn't a raw transaction need uncompressed?
402 2014-08-11 14:57:01 <sipa> no
403 2014-08-11 14:57:26 <gmaxwell> HideousSquid: pub[0]=2+(pub[64]&1);pub_len=33; but uh. please be careful, it sounds like you're new to this stuff and it can be very easy to forever lose coins while messing with directly authoring your own transactions. Are you doing this on testnet?
404 2014-08-11 14:58:00 <HideousSquid> No, but it's low amounts
405 2014-08-11 14:58:14 <sipa> well, your loss
406 2014-08-11 14:58:18 <sipa> but really, seriously
407 2014-08-11 14:58:27 <sipa> do this on testnet until it works
408 2014-08-11 14:58:43 <HideousSquid> ok!
409 2014-08-11 14:59:12 <sipa> now, can you paste me a signature?
410 2014-08-11 15:00:14 <HideousSquid> 02B083E60A048BEED23542B736E7EB10980139EB97095BABE1E025D1BB5F32CD82
411 2014-08-11 15:00:44 <sipa> that is not a valid DER encoded signature
412 2014-08-11 15:01:18 <sipa> that looks like a compressed public key, though
413 2014-08-11 15:01:59 <HideousSquid> Um, I just lopped off the 04 added the 02 and tacked on the first 32 bytes
414 2014-08-11 15:02:22 <sipa> well, you also need to change your addresses
415 2014-08-11 15:02:32 <sipa> as they are computed from the hash of the public key, and public key changed
416 2014-08-11 15:02:35 <sipa> but yes
417 2014-08-11 15:02:44 <sipa> now, can you please show me a signatutre?
418 2014-08-11 15:03:56 <HideousSquid> the scriptSig I generated?
419 2014-08-11 15:03:59 <sipa> yes
420 2014-08-11 15:04:20 <HideousSquid> 48304502206E1EA5AB66DC7B78A8382A6817571D415D6F89545E8618E33A8853B00489B52A02210086147574095D270F3F5690F8ABDFF38B8F95CC5F76F72B86728B3C4CC6DAF64C01
421 2014-08-11 15:06:18 <sipa> looks good at first glace
422 2014-08-11 15:06:26 <HideousSquid> hmmmm
423 2014-08-11 15:06:50 <HideousSquid> I had this cononical thing before but damn if I forgot what it was
424 2014-08-11 15:07:59 <HideousSquid> May I paste you the full transaction? It's not too long
425 2014-08-11 15:08:31 <sipa> i don't have time to look at it further
426 2014-08-11 15:08:45 <HideousSquid> Ok, thanks for the help
427 2014-08-11 15:10:09 <gmaxwell> HideousSquid: go yank out the canonical testing code from bitcoin and test it on your data.
428 2014-08-11 15:10:26 <HideousSquid> Will have to do that
429 2014-08-11 15:10:48 <gmaxwell> (since, presumably, you've missed something in the written description)
430 2014-08-11 15:11:42 <HideousSquid> I dug through the code before but it only glancingly mentions this error
431 2014-08-11 15:12:40 <gmaxwell> HideousSquid: there is a very extensive description of the tests performed on signatures. https://github.com/bitcoin/bitcoin/blob/master/src/script.cpp#L245
432 2014-08-11 15:13:10 <HideousSquid> Got it.
433 2014-08-11 15:13:26 <sipa> also, when submitting it to bitcoind, the actual error is logged to debug.log
434 2014-08-11 15:14:29 <gmaxwell> your r-type above is 04
435 2014-08-11 15:14:44 <sipa> ugh, indeed
436 2014-08-11 15:15:54 <gmaxwell> (actoually 0x45, whatever that isâ can't read hex in the morning it seems)
437 2014-08-11 15:16:13 <HideousSquid> No hex before coffee!
438 2014-08-11 15:16:13 <sipa> eh no
439 2014-08-11 15:16:23 <sipa> his r type is 0x02, which is correct
440 2014-08-11 15:16:27 <sipa> 0x45 is the total len
441 2014-08-11 15:16:32 <sipa> which is also correct
442 2014-08-11 15:33:38 <gmaxwell> sipa: I know I was trying to eliminate inversions, but in your WNAF code did you ever try putting A's precomputation into affine so you could use the mixed projection addition, by using a batch inversion for the conversion? would only require a single inversion for the whole table.
443 2014-08-11 15:34:18 <sipa> gmaxwell: i believe peter dettman tried that
444 2014-08-11 15:34:49 <gmaxwell> (and even with the extra multiples for the batching I seem to recall that would save two multiplies and a squaring per point.)
445 2014-08-11 15:34:53 <gmaxwell> oh darn.
446 2014-08-11 15:34:57 <gmaxwell> sorry, obviously I haven't been following closely.
447 2014-08-11 15:35:30 <gmaxwell> hm. wonder why that wasn't faster.
448 2014-08-11 15:36:24 <sipa> because inversions are really slow
449 2014-08-11 15:37:11 <sipa> like several microseconds
450 2014-08-11 15:38:06 <Billdr> I want to clear up reddit's understanding of wallet.dat. I want to make sure I understand what's happening there first. Is there an easy way to see the functions that touch that file?
451 2014-08-11 15:38:38 <gmaxwell> what are you tryint go clear up?
452 2014-08-11 15:39:00 <gmaxwell> and ... wallet.cpp but its not organized in a way where 'the file' is a useful boundary.
453 2014-08-11 15:39:11 <Billdr> There was some confusion on why you'd want to do a continuous backup as opposed to a one time.
454 2014-08-11 15:39:18 <wumpus> wallet.cpp and walletdb.cpp
455 2014-08-11 15:39:45 <Billdr> Also, I'd like to illustrate some of the advantages over a deterministic wallet.
456 2014-08-11 15:39:51 <gmaxwell> Billdr: I don't know that there is much to be confused about, they keypool behavior is well documented.
457 2014-08-11 15:40:07 <Billdr> Thanks wumpus.
458 2014-08-11 15:40:24 <wumpus> Billdr: a deterministic wallet is superior in most regards
459 2014-08-11 15:40:44 <gmaxwell> Billdr: The advantages over a determinstic wallet are key management primarly... an old backup falling into bad hands doesn't cause you to lose funds. Also you generally have important metadata you need to be backing up in any case.
460 2014-08-11 15:41:16 <gmaxwell> Really ideally users would have some kind of hybrid which is determinstic mostly, but can rotate keys at well defined intervals and never leaves them hanging with respect to backups.
461 2014-08-11 15:41:55 <wumpus> right, the only problem with (naive) determinstic wallets is that stealing one key is enough to gain access to all your future funds, being able to generate all keys is both a blessing and a curse
462 2014-08-11 15:42:09 <wumpus> but is makes backups saner and safer
463 2014-08-11 15:43:00 <gmaxwell> I suppose there are some implementation specific things: almost all current determinstic wallets are using the homomorphic derrivation, which is unsafe to export single private keys from.
464 2014-08-11 15:43:05 <Billdr> Gmaxwell: thanks. I'll try to research that in detail.
465 2014-08-11 15:43:05 <wumpus> with bitcoind's current key management it is very hard to make a backup strategy that is guaranteed to never let you lose keys
466 2014-08-11 15:43:36 <wumpus> ie, if you make a daily backup, you should set the keypool size to the maximum number of keys that you'll ever use in a day, and you need to know that upfront
467 2014-08-11 15:43:58 <gmaxwell> wumpus: yea, but it's not inherent non-determinism. E.g. you could have a wallet as a bag of determinstic master keys, with the next one precomputed, and it only rotates to start using the next one backup after you've told it to change.
468 2014-08-11 15:43:59 <Billdr> A continuous backup would cover that, no?
469 2014-08-11 15:44:13 <wumpus> I've heard of various cases where people underestimated their number of transactions
470 2014-08-11 15:44:21 <wumpus> it's a number they set once, then forgot about
471 2014-08-11 15:44:30 <gmaxwell> Billdr: sure.
472 2014-08-11 15:44:39 <wumpus> and as the keypool is automatically refilled, there is no warning when that happens
473 2014-08-11 15:45:39 <Billdr> Pairs associated with a balance always stay, I assume.
474 2014-08-11 15:45:42 <wumpus> gmaxwell: sure, I'm talking about the current implementation in bitcoind, which will likely not change in the near future; combining determinism with rotating keys (aftera backup) would make a lot of sense
475 2014-08-11 15:46:19 <gmaxwell> wumpus: I only bring it up to prevent smarter things from leaving the shared dialog. :)
476 2014-08-11 15:47:49 <wumpus> Billdr: right - a continuous backup strategy would be the only way to be sure, or "backup after every 50th transaction"
477 2014-08-11 15:48:33 <wumpus> Billdr: but it's harder to get right, as you always need to have access to your backup, it won't work with manual off-site backups for example
478 2014-08-11 15:49:00 <Billdr> And of my backup tool has 5 versions of the wallet.dat I would lose keys every 250 transactions?
479 2014-08-11 15:49:19 <gmaxwell> Billdr: old keys are kept forever.
480 2014-08-11 15:49:39 <hearn> gmaxwell: bitcoinj's HD implementation stores multiple chains in the wallet and can do key rotation (automatically respends funds arriving at old chains to new chains)
481 2014-08-11 15:49:59 <wumpus> Billdr: huh? no, if you backup every N times you need a new key (so either do a transaction OR generate a new receiving address) where N is smaller than your keypool size, you'll be safe
482 2014-08-11 15:50:09 <gmaxwell> hearn: I am aware! Hopefully it'll actually get exposed...
483 2014-08-11 15:50:32 <hearn> i think it'll probably be automatically invoked when users do things like encrypt their wallet
484 2014-08-11 15:50:45 <hearn> it's not really obvious to me that key rotation should be exposed to the user directly
485 2014-08-11 15:51:18 <wumpus> well you may want to rotate the key before every backup, as gmaxwell just said, so that the new key is on the backup
486 2014-08-11 15:51:55 <hearn> mmm. maybe. with the way bitcoin currently works a key rotation is not free. you have to pay a fee to spend money incoming on old chains to the new chains
487 2014-08-11 15:52:13 <hearn> if we adjusted the fee rules so a one-deep tx chain inherited the priority of its parent a spend-then-immediately-respend-once pattern could be free
488 2014-08-11 15:52:41 <gmaxwell> hearn: Thats true for a 'panic button' grade move, vs creating a new one and prefering to just spend off the old ones as you get a chance to do it for free.
489 2014-08-11 15:53:22 <gmaxwell> I don't see why general functioning CFPF code couldn't also work for priority.
490 2014-08-11 15:53:43 <gmaxwell> Though I don't know that it would really help that much for this, ultimately making more transactions has a cost.
491 2014-08-11 15:54:02 <hearn> yeah, for rotations that are just general hygenie i guess we don't have to actually move money off old keyse
492 2014-08-11 15:54:10 <hearn> i hadn't thought about non-panic-button rotations before
493 2014-08-11 15:54:16 <hearn> it would be easy to implement though
494 2014-08-11 15:54:23 <gmaxwell> for a 'my wallet is potentially compromised!' its worth a cost. Otherwise just doing something mostly passive as policy is.. right, it's hygenic.
495 2014-08-11 15:54:52 <hearn> *hygiene
496 2014-08-11 15:54:57 <hearn> (i hate english sometimes)
497 2014-08-11 15:55:04 <gmaxwell> the software would also know the ages of the keys that have value on them, so you can ask what your exposure is and decide to hit a panic button.
498 2014-08-11 15:55:42 <hearn> right.
499 2014-08-11 15:56:04 <hearn> for triggering it off backup that can be hidden from the user entirely, as long as they don't lose their most recent backup but still have older backups
500 2014-08-11 15:56:15 <hearn> not sure. i guess i'll mention this in the docs and let wallet authors decide
501 2014-08-11 15:56:49 <gmaxwell> Yes, it could be background but in terms of user exposed you might want a setting which is "allow backups older than X to become invalid"
502 2014-08-11 15:57:15 <gmaxwell> e.g. X = 1 year.
503 2014-08-11 15:58:27 <gmaxwell> sipa: ah, the Co-z patch does the batch inversion on the precompute.
504 2014-08-11 15:59:04 <gmaxwell> gah is there a way to get github to give more context?
505 2014-08-11 15:59:59 <wumpus> gmaxwell: no :-(
506 2014-08-11 16:00:13 <wumpus> I've requested that feature a few times
507 2014-08-11 16:00:19 <wumpus> your only choice is to show the entire file
508 2014-08-11 16:00:48 <hearn> for a code hosting site, github's diff viewer truly sucks
509 2014-08-11 16:00:51 <gmaxwell> I keep misreading patches due to insufficient context.
510 2014-08-11 16:04:05 <jrick> there are "expander" buttons in the line numbers at the top and bottom of each section of the patch
511 2014-08-11 16:04:31 <michagogo> wumpus: uh, yes there is
512 2014-08-11 16:04:31 <wumpus> jrick: wow, that must be new
513 2014-08-11 16:04:34 <michagogo> as jrick said
514 2014-08-11 16:04:41 <michagogo> I don't think it's very new...
515 2014-08-11 16:04:57 <wumpus> well I'm sure it is, or github support didn't know of it themselves
516 2014-08-11 16:05:03 <michagogo> maybe
517 2014-08-11 16:05:09 <michagogo> (also, how new?)
518 2014-08-11 16:31:34 <Billdr> Sorry, was called away. Thanks for the assistance. I'll probably run my post through here before I put it up.
519 2014-08-11 17:49:45 <hearn> nice visualisation: http://www.royalforkblog.com/2014/08/11/graphical-address-generator/
520 2014-08-11 17:49:52 <hearn> although deriving private key from passphrase, ick
521 2014-08-11 17:51:14 <Emcy> nice
522 2014-08-11 17:55:04 <Emcy> if thats goona do the rounds
523 2014-08-11 17:55:22 <Emcy> it needs a big scary red warning not to use its output for anything real
524 2014-08-11 17:56:00 <TD-Linux> it's got a small warning at the top. the passphrase makes it reproducible with your own code
525 2014-08-11 18:06:45 <Emcy> why is it in a horiz scroller iframe thing
526 2014-08-11 18:06:47 <Emcy> thats annoying
527 2014-08-11 19:39:07 <pouta> Hi!
528 2014-08-11 19:40:20 <pouta> I have a question regarding the block creation and how transactions are used in a block.
529 2014-08-11 19:42:25 <pouta> is anyone here?
530 2014-08-11 19:44:35 <super3> pouta: hello
531 2014-08-11 19:44:46 <pouta> Hi!
532 2014-08-11 19:44:52 <super3> don't ask to ask, just ask
533 2014-08-11 19:46:51 <pouta> we are now moving on to bloom tables for a faster block porpagation right?
534 2014-08-11 19:46:55 <pouta> propagation*
535 2014-08-11 19:48:17 <pouta> im talking about BIP37
536 2014-08-11 19:48:58 <pouta> brb, 5 mins
537 2014-08-11 19:49:19 <helo> pouta: i may be under-informed, but bloom filters are used so SPV nodes can tell full nodes what they are interested in while preserving some privacy
538 2014-08-11 19:50:12 <Emcy> hes talking about gavins thing
539 2014-08-11 19:56:13 <pouta> I'm talking about this https://github.com/bitcoin/bips/blob/master/bip-0037.mediawiki
540 2014-08-11 19:57:08 <pouta> I think the true problem comes with miners choosing to create a smaller block in order to have less change of having it prphaned
541 2014-08-11 19:57:26 <pouta> orphaned*
542 2014-08-11 20:00:01 <pouta> but a simple solution comes to mind, If nodes have know the transactions that are not confirmed why not let nodes reach a consesus about what transactions should be included in the next block. That way all miners would try to mine the same block leaving them with equal chance to get them orphaned.
543 2014-08-11 20:00:42 <helo> i don't think there's really any way for nodes to be put in charge of that
544 2014-08-11 20:01:16 <pouta> right now there isnt
545 2014-08-11 20:01:34 <pouta> My question is if it can be done , why not?
546 2014-08-11 20:01:54 <helo> well, the idea behind multiple miners is a diverse set of transactions that make it into blocks
547 2014-08-11 20:01:57 <helo> to avoid centralized control
548 2014-08-11 20:02:40 <helo> if everyone has to agree what is going into blocks, or if there are some odd restrictions/agreement mechanisms, it might create an avenue for censorship/control
549 2014-08-11 20:03:58 <pouta> Yes it would, but now we have to trust our nodes, or at least 51% of them right?
550 2014-08-11 20:04:31 <pouta> if that 51% decides that transaction x, y and z should all be in the next block why would that be bad?
551 2014-08-11 20:07:28 <pouta> Also where can I make this question to a broader audience?
552 2014-08-11 20:11:47 <helo> consider the "let nodes reach a consensus about what transactions should be included in the next block." part. it isn't easy to just wave your hands and reach a decentralized consensus. that's the hard problem that bitcoin solves to make it useful.
553 2014-08-11 20:13:19 <pouta> I'm not saying it is easy
554 2014-08-11 20:13:50 <pouta> if we hardcode some rules in witch the node will decide witch transactions to use and all the nodes use the same version
555 2014-08-11 20:13:51 <helo> the proof of work block-by-block approach that bitcoin uses is what allows consensus to be reached. there isn't another known method.
556 2014-08-11 20:14:21 <pouta> Sorry if I explained in a bad way
557 2014-08-11 20:14:28 <pouta> What I'm trying to say is
558 2014-08-11 20:14:50 <helo> bitcoin basically already does what you mention, as far as i can tell. aside from "all the nodes use the same version", as that isn't in practice possible.
559 2014-08-11 20:14:53 <pouta> right now the miners ask nodes for unconfirmed transations right?
560 2014-08-11 20:16:01 <helo> right. many/most unconfirmed transactions are forwarded around the network to most nodes before they are seen in a block.
561 2014-08-11 20:16:07 <pouta> yes
562 2014-08-11 20:16:26 <pouta> so, the miners get to choose witch transations they should include in a block
563 2014-08-11 20:16:57 <pouta> Mining involves a lot of money so ofcourse miners want to make the most profit out of it
564 2014-08-11 20:17:20 <pouta> that lead to miners putting less transactions in each block
565 2014-08-11 20:17:29 <pouta> in order to make it propagate faster
566 2014-08-11 20:18:24 <pouta> my solution is instead of them choosing witch to include we should let nodes decide since they dont get any benefit from bigger or smaller blocks.
567 2014-08-11 20:18:42 <pouta> and ofcourse miners still verify them and all that
568 2014-08-11 20:22:44 <helo> i don't see how that could work. it would be like employees choosing how much they get paid instead of the company's owners/administration. a massive "tragedy of the commons" problem is created.
569 2014-08-11 20:24:34 <pouta> why is that?
570 2014-08-11 20:25:00 <pouta> nodes dont get any money from mining, they have 0 interest to block certain transactions
571 2014-08-11 20:25:03 <helo> nodes want to pay low fees, miners want them to pay high fees. if nodes get to choose, the miners will starve.
572 2014-08-11 20:25:23 <pouta> and as of right now we have to trust nodes allready, at least a majority of them
573 2014-08-11 20:25:44 <pouta> why nodes want to pay low fees=
574 2014-08-11 20:25:45 <pouta> ?
575 2014-08-11 20:25:49 <pouta> i didnt know that
576 2014-08-11 20:26:31 <helo> nope. we trust that the majority of the mining power is not under the control of one entity, or that there is some diversity in the source of blocks.
577 2014-08-11 20:27:34 <pouta> really? TIL
578 2014-08-11 20:28:05 <pouta> can you tell me why nodes would gain in starving miners?
579 2014-08-11 20:28:10 <helo> pouta: nodes are users that want to send bitcoin. miners are nodes that want to mine bitcoin.
580 2014-08-11 20:28:11 <pouta> what*
581 2014-08-11 20:29:08 <gmaxwell> pouta: this doesn't belone in this channel, you'll get better help in #bitcoin
582 2014-08-11 20:29:44 <pouta> I'm not trying to get answers about bitcoin
583 2014-08-11 20:29:52 <pouta> I can search online just fine
584 2014-08-11 20:29:54 <helo> (listen to gmaxwell)
585 2014-08-11 20:30:13 <pouta> I'm here because you guys surelly know the protocol better then me
586 2014-08-11 20:30:21 <helo> so does #bitcoin
587 2014-08-11 20:30:26 <pouta> Yes
588 2014-08-11 20:30:52 <pouta> but you guys can tell me why that would not work
589 2014-08-11 20:32:01 <gmaxwell> pouta: because it's confused about exactly what the challenges bitcoin is solving are... you'll very likely get helpful answers in #bitcoin
590 2014-08-11 20:33:38 <pouta> I joined here because I though #bitcoin is more about general discustion about the protocol
591 2014-08-11 20:34:06 <pouta> and this channel more about developing for the protocol and/or sugest new Ideas in a informal way
592 2014-08-11 20:34:26 <gmaxwell> pouta: Please go to #bitcoin-dev?
593 2014-08-11 20:34:30 <gmaxwell> er #bitcoin
594 2014-08-11 20:34:44 <pouta> sure thing, no problem
595 2014-08-11 20:37:53 <patxanxa> You guys should update the topic. It still has mtgox in it
596 2014-08-11 20:38:46 <gmaxwell> patxanxa: it's there to stop people from asking about mtgox's failure, it wasn't there while mtgox was in service IIRC.
597 2014-08-11 20:39:09 <patxanxa> Oh, ok
598 2014-08-11 20:39:13 <patxanxa> Thanks