--- Log opened Mon Mar 04 00:00:39 2013
00:13 <@gmaxwell> Why do people keep saying that!
00:15 < midnightmagic> I wasn't expecting it to, because you referred to it as just plain "wizards" which suggested it was off-irc.
00:16 < midnightmagic> i took a random stab and voila
00:19 <@gmaxwell> Well, it was mentioned in full in bitcoin-dev... this is where I've shunted the cryptocurrency rocket science discussion which isn't directly related to current bitcoin. (I'm concerned that excessive OT and rocket-science talk in #bitcoin-dev disenfranchises bitcoin users from keeping track of whats being done to their currency)
00:21 < nanotube> i think this channel is a good idea. :)
00:21 <@gmaxwell> there has been some pretty awesome rocket science talk in here too.
00:24 < nanotube> hehe
00:27 < midnightmagic> I recall you mentioned something about shunting it elsewhere. :)
00:27 < midnightmagic> i think it's a good idea fwiw
00:48 <@gmaxwell> It occured to me that for the sum-hash-tree stuff that we're not constrained to any particular binary tree geometry, so we should prefer ones that result in each split having half the coins on each side. This minimizes the amount of balance information leaked.
00:49 <@gmaxwell> But we also don't want any branches becoming too long, since that would make the proofs fat.
00:49 <@gmaxwell> I think this can be used to build a sutiable tree: http://en.wikipedia.org/wiki/Package-merge_algorithm
00:51 <@gmaxwell> The 'alphabet' is the accounts, the probablity of the 'symbols' is balance/total. The length limit would be set to some small multiple of log2(n). The resulting huffman codewords are just the branching decisions in the binary tree.
00:52 <@gmaxwell> amusingly, I saw a nice package-merge implementation a few days ago and thought "what else could I use this for?"
01:23 <@gmaxwell> Another fun thing is that the banks own balance can be split up any number of ways, since the bank doesn't have to worry about producing compact proofs for it... so it could be divided up to fill in any unmatched branches.
01:25 < petertodd> Although by that point, you almost might as well say the banks balance is just whatever is in error in the sum tree.
01:28 <@gmaxwell> ::nods:: sure, just trying to maximally conceal the balance distribution. So grafting on (parts of) the bank balance anywhere in the tree that helps is useful.
01:31 < petertodd> One interesting model, would be if multiple entities held their own private keys, with the bank quickly querying them to do the actual signing, in which case the banks balance is just a set of accounts that happen to have keys associated with them, unlike normal accounts.
01:31 < petertodd> Such entities would have to be on-line to do a trade, but they could provide liquidity basically.
01:31 < petertodd> Might be too complex to explain, but it's interesting.
01:33 <@gmaxwell> (likewise, large accounts— which already tend to have short proofs— could have their balances split in two, assuming the clients were setup to accept fragmented balance statements)
01:36 <@gmaxwell> (at the limit, you divide every account down to the base units, ... but then the proofs are rather enormous, but you leak nothing under all conditions)
01:39 < petertodd> Yeah, basically the accounts become chaum token amounts...
01:39 < petertodd> Probably simple enough to just have client support for more than one account basically.
01:40 < petertodd> The server doesn't need to know accounts are being split up.
09:35 < HM> ok i've sussed out ECDSA and vaguely key recovery in my head now
09:35 < HM> I'm really enjoying this EC stuff
09:44 < HM> If i'm understanding correctly taking r = (x of kG) mod n means there are 2 possible values of kG for some values of r
09:45 < HM> Still trying to understand how the order of the curves and cofactors and such all tie together
09:45 < HM> but i think this is because the cofactor is 1 for k1
10:06 < HM> sipa's code seems to make sense to me
10:07 <@sipa> wow, you can read that? :p
10:07 < HM> lol
10:07 < HM> despite OpenSSLs api's yes
10:07 <@sipa> i think my implementation of hal's optimization is better openssl-interacting code :)
10:09 < HM> x of (kG) mod N has 2 suitable values on the bitcoin curve. one < n and one > n. so your code uses i to select either r or r+n
10:09 < HM> then computes kG using the curve
10:09 < HM> right?
10:09 < HM> uses 'i'
10:09 < HM>  if (!BN_copy(x, order)) { ret=-1; goto err; }
10:09 < HM>     if (!BN_mul_word(x, i)) { ret=-1; goto err; }
10:09 < HM>     if (!BN_add(x, x, ecsig->r)) { ret=-1; goto err; }
10:10 < HM> very simple
10:10 <@sipa> indeed
10:11 < HM> is it just 2 possible values?
10:11 < HM> p/n is the cofactor isn't it?
10:11 < HM> which is 1
10:11 <@sipa> yes, n is 2^256 - 2^128 approximately
10:12 <@sipa> so the chance of it being >n is even exceedingly small
10:14 < HM> very cool
10:14 < TD> HM: the same code exists in bitcoinj in a more readable form
10:14  * HM covers sipas ears
10:14 < HM> more readable than sipa's code you say? :P
10:14 <@sipa> HM: i make no claim my implementation of key recovery is good
10:15 <@sipa> it's a straightforward implementation of the algorithm in SEC1, but it could be much more readable
10:15 < TD> well, you can't really make openssl based code readable
10:15 < TD> https://code.google.com/p/bitcoinj/source/browse/core/src/main/java/com/google/bitcoin/core/ECKey.java#464
10:16 <@sipa> some parts can be abstracted into functions, variables can be more readable, ...
10:16 <@sipa> also, i'm not actually convinced i use the BN_CTX api correctly - it may leak
10:17 <@sipa> (something i learnt when reimplementing Hal's optimization)
10:18 < HM> TD: i prefer ther C++ :P
10:18 <@sipa> HM: feel free to compare with the OpenSSL-using code in https://github.com/bitcoin/bitcoin/pull/2061/files
10:18 < TD> each to their own :)
10:20 < HM> yeah that code is nice
10:21 < HM> I think that FLV optimisation, or whatever it is called, it well outside my grasp atm though
10:21 <@sipa> the reason why it works, i don't understand either
10:22 <@sipa> but given the mathematical property, i understand why this is correct and gives a speedup
10:23 <@sipa> HM: also, originally it was this code by Hal: https://bitcointalk.org/index.php?topic=3238.msg45795#msg45795
10:26 < HM> hmm
10:27 < HM> is it going to merge sipa?
10:27 < HM> or are you waiting for a cryptoangel to come down and bless it?
10:32 < HM> i think the bad bit is you're duplicating code from OpenSSL
10:36 < HM> offtopic but hilarious:
10:36 < HM> http://blog.evernote.com/tech/2011/05/17/architectural-digest/#comment-455
10:36 < HM> "Before Evernote, I spent five years building high-end cryptographic systems for government customers"
11:23 <@sipa> HM: i'd hope to get that into 0.8.1, but i doubt gavin likes to merge it without some big-ass crypto guy signing off on it
11:23 <@sipa> maybe rightfully so
11:25 < gavinandresen> I'd be ok merging it as an off-by-default "if sipa-turbo-transaction" option that people who are CPU limited wanted to use, could use....
11:26 < HM> lol "sue sipa mode"
11:26 <@sipa> hmm
11:27 <@sipa> i'm currently actually trying to write an ECDSA implementation from scratch, with all operations specialized for secp256k1
11:27 <@sipa> trying to see if i can beat OpenSSl :p
11:29 < HM> including your own bignum ops? :p
11:31 <@sipa> yes, i already have a specialized implementation for arithmetic modulo the secp256k1 field size
11:31 <@sipa> which has a function that does an integrated multiply-and-modulo or square-and-modulo
11:32 <@sipa> i haven't compared it with OpenSSL's montgomery multiplication (which is in assembly!) but it beats (naive) GMP by a factor of >4
11:32 < HM> nice
11:33 < HM> Bernsteins implementation of curve25519 was written in his own assembly language and translated to x86 using his own translator :|
11:33 < HM> I'm not sure if he wrote his reference of Ed in the same language
11:33 < HM> haven't looked at it
11:34 <@sipa> well i use a trick i read in the ed25519 paper, namely using 5 uint64_t's (with 52 bits in each) instead of 4
11:34 <@sipa> so you need somewhat more multiplications, but you can add several together before doing a carry
11:35 <@sipa> it needs 47ns for a field multiplication on my 3.1GHz i7
11:35 <@sipa> and doesn't have any assembly code
11:35 < HM> 52 x 5 is 260
11:36 <@sipa> the last one only has 48 bits :)
11:36 < HM> so the top 4 are 0
11:36 < HM> keeps code simple i guess
11:36 < HM> that doesn't sound particularly tricky
11:37 <@sipa> well the trick s verifying that for any allowed input you never overflow any internal variable
11:37 < HM> why is avoiding the carry ideal?
11:37 <@sipa> because 64-bit addition with carry is slow
11:37 <@sipa> (and hard to do in C...)
11:38 < HM> i guess
11:38 < HM> i wrote a divideby58 function that uses 24 bits in uint32_t words
11:38 < HM> the top byte just becomes the carry
11:38 <@sipa> and it allows you to do field additions, subtractions and multiplications with small constants without any carry
11:38 < HM> since 58 takes 6 bits
11:39 < HM> but i was just bored
11:39 <@sipa> just add/sub/mult the respective uint64_t's together
11:39 <@sipa> if you can prove they won't overflow
11:39 < HM> yeah
11:40 < HM> http://pastebin.com/rRcrYUm8
11:41 <@sipa> anyway, the result is a field doubling in 361ns
11:41 <@sipa> eh point doubling
11:41 <@sipa> i haven't implemented addition yet, or compared with openssl
11:41 < HM> sounds fast
11:42 <@sipa> i suspect it's at most a factor 2-3 faster than openssl, but may be a lot less
11:45 < HM> you should look at compiler intrinsics for 128bit operations if you want to push it further
11:45 <@sipa> i use those
11:45 <@sipa> you can't do 64*64 multiplication otherwise
11:47 < HM> sure you can
11:47 < HM> won't be fast though
11:48 <@sipa> well there is no way to do a native 64*64 multiplication in one instruction that keeps the upper ,64bit of the output otherwise
11:48 <@sipa> better?
11:49 < HM> I am satisfied :)
12:57 <@sipa> gavinandresen: -turbo added :)
13:05 < gavinandresen> cool, I look forward to the TurboUltraPlus version
18:04 <@sipa> \o/ 725ns for a point addition
18:42 < HM> that seems pretty slow
18:42 < HM> you can do better
18:43 < HM> sipa: you should really normalise that in cycles.
18:44 < HM> or cycles per byte
18:44 < HM> hmm
18:49 <@sipa> well, to give any meaningful number: a rough guess is 3x faster than OpenSSL
18:50 < HM> good work
18:51 < HM> I would find the code interesting as well
18:51 <@sipa> though i'm pretty far from a full implementation, it's just the field & group operations for now
18:52  * HM nods
19:08 < ielo> hi
19:19 < HM> hi ielo
19:19 < HM> the address format is really weird in bitcoin
19:20 < ielo> why
19:20 < HM> well the hash is converted in to base58 in big endian
19:20 < HM> so the first byte is the most significant
19:20 < HM> then it's reversed
19:20 < HM> so it's now little endian
19:20 < HM> then the front is padded, if applicable, with 1's
19:21 < HM> which means you're semantically adding 0's to the least significant end
19:21 < HM> makes no sense
19:22 < ielo> but all of those parts are useful like the key hash and checksum no?
19:23 < HM> right, it's a composite structure, so it really has no endianness
19:25 < HM> https://github.com/bitcoin/bitcoin/blob/master/src/test/data/base58_encode_decode.json
19:26 < HM> a naive conversion of say 00eb... will treat it as a big endian bigint and output L9ED...
19:27 < ielo> but in what situation would that happen
19:28 < HM> the mainline client does it
19:29 < HM> https://github.com/bitcoin/bitcoin/blob/master/src/base58.h#L64
19:31 < HM> e.g. if you had "10000" and divided it by "10" the BN_div and append op actually produces "1000"
19:31 < ielo> /
19:31 < ielo> / Why base-58 instead of standard base-64 encoding?
19:31 < ielo> / - Don't want 0OIl characters that look the same in some fonts and
19:31 < ielo> /      could be used to create visually identical looking account numbers.
19:31 < ielo> haha
19:31 < ielo> thats curious
19:32 <@sipa> HM: https://github.com/sipa/secp256k1/blob/master/secp256k1.cpp
19:33 < HM> hmm
19:33 < HM> there are some microops you can still do there i think
19:34 < HM> micro optimisations
19:34 <@sipa> i have no doubt about that
19:34 <@sipa> but much is compiler-dependent at that point
19:34 <@gmaxwell> next that gets converted into ASM. :P
19:35 <@sipa> well, that's what i mean: if you want to optimize further, you're probably better off generating the assembly, and tweaking that
19:35 < HM> i doubt it
19:36 <@sipa> for example i do keep a 128-bit accumulator throughout the first multiplication stage in SetMult
19:36 < HM> you should benchmark it in more than 1 compiler though
19:36 < HM> perhaps intels
19:36 <@sipa> in an earlier version, i took the resulting shifted output into a uint64_t, and added to that to obtain the next __int128
19:37 <@sipa> in theory, that is faster, as i know the top 64 bits are zero
19:37 <@sipa> however the generated code was slower
19:37 <@sipa> so there is certainly room for improvement at the assembly stage
19:38 < HM> 100 million
19:38 < HM> how long does it take roughly
19:38 <@gmaxwell> well, not like the compiler is going to output PCLMULQDQ on its own.
19:39 <@sipa> HM: 2.5 minutes here
19:39 <@sipa> it's actually 200 million additions
19:39 <@sipa> but i wanted to avoid always adding the same number
19:39 < HM> I'm going to try something
19:40 <@sipa> feel free :D
19:41 < HM> i only have an i5 480M in this laptop so might take a while
19:41 <@sipa> gmaxwell: it does output mul and adc instructions, which is what i need
19:42 <@sipa> (64-bit multiply with 128 output, and addition with carry of two 64 bit values)
19:42 <@sipa> i think it however generates a few add instructions too many
19:42 < HM> i wonder how much overhead is due to the lack of inlining in the openssl version
19:43 < HM> plus those CTX structs
19:45 <@sipa> those CTX's are actually very efficient
19:46 <@sipa> they cause algorithm to reuse the same variables throughout many iterations
19:46 <@gmaxwell> thats the sort of thing that the cpu will handle well too usually.
19:47 <@sipa> gmaxwell: well you don't want malloc()/free() inside your tight crypto loops
19:56 < HM> hmm
19:56 < HM> well
19:58 < HM> takes over a microsecond here
19:58 < HM> 3m30
19:59 < HM> 2.2 Ghz core
19:59 < HM> 2.67 actually :|
20:00 < HM> sipa: do you have the equivalent OpenSSL benchmark?
20:00 <@sipa> no
20:01 <@sipa> feel free to write one
20:01 <@sipa> but there are optimizations possible "higher up" that openssl doesn't do, too
20:09 <@sipa> so i'd rather continue, and make a full verifier on top of this, and then compare to OpenSSL
21:10 < HM> incidentally
21:11 < HM> i'm in need of an algorithm where a trusted third party can use to establish a shared secret between 2 parties using only their public keys and participation from *one*
21:12 < HM> e.g. Alice <-- Ted ---> Bob
21:13 < HM> Ted wants to establish a shared secret between Bob and Alice with Bobs help
21:13 < HM> but he needs to ensure Alice will be able to get it
21:13 < HM> without holding private keys for either
21:14 < HM> Ted also doesn't fully trust Bob :)
21:15 < HM> So far the best i've come up with is blinding a dozen tokens, getting Bob to compute a multiplication for each of them
21:15 <@gmaxwell> HM: what purpose does Ted serve at all?
21:15 < HM> then unblinding 11 of them and verifying them
21:15 < HM> that was there's only a 1/12 chance Bob has been dishonest and he will be caught in all likelihood
21:15 <@gmaxwell> if everyone has everyone's public keys. Bob and alice can combine them to get a shared secret... (e.g. ECDH) and no need for Ted to do anything.
21:16 < HM> yep
21:16 < HM> but Bob and Alice cannot communicate in realtime
21:16 <@gmaxwell> so? they have public keys— they have a shared secret with no more communication.
21:16 <@gmaxwell> ECDH doesn't require interaction beyond exchanging the public keys, if you don't care for the key to be ephemeral.
21:17 < HM> not really
21:17 < HM> look at it this way
21:17 < HM> Bob knows Alices public key
21:17 < HM> but he doesn't have to use it
21:17 < HM> if a package is encrypted and stored for later with some shared secret, there's no way for Alice to know until later whether he can access it
21:18 <@gmaxwell> Great, then bob knows the AliceBob shared secret.  And if Alice knows Bob's public key, then alice also knows the AliceBob shared secret.
21:19 < HM> Alice can't establish the shared secret in realtime, and decrypt the package and say "yup, that's cool"
21:19 < HM> she has to rely on Ted to make sure Bob is playing ball
21:20 <@gmaxwell> Please step back and describe what you're trying to do. What do people have, what do they know, what state are they trying to get in?
21:21 <@gmaxwell> It sounds to me like you are saying everyone knows everyone's public keys. Alice wants to send an encrypted file to bob. Bob is offline.  Later alice will be offline and bob will be online.
21:21 < HM> basically Ted is locking something up, that is witheld from both Alice and Bob, until sometime in the future.
21:23 < HM> it's encrypted and you need 2 keys to access it
21:23 < HM> either (Alices or Bobs) AND another key
21:25 < HM> the other key is made public in future if Bob needs access, but it's used with other pairings.
21:25 < HM> e.g. (Alice or Sarah) and the other key
21:26 < HM> Ted has to set this up without having Alices private key
21:26 < HM> or Sarahs and Bobs
21:26 < HM> or the private key for the other key
21:27 < HM> so far the best i have will only protect Alices access for some probability
21:27 < HM> i'm not sure it's possible
21:27 < HM> without Ted establishing an ephemeral key
21:28 < HM> I guess an easier way of thinking about it
21:29 < HM> Sarah and Bob are part of a group that need access to Teds documents if provided with a group key
21:29 < HM> Alice has access any time
21:30 < HM> it's not just a  group key though because the documents are individual, but they do need the group key
21:30 <@gmaxwell> You've overcomplicating it. Ted can just encrypt the document and then encrypt the document key for any party or group that he wants to have access. Done.
21:31 < HM> yep
21:31 < HM> but then the encrypted document key needs to be shared
21:32 < HM> the objective is to accomplish this without Sarah and Bob having to remember any additional data
21:32 < HM> or having that kept with Ted
21:33 <@gmaxwell> HM: it would be included with the document, of course.
21:34 < HM> what i invisioned was this
21:35 < HM> what syntax do you use for public EC keys?
21:35 < HM> G^x good for you?
21:37 < HM> i'll use *G
21:37 < HM> (g   +  H(b*a*G))*G =  g*G + H(b*a*G)*G
21:38 < HM> g = group key, a = alice, b = bob
21:38 < HM> H = some hash function
21:38 < HM> given a*G (Alice's public key), bob can calculate H(b*a*G), as can Alice
21:39 < HM> because that's basically D-H
21:39 < HM> if 'g' is later made public then Bob can also then get the final private key: g + H(b*a*G)
21:40 < HM> Ted can construct this whole thing because he only needs a*G and b*a*G from Bob and Bob trusts him
21:40 < HM> that is, Ted can calculate the right hand side
21:40 < HM> the problem is Ted can't just expect Bob to calculate b*a*G
21:40 < HM> 'b' is unknown so he could just as easily reply with anything
21:40 < HM> and screw Alice
21:44 < HM> My best idea atm is to have Ted blind a*G and actually keep that secret. send Bob a dozen blinded x[]*Gs and have him compute b*x[0..i]Gs
21:44 < HM> Ted can then verify that Bob has calculated at least a dozen correctly because he already has b*G which is used earlier for authentication
21:45 < HM> so Ted can be pretty sure that the b*a*G he has is really a multiple of a*G
21:47 < HM> a*G doesn't actually have to be secret, that was poor phrasing
21:47 < HM> i meant the location amongst the blinded points
21:48 <@gmaxwell> this just seems stupid to me, sorry. I can't fathom why you want this. Fragile, complicated, computationally expensive... and I'm trying to speculate _something_ this gets you over doing the obvious, simple, and secure thing and I'm coming up empty.
21:49 < HM> Bob only has to know his own key, and alices public key, aG doesn't change
21:49 < HM> the group key changes all the time as Bob participates in many groups
21:49 < HM> this way Bob doesn't need his own key within each group
21:51 < HM> consider 1000 Bobs, each participating in 100 groups. your total keys if you use encryption is 100,000. which Ted has to keep safe until both Bob and Alice have at least received a copy
21:51 < HM> with this scheme you only need 1000 keys held by 1000 bobs (no work for Ted, already required) and 100 group keys
21:52 < HM> and Ted doesn't really have to keep much safe. he can make the right hand side completely public
21:53 < HM> damn, i've lost my nick list
21:53 < HM> hopefully that makes sense
21:54 <@gmaxwell> HM: I now send you off reading: http://en.wikipedia.org/wiki/Broadcast_encryption
21:56 < HM> hmm stateless users, sounds promising
21:58 < HM> i think the idea of traitor tracing is what i was getting at with blinding
21:58 < HM> since if Bob decides to do anything other than a multiply with their key they risk detection by Ted who will ban their ass
21:59 < HM> the broadcast analogy seems spot on though thanks
22:01 <@gmaxwell> You should read the cited papers, there has been a moderate amount published on this (a bunch by IBM people, oddly)
22:02 < HM> i think where it varies is Bob actually has 2 way comms with Ted
22:04 < HM> see the appeal is Alice can just talk to Ted any time and use her 2 keys ('g' and 'a') to produce the private key from bG
22:04 < HM> and later public 'g' but never 'a'
22:04 < HM> Ted never has to provide anything he hasn't had for a long time, just knowledge that the whole thing happened
22:05 < HM> hell Alice may evne sync regularly and download Teds logs
22:05 < HM> Ted is just an extension of Alice
22:05 < HM> who doesn't have her private key
22:07 < HM> *later publish 'g'
22:07 < HM> I'll scour the web for papers later, it's 3am. Night
--- Log closed Tue Mar 05 00:00:41 2013