00:00:06justanotheruser:justanotheruser is now known as a
00:00:14a:a is now known as justanotheruser
01:16:05stqism:stqism is now known as stars0ccer
01:16:17stars0ccer:stars0ccer is now known as stqism
01:26:54nommot:Hello all
01:52:22justanotheruser:Hello
03:39:28justanotheruser:justanotheruser is now known as a
03:39:33a:a is now known as justanotheruser
05:15:55iddo:amiller: not sure what you meant by 'inherently requires knowledge of a "trapdoor"', the way it's meant to work is that the trapdoor is destroyed (meh) and only the public CRS is kept, i.e. the prover isn't supposed to know the trapdoor
05:17:54iddo:amiller: so i don't see why you think that snark is tricky without CRS, the K in snarK says that you have poly-time extractor for the witness from the prover'd data, in other words that if the prover can produce a proof then it can also produce the actual witness, this is true with the non-CRS SNARK construction
05:20:49iddo:with computational integrity proofs, this NP witness is data that shows that you executed the specified program's code
05:25:39amiller:iddo, what i mean is that the setup procedure requires knowledge of a trapdoor *during the setup procedure*
05:25:42amiller:not that the prover must know the trapdoor (the prover is just another user of the system, the entity that does the *setup* procedure is different)
05:25:51amiller:of course you can do a multiparty computation to do the setup, maybe that's good enough if you can choose these participants well
05:27:37iddo:ok but non-CRS snark doesn't have a setup procedure...
05:27:43iddo:what did you mean by 'it doesn't seem logically possible to get the "of Knowledge" i.e. the K in snarK, without that
05:27:49iddo:'?
05:27:56amiller:petertodd, you can read most of the pinocchio code if you want https://vc.codeplex.com/SourceControl/latest#pinocchio/qap/QAP.cpp
05:28:03iddo:i.e. what is "that" ? trusted setup ?
05:29:17amiller:yes the "of Knowledge" i think seems to require trusted setup, you can get a non-CRS SNARG
05:29:51iddo:i don't see what makes you think that
05:30:09iddo:why shouldn't you have poly-time extractor for non-CRS prover?
05:31:17amiller:hm, i think you're right and i'm wrong.... the non-CRS proofs are still "of knowledge" i.e. "extractable", i think because they are prove in random oracle model anyway?
05:33:00iddo:they rely on CRH i.e. if the hash function behaves as random oracle then we're good
05:33:22iddo:i don't really see the connection between "of knowledge" and trusted setup
05:34:10iddo:crh = collision resistant hash, too many acronyms here maybe :(
05:35:11iddo:the non-CRS construction produces a long PCP proof, then uses CS proof (fiat shamir heuristic) to get a succinct proof out of it
05:36:26iddo:more acronyms blah, not that CS == complete+sound is helpful to mention
05:37:04amiller:iddo, in pinocchio for example the "of Knowledge" property follows from the q-pke assumption, this is a knowledge of exponent assumption, it is along the lines of assuming that if you can compute g^a1, g^a2, etc., then you could also have computed a1, a2 etc.
05:37:57iddo:ok, how is that related to the CRS in pinocchio ?
05:38:33amiller:but since the setup process also involves computing g^s1, g^s2, etc., the same assumption implies that the setup procedure could compute the trapdoors (i.e the s1, s2 etc.) if you had the same inputs as the entity (or entities) doing the setup
05:41:39iddo:so is there some inherent connection between 'of knowledge' of the prover and the setup?
05:42:28iddo:i think the way the setup is done makes the prover's proof pass validation, and knowledge of exponent says he can only produce his proof in this way
05:43:09iddo:with non-CRS, you can have same kind of assumption like knowledge of exponent, to say prover must have produced his proof in some way
05:44:36iddo:though it wouldn't be knowledge of exponent assumption with the PCP stuff, it's some conjectures about multivariate polynomials i think
05:49:36iddo:i'll look into it, non-CRS hardness assumption should in fact be more conservative, though not sure about snarg/snark part
05:51:07amiller:hm, i'm not sure now and too tired to try working it out again, maybe it's not as obviously inherent that any setup can only be done with private coins (i.e., the private coins are effectively a trapdoor and must be assumed to be deleted by the trusted party doing the setup)
05:53:52iddo:amiller: you can be sure that the non-CRS construction exists :) only question is about the snark/snarg part of it
05:54:33iddo:i'm not even sure if snarg vs snark is a big deal in the case of bitcoin or zerocash etc.
05:55:13iddo:you still have completeness and soundness with snarg
05:56:25amiller:yes but if you have anything only computationally secure in your statement (for example the statement involves an ordinary hash function or an hmac) then it is vacuous unless it is snark not just snarg
05:58:59iddo:hmm?
05:59:33iddo:for example if you need to prove that you have a preimage to some specified output of hash function ?
05:59:38gmaxwell:iddo: if you only have a SNARG e.g. for y=sha256(x) for some X then maybe I don't know x. Vacuous in that 'duh' some x will exist.
06:00:13gmaxwell:(esp if x can be infinitely long, then you can be quite sure that some x exists even if I don't know it)
06:01:26iddo:but it's computational integrity proof in our case, the proof Pi is that you supposedly used private input x and executed the program that resulted in output y, if you can produce this Pi without knowing x, then why is it a big deal?
06:02:50gmaxwell:iddo: because x is the private knoweldge which proves you are the rightful owner of a coin, for example.
06:02:50iddo:i.e. it's not snark/snarg directly for the NP relation R(x,sha256(x))
06:03:26gmaxwell:Does it matter? If I don't really know the transacript then I may not really know x. If I don't know x I am not the owner of the coin.
06:04:05gmaxwell:transcript*
06:05:34iddo:yes snark would be best, the question about snarg is how difficult it should be to produce a proof without knowing x
06:05:59gmaxwell:Agreed, I was about to say that this may be splitting hairs, since if there is no pratical way to produce it without knowing X then thats fine.
06:06:58gmaxwell:But there ought to be at least an argument as producing a proof without knowing X violates some hardness assumption (e.g. a collision in a crh)
06:07:22maaku:maaku is now known as Guest19871
06:09:04iddo:yes snark gives rigorously what we want (though to do that it relies on conjectures), snarg doesn't, question is whether we'd have a conjecture more convincing (relies on well known conjectures) than "we conjecture that this snarg is a snark"
06:10:27iddo:i'm quite sure that the non-CRS snark construction does say "this snarg is a snark", but i'll look into how convincing are the assumptions
06:10:59iddo:s/quite sure/sure
06:13:15iddo:btw that recursive snark breakthrough is their new paper that was accepted to Crypto conference, i don't think it's anything practical yet, also the regular zerocash doesn't need it, maybe some improved version does?
06:13:40gmaxwell:it would be odd indeed for there to be a SNARG for general NP to not be a SNARK... because if you had a P time 'SNARG' cracker (e.g. no knoweldge required) for a universal circuit and you used it to check if sat instances were satisifyable[D[D or not, and it could crack without knoweldge that sounds like a proof of P==NP. :P
06:14:08gmaxwell:(but I suppose a SNARG failing to be a SNARK wouldn't have to fail for all circuits/inputs)
06:15:55gmaxwell:in any case, sometimes we care about of_knoweldge in here— for cases where the snark is used as a signature scheme, and sometimes we don't— where the snarg is use to prove some data valid in a compact way.
06:16:42iddo:well if it's SNARG and not SNARK then it'd be saying that we don't have proof yet that it might also be a SNARK, so it cannot prove P==NP
06:17:47iddo:yes for blockchain checkpoints it's enough to have snarg
06:18:49justanotheruser:Are there any previous examples of the multi-party computation that would be needed to create the random value needed to seed the SNARK that would compress the blockchain?
06:18:50gmaxwell:iddo: Right but I mean if we had a SNARG that we could prove was _NOT_ a snark on all circuits, — e.g. there was always a P time way to tell if the proof was true without knowing the witness— then that would be a proof that P==NP, since you could reformuate any NP-complete problem as a yes/no satisfaction and see if your SNARG forger is successful.
06:19:51gmaxwell:justanotheruser: what do you mean by "previous examples"
06:19:52gmaxwell:?
06:19:59iddo:gmaxwell: yes if you can prove it's not a SNARK.... but all these constructions are quite complex, no real chance of proving that
06:20:29iddo:justanotheruser: for blockchain compression it's better to use non-CRS snark
06:21:03gmaxwell:justanotheruser: the work required to generate a CRS in these CRS ZK-SNARK schemes is millions of times more complex than any MPC computation which has ever been performed, to my knoweldge.
06:22:06justanotheruser:gmaxwell: so will it probably not happen?
06:22:16iddo:justanotheruser: it isn't a big deal that the proof for the checkpoint will be a little bigger with non-CRS snark, to avoid the need for trust in the initial setup
06:22:51justanotheruser:iddo: what is non-CRS?
06:23:12justanotheruser:link to a paper maybe?
06:23:34iddo:justanotheruser: snark without trusted setup, non-CRS = no common reference string
06:23:50gmaxwell:justanotheruser: almost certantly not. I would be super happy if it were so— less because of the ability to use CRS, and more because whatever MPC system could do it would be very useful for other things. (also another issue with MPC is that many of the MPC proposals do not have strong security claims if any of the participants violate the protocol).
06:24:24iddo:justanotheruser: there are many papers at http://www.scipr-lab.org/pub
06:24:30justanotheruser:iddo: thanks
06:24:40gmaxwell:(in fact, AFAIK all MPC code which you can just download and run is not active-secure— only secure if the participants do not cheat)
06:24:56justanotheruser:gmaxwell: Is there a way to prove they're violating the protocol?
06:25:09iddo:the latest paper in Crypto is about the recursive snark stuff, isn't too clear from the name
06:25:38gmaxwell:justanotheruser: yes, run their execution under a ZK-SNARK. (and there are some nice papers proposing this)
06:25:53gmaxwell:(but hopefully you see the circular relationship here. :) )
06:26:10justanotheruser:heh
06:27:02justanotheruser:iddo: what are the most important papers I should read, especially if they will help me groc snarks
06:27:10gmaxwell:There are active secure schemes proposed which don't need a ZK-SNARK though so it's not that awful.
06:27:13justanotheruser:and in general if they will help me be wizardly
06:27:50gmaxwell:justanotheruser: if you actually want to understand them at a low level and not via a black-box engineering understanding then that is a very tall request.
06:27:59iddo:gmaxwell: the academic work on MPC secure against active attack has progressed a lot (slowdown factor of 8 or less, relative to semi-honest case), by using cut-and-choose constructions, but i'm not sure if anyone has working code yet
06:28:00justanotheruser:gmaxwell: do you?
06:28:45gmaxwell:justanotheruser: No, I understand some parts but there are swaths which I just "okay, I accept you can do this without understanding the details".
06:29:07gmaxwell:And I understand the engineering end result— what you can do with the system so long as its security assumptions hold.
06:29:31justanotheruser:okay. Well what papers should I read for understanding them via black-box
06:29:39gmaxwell:I could also go implement the verifier just fine just looking at a couple papers. I couldn't currently implement the prover.
06:29:51justanotheruser:I don't know how most cryptographic primatives work beyond black-box anywyas
06:30:03justanotheruser:and I'm in the middle of the pinnochio paper right now
06:30:20iddo:justanotheruser: right, it's difficult to understand the papers, especially as whitebox
06:32:24gmaxwell:justanotheruser: I think the pinnochio paper is pretty reasonable in general. I think reading the papers using the tools (the tinyram and vn-tinyram papers) skimming over the performance optimizations, and reading the first parts of the GGPR'12 paper, were enough for me. OTOH, I already have a pretty firm understanding of boolean and arithemetic circuits, and a general understanding other things in this space like garbled circuits, ...
06:32:30gmaxwell:... pcp theorem, etc. so YMMV.
06:34:06iddo:justanotheruser: yes the papers by GGPR give the definitions in a good way iirc, maybe this long paper covers everything http://eprint.iacr.org/2012/215
06:35:38iddo:btw my paper on fair MPC and lotteries was accepted to Crypto conference too, we will bring the gospel of Bitcoin to them for the first time :)
06:35:53gmaxwell:iddo: any idea if any of those efficient MPCs also result in public verifyability?
06:36:52justanotheruser:thanks, I'm makiong a list of what you two just said
06:37:04iddo:gmaxwell: what do you mean by publicly verifiable MPC ?
06:38:21gmaxwell:Where the MPC computation produces a public proof that the MPC computation was correct. E.g. your confidentiality is MPC secure (you're secret unless some N of M conspire), but the integrity is absolute (or at least computationally sound, even if all M are evil)
06:38:30iddo:for the trusted setup business, if dishonest majority of the "committee" wanted to cheat then they could anyway
06:39:29gmaxwell:yea, for the trusted setup business secrecy is important. But for example, in auctions and vote counting you may want stronger evidence of integrity.
06:40:20iddo:hmm google doesn't seem to return results on publicly verifiable multiparty computation, only on secret shares that can be the output of the MPC
06:40:31gmaxwell:Ideally you would use M-1 secure MPC and include all people that would ever care about the result. But sadly the people who care about the result may not be known in advance, or it may be impratical to include thousands of people in the MPC.
06:41:33gmaxwell:hm. I'm pretty sure I've seen a paper on it. (also, any scheme that turns passive secure into active secure via a SNARK should achieve this as a side effect)
06:42:17iddo:so maybe i don't understand, why active secure implies publicly verifiable ?
06:43:38gmaxwell:active secure does not. But active secure via SNARK would, assuming the snark was publically verifyable. E.g. if you take a passive MPC and prove you faithfully followed the protocol for some public MPC program and public encrypted inputs, and secret decryption keys— then publishing those snark proofs also proves the integrity of the MPC output to the public.
06:46:18iddo:can you explain a little more clearly the objective? by using some examples maybe? if the majority is dishonest then they can cheat the public, and if the majority is honest and each honest party "this MPC was executed honestly afaik" then why isn't that good enough?
06:50:43gmaxwell:Because there is a difference between cheating the confidentiality vs integrity. For example, say you want to conduct a secret ballot election for something which may pass or fail. Additionally you want to keep the votes secret because if you do not everyones vote will be revealed should the result be unanimous (or because a near tie might undermine the confidence in the decision). Votes are encrypted with N of M keys, and signed ...
06:50:49gmaxwell:... by the voters. Election officials use MPC to count the votes and output a pass/fail. If the MPC is publically verifyable then even if the officials cheat they can not change the result. Cheating allows them only to violate the confidentiality.
06:51:25gmaxwell:Meaning that the integrity is as good as if there was no MPC and the votes were made public, but the privacy is better since maybe the officials do not cheat.
06:55:06iddo:hmm so you require that the public verifiable aspect will hold even with dishonest majority ?
06:55:35gmaxwell:Correct, yes, thats the point. The verifability holds even if all are dishonest.
06:58:02iddo:ok i'm not familiar with this, i'm only familiar with publicly verifiable secret sharing, if you remember link to paper on this publicly verifiable MPC even with dishonest majority, it would be very interesting...
06:59:34gmaxwell:Yea, I'll look. As I said, it's pretty obvious how you can get one— at least one way— just do your MPC under a ZK-SNARK, potentially along with some trivial additional input verification steps to eliminate the possibility of certian malleability.
07:01:46gmaxwell:one potential application in the bitcoin space is a kind of SNARK-based-mining, where you secret share your transactions to N miners, and then they add them to a block under MPC, taking an input network state, and providing an output network state and a proof.
07:01:48iddo:i see, the output of the MPC should be the snark proof
07:02:13gmaxwell:where the transactions are now MPC-secret (no one knows what they are unless the miners conspire), and the block is SNARK valid.
07:03:23iddo:what is the goal? to avoid miners from setting policies on which txns they like to include?
07:03:26gmaxwell:such a scheme could potentially inhibit some kinds of censorship in a bitcoin like system... since no single party would even know what the transactions being processed were.
07:03:30gmaxwell:yep.
07:23:13gmaxwell:iddo: http://www.cs.ucla.edu/~rafail/PUBLIC/77.pdf < here is a paper on active secure MPC from passive plus ZKP, with a number of citations. However it doesn't talking about the publically verifyable side effect.
07:23:35gmaxwell:I really doubt I came up with the usefulness of public verification on my own; but at the moment I'm not able to find a paper mentioning it.
07:27:25iddo:cool, first two authors are in my faculty, i could ask them questions after i understand this better
07:28:43gmaxwell:I'm pretty sure at some point I saw a paper that very explicitly made the argument for the usefulness of public verifyable MPC, just can't find it again...
11:19:04cajg_:cajg_ is now known as cajg
12:14:51samson2:samson2 is now known as samson_
12:21:29petertodd:~.~.
12:45:57iddo:gmaxwell: maybe this paper is what you had in mind: http://eprint.iacr.org/2014/075.pdf
12:49:29gmaxwell:Yep, that would be it!
12:49:50gmaxwell:apparently the magic search term was auditable.
12:52:55kinlo:pompom
13:10:40qwertyoruiop_:qwertyoruiop_ is now known as qwertyoruiop
14:52:23andytoshi:haven't read past the abstract, but this seems very relevant to our interests: http://eprint.iacr.org/2014/364
15:19:29andytoshi:title: "Deleting Secret Data with Public Verifiability"
15:24:40Luke-Jr:andytoshi: relevant how? also, I didn't read it, but I'm pretty sure it's impossible
15:24:46Luke-Jr:I mean, someone can just copy before delete.
15:38:16andytoshi:Luke-Jr: they used the phrase 'intuitively impossible' so they seem to be aware that it's obviously impossible, but still believe they have a result worth publishing. it's of interest since there was a long discussion last night about deleting CRS trapdoors
15:38:53andytoshi:...but in section IV.A they discuss their threat model and explicitly disregard this case. it is assumed the user owns the data and wants it deleted, but doesn't trust the deletion hardware
15:40:51andytoshi:so actually this is not interesting for bitcoin-style protocols which require public verification despite all parties possibly cheating
15:43:21Luke-Jr:andytoshi: deletion hardware can make a copy too?
15:43:35Luke-Jr:or is the idea to encrypt it on disk so a copy is worthless?
15:49:17andytoshi:Luke-Jr: that's part of it, but obvs the hardware can also just copy the key (if ever it has access to it). so it does some dance to make sure that if the data ever leaks, this is publically verifiable
15:49:31andytoshi:idk the detals, i stopped reading after the threat model wasn't interesting :P
16:16:22maaku:maaku is now known as Guest26234
16:57:12[BNC]dansmith:[BNC]dansmith is now known as dansmith_btc
17:02:37maaku:maaku is now known as Guest56320
17:41:25maaku:maaku is now known as Guest31658
18:15:30pigeons:pigeons is now known as Guest41976
18:53:49ryan-c:is there any any public documentation on how bitcoin is going to encrypt the blockchain on disk?
18:59:29sipa:#bitcoin-dev
20:15:14Vitalik:Vitalik is now known as Vitalik_
21:05:28sl01:petertodd: please drop some maidsafe knowledge after you meet up with them, it doesn't seem there exists any indvidual that meets all of the following crieria: understands what maidsafe thinks their security assumptions/model is, is intelligent, can give concise intelligible explanations
21:07:26Luke-Jr:sl01: that presupposes that maidsafe understands their security model
21:07:31Luke-Jr:<.<
21:08:51sl01:you may be on to something >.>
21:10:17phantomcircuit:Luke-Jr, finally got a beaglebone to netboot
21:10:31phantomcircuit:black magic
21:10:47Luke-Jr::o
21:11:12Luke-Jr:* Luke-Jr pours holy water on phantomcircuit's beaglebones and watches the difficulty drop
21:11:18phantomcircuit:bwahah
21:24:31iddo:amiller: gmaxwell: about non-CRS snark (i.e. not snarg), the hardness assumption is indeed much more conservative than CRS snark, only CRH assumption is needed, it's sections 12.1 and 12.5 of http://eccc.hpi-web.de/report/2012/045/
21:27:31iddo:though it's a bit tricky because with deterministic hash like sha2 you cannot prove that the prover can never create false proofs, so you need ensemble e.g. random CRS as hash(CRS,.)
21:28:11iddo:but the point is that this CRS isn't a trapdoor, and anyway heuristically you can forget about this CRS and just use sha2 etc.
21:29:23amiller:iddo, interesting, i should try to understand this, i haven't been able to parse so far what their difference in knowledge extractor is..
21:32:13iddo:i don't claim to understand the proofs either, but there's extractor somehow that's based only on the assumption of resistance to hash collisions
21:38:38iddo:i'll try to help with actual programming of non-CRS snark, then i'll know how bad the situation is... initial proof size will probably be big
21:52:39Guest59783:Guest59783 is now known as _Tristan_
21:53:01_Tristan_:_Tristan_ is now known as [Tristan]