| 00:00:28 | shen_noe: | what if we change this to check that the blinding factors don't add exactly to zero, but rather the sum of inputs and outputs commitments leaves zG |
| 00:00:39 | shen_noe: | so sum of input commitments - output commitments is a commitment to zero |
| 00:00:51 | shen_noe: | secret key only known to the sender |
| 00:01:26 | shen_noe: | now, take a ring signature over C_1, ..., C_s, ..., C_n where C_i are possible input commitments taken ad-hoc from blockchain |
| 00:01:35 | shen_noe: | C_s being the one belonging to signature |
| 00:01:47 | shen_noe: | actually a ring sig over C_1 - outputs, ..., C_s - outputs, ..., C_n - outputs |
| 00:02:02 | shen_noe: | so sender can prove that 1/n of these is a commitment to zero |
| 00:02:28 | shen_noe: | (the LLW ring sig's are nice for this purpose) |
| 00:03:33 | shen_noe: | after this, proceed as in normal CT (proving outputs are commitments to positive values), using boromean sigs if that helps,, etc |
| 00:04:06 | shen_noe: | thoughts? |
| 00:06:31 | shen_noe: | *C_s being the one belonging to the "signer" |
| 00:14:18 | andytoshi: | shen_noe: i'm not quite sure what you gain here .. you need that every `inputs - outputs` is zero, so proving that 1/n of them are seems like it'd just be wasteful |
| 00:14:47 | MRL-Relay: | [shen] andytoshi, I want to prove that 1/n of inputs - outputs is a commitment to zero |
| 00:15:08 | MRL-Relay: | [shen] to not reveal which input index belongs to me |
| 00:15:31 | andytoshi: | oh, i see 1/n of inputs |
| 00:16:44 | andytoshi: | i guess, you are combining this with monero's usual ringsigs.. |
| 00:16:58 | shen_noe: | yeah, or the LLW that you guys used (which are more efficient) |
| 00:17:01 | andytoshi: | and what it gets you is that you can ring-sign with arbitrary input sets, and not care about their sizes |
| 00:17:21 | shen_noe: | and hide amounts better than currentlyy |
| 00:18:22 | andytoshi: | yeah, the exact scheme is not so important, what i'm trying to get is the high-level .. you have (a) a ringsignature over several inputs which proves you own one of them, (b) a "ring-CT proof" that one of these inputs is the right size |
| 00:18:38 | shen_noe: | yeah |
| 00:18:46 | andytoshi: | so, you need to link these two signatures somehow to make sure the input you're spending and the input whose value you're using are the same one |
| 00:18:54 | andytoshi: | but i'd guess this is easy once you write out the algebra |
| 00:19:35 | andytoshi: | but off the top of my head i'm not certain how |
| 00:20:31 | andytoshi: | or maybe the original ring signature is not important actually.. |
| 00:20:38 | shen_noe: | so you need to link the two sigs: I think you can include all the original C_in's so a verifier can recreate the original sig themselves |
| 00:20:43 | shen_noe: | (maybe?) |
| 00:20:49 | andytoshi: | you use the delta from 0 in the `input - outputs` as your verification key |
| 00:21:05 | shen_noe: | yeah |
| 00:21:13 | andytoshi: | then if you are able to prove that `input - outputs == 0` this also proves you own the input |
| 00:21:26 | andytoshi: | (i think) |
| 00:21:37 | shen_noe: | so in language of CT paper, (x+z)G + aH = y1G + b1H + y2G + b2H |
| 00:21:44 | shen_noe: | where x+z = y1+y2 |
| 00:21:48 | shen_noe: | and a = b1+b2 |
| 00:21:49 | andytoshi: | yeah |
| 00:21:54 | shen_noe: | then z is sk |
| 00:21:57 | andytoshi: | yeah |
| 00:24:27 | andytoshi: | so, let's think how this would work for a one-input-one-output tx, with a ringsize of one |
| 00:24:39 | andytoshi: | so there is no ring sig magic here, i'm just trying to figure out when/how the pubkey is determined |
| 00:25:33 | andytoshi: | with the current CT setup you've got something like an output value of `rG + vH` where r is secret and v is the hidden value |
| 00:25:36 | shen_noe: | ok, so above equation I guess becomes (x+z)G + aH = xG + aH |
| 00:25:48 | andytoshi: | yeah, sure, let's use your notatin |
| 00:26:18 | andytoshi: | the output is (x + z)G + aH? z is the key, a is the value, what is x? |
| 00:26:40 | shen_noe: | x + z = y is constructed as an equation of blinding factors |
| 00:26:53 | shen_noe: | oh no y |
| 00:27:05 | andytoshi: | ok i think you don't need both x and z |
| 00:27:42 | andytoshi: | oh, no, you do, cuz you have to reveal zG at some point here |
| 00:27:48 | andytoshi: | which if z was the only blinding factor, would reveal a |
| 00:29:18 | andytoshi: | so my question is: what is the output? a value commitment (x + z)G + aH as well as a verification key zG? |
| 00:29:47 | shen_noe: | output is yeah, yG + aH, where a is the sent amount, y is blinding factor |
| 00:29:57 | andytoshi: | kk gotcha |
| 00:30:34 | shen_noe: | so let's see (x + z)G + aH - yG + aH = zG |
| 00:30:41 | shen_noe: | if z = y |
| 00:30:55 | shen_noe: | and presumably you know log_G zG |
| 00:30:57 | andytoshi: | if x = y you mean |
| 00:30:58 | shen_noe: | since you made it |
| 00:31:20 | shen_noe: | yes |
| 00:31:24 | shen_noe: | (sorry been up late) |
| 00:31:28 | andytoshi: | np |
| 00:31:44 | shen_noe: | so if x = y, then (x + z)G + aH - yG - aH = zG |
| 00:32:16 | shen_noe: | now, you know log_G zG, so you can sign make a signaturre from the above difference |
| 00:32:45 | andytoshi: | yeah, understood |
| 00:32:56 | andytoshi: | can you remind me what normally happens? basically z = 0 in that case |
| 00:33:29 | shen_noe: | normally, z = 0, so it's more like xG + aH - yG - aH = 0 if x = y |
| 00:33:32 | andytoshi: | oh, never mind, i'm being silly |
| 00:33:38 | shen_noe: | the network verfies it's actually "is" zero |
| 00:33:41 | shen_noe: | rather than commitment to zero |
| 00:33:49 | andytoshi: | i was like "how do you prove you know the input" but that's not the commitment-proof's job in the original system |
| 00:33:55 | shen_noe: | sure |
| 00:34:07 | shen_noe: | :P |
| 00:34:38 | andytoshi: | kk so now i need to think for a few mins about if you can game this somehow .. i guess not if zG is in the output and can't be changed |
| 00:35:07 | shen_noe: | greatly appreciated |
| 00:35:43 | andytoshi: | ok, so i think i can choose {z, zG} then spend any output like this by taking the input point and adding zG to it to get my output point |
| 00:36:21 | andytoshi: | so i don't actually know x or a in this case |
| 00:36:39 | shen_noe: | hmm, let's see how that would work |
| 00:36:55 | shen_noe: | so C_in is chosen arbitrarilyy |
| 00:37:12 | shen_noe: | you don't know C_in = xG + aH (you don't know x or a) |
| 00:37:46 | shen_noe: | so zG + C_in - C_out = zG if C_in = C_out |
| 00:37:59 | andytoshi: | (i'll let you work thru this, meanwhile i think i have a fix, tho it's a little bigger than a single sig) |
| 00:37:59 | shen_noe: | is that what you mean? |
| 00:38:02 | andytoshi: | yes |
| 00:38:16 | shen_noe: | so basically you can send funds back to their outputs? |
| 00:38:20 | shen_noe: | I mean inputs |
| 00:38:40 | andytoshi: | hmmm, maybe that's all this wolud do.. |
| 00:38:55 | shen_noe: | it still might cause a problem somehow |
| 00:40:32 | andytoshi: | is zG part of the output that's being spent? or is the idea is it's only computed as C_in - C_out? |
| 00:41:09 | shen_noe: | so I'm thinking the input you know is xG + aH, then you decompose x into x = z + y |
| 00:41:24 | shen_noe: | and then use y = sum outputs blinding factors |
| 00:41:27 | shen_noe: | and z is sk |
| 00:42:13 | andytoshi: | understood |
| 00:42:30 | andytoshi: | my question is whether z is forced by the output that you're spending |
| 00:42:38 | andytoshi: | i think the answer should be yes |
| 00:43:24 | andytoshi: | like, what i'm saying is the output will be {C_in, zG} |
| 00:43:24 | shen_noe: | it seems like it's forced not by output, but by the blinding factors you pick |
| 00:43:32 | andytoshi: | ok, so the output is only C_in? |
| 00:43:57 | shen_noe: | yeah C_in is something you've received from previous transaction |
| 00:44:14 | andytoshi: | then i can choose C_in from an arbitary output, choose z randomly, and produce a tx whose output is C_out = C_in + zG |
| 00:44:24 | andytoshi: | now i know z and can sign anything with it |
| 00:44:43 | andytoshi: | i think putting zG in the output fixes this |
| 00:44:44 | shen_noe: | lets see |
| 00:45:12 | shen_noe: | C_in = xG + aH, C_out = xG + aH + zG |
| 00:45:32 | shen_noe: | then C_in - C_out = -zG |
| 00:45:56 | andytoshi: | ..right, and then i know -z and can sign for that |
| 00:46:17 | shen_noe: | so you can find z, then you can send funds to C_in + zG |
| 00:46:42 | shen_noe: | let's see |
| 00:46:50 | shen_noe: | what about the range proof in this case? |
| 00:47:06 | andytoshi: | there should've been a range proof attached to C_in right? |
| 00:47:08 | andytoshi: | i just copy that |
| 00:47:19 | shen_noe: | now it's a range proof for C_in + zG though |
| 00:47:32 | andytoshi: | oh hmm |
| 00:47:37 | shen_noe: | does it still work the same? |
| 00:47:48 | shen_noe: | (this is extremely helpful btw thx) |
| 00:48:14 | andytoshi: | one sec i gotta find the rangeproof writeup to remind myself |
| 00:48:27 | shen_noe: | same |
| 00:48:49 | andytoshi: | it's about:blank |
| 00:48:53 | andytoshi: | lol https://people.xiph.org/~greg/confidential_values.txt |
| 00:50:23 | shen_noe: | so it looks something like C_in + z_G == C_1 + C_2 + ... + C_5 |
| 00:50:56 | shen_noe: | where C_i represent proofs of the binary coefficients of C_in + z_G |
| 00:51:18 | shen_noe: | so C_1 proves that first binary coefficient of C_in + z_G is 0 or 1 |
| 00:52:17 | andytoshi: | yeah, so actually what you do is add zG to one of the C_i's |
| 00:52:18 | shen_noe: | so to prove C_1 you have to know either log_G (C_in + z_G) or log_G (C_in + zG - H) |
| 00:52:29 | andytoshi: | yup |
| 00:53:06 | andytoshi: | so if i have a signature for xG on m, can i mar this into a sig for (x + z)G on m, knowing only z? |
| 00:53:25 | andytoshi: | (x is just an arbitrary secret value, it doesn't correspond to anything we've mentioned so far) |
| 00:53:46 | shen_noe: | hrm |
| 00:54:03 | andytoshi: | one sec,gotta do this on paper.. |
| 00:54:09 | shen_noe: | yeah |
| 00:54:33 | andytoshi: | yeah you totally can for schnorr sigs |
| 00:54:47 | shen_noe: | using homomorphic prop? |
| 00:55:00 | andytoshi: | yeah, s -> s + zH(m||r), r -> r |
| 00:55:31 | andytoshi: | if s = k + xH(m||r) this gives you s' = k + (x + z)H(m||r) |
| 00:55:49 | shen_noe: | so that would be like signing with x + z, without knowing x, and only knowing xG |
| 00:55:59 | andytoshi: | right |
| 00:56:14 | andytoshi: | being unable to do this is -not- a standard security property that i'm aware of, i doubt it holds for any standard sig system |
| 00:56:38 | shen_noe: | so how do you sign with (x + z) without knowing (x + z) ? |
| 00:56:56 | andytoshi: | oh, wait, i was assuming you had a signature on x |
| 00:57:06 | andytoshi: | but obviously you don't, not on your new transaction.. |
| 00:57:30 | shen_noe: | hrm |
| 00:57:38 | andytoshi: | i'm beginning to think this is ok |
| 00:58:19 | shen_noe: | my super-caffeinated brain which slept 2 hours thinks its ok |
| 00:58:28 | shen_noe: | but that's not usually enough to actually "be" ok |
| 00:58:42 | shen_noe: | as my advisor has shown me numerous times |
| 00:58:42 | andytoshi: | i do think this is gonna be a bear to argue correctness for |
| 00:58:46 | andytoshi: | yeah lol |
| 01:00:07 | andytoshi: | ok, my next attack is, maybe you know (x + z) but not x or z.. |
| 01:00:25 | andytoshi: | i think you can't do this because x is gonna be different for each bit of the range-proof in the output |
| 01:00:45 | shen_noe: | yeah, as long as output is not 1H |
| 01:00:58 | shen_noe: | also, to show commitmment to zero, you have to know z? |
| 01:01:19 | andytoshi: | yeah |
| 01:02:33 | andytoshi: | ok, so, you ringsign with (C_i, C_i - H) to proof either 0 or 1, and there are always multiple random C_i's |
| 01:02:53 | andytoshi: | -but- i think we can attack this only marring one of them, you do C_1 -> C_1 + zG say |
| 01:03:04 | shen_noe: | ok |
| 01:03:29 | andytoshi: | now, the remaining C_i's have unchanged so you can keep their part of the rangeproof |
| 01:04:04 | andytoshi: | and you set things up so that you know the DL of (C_1 + zG) even tho i don't know z or the DL of C_1 |
| 01:04:12 | andytoshi: | now you can reproduce that part of the rangeproof |
| 01:04:27 | andytoshi: | -but- i think you're screwed now because you have to produce a signature with z on top of this right? |
| 01:05:01 | shen_noe: | yeah, at the end you need to sign with z |
| 01:05:12 | andytoshi: | ok, i think this is safe actually |
| 01:05:15 | shen_noe: | to prove inputs - ouputs = commitment to zero |
| 01:05:31 | andytoshi: | cuz you always have to sign with (a) z and (b) z + r, where r is some randomness from the input's rangeproof |
| 01:05:57 | andytoshi: | you don't know r unless you own the output, so you can't do both unless you own the output |
| 01:07:15 | shen_noe: | ..yes |
| 01:07:20 | shen_noe: | I think that's right |
| 01:08:04 | andytoshi: | oh, but now have we broken the value proofs? |
| 01:08:22 | andytoshi: | like, can you go spending with outputs > inputs? |
| 01:08:40 | andytoshi: | (i think) the answers is no, as long as nobody knows the DL of your generators |
| 01:09:36 | shen_noe: | I was hoping the value proofs were pretty much the same as in CT |
| 01:10:21 | shen_noe: | so.. I think outputs = inputs is guaranteed by commitment to zero of the original summation |
| 01:11:14 | shen_noe: | and then value proofs are just to prove C_out has aH with a in the right range |
| 01:11:57 | andytoshi: | i think you're right |
| 01:13:33 | shen_noe: | gmaxwell invented ct also: so I was thinking of modifying the summation equation (In1 + In2 + In3 + plaintext_input_amount*H...) - |
| 01:13:33 | shen_noe: | (Out1 + Out2 + Out3 + ... fees*H) == 0. |
| 01:13:41 | shen_noe: | to be instead a commitment to zero |
| 01:14:35 | shen_noe: | now take a ring sig over (C_1 - \sum outputs, ..., C_s - \sum outputs, ..., C_n - \sum outputs) |
| 01:14:40 | shen_noe: | where s is secret index |
| 01:14:42 | andytoshi: | shen_noe: i think 100% of CT was gmaxwell and adam3us, i had nothing to do with it |
| 01:14:55 | shen_noe: | ahh i see I saw your name on the boromean paper |
| 01:15:06 | gmaxwell: | shen_noe: adam proposed in his original thread that showing knowedlge of the discrete log of the blinding factor as a replacement for the normal signature (so long as you don't mind losing all the useful script properties) |
| 01:15:11 | andytoshi: | yeah, i wrote the paper but all i invented was the time travel stuff |
| 01:15:23 | andytoshi: | which was purely an explanatory device |
| 01:15:36 | shen_noe: | gmaxwell, ahh nice |
| 01:15:55 | shen_noe: | I've just seen your writeup of it actually |
| 01:16:00 | gmaxwell: | shen_noe: but if I send you coins I also know your blinding factors, so the send is not a payment (as I can claw the funds back) unless we use an interactive proptocol to have you generate the blinded coins. |
| 01:16:50 | gmaxwell: | (and their range proofs, etc) |
| 01:17:05 | andytoshi: | oh, i see it now, yeah, you can't hide z from the payee without interaction .. dammit |
| 01:17:14 | shen_noe: | oh i see... hmm yes sender would know the receivers blinding factors obviously |
| 01:17:30 | gmaxwell: | so it didn't really seem like a big gain, also since the rangeproofs can often be omitted. |
| 01:17:54 | andytoshi: | well, the gain was really for monero, so you could ringsign over inputs of varying values |
| 01:18:00 | shen_noe: | the reason I was considering this, is if you modify for CryptoNote, then you need someway tto hide the input index |
| 01:18:02 | shen_noe: | yeah |
| 01:18:37 | gmaxwell: | Adam actually had a proposal to for a ringsig version, but I'm not sure if it was complete or correct. |
| 01:19:15 | shen_noe: | would love to see that.. hmm |
| 01:19:25 | shen_noe: | do you remember how many steps in the interactive protocol? |
| 01:19:32 | gmaxwell: | I think the ringsig is not very exciting though since coninjoin works so will with the CT approach... and the ringsig has other costs. |
| 01:19:52 | shen_noe: | i.e. most sigma protocols (3 steps) can be made non-interactive |
| 01:20:15 | andytoshi: | shen_noe: it won't be a sigma protocol, here both parties need knowledge of secret data |
| 01:20:17 | gmaxwell: | shen_noe: it requires interaction because the reciever needs to have a secret. |
| 01:20:25 | shen_noe: | yeah, it was more of a thought exercise, since the size with ring sigs included makes it fairly large |
| 01:20:49 | shen_noe: | I see, so something like receiver passing you their blinding factor |
| 01:21:52 | gmaxwell: | shen_noe: they can't do that or you can spend their coins. Rather the reciever has to create two outputs and their range proofs and tell you their blinding factor sum and value sum. |
| 01:21:52 | shen_noe: | I wonder if you could "key-image" outputs |
| 01:22:07 | shen_noe: | and then since change-addresses are one-time keys... |
| 01:22:29 | gmaxwell: | then you can create a transaction which includes their outputs where only you know the discrete log of the sum of the blinding factors. |
| 01:22:36 | andytoshi: | shen_noe: yeah, the LWW paper has a really generic way of making key images, you just have another generator H, then the key image of xG is xH, and you provide a proof-of-equal-discrete-logs |
| 01:22:51 | andytoshi: | or ring-proof-of-equal-discrete-logs or whatever |
| 01:24:06 | shen_noe: | andytoshi, I'll have to read that more carefully |
| 01:24:33 | gmaxwell: | (but then you get into problems where you have to prohibit spending those two coins in the same transaction and other stupidity.) |
| 01:24:57 | shen_noe: | so.. maybe it would work, with some caveats on how you spend coins.. |
| 01:25:11 | CodeShark: | are many of the insights in partially homomorphic crypto using the discrete log problem applicable to lattice-based crypto? |
| 01:25:11 | gmaxwell: | and interaction on send. |
| 01:25:43 | shen_noe: | like all oupts are otk's by force, and can be spent once |
| 01:25:46 | andytoshi: | CodeShark: i don't -think- so |
| 01:27:19 | andytoshi: | CodeShark: lattice crypto is about having a secret basis in which matrices can be efficiently manipulated in sorta ad-hoc ways, i'm not aware of something similar to this "have two generators so given aG + bH nobody can know its discrete log" |
| 01:27:38 | gmaxwell: | shen_noe: double spending is not an issue there; the problem is the symmetry of the reciever and the senders knoweldge. It can be broken, with a cost, but the benefit is pretty small. |
| 01:28:00 | CodeShark: | my understanding (which admittedly isn't as good as I would like) is that lattice based homomorphic encryption is based on ideals |
| 01:28:41 | CodeShark: | as in ideals of rings |
| 01:28:49 | shen_noe: | gmaxwell, right, I was momentarily confused - so makes the transaction with the coins first wins |
| 01:29:02 | CodeShark: | but I really need to read up more :p |
| 01:29:08 | andytoshi: | CodeShark: oh, i'm only dimly aware of that side of the literature |
| 01:29:19 | andytoshi: | if you have any intuitions they probably trump mine |
| 01:29:53 | gmaxwell: | gmaxwell has left #bitcoin-wizards |
| 01:30:19 | CodeShark: | * CodeShark pulls out his old algebraic geometry texts :) |
| 01:34:21 | shen_noe: | so maybe it would need a "coins" received function where receiver scans blockchain and when they find their coins, send it to a new address.. I'm not sure what that implies |
| 01:34:53 | shen_noe: | andytoshi thx for feedback |
| 01:35:00 | andytoshi: | np shen_noe |
| 01:35:05 | andytoshi: | but i think now the complexity is not worth it |
| 01:35:15 | andytoshi: | interaction is pretty much a dealbreaker |
| 01:35:32 | shen_noe: | yeah: there is a much simpler method (but not as good) which already works in monero actually |
| 01:35:46 | shen_noe: | just split up your amount into like n = n_1 + n_2 + ... + n_m |
| 01:35:56 | shen_noe: | and the cardinality of possiblities is 2^m |
| 01:36:55 | shen_noe: | (since one-time keys for change addresses and receive addresses) |
| 01:38:08 | shen_noe: | although I think you could get away with not full interaction: receiver only interacts by scanning blockchain and "accepting" their transaction |
| 01:38:22 | shen_noe: | by sending it to a new address they control |
| 01:38:40 | shen_noe: | with new blinding factors |
| 01:38:42 | andytoshi: | i see what you're saying, yeah, that works |
| 01:38:59 | shen_noe: | so it's open to chargebacks until the receiver decides they want it |
| 01:39:23 | andytoshi: | i think |
| 01:39:41 | shen_noe: | and (unless other problems) it costs an additional transaction fee |
| 01:40:53 | shen_noe: | in any case, gotta run |
| 02:57:26 | MatrixBridge: | MatrixBridge is now known as 5EXABJ6GG |
| 05:38:12 | gmaxwell: | https://github.com/scipr-lab/libsnark/commits/master < got code for sha256 15 days ago |
| 05:53:21 | CodeShark: | so you can compress many levels of sha256 into a single proof whose size does not depend on the number of levels in a tree? |
| 05:55:46 | CodeShark: | oh very cool |
| 05:57:10 | CodeShark: | so it's an optimized "gadget" within an NP-complete language |
| 05:57:55 | Luke-Jr: | hm! is it possible, I wonder, to design a PoW that *must* be performed in a SNARK? <.< |
| 05:59:32 | CodeShark: | creating the proof is expensive - but in principle verification could be made much simpler than just brute force hashing |
| 05:59:50 | CodeShark: | that's why the NP-complete part :p |
| 06:00:54 | Luke-Jr: | right, I'm wondering this as a way to prevent block withholding on even p2pool |
| 06:00:55 | CodeShark: | substitute "in practice" for "in principle" :) |
| 06:01:09 | gmaxwell: | Luke-Jr: you've asked this before. The answer is no. |
| 06:01:18 | Guest30532: | Guest30532 is now known as amiller |
| 06:02:04 | Luke-Jr: | :| |
| 06:02:37 | gmaxwell: | CodeShark: yes, you can, so long as you're willing to take on a whole host of new strong cryptographic assumptions; and a long (like 30 seconds to minutes) proving time. And verification that runs on the order of 200 proofs per second. |
| 06:03:40 | CodeShark: | it's based on paired crypto? |
| 06:04:24 | gmaxwell: | _pairing_ crypto; though it has many more assuptions than just the hardness of discrete logs in bilinar groups and the normal stuff for most pairing crypto. |
| 06:04:57 | CodeShark: | pairing crypto, yes. that's what I meant :) |
| 06:05:43 | gmaxwell: | (I'm not dissing the approach I think it's just important to keep in mind Magic's Price) |
| 06:06:12 | CodeShark: | are the other assumptions largely surrounding statistical vs. computational zero knowledge? |
| 06:06:20 | gmaxwell: | no, absolutely not. |
| 06:06:46 | CodeShark: | so all these approaches don't assume anything more than computional zk, right? |
| 06:06:48 | gmaxwell: | (well the non-falsifyable one is) |
| 06:06:55 | CodeShark: | or specifically, this library |
| 06:07:13 | gmaxwell: | CodeShark: the ZK in this is perfect. The soundness is computational. |
| 06:07:24 | CodeShark: | ok, got it |
| 06:07:34 | gmaxwell: | No succinect proof system for genral NP can have better than computational security in any case (owing to a counting argument). |
| 06:07:46 | gmaxwell: | (er better than computational security for soundness) |
| 06:08:31 | CodeShark: | right... |
| 06:09:24 | gmaxwell: | but I'm not talking just about the hardness, I mean there are new strong assumptions; e.g. that certant functions cannot be efficiently computed; for which no proof currently exists that reduces them to an existing prior known strong assumption. (like the hardness of the computational discrete log problem in a bilinear group). They sound plausable and fortunately its an interesting enough area t |
| 06:09:30 | gmaxwell: | hat people are actually working on breaking them and such. |
| 06:09:53 | CodeShark: | so what are the other big assumptions with bilinear group stuff? |
| 06:10:15 | CodeShark: | besides difficulty of discrete log, of course |
| 06:12:47 | CodeShark: | oh, hmm |
| 06:13:10 | CodeShark: | nvm, I was late on the keyboard :p |
| 06:14:44 | gmaxwell: | The papers go over them, though unless you're a current postdoc in that subfield you'll probably (like me) mostly just shrug at them. :) |
| 06:17:45 | CodeShark: | this whole zkSNARK thing does seem too good to be true...so yeah, there's a price for that magic |
| 06:18:06 | gmaxwell: | CodeShark: one of them is that it has trusted setup. |
| 06:18:25 | CodeShark: | is there no known way around that still? |
| 06:19:25 | gmaxwell: | There are proposals to potentially use multiparty computation for it, so the trusted setup gets some threshold security. |
| 06:20:10 | gmaxwell: | People are also working on other schemes for NP proofs with a totally different cryptographic basis which won't have that problem; but their proofs will be less efficient. |
| 06:20:25 | CodeShark: | less efficient for the prover? the verifier? or both? |
| 06:20:57 | gmaxwell: | Less space efficient. They may well be faster to verify. |
| 06:22:34 | CodeShark: | by totally different cryptographic basis you're referring to something other than bilinear crypto or pairing crypto? |
| 06:22:39 | gmaxwell: | right |
| 06:24:01 | CodeShark: | but still using discrete log? or LWE or something else? |
| 06:28:14 | gmaxwell: | No; likely using using just random oracle assumptions. |
| 06:29:15 | gmaxwell: | PCP theorem plus fiat shamir tell us that at least in principle there are efficient computationally sound, statstically private proof systems for NP; that have no strong assumptions except the RO used for the fiat shamir. Though making them pratical is hard. |
| 06:30:06 | gmaxwell: | (as the most direct routes require you to e.g. build a hashtree over a set of bits with substantially more entries than atoms in the universe) |
| 06:42:52 | gmaxwell: | andytoshi: do you see any obvious way to do an _efficient_ proof of polysig equivilence. E.g. say there is a set of keys for a polysig, and some unknown permutation, and I want to prove to you that a given polysig series corresponds to that set without revealing the permutation? |
| 08:05:18 | barjavel.freenode.net: | topic is: This channel is is for discussing theoretical ideas with regard to cryptocurrencies, not about short-term Bitcoin development | http://bitcoin.ninja/ | This channel is logged. | For logs and more information, visit http://bitcoin.ninja |
| 08:05:18 | barjavel.freenode.net: | Users on #bitcoin-wizards: andy-logbot davi ThomasV binaryatrocity_ OneFixt Mably sneak damethos arubi_ spinza drwin mjerr d1ggy Xh1pher gmaxwell prodatalab Zooko-phone amiller [7] thrasher` 5EXABJ6GG moa Dr-G2 gielbier DougieBot5000 SubCreative sparetire_ PaulCapestany GAit jmcn_ melvster btcdrak AaronvanW SwedFTP JackH bosma gill3s c0rw1n BigBitz dc17523be3 SDCDev NewLiberty_ Aquentin nuke1989 ebfull Tiraspol Luke-Jr Starduster paveljanik alferz nsh AlexStraunoff |
| 08:05:18 | barjavel.freenode.net: | Users on #bitcoin-wizards: Graet bedeho veox Emcy maaku go1111111 execut3 mkarrer_ akrmn UllrSkis goregrind barthG K1773R fkhan Alanius sparetire luny justanotherusr mengine devrandom sdaftuar narwh4l adam3us cdecker badmofo Madars roybadami LeMiner waxwing digitalmagus lnovy MRL-Relay theymos stonecoldpat epscy dgenr8 mountaingoat pollux-bts Jaamg rustyn forrestv espes gnusha Cory tucenaber bliljerk101 elastoma ThinThread jonasschnelli huseby null_radix catcow adams__ |
| 08:05:19 | barjavel.freenode.net: | Users on #bitcoin-wizards: Taek rasengan cfields phantomcircuit kanzure sadoshi TD-Linux GreenIsMyPepper richardus sl01 michagogo otoburb isis ttttemp kinlo nephyrin` Krellan vonzipper larraboj_ mariorz coryfields_ optimator stevenroose BlueMatt eric afdudley warptangent ryan-c crescendo prosodyContext mappum wiz nickler_ jbenet kyuupichan livegnik pigeons davout Fistful_of_Coins mikolalysenko fluffypony BananaLotus Logicwax scoria andytoshi superobserver STRML jouke |
| 08:05:19 | barjavel.freenode.net: | Users on #bitcoin-wizards: jaromil fenn gribble nanotube Guest87353 grandmaster indolering BrainOverfl0w [ace] catlasshrugged throughnothing poggy guruvan dignork yoleaux gavinandresen Anduck helo grubles heath roasbeef ggreer Iriez starsoccer Muis Xzibit17 comboy petertodd wumpus a5m0_ jessepollak dansmith_ [d__d] sturles HM midnightmagic merlincorey warren azariah_ jrayhawk qawap Meeh_ mm_1 tromp_ koshii _whitelogger dasource jcorgan sundance bsm117532 CodeShark |
| 08:05:19 | barjavel.freenode.net: | Users on #bitcoin-wizards: gwillen lclc wizkid057 ajweiss so s1w yrashk CryptoGoon artifexd runeks kumavis platinuum yorick Apocalyptic iddo smooth weex berndj harrow harrigan brand0 leakypat Eliel xabbix @ChanServ AdrianG morcos |
| 14:33:21 | andytoshi: | gmaxwell: (a) no, and (b) i think this is pretty hard actually, adam and i ran repeatedly into a related problem (proving a sum of keys was actually computed using the keys, without eg adding r to one and -r to another) when we were trying to make constant-size ringsigs. i don't remember the details but it was related to permutations (since the real key had to occupy a specific "slot" or something |
| 14:33:23 | andytoshi: | like that which ofc should not be revealed) and we got nowhere |
| 14:33:36 | andytoshi: | i'll think about how to do it in say linear time wrt the size of the permutation tho.. |
| 14:35:14 | andytoshi: | but what was killing us was not so much our efficiency requirements, it was that you can't do much of anything to aggregate keys except adding them together, and that loses a ton of information |
| 14:36:41 | kanzure: | would there be any value in limiting the number of transactions in each block? rather than block size. |
| 14:36:46 | kanzure: | or, in addition to block size. |
| 14:37:31 | andytoshi: | kanzure: it'd encourage coinjoining |
| 14:37:36 | kanzure: | awful! |
| 14:37:47 | andytoshi: | lol |
| 14:48:37 | maaku: | kanzure: value? yes it'd make the merkle trees smaller |
| 14:49:13 | maaku: | but while it encourages coinjoining, it works against OWAS or some p2p market ideas |
| 14:52:32 | nsh: | tends towards signer/coalition centralization |
| 14:52:34 | nsh: | doubleplusungood |
| 14:53:26 | nsh: | [even if there exist privacy-enhancing coalitions, you can bet dollars to donuts they will be sparse among the types of coalition that emerge when you incentizive them] |
| 14:58:39 | kanzure: | is there a good reason we don't have a good aggregatable signature scheme yet |
| 14:58:53 | kanzure: | like a million-to-one aggregation? |
| 15:04:47 | kanzure: | "Secure proxy signature schemes for delegation of signing rights" https://eprint.iacr.org/2003/096.pdf |
| 15:09:32 | nsh: | kanzure, scaling behaviour is probably a factor |
| 15:10:18 | maaku: | kanzure: what do you mean by "we have"? there's good proposals |
| 15:10:26 | kanzure: | coinjoin is not sufficient |
| 15:10:30 | maaku: | though the one I like involves the pairing assumption |
| 15:10:39 | kanzure: | not sure which other proposals you are talking about |
| 15:10:51 | maaku: | kanzure: do you know OWAS? one-way aggregate signatures |
| 15:11:19 | maaku: | https://bitcointalk.org/index.php?topic=290971.0 |
| 15:11:21 | kanzure: | i'm aware of the concept, but not of any specific bitcoin proposals |
| 15:11:39 | maaku: | well it'd be a hard-fork change, so it hasn't got much attention |
| 15:11:40 | kanzure: | this seems to be focused on anonymity |
| 15:11:48 | maaku: | (but it's something you could do in a sidechain!) |
| 15:11:58 | kanzure: | i'd be fine with an aggregate signature scheme that has no anonymity |
| 15:12:05 | maaku: | kanzure: for what purpose then? |
| 15:12:28 | kanzure: | abridging intermediate transaction history |
| 15:12:41 | kanzure: | instead of dumping all transactions into a blockchain |
| 15:12:45 | maaku: | kanzure: oh, well lightning |
| 15:12:49 | maaku: | and micropayment hubs |
| 15:12:52 | kanzure: | lightning is only a bi-directional channel |
| 15:13:19 | kanzure: | i want to send 100k payments and have each of my 100k different receivers also send 10k payments, and none of the intermediate transactions should need to be on the blockchain itself |
| 15:13:35 | kanzure: | and also, it would be nice if there could be arbitrarily-deep transaction chains that bridge the history of an even larger transaction chain |
| 15:14:08 | maaku: | kanzure: lightning is much more than a bidirectional channel, which is why it needs so many changes |
| 15:14:29 | maaku: | i'm not sure why you think you can't do that with micropayment channels |
| 15:14:42 | nsh: | * nsh listens attentively |
| 15:14:49 | kanzure: | as you increase the number of people on each side of the channel, you increase the probability that one of them will want to throw the transaction into the blockchain to close the channel |
| 15:15:03 | maaku: | so? it only affects their channel |
| 15:15:10 | maaku: | it doesn't require anything else to hit the chain |
| 15:15:23 | kanzure: | well, the other users have to reopen channels |
| 15:15:24 | kanzure: | so.... |
| 15:15:32 | maaku: | no, channels are direct |
| 15:15:47 | maaku: | if you close your channel with hub A, I don't have to close my channel with hub A |
| 15:16:20 | maaku: | now you move an insane amount of money around in one direction at once, it is true you will saturate one direction of a channel |
| 15:16:32 | kanzure: | closing a channel means putting a transaction on the blockchain.... |
| 15:16:33 | kanzure: | sigh |
| 15:16:51 | maaku: | "well, the other users have to reopen channels" <-- this is incorrect |
| 15:17:01 | kanzure: | i was talking about a single channel |
| 15:17:04 | kanzure: | it's correct. |
| 15:18:20 | maaku: | if you have 100k people receiving payments, and 15 of them decide to close their channel, 15 transactions hit the chain |
| 15:18:32 | maaku: | i'm sorry, I'm just not seing the issue. maybe I'm dense |
| 15:19:24 | nsh: | * nsh doubts there's a way to nontrivially improve on that |
| 15:20:00 | nsh: | sorry, doubts there's a trivial way to improve on that |
| 15:25:31 | kanzure: | so, that's unrelated to a single channel, i think |
| 15:25:52 | maaku: | nsh: me being dense? probably. nootropics? |
| 15:25:55 | kanzure: | the idea was to abridge transaction history, not "hope that they all collectively decide to close their channels after transacting in a way that happens to reduce the total number of transactions" |
| 15:26:17 | nsh: | * nsh is definitely the denser :) |
| 15:26:42 | nsh: | kanzure, abridging without cooperation is... i don't want to say impossible |
| 15:26:49 | maaku: | snarks |
| 15:27:00 | nsh: | yeah, moonmathematical |
| 15:27:03 | maaku: | otherwise... nothing i know |
| 15:27:07 | kanzure: | i'd be okay with cooperation. |
| 15:27:09 | nsh: | that's a nice compromise between possible and impossible :) |
| 15:27:13 | nsh: | well, not closing your channel is cooperation |
| 15:27:30 | maaku: | kanzure: well, an active fee market is also important |
| 15:27:31 | kanzure: | no, snarks cooperation would probably involve stuff like "here, sign my fart" |
| 15:27:57 | kanzure: | instead of just "plz don't close your channel" |
| 15:28:28 | maaku: | kanzure: where I'm being dense is I don't understand the concern. closing a channel is not an externalized cost, due to fees |
| 15:28:39 | maaku: | if you want to close your channel, fine. pay up |
| 15:29:07 | maaku: | well, modulo all of bitcoin being an externalized cost to non-mining full nodes, etc. etc. |
| 15:30:10 | Guest87353: | Guest87353 is now known as mr_burdell |
| 15:30:31 | kanzure: | so you believe that large quantities of transactions- perhaps billions- will have users that choose to use software that tries to find ways to close the channels in a way that minimizes the number of fees and number of transactions that get into the blockchain? |
| 15:31:15 | nsh: | no, i imagine the people paying the users will be strongly incentivized to minimise the overhead for the recipients |
| 15:31:21 | nsh: | and that will tend towards streamlining |
| 15:31:22 | maaku: | kanzure: when transaction fees are $100/tx, yes |
| 15:55:26 | c0rw1n: | c0rw1n is now known as c0rw|away |
| 16:05:01 | andytoshi: | kanzure: OWAS is slow and depends on pairing. it hasn't been implemented 'til now because it'd be a controversial hardfork for bitcoin plus it'd have bad scaling consequences (why there has been no "pairing-crypto alt" idk, nobody here has done it because there are better uses of our time) |
| 16:06:07 | andytoshi: | but given gmax's comments above about how OWAS interacts with CT, and adam's periodic musings on a "BDH-secure sidechain" (meaning one where pairing crypto's security assumptions are considered sufficient), i'm sure something will crop up in this area sooner or later.. |
| 16:08:03 | nsh: | well, i think once alpha proves the sidechains concept is feasible [assuming it does], then there might be a cambrian explosion |
| 16:08:20 | nsh: | to put it in provocative hyperbolic terms, after my idiom |
| 16:17:32 | maaku: | the only reason OWAS wasn't in alpha was because CT was easier to get out the door first |
| 17:16:24 | maaku: | maybe-interesting observation : with onion routing of lightning payments you can have "hidden" payment addresses |
| 17:21:54 | Luke-Jr: | can't you already? just payment protocol over tor |
| 17:23:48 | nsh: | CT can easily allow for hidden payment addresses by using address-ratcheting [OTR-style] through the side-channel. doesn't deal with the first address issue though |
| 17:24:13 | nsh: | (likewise OTR doesn't deal with identity/presence management) |
| 19:15:06 | Tiraspol: | Anyone here who can help me with some java questions? |
| 19:29:20 | fluffypony: | Tiraspol: ##java |
| 21:47:59 | c0rw|away: | c0rw|away is now known as c0rw1n |
| 22:54:08 | c0rw1n: | c0rw1n is now known as c0rw|zZz |