00:27:22	roidster:	roidster is now known as Guest16109
04:19:09	mike4:	mike4 is now known as c--O-O
14:54:14	tt_away:	tt_away is now known as tacotime_
17:44:58	nsh:	vertcoin is planning to "implement zerocoin"
17:44:59	nsh:	https://bitcointalk.org/index.php?topic=404364.msg5019536#msg5019536
17:45:07	nsh:	i am trying to figure out what that actually means, if it means anything
17:45:53	nsh:	s/zerocoin/zerocash/ per http://www.reddit.com/r/vertcoin/comments/1xcnne/i_am_the_developer_of_vertcoin_here_to_explain_to/cfa6fcc
17:46:14	nsh:	we're still waiting on the specification of zerocash though, aren't we?
18:09:35	andytoshi:	idk what zerocash is supposed to be, but the other comments on that reddit link suggest this guy has no idea what he's talking about
18:10:10	sipa:	zerocash == zerocoin altcoin, no?
18:14:26	gmaxwell:	zerocash is what the new design based on the GGPR ZKP instead of the RSA accumulator is called.
18:15:23	gmaxwell:	(in particualr, it deserves the 'cash' name because its truly an anonymous ecash— the coins can spend their entire lives anonymous, including merging, splitting, and having arbritary value)
18:16:14	sipa:	ok
18:16:39	sipa:	what complexities for spending/verifying does it have?
18:16:49	andytoshi:	somebody posted on bct a transcription of a matt green talk about it. http://0bin.net/paste/pJZ1Pk0qajZCxoYe#n+S+MhRf12Ru3EbBSPwNp542Nz+1JU/3L467AktQIu4=
18:17:00	andytoshi:	(i moved it from pastebin to 0bin because pastebin was blocking my tor exit)
18:17:38	andytoshi:	i'm only partway through it, it doesn't look nearly technical enough to answer any of our questions..
18:21:36	gmaxwell:	sipa: it's the GGPR based ZKP meaning that the verifying complexity is very low... on the order of ~8 related pairing operations to verify a proof. a couple ms per transaction *(subject to some limitations, only being able to do 2 inputs/2 outputs at a time, just due to using a single canned program to verify)
18:22:02	gmaxwell:	proving (spending) is substantially more complex but they were talking about numbers in the 30 seconds range, so not completely unreasonable.
18:22:26	sipa:	that comes close to being practical indeed
18:22:36	andytoshi:	does it still have the crs problems?
18:22:51	gmaxwell:	Yep... the system needs a trusted initilization.
18:24:00	gmaxwell:	Coins in the system are just H(pubkey||H(value||nonce)) (or equal).. like the hash of a UTXO entry with a nonce.
18:25:15	gmaxwell:	To spend a coin you verify a proof that the coin you're spending is in a coins tree, and reveal its pubkey; You also provide the new coins you are creating (just their hashes), and verify that the values add up. You do this all under the ZKP system.
18:26:02	gmaxwell:	So under the ZKP you run a bunch of hash operations to verify the hash tree, verify the outputs, and two additions and three comparisons or something like that; so no much is done under the zkp.
18:26:32	gmaxwell:	The blockchain then adds the pubkey you spend to a search tree of coins that have been spent already, so you can't spend it again.
18:26:49	andytoshi:	ok, nice. i guess that's what matt green means when he talks about "optimizing these proofs", just minimizing the amount that he actually has to zkp
18:26:55	gmaxwell:	pubkey is used to sign the transaction, etc.
18:27:45	gmaxwell:	well not just that, they've apparently implemented sha256 directly, by hand, as an arithemetic circuit over whatever field this thing is using (some 200 bit prime field)... in order to make the hash function proving as fast as possible.
18:28:20	gmaxwell:	it's a quite simple system, similar to petertodds MMR thinking; but you do the operations under ZKP.
18:28:31	gmaxwell:	(which makes it private, and also makes the proofs quite compact)
18:29:08	gmaxwell:	there is actually a bunch of yet unsolved implementation complexity remaining in turning it into a real system.
18:29:32	sipa:	define "quite compact" ?
18:30:00	gmaxwell:	For example, if I pay you a zerocash coin— how the @#@$# do you know I did? I have to give you the nonce/value... or you have to given me the nonce/value so I can watch for it. Or we need a private messageing channel of some kind.
18:30:48	sipa:	that's not really a problem, i think
18:31:00	sipa:	just make it payment-protocol-only
18:32:44	gmaxwell:	sipa: 230 bytes for 80 bit security IIRC, I think 128 bit security makes them about 320 bytes. (this is just the proof, you'd also need to enumerate the pubkeys in use and the new coins you're creating— of course.
18:34:08	gmaxwell:	make 288 for 128. They're 8 G1 field elements and 1 G2 field element, they used a specially constructed curve where the G2 elements have a compact representation (instead of being 3000 bits long as is typical for pairing crypto G2 elements).
18:34:51	andytoshi:	this is in the GGPR12 paper? ben-sasson cites a GGPR13 paper, is that the same one?
18:36:53	gmaxwell:	andytoshi: well the original GGPR paper was a 2012 one, but it's been enhanced a number of times.
18:37:12	gmaxwell:	the later papers make it more efficient but fundimentally the same.
18:37:28	andytoshi:	ok, i'm sure i can track it down. i'm paper-backlogged at least 2 months right now anway
18:38:28	gmaxwell:	I call the approach 'quadratic span/arithemetic circuts proven by verifying encrypted polynomial evaluation via pairing crypto with CRS keys' GGPR12 ... the paper is not super transparent in any case.
18:39:56	gmaxwell:	sipa: if you're interested in performance, this paper http://eprint.iacr.org/2013/879.pdf has a ton of performance info. It's talking about vntinyram which is an implementation of a general purpose computer as the circuit being verified (instead of something specialized like a bunch of hash operations). The proving times are irrelevant to zerocash, but the verifying times should be exactly the same— since its the same verification.
18:41:42	gmaxwell:	(the advantage of verifying a general purpose computer is that the program is an input, so you can use a single circuit for all tasks, and thus only have to do the CRS thing once.... also branchy programs are much more efficiently implemented that way than as a direct circuit. Alas, a bunch of hash operations is not very efficient to implement that way— a hand coded circuit for the hash is like 1000x less complex to prove than one ...
18:41:42	gmaxwell:	... running in tinyram)
18:42:45	andytoshi:	have you read the tinyram paper? do you get the impression that we could build it from the paper even tho they have not released source?
18:44:10	andytoshi:	i think we could make a modified tinyram which had hash opcodes which baked to handwritten circuits.
18:45:15	nsh:	hmm
18:45:37	nsh:	i think handwritten circuits might break the verification model, unless you can prove them independently
18:45:52	nsh:	should be surmountable at least
18:46:42	andytoshi:	but this crs stuff really kills me. matt green says several times in this talk "we just need to find somebody we trust", but ofc that person also needs to be willing to be tortured to death because everybody knows he has money-printing keying material
18:47:24	sipa:	andytoshi: it's probably easier to find someone who agrees to be just killed (instead of being potentially tortured to death)
18:48:33	c0rw1n:	find someone who's currently dying and release the public hashes when they're dead?
18:48:49	c0rw1n:	maybe someone who's already signed up for euthanasia
18:49:21	nsh:	it's not a question of brain-forgetting. it's a question of definitely destroying the digital traces
18:49:33	nsh:	it could be ceremonialized
18:49:42	c0rw1n:	"dead brainwallet" sounds secure enough to me
18:50:53	andytoshi:	anyway all the best to this altcoin fellow. he will run into some pretty thorny problems but hopefully we can learn something from it
18:52:01	nsh:	* nsh nods
18:55:09	andytoshi:	while we are talking about snarking coins tho, last we talked about a snarkcoin it was suggested to snark-prove VALID(old chainstate, new chainstate, chainstate diff, [zk] transactions). there is redundancy there b/c the diff + old chainstate implies the new chainstate
18:55:32	andytoshi:	... gmaxwell said, while we're being redundant also snark-prove the chainstate at blockheight/2
18:55:44	andytoshi:	then a new user can validate back to the genesis in logarithmic time
18:56:06	andytoshi:	this also has the neat effect of encouraging all miners to be archival nodes
18:57:11	andytoshi:	so two birds with one stone there. but i'm not clear on whether there are incentives then for miners to keep old blocks secret to try to exclude people from mining
18:57:49	andytoshi:	probably not, information wants to be free so you'd need 100% of the miners to collude to manage this.
19:05:24	gmaxwell:	well torturned isn't really quite the risk, since if the 'trusted' party destroys the secret data then there is no issue.
19:05:53	gmaxwell:	but you're talking about a key that yields unbounded undetectable inflation. How can you really trust that they deleted it?
19:06:00	c0rw1n:	point is the torturer might not believe that it's been destroyed, that's the risk for the secret holder
19:06:08	c0rw1n:	yes
19:06:14	nsh:	first time a crypto problem has been solved by the creative application of an electromagnetic pulse weapon?
19:06:20	nsh:	that would be pretty fun
19:06:38	nsh:	you'd still have to get the CRS out though
19:07:08	nsh:	hard to isolate the system so that the CRS can emerge but no covert channels for the bad-data to escape
19:07:17	c0rw1n:	there will be some point where you need to trust something by fiat, no? you can't really be sure, say, the RNG hasn't been tampered with
19:07:46	c0rw1n:	or that there is no hidden copy of the secret
19:07:57	sipa:	have anyone who wants to have randonmess sent it
19:08:23	sipa:	make a giant document with a list of "name: " strings
19:09:25	sipa:	add a randomly generated (r,s) signature, deterministically from what goes before
19:09:45	sipa:	wait, just randomly i guess
19:10:04	sipa:	now have a trusted computer generate a private key to sign it using that signature (ecdsa self-signing feature)
19:10:33	c0rw1n:	^ how do you trust that computer for not having been tampered with?
19:11:16	c0rw1n:	(dat compiler attack in Reflections in trusting trust )
19:11:48	sipa:	depends on what you mean by tampering... if that includes a covert EM transmitter that sends the private key somewhere, sure
19:12:04	c0rw1n:	hey, they do exist :/
19:13:15	c0rw1n:	maybe put the computer in a faraday cage at the time it crunhes, then EMP blast it from the inside
19:14:02	c0rw1n:	won't prevent tampering with the computing/RNG/whatevr, but at least the secret would be safe
19:15:08	c0rw1n:	ooh maybe simpler with shamir secret sharing the key? so that no-one has it full
19:18:48	gmaxwell:	nsh: yea, I though an RF shielded bunker which you then explode would be fun.
19:19:04	nsh:	indeed :)
19:19:30	gmaxwell:	But even for that you'd want to implement the thing under multiparty computation and have the bunker just be one part of it— due to it being basically impossible to avoid having a leak of some kind.
19:19:55	nsh:	right, forgetting-in-depth
19:20:48	gmaxwell:	doing it via MPC is I think still just pure theory wank. it would be a much harder computation than has ever been done in any kind of mpc.
19:20:56	gmaxwell:	The proving keys are rather enormous too.
19:21:15	gmaxwell:	(like hundreds of megabytes) (these are keys you only need for signing, and they're universal for the system)
19:21:42	c0rw1n:	wow we need to upgrad the internet then
19:21:50	gmaxwell:	what? why?
19:22:00	c0rw1n:	connections throughput
19:22:05	gmaxwell:	for what?
19:22:09	nsh:	this would be a one-time thing not requiring networking necessary
19:22:12	nsh:	*necessarily
19:22:17	c0rw1n:	keys that take up hundredes of megs?
19:22:35	c0rw1n:	(gah catastrophic amont of typos)
19:22:35	gmaxwell:	::sigh:: you've misunderstood, darnit, and I tried to hard to be clear above.
19:22:36	nsh:	c0rw1n, still in the context of initiating the common-reference-string of a zerocash-like system
19:23:02	gmaxwell:	They're just an initilization parameter of the system. They're the same for everyone. It's just additional size for wallet software.
19:23:12	nsh:	(a forget-then-forget action, heh...)
19:23:19	c0rw1n:	ok ok, i got it
19:23:38	c0rw1n:	(i'm not smart enough to talk here dammit, why do i keep doing that)
19:23:42	gmaxwell:	But it contributes to making it infeasable to use MPC to compute the initilization because just a lot (in MPC terms) of data is involved.
19:24:04	nsh:	what affects the scaling of the keys most?
19:24:30	gmaxwell:	c0rw1n: psh. Nah, if I were really excillently explaining it, it would be clear to even an idiot... and I doubt you're an idiot in any case. :)
19:24:44	gmaxwell:	nsh: proving key scales with the size of the circuit being proven.
19:24:53	nsh:	right
19:25:33	nsh:	is there a determinate lower bound for CRS length/complexity?
19:25:38	gmaxwell:	verifying key is a constant size, about 2kb (+/- depending on what precomputation you do to speed up verifying). Proofs are a constant size (couple hundred bytes).
19:26:22	gmaxwell:	nsh: the proving keys are basically two (IIRC) field elements per arithemetic gate in the circuit or something like that.
19:26:57	nsh:	so for zerocash it's bounded by the minimum length of the accumulator functions?
19:27:12	nsh:	(which i guess are still subject to some improvement?)
19:27:26	nsh:	s/length of/length of circuits for/
19:27:30	gmaxwell:	Right, which is bounded by how big the hashfunction is in the arithemetic circuit representation, and also by how deep a hash tree you need to prove.
19:27:57	nsh:	mm
19:28:21	gmaxwell:	e.g. the 2 in 2 out circuit you'd normally need for spending verifies membership two 64 deep hashtrees (the two inputs), plus a couple hashes to verify the outputs.
19:28:54	nsh:	does that mean that a zerocash initialization has an implicit 'lifespan' in terms of the tree depth, or can that be prevented from growing indefinitely through use?
19:28:57	gmaxwell:	I suggested they consider reducing the depth to 33 or something like that and then providing the upper parts of the tree publically, this would reduce the anonymity set size to one in 8 billion coins, but would make the proving a lot faster.
19:29:09	nsh:	ah, right, it bounds the total coins
19:29:26	nsh:	(not transactions)
19:29:37	gmaxwell:	nsh: kinda. though they reason that 2^64 is close enough to infinite. I had suggested instead that they just support having more tree outside of the proof, that removes the limit and potentially lets the proof be smaller.
19:29:48	nsh:	* nsh nods
19:29:56	gmaxwell:	(mildly inflating the proof sizes)
19:30:15	c0rw1n:	* c0rw1n goes learn moar math
19:30:31	nsh:	i wonder if matt can get funding to have students simulate all these tweak ramifications
19:30:46	nsh:	(or another academic)
19:31:01	gmaxwell:	Mozilla is funding him on some other stuff.
19:31:24	nsh:	* nsh nods
19:33:20	gmaxwell:	the having part of the tree outside of the proof also fits nicely with petertodd's thoughts on spending old coins just requiring longer signatures for the MMR stuf.
19:34:06	nsh:	is that thinking explained on the list or a thread somewhere?
19:40:44	gmaxwell:	someplace!
19:40:52	gmaxwell:	I wrote up some summary of it someplace.
19:42:28	nsh:	ah, lemme know if it turns up. got plenty to read in the meantime :)
20:27:06	rdymac_:	rdymac_ is now known as rdymac
21:08:47	tromp:	tromp has left #bitcoin-wizards
22:19:04	nsh:	* nsh pokes justanotheruser's client until it stops that
22:41:18	tacotime_:	Are multisig addresses just hashes of the concatenation of the public keys of potential signatories?
22:48:31	sipa:	no
22:48:37	sipa:	there are no 'multisig addresses'
22:48:54	sipa:	there are P2SH addresses, which are the hash of a subscript
22:49:16	sipa:	if that subscript is something that enforces signatures from multiple keys, it's a multisig destination
22:49:25	sipa:	but you can't tell from just the address
22:49:30	sipa:	(nor should you)
22:55:52	tacotime_:	I see. So the subscript itself specifies that it requires multiple public keys signing in order to conduct a transaction.
22:59:08	sipa:	indeed