00:42:46phantomcircuit:I've been looking at time lock puzzles, specifically one which can be cheaply verified (excluding a chain of hashes) and cheaply created (seemingly excluding all solutions)
00:43:15phantomcircuit:(ie the problem needs a backdoor)
00:43:48kanzure:maybe there's a class of timelock puzzles that you can iterate over, but not know the solutions to upfront?
00:44:38phantomcircuit:im not sure that's why i was asking :P
00:45:17gmaxwell:phantomcircuit: what exactly are you excluding a chain of hashes for.
00:45:19kanzure:hey you wanted a solution hehe
00:47:49phantomcircuit:gmaxwell, need to be able to cheaply validate partial solutions
00:48:56phantomcircuit:not to mention doesn't fit the second constraint either
00:50:26gmaxwell:phantomcircuit: find me a partile preimage of 0
00:50:35gmaxwell:^ I generated you a timelock puzzle in constant time.
00:51:25gmaxwell:phantomcircuit: what do you mean by "cheaply validate partial solutions" You mean you need to cheaply validate a cumulative solution from many partial ones, in order to have progress and low variance?
00:51:36gmaxwell:If so, thats what the compact SPV proof does from the sidechains paper.
00:54:11phantomcircuit:hmm maybe i didn't articulate that very well
00:55:36phantomcircuit:E(m, k) such that k is cheap to construct if you know s, but can be otherwise constructed without s
00:55:51gmaxwell:right so you want encryption, and not just a proof of work.
00:56:59phantomcircuit:gmaxwell, encryption which can be decrypted by someone without the key, but only by solving a time lock puzzle
00:56:59gmaxwell:right so you actually want a asymetric encryption scheme where public keys can be generated without knowing the private keys; and then can be cracked with predictable time. I can give you something along those lines.
00:57:27gmaxwell:For example generate random small EC curves, and random pubkeys in them. Encrypt with M of these things. (M to lower variance)
00:58:00gmaxwell:Unfortunately EC attacks are not progress free, so larger participants have an advantage; which may be bad for some applications.
00:58:29gmaxwell:I am not aware of an public key encryption scheme where the best attack is a guess and check that allows you to blindly construct pubkeys.
00:58:33phantomcircuit:yeah it needs to be progress free
01:00:17phantomcircuit:i can actually use a chain of hashes for this but it's considerably suboptimal
01:00:40gmaxwell:oh perhaps a scheme based on error correcting codes. could satisify that largely.
01:01:08gmaxwell:your chain of hashes is symetric crypto though; sender has to solve the whole puzzle themselves first.
01:01:36phantomcircuit:that's seriously not ideal, but would actually work
01:01:41gmaxwell:rivest timelock puzzle works; but its trapdoored. the creator has a secret that can unlock it again for free.
01:02:11phantomcircuit:that's actually acceptable
01:02:24gmaxwell:oh well then you want the rivest timelock puzzle.
01:02:34op_mul:is it intended to be malicious, or a known backdoor?
01:02:39phantomcircuit:that one?
01:02:59gmaxwell:op_mul: no no not that kind of backdoor, perhaps I should say trapdoor.
01:03:27op_mul:you did say trapdoor, I just wanted to confirm it was an intentional differentiation.
01:03:55gmaxwell:Basically the puzzle is to compute successive squarings of a value mod some value. This is easy if you know the orders of the group (from the prime factors of the value), you can just compute the Nth squaring directly if you do.
01:04:24gmaxwell:If you don't know the factors, the best known way is to compute it the slow way.
01:04:31gmaxwell:by actually doing all the squarings.
01:05:24gmaxwell:it can be blinded too, as adam back pointed out on bct... which is kinda cool.
01:05:56gmaxwell:he'd wanted to use it for brainwallet (yuck) hardening; but for that application you have to store the value you're mod someplace.
01:07:48gmaxwell:by blinded I mean you can take an instance of the puzzle... modify it in a way that makes it indistinguishable from random, and hand it to someone to grind... and they can give you the value back to unblind and they learn nothing about your instance (at all, absolute zero knoweldge).
01:08:32gmaxwell:so they can't use that interaction with you to can any advantage in cracking your wallet for themselves.
01:08:42phantomcircuit:if im reading this right you can provide a cheaply verified solution to a third party without knowing the trapdoor secret, is that correct?
01:12:23gmaxwell:Say I know the factors P,Q of N (the composite these operations are mod). I can directly compute the X-th squaring of Y with O(1) work, lets call that answer A. I can tell you N, Y, X, H(A) and you can do the work (with O(X) operations) and find A, and show people.
01:15:01phantomcircuit:gmaxwell, it seems to me like you could abuse this to limit withholding attacks while also resisting censorship
01:15:43phantomcircuit:but only if you already have a pow system to provide ordering
01:16:56gmaxwell:sounds like you're talking about comitted transactions or something related. The problem with what I was just talking about for that is that the 'setup' is trusted. Imagine, I generate N, Y, X, H(A) ... but really instead of H(A) I just use a random value. So you do the X work, and the result doesn't match.
01:17:15gmaxwell:I can't prove that to anyone.
01:17:27gmaxwell:(well they can check for themseles with X work)
01:18:50phantomcircuit:hmm yeah
01:21:10gmaxwell:thats where you need something that doesn't have a trapdoor.
01:21:34gmaxwell:and you end up back at the discrete log based challenge I mentioned ( which is also on the altideas page from a few years ago)
01:23:59gmaxwell:so one possibility is this. Take a strong curve (like secp256k1), generate a random private key, and the matching public key. Reveal 256-x bits where x is some usefully small number like 64. Include a zero knoweldge proof that the revealed bits are consistent, so you know a search will be successful.
01:24:45gmaxwell:A snark could do the ZKP of course, but there may be less magic way.
01:25:10phantomcircuit:i was kind of waiting for the zk-snark solution to pop up :P
01:25:18gmaxwell:if you use a strong curve, the rho attack which has progress is infeasable, so you're left with only the progress free attack.
01:26:19gmaxwell:Though beware non-black-box group properties that might yield some speedup when you know part but not all of a key.
01:26:50phantomcircuit:right, but ultimately you dont want a progress free attack
01:27:32phantomcircuit:if it's easy to attack the program in parallel then it's not particularly useful as a time lock
01:28:09phantomcircuit:it's generally easy to improve the performance of a problem that can be solved in parallel
01:28:13gmaxwell:phantomcircuit: it's easy to give it progress.
01:28:19gmaxwell:you just apply encryption recursively.
01:28:36gmaxwell:e.g. generate N puzzles, and encrypted the Nth with the N-1th
01:33:46Eliel:... what happened to the "has to be progress free"?
01:38:19phantomcircuit:Eliel, for this you actually want progress
01:39:05Eliel:oh ok.
01:39:25Eliel:I just thought you said earlier you needed a progress free algo. Perhaps I misunderstood then.
01:40:00phantomcircuit:oh i did say that
01:40:03phantomcircuit:that's wrong
02:04:38amiller:phantomcircuit, have you looked at the expander graph based timelock puzzle
02:04:59amiller:phantomcircuit, http://www.cs.virginia.edu/~mohammad/files/papers/15%20TimeStamp.pdf
02:05:52amiller:eh i can't tell from your description of what you're actually looking for whether you want it to have a trapdoor or not
02:06:16amiller:i think you want timelock encryption and nevermind i have nothing new to say about that
02:06:46phantomcircuit:amiller, i horribly screwed up describing what i was looking for
02:08:27phantomcircuit:i want to encrypt a message such that the message can be decrypted by solving a time lock puzzle or if the original secret is provided
02:08:51phantomcircuit:optimally in such a way that the typical case isn't expensive
02:08:58phantomcircuit:ie construction is cheap
02:09:03phantomcircuit:amiller, that make sense
02:10:51amiller:yeah, got it... if i read the scrollback enough times it would have been clear :) the rivest timelock puzzle is good for that
02:10:56petertodd:phantomcircuit: https://github.com/petertodd/timelock
02:11:42petertodd:phantomcircuit: making construction cheap is not possible without sacrificing any hope of having predictability of decryption time (problem becomes parallelizable)
02:17:43phantomcircuit:petertodd, parallelization construction is a sufficient advantage for this application
02:17:52petertodd:phantomcircuit: what's the application?
02:18:15petertodd:phantomcircuit: note that timelock is parallelizable for the creator of the timelock
02:18:24phantomcircuit:yeah that's fine
02:18:31phantomcircuit:(indeed that's likely preferable)
02:18:55petertodd:you do have to do 100% of the work, but you can throw as many computers at it as you want
02:19:17amiller:i can't figure out how it works from the readme, looks cool though
02:19:37phantomcircuit:the missing piece for me is being able to show a third party that you did all the work and prove to them what the result was
02:19:57petertodd:amiller: it's just multiple parallel hash chains - you create them from a set of n nonces, then encrypt each chain with the result of the previous chain
02:20:29petertodd:amiller: the key trick is the result of a chain is also used to derive a secret key, which can be used to spend bitcoins on the blockchain, giving an incentive to tell the world how fast the cracking effort is going
02:20:36phantomcircuit:amiller, n seeds, encrypt seed n+1 with the final hash in the chain for seed n
02:20:49amiller:oh, ok i see
02:21:26phantomcircuit:petertodd, ah so you get a fuzzy timestamp of how fast someones able to do this
02:21:28phantomcircuit:that's neat
02:21:49amiller:thats really cool
02:22:08petertodd:exactly! and by opening it up to anyone in the world, you give all kinds of people incentives to push the envelope of performance, giving you good data on how many hash/s is possible
02:23:12petertodd:scalar performance is stagnent remember - best performance some grad students could pull out of some crazy liquid nitrogen cooled FPGA is probably only an order of magnitude worse than a expensive ASIC, maybe even closer if said students are really clever
02:23:43petertodd:I do need to change it to make the timelock algorithm be something even more common like AES encryption of fixed data - will map well to reasonably common ASIC implementations hopefully
02:28:12phantomcircuit:so a time lock puzzle in which any party that does the work to solve the puzzle can produce a proof of the puzzles solution (or if the setup was broken the lack of a solution)
02:28:33phantomcircuit:something tells me moon math
02:29:54petertodd:so proof the puzzle has a solution is dead simple: just provide the secret key created by doing the calculation
02:30:11petertodd:proof the puzzle doesn't have a solution OTOH is moon math,
02:30:20phantomcircuit:right it's the proof that the puzzle doesn't have a solution that i suspect it moon mathy
02:31:15petertodd:yeah, you may be able to do it by constructing a merkle tree over some of the inner parts of the calculation though - say every 10,000 hashes
02:33:24petertodd:the main thing is ask what exactly are you trying to prove? the ideal from the point of view of the uninterested timelock cracker is they want to know if they're going to get a reward by attempting to crack the timelock.
02:34:40petertodd:easiest thing to do there is just force the publication of the timelock in the first place to be accompanied by a bitcoin sacrifice around the same level as the value of each individual chain - you'll potentially waste some time, but at least it wasn't free to waste your time
02:35:46petertodd:a merkle tree then could save others time by letting them quickly verify your findings that the timelock puzzle was broken - but it's not clear that's actually in your incentive strictly speaking
02:37:06petertodd:now in theory you could construct a bitcoin-like script that would get you a reward for proving a timelock was broken, but the obvious way to do that is to hash basically every intermediate result into some giant tree... kinda ugly
02:37:24petertodd:er, s/ugly/stupidly inefficient to create/
02:37:50petertodd:(never mind that bitcoin is missing CAT so you can't create such a script :( )
03:42:28phantomcircuit:gmaxwell, might do best to ignore mr connor
03:43:32gmaxwell:but if I stop responding a terminator from the future may kill my mother! (or wait, save me from another robot from the future? I forget how this goes)
03:43:57gwillen:gmaxwell: depends on which movie
03:44:13gwillen:(same robot in both cases, IIRC)
03:44:54kanzure:all robots from the future are dangerous because they might be here to kill past-you
03:45:23kanzure:(i know someone who is deeply troubled by this to the point of something approximating inaction)
03:45:35phantomcircuit:gmaxwell, he's some altcoin creator (appears to have actually done some real work on that though!)
03:46:42gmaxwell:phantomcircuit: seems to be nothing on his github but promises, no code; there is a 'whitepaper' http://vanillacoin.net/papers/vanillacoin.pdf ... supprised to have not seen op_mul quoting from this one yet.
03:46:58gmaxwell:In any case, given that data I expect your assumptions are right.
03:47:13op_mul:gmaxwell: I figured people would be getting bored of that.
03:47:40phantomcircuit:gmaxwell, there is actual code
03:47:59phantomcircuit:it's all headers though :P
03:49:53op_mul:"I have thought about eventually SSLing all the connections. I assume anything
03:49:56op_mul:short of SSL would be pointless against DPI.
03:50:41op_mul:I'm not sure that really has any impact anyway. imagine for a second that all the bitcoin nodes ran on port 443 and used perfect SSL. you could still censor their connections by just looking at who they connect to.
03:50:53phantomcircuit:op_mul, anyways that cat5e run works perfectly fine with devices
03:53:49op_mul:(that assumes a eavesdropper with the ability to kill connections, not sit in the middle of them)
03:54:58phantomcircuit:op_mul, which is of course actually much easier
06:39:15gmaxwell:::sigh:: https://github.com/bitcoin/bitcoin/pull/5634#issuecomment-69484895
06:42:43op_mul:'This bug does not have any relations to "network consensus" like Gavin has stated.'
06:43:10op_mul:"ERROR: CScriptCheck() : ee6f0a01bc1ae0f7e79545a947d98ca2cee01394c69187ac6d1efbbc25f2ca5b:0 VerifySignature failed: Script evaluated without error but finished with a false/empty top stack element"
06:44:40op_mul:(many more lines follow of blocks failing verification, my node banning all of it's peers and freaking out)
07:08:20Dizzle__:Dizzle__ is now known as Dizzle
07:08:52op_mul:hm, why do we ban on an invalid block anyway, doesn't that impede the discovery of a large, invalid chain with valid PoW? my node would never have known, because it banned every peer it knew about.
07:12:31gmaxwell:op_mul: because they just wasted a huge chunk of your resources. The banning keeps people from iterating invalidity to starve you and potentially partition you.
07:14:25op_mul:not what I would have expected, but alright. I've found a few nodes on the network with 0 connections other than me, I'm assuming they hit some memory corruption or something and banned all of their peers as a result.
07:15:25op_mul:quite a few behind the main chain, too, though not at any regular interval.
07:15:40gmaxwell:yea, luke has (used to have?) graphs of this
07:16:44phantomcircuit: [03:42:28] gmaxwell, might do best to ignore mr connor
07:16:54op_mul:according to bitnodes.io it's 16% of the network that aren't at the tip, which is alarmingly high in my mind.
07:18:04gmaxwell:phantomcircuit: didn't have any liquor hard enough to forget that nonsense, it seemed.
07:18:12op_mul:syncing nodes don't announce themselves, so it wouldn't be attributed to that I don't think.
07:18:20phantomcircuit:gmaxwell, haha
07:19:21gmaxwell:op_mul: thats 'at the tip mean'? I mean, one should allow for 1 block plus rescan time slop.
07:19:42gmaxwell:op_mul: and exclude anything pre-0.8 for obvious reasons.
07:19:44op_mul:6 or more blocks behind. I'd give better stats but bitnodes doesn't publish them now.
07:21:06phantomcircuit:op_mul, i suspect there's a good number of nodes stalled waiting on a bad peer
07:21:32phantomcircuit:there seems to be a good number of connectable peers which dont respond to getdata requests at all
07:22:19op_mul:yes, I've noticed that too. a good litmus test to find fake nodes is to do an obscure network command like clearfilter.
07:23:58op_mul:would be nice to be able to know if these peers got stuck while syncing, or got left behind by the chain.
07:28:41midnightmagic:same model of robot anyway. different unit.
07:31:17op_mul:one is a *lot* more interesting though
07:40:14midnightmagic:yeah the one that happened before arnold decided he wanted to be the good guy so he wouldn't scare his kids
08:40:19luigi75ooooooooo:ciao a tutti
09:05:13sinisalo.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
09:05:13sinisalo.freenode.net:Users on #bitcoin-wizards: andy-logbot MoALTz__ Emcy eslbaer_ iddo Guyver2 HarusameNyanko bvu NewLiberty delll irc88 Fistful_of_Coins TheSeven thrasher` d1ggy_ Dr-G2 bosma Shiftos Krellan_ nullbyte Starduster yoleaux Dizzle butters zooko justanotheruser Tjopper DoctorBTC PRab dgenr8 NikolaiToryzin samson_ austeritysucks ryanxcharles nsh Quanttek epscy wizkid057 luny spinza fanquake copumpkin tacotime adlai atgreen roconnor nuke1989 Guest7999 DougieBot5000 mortale
09:05:13sinisalo.freenode.net:Users on #bitcoin-wizards: catlasshrugged PaulCapestany op_mul HaltingState maaku Graftec cluckj Hunger- hashtagg kyletorpey gribble ebfull Greed Iriez ajweiss BlueMatt mbelshe Graet jaekwon dansmith_btc midnightmagic starsoccer huseby Grishnakh Luke-Jr SubCreative BrainOverfl0w burcin [d__d] gavinandresen danneu catcow TD-Linux ryan-c smooth Alanius AdrianG tromp pigeons Dyaheon- Cory jbenet livegnik MRL-Relay lechuga_ pi07r sadgit throughnothing poggy JonTitor
09:05:13sinisalo.freenode.net:Users on #bitcoin-wizards: hollandais amiller LarsLarsen Muis kumavis michagogo artifexd lnovy cfields btc__ rasengan gavink hguux_ Meeh yrashk a5m0 jgarzik Keefe berndj fluffypony morcos Logicwax stonecoldpat sl01 optimator wiz null_radix roasbeef_ hktud0 BigBitz [\\\] mappum gnusha otoburb mr_burdell s1w go1111111 HM2 Apocalyptic sdaftuar btcdrak CryptOprah jcorgan forrestv tromp_ lclc_bnc harrow @gmaxwell isis brand0 eric Krellan @ChanServ jaromil petertodd helo
09:05:13sinisalo.freenode.net:Users on #bitcoin-wizards: v3Rve espes__ nickler ahmed_ warren fenn phantomcircuit kanzure bobke BananaLotus coryfields Anduck Eliel nanotube gwillen wumpus heath EasyAt asoltys_ K1773R comboy andytoshi warptangent Guest38445 kinlo azariah sneak @sipa Taek crescendo so phedny
09:05:13sinisalo.freenode.net:[freenode-info] please register your nickname...don't forget to auto-identify! http://freenode.net/faq.shtml#nicksetup
10:14:58lclc_bnc:lclc_bnc is now known as lclc
10:25:24d1ggy_:d1ggy_ is now known as d1ggy
11:30:10lclc:lclc is now known as lclc_bnc
11:59:59lclc_bnc:lclc_bnc is now known as lclc
12:05:03Pan0ram1x:Pan0ram1x is now known as Guest62409
13:54:21fanquake:fanquake has left #bitcoin-wizards
15:48:42fanquake:fanquake has left #bitcoin-wizards
16:20:29samson2:samson2 is now known as samson_
16:48:44d1ggy_:d1ggy_ is now known as d1ggy
19:38:36execut3:execut3 is now known as shesek
20:03:09kanzure:heh i am reading this prospectus that monetas has sent out, and basically they are admitting that they are shoveling crippleware
20:08:12sl01:kanzure: link?
20:14:58kanzure:does not seem to be public, will as
20:15:32kanzure:also, they directly and positively compare it to some well known scams and ponzi schemes at the moment (e.g., without mentioning the fraud), so i don't know what's going on here.. i'm gonna ignore this.
21:14:30adlai:how do you make a positive comparison to a known scamzi?
21:40:58nullbyte:monetas is a scamzi? thats news
22:07:44kanzure:adlai: like "it is similar to [totally disastrous thing that, apparently, someone does not know is totally disastrous]"
22:08:07kanzure:anyway, off-topic i suppose
22:17:28lclc:lclc is now known as lclc_bnc
22:57:28[\\\]:[\\\] is now known as imsaguy
22:57:38imsaguy:imsaguy is now known as [\\\]