--- Log opened Sun Dec 01 00:00:22 2013
04:46 < fagmuffinz> I hear you're all smart as fuck
05:06  * gmaxwell puts on his robe and wizard hat
05:09 < Mike_B> here's a question that probably belongs here rather than #bitcoin-pricetalk... i've been thinking a lot about generalized PoW functions, and how to make sense of them from the standpoint of computational complexity. has anyone worked that out before?
05:09 < Mike_B> for instance
05:09 < Mike_B> let's say hashcash is a function hashcash(input, nonce, d), where d is difficulty, written in unary. given that definition of hashcash, it'd be in TFNP, right?
05:10 < Mike_B> sorry, to be clear, i'm envisioning d as "number of leading zeros," or something like that
05:11 < gmaxwell> right you're being clear, but you may want to repeat that in a few hours when adam3us rejoins, since I'm sure he'll be interested too. :)
05:11 < Mike_B> so that brute forcing a solution is O(exp(d)), but checking a solution is O(whatever SHA256 is)
05:11 < Mike_B> oh is that adam back?
05:12 < gmaxwell> (there is some interesting history on hashcash about the target, apparently the idea of just using a trivial preimage was a later idea... IIRC from comments adam made in the past)
05:12 < gmaxwell> Yea.
05:12 < azariah4_> Mike_B: it would depend on the algo in question though, not sure how much one can say about it in the generalized case
05:13 < Mike_B> gmaxwell: yep, i read the hashcash paper and i saw where he talked about someone suggesting later to just use x leading 0s
05:13 < gmaxwell> well if you want to talk about the difficulty of partial preimages, I suppose the complexity depends on the distribution of the values. e.g. I can give you a constant time hashcash, the hash function always returns all zeros, for example.
05:13 < azariah4_> in general hash functions have 2^B where B is number of bits to brute force and constant time to verify
05:14 < azariah4_> though technically its not constant I guess, but also depends on number of bits, which is just constant on modern CPU archs if e.g. the number of bits fits in 2 words
05:15 < Mike_B> gmaxwell: yeah, i guess i'm making the assumption that the probability distribution for which things hash to which SHA256 hashes is totally flat
05:15 < Mike_B> (i could formalize that nicely with natural density if you like)
05:16 < Mike_B> but i suppose it could be the case that SHA256 doesn't have anything hashing to less than a certain max value, so that if difficulty is less than that, hashcash will never halt
05:16 < Mike_B> azariah4_: yes i agree
05:17 < gmaxwell> Mike_B: right, and we can't prove otherwise, though structurally it seems really really unlikely (esp for bitcoin where we do have >256 bits of input to the process)
05:19 < gmaxwell> (random aside: I read a neat paper a while back where they show how to use error correcting codes to efficiently solve hamming distance threshold paritial collision problems efficiently by searching for partial preimage collisions on a coded version of the output.)
05:20 < Mike_B> what do you mean by partial collision problems here?
05:20 < Mike_B> like two strings whose hamming distance is less than some threshold?
05:20 < gmaxwell> Mike_B: yes.
05:21 < Mike_B> hmm, interesting
05:22 < gmaxwell> (http://eprint.iacr.org/2012/731.pdf)
05:25 < Mike_B> very neat
05:25 < Mike_B> another paper for me to wade through :)
05:26 < Mike_B> there's also this i found, which relates to the question i was asking earlier
05:26 < Mike_B> http://www.hashcash.org/papers/bread-pudding.pdf
05:26 < Mike_B> so i assume adam already knows about it :)
05:26 < Mike_B> seems to classify proofs of work
05:50 < TD> good morning
07:41 < azariah4_> reading the WP article about commitment schemes, I was suprised to not see hashing as a example
07:42 < azariah4_> e.g. if alice creates hash = SHA-256(foo_msg) and gives it to bob, she has commited to foo_msg without revealing it, and can later reveal it for checking
07:43 < gmaxwell> azariah4_: it may be because cryptographic protocols which are 'merely' secure in the random oracle model are somewhat out of fashion with academic cryptographers.
07:46 < azariah4_> ah yeah, to get perfect binding in a commitment scheme using a hash requires that the hash is a perfect hash function
07:46 < azariah4_> well, the article does mention signature schemes
07:47 < azariah4_> No real function can implement a true random oracle.[citation needed]
07:47 < azariah4_> WP <3
07:48 < gmaxwell> The other aspect of that is a lot of fancy things are built effectively out of commitment schemes that have extra properties like certian kinds of homorphism or proofs... so non-symetric commitment schemes are generally more interesting because they do have these properties.
07:50 < azariah4_> ah
07:50 < gmaxwell> I'm not a big fan of loss of love for the random oracle model, much of that is driven by a set of papers that show you can have a a protocol which is secure in the random oracle model but not secure in practice... and in fact cannot be secure with _any_ real hash function in place of the random oracle.  Anything (so far) know to do this is totally contrived, but it's created an excuse to avoid proofs based on reduction to random oracle.
07:51 < gmaxwell> s/know/known/
07:51 < azariah4_> aha, interesting
07:52 < azariah4_> going through some ZKPs examples which uses commitment schemes
07:53 < gmaxwell> ...personally I'd usually take a well studied hash function and a proven secure in the random oracle model protocol over something depending on gap-dh.
07:54 < gmaxwell> azariah4_: yea, some of the most powerful ZKP stuff is basically a special kind of homorphic hashing where you can hash encrypted 'wire' values in a circuit and still apply the tests that the circuit is satisfied. ... and then hash this validation itself and so on.
08:22 < TD> gmaxwell: what kind of schemes are secure in ROM but not when instantiated with a real hash function?
08:39 < gmaxwell> TD: there are a couple layers to it they start with a contrived scheme where you take a regular secure signature scheme and then wrap it
08:40 < gmaxwell> with a if (messsage,oracle(message)) ∈ table then return secret key.
08:40 < gmaxwell> and then modify the verifier to also accept for that message.
08:42 < gmaxwell> and then go on to describe how to fill out the table in a way which it is computationally intractable if you use a real random oracle but possible for any real hash function.
08:42 < gmaxwell> (I don't actually recall what they do there)
08:43 < TD> ok
09:50 < azariah4_> just found the libzerocoin docs on github, awesome stuff
09:51 < azariah4_> helps understand the protocol since its from a integration point of view rather than the pure crypto/math description
09:52 < azariah4_> this in particular is quite interesting: https://github.com/Zerocoin/libzerocoin/wiki/Generating-Zerocoin-parameters
09:53 < azariah4_> so the initialization of a zerocoin instance depends on a single trusted entity
09:54 < gmaxwell> yep.
09:54 < gmaxwell> and that entity has inflation power, at least up to the total amount ever put into the accumulator (assuming the system is engineered to track that)
09:58 < azariah4_> it mentions distributed multiparty generation of the modulues however
09:59 < azariah4_> and another paper linked for that, crap
09:59 < azariah4_> feels like im going down the rabbit hole with this, too many papers bookmarked already :P
10:00 < gmaxwell> azariah4_: yes, though the state of pratical multiparty computation is sad (non-implemented, slow (quadratic communication usually), half of it is secure against only lame threat models), but ignoring that: you're still left with some cabal of parties to performed that act... tricky to not have people constantly fudding the cabal.
10:00 < azariah4_> yes indeed
10:00 < gmaxwell> e.g. you have 3 people do MPC to produce the value...  and okay, so it's two of three who people fearmonger about. :)
10:01 < azariah4_> I imagine there has been some thought about multiple instances of zerocoin to reduce the risk given a single generation of N per instance is used
10:01 < azariah4_> however anonymity is reduced if e.g. my txs are in a zerocoin instance with only 10 other people
10:02 < gmaxwell> maybe with enough resources and effort you could do a really big MPC scheme where some parties seal computers in bunkers and blow them up after the fact.. :) sort of an open question over what would be enough.
10:02 < gmaxwell> A somewhat frequent bit of FUD bitcoin gets is confused people claiming that satoshi has a master key that gets him unlimited bitcoin or the like. Fortunately these are easily shut down because you can show it impossible.
10:03 < gmaxwell> In such a scheme it's not possible to show that its impossible for a cryptographic backdoor to exist.
10:04 < azariah4_> exactly
10:07 < azariah4_> would it be insane to instead of generating 2 safe primes that multiplied gives N, generate a larger set of safe primes and multiply all together?
10:11 < azariah4_> ah, integer factorization is hardest when the integer N is semiprime
10:17 < sipa> i wonder, could you create a script system that allows outputs which 1) prevent spending before X confirmations, and 2) are able to observe the block hash of block X further
10:18 < CodeShark> you mean able to reference external state?
10:19 < sipa> well it's state that will exist at the time you're going to spend the output
10:19 < sipa> nothing external to it
10:19 < gmaxwell> sipa: I thin you can, just have a PUSH_<thing that would have been in the future>. opcode.
10:19 < gmaxwell> e.g. push it by reference.
10:20 < gmaxwell> But what would you accomplish with this? oh to prove another transaction was in the chain?
10:20 < sipa> it would allow some betting schemes that aren't vulnerable to "mining the transaction hash", and without secret state for the operator
10:21 < CodeShark> by "external" I meant outside just the input script and output script
10:21 < sipa> not sure that's something to encourage, or whether there aren't any better ways
10:22 < sipa> but you could have a script that uses H(txid + H(block_N_in_the_future)) < some_value
10:26 < CodeShark> what do you mean "mining the transaction hash"?
10:26 < CodeShark> sha256 collisions?
10:26 < gmaxwell> CodeShark: basically you use the hardness mining a block to boost the security of a random selection scheme.
10:27 < gmaxwell> e.g. output can be spent by A only if the next block hash &1==0 otherwise spendable by B.
10:27 < CodeShark> ah
10:27 < gmaxwell> sipa: on this general subject I'd like there to be a way to do a probablistic micropayment that doesn't produce any transactions when the payment fails.. which I suspect needs a similar kind of change.
10:35 < gmaxwell> (e.g. a signature which is only valid if the next, yet unknown block's hash passes a test.)
10:38 < sipa> next, or 100th following even
10:38 < sipa> if you want to prevent people mining blocks specifically to revert it
10:39 < gmaxwell> well for low value transactions you basically trust that throwing out $subsidy+$typical_fees  is much worse than losing the micropayment.
10:39 < sipa> right, sure
10:42 < gmaxwell> sipa: where is your simulation of your charts with constant hashrate?
12:07 < petertodd> jtimon: in a txin commitments system you probably have to pay tx fees with pow rather than fees per-se, though I think it'd be better if mining was forced to be more decentralized in that fashion.
12:08 < petertodd> maaku: it's not a spent-txin set, it's just a txin set - a txin implies a spend. :) seriously though, the advantage is reducing the data the blockchain actually handles - in that system the blockchain doesn't even have full transactions, hence less privacy risks and potentially better scalability
12:23 < jtimon> thanks petertodd, pow anti-spam ala hashcash is what I had thought
12:25 < jtimon> related to maaku's question, can you have SPV nodes with this scheme?
12:25 < petertodd> yup, granted, I'd *like* there to be a way for users to pay hashers to do the pow for them, but that can be a separate mechanism and can change
12:25 < petertodd> *NO*
12:25 < jtimon> yeah, outsourcing the pow would be interesting
12:26 < petertodd> remember that the whole point of SPV is you let someone else do verification for you on the principle that they're probably going to do it because of the incentives with mining
12:27 < jtimon> I thought that maybe the payer could provide the proofs necessary for the SPV recipient to validate them only looking at the current Txin set
12:28 < jtimon> so the "only first txin goes into the txin set" validation, which is the only validation done, could be enough
12:28 < jtimon> it is very possible that I'm misunderstanding something
12:29 < petertodd> right, but remember in that scheme a step back isn't verified by anyone
12:29 < petertodd> OTOH with scip...
12:29 < jtimon> sorry what was otoh?
12:30 < fagmuffinz> gmaxwell, you're full of nuggets
12:30 < petertodd> I mean, with SCIP you can prove the previous history of the txout followed the rules without providing it
12:30 < jtimon> on the other hand, ok
12:31 < jtimon> so you could actually have spv nodes with this minimized central validation
12:32 < jtimon> the main problem I see is that the TXI set grows forever
12:32 < jtimon> by "central" I meant in-chain
12:33 < jtimon> this minimized in-chain validation
12:34 < jtimon> if I understand correctly, miners only receive inputs and validate the following:
12:34 < jtimon> if it is already in TXI, do nothing, otherwise, insert in the TXI tree
12:35 < jtimon> is that right?
12:42 < fagmuffinz> Can you guys get me up to speed on hashcash?
12:42 < fagmuffinz> I'm taking it this is kind of the gauntlet for ideas
12:45 < fagmuffinz> I'm moving through Zerocoin's paper right now
12:46 < petertodd> jtimon: right, that the txin set grows forever is a problem that I need to solve in some clever fashion :)
12:46 < petertodd> jtimon: after all, I mainly wrote that as a "hey! if we do this as yet undiscussed thing we get a system with different properties!"
12:47 < jtimon> Ihehe
12:47 < jtimon> I'm not sure I understand the structure of the commited inputs though
12:47 < _ingsoc> fagmuffinz: Which one?
12:47 < fagmuffinz> http://zerocoin.org/media/pdf/ZerocoinOakland.pdf
12:48 < jtimon> miners receive independent inputs with tx_hash, output_id and another hash?
12:48 < _ingsoc> Ah, right.
12:48 < fagmuffinz> Figuring out the mechanism still
12:48 < petertodd> jtimon: well, it's indexed by the txout:n being spent, and miners store the scriptSig + rest of tx hash basically
12:51 < fagmuffinz> Digital commitments
12:51 < jtimon> so the final hash lets you identify which inputs go in the same transaction, no?
12:51 < fagmuffinz> Things I haven't heard of
12:52 < fagmuffinz> I've written a simulation of Shor's circuit
12:52 < fagmuffinz> Haven't heard of this
12:54 < petertodd> jtimon: right, so it's still a totally committed set of hashes, but miners only are ensuring that the chain can't be changed, not what's in the tx's themselves
12:54 < petertodd> jtimon: and until a txout gets spent, it has no affect on the blockchain at all and no-one but the tx holder knows it exists in any faashion
12:55 < jtimon> yes, yes, just wanted to make sure I understood the structure
12:55 < petertodd> you do, I think :P
12:56 < fagmuffinz> And it's time to spend some more time with zero-knowledge proofs
12:56 < jtimon> so what about this for the evergrowing TXI-set...
12:57 < jtimon> in the TXI tree that is hashed each block
12:58 < jtimon> when you add a new input, you also store a refHeight with the block number in which the input appeared in the chain
12:58 < jtimon> when the refHeight + X = current block height
12:59 < jtimon> that input has to be removed from the TXI data structure
12:59 < jtimon> basically, inputs only stay in the chain for X blocks
12:59 < jtimon> that could be 100,000,000 blocks, but it's still better than ad infinitum
13:00 < jtimon> holders just have to move their funds from time to time
13:01 < jtimon> hmmh, but you only answered half of the fee question...why miners mine in this protocol?
13:05 < petertodd> jtimon: heh, I don't know all the answeres yet :)
13:06 < petertodd> jtimon: but I gotta go - I'm at the darkwallet conf right now
13:06 < jtimon> ok, have fun
14:06 < maaku> jtimon: the better approach is to construct the TXI tree in such a way that no one needs (random access to) the whole structure
14:07 < maaku> then it doesn't matter if it grows forever
14:08 < warren> anyone know how long bitcointalk has been down?
14:08 < maaku> not more than an hour or two since I was just there
14:12 < jtimon> maaku, when a miner gets an input, he needs to check wether the input has already been published or not
14:13 < maaku> jtimon: yes, and the creator of the transaction could provide proof-of-not-inclusion along with the transaction
14:13 < jtimon> I don't know how can you construct the TXI tree the way you propose and still satisfy that validation rule
14:13 < maaku> so long as they maintain those proofs, the miner doesn't have to
14:13 < maaku> BUT, they do need random access to initialize the proofs for their as-yet unspent outputs when the create the transaction
14:14 < maaku> but they wouldn't if you use a merkle-mountain range
14:14 < jtimon> I got lost
14:15 < jtimon> how does the payer provide a non-inclusion proof to the miner?
14:15 < maaku> the payer provides for each input a path through the input tree showing that the input does not exist yet
14:16 < maaku> those same paths can be used to insert the input record into the tree, updating the root hash
14:16 < maaku> so the miner only has to store the root hash
14:17 < maaku> and the onus is on the payer to maintain the proofs needed to spend
14:35 < fagmuffinz> I return
14:37 < maaku> the problem, i believe, is that as presented the payer (or recipiant) has no meaningful control over the hash of the new transaction, and therefore the portion of the tree needed  for the proofs related to the new outputs
14:37 < maaku> proof-updatable UTXO trees suffer from the same problem
15:30 < HM2> ah sipa's back
15:30 < HM2> sipa, not retired yet?
15:32 < sipa> retired? :o
15:32 < sipa> maybe when i'm twice my current age or something...
15:32 < sipa> actually, not even
15:32 < Luke-Jr> lol
15:33 < HM2> Oh that's only you're well to do enough to live in to cryogenics :P
15:34 < HM2> sipa, could you remind me of your variable length integer encoding? I've been regoogling and can't come across it
15:34 < Luke-Jr> wtf, does *everyone* have their own varint encoding? :o
15:34 < HM2> Yes, but sipa's is best
15:35 < sipa> HM2: https://github.com/bitcoin/bitcoin/blob/master/src/serialize.h#L242
15:37 < HM2> ah that was it
15:37 < HM2> thanks
15:37 < Luke-Jr> why is it in bitcoind src? :o
15:38 < sipa> the chainstate uses it
15:38 < sipa> ultraprune started out as an experiment to see how small the chainstate could be encoded as
15:38 < Luke-Jr> i c
15:39 < sipa> there are some overkill things in it :)
15:39 < Luke-Jr> looks nice
15:39 < Luke-Jr> often I just abuse UTF-8 <.<
15:39 < Luke-Jr> of course, that's not remotely compact
15:39 < sipa> it is, for numbers with the right distribution :)
15:40 < Luke-Jr> sure, but not compared to yours
15:40 < Luke-Jr> or even protobuf's
15:40 < sipa> mine is for all intent and purposes the same as protobuf
15:40 < sipa> in encoding size
15:40 < sipa> but it's unique
15:40 < sipa> (and a tiny tiny bit smaller)
15:41 < Luke-Jr> oh, so you never use 0xff?
15:41 < Luke-Jr> could extend your range slightly if you did.. ;)
15:41 < sipa> it is optimal
15:41  * Luke-Jr looks at it in more detail
15:41 < sipa> every unique infinite sequence of bytes corresponds to a unique sequence on integers
15:42 < HM2> you'd have to zigzag encode it for signed ints
15:42 < HM2> right?
15:43 < sipa> yup
15:43 < HM2> but that's post/preprocess so not important at all
15:58 < HM2> hmm
15:59 < sipa> i just pushed a change to libsecp256k1 that makes it 1.3x slower :(
16:06 < Luke-Jr> why?
16:07 < HM2> sipa, timing leak?
16:07 < sipa> potential patent
16:08 < Luke-Jr> sipa: old code in #ifdef? :P
16:08 < sipa> yes
16:10 < Emcy_> who gets sued?
16:12 < HM2> #ifdef I_ACCEPT_THE_DISCLAIMER
16:12 < sipa> it's still there, via --use-endomorphism
16:40 < HM2> sipa, the commends on your serialization code are whack
16:40 < HM2> https://github.com/bitcoin/bitcoin/blob/master/src/serialize.h#L260
16:40 < HM2> 128-16511: 2 bytes
16:40 < HM2> then on line 260
16:40 < HM2> 16511: [0x80 0xFF 0x7F]
16:40 < sipa> ha!
16:41 < HM2> i thought the code was broke :|
16:44 < Luke-Jr> sipa: should be --enable-endomorphism :/
16:44 < Luke-Jr> (and will probably *need* to be to autotools it)
21:41 < Mike_B> people are panicking over this directory.io thing, i think it's hilarious :)
22:10 < midnightmagic> Mike_B: Hrm?  directory.io?
22:10 < pigeons> yeah check it out, funny
22:11 < midnightmagic> ok
22:12 < midnightmagic> ha ha ha!
22:13 < midnightmagic> "It took a lot of computing power to generate this database."
22:33 < gmaxwell> Mike_B: lol, link to panic?
22:34  * gmaxwell adds "it doesn't contain compressed keys! so if you use those you're safe!"
22:38 < Mike_B> haha
22:38 < Mike_B> it was mostly irc
22:39 < Mike_B> this guy tried to calm everyone down on reddit, but did it the wrong way: http://www.reddit.com/r/Bitcoin/comments/1ruk0z/dont_panic_directoryio_thing_is_fake/
--- Log closed Mon Dec 02 00:00:25 2013