--- Log opened Mon Jan 13 00:00:40 2014
--- Day changed Mon Jan 13 2014
00:35 < Luke-Jr> my wife and I will probably both be in Miami
01:23 < amiller> turing complete sucks as a catchphrase/soundbyte/feature
01:23 < amiller> it's a total red herring
01:23 < amiller> all sorts of interesting/expressive languages are not turing complete
01:24 < amiller> and even a turing complete language would be useless if it's not hooked up correctly to txouts and etc
01:24 < amiller> it's neither sufficient nor necessary for what anyone actually wants with a modified transaction script
01:24 < amiller> try to build a sponsored chess game, as a thought experiment
01:24 < amiller> or a poker game
01:24 < Luke-Jr> amiller: dunno, turing complete *might* make it possible to get at anything
01:24 < gmaxwell> well besides any computer with finite memory is not technically turing complete. :P
01:25 < amiller> you don't need turing complete for any of that, and also turing complete doesn't automatically make those work
01:25 < gmaxwell> Luke-Jr: but if the chess game program is so huge that you can't realistically use it... no real point.
01:25 < Luke-Jr> sure
01:25 < amiller> you could trivially make bitcoin-script turing complete by adding opeval or whatever, and it still wouldnt' solve that problem
01:25 < Luke-Jr> but I mean, to get at txout info, you *could* just confirm the transaction is part of a block etc
01:26 < amiller> that's pretty complicated, but i guess
01:26 < gmaxwell> sure and you could do that in script if substr and cat hadn't been disabled.. and without being turing complete.
01:27 < gmaxwell> and if you replaced script with, say, 8 bit AVR instructions you could do it as well, but the transaction would be so big as to be unusable.
01:29 < gmaxwell> though I looked at their codebase, and uh.. it's implementing basically bitcoin script— with a bignum as the basic type— with and added instruction pointer and jmp instruction.  Seems like someone has never worked with forth, the result is kinda unholy looking.
05:05 < gmaxwell> petertodd: you did realize why you can't encrypt your stealth addresses, right?
05:06 < gmaxwell> petertodd: (because if you do, then someone with the candidate stealth address can test if any stealth payment on the chain is connected to that one by decrypting the nonce and testing if its a valid point)
05:09 < TD> elligator?
05:10 < gmaxwell> TD: alas for this it needs to be bitcoin compatible public key, and the elegator mapping cannot work for our curve.
05:10 < gmaxwell> (can't work for curves where the x term is 0)
05:11 < TD> you can do elligator for curve25519 however, so if we switch to supporting ed25519 signatures in future, it might become workable
05:34 < nsh> gmaxwell, is it not possible in principle to have an elligator-like mapping to uniform strings from the bitcoin curve points?
05:35 < gmaxwell> nsh: the points are enumerable so it's possible to map... an efficient one? I don't know of one for our curve.
05:35 < gmaxwell> There are other ways to make bitcoin points statistically uniform.
05:35 < nsh> hmm
05:36 < gmaxwell> E.g. take your point and randomly choose a x value between it and the prior valid point... then have the reciver do the reverse process... its just a little computationally expensive.
05:36 < nsh> do curve25519/ed25519 have extra structure that facilitates efficient mapping?
05:36 < gmaxwell> Yes.
05:36 < nsh> ok
05:37 < TD> every value is a valid point, or something like that
05:39  * nsh rereads petertodd's proposal thread
05:39 < gmaxwell> well the elegator mapping achieves that. Raw curve25519 x values are only about half valid like ours. The elegator mapping isn't totally trivial either, but its not as slow as "test points until you get a valid one"
05:40 < gmaxwell> (also the elegator mapping doesn't work for all points, just a really large number of them, so you have to generate ed25519 points with that in mind if you're going to use it, which is a little annoying)
05:40 < TD> i think it's spelled "elligator"
05:40 < TD> i remember this, because i know a cryptographer called elli
05:41 < nsh> 50% of ed25519 points don't have elligator mappings iirc
05:56 < gmaxwell> http://lightspeedindia.wordpress.com/2014/01/13/bitcoin-2014-top-10-predictions/
05:57 < gmaxwell> 7. The use of Bitcoin will evolve beyond ‘store of value’ or ‘transactions’
05:57 < gmaxwell> The underlying Bitcoin protocol makes itself applicable beyond the use cases of ‘store of value’ and ‘payments’. The Bitcoin foundation took a huge step in allowing meta data to be included in the blockchain.
05:57 < sipa> note that they at least say "meta data" and not "data"
05:58 < gmaxwell> Fair. hah. they link to https://www.secondmarket.com/education/landing/bitcoin-ecosystem  ... someone should make a version of that without survivorship bias that includes all the companies that vanished with everyone's money. :P
05:59 < Ursium> Morning! (if you're in the UK and went to be late like me :)) - What do you guys think of Ethereum?
08:23 < justanotheruser> What do you guys think of ethereum?
08:40 < tacotime_> This question again haha
08:41 < tacotime_> Usually it boils down to "is including executable code in txs a good idea", but there are interesting things about it, it's moving quickly, and it looks to be very well funded.
10:20 < Ursium> tacotime_: but the fundraiser hasn't taken place yet
10:20 < Ursium> oh do you mean 'it will be well funded' ok .
10:21 < tacotime_> Ursium: There are 3+ devs hacking it right now, they have to be getting money to eat from somewhere I'd guess.  Plus the folks behind mastercoin seem to be involved.
10:22 < Ursium> tacotime_: source on the master coin link? (not questionning it's true, just curious as i'm following this very closely). As for money to eat vitalik is part of kryptokit and I don't believe he works for free :)
10:42 < petertodd> gmaxwell: ?
10:42 < petertodd> gmaxwell: what do you mean by "decrypting the nonce"?
11:34 < gmaxwell> petertodd: you suggested in your message that the nonce could be encrypted with H(stealth address)
12:11 < petertodd> gmaxwell: oh that, yeah, of course they can do that. The encryption only helps against someone who doesn't know the stealth address - that's why I said it's a minor protection
12:12 < petertodd> gmaxwell: The point of doing so is only as a incremental improvement so that all OP_RETURN uses looks semi-similar.
12:13 < petertodd> gmaxwell: oh, wait, I get your point... yeah, that's a problem
12:13 < petertodd> gmaxwell: right, and your thinking re: other ECC styles is just so that the decryption with an incorrect key should always lead to a valid - if not correct - pubkey
12:25 < adam3us> gmaxwell, petertodd: but wait u are saying c=H(eP)=H(dQ) and what encrypt r=R.x?   so r'=E_c(r) so that there is no key recovery on the signure.  hmm i am confused what are you encrypting and why?
12:28 < adam3us> gmaxwell, petertodd: or are u talking about this two point version with two inputs, Q=dG and Q2=d2G where Q2 is used only for screenin by an untrusted party and presumably the thing is a scripthash sig so the screener cant spend?
12:29 < adam3us> gmaxwell: i mean in principle if u dont know the key, you learn nothing other than you dont have the key whether the resulting point is on the curve or not?
12:29 < gmaxwell> adam3us: go see petertodd's stealth address post in bitcoin-dev
12:29 < adam3us> gmaxwell: yes i read that at the time.
12:30 < gmaxwell> He proposed, in passing, to encrypt the nonce used in the transaction with e.g. H(stealth address). This is bad because if you have a large list of stealth addresses you can test transactions to see if they might be related to one stealth address or another.
12:33 < adam3us> gmaxwell: ok so nonce is the wrong term i guess; he said "payor generates nonce keypair P=eG" less confusing to call that an emphemeral keypair.  the only nonce in DSA could arguably be k.
12:39 < petertodd> adam3us: basically something like 1 in 256 arbitrary 33 byte strings are valid ECC pubkeys, so decrypting and checking gives you a lot of statistical info that it shouldn't
12:39 < adam3us> petertodd: i did not find the encrypt with H(addr) so I dont know what you are encrypting yet, but if you are encrypting with something unknown to the attacker i do not see the attack
12:40 < petertodd> adam3us: well the stealth address is known to our attacker in my attack model
12:41 < adam3us> petertodd: doesnot the stealth address S=dP=eQ ie unknowable if u do not know d or e
12:42 < petertodd> adam3us: we're talking about the sender emphemerial pubkey, the one that goes into a OP_RETURN txout, I suggested encrypting that data so that it wasn't obvious if the transaction was or was not a stealth tx
12:42 < petertodd> adam3us: gmaxwell's point is that the encryption leaks info because you can trial decrypt, and if the result is a valid pubkey, you know you have a high probability of having guessed the right stealth addr
12:42 < adam3us> petertodd: ok as far as that goes i why dont you use one of the input addresses as the emphemeral pub key
12:43 < petertodd> adam3us: because that leaks info to the receiver about which txin did the money come from, and also makes assumptions about how you fund the tx
12:43 < adam3us> petertodd: still if its proper encryption with a key unknown to the attacker you can trial decrypt until the heat death of the universe ;) and only explore which are on the curve and not, which has a known probability distribution... and so what?
12:44 < petertodd> adam3us: the thing is in this case the attacker *does* know the key, only the weaker attacker doesn't
12:44 < petertodd> adam3us: the weak attacker is worse off, but the not so weak attacker is much better off - bad tradeoff
12:45 < adam3us> petertodd: how did u arrive at a threat model where the attacker knows your decryption key?
12:45 < petertodd> adam3us: because it's in the stealth address itself
12:52 < adam3us> petertodd: so you are talking about encrypting P the ephemeral pub key, using the hash of the stealth pub key S (presumably a diff hash than the one used to compute the stealth address as that is also public).  now S=dQ and Q is the recipients static receive addess.  and S=eP, and P=dG d is nly known to the sender.  But e is known to the recipient Q=eG.  so the recipient has a catch 22 he doesnt known d so he cant compute S=dQ, and he knows
12:52 < adam3us> petertodd: seems stuck in circular dependency
12:54 < petertodd> adam3us: the point is to hide the transaction from weaker attackers who *don't* know the stealth address, which is a valuable thing. but it's not worth it if it makes it easier for attackers who do know; there's no circular dependency there
12:55 < petertodd> adam3us: read my post again and you'll see what I mean
12:55 < adam3us> petertodd: the original post or one of the 5 followup posts? (i didnt find it yet)
12:55 < petertodd> adam3us: my original
13:01 < adam3us> petertodd: ah ok so u want to encrypt it with H(Q) not H(S).  gmaxwell had said "you suggested in your message that the nonce could be encrypted with H(stealth address)" ok so the stealth address is Q, not S, and actually I see you changed to Q' in the write up over previous IRC here.  fine.  yes gmaxwell is right.
13:02 < adam3us> petertodd: but why do you want to encrypt ephemeral pub key P at all?  to obfuscate that ths is a stealth payment?  who else makes 0 value payments to invalid addresses?
13:05 < adam3us> petertodd: "the [ephemeral] keypair [P...] is included in the transaction in an additional zero-valued output: RETURN <P>" what is that an ignored, UTXO compactible, 32 byte message?
13:29 < gmaxwell> adam3us: he wanted to obscure that it was a stealth payment maybe share anonymity set with a timestamping thing.
13:30 < gmaxwell> But no joy.
13:30 < adam3us> gmaxwell: ok hence the elligator thread.
13:32 < adam3us> gmaxwell: it a classic steganography requirement.  all decryptions must be equally plausible.  alternatively he could send P+Q and hash2curve his timestamp hashes :)
14:01  * nsh looks at this twister.net.co thing
14:33 < nsh> libboost-dev is 60Mb....
14:33 < nsh> (with all the attendant repocruft)
14:36 < nsh> wait, another 139Mb for libboost-all-dev
17:40 < gmaxwell> https://soundcloud.com/rdlmitedu/140113_0001-wav Matt Green presents Zerocoin/Zerocash at Real World Crypto 2014
17:45 < Luke-Jr> gmaxwell: is it practical now?
17:46 < petertodd> gmaxwell: they released a paper yet?
17:46 < jron> petertodd, no paper yet afaik.
17:47 < nsh> has anyone looked at how twister is using the blockchain/PoW and to what degree it's sane/scalable?
17:47 < petertodd> nsh: it's aweful, for instance there is a per-tx PoW, yet the difficulty for that PoW is hard-coded
17:47 < nsh> mm
17:48 < nsh> it is viable in principle though?
17:48 < maaku> gmaxwell: anything new presented at that talk?
17:48 < nsh> seems to be very early alpha, so maybe all kinds of silly parametric decisions/hacks
17:48 < petertodd> nsh: no, there's no incentive built into the system other than the ability to spam other users with messages... and no way to guarantee the messages will be shown in the UI
17:48 < nsh> :/
17:49 < gmaxwell> maaku: I haven't listened to it yet, I peppered jron with some questions.
17:49 < maaku> k
17:49 < petertodd> jron: pity
17:49 < jron> Luke-Jr, it sounds like the only thing they add to the blockchain is 288 bytes
17:49 < petertodd> nsh: it should have used an existing name thing like namecoin
17:49  * nsh nods
17:50 < petertodd> jron: small enough it doesn't need to be a separate chain, although my understanding is they're making it one
17:50 < jron> petertodd, correct. they are calling it "zerocash"
17:50 < gmaxwell> jron: Oh, I'm pretty sure its a bit more complex than that. At a minimum it should be their proofs plus one or two additional hash trees.
17:50 < petertodd> jron: and totally separate PoW right?
17:50 < gmaxwell> jron: Did they say anything about recovering space from old completed transactions? (e.g. analogous to pruning in bitcoin)
17:51 < jron> petertodd, there was no mention of their PoW function.
17:51 < gmaxwell> I had a couple ideas for how to achieve pruning in a zerocash like system but they all were kinda ugly and had tradeoffs I didn't like.
17:52 < petertodd> jron: heh, hopefully they'll take my advice from last summer and do a proof-of-sacrifice or bitcoin timestamped+pos for proof-of-publication
17:52 < jron> gmaxwell, there was no talk of pruning that I heard.
17:52 < gmaxwell> jron: :(
17:52 < jron> petertodd, I assume proof of sacrifice is destroying btc?
17:52 < petertodd> jron: yup
17:53 < jron> I was thinking about that on the drive home.
17:54 < petertodd> jron: basically you need to be able to securely order the transactions to solve double-spending, which is easy, and also come to consensus about what chain has the most "users" in a sense. pow is a really simple way to do both, but is vulnerable to attack.
17:54 < nsh> that soundcloud recording is 600% reverberation by weight
17:54 < nsh> :/
17:54 < petertodd> nsh: I hear it was held in a big church :/
17:54 < nsh> shame
17:54 < gmaxwell> jron: can you go compare zerocash with zerocoin for the channel?  (I know some things from private conversations that I haven't told people here which were probably disclosed in the talk, but it'll take a couple hours before I can listen)
17:58 < Luke-Jr> anyone have any legal contacts with Google?
17:58 < maaku> Luke-Jr: as in with Google's lawyers?
17:58 < Luke-Jr> maaku: yes, or anyone who can help me get Nest thermostats GPL compliant :p
17:59 < jron> I need to relisten but it sounds like they ripped out a lot of the code from libzerocoin. They also cut the proof size down from about 4KB to 288 bytes and the verification time down milliseconds.
17:59 < maaku> holy cow, $3.2 billion for a thermostat?
17:59 < Luke-Jr> maaku: it's a smartphone inside
18:00 < Luke-Jr> and right now it gives the company complete control over your home temperatrue :/
18:00 < jron> the trade of for the verification time is it takes about 2 minutes to perform a transaction in addition to the confirmation time.
18:01 < petertodd> jron: 2 min on what kind of machine?
18:01 < jron> petertodd, single core current gen
18:01 < petertodd> jron: not bad, is the computation parallelizable?
18:02 < jron> petertodd, he didn't say. I assumed it was but that is a great question.
18:02 < maaku> Luke-Jr: most effective, but asshole method for compliance is to get a blog post calling them out on the front page of HN
18:02 < maaku> it'll be fixed within hours
18:03 < petertodd> jron: if the computation can be outsourced in any way would be really interesting too
18:03 < jron> he also mentioned a large blog that is required to spend coins. the size is about 1.2 GB.
18:03 < maaku> jron: 2 minutes to *verify* a transaction, not sign?
18:03 < jron> large blob*
18:03 < petertodd> jron: is the 1.2GB akin to a private key, or some shared data structure everyone just needs?
18:03 < maaku> ok n/m reading fail
18:03 < jron> maaku, verification is sub second.
18:03 < gmaxwell> jron: sounds like he actually didn't give a lot of technical details.
18:04 < jron> gmaxwell, it was a basic overview.
18:04 < Luke-Jr> maaku: HN?
18:04 < gmaxwell> This is annoying, because I actually can answer all of these questions.
18:04 < michagogo|cloud> Luke-Jr: Hacker News
18:05 < michagogo|cloud> Luke-Jr: So I'm guessing you already saw https://nest.com/legal/compliance/ and it's incomplete?
18:05 < gmaxwell> well, in any case, I don't think I'm giving anything away that I hadn't guessed at before I'd talked to them. They're using a ZK-SNARK based on the GGPR 2012 paper,  this is the CRS-assumption pairing crypto knoweldge of exponent assumption for quadratic arithemetic programs stuff that is used in pinocchio and the tinyram papers.
18:06 < jron> petertodd, he descibes the 1.2 GB dataset as a large set of public params required to spend coins.
18:06 < gmaxwell> The proving side of this system is pretty highly paralizable. I don't know the size of the proving key, since it's polylogarithmic in the size of the circuit being proved.
18:07 < Luke-Jr> michagogo|cloud: it's missing build/install stuff
18:07 < gmaxwell> The verification key and proof sizes are just dependant on security, and you can see figures on them in the vntinyram paper: http://eprint.iacr.org/2013/507
18:07 < michagogo|cloud> ah
18:08 < gmaxwell> But presumably they wouldn't use tinyram for this, they don't need turing complete to prove some anonymous transactions. Instead I expect them to prove hashfunctions and equality, and so a custom circut could be a lot smaller.
18:09 < gmaxwell> (a straighforward implementation of SHA256 has 30k AND gates— but most (90%?) of these are in 32 bit adders, and a 32 bit adder in a QAP takes just a couple gates instead of 65 in a boolean circuit)
18:10 < jron> they did mention the use of SHA256 and SNARK to achieve the proof size
18:12 < maaku> jron: did they go into any detail about how the public params were derived?
18:13 < jron> <jron> he did mention two possible options. the first was finding as many willing and "trusted" participants to create it in a semi-distributed fashion.
18:13 < jron> <jron> the second was writing software to do it p2p but he didn't go into specifics on how that could be pulled off.
18:14 < gmaxwell> ^ that was from when I asked in #zerocoin
18:15 < gmaxwell> So yea, the problem with the GGPR ZK-SNARK is that there is a set of asymetric encryption keys and if _anyone_ knows them or finds them, then that party can trivially make false proofs.
18:16 < Alanius> I think I know what I'm reading tomorrow :-)
18:16 < Luke-Jr> gmaxwell: does someone *need* to know the private key?
18:16 < maaku> Luke-Jr: you need the private key to create the public params
18:16 < Luke-Jr> else, have lots of N people pick entropy to produce a public key for which there is no known private <.<
18:16 < maaku> so you need to trust that someone diddn't keep a record
18:16 < gmaxwell> it has to be known temporarily to generate the public keys.  At least unless you invoke some multiparty computation unicorn.
18:16 < maaku> or MPC
18:16 < Luke-Jr> so the public key can't be generated without the private key? :<
18:17 < nsh> someone needs to be trusted to forget something...
18:17 < Luke-Jr> Bernanke can do it!
18:17 < gmaxwell> At which point we're starting to recursively nest unicorns, since most efficient MPC stuff being written about works by using ZK-SNARKS to prove the players aren't cheating.
18:17 < nsh> lol
18:17 < gmaxwell> Basically the whole GGPR scheme works by reducing proving the correctness of program execution to proving you know the roots of some polynomials meeting some constraints.
18:18 < gmaxwell> What happens is that you find these polynomials and then encrypt them with the public keys produced in a prior initilization phase, and then also encrypt your roots.. And the cryptosystem has the right kind of homorphism that the encrypted roots are still roots of the encrypted polynomial.
18:18 < petertodd> gmaxwell: pity, although I'll bet you the average person won't blink an eye at the "founders could fuck it all up" problem
18:18 < maaku> gmaxwell: wait, it's a valid question - is there some way you can just use random junk for the public portion, like say the first sequence of PI bits which satisfies whatever constraint is necessary?
18:19 < gmaxwell> maaku: no.
18:19 < maaku> k, fair enough :)
18:19 < gmaxwell> Since you have no freeking clue what points the polynomial is being evaluated at, you can't generate a fake polynomial that will pass the test. but if you have the secret data you know the points and its trivial to generate a fake proof.
18:19  * maaku demonstrates is ignorance of pairing crypto
18:20 < gmaxwell> maaku: basically you can pick random keys, but they won't agree with each other, since you need to both encrypt your roots and the polynomial in such a way as the result can still be tested.
18:20 < jtimon> https://groups.google.com/d/msg/bitcoinx/EntSAsMLFck/X-7h5sgnMNoJ
18:22 < petertodd> jtimon: pragmatic, but computational crypto-coins are admittedly a lot more interesting solution to that problem
18:22 < gmaxwell> in any case, I'd really suggest sitting down and reading the vntinyram paper, — skipping over the mathy parts as you see fit.
18:23 < gmaxwell> Because the scipr-lab.org people have a public maining list, and I have an existance proof now that they respond on it. :)
18:23 < gmaxwell> (linked here: http://www.scipr-lab.org/ )
18:23 < jtimon> petertodd: I don't think I understand you
18:23 < gmaxwell> while they probably don't know anything about zerocash, they do know the backend cryptosystem.
18:24 < jtimon> petertodd: what problem you mean exactly?
18:25 < jtimon> petertodd: and what do you mean by "computatuional crypto-coins"?
18:26 < gmaxwell> Oh I linked the wrong paper earler, the vnTinyRam paper is http://eprint.iacr.org/2013/879 and it has all the benchmark figured (and I strongly believe that the verfier numbers will apply to any zerocash proposal)
18:27 < petertodd> jtimon: basically, people have proposed much more sophisticated scripting languages, to the extent that the txin scriptPubKey could constrain txout scriptPubKey's, meaning that a txout with a scriptPubKey of a specific form would be proof that the txin scriptPubKey also had the correct form all the way back to some genesis txout, thus, colored coins
18:28 < jron> someone posted some of the key points from the zerocash presentation here: http://pastebin.com/Dd60ZaT7
18:28 < gmaxwell> petertodd: Zero knoweldge computational crypto coins are even better for that.
18:29 < petertodd> gmaxwell: of course, after all, you write about coin covenents on trolltalk
18:29 < petertodd> gmaxwell: s/write/wrote/
18:30 < gmaxwell> jron: thanks!
18:30 < petertodd> gmaxwell: directly interpreted consensus systems can be upgraded to ZK systems after the fact
18:31 < gmaxwell> Yea, okay, so they point out there that the ZK based construction allows them to encrypt values to.
18:31 < gmaxwell> s/to/too/.
18:32 < gmaxwell> This is really important because it means that the anonymity set size is all transactions, not just all transactions with plausable values for you.
18:32 < gmaxwell> But it has some crazy consequences.
18:32 < gmaxwell> Like there becomes no way to even roughly gauge the size of the economy anymore.
18:33 < gmaxwell> It also interacts very poorly with the security assumptions... In zerocoin someone who compromised the magical RSA number could drain out an accumulator and steal all the coins in it. Which is bad but:
18:33 < jtimon> petertodd: I'm not sure I understand your claim yet thought, you're just saying that you prefer other colored coins schemes over this one https://bitcointalk.org/index.php?topic=253385.0?
18:34 < gmaxwell> In a system with hidden values under ZK proof a CRS compromise gives unbounded undetectable(*) inflation.
18:34 < Alanius> you could estimate roughly the size of the economy by monitoring the transaction fees
18:34 < petertodd> jtimon: no, I'm saying I prefer schemes that allow for totally generic colored coins, or anything else you might want to do
18:34 < gmaxwell> (*) well, I suppose once you personally end up with more coins in your wallet than should exist you will then believe there has been a cryptosystem compromise.
18:34 < jron> gmaxwell, hah!
18:34 < maaku> Alanius: txn fees have nothing to do with txn values..
18:34 < gmaxwell> Alanius: perhaps! but you couldn't tell if a transaction was for 1 coin or 100000 coins.
18:35 < maaku> petertodd: what does "totally generic" mean?
18:35 < Alanius> sure, but it would be pretty stupid to fee 10 coins for 1 coin's worth of actual transfer
18:35 < Alanius> hence, "roughly" :)
18:35 < maaku> it'd be a lower bound ... but probably a very low lower bound
18:35 < gmaxwell> Alanius: normally in bitcoin like systems the fees are just proportional to the data size of a transaction, since that reflects the networks actual processing cost.
18:36 < maaku> but i think you understand that :)
18:36 < gmaxwell> maaku: you could force fees to be related to value.. I suppose, though that would be an information leak, plus it would be u. You can't have it both ways, I think. :P
18:36 < sipa> Alanius: when fees are free-floating and there's an actual market around, i suppose to some extent
18:36 < petertodd> maaku: if a scriptPubKey can restrict redemption to transactions with txouts with scriptPubKeys of forms that propagate those convenants, then you can create generic limitations on how the coins can be spent
18:37 < gmaxwell> heck you could even force a kind of value information leak from transactions. E.g. force under the zk proof for you to generate a randomly fuzzed version of your txn value which you make public. And then people could gauge the average economy size without any specific transaction giving away its size... but its not clear to me if being able to size up the economy from the blockchain is actually an important enough property, kinda ...
18:37 < gmaxwell> ... weird that you couldn't though!
18:38 < petertodd> maaku: for instance a really extreme example is to create a consensus system with no concept of coins at all, that does nothing more than map H(program)->Eval(program), if the program can access blockchain data as part of it's execution, the program itself can implement a bitcoin-like currency!
18:38 < petertodd> maaku: (sorry, that's commit to (H(program), input arguments)->Eval() to be exact)
18:38 < gmaxwell> "best part of this is that you already need 16GB to store the blockchain," ... ::sigh:: this isn't true, and it's also why I was asking about pruning in zero cash. Seems that they don't realize you can prune simply because the reference software doesnt'.
18:39 < petertodd> gmaxwell: or worse, have their marketing hats on...
18:39 < gmaxwell> I don't see any easy and catch free way to get pruning into an anonymous coin though.
18:39 < gmaxwell> petertodd: nah I just don't think they know a lot of people don't.
18:39 < petertodd> gmaxwell: ugh, pruning is in the satoshi whitepaper...
18:40 < gmaxwell> you think they really read it?
18:40 < petertodd> gmaxwell: the interesting part isn't that you can do pruning, but the extent to which the fact that you can is a bad thing
18:41 < gmaxwell> in any case, for these anonymous coin ideas what you end up having to have is a database of encrypted coins which have been created, and another database of non-encrypted coins that have been spent.
18:42 < maaku> petertodd: ok, i understand the feature request now. do you know a way in which this might be implemented?
18:42 < gmaxwell> The ZK proof when you spend is of a statement like  "This decrypted coin exists in encrypted form in the encrypted coin database". And then the newly decrypted coin is added to the database of spent coins.
18:42 < petertodd> gmaxwell: though the database can be split up; you can think of both databases as cryptographic accumulators supporting VerExists() and conversely VerNoExist(), and thus get succinct proofs of either for SPV.
18:43 < gmaxwell> so you can't prune the encrypted coin database because you can't tell which entries have been spent. And you can't prune the spent coins database because then the coins could just be respent.
18:43 < gmaxwell> The coins database can be append only, but the spent coins database needs an efficient VerNoExist() so it must be key ordered.
18:44 < gmaxwell> key ordered makes it hard to outsource efficiently. (requires tracking the network)
18:44 < maaku> petertodd: if script was homoiconic it would be easier to attach a script which takes the transaction as input and outputs scripts to be attached to the outputs
18:44 < maaku> and those could be carried forward
18:44 < petertodd> maaku: well, in Bitcoin you need a very invasive soft-fork. vitalik's ethereum is in those directions, but the implementation is yuck
18:44 < Alanius> couldn't one store the spent coins in a merkle mountain range? Or am I mixing things up here?
18:45 < petertodd> gmaxwell: right, with spent that's the same problem as UTXO proofs. although you can design it so that the spent database need not be held in entirely for any one miner
18:45 < maaku> Alanius: "the spent coins database needs an efficient VerNoExist() so it must be key ordered"
18:45 < Alanius> ah, mmr'
18:45 < Alanius> s do not allow proof of non-existence?
18:45 < petertodd> Alanius: MMR can be used for unspent only, and I'm going to be very interested to find out if that's what they did
18:46 < petertodd> Alanius: they do, but the proof-of-non-existance is O(m log n) in size for a span of m blocks
18:46 < petertodd> Alanius: which you can do in zk-snark fashion, but that's costly
18:46 < maaku> petertodd: i think that's misleading from the context of his question
18:46 < maaku> Alanius: you can only prove non-existence based on what is being indexed
18:47 < maaku> MMR is indexed based on insertion order
18:47 < maaku> so you can prove, for example, that no coin was spent in between two adjacently spent coins
18:47 < jtimon> petertodd: I like a generic scheme too, I'm just not contrained to softforks, seriously I don't know what your claim is yet what solution and what problem are you referring to from my link?
18:47 < maaku> which is pretty useless
18:48 < Alanius> maaku: thanks! very intuitive explanation :)
18:48 < maaku> jtimon: he wants to attach arbitrary validation rules to outputs, and have those propogate in arbitrary ways in future transactions
18:48 < petertodd> maaku: but that's the thing, it's *not* useless, if you can prove when the coin was created, you naturally have a reasonable limit on the non-existance proof, which is a way that you could get something akin to pruning in zerocoin
18:48 < petertodd> maaku: basically the cost to make the zk-proof would increase as the coin gets older, but my understanding is that cost blows up very fast with current zk-snark technology
18:49 < gmaxwell> yea, so my thought for pruning is that when you create a coin you could created it with a generation number (which is made public by the ZK proof)
18:49 < gmaxwell> where 'generation number' means like "what month was it created in"
18:49 < petertodd> gmaxwell: yup
18:50 < gmaxwell> and then you can say that coins become unspendable after so many months, allowing you to prune both data sets.
18:50 < gmaxwell> But its kinda ugly.
18:50 < Alanius> that would partition the anonymity set
18:50 < gmaxwell> as it reduces your anonymity set and makes your coins expire.. and we can't even tell how many coins have expired!
18:50 < petertodd> gmaxwell: but why make them unspendable? just force you to prove correct manipulation of the spent set in your tx
18:51 < gmaxwell> petertodd: hm. and store the new spent set root? so you never close off an old spent set, it just becomes more espensive to spend from it?
18:51 < gmaxwell> I suppose thats true.
18:51 < petertodd> gmaxwell: well, doesn't even have to be more expensive, just more annoying
18:52 < gmaxwell> You still have the anonymity set reduction though, alas.
18:52 < petertodd> gmaxwell: basically if you're spent token set is a single radix tree, then you have a bunch of data that needs accessibility, to do better, shard that
18:52 < petertodd> gmaxwell: sure, but it's still easily inline with what coinjoin can do (anonymity set of tx's happening at roughly the same time)
18:53 < gmaxwell> oh it's much better since same time could be defined to be a month or more.
18:53 < petertodd> exactly!
18:53 < gmaxwell> it's still not free however.
18:53 < petertodd> and you want some amount of time anyway, as mining needs to imply at least having the data, so you want mining to be tied to, say, the last month of data
18:53 < gmaxwell> also there are some other tradeoffs which come into play.
18:53 < petertodd> ?
18:54 < gmaxwell> The ZK proofs are going to be most efficient if they have no branching, just a constant number of hash evaluations and some muxes to get data on the right side of the hash input.
18:54 < gmaxwell> One of the plus sides of pruning is that it should make the ZK proofs faster.
18:54 < petertodd> gmaxwell: so make a tree of every month from now until eternity
18:55 < petertodd> ok, sure
18:55 < gmaxwell> "once we have these coins we put in the hash tree; 64-depth key (2^64); when want to redeem; reveal the serial number, and can reveal 64-hashes before in the tree; "
18:55 < gmaxwell> (quoting from the talk)
18:55 < gmaxwell> sounds like they fixed the tree size at 64 deep so that they'd 'never' run out of room.
18:55 < petertodd> (note how they must have some mechanism to make collisions hard...)
18:56 < gmaxwell> With pruning we can do better and say, have a 2^33 deep tree. Which is fine for a months of transactions.
18:56 < petertodd> (oh, actually, no that's not true, you don't need that)
18:56 < petertodd> true, although the risk of accidentally picking someone elses serial number goes up
18:57 < gmaxwell> petertodd: no need to have a risk of that, you just use a >128 bit random serial number.
18:57 < gmaxwell> one turn of the compression function takes 512 bits.
18:58 < gmaxwell> In there you have to fit the value of the coin, a P2SH hash for the pubkey needed to spend it, and a serial number.
18:58 < petertodd> gmaxwell: wait, so how does that help? the tree is indexed right, so if the first 33 bits match I have a problem
18:58 < jtimon> for scalable "anonymous" transactions, more than zerocoin-like stuff I like petertodd's inputs only approach with an expiry on the UTXI entries
18:58 < gmaxwell> petertodd: no no, it's insertion ordered.
18:59 < petertodd> gmaxwell: oh right, doh
18:59 < petertodd> gmaxwell: quite correct
19:00 < petertodd> gmaxwell: well basically, the depth of that tree is purely your anonymity set
19:00 < gmaxwell> yes
19:00 < gmaxwell> say a coin looks like this [128 bit serial number, 64 bit future extensibility, 64 bit value, 256 bit P2SH hash]   you add it to an insertion ordered tree.
19:01 < petertodd> jtimon: it's only scalable if you can figure out the right mining incentives and solve the data-hiding attack sufficiently
19:01 < gmaxwell> And then to emerge COIN  you just produce a ZK proof that  H(COIN)  is in the tree.. which takes Log2(size) hashes under the ZK proof.
19:01 < gmaxwell> so if you require multiple trees for pruing purposes, then you can make them reasonably small at the cost of reducing the anonymity set.
19:03 < jtimon> petertodd, I don't know the data-hiding attack, but from what I hear from maaku what you're talking about is new, can I read a summary somewhere?
19:03 < petertodd> jtimon: https://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg03307.html
19:05 < petertodd> jtimon: basically, your utxo/txo/txin set in a cryptographic accumulator, and you can only update the state of that set if you have the transactions that have happened, thus somehow you have to ensure you don't end up with that data getting lost
19:05 < maaku> petertodd: that doesn't have generic-coloring stuff you were just talking about right?
19:05 < petertodd> jtimon: easy to do in a single consensus-realm system, but quickly becomes an existential risk if you try to scale more than that
19:05 < petertodd> maaku: not explicitly, but the basic ideas in that paper can be applied to such schemes
19:06 < maaku> petertodd: is this accurate to what you are talking about:
19:06 < maaku> <maaku> So one can imagine a coloring script that acts kinda like a virus: it loads the transaction, does some checks to make sure it doesn't invalidate any coloring constraints, and then attaches itself (referencing it's own source code) to the colored outputs
19:06 < jtimon> petertodd: in that thread you only had commited utxi, not utxo
19:06 < petertodd> maaku: yup
19:06 < petertodd> jtimon: right, but the logic applies equally to utxo too
19:06 < maaku> you'd need a much more powerful script language to do interesting things with that
19:07 < maaku> but you certainly could do interesting things
19:07 < petertodd> maaku: heh, I'll say... such scriptPubKey's are quine's after all!
19:07 < jtimon> I'm sorry guys, I'm not sure I follow
19:07 < gmaxwell> petertodd: the coloring constraint can even validate a issuing authority signature, to make sure the the initial attachment was permitted.
19:07 < maaku> jtimon: http://en.wikipedia.org/wiki/Quine_%28computing%29
19:07 < jtimon> but what I meant by making the utxi scalable through expriries
19:07 < gmaxwell> So you can't just go affixing it ot new random coins.
19:08 < petertodd> jtimon: so in bitcoin, when a miner finds a block, what forces them to release the actual block contents rather than just the block header?
19:08 < petertodd> gmaxwell: yup, or make it part of the program operating "if prev txout == magic return true"
19:09 < gmaxwell> petertodd: and to avoid the awful outcomes in my covenant thread... you make sure the color virus has a kill switch.
19:09 < jtimon> petertodd, other miners won't mine on top of your block if they can't see it in full, it could be invalid
19:09 < gmaxwell> e.g. a way to spend it to tell it to not attach to the output.
19:09 < maaku> petertodd: we originally had introspective scripts in the freimarkets spec but gutted it because we didn't see a compelling use case, but this changes things
19:09 < maaku> it's a bit of complexity, but probably worth it
19:10 < petertodd> jtimon: Exactly. But other than that, what actually forces them to do that? For instance, what if you could prove a transaction was valid without the UTXO data itself?
19:11 < petertodd> maaku: I gotta read the freimarkets spec...
19:11 < jtimon> nobody forces them, is just the best they can do, not sure I understand the second question...
19:12 < gmaxwell> http://www.itbusiness.ca/news/royal-canadian-mint-readies-its-version-of-bitcoin-mintchip/46113  mintchip is moving forward? heck yea.
19:12 < petertodd> jtimon: well, we can make systems where transactions can be accompanied by short proofs that their txins are valid, and those proofs can be used to update things like committed UTXO set trees. Those two things let miners mine while fully validating, but without any blockchain data.
19:12 < maaku> petertodd: well its not in any public version of the spec, but I wouldn't be opposed to adding it back in
19:12 < maaku> petertodd: it may be sufficient reason to revamp script entirely
19:13 < petertodd> gmaxwell: I'll be interested to see if that alleged privacy leak is still in the spec...
19:13 < maaku> (we mostly dropped it because doing introspection was a kludge without LISP-like semantics)
19:13 < petertodd> maaku: it's a pretty useful feature IMO - I first thought of it for fidelity-bonded bank stuff
19:13 < petertodd> maaku: I suspect you can do it reasonably nicely with real forth semantics
19:14 < gmaxwell> petertodd: man, I wish I'd thought to ask them to be able to do something to do trustfree binding with bitcoin.
19:14 < petertodd> gmaxwell: if it was possible by accident they probably would have changed it to prevent it...
19:15 < gmaxwell> petertodd: e.g. just a "I've been paid!" message signed by your chip is enough.
19:16 < petertodd> gmaxwell: sure, although good luck on it being crypto-compat with bitcoin
19:16 < maaku> has anyone looked at hard-fork scripting improvements? other than Merklized scripts
19:16 < petertodd> maaku: I'm not sure there are any scripting improvements that actually need a hard fork you know...
19:16 < gmaxwell> Merklized scripts don't have to be a hardfork improvement.
19:16 < gmaxwell> You just P2SH deploy the update.
19:17 < jtimon> petertodd: does this require any snark-like tech? maaku: what are the differences from "regular stateless validation"
19:17 < jtimon> ?
19:17 < petertodd> jtimon: not at all
19:17 < maaku> jtimon: i think petertodd is explaining stateless validation
19:17 < petertodd> maaku: yup
19:18 < gmaxwell> maaku: things I want merklized scripts, restore missing opcodes, extra checksig flexibility, true scalable threshold signatures (e.g. schnorr).
19:19 < petertodd> "Money instantly moves from one cloud-based, MintChip account to another" <- it's cloud-based now? hmm...
19:19 < jtimon> ok, I guess then I don't undesrtand stateless validation well enough because I don't see how would you do coloring or what the power of the scripting language has to do with it
19:19 < gmaxwell> oh also, I eventually invented a much better scheme for hash based signatures, only to realize I invented something that has long been known. E.g. one time use hash based signature with 128 bit security (using 256 bit hashes) = 2.1kbytes.
19:19 < petertodd> jtimon: it's got nothing to do with either
19:19 < gmaxwell> petertodd: oh dear, did they make it suck?
19:20 < petertodd> gmaxwell: wouldn't surprise me... they probably noticed phones don't have card-readers
19:20 < petertodd> gmaxwell: and if they made it suck, they probably also made it possible to reverse tx's due to hacks...
19:20 < gmaxwell> damnit
19:20 < jtimon> can't you put an NFC card near a phone?
19:21 < petertodd> jtimon: that's harder than making it suck
19:21 < gmaxwell> I hope they didn't make it suck.
19:21 < petertodd> jtimon: and seriously, even that is susceptable to hacks - you really need a NFC card with a LCD display
19:21 < gmaxwell> Even without trustless binding it was going to be awesome for bitcoin.
19:22 < maaku> gmaxwell: i've been compiling a list of things that might make it in an updated freimarkets spec, and those are on it
19:22 < jtimon> yeah, I guess you need a lcd and a couple of buttons in the card
19:22 < maaku> i'd love both lamport signatures and ed25519-derived schnorr signatures (if that is possible)
19:22 < petertodd> jtimon: yup, and then you really want the cards to be registered to people's names, so the lcd displays who it's really going too...
19:22 < maaku> using the sighash byte to keep compatability
19:22 < gmaxwell> I am less enamored with ed25519 than I was. I like our curve better now. :P
19:23 < maaku> why?
19:23 < gmaxwell> maaku: just have a second checksig operator.
19:24 < gmaxwell> maaku: because ed25519 has a cofactor of 8, and because the "standard" software for it is incompatible with things like BIP32.   (also, because one of the things I thought was weak about our curve turned out not to be.)
19:25 < gmaxwell> I believe our curve also has higher security against all known attacks, outside of implementation mistakes, not that it matters much.
19:25 < maaku> but it is faster & resistant to timing attacks, isn't that pretty significant?
19:26 < gmaxwell> no, in fact it's not resistant to timing attacks unless you drop the compatiblity with BIP32. (or make it much slower)
19:26 < gmaxwell> To make it constant time (and faster) they require the most siginficant bit of the private key be 1.
19:26 < maaku> i mean I'm in aggreement with our curve not being weak, but I thought ed25519 was strictly better in most cases
19:26 < gmaxwell> which means that you can't have a 'randomly' generated private key, e.g. from a public derrivation.
19:27 < gmaxwell> and without that you make it slower and you take away the constant timeness (though you could get back the constant timeness with a major slowdown, just like for our curve)
19:27 < maaku> sorry confusing pronoun dereferencing : ed25519 is resistant to timing attacks and secp256k1 is not, right?
19:27 < gmaxwell> and the speed difference isn't so huge.
19:27 < maaku> hrm. ok
19:29 < maaku> i see, so it'd be quite a bit of work for little payoff
19:29 < gmaxwell> maaku: _curves_ aren't resistant or not, their implementations are, though curve choice can limit what implementations are available.  ed25519's canonical implementation is both fast and timing resistant, but requires that the most significant bit of the private key be 1.
19:29 < maaku> which kills bip32, i understand now
19:29 < petertodd> so why does that kill bip32?
19:29 < gmaxwell> which is neat, but if you take away that bit, then its not timing resistant, and making it timing resistant makes it not fast. (though it may still be better off than secp256k1)
19:30 < gmaxwell> petertodd: it kills type-2 derrivation since you can't tell if the private key will have the MSB set.
19:30 < gmaxwell> now— it may not be much work in reality, because the tor project has this whole big proposal for a redo of hidden services.
19:31 < gmaxwell> And it does something very similar to type-2 derrivation to prevent HS directories from enumerating which hidden services are in use.
19:31 < petertodd> gmaxwell: right, although you could do a checksig that did bip32 with some kind of crazy 1-of-m multisig essentially, although at the cost of privacy
19:31 < gmaxwell> And they're planning on doing this with the ed25519 curve.
19:31 < gmaxwell> And I don't think they've yet realized that they won't be able to use the standard implementation…
19:31 < jtimon> separate issue, does what I said here make any sense? Is Flavien right? https://groups.google.com/d/msg/bitcoinx/Nq_8dkC3zqU/h_aqRA5A7TkJ
19:31 < gmaxwell> (I only realized this because I went and tried to implement ed25519 for bitcoin)
19:32 < gmaxwell> petertodd: BIP32 perhaps, but not the privacy purposes of it.
19:32 < gmaxwell> Or stealth addresses.
19:32 < gmaxwell> Which is basically the same usecase tor has.
19:32 < petertodd> gmaxwell: yup, although OTOH a merkle tree would do it, at the cost of size
19:32 < gmaxwell> (and incidentally, tor is working on a rigorous security proof for their derrivation scheme, though last I checked they hadn't made much progress)
19:33 < gmaxwell> petertodd: not for privacy, I could see your hashroot was the same. :P
19:33 < petertodd> jtimon: it makes sense
19:34 < petertodd> gmaxwell: no, the hash root would be of n pubkeys, and if you could spend any one of them you can spend the txout. each pubkey is still bip32-style secure, although there is a 1 in 2^256 chance of not being able to spend the txout (or whatever the math is)
19:34 < jtimon> petertodd: thanks, so Flavien is wrong saying you can reuse an address to sign securely 100 times a day even if you don't care about privacy
19:35 < petertodd> jtimon: well, the bigger thing is that you should just have the definition of a valid ccoin txout be "whatever the issuer signs", with a separate merkle sum tree for auditing purposes
19:36 < petertodd> jtimon: your proof that your ccoin is valid just needs to be that the signature on the genesis txout was valid
19:36 < maaku> jtimon: the chance of choosing the same K value is exceedingly low ... unless you have a bad RNG, in which case it is exceedingly high
19:36 < gmaxwell> petertodd: oh god, you mean using lots of bip32 keys just to make sure you get one where the MSB is 1?
19:37 < petertodd> gmaxwell: yes! not that I ever said it was a good idea :P
19:37 < gmaxwell> petertodd: dear god, that idea ... so bad. ... must stab
19:37 < jtimon> petertodd, flavien is talking about "inflatable colored coins" in which the same address can be used to just issue more
19:37 < maaku> If you assume your RNG is good or use deterministic signatures, key reuse is not a problem (from that perspective only)
19:37 < petertodd> gmaxwell: pity you can't stab someone over the internet
19:37 < jtimon> so maaku says flavien is right...
19:37 < gmaxwell> I'm pretty sure there is an onion site for that.
19:37 < petertodd> jtimon: yes, which is a dumb idea, just use the signature to sign a message saying some arbitrary txout is colored
19:38 < maaku> but you still wouldn't want to tie it to an unchanging address anyway, for a multitude of other reasons
19:38 < maaku> jtimon: he is not factually incorrect when he says "Signing a billion transactions per second, it would still take you hundreds billion times the age of the universe before you have 1% chance of collision."
19:38 < maaku> (assuming perfect RNG or deterministic signatures)
19:39 < gmaxwell> petertodd: you ever hear about how the signature systems which are based on one-time-hash based signatures but allow ~infinite signatures work?
19:39 < maaku> but those are invalid assumptions for real-world cryptography
19:39 < petertodd> gmaxwell: of course, which is why I expected the idea to raise your blood pressure :P
19:40  * petertodd has been paid off by the NSA to kill gmaxwell via heart disease
19:40 < maaku> where with a bad RNG (or a reused seed value on a VM) it only take two signatures to give up the key
19:44 < jtimon> maaku I was going to answer something like "thank you for the clarification, then addresses is still the right approach for inflatable basic CC, but since we have tokens in freimarkets for other reasons, they're still more convenient for re-issuance as well"
19:46 < maaku> jtimon: it's not just a matter of convience. it lets you have more control over operational security, for example by having one key per signing server and local protections against K reuse
19:47 < maaku> which would protect you against spinning up two separate servers, who each sign separate messages with the same K value
19:47 < warren> petertodd: I knew it!
19:47 < maaku> (due to saved random state in the VM image and a lack of entropy)
19:47 < justanotheruser> Is bitmessage off topic here?
19:48 < maaku> justanotheruser: so long as it involves arcane spell
19:48 < maaku> s
19:48 < justanotheruser> ?
19:48 < jtimon> well the "one address" in colored coins could be a p2sh multisig or whatever, by convenience I also mean that more control
19:49 < maaku> jtimon: yes, but in the example I gave you need tokens because you need a new key every time you spin up a server, and eventually you run out
19:50 < jtimon> tokens allow you to change the p2sh one addres doesnt
19:50 < maaku> although if you had bip-32 in script...
19:50 < maaku> yes
19:50 < maaku> if you could do bip-32 derivation in script though, you could get by with a single address
19:51 < justanotheruser> Anyways, how well does bitmessage scale? Would it work with 10 million users?
19:51 < jtimon> not if you want to radically change the config
19:51 < maaku> yeah
19:52 < gmaxwell> justanotheruser: scaling is largely in terms of the anonymity set size.
19:53 < gmaxwell> justanotheruser: they kinda waved their hands at the streams stuff in their initial writeup though so the mechnisms needed to get people onto different streams is unde(rde)fined.
19:53 < justanotheruser> Nice use of parenthesis there. How is scaling in terms of the anonymity set size? Will the network break into sections or something?
19:54 < gmaxwell> justanotheruser: the idea is that the POW would increase to keep the datarate in a stream sane. And thus that would push people off onto other streams where the pow was lower (but the anonymity set smaller).
19:55 < petertodd> ...which is basically what sane people propose for consensu blockchains in general.
19:55 < justanotheruser> I see. And there is no in depth explanation for their streams?
19:55 < petertodd> it's just that how that'll actually work in bitmessage si a lot more obvious - no "oops I let a tx spent a bit of dust that didn't actually exist" problem
19:55 < petertodd> justanotheruser: not that I've seen
19:56 < gmaxwell> there is a stream setting on addresses, so the stream stuff is implemented but no 'fee intelligence' if you will.
19:56 < petertodd> justanotheruser: you can also do steams based on sharding H(addr) space (roughly speaking)
19:56 < gmaxwell> I think they don't quite have the incentives well aligned. they guy sending to you pays the pow for your choice of stream.
19:57 < gmaxwell> so, duh, yea, of course I'm going to pick stream 0.
19:57 < gmaxwell> let you suckers pay the cost of messaging me.
19:57 < petertodd> gmaxwell: yup, although another way to look at it, is the person messaging you is picking the size of the anonymity set thye want *their* message to be in
19:57 < justanotheruser> Well there is an incentive to have someone message you right?
19:57 < justanotheruser> I mean to send a message
19:58 < justanotheruser> So if you don't agree on the stream then it wouldn't be sent
19:58 < petertodd> justanotheruser: yup, and stream would be part of addr
19:58 < gmaxwell> petertodd: well no the recipent picks the the stream. Not the sender, and thats generally good because its the recipents privacy that is triciker.
19:58 < gmaxwell> I think the incentive issue is probably not fatal, as justanotheruser says— people want to recieve messages.
19:58 < gmaxwell> But it is interesting.
19:59 < petertodd> gmaxwell: right, but you can easily imagine a system where you have receivers listening to some fraction of the addr space by prefix, and senders get to pick how much of the prefix they match based on how much pow they spend
19:59 < petertodd> gmaxwell: limit bandwidth based competition for a given prefix specificity
20:00 < petertodd> gmaxwell: hilariously, that matches really well to what PoW algorithms actually do... but in the exact wrong way
20:01 < justanotheruser> How does the reduced anonymity effect the anonymity of coinjoins? Does it even matter?
20:01 < petertodd> justanotheruser: depends on how anonymous you want to be...
20:01 < gmaxwell> I don't know that it even matters. ... though I assume anyone would use bitmessage over tor.
20:03 < petertodd> justanotheruser: oh, you mean coinjoin over bitmessage? meh, bitmessage isn't a great message layer for cj anyway from a usability perspective
20:04 < gmaxwell> petertodd: there are no more sutiable traffic analysis resistant privacy networks.
20:04 < justanotheruser> petertodd: Why not? I would think it is great, it just needs a layer on top of it to handle it
20:04 < petertodd> justanotheruser: needing a PoW to send a message is ugly vs. using fees for it
20:04 < petertodd> justanotheruser: and you can use fees to pay for it with the nLockTime trick
20:05 < justanotheruser> petertodd: I think gmaxwells idea of using PoS is better.
20:05 < justanotheruser> People don't really want to pay double fees, one for the message and one for the coinjoin.
20:06 < petertodd> justanotheruser: you don't have too though, you make a nLockTime'd tx spending one input, and then respend it in the coinjoin
20:06 < petertodd> justanotheruser: either way you spend some tx fee, and you can arrange all of this such that the attacker doesn't learn much
20:06 < justanotheruser> petertodd: how would you determine the coinjoin tx without being able to communicate with the network first?
20:07 < petertodd> justanotheruser: your communication includes that nLockTime'd tx - that's how you pay for it
20:07 < justanotheruser> petertodd: well you would have to pay a fee for that tx, then everyone would have to pay a fee for the coinjoin tx to go through
20:08 < petertodd> justanotheruser: which you have to anyway - tx's aren't free
20:08 < justanotheruser> petertodd: yes, but with PoS you only have to pay one
20:09 < petertodd> justanotheruser: no, it's identical to pos, except that you ensure something of value is actually lost
20:09 < petertodd> justanotheruser: after all, you can't prove pos other than by signing for a txotu scriptPubKey, this is the same, except you've signed a valid-in-the-future transaction with some minor fee
20:11 < justanotheruser> petertodd: When you have stake that means you payed a fee to  get the coins. That is what you lost.
20:12 < petertodd> justanotheruser: it's the same argument as merge-mining: to the attacker they can re-use something they already have (txouts sitting around) for free
20:12 < justanotheruser> except for cases where millionaires don't pay fees, but there aren't enough of those to worry about
20:13 < justanotheruser> petertodd: they can use it for free, but they can only use a certain amount of it. Then they have to make another tx to spend again. The coinjoin tx takes care of this.
20:14 < justanotheruser> s/use a certain amount of it/use it to a certain extent.
20:15 < petertodd> justanotheruser: yes, but now you have to have a database of UTXO's whose stake has been proved, vs. there's a natural time limit because the fee sacrifice tx's get mined
20:16 < justanotheruser> gmaxwell: does pinnochio take care of petertodds concern?
20:17 < justanotheruser> petertodd: Wouldn't proof of burn also remove anonymity in the same way?
20:18 < petertodd> justanotheruser: yes, emphasis on the same way, they're both identical re: anonymity, but the burn version has better resistance to DoS attack
20:21 < justanotheruser> petertodd: I don't understand pinnochio fully, but gmaxwell said it would work for proof of burn and I think he said it would work with PoS
20:22 < justanotheruser> It's a pretty big research paper
20:22 < gmaxwell> what concern?
20:22 < justanotheruser> And I have to look stuff up every page
20:22 < gmaxwell> you guys said a bunch of stuff
20:22 < justanotheruser> gmaxwell: (08:15:21 PM) petertodd: justanotheruser: yes, but now you have to have a database of UTXO's whose stake has been proved, vs. there's a natural time limit because the fee sacrifice tx's get mined
20:22 < petertodd> justanotheruser: pinnochio is orthogonal to the choice between proof-of-stake and proof-of-sacrifice
20:23 < justanotheruser> petertodd: then your comment was irrelevant to the discussion of which was the better method
20:23 < gmaxwell> what pinnochio lets you do is make compact blind proofs from something where you have efficiently extractable authenticated data.
20:23 < justanotheruser> because they both have that glaw
20:24 < petertodd> justanotheruser: pinnochio's proof-of-stake for anti-DoS still requires a UTXO database, or you can re-use proofs. (it becomes like some weird zero-coin thing in that case)
20:24 < gmaxwell> right now because we don't have a committed utxo proof-of-sacrifice will be smaller unless you expect all validators to keep a copy of the utxo themselves.  Having the verifiers have a utxo database might actually be a bunch better since it could be restructured in a way to make the proofs small.
20:24 < petertodd> justanotheruser: for the proof-of-burn case, then pinnochio is less desirable because you have to do a separate burn that's actually mined 
20:25 < gmaxwell> petertodd: my suggest for rate limiting based on POS is that you do get a once per $time_interval random ID out of your stake.
20:25 < petertodd> gmaxwell: proof-of-stake for anti-dos requires you to at worst end up storing something like a bloom table of spent stakes
20:25 < petertodd> gmaxwell: it's doable, but potentially ugly long-term if people really want to attack it
20:25 < gmaxwell> yea, you'd then use a hashtable that you keep for $time_interval
20:26 < petertodd> gmaxwell: I mean, you've created an incentive to make a lot of utxo's you know... or failing that, you let rich people block coinjoin
20:26 < petertodd> gmaxwell: at least proof of burn ensures they'll spend fees doing so
20:26 < gmaxwell> petertodd: well of course the proof can emerge a bound on its value.
20:26 < justanotheruser> couldn't your "proof of time" be the hash of your proof plus the unix time being below a certain value?
20:26 < gmaxwell> proof of burn can't be done non-interactively in zero knoweldge.
20:27 < gmaxwell> PoS and PoS can be.
20:27 < petertodd> gmaxwell: no, but my trick of nLockTime'd tx's isn't a serious disadvantage - note how you can very much use a different txout then the one you actually join
20:28 < gmaxwell> for coinjoin PoB is pretty great, I agree.
20:28 < gmaxwell> since coinjoin inherently must expose a txout.
20:28 < petertodd> yeah, and for everything else, proof-of-prior sacrifice *with* some kind of domain-specific tag is pretty decent
20:28 < gmaxwell> for something like a replacement for BitMessage's pow I prefer PoS or PoS.
20:28 < sipa> gmaxwell: PoS and PoS (i do keep reading that as piece of s**t...)
20:29 < gmaxwell> Proof of Stake or Proof of sacrifice.
20:29 < petertodd> sipa: PoS and PoX I prefer myself
20:29 < justanotheruser> gmaxwell: should their stake expire after a certain number of blocks? Otherwise they can use the network at no cost
20:30 < gmaxwell> justanotheruser: you'd prove that you had stake as of some reference time that moves periodically.
20:30 < gmaxwell> e.g. first block after midnight utc every day.
20:30 < petertodd> justanotheruser: funny how you actually want the inverse of coinage in this case
20:30 < justanotheruser> petertodd: yes, coin/days
20:30 < gmaxwell> every day at the first block after midnight all the message nodes snapshot their utxo and reorg it into a hash tree and save the root.
20:31 < gmaxwell> Then when you want to use a message for this hour you run the ZK proof to get a token good for the hour that proves you had a coin in the last day's utxo snapshot.
20:32 < gmaxwell> likewise for proof of sacrifice, except you just extract sacrifice like transactions.
20:32 < petertodd> gmaxwell: heck, just prove you have a txout that existed in some time period, and spent a txout preior with some amount of coin-days destroyed
20:33 < gmaxwell> yea, whatever, you can get compact proofs of any of this if you don't mind the participants needing to bitcoin nodes and thus generating the data extracts themselves.
20:33 < petertodd> gmaxwell: well, that case you'll have all that data in your wallet actually
20:33 < gmaxwell> unfortunately using bitcoin's own data for ZK proofs is kinda craptastaic because of having to traverse a whole variable length transaction just to extract an output.
20:34 < petertodd> yup
20:34 < gmaxwell> but if you extract the data directly you can reorder how its stored.
20:34 < justanotheruser> How big is the proof of stake using pinnochio?
20:34 < gmaxwell> e.g. use exactly the ultraprune data structure though bitcoin itself never commits to it... all participants would come up with the same value.
20:36 < gmaxwell> justanotheruser: the proofs are 288 bytes (well, in the pinnochio paper they might be a bit larger, but they can be done in 288 bytes), plus a few more bytes to identify the serial number, epoch, and utxo set that its relative too.
20:36 < justanotheruser> That's not bad
20:39 < justanotheruser> gmaxwell: Why is a proof of SHA256 so big?
20:41 < maaku> justanotheruser: SHA256 is a non-trivial function?
20:41 < justanotheruser> maaku: So ECDSA isn't?
20:42 < maaku> that's an apples-to-hot-wheels-cars comparison
20:42 < midnightmagic> gmaxwell: I do not appear to have an easily-accessible sidechain that reorgs out 1000-blocks, if -loadblock can be used to replay the blk*.dat files and the dat files have the sidechains stored in them by default.
20:42 < petertodd> justanotheruser: you don't need to prove ECDSA in this case
20:42 < midnightmagic> gmaxwell: I have one more place where I can look. Would you like me to check?
20:43 < gmaxwell> Because ECDSA is special in that it naturally yields compact proofs of knoweldge. There are very few things that do this.
20:43 < gmaxwell> midnightmagic: not that urgent I have it at home someplace.
20:43 < petertodd> gmaxwell: how does that work?
20:43 < midnightmagic> ok
20:44 < midnightmagic> gmaxwell: If it's cleanly possible to get a copy of that I would sure love one. :-D
20:44 < gmaxwell> petertodd: an ECDSA signature is a proof you know the discrete log of the public key value.
20:44 < petertodd> gmaxwell: ah, and these schemes can do that directly?
20:45 < gmaxwell> petertodd: no no. Perhaps we're miscommunicating.
20:45 < gmaxwell> I thought justanotheruser was asking why the pinnochio proofs were much bigger than an ECDSA signature.
20:46 < petertodd> gmaxwell: right, I took it as asking why you couldn't feasible make a pinnochio proof of a ECDSA sig
20:46 < sipa> ECDSA is basically a scheme designed for creating a compact proof... for a very specific operation
20:46 < gmaxwell> petertodd: oh you could, and ... like all other GGPR'12 proofs would be 288 bytes.  Though the proving time might be awful.
20:47 < petertodd> gmaxwell: right, and the proving would be some crazy thing that basically implements ECDSA with some circuit
20:47 < gmaxwell> right, with an arithemetic circuit over some finite field.
20:48 < gmaxwell> (or some boolean circuit, though usually arithemetic circuits are more compact, e.g. they make sha256 quite compact)
20:56 < petertodd> so the pinnochio source code is available, but I don't see any license anywhere
20:57 < petertodd> oh wait, I found it, Microsoft non-commercial, not too useful
21:12 < gmaxwell> petertodd: meh, that doesn't worry me _that_ much. The verifier is just a couple dozen lines of code given a sutiable pairing library. (which they don't provide, but there are several sutiable liberally licensed ones available)
21:14 < gmaxwell> the interesting code they provide is the circuit generator and the prover which are non-normative so long as you don't make something which is married to a single validation key.
21:16 < adam3us> about coloring in the context of zerocash, i think they could include another value in the hash, being the color
21:17 < adam3us> gmaxwell: that kind of sucks about the EdDSA high bit.. i was looking forward to compact k of n sigs, blind sigs & such :(
21:19 < gmaxwell> adam3us: I mean, it would only be a couple of lines of code to add schnorr signatures to sipa's library.  compact k of n is kind of a killer feature.
21:20 < adam3us> gmaxwell: kind of annoyed at DJB now that is an unclean hack disguised as a feature.  it fails composability
21:23 < gmaxwell> adam3us: well, I was made kind of annoyed by the "Safe or Not" summary table most recently added to safercurves
21:24 < gmaxwell> which has now three times caused me to get questions with urgent concerns that bitcoin's curve is not safe.
21:25 < adam3us> gmaxwell: the guys on IRTF/CFRG are making an RFC for safe curves.. can be  good place to ask questions or complain if u see problems.  they seem to have a good collection of people who understand ECC & coding
21:26 < adam3us> gmaxwell: as there is a guy moving pretty fast on getting an RFC through standardizing the safe curves
21:26 < gmaxwell> It's my opinion that the addition of the binary safe or not table debased an otherwise thoughtful site to marketing tripe... since it happily fails bitcoin's curve because the endomorphism shaves off 1.5 bits of security, while meanwhile his curves cofactor of 8 shaves off at least three bits of his already smaller curve, and then his implementation throws away another bit for that optimization.
21:30 < CodeShark> "safe or not" is pretty stupid when it comes to proclamations of security completely devoid of context
21:31 < maaku> if someone wants to advocate for schnorr and bip-32 comaptability with the RFC safe curves, that'd be a noble thing to do
21:35 < sipa> what is considered unsafe about secp256k1?
21:35 < gmaxwell> http://safecurves.cr.yp.to/
21:35 < gmaxwell> scroll down
21:35 < gmaxwell> it's "not safe" if it doesn't meet all of DJB's criteria.
21:36 < gmaxwell> the criteria are all interesting. Few of them would justify not-safe for failing them
21:37 < gmaxwell> esp since the critiera omits other no less reasonable considerations like "cofactor == 1", presumably since his own curves fail it.
21:37 < maaku> chiefly, the fact that it doesn't have "25519" in its name
21:41 < gmaxwell> I gave a somewhat irritated response here: https://bitcointalk.org/index.php?topic=380482.0  (being that it was the second time that day I'd been asked about it)
22:28 < andytoshi> wizards, i am enrolled in a "numerical iterative methods" class which is very open ended
22:28 < andytoshi> can you think of any interesting (or useful to bitcoin) numerical analysis projcets?
22:35 < gmaxwell> andytoshi: network simulations can fall in that bucket.
22:36 < gmaxwell> andytoshi: if you wanted to fool with an altcoiny thing, control loops for difficulty adjustment.  What else? Hm. anti-spam/dos attack hurestics perhaps.
--- Log closed Tue Jan 14 00:00:09 2014