01:14:29	tromp:	talking about excess complexity, Stephen Reed and his TexaiCoin project are not to be outdone. For Self-signed X.509 Certificatestorage he says "I am thinking about following the keyless signature infrastructure (KSI) design suggested by Scumby in which a growable binary merkle hash tree timestamps and stores the certificates along with a Solar Flux Index chaos value".
01:22:43	jchp_:	2
01:37:35	gmaxwell:	The power of chaos!
01:41:10	sipa:	The chaos of power!
01:41:55	jedunnigan:	lol
01:44:28	XxionxX:	XxionxX has left #bitcoin-wizards
01:48:38	jgarzik:	I want an engine powered by pure entropy.
01:50:16	sipa:	reddit seems to be a close approximation?
01:52:11	justanotheruser:	aren't all engines powered by almost pure entropy?
01:57:06	jgarzik:	it's the "almost" that I object to!
01:57:40	justanotheruser:	jgarzik: well I can use the heat from my engine to warm myself
01:58:14	justanotheruser:	so less net entropy is used
01:59:53	justanotheruser:	or created
02:14:19	kanzure:	is there an hsm that could be coerced into doing secp256k1 ecdsa operations?
02:23:46	gmaxwell:	andytoshi: so, can we construct a completely non-interactive (weighed?) schnorr threshold signature (or perhaps only setup interactivity) without overhead? (I was thinking I knew nothing; then realized I know how to construct ones with high overhead)
02:24:04	gmaxwell:	kanzure: sure, ibm cryptocard. Virtually all other HSMs are nearly worthless anyways.
02:24:44	gmaxwell:	(in that they're so limited in the policy they impose that they darn near only serve the purpose of rate limiting things)
02:25:37	gmaxwell:	crypcard is a >$10k pricetag; but you can load it with arbritary software; thus get whatever policy (and cryptosystem) you want.
02:28:12	kanzure:	gmaxwell: thank you
02:28:57	gmaxwell:	(and it can prove to third parties that it's actually running whatever code you're saying it is)
02:31:04	kanzure:	gmaxwell: know of anyone that has bothered to do bitcoin things with ibm cryptocard?
02:31:35	gmaxwell:	Nope. I've got a cryptocard here (a 4764, so one model old) but haven't been able to get the %@$%# devkit.
02:31:55	gmaxwell:	(Hal's RPOW system was on the model before that)
02:32:08	kanzure:	"some devices support secp256k1 but not EC point multiplication which is another nuance (thales' HSM for example)"
02:32:39	gmaxwell:	kanzure: there is no support issue like that. cryptocard is a PPC and you can run arbritary code on it.
02:32:53	gmaxwell:	I have on my todo actually contacting IBM in a business capacity; perhaps I can get more love not as a random OSS hacker.
02:33:14	gmaxwell:	but it's not super high on my todo.
02:33:57	gmaxwell:	(it also contains an FPGA which is used for crypto accel, but only IBM can update it as part of the microcode; as it could be used for remote-attest-escape if you had free control over it)
02:34:30	gmaxwell:	(well, the newer ones do, I think the older ones just had fixed function crypto accel)
02:35:05	kanzure:	i have been looking at the pkcs#11 api and i am not sure if bip32 information can be stuffed into api calls through it
02:35:44	gmaxwell:	I'm sure it can't.
02:35:47	gmaxwell:	er relatively sure.
02:36:18	gmaxwell:	(haven't actually checked: but I wouldn't expect it to accomidate a novel cryptographic technique we invented...)
02:36:43	kanzure:	oh it looked like a protocol, and the other end could be a custom implementation
02:37:03	gmaxwell:	okay sure yea you can probably find some way to pack it in.
02:37:40	kanzure:	what sort of binaries can i dump on cryptocard?
02:41:10	gmaxwell:	any sort you want. It's a PPC host on a card locked into a special execution enviroment. You can write code in C for it (assuming you have the @#$@ devkit), compile with gcc and load up on the card.
02:46:08	andytoshi:	gmaxwell: been thinking about it, not sure, i don't have anything
02:46:17	andytoshi:	are you asking about jaekwon's problem?
02:48:42	andytoshi:	you can do noninteractive n-of-n with interactive setup by using bip32 to generate nonces (from a "nonce pk" NOT anything related to the secret key)
02:50:23	gmaxwell:	yea, I know n-of-n. Thats easy.
02:51:42	gmaxwell:	Basically was talking today about how much need there is for CHECKSCHNORMULTISIGVERIFY ... the normal approach of requiring interaction is really lame for engineering reasons (E.g. requiring bidi sync communications), thus leaving a reason to keep using space inefficient multisignatures.
02:52:26	andytoshi:	why can't you do LSSS with the nonces?
02:52:39	gmaxwell:	But perhaps there is something with constant overhead that removes the interaction and lets you get N of M.
02:54:01	andytoshi:	maybe you can ... feels too simple
02:56:55	gmaxwell:	well for example, here is a hybrid cryptosystem that is kinda wonky but works.
02:57:03	gmaxwell:	(but the overhead is kinda high)
02:57:20	gmaxwell:	you compute all possible N key satisfactions of your N of M, and build a hash tree of them.
02:57:31	gmaxwell:	Now reveal a log sized membership proof and a N of N signature.
02:57:54	maaku:	maaku is now known as Guest81235
02:57:56	gmaxwell:	tada. I have better scaling than a multisignature in the asytomtic case.
02:59:08	andytoshi:	size of membership proof will be 512 bits (hash + neighbor) * log(N)?
02:59:25	andytoshi:	err, log(N choose M)
03:02:10	gmaxwell:	Yes.
03:03:24	gmaxwell:	e.g well M choose N for the normal ordering of the words. :)
03:03:27	gmaxwell:	oh not hash+neighbor.
03:03:33	gmaxwell:	just neghbor, so 256.
03:05:19	gmaxwell:	e.g. I compute 14*256 3584 bytes, plus 14 bits, plus a regular 64 byte signature for 15 of 20.
03:05:41	andytoshi:	i'm thinking just additive schnorr. so, as part of your setup phase you'd establish a bip32 master nonce curvepoint m ... then when signing you'd choose a 256-bit "public nonce" which you'd translate into a curvepoint as m/a/b/c/d/e/f/g/whatever (just splitting the nonce into chunks small enough to be bip32 childkeys)...now you can compute everyone's kG using ckd_priv as well as your own k using
03:05:43	andytoshi:	ckd_pub...then i feel like you can use these values to do some sort of LSSS-like polynomial interpolation to compute a nonce curvepoint κG where κ is a shared secret, as well as your own secret share
03:05:52	andytoshi:	but i am too tired to see how that last step works in my head
03:06:16	gmaxwell:	so 3584+2+64=3650 bytes vs 20*32 + 15*64 = 1600.. hmm!
03:06:45	gmaxwell:	hm. indeed.
03:07:10	gmaxwell:	(turns out that logs of binomals eq are not so nice!)
03:07:53	andytoshi:	the nonce κG doesn't need to be secret, it just has to be the same no matter which N signers compute it ... then κ itself needs to be a sum of secret values
03:08:17	andytoshi:	yeah, binomials are borderline factorial, so log(binomial) could actually be worse than linear :)
03:09:06	kanzure:	gmaxwell: thanks
03:10:55	andytoshi:	i'm using bad terminology, κ is not a shared secret, nobody actually knows it. everywhere i say LSSS i just mean "lagrange interpolation"
03:11:17	gmaxwell:	oh wait. I failed at bytes.
03:12:19	phantomcircuit:	gmaxwell, arithmetic is hard
03:12:21	gmaxwell:	that should have been 448+2+64=512 bytes.
03:12:40	gmaxwell:	(I was boggled there because I thought I'd worked through this a while ago and knew it would work)
03:13:11	andytoshi:	oh lol, i didn't even see that
03:13:34	andytoshi:	it is weird that we talk of hashes in terms of bits
03:13:40	gmaxwell:	so yea, I think that works for some range of numbers, but it's kinda ugly.
03:14:22	andytoshi:	kinda, but not as bad as i first thought. like 20 choose 15 is only 15k, i thought it'd be way higher..
03:15:02	gmaxwell:	well if you start thinking about the weighed schemes you need to get fancier policies it blows up hugely and fast.
03:15:34	andytoshi:	13680 ... i computed that, dunno how my brain approximated it to "15k"
03:15:39	gmaxwell:	OTOH, if your policies involve things other than just EC signatures (E.g. hash preimages) then what I just said is the best that can be done (absent SNARK like things).
03:16:04	andytoshi:	i wonder if we can mkae something that emulates hash preimages with EC signatures
03:16:10	andytoshi:	like schnorr sigs with k == x enforced
03:16:44	tromp:	20 choose 15 is under 3k ?!
03:17:00	andytoshi:	maybe that fails to leak the key when you add it to a bunch of other sigs..
03:18:30	andytoshi:	(i was thinking about this in context of brs sigs, since i finally got aronud to verifying that 2-of-2 multisig works in the obvious way)
03:19:20	OneFixt_:	OneFixt_ is now known as OneFixt
03:32:07	kanzure:	win 2
03:32:09	kanzure:	oops :(
04:59:44	justanotheruser:	justanotheruser is now known as ididntkicku
05:00:58	ididntkicku:	ididntkicku is now known as justanotheruser
05:07:40	gmaxwell:	andytoshi: oh good you did verify that then?
05:09:07	jaekwon:	gmaxwell, andytoshi: have you looked at bilinear pairings? I believe there are very efficient n-of-m threshold algorithms (the sig is only 20 bytes!). In the very least there are very efficient multisignature algorithsm, again where the sig is only 20 bytes. So for an n-of-m threshold sig, you can definitely do (20 + m/8) byte signatures. The worst part would be the computation time, which requires 2 pairing operations which
05:11:33	jaekwon:	Check out Boldyreva's paper, "Efficient threshold signature, multisgnature, and blind signatures based on the Gap Diffie Hellman Group signature scheme"
05:12:13	gmaxwell:	jaekwon: yes we know a lot about them.
05:12:45	gmaxwell:	20 bytes is below what I'd consider acceptable security. You can only get 80 bits of discrete log hardness at best.
05:13:21	gmaxwell:	jaekwon: we have efficient signatures without pairing; the question I'm asking is making them non-interactive.
05:13:43	jaekwon:	i'm pretty sure the paper cites noninteractive algorithms.
05:13:49	gmaxwell:	also, keep in mind a pairing short signature is 100x slower than ecdsa to verify. (and worse compare to schnorr)
05:15:26	gmaxwell:	I believe your above 20+m*20 unless you require IBE for pubkey generation; which is a useless security assuption usually (requires a trusted party to issue keys)
05:17:52	gmaxwell:	jaekwon: in any case, the pairing short signature halves your signature size at a given security level... but introduces a less mature security assumption and makes it much slower. Hardly seems like a win for just plain signatures. (they're way more interesting for many other things)
05:19:19	jaekwon:	Sure.
05:21:17	jaekwon:	Just saying. I think that paper's alg is IBE without a trusted party. Definitely non-interactive. The bee's knees.
05:21:43	jaekwon:	If you trust the bee that is.
05:22:21	gmaxwell:	jaekwon: well, you mean 20
05:22:53	jaekwon:	20?
05:23:04	gmaxwell:	er misfire. unsend last line. Glitch in the matrix.
05:23:18	jaekwon:	I just had a dejavu
05:28:36	maaku:	maaku is now known as Guest89244
07:05:35	maaku:	maaku is now known as Guest50557
08:05:15	holmes.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	holmes.freenode.net:	Users on #bitcoin-wizards: andy-logbot qualiabyte AaronvanW arubi pen damethos cbeams Emcy_ wallet42 Guyver2 Guest50557 p15 Dr-G3 licnep x48 devrandom TheSeven jchp OneFixt coinheavy eslbaer_ ericp4 koshii eristisk fanquake arowser rfreeman_w irc88 _2539 DougieBot5000 kmels Meeh mortale justanotheruser spinza epscy br4n jgarzik Adlai tjopper nuke1989 Fistful_of_coins BlueMatt Sangheili skinnkavaj samson_ dgenr8 Transisto Graftec Starduster go1111111 Logicwax
08:05:15	holmes.freenode.net:	Users on #bitcoin-wizards: NikolaiToryzin tromp__ LarsLarsen nanotube tromp emsid ebfull wizkid057 a5m0 tucenaber artifexd digitalmagus8 HaltingState prepost mappum SDCDev Grishnakh altoz wiretapped iddo starsoccer midnightmagic Adohgg jaekwon Muis berndj-blackout gribble nsh Graet melvster kinlo zenojis hollandais [Derek] Dyaheon CryptOprah_ jbenet promoJo michagogo zlinn_ btc_ copumpkin pigeons BrainOverfl0w lianj_ UukGoblin optimator wumpus Apocalyptic poggy rs0
08:05:16	holmes.freenode.net:	Users on #bitcoin-wizards: jcorgan_ Iriez mr_burdell fluffypony K1773R bbrittain SomeoneWeird forrestv livegnik mkarrer Anduck amiller Nightwolf Keefe Krellan BigBitz [\\\] dansmith_btc Taek42 @ChanServ phedny so petertodd burcin LaptopZZ danneu catcow TD-Linux lechuga_ abc56889 Guest50253 helo smooth otoburb gwillen kanzure ryan-c pi07r nickler_ Alanius Guest47516 throughnothing CodeShark Eliel mmozeiko andytoshi roasbeef harrow DoctorBTC gmaxwell zibbo phantomcircuit
08:05:16	holmes.freenode.net:	Users on #bitcoin-wizards: HM crescendo pajarillo nsh- bobke [d__d] coryfields sipa espes__ Luke-Jr comboy_ sl01 EasyAt waxwing Hunger- asoltys warren
09:35:52	fanquake:	fanquake has left #bitcoin-wizards
09:46:02	davidlatapie:	davidlatapie has left #bitcoin-wizards
10:43:11	davidlatapie:	davidlatapie has left #bitcoin-wizards
11:09:53	andytoshi:	gmaxwell: verified that the additive thing worked, spent a bit of time on their proof ... i think the sigscheme is ok but but their proof is basically "see [24]" and they still managed to fit some typos in there. still haven't gotten a chance to look at [24] which is http://eprint.iacr.org/2006/389
11:10:21	andytoshi:	have had no spare cycles yet this week, should have some this afternoon
11:18:50	maaku:	maaku is now known as Guest49933
11:31:22	andytoshi:	e.g. typos, switches between 0-indexing and 1-indexing, part of the signatures are `c_i = ... sum_i c_i ...`, i think nobody reviewed this before publishing
11:31:57	andytoshi:	or maybe their "crypto guy" came up with it and nobody else was able to review :)
13:03:19	davidlatapie:	davidlatapie has left #bitcoin-wizards
13:36:03	SDCDev:	SDCDev is now known as SCDDev
13:36:52	SCDDev:	SCDDev is now known as SDCDev
13:38:26	maaku:	maaku is now known as Guest78388
14:28:24	x48_:	x48_ is now known as x48
14:41:46	andytoshi:	i think this perfectly sums up the bct understanding of information theory: https://bitcointalk.org/index.php?topic=654037.msg8967191#msg8967191
14:43:05	nsh-:	connection refused
14:43:24	andytoshi:	the quote is "the whole point of a brain wallet is to store nothing on any device"
14:43:41	nsh-:	heh
14:51:43	fluffypony:	nsh-: s/connection/logic
14:51:45	fluffypony:	:-P
15:03:52	maaku:	maaku is now known as Guest10258
16:31:23	maaku:	maaku is now known as Guest96304
17:50:39	kanzure:	"In what follows, we will define a function that derives a number of child keys from a parent key. In order to prevent these from depending solely on the key itself, we extend both private and public keys first with an extra 256 bits of entropy."
17:50:55	kanzure:	what's wrong with the dependence? and if you have low entropy private keys don't you have bigger problems?
17:59:02	Eliel:	no idea what you're reading, but perhaps it could be to make it difficult to prove the child keys are related to the parent key?
18:10:07	sipa:	is that from bip32?
18:10:39	sipa:	the idea was to avoid: know parent key -> know all child keys
18:10:57	sipa:	you need some extra information to be able to recurse
18:13:47	gmaxwell:	otherwise there is basically no advantage over just using a single key.
18:48:28	kanzure:	bip32utils is giving me a different chain code on a child public key (not the same as the parent public key chain code). is this right?
18:53:32	sipa:	yes
19:26:06	gmaxwell:	andytoshi: sipa and I reasoned out some futher improvements on things related to the MT-multischnorr that are pretty fun.
19:29:50	gmaxwell:	without the hashtree we can get a generic M_pubkeys*32 + 64 + small_overheads construction now that is non-interactive... but somewhat more expensive to verify than a single signature (linear in N but small constants).
19:31:08	gmaxwell:	also supports weights too (obvious with the overhead of signaling the weights)
20:01:18	x48_:	x48_ is now known as x48
21:43:05	andytoshi:	nice!
21:43:58	andytoshi:	i must be being daft here.... can anyone check pg 9 of http://download.wpsoftware.net/bitcoin/wizardry/cryptonote-whitepaper.pdf for the signing algo and point me to where the secret key is actually used?
21:44:44	andytoshi:	gmaxwell: ^ ^^
21:45:34	andytoshi:	also i'm curious what the deets are for how you avoid the hashtree..
21:46:20	andytoshi:	oh, re "where the secret key is actually used" in r_i, second-to-last line on the page
21:46:56	tacotime:	andytoshi, can i send you something in private in confidence?
21:47:03	andytoshi:	they rearranged stuff relative to the original paper, imo it's way less clear where things are the way they've written it..
21:47:05	andytoshi:	tacotime: yup
21:47:08	tacotime:	i can't remember if you dumped your pm logs or not
21:47:08	tacotime:	k
21:47:19	andytoshi:	tacotime: all PMs are confident unless both parties agree
21:47:42	andytoshi:	(except, if you are PMing me on #bitcoin because i'm an op. then i sometimes post stuff on #bitcoin-ops. this would never apply to you)
21:53:05	Dizzle__:	Dizzle__ is now known as Dizzle
22:31:58	ucerron:	what do you guys think of maidsafe's DHT?
22:33:34	Aquent_:	Aquent_ is now known as linus
22:34:08	linus:	linus is now known as linusss
22:34:23	linusss:	linusss is now known as linnuss
22:34:28	linnuss:	linnuss is now known as linnus
22:39:16	fluffypony:	ucerron: vs the Tahoe LAFS DHT, for instance?
22:43:43	linnus:	linnus is now known as paavo
22:45:05	paavo:	paavo is now known as llinus
22:55:23	zooko:	fluffypony: YOU MENTIONED MY FAVORITE TOPIC!
22:55:27	zooko:	One of my many favorite topics.
22:55:29	zooko:	* zooko reads IRC log
23:28:19	ucerron:	yeah vs Tahoe LAFS DHT
23:32:21	zooko:	:-)