--- Log opened Mon Dec 09 00:00:42 2013
00:32 < amiller> lol.
02:41 < wumpus> hahaha nice gmaxwell
03:31 < wumpus> gmaxwell: so does that actually generate keys, convert to an address, create a qr code, and match to some target image or so?
03:33 < wumpus> or is the actual information in the qr code not important and it just makes use of the redundancy in the representation?
03:43 < maaku> wumpus: i would assume it's making use of redundancy, just from visual inspection
03:46 < wumpus> maaku: it seems that way,  just found the paper: http://dl.dropboxusercontent.com/u/12405967/qrsem.pdf
03:47 < wumpus> I suppose that if one generated vanity keys one could get even closer to the target image, but it's not needed for the effect at all
03:48 < maaku> yeah that's why i figured it was redundancy
03:48 < maaku> it could have been a cleaner image without
03:48 < maaku> er, with a vanitygen approach
06:00 < michagogo|cloud> gmaxwell: Nice. (my phone couldn't read that, but zxing.org could)
14:18 < gmaxwell> hm. An interesting point about cryptocurrencies with perfect anonymity and fungibility is that they have— assuming spherical cryptography— fundimentally better scalablity.  not having privacy means communicating more information.
14:19 < gmaxwell> you could imagine a cryptocurrency based on encrypted commitments and state outsourcing where a block doesn't communicate transactions at all, just the final state commitments and proofs that they're correct.
14:20 < iddo_> what is spherical cryptography ?
14:21 < gmaxwell> iddo_: I mean with tools that achieve everything we know is theoretically possible, "spherical cow", without pratical considerations or constant factors.
14:21 < iddo_> ahh
14:21 < gmaxwell> e.g. imagine a block that doesn't carry transactions, it just commits to the final state after all transactions were applied, and proves that the updates met the rules.
14:22 < iddo_> so with anonymous cryptocurrency, you mean that it's less communication complexity, but more computational complexity locally?
14:24 < gmaxwell> well I'm ignoring the complexity of the proof systems, in theory SNARKS can give quasi linear work on the prover, and constant communication and verifier complexity or similar efficiency.
14:24 < iddo_> gmaxwell: why did you say several days ago that Bitcoin mining power is about 2^74 now? i see about 64 leading zeros in the PoW hash of blocks now, isn't that 2^64 complexity?
14:24 < eristisk> So, a distributed blockchain model where the data contained within the blocks would be of much smaller size because of the the intentional absence of the bulk of the transaction data... wouldn't miners that solved the block still see the entire contents of the transactions?
14:24 < gmaxwell> iddo_: aggregate vs each blocks.
14:25 < gmaxwell> eristisk: sure, but only the block they produced.
14:25 < iddo_> gmaxwell: aggregate means what in this context? all the work that has been done since the genesis block?
14:25 < gmaxwell> Maybe my point was too abstract, but I'm only pointing out that the theoretical limits of cryptocurrency efficiency can only be achieved if the cryptocurrency is anonymous... because adding identifyable information increases that communication complexity to at least linear.
14:26 < gmaxwell> iddo_: correct.
14:26 < iddo_> cool
14:26 < gmaxwell> 74.63 right now.  Smalleast hash so far is 000000000000000000028c32e6952731326747bae4be8db0f832d6eea0362050
14:26 < eristisk> Right, you'd have to have widespread miner collusion to consistently publish or backhandedly share the data in order to get all data.  The other important part you brought up is something I'd personally like to see in Bitcoin (and other "complete blockchain" altcoins) itself anyway, which is encrypted commitments.
14:28 < gmaxwell> eristisk: well, there are ways to construct this stuff so that its anonymous even against miners. Doing so has pratical engineering challenges today, but they're solvable. It also has significant political challenges.
14:28 < gmaxwell> But perhaps the point I'm making eases the political challenges: anonymity is pretty much a mandatory outcome of optimal efficiency.
14:29 < iddo_> politicians care about efficiency ? :)
14:29 < zooko> Uh, did you just say "spherical cryptography" ?
14:29 < zooko> What's that?
14:30 < zooko> Oh, someone already asked.
14:30 < eristisk> It could be argued that there is space enough for a model as Bitcoin exists today (accelerating technological burdens of the large distributed data set notwithstanding) as well as an altcoin which successfully implements fully encrypted transport streams between nodes as well as transactionless blockchains as you are speaking of.
14:31 < gmaxwell> like a spherical cow, sorry. :) I just am talking about the theoretical asymptotic efficiency. The pratical implementations of the required tools are not there yet.
14:31 < gmaxwell> eristisk: money likes a monopoly.
14:31 < eristisk> More like: people like a money monopoly  :P
14:32 < gmaxwell> And confidence in cryptocurrencies probably depends on a reasonably high degree of stickyness.  "Why do I want your foo coins when next year bar coins will be the new hotness?"
14:33 < iddo_> thing about zerocoin is that CRS is exactly the kind of thing that people who are attracted to zerocoin don't like... i already see thread on that http://www.reddit.com/r/ZeroCoin/comments/1rxwvh/zerocoin_has_a_master_key/
14:33 < gmaxwell> So yea, sure alternatives can and will exist... but I suspect that in enough time, as the engineering tradeoffs mature and stop being tradeoffs anymore it will just become a no-brainer to do thing like use snarks to compress bitcoin... and at the limit you end up making it anonymous even if that wasn't your goal.
14:33 < gmaxwell> iddo_: yea the CRS stuff is ... not good. But it's not fundimental.
14:34 < gmaxwell> we know from theoretical work that publically verifyable non-CRS sub-linear communication cost SNARKs can exist.
14:35 < iddo_> yes:)
14:35 < eristisk> Ah I see.  Well, encrypted commitments could be added to Bitcoin with reasonably smaller fundamental changes in comparison to rewriting the protocol spec to remove transactions from the blockchain data.  I get your point about "selling" it under the premise of solving the spiralling problem of storing such an increasingly massive distributed dataset whilst simultaneously arriving at a more...
14:36 < eristisk> ...anonymous system architecture, but wouldn't such a large change in the protocol be extremely difficult?
14:36 < gmaxwell> Well, not just selling. I don't mean that there is room for pretext... that I think if you optimize for scalablity OR privacy you end up with the same system.
14:37 < eristisk> You'd also make RMS happier.  :)
14:37 < gmaxwell> eristisk: In practice everything is difficult.
14:37 < gmaxwell> s/pretext... that I think/pretext... I mean that I think/
14:38 < gmaxwell> e.g. in either case you end up with a system that does state commitments and then succinct proofs that the state updates were faithful.
14:39 < eristisk> In my admittedly imperfect understanding of how that might be implemented exactly, it would seem that the blocks would have 'metadata' about the transactions to proove that they were valid instead of transaction data itself.
14:39 < gmaxwell> and you learn nothing about the details of the transactions, except that which is disclosed by the final state as compared to the prior state... (meaning you lose all the information about transactions chains that happened entirely in a block)
14:40 < iddo_> with headers-only sync, Bitcoin blocks also wouldn't contain transactions, just txid hashes ?
14:41 < gmaxwell> eristisk: No, they don't... :)
14:41 < gmaxwell> iddo_: no, headers are just the 80 byte bitcoin headers.
14:41 < gmaxwell> no txids.
14:42 < iddo_> gmaxwell: but we could have blocks only with the txids, and miners keep locally the txns themselves (and transmit txns to peers upon request) ?
14:42 < gmaxwell> eristisk: so some quick background. It's possible to construct cryptographic proofs that a given output was the faithful product of running a specified program on a specified input (along with additional private inputs, optionally).
14:42 < gmaxwell> iddo_: filtered blocks can do that, via the bloom filter stuff with just a trivial set.
14:43  * eristisk goes back to study the byte map of transactions to try to figure out what could realistically be ommitted in a state outsourcing system
14:43 < gmaxwell> eristisk: everything can be omitted.
14:43 < eristisk> I suppose so... kind of the point of hashing algorithms.
14:44  * nsh is dubious
14:44 < iddo_> gmaxwell: is it the devs plan to incorporate filtered blocks to Bitcoin in the future?
14:44 < gmaxwell> iddo_: it's already there, for over a year.
14:44 < iddo_> oh?
14:45 < iddo_> satoshi client already sends blocks without txns? and txns separately upon request?
14:45 < gmaxwell> iddo_: it's not used for fetching between bitcoind nodes, someone ought to do some testing to show if its actually faster once you consider the overhead of sending txids and the roundtrip latency.
14:45 < gmaxwell> iddo_: it can, if you ask it to.
14:45 < iddo_> cooool
14:45 < gmaxwell> eristisk: if you finish the prior block with a commitment to— say, in bitcoin today,— the UTXO set.  Then you can have a program that takes in a prior utxo root hash as a public input, and then a bunch of transactions and utxo fragments as private inputs.. and it gives a public output as the new root hash of the utxo set.
14:47 < gmaxwell> and then a proof of this program's execution can be attached to the blocks. (and proofs can be constructed which are sublinear in the programs execution— even constant just constant depending on the security parameters)
14:52  * nsh frowns
14:52 < nsh> there's a catch
14:52 < nsh> i'm pretty sure there's a catch...
14:53 < eristisk> ...essentially replacing the bulky transaction data itself with different data in the blocks containing the proofs of the cryptographic solution in the form of the new root hash to be used as public input for the next unsolved block?
14:55 < gmaxwell> eristisk: right. plus the extra data needed in the final state. e.g. if this was dones directly to bitcoin today it would be new utxo created, and the data required to remove the old utxo. But intermediate ones (created and destroyed within a block) are not ever communicated.
14:56 < eristisk> Very large pools could analyse and save significant amounts of transactions in secret, however.
14:56 < gmaxwell> There have been some proposed blockchain redesigns that would reduce that further.
14:56 < gmaxwell> eristisk: perhaps, but you still don't know whats happening in blocks created by other parties.
14:57 < gmaxwell> (these same techniquies can be applied to transactions themselves, and then you get what the zerocoin people are going to propose in their update. I'm just raising the level you do the proofs at to the whole block instead of the transactions.
14:57 < nsh> gmaxwell, i'd sure like to see some toy model of SNARK proof verification in aciton over a distributed system
14:58 < nsh> because i just can't shake this niggling feeling that there's a catch...
14:58 < gmaxwell> nsh: go grab the pantry stuff then.
14:58 < nsh> pantry stuff?
14:58 < gmaxwell> nsh: oh there are all kinds of _pratical_ engineering catches right now.
14:58 < gmaxwell> But the only fundimental catch is that you only get cryptographic soundness, not perfect soundless like bitcoin has now.
14:59 < nsh> modulo what assumptions?
14:59  * nsh checks https://github.com/srinathtv/pantry/
15:01 < gmaxwell> nsh: you can construct these things out of serveral different cryptographic assumptions. Including ones that basically just depend on the existance of one way functions. (though those do not achieve optimal effiency so far)
15:01  * nsh nods
15:02 < nsh> ;;google knowledge-of-exponent assumption
15:03 < nsh> http://crypto.stackexchange.com/questions/6117/how-much-do-we-trust-kea1-assumption
15:05 < gmaxwell> nsh: the real catch in the system used behind that has nothing to do with KEA1 (and really what you'd need to ask about is just crypto in bilinear groups more than N-th power KEA)
15:06 < nsh> hmmm
15:06 < gmaxwell> it's that it's only publically verifyable in the CRS model— e.g. there is a trusted magic value that everyone needs to be using.
15:06  * nsh reads amiller's post http://comments.gmane.org/gmane.comp.file-systems.tahoe.devel/7942
15:06 < gmaxwell> But as mentioned, it's possible to build such systems without that limitation. (though the proofs are not as insanely small in the things people have been coming up with)
15:07  * nsh nods
15:09 < nsh> can you formalize the argument that privacy is in some way proportional to communicative efficiency in a system of distributed ledger (or more generally a distributed many-party-input dataset)?
15:10 < nsh> it makes sense intuitively that there's an overhead to bearing deanonymising information
15:10 < gmaxwell> nsh: probably. I mean, I gave the adhoc outline of the argument... right.
15:10 < nsh> but it's be nice to think about it more mathematically perhaps
15:11 < nsh> oh, i wonder
15:11 < nsh> if you can apply a thermodynamic analysis to the system
15:12 < nsh> with information that can be destroyed/discarded without affecting the security of the system being analogous to waste heat
15:12 < gmaxwell> there is a counting argument.
15:12  * nsh nods
15:13 < gmaxwell> There are many ways to get from state A to B. An anonymous system doesn't care which one you take, an non-anonymous system does.
15:13 < nsh> right
15:14 < nsh> all we care about is certain rules about the traversal from the space of A to the space of B
15:14 < nsh> not the exact paths
15:15 < nsh> so the compression/succinctness is a product of symmetries defined by our agnosticism
15:15 < gmaxwell> probably easier to just compute the entropy of the deanonimizing information and say you save that.   Though it's a little more complicated:  if a coin used these states and proofs approach it would also compress away a bunch of non-anonymity related overhead.
15:15 < gmaxwell> And so you'd just get the anonymity savings as a side effect
15:15 < nsh> oh, hmm
15:16 < nsh> what other overhead is saved?
15:16 < jtimon> gmaxwell it seems to me that Peter todd's proposal for an inputs-only chain would be both more scalable (because miner's validations become simpler) and more private (because no miner gets full transactions)
15:16 < jtimon> at least more "spherically scalable"
15:16 < gmaxwell> jtimon: it's orthorgonal! ideally you combine these things. The proofs prevent linear complexity from signatures, the MMR stuff keeps the state space minal.
15:16 < jtimon> but the problem remains, why would miners mine in such a system
15:17 < gmaxwell> (thats also why I kept qualifying above as "if we were to do this as bitcoin is today")
15:17 < jtimon> yeah, I mean combining his proposal with full-block snark
15:17 < jtimon> I se
15:17 < jtimon> e
15:17 < gmaxwell> nsh: e.g. there are 2^big ways to satisfy a typical scriptpubkey.
15:17 < gmaxwell> nsh: which of those you used would be hidden.
15:17 < nsh> oh, right
15:18 < nsh> there are advantages to script transparency though
15:18 < nsh> for contracts, etc.
15:18 < gmaxwell> nsh: sure, but you can make them transparent directly between the users.
15:18 < nsh> right
15:19 < gmaxwell> No system that discloses the transactions can have better than linear scalablity in the size of new blocks for full nodes. ... 'cause you recieve data per transaction.
15:19 < gmaxwell> instead you use some snark and you end up with sublinear communications and validation complexity. The larger the system the bigger the advantage.
15:20 < nsh> but there is some preprocessing cost, or something
15:20 < gmaxwell> there are constants.
15:20 < jtimon> yeah, that would be the scalability vs centralization tradeoff
15:20 < gmaxwell> jtimon: I don't think there is.
15:21 < jtimon> you say the bigger the system the bigger the advantage
15:22 < jtimon> wouldn't a system that processes 1 M tx per snark block imply more centralization than one that only processes up to 100 tx/block?
15:22 < gmaxwell> jtimon: I don't see why?
15:23 < gmaxwell> just talking about the miner's computational costs?
15:23 < jtimon> because there are less computers in the world capable of validating that number of transactions?
15:24 < gmaxwell> jtimon: okay, but then just don't produce a block with 1M transactions.
15:24 < gmaxwell> the snarks mean that the verifiers cost is not related the block size (or at least sublinear, perhaps constant)
15:25 < jtimon> ok, I could only process 100 tx, but then I won't be able to compete with miners that do produce 1M transactions
15:25 < gmaxwell> 'compete'? in any case, to the extent thats true you can still cap blocks
15:26 < jtimon> that was my point
15:26 < jtimon> by compete I mean earning "equivalent fees" as the other miners for the "same" pow
15:27 < nsh> oh, hmm
15:29 < jtimon> so the cap on transactions per block would be to defend p2p-ness against scalability
15:30 < gmaxwell> jtimon: not just that, in bitcoin we need some reason for the fee to be >1e-8 btc. :P
15:31 < jtimon> well, divisibility can be improved
15:31 < gmaxwell> jtimon: but at least such a change would make it so that someone _else_ producing enormous blocks didn't keep non-miners and smaller from validating... so the impact is reduced.
15:31 < gmaxwell> jtimon: that wasn't my point. for the system to be secure we need the pow to be many orders of magnitude more expensive that validation
15:31 < gmaxwell> otherwise the validation is most of the operating cost, and an attacker that just mines a few doublespending txn has an advantage. :)
15:32 < jtimon> oh, I see
15:33 < gmaxwell> an interesting point would be to have a cap only on fee paying txn, but sadly people would pay fees "out of band" :)
15:33 < jtimon> well, there's also demurrage, but now I get your point
15:34 < jtimon> hmm, so there's really no way to cap transactions
15:34 < gmaxwell> jtimon: hm? sure there is— it can just be part of the proof.
15:34 < jtimon> oh, sure
15:35 < gmaxwell> though "writes to the spent coin list" or something might be a better capacity metric in a system that has been MMR compressed.
15:36 < jtimon> I'm not sure I understand MMR but it's basically a tree structure for the utxo, like mmaaku's but with other properties, no?
15:36 < jtimon> maaku's
15:39 < jtimon> on the inputs-only proposal, I know petertodd wanted "pow fees" for anti-spam, but does anyone know if he had something in mind for miner's rewards?
16:01 < andytoshi> it seems like i missed a very cool conversation about entropy of identifying information..
16:01 < andytoshi> if there are no complaints i'll set up a cronjob to publish logs for this channel
16:01 < andytoshi> andytoshi-logbot has been recording for a few days now, seems to be working..
16:02 < nsh> +1
16:02 < andytoshi> ok, lemme just finish catching up on the logs in secret :}
16:06 < andytoshi> http://download.wpsoftware.net/bitcoin/wizards/
16:07 < Emcy> how many 'official' places does dev discussion happen now
16:07 < Emcy> at least 2 irc hcans i know of, the sourceforge list, the github list
16:08 < Emcy> which one is the 'source of record' as it were, if the aim is transparency
16:10 < andytoshi> is there a github mailing list? it seems like github links you to sourceforge..
16:11 < phantomcircuit> no there isn't
16:11 < phantomcircuit> the mailing list is sourceforge
16:11 < phantomcircuit> the issue tracker is github
16:12 < Emcy> the github threads system seems like you can email in and out of it
16:12 < Emcy> probably wrong to call it a list
--- Log closed Tue Dec 10 00:00:45 2013