00:08:50BlueMatt:andytoshi: ehhh, I think we should remove the cryptonote paper due to excess of pow wankery
00:09:47andytoshi:BlueMatt: :/ i dunno, probably
00:10:01andytoshi:i guess, it's on wpsoftware for posterity
00:11:24BlueMatt:didnt someone say something about rederiving the ring sig stuff separately?
00:14:16andytoshi:BlueMatt: yeah, i did, i managed to waste all day trying to generalize it to N-of-M..
00:14:25BlueMatt:heh, oops
00:14:52andytoshi: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:56andytoshi:no ETA tho :)
00:15:12BlueMatt:fair enough
00:21:20andytoshi: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:13sipa:gmaxwell: mbcaa(4) = 114
00:23:31sipa:gmaxwell: A00616
00:23:37sipa:gmaxwell: A006126
00:25:40gmaxwell:ah ha!
00:26:03sipa:let me see whether my code finds 6894 for the next step...
00:27:37sipa:so all we need is a precomputed table with 6894 32-bit numbers
00:31:11gmaxwell:to handle up to 5? thats kinda neat.
00:31:39sipa:here's the list for 4:
00:32:32gmaxwell:why does it need to be 32 bit numbers when its only a predicate over 5 bits?
00:33:59sipa:a 32-bit numbers encodes an arbitrary function of B^5 -> B
00:40:32sipa:gmaxwell: http://0bin.net/paste/+GAd6zX2TY7KrHwn#kfE6O0KDJI-jFGwbdx0CFB2VaXGrHw+fBUPAJsW5x02
00:46:56sipa:gmaxwell: actually, LESS!
00:47:02sipa:wait, no
00:50:55gmaxwell: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:53sipa:why do you need and/or?
00:51:57sipa:ah, for more bits
00:55:21sipa:how many max different keys at most?
00:58:29gmaxwell: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:01sipa:a primitive for M-of-N seems useful too
00:59:05sipa:with N>5
01:00:22gmaxwell: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:02gmaxwell: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:05gmaxwell: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:27sipa:what if you do weighted thresholds, but require an exact match?
01:03:35sipa:ah no, still not
01:03:43gmaxwell:yea, so _that_ is how I came up with that example.
01:04:10gmaxwell:because I was trying to see if allowing an exact match increased the computational power enough to cover all the cases.
01:04:33sipa:so: multidimensional thresholds :)
01:04:55gmaxwell: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:46gmaxwell:polynomal weighed threshold with order equal to the bits in is general for boolean functions (not just monotonic ones). but ... expoential size. :(
01:10:26gmaxwell:(alternatively, even a single weighed threshold can construct a NAND gate, so they're also universal if you can cascade them)
01:27:15sipa:gmaxwell: nothing prevents us from having a MBCAA node in MAST :)
01:30:25gmaxwell: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:53sipa: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:15sipa:expect when you have public keys that are used more than once in your predicate
01:32:28gmaxwell:(e.g. could the logic have only And and Or, no not)
01:32:38phantomcircuit:gmaxwell, huh
01:33:00phantomcircuit:cant find any implementation of schnorr signatures that seems sane
01:33:22phantomcircuit:oh hey
01:33:25phantomcircuit:there's one in openssh
01:34:51sipa: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:19sipa:all you need is AND/OR and sigchecks in script :)
01:35:26gmaxwell:yes, exactly.
01:35:40gmaxwell:but the insofar is the key point there. :)
01:35:52sipa:that's a question of use cases, i'm sure
01:36:05sipa:not expressivity
01:36:16gmaxwell:well, say a trustless lottery example.
01:36:51gmaxwell:that still works, it's A&&lottery-preimage-likethis || B&&lottery-preimage-like-that
01:37:34sipa:but this is interesting as an abstraction layer
01:45:49brisque: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:47:36gmaxwell:brisque: he's simply incorrect. The attack success probablity that ignores time is only correct in a latency free universe.
01:48:01gmaxwell:And it's only telling you about security in worlds where attackers can't rent hashpower bursts.
01:48:18gmaxwell:The first is a reasonable assumption when the interblock time is large with respect to the network radius.
01:48:58gmaxwell: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:27brisque:thanks. the whole comment makes some strange assumptions.
01:51:37gmaxwell: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:52:09brisque:I don't think it's worth your time or effort
01:53:20brisque: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:41gmaxwell: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:54gmaxwell: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:55brisque: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:38gmaxwell: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:45gmaxwell: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:46brisque:oh I wasn't saying that he wouldn't! just the viewership of that particular forum wouldn't see it that way
02:01:24maaku:maaku is now known as Guest44632
02:03:16gmaxwell: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:22gmaxwell:... solved by risky fixes. Expirence in bitcoin suggests this view is in fact the optimistic one.
02:04:15andytoshi: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:42gmaxwell:you'd be fine, I think. At least for now.
02:04:55gmaxwell:you'll be the man soon enough, I'm sure. :P
02:05:03andytoshi:yeah, no doubt :P
02:05:15brisque: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:35andytoshi:brisque: understood, my question is purely about PR
02:06:57brisque:PR is hard, especially as there's such wide ranges of view on what is kosher or not.
02:09:30kanzure:you've already lost if your understanding of cryptoanything is limited to pr
02:12:27andytoshi:well, sure, but if bitcoin's appeal is limited to people who aren't lost, it won't be a useful system :)
02:14:09brisque: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:15phantomcircuit:pr is hard... because it's difficult to counter someones message if they're willing to straight up lie
02:14:54brisque:phantomcircuit: cloudhashing is powered by burning bibles.
02:28:10gmaxwell:"well technically..."
02:29:42phantomcircuit:brisque, ironically we're not 100% hydro/geothermal
02:30:21gmaxwell:so, you're powered by the buring souls of the damned?
02:31:37phantomcircuit:gmaxwell, only on taco tuesdays
04:47:42maaku:maaku is now known as Guest36626
06:05:28XPLZ:Hello everyone
06:12:31XPLZ:XPLZ has left #bitcoin-wizards
06:13:58adohgg:adohgg is now known as Adohgg
06:18:48BlueMatt:phantomcircuit: mmmm, tacos
06:23:37BlueMatt:we could do taco tuesday...
08:05:15rajaniemi.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:15rajaniemi.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:15rajaniemi.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:15rajaniemi.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:15rajaniemi.freenode.net:Users on #bitcoin-wizards: harrow @ChanServ phedny petertodd burcin lechuga_ abc56889 Alanius Guest47516 throughnothing CodeShark
08:18:16Dizzle_:Dizzle_ is now known as Dizzle
14:11:10andytoshi: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:48fanquake:fanquake has left #bitcoin-wizards
17:24:47x48_:x48_ is now known as x48
18:05:55gavinandresen_:gavinandresen_ has left #bitcoin-wizards
18:57:53lnovy:lnovy is now known as zz_lnovy
18:59:30zz_lnovy:zz_lnovy is now known as lnovy
20:10:05adam3us1:adam3us1 has left #bitcoin-wizards
20:14:24gmaxwell: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:01gmaxwell:This reduces the number of functions a lot... it eliminates some multiple of (n-1)! functions.
20:16:20sipa:not sure how you use this
20:18:39sipa: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:50sipa:but that doesn't remove a function from the set
20:18:59gmaxwell:yes, but there is also (x or y) && z and its permutations.
20:19:35gmaxwell:and, IIRC, there are 6 of those, you can eliminate 5. Those are the only ones you can eliminate for size 3.
20:19:47gmaxwell:there are a bunch more for size 4 though.
20:19:51sipa:i see!
20:20:18gmaxwell:e.g. maj(3) && x has a bunch of permutations about which input gets the veto.
20:21:25gmaxwell:I'm not sure how many it elimates, but it's some function of input! so probably a lot.
20:25:53sipa:maybe we can get to 6-inputs :)
20:26:12sipa:meanwhile, i'm implementing schnorr in libsecp256k1
20:26:18gmaxwell:thats what I was thinking.
20:27:22sipa:detecting permuted functions sounds very expensive, though
20:28:36sipa:hmm, maybe not
20:29:41gmaxwell:you just ignore the input lables and look at the gates.
20:32:15sipa:i have a 32-bit integer that encodes the function
20:32:38sipa:to strip out the permutations, you could require that only the lowest 32-bit integer version is present
20:33:22sipa: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:28gmaxwell: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:58gmaxwell:(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:51sipa:gmaxwell: so there are only 3 3-input functions?
20:55:11gmaxwell:I think.
20:55:32sipa:then my code is wrong
20:56:19sipa:0x80, 0xe8, 0xfe
20:56:29sipa:the first is a&b&c
20:58:02sipa:the second is a|(b&c)
20:58:43sipa:ah no
21:00:13gmaxwell:hm. darn, actually I think the numbers we were using actually ignored the permutations already.
21:00:19Eliel:a&(b|c) (the reverse of the second one)
21:01:21sipa:0xe8 is (a&b) | (a&c) | (b&c)
21:01:27sipa:aka 2-of-3
21:01:59sipa:0xfe is a|b|c
21:02:24sipa:so a&(b|c) is missing
21:06:13gmaxwell: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:16gmaxwell:er 9
21:06:24gmaxwell:I think none of those are permutations of the others.
21:06:50sipa:(a||b)&&(a||c) is a permutation of (a||b)&&(b||c)
21:07:25gmaxwell:oh duh
21:07:26sipa:just swap a and b
21:07:43Eliel:also (a||c)&&(b||c)
21:08:07gmaxwell:okay good, I wasn't previously crazy then.
21:08:29adam3us:so what about sort variables, and operators, and use all variables exactly once
21:15:18sipa:ok, my code says 5 now
21:15:43sipa:80, A8, E8, EA, FE
21:17:50sipa:aka: a&b&c, (a&b)|(a&c), 2-of-3, a|(b&c), a&b&c
21:18:09sipa:eh, a|b|c is the last one
21:18:24sipa:there's 20 left for 4 inputs
21:18:39sipa:instead of 114
21:22:23gmaxwell:makes me hopefuly for 6. :)
21:22:41sipa:i'm almost done computing them for 5
21:22:49sipa:computing them for 6 will require a different approach
21:22:58gmaxwell:you just testing all boolean functions?
21:23:53gmaxwell: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:55Eliel: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:57sipa:180 for 5
21:26:31gmaxwell:wow. thats a nice reduction too.
21:27:08Eliel:sounds like 32 bits will be able to encode quite a large number of inputs.
21:27:44sipa:so: 1:1,2:2,3:4,4:20,5:180
21:28:11sipa:not in OEIS :(
21:29:10Eliel:I think you can safely assume the number will be bigger than nCr(n-1,n)
21:30:28sipa:oh, no, 1,2,5,20,180
21:30:53sipa:and OEIS says for 6 it is 16143
21:32:30siraj:siraj has left #bitcoin-wizards
21:33:07sipa:now, constructing those for 6...
21:33:42sipa:A006602 for more information
21:34:03Eliel:are you creating the functions for higher levels by combining the functions from lower levels?
21:34:13sipa:i should
22:58:24ahmed_:ahmed_ is now known as ahmed_ZzZz
23:04:07gmaxwell:lol. go go OEIS
23:05:09tromp:i'm trying to extend A094777
23:07:47gmaxwell: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:16gmaxwell:sipa: Do you have a construction in mind that nicely constructs larger monotone circuits out of these objects as nodes? How does that look?