--- Log opened Tue Jul 16 00:00:05 2013
--- Log closed Tue Jul 16 06:14:42 2013
--- Log opened Tue Jul 16 06:15:12 2013
16:28 < gmaxwell> oh, hey, doing non-interactive cut and choose would let you do things like reasonably compact 1024 of 2048 multisig transactions via (sufficiently powerful) script.
16:31 < gmaxwell> e.g. the pubkey commits to a hashtree of M allowed voters (h1),  the signature provides a hashtree (h2) over N approving voters, signatures for a sufficient number of voters selected via CSPRNG from (h2), and the connecting hashtrees.
16:33 < gmaxwell> e.g. a 128 bit security 1024 of 2048 could be done in about 9.5kbytes.
17:42 < petertodd> Nice!
22:53 < petertodd> Note though, this only works in scenarios where creating the signature is expensive/one-time, otherwise there's no cost to keep trying until the cut-n-choose gets lucky,.
22:54 < petertodd> So you could do a two-stage tx in this method, if committing to a signature provably costs you something. (like fees paid to a miner in the future)
22:55 < gmaxwell> petertodd: you don't have to— if the cut and choose picks enough points you will expect to do >2^128 (or other security parameter, your choice) hash operations before you get one that only picks your chosen values.
22:57 < gmaxwell> obviously it creates some slop right around the threshold, I suppose it would be better for things that required a supermajority.
22:58 < petertodd> gmaxwell: yeah, I'm thinking those edge cases where that's much harder, or for sets that aren't all that large
22:58 < gmaxwell> yea, if the set isn't that large acceptable security starts demanding you provide all the signatures.
22:58 < petertodd> what's the equation for hash functions required vs. proof size exactly? I seem to remember it's not all that forgiving in many cases
23:11 < gmaxwell> It actually works out less well than I thought, because the probablity that the hidden set does not contain a opposing voter drops off much less rapditly than the probablity that it contains only one supporting voter.
23:13 < petertodd> yeah, I worked it out for trying to do NI cut-n-choose on sacrifice proofs and it was ugly
23:17 < petertodd> idea I had: do a partial UTXO set mode where you build the UTXO set based on what txouts you have verified, starting at the most recent block
23:17 < petertodd> it's interesting, because you can then validate transactions that spend from that partial set with good confidence
23:18 < petertodd> hence such nodes can safely relay transactions and be useful to the network, and over time download enough blocks to become full nodes as well
23:18 < petertodd> makes for a nice SPV->partial UTXO->full node progression
23:19 < petertodd> the scary thing though is you could safely mine in this mode as well... safe from your perspective anyway
23:19 < gmaxwell> e.g. for the probablity that your revealed values are the only good ones: product(1/(1024-x),x,1,13)<=1/2^128  which is good, but the "are no false ones" can never have a probablity better than 1/(n-1).
23:20  * Luke-Jr ponders why petertodd's remote didn't update with --all :/
23:20 < petertodd> Luke-Jr: my remote?
23:20 < Luke-Jr> petertodd: on github. probably their fault
23:20 < petertodd> Luke-Jr: ah, what code are you interested in?
23:21 < Luke-Jr> petertodd: preparing to do another next-test spin
23:21 < Luke-Jr> so.. everything
23:21 < Luke-Jr> well, everything there's an open pullreq for anyhow :x
23:22 < Luke-Jr> hmm
23:22 < petertodd> Luke-Jr: heh, the mempool rewrite is partial, I only did the pull-req because I wanted to run the pull-tester against it... :P
23:22 < Luke-Jr> petertodd: well, at least this way you'll annoy me and get a rant if it breaks gitian? :p
23:23 < petertodd> Luke-Jr: heh
23:23  * Luke-Jr dunno why the pulltester doesn't use gitian yet
23:23 < Luke-Jr> second --all found codeshark's not updated either
23:23 < Luke-Jr> stupid git
23:24 < petertodd> oh, reminds me, so in the mempool code, I created a CMemPoolTx subclass of CTransaction and use that subclass to store the extra mempool-related data - is that considered good C++ practice?
23:25  * petertodd hasn't done serious C++ programming since highschool.
23:25 < Luke-Jr> petertodd/correct-isfinal-isstandard and discourage-fee-sniping need rebase
23:26 < Luke-Jr> petertodd: bad in our case, at least - the transaction should be capable of being in multiple distinct mempools
23:27 < petertodd> I wanted to avoid that additional layer of indirection - leads to some ugly code
23:27 < petertodd> you'd need to do ref counting too in that case
23:28 < Luke-Jr> good thing boost has pointers to handle that for us <.<
23:28 < Luke-Jr> side rant about rebasing: it prevents anyone from maintaining a real fork of the codebase
23:28 < petertodd> I know, but from what I see we've avoided those constructions everywhere else
23:28 < Luke-Jr> effectively forces centralization on the project
23:29 < petertodd> Luke-Jr: IMO not relevant here because we're talking about code that is getting changed drasticly as the pull-req evolves
23:30 < Luke-Jr> petertodd: sometimes. most of the time the rebase is just to adapt to the upstream
23:30 < Luke-Jr> and even then, those changes could be additional commits on top
23:30 < petertodd> Luke-Jr: I think more interesting is what litecoin is doing, rebasing all the 0.7->0.8 changes, where they probably could have done a merge
23:31 < petertodd> So what's your usecase for multiple distinct mempools anyway?
23:33 < Luke-Jr> petertodd: I do that every other month. It's possible, but a real pain.
23:33 < Luke-Jr> petertodd: I wouldn't want to actually *maintain* a client based on it.
23:33 < Luke-Jr> no use case. just proper abstraction
23:34 < petertodd> hmm, well when that case comes up changing things would be a fairly mechanical patch
23:35 < petertodd> more generally it shows how a more functional style would make sense here - we keep on recomputing tx hashes because tx's are mutable
23:37 < petertodd> gmaxwell: so is this partial UTXO mode scary enough that you'd rather not see it happen or what? I figure long-term we need UTXO posession proofs for miners, and it pushes decentralization by making it easier to run a full-node
23:38 < petertodd> gmaxwell: I really like how it lets those nodes do useful work for the network - relaying tx's increases your anonymity set, and they can serve SPV nodes just fine
23:39 < petertodd> gmaxwell: heck, add a way to make bogus tx's expensive and they can even relay any transaction, or just rely on how the proofs that a tx was bogus just give the partial-UTXO holders information they would have retrieved later anyway
23:39 < petertodd> (needs a relatively expensive *spent* UTXO map, but that map can be distributed)
23:39 < gmaxwell> I don't see why it would hurt.. but if there were a committed utxo you could relay any transaction just by getting the membership proofs for its inputs.
23:40 < petertodd> gmaxwell: yes, that too, and it'd lead to a mode of use more applicable to adding committed UTXO later
23:46 < Luke-Jr> petertodd: should I post "needs rebase" to all your open pullreqs that need it, or can I just make you a list here? ☺
23:47 < petertodd> Luke-Jr: nah, add it to the pullreqs
23:47 < Luke-Jr> k
23:51 < petertodd> Luke-Jr: nLockTime rolling for mining - what timespan do miners actually change the timestamp when doing this?
23:51 < petertodd> Luke-Jr: er, nTime rolling...
23:51 < petertodd> Luke-Jr: and is time rolling now obsolete?
23:52 < Luke-Jr> petertodd: in practice, I'd say it varies :/
23:52 < Luke-Jr> time rolling isn't obsolete, but not implemented with stratum yet
23:52 < petertodd> Luke-Jr: we talking seconds, tens of seconds? minutes?
23:52 < Luke-Jr> it's somewhere near the top of my BFGMiner todo
23:52 < Luke-Jr> petertodd: I would be surprised if ntime was off by more than 5 minutes
23:52 < petertodd> huh, I thought it was actually common
23:53 < Luke-Jr> stratum regressed a lot of progress that had been made with getwork :/
23:54 < petertodd> I was thinking it could be interesting to do a high-resolution timestamping facility by taking the best pow known for every second basically
23:54 < Luke-Jr> well, you might still get a lot of variety from fast pools
23:55 < petertodd> Yeah, it's no good if people need time rolling.
23:55 < petertodd> (although another non-rolled header could be acceptable)
23:57 < petertodd> See, it'd be possible for nLockTime w/ time-based locks to create some really ugly incentives for miners to mine blocks at thelimit of the 2hr window - a timestamping chain could provide a way for nodes to at least detect that their clocks are off, especially given how peers can mess with them.
23:58 < petertodd> It's still dodgy though... I was thinking if nLockTime-by-time inclusion was based on the previous block timestamp it'd be ok, but that still leaves large miners with incentives to screw with the 2hr window, never mind how it can reduce competition if there exists clock skew in the mining nodes.
--- Log closed Wed Jul 17 00:00:57 2013