01:09:40 | Taek: | Is 56 bits enough? The Bitcoin network does 2^67 hashes every block. Someone with 1% of that hashing power can crack a 56 bit password minute. It's stronger if you use multiple iterations, which might be enough for the average person |

01:09:57 | Taek: | It's not something that I would trust more than a few thousand dollars to though |

01:10:36 | Taek: | *56 bit password every minute |

01:11:38 | Luke-Jr: | Taek: mining chips can't crack passwords in any case |

01:11:51 | maaku: | maybe you remember two passwords? |

01:13:02 | Taek: | How hard would it be to manufacture a password cracking sha2 ASIC given that bitcoin mining asics exist? I legitimately don't know. |

01:14:47 | phantomcircuit: | Luke-Jr, very very specific passwords |

01:14:48 | phantomcircuit: | heh |

01:15:14 | phantomcircuit: | Taek, it costs >3m to do a 28nm asic |

01:15:22 | phantomcircuit: | the question isn't how hard, but how expensive |

01:17:18 | Taek: | that's convincingly expensive to me. I remember that you can skip the final 3 rounds of sha2 when doing Bitcoin mining, something I imagine most of the ASICs do. Wouldn't that make it essentially useless for passwords though, even if they did the same double hashing as Bitcoin? |

01:18:07 | Luke-Jr: | Taek: nah, the host CPU can do the full hash over for good guesses |

01:19:08 | Taek: | oh that makes sense |

01:20:39 | phantomcircuit: | Taek, you could repurpose bitcoin miners to brute force passwords which are hashed with sha256d which start with 32bits of leading zeros and which are a fixed 64 byte length |

01:23:17 | kanzure: | "given that bitcoin mining asics exist" has nothing to do with it, i would say just as easy as before. |

01:23:44 | kanzure: | and of course, not all asics require 28nm or $3M |

01:24:14 | phantomcircuit: | kanzure, sure for a couple hundred grand you can do 180nm |

01:24:57 | kanzure: | there was at least one company offering $3k per run but you'd get like half a wafer and >200nm feature sizes |

01:25:11 | kanzure: | but they would also do packaging for you and stuff. |

01:25:13 | phantomcircuit: | i've actually considered getting a 180nm fpga with static components to accelerate common hash algorithms to mess wtih altcoins |

01:25:32 | phantomcircuit: | kanzure, shared wafer lots |

01:25:37 | phantomcircuit: | those can take a long long time |

01:25:43 | kanzure: | oh, how long? |

01:25:48 | phantomcircuit: | indefinite |

01:25:53 | kanzure: | what? |

01:25:56 | phantomcircuit: | they wait to have enough people to do a full lot |

01:26:08 | phantomcircuit: | so you could be waiting foreve |

01:26:09 | phantomcircuit: | r |

01:26:42 | kanzure: | weird, i would have guessed there's more demand for partial wafer lots etc and they would fill up fast |

01:27:20 | kanzure: | i should put together a verilog or vhdl library of bitcoin stuff. hrm. |

01:29:05 | phantomcircuit: | kanzure, they do tend to fill up relatively quickly |

01:29:10 | phantomcircuit: | so it's mostly not an issue |

01:29:22 | kanzure: | meh? https://github.com/progranism/Open-Source-FPGA-Bitcoin-Miner/tree/master/src |

01:29:52 | phantomcircuit: | but it's still going to add some delay to a process that already takes minimum 45 days and average 60 |

01:52:10 | maaku: | maaku is now known as Guest20595 |

01:58:01 | Guest20595: | Guest20595 is now known as maaku |

02:15:10 | justanotheruser: | justanotheruser is now known as senpai-san |

02:16:14 | senpai-san: | senpai-san is now known as justanotheruser |

02:56:12 | maaku: | maaku is now known as Guest15747 |

03:26:03 | Guest15747: | Guest15747 is now known as maaku |

03:55:40 | zooko`: | zooko` is now known as zooko |

04:50:21 | maaku: | maaku is now known as Guest14231 |

05:44:52 | kanzure: | leaderless byzantine paxos http://research.microsoft.com/en-us/um/people/lamport/pubs/disc-leaderless-web.pdf |

05:46:49 | Taek: | long ass paper |

05:47:19 | kanzure: | brevity is the soul of not wasting my time, etc |

05:49:17 | Taek: | I actually really like reading Lamport. I find he gets the point across better than most writers. |

06:43:38 | wyager: | wyager has left #bitcoin-wizards |

06:50:22 | fanquake: | fanquake has left #bitcoin-wizards |

08:05:14 | card.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:14 | card.freenode.net: | Users on #bitcoin-wizards: andy-logbot ebfull Guyver2 profreid Adlai pen d4de^^ MoALTz__ mortale Dr-G TheSeven rdponticelli aburan28 c0rw1n_ RoboTeddy drawingthesun DoctorBTC p15 vmatekole Graftec Luke-Jr zenojis justanotheruser zwischenzug2 jtimon devrandom spinza copumpkin DougieBot5000 Max_H3adr00m EasyAt wizkid057 gavinandresen NewLiberty eristisk gribble go1111111 nuke1989 MRL-Relay artilectinc shesek epscy rfreeman_w wiretapped altoz koshii HaltingState Aquent Emcy |

08:05:14 | card.freenode.net: | Users on #bitcoin-wizards: hollandais tromp_ dansmith_btc2 super3 Guest29578 nanotube Starduster burcin SDCDev Meeh LarsLarsen samson_ pi07r optimator_ stonecoldpat wumpus Grishnakh mmozeiko jgarzik Nightwolf grubles berndj forrestv asoltys [d__d] livegnik reick nsh Dyaheon Sangheili Fistful_of_coins myeagleflies SomeoneWeird Krellan CryptOprah emsid harrow throughnothing abc56889 lechuga_ phedny @ChanServ fluffypony mr_burdell Apocalyptic kinlo midnightmagic starsoccer so |

08:05:14 | card.freenode.net: | Users on #bitcoin-wizards: ahmed_ Gnosis Keefe pajarillo roasbeef ryan-c otoburb helo [Tristan] TD-Linux catcow danneu UukGoblin poggy coryfields kgk btc_ crescendo amiller Eliel zibbo_ jbenet mappum yoleaux firepacket jrayhawk_ Hunger-- Muis Kretchfoop weex bbrittain tromp michagogo artifexd sl01 @gwillen Graet BlueMatt smooth CodeShark digitalmagus BrainOverfl0w espes__ waxwing BigBitz petertodd bobke andytoshi a5m0 heath kumavis phantomcircuit K1773R Alanius hguux |

08:05:14 | card.freenode.net: | Users on #bitcoin-wizards: dgenr8 lnovy LaptopZZ_ _2539 kanzure Taek gmaxwell sipa pigeons [\\\] coryfields_ Logicwax warren arowser HM Anduck NikolaiToryzin comboy [Derek] Iriez |

12:14:48 | Pan0ram1x: | Pan0ram1x is now known as Guest21768 |

17:02:21 | kanzure: | hmm andrychowicz/dziembowski are also looking towards the rational cryptography approach, http://eprint.iacr.org/2014/796.pdf |

17:03:04 | kanzure: | "In his paper Bahack shows than an adversary can discard a block on any depth with a probability 1 regardless of his computational power if he is willing to wait long enough." |

17:10:55 | kanzure: | a little off-topic, http://blanu.net/curious_yellow.html "The primary strategy behind the Warhol superworm is to pre-scan the network for vulnerable targets. When the worm is launched it already has a large list of targets with a known method for infection and can therefore quickly infect an initial seed population. One thing which the Warhol paper mentions is that better results might be achieved via a coordinated worm in which various ... |

17:11:01 | kanzure: | ... instances of the worm on different computers communicate with each other in order to optimize infection. The Warhol paper states, however, that no coordinated worm has ever been created. This paper proposes the first design for a worm which utilizes efficient communication between worm instances for an optimal infection strategy." |

17:22:02 | wumpus: | one drawback (from the worm's perspective) of that would be that other software could pretend that they're worm instances, and thus confuse and disrupt the worm's strategy |

17:34:17 | amiller: | kanzure, weird, that andrychowicz/dziembowski paper has basically exactly the same results and model as what i just submitted to eurocrypt. |

17:34:34 | amiller: | (neither of which has anything to do with rational crypto though) |

17:34:47 | kanzure: | oh, they mention it, that's all i meant |

17:48:11 | kanzure: | wumpus: worms would be authenticated i think |

18:02:41 | andytoshi: | i'd bet you could pull a key out of a worm if it had one |

18:05:22 | kanzure: | part of that page/article explains something about protecting an infected node because obv. it was just vulnerable to your own worm |

18:10:56 | fenn: | fenn has left #bitcoin-wizards |

18:33:20 | myeagleflies: | myeagleflies has left #bitcoin-wizards |

19:19:52 | gmaxwell: | kanzure: this is that approach that assumes hashpower (for the defenders and attackers) increases exponentially forever, and only obtains a non-negligible probablity in the limit and not over any remotely sane timeframe (like 1000 years)? |

19:21:04 | kanzure: | that's what i assumed when i saw it referenced, but i haven't confirmed |

19:28:58 | gmaxwell: | If so, it's something that I found intellectually very interesting, but it seemed to be of no pratical interest itself. |

19:31:54 | kanzure: | agreed, i'm more surprised that someone has already bothered to work out the exact scenario or w/e |

19:35:10 | amiller: | it's totally false that that attack has a negligible probability over a finite time frame |

19:38:24 | c0rw1n_: | c0rw1n_ is now known as c0rw1n |

19:40:01 | amiller: | (it's not even clear here what you would want "negligible" to mean here, because the attack does not involve hash collisions so there's no security parameter, and the strength of the attacker is denoted by a hashpower fraction p rather than some poly(k) function) |

19:41:30 | amiller: | "Her chances of succeeding are about ∆·p / (t−2015)" |

19:41:52 | amiller: | p is the attacker's strength (as a fraction of the honest rest of the network) |

19:41:55 | gmaxwell: | amiller: yes. this is attacker has 0.0001% of the hashpower forever, and the hashpower goes up exponentially forever (physically impossible). What I mean by negligible was that I ran numbers for some things assuming e.g. 1000 years and still ended up with success probablities under 1/2^128. |

19:43:06 | amiller: | okay the expression for the success probability in a finite time is for constant hashpower, no assumptoin about it going up |

19:43:28 | gmaxwell: | it's quite surprising and curious that they go up over time, but didn't seem to be consequential in any real sense. (Since external processes will effortless reject a 1 year rewrite, much less a 1000 year one; so ... why bother trying?) |

19:43:36 | amiller: | they only bring up increasing hashpower in the last paragraph, it's not required for the finite time probability |

19:43:37 | gmaxwell: | Okay then this is a different argument than the one I'm aware of. |

19:44:44 | amiller: | the paper presents the attack in sort of increasing complexity as it models more of the practical countermeasures bitcoin has for this |

19:45:54 | amiller: | to understand the basic attack, suppose the attacker can set choose an arbitrarily high difficulty for bocks he mines |

19:47:01 | amiller: | also suppose he has 10% of the hashpower, that he wants to rewind history to a point 1 month ago (from the time that the attack starts), and he wants to succeed at this by 1 month from now. |

19:47:26 | amiller: | on average it takes the adversary 20 months to build a chain with 2 months of work, regardless of the difficulty, right? |

19:48:38 | amiller: | but to succeed at this attack he has to find a *single* 2 month block in only 1 month, which is in like 5% of the expected amount of time |

19:49:59 | amiller: | he has roughly a 1/20 chance of attack success. |

19:50:48 | amiller: | 1-poisson.cdf(0,0.05) = ~0.049 |

19:51:31 | amiller: | (that's the probability of finding at least 1 block in 0.05 of the mean time to find a block) |

19:51:35 | gmaxwell: | I follow that. Yep. So how does this bridge to Bitcoin? The paper I read before on the diff ramping attack still required exp hashrate growth because the fixed retargeting windows meant the network still made progress. |

19:52:16 | gmaxwell: | (and so it needed the growth so the attacker could wipe out his past losses with constant probablity no matter how far behind he'd fallen) |

19:52:44 | amiller: | yes they introduce that (goofy) assumption so they can claim a finite "mean time to success" |

19:53:08 | amiller: | if that assumption isn't in place, the average amount of time to successfully revert to a fixed point in history is infinite... however the median time is finite |

19:53:19 | amiller: | meaning there's a finite time where the attack succeeds with probaility 50% |

19:55:43 | gmaxwell: | (the paper I'm thinking actually uses it to prove p=1 in the limit, ... but its not useful :) ) |

19:56:12 | amiller: | yeah we're talking about the same paper i think... http://arxiv.org/pdf/1312.7013.pdf |

19:57:25 | gmaxwell: | yep. K. |

19:59:20 | kanzure: | is there anything in the current bitcoind that rejects a 1 year rewrite, other than existing checkpoints? |

20:01:05 | amiller: | okay so because the difficulty by a factor of 4 each time, the attacker has to spend a lot more time just to increase the difficulty enough. But still the attacker has a probability of success in a finite time interval that's basically proportional to his hashpower, and the finite amount of time he's willing to try for |

20:01:19 | amiller: | even with the network having constant hashpwoer. |

20:05:01 | gmaxwell: | (well not 'each time' he has to mine 2016 blocks at the current difficulty, this is part of how I can't see that it ever reaches 50% success probablity, since there is progress enforced by the difficulty changing) |

20:06:38 | amiller: | if the 10% attacker starts today, he can create a fork with increased difficulty at the tip every 20 weeks (yes, admittedly that's already pretty impractical!)... let's say he spends a year and does this twice |

20:07:31 | amiller: | er... that's still not good, he's a year behind, and the 16x difficulty only lets him clear less than a year with a single block. |

20:08:17 | amiller: | how about he spends 60 weeks (a year and two months) but now he has a fork with 64x difficulty, which lets him clear 2 years in a single lucky block |

20:10:18 | amiller: | so, he spends an average of 1 year grinding on his fork to increase the difficulty to 64x, then he spends 1 year hoping to get a lucky block at that difficulty.... which again he can succeed at with probability 1/20 or so |

20:10:25 | gmaxwell: | there are around 52k blocks in a year, so you need a diff of roughly 100k higher to clear two years in a single lucky block. |

20:10:49 | amiller: | oh, crap yeah i messed up with 2 weeks instead of 10 minutes sheesh |

20:11:53 | gmaxwell: | bbiaf |

20:18:40 | amiller: | hmmm right i calculated that wrong anyway... |

20:24:24 | amiller: | okay i think you're right here, so it takes an attacker with constant hashpower something like 4^k time (also with very low variance) to increase the difficulty by 4^k... ok i'd have to work that out more |

20:28:03 | amiller: | maybe this is more fun with like a 49% attacker that doesn't fall that much behind. |

20:29:50 | amiller: | bbl |

21:08:02 | Taek: | The attacker in the DRA needs to find 2016 blocks at a given difficulty to push the difficulty up 4x |

21:08:20 | Taek: | Each time the attacker does this, it will take E(4x) longer than the last time |

21:08:38 | Taek: | which means the dominant term is the current 2016 blocks |

21:09:11 | Taek: | So the attacker only needs to get lucky on one set of 2016 blocks to be able to make up for all of the lost time |

21:09:53 | Taek: | Meaning the attacker can just keep driving the difficulty up and starting over |

21:10:30 | Taek: | In the meantime, the honest network is producing an exponential number of blocks with regards to the attackers re-rolls |

21:11:33 | Taek: | But getting lucky over the space of 2016 blocks seems very unlikely |

21:12:40 | Taek: | and has the attacker investing an exponential amount of time per retry |

21:15:35 | Taek: | Assuming the attacker has 40% total hashing power, remaining network has 60% (attacker is 2/3 strength of remaining network) |

21:17:19 | Taek: | The attacker needs to create 1008 blocks to catch up with his work from the previous tries, and 1008/3 blocks to catch up from being 1/3 less powerful |

21:19:26 | Taek: | So if the attacker can make 2016 blocks in the amount of time where you'd expect to see ~650, then the attacker succeeds in getting ahead |

21:19:53 | Taek: | So at 40% strength, the attacker just needs to raise the difficulty until he can create 2016 blocks in the space where you'd expect to see 650 |

21:33:06 | Taek: | using a poisson distribution (perhaps incorrectly), I'm getting a 10^-400 chance of success per retry |

21:33:21 | Taek: | needing to spend an approximate eternity, even at 40% hashing power |

22:03:20 | amiller: | i still think that's not the right way to look at it |

22:03:30 | amiller: | suppose the attacker doesn't want to rewrite a particular point in history |

22:03:51 | amiller: | but just wants to pull off a history revision attack that's X blocks long (from whatever the front of the main chain is when the attack succeeds) |

22:05:08 | amiller: | the point is the attacker can put in exactly the expected amount of work to increase the difficulty, and then has to get lucky on only the blocks after that |

22:07:19 | Taek: | Right how *how* lucky is important |

22:07:33 | Taek: | the longer the attacker takes to increase the difficulty, the luckier they have to get |

22:07:50 | Taek: | and each time they don't get lucky, they have that much more work to do catchup with |

22:08:14 | Taek: | *but how lucky |

22:09:04 | Taek: | so you have to keep driving up the difficulty as you fail to get lucky or you just fall behind from your unlucky attempts |

22:16:30 | amiller: | if you want to rewind history to a fixed date, then it gets more and more unlikely because you fall behind yeah |

22:17:18 | amiller: | but if you want to make *some* rewinding attack that rewinds T amount of history, then your probability of success each time you make a finite attempt is nonnegligible in T |

22:20:13 | Taek: | ok that makes sense. But then each time you have to start over in pushing the difficulty up? |

22:20:38 | Taek: | And all the mining from a failed attempt just goes to waste? (you can't get a reward?) |

22:32:23 | amiller: | Taek, yeah absolutely. |

22:32:24 | amiller: | it's still a pretty crappy and unrealistic attack, but it's not "negligible" in one way you'd want it to be |

22:32:25 | amiller: | i think the blck ramping cap is a pretty good defense. |

23:15:55 | midnightmagic: | |

23:21:28 | andytoshi: |