00:04:11gmaxwell:yea, when their paper came out I was kinda torn with correcting some of the grand standing. In the initial post (and in more detal in post #5) I explained some approaches to not need a TTP... but whatever, I'm supper happy they are implementing things and working out some details
00:04:33gmaxwell:I can only guess that the positioning is a result of reaching some minimum publishable unit test. :(
00:05:06gmaxwell:But it is a bit hard to not be offended at positining the whole idea as though it were a new invention.
00:07:39gmaxwell:maaku: or its just sloppyness
00:09:04gmaxwell:IIRC their paper also attributed random things from the threat to me too. ::shrugs::
00:09:13gmaxwell:but whatever, useful work is useful.
00:09:19gmaxwell:And they published code with their work.
00:11:31maaku:yeah i sent him a note about it. didn't CC the list though, because it is good work and I don't want to distract from that...
00:14:23gmaxwell:maaku: free on monday evening: http://www.meetup.com/SF-Bitcoin-Devs/events/195004712/ ?
03:48:22Pasha:Pasha is now known as Cory
03:53:16dgenr8:wumpus: do you have a reference for exactly what you mean when you refer to replace-by-fee?
04:00:51dgenr8:jgarzik: fwiw regarding "network tx" concept, it sounded interesting, but I wondered if it was mainly to avoid the work in revving tx format
04:01:44jgarzik:dgenr8, of course. there are serious risks and billions of value at stake during any conscious fork
04:02:26jgarzik:not just the theoretical game some people seem to treat it
04:02:52dgenr8:gmaxwell: you must tolerate fools, while the rest of us must fight the urge to create yet another altcoin
04:05:32jgarzik:dgenr8, We all have "theorycoin" or "cleanslatecoin" that we would create...
04:09:14dgenr8:expiring from mempool based on nLockTime, on a time scale of days, solves a big problem with expiring by wall clock and does none of: fork; whole new failure mode; invalidate existing tx; break even "large" reorgs.
04:35:59nkuttler_:nkuttler_ is now known as nkuttler
04:47:10jcorgan_:jcorgan_ is now known as jcorgan
06:40:36sl01:from the storj metadisk paper: ", in the same way that Bitcoin prices are in part determined by the cost
06:40:39sl01:of mining Bitcoin"
06:47:02sipa:dgenr8: #bitcoin-dev
07:43:01Luke-Jr:sl01: doesn't suggest confidence in storj design, does it? :p
07:46:01justanotheruser:sl01: is that just a comment or a fundamental assumption for their design to work? Link?
08:22:06sl01:justanotheruser: http://metadisk.org/metadisk.pdf
11:51:36SDCDev:SDCDev is now known as Rynomster
11:51:55Rynomster:Rynomster is now known as SDCDev
12:39:04hearn:hello
12:39:26hearn:gmaxwell: new zk-SNARK paper, it's awesome: http://eprint.iacr.org/2014/595.pdf
12:39:43hearn:gmaxwell: proving time is now a fixed multiple of execution time (ok, a high multiple, ~20 seconds per cycle)
12:40:14hearn:gmaxwell: or 0.05 hertz :)
12:41:07hearn:BUT, very interesting advance. summary of paper is: each step in the computation is now to run under ZKP: (1) verify previous zk-SNARK (2) run a machine step.
12:41:09hearn:so it's recursive
12:42:00hearn:they manage to find a way to do the elliptic curve pairing calculations inside the circuit efficiently too, using some crazy curve-cycle technique i didn't grok yet (still working through the paper)
12:42:15hearn:they actually found a pair of curves such that the field size of one is equal to the group order of the other and vice versa
12:43:51hearn:gmaxwell: another neat technique - they design a custom hash function designed for efficient implementation in the circuit, and from that construct an efficient merkle branch verification circuit
12:50:29untilted:untilted has left #bitcoin-wizards
13:28:39hearn:gmaxwell: took them ~70 core years to find the curves
13:31:02gmaxwell:I was aware of the possibility of that recursive construction. (It must have been mentioned in another one of their papers)
13:31:18gmaxwell:Neat.
13:41:16gmaxwell:sipa: https://bitcointalk.org/index.php?topic=727918.0
13:46:05sipa:gmaxwell: replied
13:49:33gmaxwell:sipa: thanks! (If you note his proposed implementation of 'even' is actually picking the small s)
13:53:15sipa:gmaxwell: see my edit :)
14:09:54hearn:gmaxwell: yeah the whole paper is very easy to read and very clever
14:10:37hearn:gmaxwell: makes me wonder if in future we're going to be wanting to add support for MNT4/MNT6 curves to OP_CHECKSIG :)
14:18:23hearn:gmaxwell: i guess now it's "just" a case of optimisation that constant multiplier through as many traditional techniques as possible
14:23:51gmaxwell:hearn: a little unfortunate that they've chosen the 80 bit security level, just at a time when bitcoin completes 2^80 computation. :P
14:23:59hearn:heh
14:24:33gmaxwell:(in these cases the 'security level' is also for a class break, that basically makes discrete logs solvable for there curves and would break every use.)
14:27:48gmaxwell:talk about rigid curve selection though, hah.
14:28:35hearn:yeah. of course once people start wondering "what if the NSA chose those curves" we're doomed :)
14:29:21gmaxwell:well right, annoyingly it doesn't sound like they used a determinstic process to choose them (or at least haven't mentioned it!)
14:29:40hearn:is it possible to do it deterministically? sounded like a classical brute force search
14:29:53hearn:i suppose you can convince yourself the curves are legit by just checking that they satisfy the absurdly specific requirements
14:30:11hearn:the chances of two curves being both weak AND satisfiying those requirements seems minimal
14:30:28gmaxwell:Sure. Thats the idea of rigidity, that the requirements basically fix the selection, but you still need to show that you picked the first such one you found.
14:31:40gmaxwell:The find a pair of pairing friendly curves such that the prime order of one curve is the field size used for the other one, and vice versa. It would be simple enough to conduct your tests in a particular 'obviously fair' order, then just disclose the solution, and someone could independently verify that there were no earlier solutions in your order.
14:31:46gmaxwell:s/The/They/
14:34:34hearn:yeah
14:34:47hearn:well i guess this is not the last word in 2-adic curve cycles so perhaps the next one will do this
14:35:45gmaxwell:yea, well as I said, 80 bits is ... bleh. (mostly bleh because it's a class break, so your not-worth-attacking system may because broken because some other genius put something stupidly valuable behind the same cryptosystem)
14:36:04gmaxwell:s/because/become/
14:45:30gmaxwell:The fact that their specific search approach requires that one of the curves has an embedding degree of 4 makes higher security a pain— probably why they settled on 80 bits.
14:47:25gmaxwell:a ~256 bit 4-embedding curve only has about 80 bits of security (because 4*256 = 1024, and Fp|1024| has only about 80 bits of discrete log security)
14:49:54hearn:i thought you halved the bit length to get dl security?
14:49:59hearn:what's the relationship between 1024 and 80?
14:52:08gmaxwell:You half bit length to get dl security on sutable elliptic curves... but the way pairing works is that there is a transfer from points on a small dl-hard elliptic curve, to a larger integer field where discrete logs are 'easy'— but if you picked your parameters wisely, the 'easy' discrete log is still intractable there.
14:56:07gmaxwell:And 1024 bit discrete log with integers has roughly 80 bit security.
14:58:22o3u:o3u is now known as Fistful_of_coins
14:59:49gmaxwell:The other bummer of their approach is that it forces it onto MNT curves that are a fair bit slower to verify outside of their system than the more normal BN curves... so the snark verifier for this system will be slower.
15:00:11gmaxwell:(I assume they give performance numbers, but I haven't gotten very far into the paper yet)
15:02:23gmaxwell:yea, they show their verifier taking 23ms.
15:03:37gmaxwell:(plus some amount that depends on the program size, since their hash function for verifying program consistency is also much slower, though that can be amortized against multiple executions of the same program, or skipped for most of our applications for just putting the program hash in the public key)
15:03:51gmaxwell:(also much slower than a regular cryptographic hash)
15:04:44hearn:ah, right
15:04:57hearn:yes indeed. going to bit length div 2 is the entire point of using elliptic curves in the first place
15:05:14gmaxwell:oh ha. in 8. open problems they also note the problem with increasing the security due to the embedding degree stuff.
15:05:27hearn:i missed the part where the pairing was mapping onto a regular integer field rather than a field of points
15:05:41hearn:seems like it parallelises very well though
15:05:44hearn:for 4 cores they get a 3x speedup!
15:10:43gmaxwell:Thats the prover... yea, though I'm not sure how they can get more than a ~8 fold speedup since this kind of snark involves roughly 8 pairing operations in the verification, and they compute the proof linearly, an instruction at a time... so that should give an upper bound on the prover parallelization gains. However, they could just as well have proposed a tree structured prover that would have had much more parallelism.
15:14:01gmaxwell:beyond parallelism, even the fully linear construction is perfectly pipelineable.
15:43:08tacotime:https://rushwallet.com/#m um, hm
15:43:59tacotime:oh, it's from the ethereum guys.
15:44:18gmaxwell:ISTM that it may be more pratical to arrange the proof as a tree of fixed depth... this sets an upper bound on the computation size under a given proof, but it can be arbitrarily large. This would remove the requirement the the curves for a cycle, instead you just need a collection of curves whos base field is the order of the prior one. And you can arrange it so the top one is optimally efficient to execute on a cpu since it'll ...
15:44:25gmaxwell:... never be used inside a proof... and the inner ones will never be run by a verifier so it's only relevant that they be fast inside the prover.
15:44:50pigeons:is it really? they really are into the whole mouse movement entropy source thing
15:45:48gmaxwell:tacotime: their first version of their 'mouse movement entropy' sampled the mouse only 5 times in a tight loop.. had had no other real source of cryptographic randomness (e.g. it was just time and math.random...). Expect a bunch of presold 'ether' to get stolen. :(
15:46:07pigeons:i noticed i just swish back from side to side on this one
15:46:51tacotime:gmaxwell, yikes.
15:48:20gmaxwell:dsnrk complained about it and they quietly improved it, then when he pressed in public they claimed it was no issue. :-/ Last I checked it was still braindamaged (still using math.random and not window.crypto)
15:50:36dsnrk:tacotime: gmaxwell: it's still like that. Vitalik's horrible code is used for making all Ethereum private keys (though it's not 5 rounds now, it's slightly more), for the KryptoKit browser extension wallet, and for the newly launched RushWallet.com (think instawallet). I've notified them a bunch of times that it's still totally nuts to be using it, but it's "industry standard".
15:51:18gmaxwell:Industry standard now means horrifying and not used by anyone else?
15:55:13tacotime:speaking of which, what are we using?
15:55:15tacotime:https://github.com/monero-project/bitmonero/blob/master/src/crypto/random.c
15:55:23dsnrk:https://pay.reddit.com/r/ethereum/comments/2bilqg/note_there_is_a_paranoid_highsecurity_way_to/cj5s4ub < if anybody was curios as to vbuterin's responses. they ignored me up until the point where I called them out for it in public, which is why my responses are a little more terse than you'd expect.
15:55:23tacotime:dev/urandom i guess
15:58:17dsnrk:Bitcoin QT gathers it's own just because Windows doesn't really have /dev/random, I think. there's something in there about taking screenshots.
16:10:37grubles:kryptokit is from the ethereum peeps as well?
16:11:27pigeons:yes vitalik at least
16:12:34grubles:hm
16:13:13gmaxwell:Hm. I suppose that notion of having the top pairing group be cheap to verify doesn't preclude the cyclic construction. e.g. you can just have a cycle where one of the curves base points is the order of an easily verified field.
16:14:16gmaxwell:I'm sure the people who are unable with the security proof for their prior snark are having fits over this paper, because it makes the recursion in the security assumption infinite— some people were already pretty unhappy with the existing handwave.
16:42:25phantomcircuit:gmaxwell, nobody will even be able to prove that their ether got stolen
16:42:34phantomcircuit:although i dont expect it to much matter since they're worthless
16:50:49dsnrk:phantomcircuit: yup. it'll be put down to people not securing their email (why on earth are they emailing the private keys anyway)
16:51:49phantomcircuit:dsnrk, if they dont email the private keys people will complain about losing them
16:51:55phantomcircuit:it's basically a lose lose
16:52:14phantomcircuit:in the end i dont think it will matter though since ethereum has basically zero chance of working
16:52:18dsnrk:phantomcircuit: people used throwaway email accounts for it.
16:52:20phantomcircuit:so
16:52:32phantomcircuit:"oh nose my worthless ethers got stolen"
16:52:35phantomcircuit:shrug
16:52:59dsnrk:no, the only endings I can see is 1) everybody gets it stolen due to the RNG bug 2) Vitalik is arrested 3) everybody realises how useless it all is
16:53:11grubles:1 ether = 0.002+ btc
16:53:20grubles:because they said so
16:54:21dsnrk:as was pointed out to me before, the IPO altcoin thing is sort of a dotcom bubble. you could throw up anything at the moment and people would "invest".
16:56:28tacotime:that's why i took my ipo down. that and i'm just not terribly confident in my programming skills. :P i've never bought into an ipo and i have no plans to ever do so, after what happened with mining pre-orders.
16:57:23phantomcircuit:dsnrk, 2) depends on 1) and 3)
16:57:29tacotime:unfortunately it seems that the user base of cryptocurrencies are slow to understand that what cryptocurrency transfers amount to is irreversible wire transfers, and there's a reason banks are usually belligerent about doing them.
16:57:39phantomcircuit:the SEC is unlikely to take significant action unless people lose their money
16:57:50phantomcircuit:(which i personally think is extremely likely)
16:58:35tacotime:it took a long time to get hashfast and bfl to the courts, and that's still ongoing.
16:59:36dsnrk:they didn't in the public view take $20.5M USD though.
17:00:08tacotime:well, hashfast for sure took millions, i'm sure bfl too.
17:00:21tacotime:millions isn't really that much money these days, considering what some apps sell for.
17:00:32gmaxwell:SEC actions can be much faster, but also seem to be not as consequential.
17:00:39dsnrk:it is to the poor fools "investing".
17:01:01phantomcircuit:gmaxwell, SEC tends not to take significant action unless people actually lose a lot of money
17:01:04tacotime:well, poor implies they can't afford the lawyers necessary to make someone responsible for their actions. :P
17:01:18gmaxwell:E.g. Satoshi dice's 'investment' stuff resulted in a ~$50k fine, in that case AFAIK no one was crying about money lost.
17:01:19kanzure:i have emailed private keys just to monitor some addresses for withdrawals from email snoopers
17:01:24kanzure:*for email snoopers
17:40:33lechuga__:lechuga__ is now known as lechuga_
18:26:12eizh_:eizh_ is now known as eizh
19:19:06Luke-Jr:[17:01:18] E.g. Satoshi dice's 'investment' stuff resulted in a ~$50k fine, in that case AFAIK no one was crying about money lost. <-- maybe someone did. it's not like they weren't cheating people
19:29:38helo:kanzure: any bites?
19:30:59kanzure:not yet
19:48:04andytoshi:kanzure: in clonecoin developer logic i believe that constitutes a proof that SMTP servers are secure key storage
19:48:58kanzure:i am trying to decide when to become surprised that there's no takers
19:49:22kanzure:for example, if i send a new one today, and only send it over email once, to some really strange destination, should i be surprised if the balance is never stolen?
19:49:36kanzure:s/stolen/taken
19:51:56andytoshi:i'd guess that PGP keys are scanned for and stored but never used (except by NSA who is also storing all the encrypted emails)... bitcoin keys might be caught in the dragnet but i'd bet nobody looks specifically for them
19:52:08andytoshi:maybe when NSA comes to your door one of the individual agents will see it and take them :P
19:52:25andytoshi:it's a pretty weird thing to transfer by email
19:58:51gmaxwell:annoyingly I know no efficient way to construct a single tx out which can be spent by a large number of identifyable secrets. If script were a little more powerful it could be done though.
19:59:25gmaxwell:(e.g. a 1 of N where N can be very large and the pubkey+scriptsig is at worst log(n) in size)
20:01:37kanzure:wouldn't the snoopers want to avoid those because it would reveal their monitoring presence?
20:01:59kanzure:they would have to bet that the person who setup the private key would have forgotten which channel it was published through
20:02:54kanzure:(and they would notice the weird scheme when programming their snooptaker)
20:04:40kanzure:i suppose that's the same bet they would be taking anyway with any other output they are taking for themselves
20:06:22Starduster_:Starduster_ is now known as Starduster
20:19:07andytoshi:good point kanzure probably anyone skimming keys will never use them visibly (certainly not record their usage in a blockchain!)
20:29:35gmaxwell:kanzure: depends on how big the bounty is. :P
20:31:04kanzure:true. plus things like prisoner's dilemma about other skimmers possibly taking it first..
20:37:00gmaxwell:kanzure: well you get fun things like the NSA would never move it even if it was huge, but ... maybe their staff is not quite so 'trustworthy'.
21:02:42maaku:that's why it would be nice if bitcoin script was expressive enough to implement various other crypto systems
21:03:12maaku:so we could have other bounties like the sha256 birthday bounty
22:18:05tromp__:how is that different from a sha256 collision bounty?
22:19:33sipa:how is what different?
22:19:44sipa:i think maaku means 'other things like that'
22:19:57sipa:the sha256 collision is just one of the few things that are possible today
22:20:06tromp__:maaku wanted more expressive bitcoin script to "have other bounties like the sha256 birthday bounty"
22:20:38sipa:yes
22:20:49sipa:so to more things like sha256 collisions?
22:21:01sipa:*be able to do
22:21:02gmaxwell:like other functions.
22:21:43tromp__:ah, i seem to have misparsed his grammar
22:21:43gmaxwell:tromp__: Maaku was referring to things like 37k7toV1Nv4DfmQbmZ8KuZDQCYK9x5KpzP
22:22:08tromp__:yes, i know peter todd offered many such bounties in sep '13
22:22:14gmaxwell:get 2.4 BTC if you know a collision for sha1 and share it with the network.
22:23:45midnightmagic:can i still claim that if my input text is like 40MB ?
22:24:02tromp__:as peter noted, 3) Due to limitations of the Bitcoin scripting language bounties can only be collected with solutions using messages less than 521 bytes in size.
22:25:22gmaxwell:The discussion is here:
22:25:22gmaxwell:http://download.wpsoftware.net/bitcoin/wizards/2013/09/13-09-09.log
22:25:29gmaxwell:starts at 02:02 < gmaxwell> Someone should create a P2SH address that serves as a bounty for a SHA-256 collision. The script would be something like "OP_2DUP OP_NUMNOTEQUAL OP_VERIFY OP_SHA256 OP_SWAP OP_SHA256 OP_EQUALVERIFY"
22:26:46gmaxwell:hm. I thought there was more discussion than that, but I guess it must have moved someplace else.
22:27:03midnightmagic:i think there was a bitcointalk post about it too
22:27:05gmaxwell:E.g. the reason that there is an ABS one out of a desire to have one that was actually testable for people. :P
22:27:14tromp__:also see this thread https://bitcointalk.org/index.php?topic=293382.0
22:27:15gmaxwell:midnightmagic: yes, petertodd went and made a post.
22:29:48gmaxwell:This was also the actual motivation to add a decodescript to the bitcoin rpc, so you could actually verify the address did what you thought it did.
22:30:24gmaxwell:(which actually was the gating factor on announcing the addresses, amusingly enough)