| 00:08:50 | BlueMatt: | andytoshi: ehhh, I think we should remove the cryptonote paper due to excess of pow wankery |
| 00:09:47 | andytoshi: | BlueMatt: :/ i dunno, probably |
| 00:10:01 | andytoshi: | i guess, it's on wpsoftware for posterity |
| 00:11:24 | BlueMatt: | didnt someone say something about rederiving the ring sig stuff separately? |
| 00:14:16 | andytoshi: | BlueMatt: yeah, i did, i managed to waste all day trying to generalize it to N-of-M.. |
| 00:14:25 | BlueMatt: | heh, oops |
| 00:14:52 | andytoshi: | i will do it tho, their security proofs are crap, you have to check the source material for every other sentence to fill in the gaps |
| 00:14:56 | andytoshi: | no ETA tho :) |
| 00:15:12 | BlueMatt: | fair enough |
| 00:21:20 | andytoshi: | if somebody gives a positive answer to https://crypto.stackexchange.com/questions/19365/nizk-proof-of-knowledge-n-of-m-discrete-logarithms-threshold i expect i'll be able to do it |
| 00:22:13 | sipa: | gmaxwell: mbcaa(4) = 114 |
| 00:23:31 | sipa: | gmaxwell: A00616 |
| 00:23:37 | sipa: | gmaxwell: A006126 |
| 00:25:40 | gmaxwell: | ah ha! |
| 00:26:03 | sipa: | let me see whether my code finds 6894 for the next step... |
| 00:26:42 | sipa: | yup! |
| 00:27:37 | sipa: | so all we need is a precomputed table with 6894 32-bit numbers |
| 00:31:11 | gmaxwell: | to handle up to 5? thats kinda neat. |
| 00:31:39 | sipa: | here's the list for 4: |
| 00:31:41 | sipa: | 0x8000,0x8880,0xa080,0xa800,0xa880,0xa888,0xa8a0,0xaa80,0xaaa8,0xc080,0xc800,0xc880,0xc888,0xc8c0,0xcc80,0xccc8,0xe000,0xe080,0xe0a0,0xe0c0,0xe800,0xe880,0xe888,0xe8a0,0xe8a8,0xe8c0,0xe8c8,0xe8e0,0xea00,0xea80,0xea88,0xeaa0,0xeaa8,0xeaaa,0xeac0,0xeac8,0xeae0,0xeae8,0xec00,0xec80,0xec88,0xeca0,0xeca8,0xecc0,0xecc8,0xeccc,0xece0,0xece8,0xee80,0xeea0,0xeea8,0xeec0,0xeec8,0xeee0,0xeee8,0xeeea,0xeeec,0xf080,0xf0e0,0xf800,0xf880,0xf888,0xf8a0,0xf8a8... |
| 00:31:48 | sipa: | ,0xf8c0,0xf8c8,0xf8e0,0xf8e8,0xf8f0,0xfa80,0xfa88,0xfaa8,0xfac0,0xfac8,0xfae0,0xfae8,0xfaea,0xfaf8,0xfc80,0xfc88,0xfca0,0xfca8,0xfcc8,0xfce0,0xfce8,0xfcec,0xfcf8,0xfe00,0xfe80,0xfe88,0xfea0,0xfea8,0xfeaa,0xfec0,0xfec8,0xfecc,0xfee0,0xfee8,0xfeea,0xfeec,0xfeee,0xfef0,0xfef8,0xfefa,0xfefc,0xff80,0xffa8,0xffc8,0xffe0,0xffe8,0xffea,0xffec,0xfff8,0xfffe |
| 00:32:32 | gmaxwell: | why does it need to be 32 bit numbers when its only a predicate over 5 bits? |
| 00:33:59 | sipa: | a 32-bit numbers encodes an arbitrary function of B^5 -> B |
| 00:40:32 | sipa: | gmaxwell: http://0bin.net/paste/+GAd6zX2TY7KrHwn#kfE6O0KDJI-jFGwbdx0CFB2VaXGrHw+fBUPAJsW5x02 |
| 00:46:56 | sipa: | gmaxwell: actually, LESS! |
| 00:47:02 | sipa: | wait, no |
| 00:50:55 | gmaxwell: | 5 bits is sort of an odd number, I wonder how nice an encoding one can get for boolean circuits constructed from and, or, {3,4,5 fan-in mbcaa} |
| 00:51:53 | sipa: | why do you need and/or? |
| 00:51:57 | sipa: | ah, for more bits |
| 00:55:21 | sipa: | how many max different keys at most? |
| 00:58:29 | gmaxwell: | I dunno. 5 seems limiting. 16 or 32 seems more reasonable.. though at some point "all you get is a threshold for this size" is not crazy. |
| 00:59:01 | sipa: | a primitive for M-of-N seems useful too |
| 00:59:05 | sipa: | with N>5 |
| 00:59:12 | gmaxwell: | right. |
| 01:00:22 | gmaxwell: | a&&b&&c&&d || e&&f&&g&&h seems completely reasonable... even ones with more considering that we think we've got a construction that only takes one additional pubkey per bit... |
| 01:01:02 | gmaxwell: | I'd commented before that a not insane size transaction could have a 1500 of 3000 in it... though obviously I don't expect that to be anything other than a threshold test. |
| 01:03:05 | gmaxwell: | I was happy with 'meh, weighed thresholds' but that &&||&& case can't be done with a weighed threshold and it's super useful. |
| 01:03:27 | sipa: | what if you do weighted thresholds, but require an exact match? |
| 01:03:35 | sipa: | ah no, still not |
| 01:03:43 | gmaxwell: | yea, so _that_ is how I came up with that example. |
| 01:04:10 | gmaxwell: | because I was trying to see if allowing an exact match increased the computational power enough to cover all the cases. |
| 01:04:33 | sipa: | so: multidimensional thresholds :) |
| 01:04:55 | gmaxwell: | one argument for a general tool is that a general tool can always allow you to combine two existing policies. E.g. my policy is A&&B and yours is B&&C and we want a 1 of 2 of us. |
| 01:05:46 | gmaxwell: | polynomal weighed threshold with order equal to the bits in is general for boolean functions (not just monotonic ones). but ... expoential size. :( |
| 01:10:26 | gmaxwell: | (alternatively, even a single weighed threshold can construct a NAND gate, so they're also universal if you can cascade them) |
| 01:27:15 | sipa: | gmaxwell: nothing prevents us from having a MBCAA node in MAST :) |
| 01:30:25 | gmaxwell: | I was trying to think before if ... more than just checksig criteria, if only monotone predictates on cisc-ish opcodes was actually sufficient for the things small ambition Script. Wasn't sure. |
| 01:30:53 | sipa: | and as an unevaluated MAST branch takes 32 bytes, which is less/equal to a public key, for many cases that would probably even be more efficient in terms of encoding |
| 01:31:15 | sipa: | expect when you have public keys that are used more than once in your predicate |
| 01:32:28 | gmaxwell: | (e.g. could the logic have only And and Or, no not) |
| 01:32:38 | phantomcircuit: | gmaxwell, huh |
| 01:33:00 | phantomcircuit: | cant find any implementation of schnorr signatures that seems sane |
| 01:33:22 | phantomcircuit: | oh hey |
| 01:33:25 | phantomcircuit: | there's one in openssh |
| 01:34:51 | sipa: | gmaxwell: insofar as that a script is ultimately a boolean condition over keys that need to sign something (and this can be generalized i guess to knowing the solution to some puzzle), i'd say yes |
| 01:35:19 | sipa: | all you need is AND/OR and sigchecks in script :) |
| 01:35:26 | gmaxwell: | yes, exactly. |
| 01:35:40 | gmaxwell: | but the insofar is the key point there. :) |
| 01:35:52 | sipa: | that's a question of use cases, i'm sure |
| 01:36:05 | sipa: | not expressivity |
| 01:36:16 | gmaxwell: | well, say a trustless lottery example. |
| 01:36:51 | gmaxwell: | that still works, it's A&&lottery-preimage-likethis || B&&lottery-preimage-like-that |
| 01:37:34 | sipa: | but this is interesting as an abstraction layer |
| 01:45:49 | brisque: | this is straying a off topic a little, but I'd love some help understanding with vitalik buterin is saying in this reddit comment. |
| 01:45:59 | brisque: | https://pay.reddit.com/r/Bitcoin/comments/2hmjij/cryptocurrencies/cku7kpm |
| 01:47:36 | gmaxwell: | brisque: he's simply incorrect. The attack success probablity that ignores time is only correct in a latency free universe. |
| 01:48:01 | gmaxwell: | And it's only telling you about security in worlds where attackers can't rent hashpower bursts. |
| 01:48:18 | gmaxwell: | The first is a reasonable assumption when the interblock time is large with respect to the network radius. |
| 01:48:58 | gmaxwell: | The latter is a reasonable assumption when the lost mining income of a fork is large with respect to the sum of attacks you're avoiding. |
| 01:51:27 | brisque: | thanks. the whole comment makes some strange assumptions. |
| 01:51:37 | gmaxwell: | but, this is nothing new to see vitalik agressively announcing misinformation. To his credit, I'm sure if I responded he's revise his statement and post some really complex scheme that takes more time than I have available to respond to. |
| 01:51:45 | gmaxwell: | ::shrugs:: |
| 01:52:09 | brisque: | I don't think it's worth your time or effort |
| 01:53:20 | brisque: | I sort of grok how Ethereum and VB work in this regard. it's not so much well designed cryptographic security, as just being so complex that nobody can analyse it. |
| 01:53:41 | gmaxwell: | well, moreover I'm not in the business of providing consulting to competing cryptosystems; especially when the result assuredly wouldn't be something I'd want my name on (esp since they've historically failed horribly on attribution in any case) |
| 01:54:54 | gmaxwell: | the first several rounds of "holy crap, whats you're saying is busted" wasn't met by fixes, it was just met with obfuscation. Same pattern with the proshares stuff (some of the same people started those systems). |
| 01:56:55 | brisque: | I'm also not sure if your responses would be taken seriously by any other viewer. in this particular situation you are "the man" and VB is fighting against your tyrany. |
| 01:58:38 | gmaxwell: | VB would actually take it seriously. Every time I've responded to him he's been thoughtful and polite. (and then gone on to propose something ill advised) |
| 01:59:45 | gmaxwell: | e.g. there was some place where VB was plugging turing complete, and I pointed out that turing complete is actually not really meaningful in the context of cryptocurrency script; that other models have equal expressivity... and he agreed and said that indeed it was mostly useful for space efficiency. |
| 02:00:46 | brisque: | oh I wasn't saying that he wouldn't! just the viewership of that particular forum wouldn't see it that way |
| 02:01:24 | maaku: | maaku is now known as Guest44632 |
| 02:03:16 | gmaxwell: | it's not an issue of honesty or intelligence. There is a design philosophy difference. In my view cryptocurrencies are cryptosystems, they're works which are on the envelope of what we know how to achieve engineering wise. To be successful you have to scale back your complexity 100x fold, even against already pessimistic real-world software engineering expirence... and even then there will still be serious failures which can only be ... |
| 02:03:22 | gmaxwell: | ... solved by risky fixes. Expirence in bitcoin suggests this view is in fact the optimistic one. |
| 02:04:15 | andytoshi: | brisque: do you know if i am The Man? (not that i'm interested in responding to VB, but it may be useful if my bitcoin defenses are apparently impartial) |
| 02:04:42 | gmaxwell: | you'd be fine, I think. At least for now. |
| 02:04:55 | gmaxwell: | you'll be the man soon enough, I'm sure. :P |
| 02:05:03 | andytoshi: | yeah, no doubt :P |
| 02:05:15 | brisque: | andytoshi: you're not The Man, and gmaxwell is not either. the only times you're put into that frame is when you can be seen to be trying to squash a competing system. not saying either of you have that intention. |
| 02:05:35 | andytoshi: | brisque: understood, my question is purely about PR |
| 02:06:57 | brisque: | PR is hard, especially as there's such wide ranges of view on what is kosher or not. |
| 02:09:30 | kanzure: | you've already lost if your understanding of cryptoanything is limited to pr |
| 02:12:27 | andytoshi: | well, sure, but if bitcoin's appeal is limited to people who aren't lost, it won't be a useful system :) |
| 02:14:09 | brisque: | I think that's quite a narrow view of it all. the entire altcoin ecosystem relies on PR to get their pumps going and their FUD spread. |
| 02:14:15 | phantomcircuit: | pr is hard... because it's difficult to counter someones message if they're willing to straight up lie |
| 02:14:54 | brisque: | phantomcircuit: cloudhashing is powered by burning bibles. |
| 02:28:10 | gmaxwell: | "well technically..." |
| 02:29:42 | phantomcircuit: | brisque, ironically we're not 100% hydro/geothermal |
| 02:29:54 | phantomcircuit: | er |
| 02:29:55 | phantomcircuit: | now* |
| 02:30:21 | gmaxwell: | so, you're powered by the buring souls of the damned? |
| 02:31:37 | phantomcircuit: | gmaxwell, only on taco tuesdays |
| 04:47:42 | maaku: | maaku is now known as Guest36626 |
| 06:05:28 | XPLZ: | Hello everyone |
| 06:12:31 | XPLZ: | XPLZ has left #bitcoin-wizards |
| 06:13:58 | adohgg: | adohgg is now known as Adohgg |
| 06:18:48 | BlueMatt: | phantomcircuit: mmmm, tacos |
| 06:21:37 | sipa: | tacos! |
| 06:23:37 | BlueMatt: | we could do taco tuesday... |
| 08:05:15 | rajaniemi.freenode.net: | topic is: This channel is not about short-term Bitcoin development | http://bitcoin.ninja/ | This channel is logged. | For logs and more information, visit http://bitcoin.ninja |
| 08:05:15 | rajaniemi.freenode.net: | Users on #bitcoin-wizards: andy-logbot Dizzle_ go1111111 chris2000 michagogo x48_ pen hollandais Guest36626 copumpkin jtimon atgreen TheSeven arubi ericp4 _2539 tromp__ coinheavy brisque postpre koshii SDCDev jgarzik altoz Kuba1234 zenojis Dr-G2 shesek mappum jchp hashtag justanotheruser warren DougieBot5000 Happzz jrayhawk jbenet LaptopZZ cfields optimator_ pi07r Meeh drawingthesun Hunger-- Eliel poggy_ Luke-Jr Emcy_ Guest94465 devrandom Adlai kanzure danneu catcow |
| 08:05:15 | rajaniemi.freenode.net: | Users on #bitcoin-wizards: TD-Linux Guest50253 helo smooth otoburb gwillen ryan-c nickler_ mmozeiko roasbeef pajarillo sl01 Keefe Dyaheon Grishnakh HaltingState rs0_ Gnosis nuke1989 MoALTz todaystomorrow eristisk c0rw1n ahmed_ wiretapped roconnor_ Muis artifexd spinza Logicwax puszl nanotube espes__ andytoshi samson_ gavinandresen mortale mkarrer rfreeman_w so zibbo emsid irc88_ lnovy dansmith_btc epscy tacotime comboy Graftec grandmaster2 LarsLarsen arowser OneFixt |
| 08:05:15 | rajaniemi.freenode.net: | Users on #bitcoin-wizards: Fistful_of_coins BlueMatt Sangheili dgenr8 NikolaiToryzin tromp wizkid057 a5m0 digitalmagus8 iddo starsoccer midnightmagic Adohgg jaekwon berndj gribble Graet kinlo [Derek] pigeons BrainOverfl0w lianj_ wumpus Apocalyptic jcorgan_ Iriez mr_burdell fluffypony K1773R bbrittain SomeoneWeird forrestv livegnik Anduck amiller Nightwolf Krellan BigBitz [\\\] Taek42 asoltys EasyAt sipa [d__d] bobke nsh- crescendo HM phantomcircuit gmaxwell DoctorBTC |
| 08:05:15 | rajaniemi.freenode.net: | Users on #bitcoin-wizards: harrow @ChanServ phedny petertodd burcin lechuga_ abc56889 Alanius Guest47516 throughnothing CodeShark |
| 08:18:16 | Dizzle_: | Dizzle_ is now known as Dizzle |
| 14:11:10 | andytoshi: | i asked a q on crypto.SE recently and was pointed at http://www.win.tue.nl/~berry/papers/crypto94.pdf ... very good fundamental paper |
| 16:15:48 | fanquake: | fanquake has left #bitcoin-wizards |
| 17:24:47 | x48_: | x48_ is now known as x48 |
| 18:05:55 | gavinandresen_: | gavinandresen_ has left #bitcoin-wizards |
| 18:57:53 | lnovy: | lnovy is now known as zz_lnovy |
| 18:59:30 | zz_lnovy: | zz_lnovy is now known as lnovy |
| 20:10:05 | adam3us1: | adam3us1 has left #bitcoin-wizards |
| 20:14:24 | gmaxwell: | sipa: so I realized that for signatures we actually need only an even smaller class of fuctions than monotone_but_cares_about_all: monotone_but_cares_about_all_upto_permutation ... the user can freely permute the inputs. |
| 20:15:01 | gmaxwell: | This reduces the number of functions a lot... it eliminates some multiple of (n-1)! functions. |
| 20:16:20 | sipa: | not sure how you use this |
| 20:18:39 | sipa: | within the set of 3-input functions, there is exactly one "2 of 3" function, and yes, it does not care about the order of its arguments |
| 20:18:50 | sipa: | but that doesn't remove a function from the set |
| 20:18:59 | gmaxwell: | yes, but there is also (x or y) && z and its permutations. |
| 20:19:35 | gmaxwell: | and, IIRC, there are 6 of those, you can eliminate 5. Those are the only ones you can eliminate for size 3. |
| 20:19:47 | gmaxwell: | there are a bunch more for size 4 though. |
| 20:19:51 | sipa: | i see! |
| 20:20:18 | gmaxwell: | e.g. maj(3) && x has a bunch of permutations about which input gets the veto. |
| 20:21:25 | gmaxwell: | I'm not sure how many it elimates, but it's some function of input! so probably a lot. |
| 20:25:53 | sipa: | maybe we can get to 6-inputs :) |
| 20:26:12 | sipa: | meanwhile, i'm implementing schnorr in libsecp256k1 |
| 20:26:18 | gmaxwell: | thats what I was thinking. |
| 20:27:22 | sipa: | detecting permuted functions sounds very expensive, though |
| 20:28:36 | sipa: | hmm, maybe not |
| 20:29:41 | gmaxwell: | you just ignore the input lables and look at the gates. |
| 20:32:15 | sipa: | i have a 32-bit integer that encodes the function |
| 20:32:38 | sipa: | to strip out the permutations, you could require that only the lowest 32-bit integer version is present |
| 20:33:22 | sipa: | so you can start from the function number, compute what number corresponds to all permutations of it, and if the result is lower, skip |
| 20:35:28 | gmaxwell: | I was also trying to think of if there was any other classes of function like Threshold that are inefficient to implement with smaller circuits and have simple non-redundant encodings like threshold does. (this is what caused me to notice the permutation redundancy, since e.g. an OR of two thresholds of size 1/2 needs to encode a permutation, which is a pain to encode optimally) |
| 20:35:58 | gmaxwell: | (that particular one is not a great example in any case, since you can .. implement it as a or of two thresholds, so it's reasonably efficient) |
| 20:53:51 | sipa: | gmaxwell: so there are only 3 3-input functions? |
| 20:55:07 | gmaxwell: | 4. |
| 20:55:11 | gmaxwell: | I think. |
| 20:55:32 | sipa: | then my code is wrong |
| 20:56:19 | sipa: | 0x80, 0xe8, 0xfe |
| 20:56:29 | sipa: | the first is a&b&c |
| 20:58:02 | sipa: | the second is a|(b&c) |
| 20:58:43 | sipa: | ah no |
| 21:00:13 | gmaxwell: | hm. darn, actually I think the numbers we were using actually ignored the permutations already. |
| 21:00:19 | Eliel: | a&(b|c) (the reverse of the second one) |
| 21:00:58 | sipa: | no |
| 21:01:21 | sipa: | 0xe8 is (a&b) | (a&c) | (b&c) |
| 21:01:27 | sipa: | aka 2-of-3 |
| 21:01:59 | sipa: | 0xfe is a|b|c |
| 21:02:24 | sipa: | so a&(b|c) is missing |
| 21:02:40 | adam3us: | a&b&c,(a&b)|c,a&(b|c),a|b|c? |
| 21:05:24 | adam3us: | (a&b)|(a&c)=a&(b|c) |
| 21:06:13 | gmaxwell: | lets see, actually 5: a||b||c, a&&b&&c, majority, (a||b)&&(a||c), (a||b)&&(b||c), (a||c)&&(b||c), (a&&c)||(b&&c), (a&&b)||(b&&c), (a&&b)||(a&&c) |
| 21:06:16 | gmaxwell: | er 9 |
| 21:06:24 | gmaxwell: | I think none of those are permutations of the others. |
| 21:06:50 | sipa: | (a||b)&&(a||c) is a permutation of (a||b)&&(b||c) |
| 21:07:25 | gmaxwell: | oh duh |
| 21:07:26 | sipa: | just swap a and b |
| 21:07:43 | Eliel: | also (a||c)&&(b||c) |
| 21:08:07 | gmaxwell: | okay good, I wasn't previously crazy then. |
| 21:08:29 | adam3us: | so what about sort variables, and operators, and use all variables exactly once |
| 21:10:49 | adam3us: | (a|b)&(a|c)=a|(b&c) |
| 21:15:18 | sipa: | ok, my code says 5 now |
| 21:15:43 | sipa: | 80, A8, E8, EA, FE |
| 21:17:50 | sipa: | aka: a&b&c, (a&b)|(a&c), 2-of-3, a|(b&c), a&b&c |
| 21:18:09 | sipa: | eh, a|b|c is the last one |
| 21:18:24 | sipa: | there's 20 left for 4 inputs |
| 21:18:39 | sipa: | instead of 114 |
| 21:22:23 | gmaxwell: | makes me hopefuly for 6. :) |
| 21:22:41 | sipa: | i'm almost done computing them for 5 |
| 21:22:49 | sipa: | computing them for 6 will require a different approach |
| 21:22:58 | gmaxwell: | you just testing all boolean functions? |
| 21:23:06 | sipa: | yup |
| 21:23:53 | gmaxwell: | yea, so there is probably some recursive construction which terminates early, e.g. where all subtrees are non-monotonic or are just permutations. |
| 21:25:55 | Eliel: | I wonder if you can express most boolean functions as a permutation of the operators || and &&. n-of-m seems to be an exception though. |
| 21:25:57 | sipa: | 180 for 5 |
| 21:26:31 | gmaxwell: | wow. thats a nice reduction too. |
| 21:27:08 | Eliel: | sounds like 32 bits will be able to encode quite a large number of inputs. |
| 21:27:44 | sipa: | so: 1:1,2:2,3:4,4:20,5:180 |
| 21:28:11 | sipa: | not in OEIS :( |
| 21:29:10 | Eliel: | I think you can safely assume the number will be bigger than nCr(n-1,n) |
| 21:30:28 | sipa: | oh, no, 1,2,5,20,180 |
| 21:30:53 | sipa: | and OEIS says for 6 it is 16143 |
| 21:32:30 | siraj: | siraj has left #bitcoin-wizards |
| 21:33:07 | sipa: | now, constructing those for 6... |
| 21:33:42 | sipa: | A006602 for more information |
| 21:34:03 | Eliel: | are you creating the functions for higher levels by combining the functions from lower levels? |
| 21:34:07 | sipa: | nope |
| 21:34:13 | sipa: | i should |
| 22:58:24 | ahmed_: | ahmed_ is now known as ahmed_ZzZz |
| 23:04:07 | gmaxwell: | lol. go go OEIS |
| 23:05:09 | tromp: | i'm trying to extend A094777 |
| 23:07:47 | gmaxwell: | just fitting the change in size, it's unlikely 7 would fit in 16 bits. Sort of nice that the sum of 1..6 fits nicely in 14 bits though. |
| 23:24:16 | gmaxwell: | sipa: Do you have a construction in mind that nicely constructs larger monotone circuits out of these objects as nodes? How does that look? |