| 00:42:46 | phantomcircuit: | 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:15 | phantomcircuit: | (ie the problem needs a backdoor) |
| 00:43:48 | kanzure: | maybe there's a class of timelock puzzles that you can iterate over, but not know the solutions to upfront? |
| 00:44:38 | phantomcircuit: | im not sure that's why i was asking :P |
| 00:45:17 | gmaxwell: | phantomcircuit: what exactly are you excluding a chain of hashes for. |
| 00:45:19 | kanzure: | hey you wanted a solution hehe |
| 00:47:49 | phantomcircuit: | gmaxwell, need to be able to cheaply validate partial solutions |
| 00:48:56 | phantomcircuit: | not to mention doesn't fit the second constraint either |
| 00:50:26 | gmaxwell: | phantomcircuit: find me a partile preimage of 0 |
| 00:50:35 | gmaxwell: | ^ I generated you a timelock puzzle in constant time. |
| 00:51:25 | gmaxwell: | 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:36 | gmaxwell: | If so, thats what the compact SPV proof does from the sidechains paper. |
| 00:54:11 | phantomcircuit: | hmm maybe i didn't articulate that very well |
| 00:55:36 | phantomcircuit: | E(m, k) such that k is cheap to construct if you know s, but can be otherwise constructed without s |
| 00:55:51 | gmaxwell: | right so you want encryption, and not just a proof of work. |
| 00:55:59 | phantomcircuit: | right |
| 00:56:59 | phantomcircuit: | gmaxwell, encryption which can be decrypted by someone without the key, but only by solving a time lock puzzle |
| 00:56:59 | gmaxwell: | 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:13 | phantomcircuit: | right |
| 00:57:27 | gmaxwell: | For example generate random small EC curves, and random pubkeys in them. Encrypt with M of these things. (M to lower variance) |
| 00:58:00 | gmaxwell: | Unfortunately EC attacks are not progress free, so larger participants have an advantage; which may be bad for some applications. |
| 00:58:29 | gmaxwell: | 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:33 | phantomcircuit: | yeah it needs to be progress free |
| 01:00:17 | phantomcircuit: | i can actually use a chain of hashes for this but it's considerably suboptimal |
| 01:00:40 | gmaxwell: | oh perhaps a scheme based on error correcting codes. could satisify that largely. |
| 01:01:08 | gmaxwell: | your chain of hashes is symetric crypto though; sender has to solve the whole puzzle themselves first. |
| 01:01:17 | phantomcircuit: | right |
| 01:01:36 | phantomcircuit: | that's seriously not ideal, but would actually work |
| 01:01:41 | gmaxwell: | rivest timelock puzzle works; but its trapdoored. the creator has a secret that can unlock it again for free. |
| 01:02:11 | phantomcircuit: | that's actually acceptable |
| 01:02:24 | gmaxwell: | oh well then you want the rivest timelock puzzle. |
| 01:02:34 | op_mul: | is it intended to be malicious, or a known backdoor? |
| 01:02:37 | phantomcircuit: | http://people.csail.mit.edu/rivest/lcs35-puzzle-description.txt |
| 01:02:39 | phantomcircuit: | that one? |
| 01:02:59 | gmaxwell: | op_mul: no no not that kind of backdoor, perhaps I should say trapdoor. |
| 01:03:27 | op_mul: | you did say trapdoor, I just wanted to confirm it was an intentional differentiation. |
| 01:03:55 | gmaxwell: | 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:24 | gmaxwell: | If you don't know the factors, the best known way is to compute it the slow way. |
| 01:04:31 | gmaxwell: | by actually doing all the squarings. |
| 01:05:24 | gmaxwell: | it can be blinded too, as adam back pointed out on bct... which is kinda cool. |
| 01:05:56 | gmaxwell: | 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:48 | gmaxwell: | 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:32 | gmaxwell: | so they can't use that interaction with you to can any advantage in cracking your wallet for themselves. |
| 01:08:42 | phantomcircuit: | 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:23 | gmaxwell: | 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:01 | phantomcircuit: | gmaxwell, it seems to me like you could abuse this to limit withholding attacks while also resisting censorship |
| 01:15:43 | phantomcircuit: | but only if you already have a pow system to provide ordering |
| 01:16:56 | gmaxwell: | 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:15 | gmaxwell: | I can't prove that to anyone. |
| 01:17:27 | gmaxwell: | (well they can check for themseles with X work) |
| 01:18:50 | phantomcircuit: | hmm yeah |
| 01:21:10 | gmaxwell: | thats where you need something that doesn't have a trapdoor. |
| 01:21:34 | gmaxwell: | 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:59 | gmaxwell: | 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:45 | gmaxwell: | A snark could do the ZKP of course, but there may be less magic way. |
| 01:25:10 | phantomcircuit: | i was kind of waiting for the zk-snark solution to pop up :P |
| 01:25:18 | gmaxwell: | 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:19 | gmaxwell: | Though beware non-black-box group properties that might yield some speedup when you know part but not all of a key. |
| 01:26:50 | phantomcircuit: | right, but ultimately you dont want a progress free attack |
| 01:27:32 | phantomcircuit: | if it's easy to attack the program in parallel then it's not particularly useful as a time lock |
| 01:28:09 | phantomcircuit: | it's generally easy to improve the performance of a problem that can be solved in parallel |
| 01:28:13 | gmaxwell: | phantomcircuit: it's easy to give it progress. |
| 01:28:19 | gmaxwell: | you just apply encryption recursively. |
| 01:28:36 | gmaxwell: | e.g. generate N puzzles, and encrypted the Nth with the N-1th |
| 01:33:46 | Eliel: | ... what happened to the "has to be progress free"? |
| 01:38:19 | phantomcircuit: | Eliel, for this you actually want progress |
| 01:39:05 | Eliel: | oh ok. |
| 01:39:25 | Eliel: | I just thought you said earlier you needed a progress free algo. Perhaps I misunderstood then. |
| 01:40:00 | phantomcircuit: | oh i did say that |
| 01:40:00 | phantomcircuit: | derp |
| 01:40:03 | phantomcircuit: | that's wrong |
| 02:04:38 | amiller: | phantomcircuit, have you looked at the expander graph based timelock puzzle |
| 02:04:59 | amiller: | phantomcircuit, http://www.cs.virginia.edu/~mohammad/files/papers/15%20TimeStamp.pdf |
| 02:05:52 | amiller: | 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:16 | amiller: | i think you want timelock encryption and nevermind i have nothing new to say about that |
| 02:06:46 | phantomcircuit: | amiller, i horribly screwed up describing what i was looking for |
| 02:07:30 | amiller: | :p |
| 02:08:27 | phantomcircuit: | 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:51 | phantomcircuit: | optimally in such a way that the typical case isn't expensive |
| 02:08:58 | phantomcircuit: | ie construction is cheap |
| 02:09:03 | phantomcircuit: | amiller, that make sense |
| 02:09:25 | phantomcircuit: | ? |
| 02:10:51 | amiller: | 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:56 | petertodd: | phantomcircuit: https://github.com/petertodd/timelock |
| 02:11:42 | petertodd: | phantomcircuit: making construction cheap is not possible without sacrificing any hope of having predictability of decryption time (problem becomes parallelizable) |
| 02:17:43 | phantomcircuit: | petertodd, parallelization construction is a sufficient advantage for this application |
| 02:17:52 | petertodd: | phantomcircuit: what's the application? |
| 02:18:15 | petertodd: | phantomcircuit: note that timelock is parallelizable for the creator of the timelock |
| 02:18:24 | phantomcircuit: | yeah that's fine |
| 02:18:31 | phantomcircuit: | (indeed that's likely preferable) |
| 02:18:55 | petertodd: | you do have to do 100% of the work, but you can throw as many computers at it as you want |
| 02:19:17 | amiller: | i can't figure out how it works from the readme, looks cool though |
| 02:19:37 | phantomcircuit: | 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:57 | petertodd: | 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:29 | petertodd: | 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:36 | phantomcircuit: | amiller, n seeds, encrypt seed n+1 with the final hash in the chain for seed n |
| 02:20:49 | amiller: | oh, ok i see |
| 02:21:26 | phantomcircuit: | petertodd, ah so you get a fuzzy timestamp of how fast someones able to do this |
| 02:21:28 | phantomcircuit: | that's neat |
| 02:21:49 | amiller: | thats really cool |
| 02:22:08 | petertodd: | 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:12 | petertodd: | 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:43 | petertodd: | 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:12 | phantomcircuit: | 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:33 | phantomcircuit: | something tells me moon math |
| 02:29:54 | petertodd: | so proof the puzzle has a solution is dead simple: just provide the secret key created by doing the calculation |
| 02:30:11 | petertodd: | proof the puzzle doesn't have a solution OTOH is moon math, |
| 02:30:20 | phantomcircuit: | right it's the proof that the puzzle doesn't have a solution that i suspect it moon mathy |
| 02:30:27 | phantomcircuit: | is* |
| 02:31:15 | petertodd: | 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:24 | petertodd: | 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:40 | petertodd: | 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:46 | petertodd: | 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:06 | petertodd: | 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:24 | petertodd: | er, s/ugly/stupidly inefficient to create/ |
| 02:37:50 | petertodd: | (never mind that bitcoin is missing CAT so you can't create such a script :( ) |
| 03:42:28 | phantomcircuit: | gmaxwell, might do best to ignore mr connor |
| 03:43:32 | gmaxwell: | 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:57 | gwillen: | gmaxwell: depends on which movie |
| 03:44:13 | gwillen: | (same robot in both cases, IIRC) |
| 03:44:54 | kanzure: | all robots from the future are dangerous because they might be here to kill past-you |
| 03:45:23 | kanzure: | (i know someone who is deeply troubled by this to the point of something approximating inaction) |
| 03:45:35 | phantomcircuit: | gmaxwell, he's some altcoin creator (appears to have actually done some real work on that though!) |
| 03:46:42 | gmaxwell: | 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:58 | gmaxwell: | In any case, given that data I expect your assumptions are right. |
| 03:47:13 | op_mul: | gmaxwell: I figured people would be getting bored of that. |
| 03:47:40 | phantomcircuit: | gmaxwell, there is actual code |
| 03:47:59 | phantomcircuit: | it's all headers though :P |
| 03:49:53 | op_mul: | "I have thought about eventually SSLing all the connections. I assume anything |
| 03:49:56 | op_mul: | short of SSL would be pointless against DPI. |
| 03:50:41 | op_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:53 | phantomcircuit: | op_mul, anyways that cat5e run works perfectly fine with devices |
| 03:51:46 | phantomcircuit: | other* |
| 03:53:49 | op_mul: | (that assumes a eavesdropper with the ability to kill connections, not sit in the middle of them) |
| 03:54:58 | phantomcircuit: | op_mul, which is of course actually much easier |
| 06:39:15 | gmaxwell: | ::sigh:: https://github.com/bitcoin/bitcoin/pull/5634#issuecomment-69484895 |
| 06:42:09 | op_mul: | ._. |
| 06:42:43 | op_mul: | 'This bug does not have any relations to "network consensus" like Gavin has stated.' |
| 06:43:10 | op_mul: | "ERROR: CScriptCheck() : ee6f0a01bc1ae0f7e79545a947d98ca2cee01394c69187ac6d1efbbc25f2ca5b:0 VerifySignature failed: Script evaluated without error but finished with a false/empty top stack element" |
| 06:44:40 | op_mul: | (many more lines follow of blocks failing verification, my node banning all of it's peers and freaking out) |
| 07:08:20 | Dizzle__: | Dizzle__ is now known as Dizzle |
| 07:08:52 | op_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:11:54 | gmaxwell: | https://bitcointalk.org/index.php?topic=920344.0 |
| 07:12:31 | gmaxwell: | 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:25 | op_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:25 | op_mul: | quite a few behind the main chain, too, though not at any regular interval. |
| 07:15:40 | gmaxwell: | yea, luke has (used to have?) graphs of this |
| 07:16:44 | phantomcircuit: | [03:42:28] gmaxwell, might do best to ignore mr connor |
| 07:16:46 | phantomcircuit: | :( |
| 07:16:54 | op_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:04 | gmaxwell: | phantomcircuit: didn't have any liquor hard enough to forget that nonsense, it seemed. |
| 07:18:12 | op_mul: | syncing nodes don't announce themselves, so it wouldn't be attributed to that I don't think. |
| 07:18:20 | phantomcircuit: | gmaxwell, haha |
| 07:19:21 | gmaxwell: | op_mul: thats 'at the tip mean'? I mean, one should allow for 1 block plus rescan time slop. |
| 07:19:42 | gmaxwell: | op_mul: and exclude anything pre-0.8 for obvious reasons. |
| 07:19:44 | op_mul: | 6 or more blocks behind. I'd give better stats but bitnodes doesn't publish them now. |
| 07:21:06 | phantomcircuit: | op_mul, i suspect there's a good number of nodes stalled waiting on a bad peer |
| 07:21:32 | phantomcircuit: | there seems to be a good number of connectable peers which dont respond to getdata requests at all |
| 07:22:19 | op_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:58 | op_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:41 | midnightmagic: | same model of robot anyway. different unit. |
| 07:31:17 | op_mul: | one is a *lot* more interesting though |
| 07:40:14 | midnightmagic: | yeah the one that happened before arnold decided he wanted to be the good guy so he wouldn't scare his kids |
| 07:40:18 | midnightmagic: | :-( |
| 08:40:19 | luigi75ooooooooo: | ciao a tutti |
| 09:05:13 | sinisalo.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:13 | sinisalo.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:13 | sinisalo.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:13 | sinisalo.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:13 | sinisalo.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:13 | sinisalo.freenode.net: | [freenode-info] please register your nickname...don't forget to auto-identify! http://freenode.net/faq.shtml#nicksetup |
| 10:14:58 | lclc_bnc: | lclc_bnc is now known as lclc |
| 10:25:24 | d1ggy_: | d1ggy_ is now known as d1ggy |
| 11:30:10 | lclc: | lclc is now known as lclc_bnc |
| 11:59:59 | lclc_bnc: | lclc_bnc is now known as lclc |
| 12:05:03 | Pan0ram1x: | Pan0ram1x is now known as Guest62409 |
| 13:54:21 | fanquake: | fanquake has left #bitcoin-wizards |
| 15:48:42 | fanquake: | fanquake has left #bitcoin-wizards |
| 16:20:29 | samson2: | samson2 is now known as samson_ |
| 16:48:44 | d1ggy_: | d1ggy_ is now known as d1ggy |
| 19:38:36 | execut3: | execut3 is now known as shesek |
| 20:03:09 | kanzure: | heh i am reading this prospectus that monetas has sent out, and basically they are admitting that they are shoveling crippleware |
| 20:08:12 | sl01: | kanzure: link? |
| 20:14:58 | kanzure: | does not seem to be public, will as |
| 20:14:59 | kanzure: | *ask |
| 20:15:32 | kanzure: | 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:30 | adlai: | how do you make a positive comparison to a known scamzi? |
| 21:40:58 | nullbyte: | monetas is a scamzi? thats news |
| 22:07:44 | kanzure: | adlai: like "it is similar to [totally disastrous thing that, apparently, someone does not know is totally disastrous]" |
| 22:08:07 | kanzure: | anyway, off-topic i suppose |
| 22:17:28 | lclc: | lclc is now known as lclc_bnc |
| 22:57:28 | [\\\]: | [\\\] is now known as imsaguy |
| 22:57:38 | imsaguy: | imsaguy is now known as [\\\] |