00:00:16tromp_:no zooko, you get to choose the macro nonce and nothing else
00:00:36tromp_:that fixes the graph
00:01:02Taek:gmaxwell: amortization of equipment costs is less of a centralization thing and more of needing to be in it for the long haul. As I understand, it's only a centralization problem if the entry costs are high (e.g. needing a $150 miner to be competitive vs. needing a $15,000 miner to be competitive).
00:02:13coke0:cost is dominated by variance
00:02:27adam3us:tromp: "the size of this array is chosen to be significantly larger than the largest cache available; at present, the size of hte array could be 16MB, say" :) (2002 first paper on memory bound PoW.)
00:02:36coke0:not the cost of the equipment per se, but the economic opportunity cost
00:02:36zooko:I think this is the Fiat-Shamir transform: instead of me giving you a random graph and you solving a challenge in it (e.g. find a cycle in it), you can give
00:02:53zooko:me a random graph along with a solution to the challenge, but you have to prove that the graph was generated in a way that it would be hard for you to have picked an easy one.
00:03:11zooko:I.e., by generating the graph using (in the old style, at least) a Random Oracle from something else that you are committed to,.
00:03:30zooko:Am I understanding "Fiat-Shamir transform" right?
00:03:41bramm:zooko, You can't make the graphs biased
00:03:52tromp_:coke0: one scenario is: big mining operators will fill warehouses with fpgas and dram clusters but will be less centralized because cooling and power costs are less of an issue
00:04:02bramm:Sorry, accidentally missed the last few minutes of discussion before sending my last message
00:04:25coke0:the cooling argument works at massive scales
00:04:46tromp_:the scale will be limited by dram costs
00:05:00gmaxwell:Taek: I don't quite follow that argument. Lets assume the operating costs are ~0. Say today mining is very profitable and so I go out and buy huge amounts of ram based hardware, enough to the point where I'm moving the market price and disrupting my profit plans or changing the network difficulty. Okay. great. now time goes on and difficulty rises (from me and others doing that). New entrants are locked out because they cannot ...
00:05:02adam3us:zooko: fiat-shamir transform is using a hash output as a fair challenge.
00:05:06gmaxwell:... expect a positive investment (e.g. relative to x% apy or whatever they'd expect in boring market investments).
00:05:06coke0:so cooling won't be a limiting factor
00:05:41gmaxwell:yea, thanks coke0 economic opportunity cost is what I should have said there, as thats more complete.
00:05:55coke0:gmaxwell: exactly, mining has to offer a better sharpe ratio than the S&P
00:06:19bramm:I still haven't seen *any* discussion on what sorts of operations other than memory lookups might require the same power on ASICs as on CPUs
00:06:22tromp_:many people will be happy to mine at a loss
00:06:46bramm:People do mine at a a loss. There are a lot of stupid VCs out there.
00:06:46gmaxwell:tromp_: Expirence in bitcoin suggests this is untrue.
00:06:51tromp_:either with a lottery mindset, or as a buy to obtain coins anonymously
00:06:52zooko:adam3us: yes, that's what I'm claiming is implicity a part of cuckoo's design.
00:07:02gmaxwell:bramm: they do, but not small scale miners intentionally.
00:07:12zooko:And currently the hash spec'ed in cuckoo is SipHash.
00:07:12tromp_:gmaxwell: that's partly because the performance gap is so huge
00:07:25gmaxwell:As I mentioned before there was not a CPU miner to be found back when cpu mining was still objectively profitable (but not very) over power costs for everyone.
00:08:11gmaxwell:And even ignoring cpu miners; people turn off and lay dormant their old bitcoin mining asics that have half the power efficiency, even though there isn't a huge gap in performance.
00:08:15tromp_:if you can install an app on your phone to mine overnight during charging, then you dont care about the cost
00:08:46kanzure:that motivation seems backwards
00:09:12coke0:if you run on your phone, your mobile phone operator is a threat
00:09:21kanzure:whehter or not they care about cost is independent of er.... the thing we were talking about, i think.
00:10:22sipa:tromp_: you may care about the decreased lifetime of the phone (overheating risks, ...)
00:10:33tromp_:let's just wait and see when cuckoo cycle is adopted, how the mining scene develops
00:10:34kanzure:so your goal seems to be something about arbitrarily low performance hardware
00:10:50gmaxwell:tromp_: I thought that too, but people seemed to care. also wrt costs. My initial gpu mining setup was probably about $30k in hardware at peak. Right now that buys as much memory as about 4000 cell phones. I don't know why you think that someone's cell phone mining isn't going to be insignificant compared to people mining industrially.
00:11:45tromp_:it will be insignificant, but ppl will be happy to run it anyway
00:12:04tromp_:if the effort is really limited
00:12:15tromp_:and they can dream of "winning the lottery"
00:12:23Eliel:as long as they think there's a point, some people will do it.
00:12:33Eliel:if it's not too difficult
00:13:19tromp_:botnets will also help decentralize cuckoo (runs and hides:-)
00:13:29kanzure:i can't tell if this would satisfy your goals or not, but it sounds like you might be happy if pool shares paid out for significantly smaller amounts than they are presently configured? this would not require anything about particularly low performance hardware, either.
00:13:33gmaxwell:tromp_: this, again, hasn't been our expirence. I expected these things too, and they haven't happened. Even with cpus. Keep in mind we didn't go from cpus to 20,000 times more efficient asics over night.
00:13:48gmaxwell:tromp_: expirence in some of the altcoins is that the botnets have frequently been used for attacks. :(
00:15:22gmaxwell:kanzure: people don't usually seem to be unhappy about funny money numbers moving in pool accounting systems. The issue is that they're small. I'm sure if my grep my logs I can find some quote along the lines of "You're a moron for cpu mining, it'll cost you $10 a month in power and it'll take you three weeks just to get a single bitcoin!" from around a time when bitcoin was $10 the first time around. :)
00:15:24zooko:Bye for now, folks...
00:15:37tromp_:bye, zooko
00:15:57kanzure:oh that's interesting
00:15:58roidster:roidster is now known as Guest17201
00:16:12kanzure:but this does seem like it's related to pool accounting numbers
00:16:24kanzure:like, any hardware can be used for mining, as long as you're okay with not being profitable or something
00:16:43kanzure:including certain cell phones (well, it might require some clever forethought)
00:16:59tromp_:gmaxwell: back when bitcoin mining moved off cpus, i think smartcoin wallets were very much a rare thing
00:17:02gmaxwell:hehe: people arguing htat botnet operators won't mine. (looking at logs)
00:17:18gmaxwell:todaystomorrow: what do you mean by smartcoin wallets?
00:17:30gmaxwell:er damn complete, sorry todaystomorrow, that was directed at tromp_
00:18:22tromp_:i mean you need the convenience of a one -click install of a sandboxed app to entice a large number of ppl to take up cpu mining
00:18:24Taek:If operating costs (deprication included) are 0, the ROI is unbounded and gets better with time. New entrants can expect a great ROI but only if they stick around for many years. The question becomes "Should I sit on this $1m pile of hardware and make $X or should I sell it for $1m and invest the $1m somewhere else", which effects the incumbants equally to the newcomers.
00:18:27op_null:gmaxwell: botnet mining is interesting because we can assume are rational but also do anything over morality to get the biggest profit. you can say Eligius probably won’t mine forks to get fees other pools already mined, but a botnet owner has a clear motive and opportunity. they probably won’t due to lack of skill, though, the people running them never seem to be the brightest bunch.
00:18:28Taek:if that makes sense
00:19:00phantomcircuit:gmaxwell, people seriously arguing that?
00:19:14sipa:tromp_: in the CPU mining days, it *was* a one click install (the bitcoin GUI program did mining internally)
00:19:26sipa:well, the very early cpu mining days
00:20:10gmaxwell:We actually disabled the default mining in the refernce client because of people who were _very_ angry that their cpu had been pegged for weeks without a result.
00:20:25gmaxwell:phantomcircuit: well tux was, so take that for what its worth.
00:20:48sipa:the magical one?
00:20:48op_null:phantomcircuit: hard to argue that point. people like the Skynet botnet's owner did an AMA and posted a screenshot of their "cloud hashing" console, complete with ponies.
00:20:49tromp_:maybe you should have made it to only run overnight:)
00:21:08sipa:op_null: wait, Skynet?
00:21:25op_null:Le Tor Botnet
00:21:35sipa:i thought it was from a movie
00:22:07op_null:here's their screenshot, they mined at BTCGuild by the looks of things. https://i.imgur.com/Z2eB9GY.png
00:22:15gmaxwell:op_null: 'rantional' is pretty bounded, my expirence with the botnet folks is that like other criminals many of them are morons (non-morons can find better ways to make a living). E.g. the most halarious ones where the ones who would show up in #bitcoin-dev and demand to be taught to setup a pool for their botnet or they'd dos attack you (And then actually send a large dos attack when you punted them). ... thats probably the only ...
00:22:21gmaxwell:... reason I've been happy about all those altcoins with their altpows .... drew off the sleezy botnet people completely.
00:22:22phantomcircuit:gmaxwell, that's weird since there are literally people admitting to doing it as op_null says
00:22:53gmaxwell:phantomcircuit: sure sure, this was back in early 2011 before it was really conspicious. Was looking at old logs.
00:23:04op_null:what was the hashrate in April 2014?
00:23:10op_null:er 2012.
00:23:11kanzure:not just non-morons able to find better ways to earn money, but something about opportunity cost of continuing to look for job opportunities
00:23:25kanzure:(this is partly how you end up with lots of bizarre-good talent in ukraine or something)
00:23:33sipa:op_null: http://bitcoin.sipa.be/speed-ever-large.png
00:23:36phantomcircuit:gmaxwell, there was an argument to be made that it would be too obvious
00:23:55sipa:op_null: wait, remove the '-large'; that one is busted
00:24:11sipa:around 10 TH/s
00:24:33op_null:phantomcircuit: the Skynet guy talked about that. he rigged up the miners so that only the people with the best GPUs mined, and not very hard, and only when the computer was inactive for his timezone. he was very very chatty about it, probably not so much now that he's in jail.
00:24:53phantomcircuit:is he in jail?
00:25:01op_null:yeah, got busted ages ago
00:25:19op_null:December 9 2013
00:25:39gmaxwell:what blockheight do you want to know the hashrate for?
00:26:00op_null:24th APril 2012, same day as the skynet botnet screenshot
00:26:50gmaxwell:itcoin-cli getnetworkhashps 288 177046
00:27:04adam3us:adam3us has left #bitcoin-wizards
00:27:17sipa:heh, i forgot about that RPC
00:28:18op_null:so he was 0.1% of the network with a Botnet. not as big as I was expecting, but 2012 was pretty late for that sort of activity I guess.
00:28:54sipa:in march 2011 there was a fun one
00:29:05sipa:a botnet with probably close to half the hashrate
00:29:20sipa:overnight the hashrate doubled
00:29:36gmaxwell:'mystery miner'
00:29:46sipa:the MM
00:29:56op_null:gmaxwell: yes, there's several comments in the Monero threads about how good it is for botnets. phantomcircuit commented the same about X11. and the whole Dogecoin network storage botnet backs that up too.
00:31:04gmaxwell:network storage botnet?
00:31:39op_null:yeah. somebody made a Dogecoin mining botnet that used an exploit on some brand of NAS. got found out because it slowed them all down.
00:32:39sipa:i was hoping dogecoin had switched to proof-of-storage
00:34:02op_null:if anybody was interested in the Skynet botnet AMA, it's quite interesting just how frank he is about using peoples computers to mine for him. the user is "throwaway236236" http://redd.it/sq7cy
00:35:08op_null:the numbers surprised me the most, $15/1000 infections is quoted. I wouldn't ever have pegged it to be so low.
00:36:24kanzure:that page does not mention skynet
00:38:16op_null:it's the same person though. they also had a very public twitter account where they made the same sort of comments. oddly enough, the last tweet they made is a dead mans switch. https://twitter.com/skynetbnet
00:38:45rasengan:rasengan has left #bitcoin-wizards
00:44:05op_null:that's neat. he screwed up and used a "vest" instead of "west" in a comment, forward a year he is arrested in germany.
00:46:09gmaxwell:"if it weren't for those damn kids"
00:50:20kanzure:so er, should i assume that "better pool share payouts" do not solve the concerns regarding "low performance hardware should still be useful"?
00:50:48gmaxwell:kanzure: I don't think the payouts were ever the limiting factor. I think people have a non-linear utility function for money.
00:51:00gmaxwell:And one which goes negative for small amounts.
00:51:37kanzure:so for someone such as tromp_ (or anyone else bringing up similar concerns, not specifically tromp_), the concern is not only that the hardware has to be cheap, but also the payouts have to be large per chunk of commodity hardware?
00:51:53op_null:for bitcoin in particular the fees aren't related to the value, so small ammounts are less than worthless in a way. you have money but you can't spend it.
00:52:07kanzure:"i have money, but you've never heard of it" i call it hipstercash
00:52:52gmaxwell:tromp_ believes otherwise, I did too previously but could never understand people's behavior. Perhaps what we expierenced in bitcoin previously was a fluke... and people would continue to mine even if the returns were negligible.
00:52:54kanzure:("and also i can't spend it anyway")
00:53:34op_null:well, what amount of bitcoin is work something after the fee?
00:53:59gmaxwell:well any amount if it adds up for long enough in your pool account.
00:54:28kanzure:well, i could see a good argument for "the returns have to be at least enough such that you can withdraw something from the pool", which can be solved y lowering minimum withdrawal fees or polluting the blockchain with sub-satoshi outputs.
00:54:47kanzure:s/minimum withdrawal fees/minimum withdrawal amounts
00:54:53op_null:sub satoshi sort of doesn't work :P
00:55:13gmaxwell:1e-8 btc is a really small amount.
00:55:27kanzure:well presumably these pools are paying out even smaller, per share, right?
00:55:48op_null:oh yeah, it's been under 1 satoshi a share for ages.
00:56:09gmaxwell:well for diff 1 share, but not like they're accepting diff 1 shares normally anymore either.
00:56:19op_null:BTC Guild pays 0.00000000023361 per diff1 share.
00:56:39op_null:that varies though, like gmaxwell says they're not doing PPS
00:56:59kanzure:so why isn't that the solution instead of trying to find a memory hard solution
00:57:37op_null:even with more granularity it's still not worth my time to mine with old hardware.
00:57:47kanzure:the claim wasn't that it would be worth your time
00:58:01kanzure:(with minimum wage laws especially, hehe)
00:59:19kanzure:oh wait, maybe that was the claim
00:59:25kanzure:regarding the overnight-cellphone-charging-and-mining example?
01:00:50gmaxwell:I made the point that even a small performance gap (tromp believes he can get it under 'orders of magnitude' and I'll buy that) means that anything but the most efficient industral miners will be operating at a loss rapidly.
01:01:58gmaxwell:tromp argued than that people would continue to mine at a loss. I pointed out that this is observably untrue in bitcoin; it was untrue when gpu mining was new and displacing cpu mining, it's untrue now relative to different generations of asic hardware. He believes otherwise. I can't argue further because I the behavior in bitcoin surprised me.
01:02:17gmaxwell:And I don't know why people stopped cpu mining even before it was operating at a loss to continue to do so.
01:03:19op_null:it's "profitable" for me to mine Monero. but I don't because the profit doesn't cover the cost of me opening the miner application.
01:03:31gmaxwell:early gpu miners were only about 10x faster than cpus on a 1:1 device count ratio. Though it was more like 25:1 as they got in full swing.
01:04:10gmaxwell:op_null: heh. well w/ monero you have the other issue that the software seems to have been originally written by malicious parties; who think nothing of exploiting the forks.. :(
01:04:38c0rw1n:c0rw1n is now known as c0rw|sleep
01:05:30op_null:I've always run it in a virtual machine and I don't own any particular amount of it. it's unfortunate that the Bytecoin people came up with such a neat idea and tried to scam with it over and over.
01:05:56gmaxwell:but interesting point; we have other 'memory hard' functions even if they're crappy in other respects (slow to verify) ... so you can't just say that the failure of expectations for ltc-scrypt is because ltc-scrypt wasn't memory hard enough.
01:05:56op_null:did you know that most people concluded that all of the forks beside monero are the Bytecoin people's as well?
01:06:13gmaxwell:op_null: I'd heard that.
01:06:40op_null:all of them randomised a key inside the app, except for monero. nobody even knew the key existed, so it's weird that so many forks did.
01:07:32op_null:for Monero pools the hash function is a pretty big hit for them too. most of the pools handle it by not verifying all of the users shares and just assuming they are correct.
01:09:36op_null:admittedly it does seem to run pretty terribly on GPUs no matter what people do with it. so it seems to be the most "GPU hard", but as a result their network is almost certainly a large portion Botnet miners.
01:16:47maaku:maaku is now known as Guest36612
01:17:34Guest36612:Guest36612 is now known as maaku
01:43:16roidster:roidster is now known as Guest4502
01:43:19bramm:tromp_, How well can cuckoo be parallelized on a single machine? I mean, how many memory lookups can you have going at once?
01:44:29op_null:I think you end up memory bandwidth limited
01:44:59bramm:Yeah I wonder if custom hardware could have more memory bandwidth
01:45:22bramm:And whether, say, you have separate memory bandwidth for each CPU or if it's a single aggregate thing. I don't know hardware.
01:45:55phantomcircuit:bramm, memory bandwidth is typically per cpu
01:46:00op_null:for off the shelf CPUs they usually have a limit on your memory bus
01:46:12phantomcircuit:and yes custom hardware could have substantially more memory bandwidth
01:46:34phantomcircuit:since you could balance cpu speed and memory bus bandwidth
01:47:50op_null:for some reason GPUs are actually getting thinner memory busses now, the newer nvidia ones do some sort of compression to try and get around the lack of raw bandwidth.
01:48:12phantomcircuit:op_null, wide memory buses are difficult to get right
01:50:42op_null:yeah. you're not doing that in a breadboard i'm sure.
01:54:43tromp:bramm, i tried with up to 32 threads. i think there's a plot in the paper with speedups
01:55:34tromp:32 threads on opteron was more than enough to saturate the memory subsystem, but on Xeon dual core it's not maxed yet at 43
01:55:45tromp:sorry, at 32
01:56:12op_null:tromp: how fast is cuckoo cycle on a 8 core xeon?
01:56:35op_null:I assume you meant 16 threads on an 8 core xeon.
01:56:48tromp:i measured 1min/GB for 20 threads.
01:57:31tromp:so to use 1GB you prolly need a pretty long block interval alrd
01:58:03op_null:everything else aside, I love the term "tomato" for TMTO
01:58:24tromp:i think that was David Anderson's idea
01:59:23tromp:there are now Xeon's with 18 cores, so dual hyperthreaded cld give 72 threads; wld love to bench those
01:59:45op_null:I'd probably ened to live on the street to buy one of those.
01:59:56tromp:i expect those will max the memory system
02:00:29tromp:wld be nice if siphash was a native instruction...
02:00:52op_null:think you missed out on that one. some of the SHA family will be soon though.
02:01:19tromp:but it seems to be more a matter of supporting dozens of pending memory accesses
02:03:10tromp:i think with native siphash the cpu wld only spend a few % of runtime doing computation, and the rest waiting for mem
02:03:27tromp:now it's 33% computation and 67% waiting
02:04:14phantomcircuit:tromp, is memory access linear or random with cuckoo cycle?
02:04:40tromp:access to the live nonces bits is linear; access to the degree counters is random
02:05:17tromp:also access to the latter should be atomic
02:05:32tromp:in case of running multiple threads
02:06:09tromp:if not, then you risk missing some cycle
02:06:30tromp:(which might be ok as long as risk is small)
03:02:01rusty:gmaxwell: I wish I had discovered https://en.bitcoin.it/wiki/User:Gmaxwell/features#Proofs earlier. It basically describes pettycoin, with a few differences.
03:02:57rusty:gmaxwell: I use a lottery system for Proof of false inflation . Pick random tx, take fee, multiply by number of txs, that's the reward.
03:03:17rusty:gmaxwell: your solution is more elegant.
03:43:35Taek:gmaxwell, wrt using libsecp256k1, I thought of a solution which might allow you to use multiple paths without sacrificing a factor of N slowdown.
03:44:43Taek:you verify each signature with randomly selected blocks of code, but only once
03:45:04Taek:if your conclusion matches the conclusion followed by the heaviest fork, you don't verify again and just accept it
03:46:00Taek:if you get a confliction solution (meaning something didn't verify but the heaviest fork suggests that it was verified), you check using multiple paths or perhaps a completely different library
03:46:09Taek:your slowdown is only when you don't verify something that should be verified
03:46:23Taek:the risk is that you verify something that shouldn't be verified
03:47:05Taek:but since everyone is using random code paths, only some people (with enough potential paths, very very few people) will accept the transaction
03:47:40Taek:and so some people will fork unintentionally because they confirm something that shouldn't be confirmed, the majority of mining power will not accept the invalid signature, and the heaviest fork will remain pure
03:48:41Taek:I would argue that having multiple implementations to switch between randomly when verification is a lot stronger for the network than just having one.
03:49:37Taek:because when most everyone uses the same library, a single mistake can cause a big fork. But if everyone is using dozens of implementations, to get a fork you have to find a signature that causes errors in the majority of the implementations
03:50:05Taek:s/when verification/when verifying
04:56:32kanzure:is there a better lamport paper than http://diyhpl.us/~bryan/papers2/bitcoin/Time,%20clocks,%20and%20the%20ordering%20of%20events%20in%20a%20distributed%20system%20-%20Lamport.pdf to be using
06:28:07lclc_bnc:lclc_bnc is now known as lclc
08:48:39gmaxwell:rusty: there are some writeups on that stuff elsewhere on this too, it's a kind of notion that is in a kind of unfortunate valley where its merely engineering work and not interesting to the academics, but big enough engineering work that it doesn't have super short term impact on bitcoin.
09:05:17asimov.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:17asimov.freenode.net:Users on #bitcoin-wizards: andy-logbot cbeams AaronvanW damethos adam3us rusty gues JonTitor ryanxcharles llllllllll devrandom RoboTedd_ tdlfbx Aquent Shiftos TheSeven coiner jb55 ebfull samson_ wallet42 coke0_ eristisk Dr-G2 prodatalab maaku op_null phantomcircuit Graftec nuke1989 sl01 mkarrer Starduster_ grandmaster Qfwfq Cory koshii luny Grishnakh shesek sipa spinza mortale DoctorBTC c0rw|sleep Flyer33 OneFixt zwischenzug Alanius epscy jbenet HM dansmith_btc dgenr8
09:05:17asimov.freenode.net:Users on #bitcoin-wizards: artifexd hguux_ michagogo btc__ Nekokamisama mappum Muis copumpkin HaltingState adlai bosma azariah4 nanotube waxwing Hunger- orw MRL-Relay fluffypony PRab tromp berndj jgarzik PaulCapestany K1773R BlueMatt a5m0 Pan0ram1x kgk sneak LaptopZZ SubCreative Luke-Jr Emcy LarsLarsen Baz___ gazab Guest39111 po1son3r123 SomeoneWeird AdrianG iddo jaekwon_ yoleaux xabbix heath gwillen livegnik prepost BananaLotus d4de Myagui @ChanServ bitname btcdrak
09:05:17asimov.freenode.net:Users on #bitcoin-wizards: burcin coutts wizkid057 arowser Nightwolf paperbot Dyaheon bbrittain NikolaiToryzin forrestv null_radix nickler bobke_ warptangent mr_burdell Logicwax zibbo Meeh kanzure tromp_ Krellan poggy pi07r_ comboy_ mmozeiko lnovy Taek optimator_ [\\\] Apocalyptic throughnothing petertodd crescendo CryptOprah cfields Fistful_of_Coins gmaxwell kinlo ahmed_ so Anduck lclc [d__d] gnusha_ espes___ BigBitz otoburb wumpus EasyAt starsoccer hollandais fenn
09:05:17asimov.freenode.net:Users on #bitcoin-wizards: jaromil helo Keefe Iriez Eliel jrayhawk huseby phedny midnightmagic nsh coryfields andytoshi BrainOverfl0w fds4345 warren asoltys gribble Graet smooth amiller danneu catcow TD-Linux [Tristan] ryan-c roasbeef harrow abc56889 lechuga_ pigeons
09:33:12rusty:gmaxwell: One difference between your suggestions and mine which I'd be interested in your thoughts. I hashed with each transaction an array of backrefs (ie. blocks ago, transaction number), to allow proving an unknown input. That seems simpler than trees of UTXOs + produced + consumed outputs.
09:34:51gmaxwell:rusty: then you cannot spend an unconfirmed transaction? The design of bitcoin strongly decouples the transactions themselves from the chain; the chain just provides ordering, the txn themselves exist freestanding and can be validated independantly of the chain.
09:35:08rusty:gmaxwell: blocksago == 0, though my implementation didn't do that.
09:35:50gmaxwell:I mean, say you author a transaction spend ago 0 but then the unconfirmed confirms, but the spend hasn't yet.
09:36:36gmaxwell:or the chain reorgs harmlessly, have you now invalidated transactions and require signers to come back out of their valults to resign?
09:36:58rusty:gmaxwell: no, backrefs are inserted by miners, not part of transactions.
09:37:20rusty:gmaxwell: they're simply extra metadata.
09:37:24gmaxwell:oh, if it's not part of transactions then it's probably isomorphic.
09:38:08gmaxwell:upto perhaps some efficiency differences. Commited state is something we've long wanted more of because it's useful for many other things, not just incremental validation... so that probably colors my assumptions.
09:38:48gmaxwell:hm. actually if its just backrefs how do you incrementally discover a double spend?
09:39:31gmaxwell:e.g. tx10 spends coin A. You can form a backref to tx1 creating it... but really in the middle tx5 already spent that coin.
09:40:29rusty:gmaxwell: it doesn't detect ds by itself, no
09:41:02gmaxwell:Oh well with state commitments you can detect the double spends without there existing any full nodes.
09:41:41rusty:gmaxwell: since the network is divided into shards, and the txs are ordered (such that same shard txs are adjacent), you'll detect ds anyway.
09:42:23rusty:gmaxwell: yes, in your scheme even miners don't need to be full nodes. That's pretty sweet.
09:44:51gmaxwell:Are you making an additional assumption there. E.g. that there exists some node X who isn't me, who will check all of Y or my probablity of detection of a doublespend in Y is zero. (not sure if thats materially worse that 'my probablity of detecting is at least $small, even if I am almost alone in being honest'; different in any case)
09:48:49comboy_:comboy_ is now known as comboy
09:51:18rusty:gmaxwell: sorry, was distracted.
09:52:34rusty:gmaxwell: assumption is that every node has full knowledge of at least 2 shards, so probability should be low.
09:53:04rusty:gmaxwell: Simplified txs only allow inputs and outputs to cross two shards, which helps.
09:54:45rusty:gmaxwell: it's trivially easy to tell if you know all txs out of your shard (due to tx ordering in block), txs in are best-effort.
09:55:27gmaxwell:okay, too tired to think about the implications of that, its a very different design.
09:56:03gmaxwell:I'm not sure what it gains over a design with a common merkelized state. May be more obvious to me in the morning.
09:56:24rusty:gmaxwell: yeah, I had to bend things pretty badly to make it work :(. That's why I'm coming around to your scheme.
09:57:31rusty:gmaxwell: oh, and in practice the tx+amount hashtree will probably have to be in addition to the normal tx hashtree, assuming sidechains have to look bitcoin-like for tx proofs.
09:58:03gmaxwell:well sidechains only should have to look bitcoin like enough for the recovery txn, the other parts could be fairly different.
09:58:50gmaxwell:Here is a fun additional thought that I hadn't had back when that text was written. Imagine you are a thin client, and there are several full nodes claiming different things about the validity of a given block. Also imagine that the bitcoin blockchain and its commitments is unchanged as it is now.
09:59:55gmaxwell:It's actually possible for our hapless litenode to figure figure out the truth if at least one of their peers is telling the truth with only O(log()) queries.
10:00:31phantomcircuit:i think you accidentally n
10:01:28gmaxwell:if I'm truncated tell me where.
10:02:03rusty:gmaxwell: well, AFAICT an honest node can disprove any spurious claim (eg. "that input never existed!", which is the hard one).
10:02:16gmaxwell:The notion is that the peers keep merkelized transcripts of their validation progress along the chain (e.g. all the data they looked up and what its results were, etc). If no one is faulty, the hashes will agree (process is determinstic). If the hashes don't agree then you can do a log() operations search against a pair of peers to find the point where they diverge. Then check to see which of them follows the rules.
10:02:19phantomcircuit:har har
10:03:39gmaxwell:rusty: at the time I'd written that text I'd assumed it was impossible to efficiently prove, e.g. "the subsidy paid out in this block is correct". with the current blockchain structure... not without giving the peer all the transactions being spent (which can be a _lot_ of data)
10:04:23gmaxwell:and thats so, in a non-interactive context, unless there are additional commitments as the proofs page talks about... but in the interactive context there don't even need to be blockchain data changes.. which is interesting at least.
10:05:26rusty:gmaxwell: I see, but this still assumes a full peer exists. If the miner is the only one who knows the entire block, you still need your enhancements as no one can call her on it. I preferred the original "no full nodes" premise: more ambitious :)
10:06:50gmaxwell:yea sure sure. Just an additional thought. The more complete vision is more interesting.
10:07:28gmaxwell:But the technique used for the interactive thing could be used to provide all kinds of interesting summaries of blockchain data, that you might not want general nodes being responsible for maintaining, and thats kind of neat too.
10:07:57gmaxwell:(just thought I'd mention it because it was the sort of thing I wish I'd realized earlier.)
10:33:36Shiftos_:Shiftos_ is now known as Shiftos
10:42:56c0rw|sleep:c0rw|sleep is now known as c0rw1n
10:47:22cfields:cfields is now known as cfields-away
11:43:04c0rw1n_:c0rw1n_ is now known as c0rw1n
14:08:38kanzure_:kanzure_ is now known as kanzure
15:55:56Myagui:Myagui is now known as Iocohammerhead
15:56:27Iocohammerhead:Iocohammerhead is now known as Myagui
16:04:43c0rw1n:c0rw1n is now known as c0rw|away
18:10:55bramm:Hey everybody
18:14:13bramm:I have a thought on how cuckoo's hashes could possibly be made smaller
18:19:56bramm:You know, there's nothing in the side chains spec which actually requires that pegging be done to a crypto currency. All it says is that a certain amount of work is necessary to bring the thing back.
18:35:26lclc:lclc is now known as lclc_bnc
18:45:45Eliel:bramm: if you mean cuckoo's PoW data structure can be made smaller, I'm all ears.
18:46:34bramm:Eliel, I mean I think it's possible to make a very similar problem with similar properties where the actual proof is smaller
18:47:04bramm:Not sure if that's the possibility which piqued your interest, but I'm happy to explain my idea regardless
18:48:49Eliel:if it's less data and is similar enough to be functionally identical, yes, I'm interested
18:50:58tromp_:hi Bram
18:51:22bramm:Hmm, I think my idea for a dramatic reduction in size is a fail, but I can get roughly a factor of 2
18:51:22tromp_:did you finish reading the whitepaper?
18:51:38bramm:tromp_, I think I've read the whole thing now, not contiguously though
18:51:47tromp_:all clear now?
18:52:04bramm:I think so. I have an idea I'd like to suggest though
18:53:20bramm:With cuckoo as you've defined it the way edges are derived is by going nonce -> (a, b)
18:54:08tromp_:yes, with 2 separate hashes
18:54:56bramm:Maybe edges could be defined by going a -> b, which defines an edge between a and b, so that in the PoW itself b can be skipped over if the a->b edge is defined by a.
18:56:03tromp_:how do you get a then?
18:56:25tromp_:you mean nonce->a->b ?
18:56:41adam3us1:adam3us1 has left #bitcoin-wizards
18:56:59bramm:Oh, the very first spot in the cycle has to be specified, then the later ones are either said to be the edge defined by a, or b is given
18:57:33bramm:So on average you'll only have half as many things
18:57:35tromp_:the proof is 42 nonces
18:57:58tromp_:that's unavoidable
18:58:04bramm:Yeah I'm suggesting it could be 24 nodes
18:58:32tromp_:you mean 21?
18:58:44bramm:Yeah, 21. And an average of 21
18:58:59tromp_:then you dont know what nonces link them up
18:59:26bramm:What you do when generating the edges is for each node you flip a coin and if it comes up heads you find another edge to connect it to and if it comes up tails you skip it
19:00:02bramm:So each edge can be specified by a node, and there are on average as many edges as there were before.
19:00:43bramm:So then when I want to specify a cycle I give the first node, then say either than the next node is the one defined by the first node or something else. If it's something else I specify it, if it isn't then I get to skip one
19:01:23tromp_:that's a different random graph model, with a variable number of edges
19:01:52bramm:In the sizes we're talking about the number of edges will be almost identical for statistical reasons
19:02:16bramm:You can make it bipartite easily enough. The coin toss even gives you something to do with that extra bit.
19:02:22tromp_:yeah, with expected roughly O(sqrt(N)) swings
19:02:51bramm:Yes, when you're talking 2^32 edges the 2^16 standard deviation is no big deal
19:03:34tromp_:but you may have problems getting the other parts to work. for instance, i now need only N/2 bits for tracking live nonces
19:04:12tromp_:with your approach, how wld i iterate over a sparse subset of live edges?
19:04:45tromp_:seems you'd need to keep N bits for the generating nodes
19:04:53bramm:It isn't very sparse, it's half, it's probably fastest to use N bits and have half of them be marked as dead from the get-go because they lost the coin toss
19:05:23bramm:I assume that the graph has N total nodes, even though it's bipartite
19:06:21bramm:I've effectively made nodes also be nonces. Maybe that speeds things up a bit, but it's like a factor of 2 reduction in memory usage for a factor of 2 reduction in size of proof, which seems well worth it
19:06:47tromp_:it starts dense, and gets sparser after every trimming rouind
19:07:30tromp_:no, you've doubled mem use
19:07:51bramm:Doubling memory usage isn't a bad thing
19:08:02tromp_:it's pretty bad in my view
19:08:24bramm:Why? It's a proof of work, it's supposed to require lots of memory
19:08:29tromp_:when having to defend against tmtos
19:08:50tromp_:you want to make it very costly to run the pow with less than intended memory
19:09:34bramm:I'm not sure this enables any new tmtos
19:09:44tromp_:your scheme using N bits to track live edges is more likely to have some alternate implementation using less than N bits
19:10:31tromp_:let me think if other parts of my algorithm are affected...
19:10:58bramm:Okay, wanted to suggest it because the proofs are kinda big
19:11:18tromp_:big but manageable
19:11:44tromp_:header goes from 80 to 248 bytes
19:11:46lclc_bnc:lclc_bnc is now known as lclc
19:11:57bramm:Yeah but big enough that it would be nice to knock them down
19:12:09tromp_:you could lower cycle length to 20
19:12:34bramm:Yes that's another shortening trick, also a complementary one
19:13:18tromp_:i the grans scheme of things, a factor 3 increase in header size is not a very big deal
19:13:23tromp_:in the grand...
19:13:27bramm:My really crazy idea is to make the graph a directed one and the cycle much go with the flow of edges. That probably has time memory tradeoffs though
19:13:58bramm:It depends what you're using it for. There might be places which use a lot more of such things
19:14:57tromp_:your approach also makes the tmto more effective
19:15:32bramm:I don't really understand the tmto
19:15:58tromp_:it's breadth first search from a node subset
19:16:52bramm:Oh, yeah, you can skip over some lookups from nonces to nodes. That might help the basic algorithm an equivalent amount though.
19:17:09tromp_:for really small subsets it uses less memory than the reference algorithm
19:17:23tromp_:with your approach, it pretty much works as before
19:17:56tromp_:but since you doubled the live edge memory usage in the reference...
19:18:44tromp_:you reduced the effective slowdown of the tmto
19:20:38tromp_:hmm, wait
19:20:49tromp_:there's another problem with your approach
19:21:17tromp_:it doesn't work at all:(
19:21:38tromp_:it can be solved with no memory
19:22:53bramm:How so?
19:23:24tromp_:hint: your proofs can be reduced to a single node:)
19:23:50bramm:Oh, yes, my extreme approach has that problem, I realized that, hence my comment about it having tmto
19:24:19tromp_:what extreme approach?
19:24:39bramm:The one where the entire graph is made directed and you have to go only in the positive direction of edges
19:25:04bramm:In the less extreme one you can't go to a single node because about half the graph edges will point backwards
19:25:09tromp_:your approach implies extremism
19:26:09tromp_:you cannot have a cycle where edge are not all generated in the same direction
19:27:41bramm:Let's say we're looking for a 4-cycle. It will go A->B->C->D->A. If we start our proof with A, then *maybe* the A->B edge will be generated by A, but half the time it will be generated by B, in which case we have to give B
19:28:09tromp_:it will always be generated by all nodes in the cycle
19:28:39bramm:If it is, say A->B<-C<-D... oh crap
19:28:45tromp_:crap indeed:)
19:28:49bramm:it can't reconnect at the other side
19:30:13bramm:Well that should be fixable, just have to make it so nodes can sometimes have more than one outgoing
19:30:36bramm:Say, make them have a 1/4 chance of two outgoing connections
19:31:22tromp_:i dont like adding complications that might just make the failure mode harder to notice:(
19:32:09tromp_:maybe you could implement your approach and check that at least the cycle distribution length is presered?
19:32:30bramm:This is mutating into a rather different animal in my brain and might have to be analyzed from scratch
19:33:04tromp_:also, you risk further inflating the live edge storage size
19:37:51bramm:Here's another unrelated though, where I'm not sure what the consequences are:
19:38:19bramm:How about instead of a nonce specifying a single edge, it specifies a clique of nodes which are all connected to each other?
19:39:16tromp_:that's a rather ugly complication:(
19:39:54bramm:It is, but maybe you could have a shorter proof of work in exchange for it taking a bit more work to verify
19:40:59tromp_:but you give up more security in having a complex algorithm, then by just shortening cycle length?@
19:41:24bramm:I'm not sure what the disadvantages of shortening the cycle length are exactly
19:41:55tromp_:the tmto's have less relative slowdown on shorter cycles
19:42:33bramm:Would using clique edges make the tmto have to do more work on a shorter cycle?
19:42:34tromp_:but might still be ok at length 8
19:43:26tromp_:the problem is that it becomes harder to see what tmto approaches are possible
19:44:05tromp_:that's why i want the underlying problem to be as simple as possible
19:44:12tromp_:just find cycles in rnd graphs
19:44:20bramm:Yeah I get that the big fear is of possible cleverness
19:44:33tromp_:that shld leave as little room as possible for funky algorithms
19:44:55bramm:It's interesting how one of the virtues of cuckoo is its easiness, that allows it to require lots of memory for the amount of work done
19:45:09bramm:Things which aren't roughly linear wind up requiring a lot less memory
19:46:45tromp_:maybe you shld further develop your 4sum idea and see how it compares with cuckoo
19:48:07bramm:Yes it might be a good idea to actually implement it
19:48:15tromp_:th major downsides of cuckoo are
19:48:18tromp_:1) big proofs
19:48:37tromp_:2) very slow at using >=1GB of memory
19:48:44gmaxwell:bramm: "All it says is that a ertain amount of work is necessary to bring the thing back" ... actually, no, it says that a signature must be provided; and goes through and presents a generalized concept of signature systems to prevent 'work' as a kind of anonymous threshold signature. And sure, it's more general that crypto currency, intentionally so.
19:48:59zooko:tromp: why very slow at using ≥ 1GB of memory?
19:49:47tromp_:it takes 1min/attempt even on a 20threaded Xeon
19:50:40bramm:gmaxwell, I'm not sure what sorts of escrow schemes for the necessary signature you guys might have in mind, a coin seems to not be very handed off if the key is still quarreled away somewhere
19:51:15bramm:squirreled, not quarreled
19:51:57tromp_:let's not quarrel over squirrels
19:51:59bramm:I just turned off spelling correction. Man that was annoying
19:52:04gmaxwell:bramm: There are signature systems which have no private key data. Blockchain proof of work is one, another is zero knoweldge signatures of knoweldge. (e.g. the SCIPR lab work).
19:54:17bramm:gmaxwell, How general can the thing to release a coin be made to be? I understand conceptually how it being based on a proof of work could be used
19:56:13Sub|afk:Sub|afk is now known as SubCreative
19:57:44bramm:tromp_, going with 4sum is basically giving up on making the difficulty of the work be based on speed of random access and going with it being based on bus speeds
19:57:47gmaxwell:The pegged sidechain paper talks about how to make a release for a proof of work systems. The 2wp was originally decribed by me far more generally (in the context of a ZK SOK) which would let the release be any machine decidable statement. https://bitcointalk.org/index.php?topic=277389.0 (but it requires tools which are not mature, so that fully general view isn't something thats likely to be implemented in the super near term). At ...
19:57:53gmaxwell:... least what I'm planning on working on now is limited to POW-signatures with basic constraints, and classical knoweldge of discrete log signatures, and combinations of them.
19:58:21bramm:Which might actually be an improvement because maybe you can require a lot more memory that way. But it also might be very hard for the CPU to outperform memory bus.
19:59:02bramm:gmaxwell, So this isn't implemented yet?
20:00:41bramm:Anybody know if CPUs can outperform memory buses?
20:01:05tromp_:bramm: you need to phrase the problem in such a way that sorting is not the best way to solve it
20:01:17gmaxwell:bramm: none of the more general stuff is yet, none of the sidechains stuff is ready for wide deployment yet.
20:03:17bramm:tromp_, I've tried!
20:03:34tromp_:perhaps the 4sum shld be exactly 0, and you pose an additional constraint on hash(a|b|c|d) to meet a diff target
20:03:35bramm:Sorting does in fact require a fair amount of memory
20:04:07tromp_:then it starts looking like momentum though
20:04:39bramm:momentum is just a collision isn't it?
20:04:59bramm:4sum is a clever way of reducing the CPU needed for 2sum, but it isn't that big an improvement
20:06:14bramm:I suspect hardware can do a great job of sorting
20:08:58tromp_:btw, bramm, you wouldn't know any1 with spare supercomputing capactity, would you?
20:10:43bramm:tromp_, Depends on whether it's spare supercomputing capacity which they're actually willing to use
20:20:51bramm:The problem with finding things which require random access lookups is that there are lots of ways of leveraging sorting very effectively
20:21:20bramm:So you have to come up with a problem which somehow forces actual random accesses rather than repeated sorts
20:22:08tromp_:it's hard to imagine sorting being effective at finding cycles
20:22:45bramm:If you're looking for a cycle of length N you can do it with N sorts
20:23:16bramm:Which might require more memory but fewer random accesses
20:25:51bramm:Really using memory and doing random accesses are two different kinds of work
20:31:05tromp_:most memory oriented pows try to force random access by pointer/index hopping with indices generated from hash outputs
20:31:23adam3us:bramm: gmaxwell means the zk snark / scip based proofs are not implemented into a peg system, and indeed their crypto properties are sufficiently new and there scalability vs program complexity poor enough that its not clear if you would want to rely on it right now or if it would complete useful fast even with a lot of GPU/FPGA power thrown at it.
20:31:33tromp_:like scrypt, memorycoin, cryptoknight...
20:31:48jrayhawk:jrayhawk has left #bitcoin-wizards
20:32:08bramm:tromp_, Yes I came up with a version of that which I think is better, the problem is that it's expensive to validate
20:32:11adam3us:bramm: but if you want something fun to bend your mind read about SNARKs… the things you can do with them are the signature analog of FHE, except that they actually work and kind of scale where as FHE basically doesnt practically
20:32:31tromp_:but cuckoo has random access to tiny 2-bit blocks, which is a different ballgame
20:32:47bramm:Yeah I remember snarks being supercool it's one of those things I have trouble holding in my brain though
20:33:00bramm:I tend to work with boring simple primitives
20:34:03tromp_:bramm: memory coin has much cheaper validation, since they search many starting points for one that satisfies some property
20:34:30tromp_:but still far from instant verification
20:34:51bramm:tromp_, Is that something besides the obvious tradeoff that you can have faster validation for less work to do them?
20:36:21tromp_:they have N blocks/starting points, and M-hop paths, so memory use is O(N) and verification is O(M)
20:36:48bramm:I don't follow
20:37:45c0rw|away:c0rw|away is now known as c0rw1n
20:38:55tromp_:they look for some 0<= i < N such that the path of length M starting at block i satisfies some constraint
20:39:46tromp_:the verifier doesn't have to compute all N blcoks
20:40:40tromp_:nothing interesting there:(
20:41:31c0rw1n:c0rw1n is now known as c0rw|timetravel
20:44:09Dizzle__:Dizzle__ is now known as Dizzle
20:48:11c0rw|timetravel:c0rw|timetravel is now known as c0rw1n
20:50:13lclc:lclc is now known as lclc_bnc
21:05:08bramm:tromp_, Here's a thought on requiring lots of memory accesses:
21:05:10rusty2:rusty2 has left #bitcoin-wizards
21:05:40bramm:First, you make a list of pseudorandom numbers, by hashing values
21:06:06bramm:Then, you need to find two which are within some small delta of each other, delta being set that on average each one is within that amount of one other value
21:06:59bramm:those two values are then hashed, so they need to be within a similar delta of a third value, which then gets hashed to find a fourth, etc. for some number of hops
21:08:15bramm:The problem is you can attack this by sorting
21:08:40bramm:It does of course structurally resemble cuckoo quite a bit
21:09:32adam3us:btw is there an application of cuckoo cycle in this topic? something specific?
21:10:50samson2:samson2 is now known as samson_
21:12:36bramm:adam3us, Presumably proofs of work in a crypto currency
21:12:42tromp_:i'm not aware of cuckoo being applied anywhere yet
21:14:13tromp_:in the past, the author of http://twister.net.co expressed interest in using it
21:14:14adam3us:bramm: the interesting topic from yesterday is whether when the asic version is made the higher ratio of hw cost vs electrical cost makes that more or less decentralised.
21:15:48bramm:adam3us, That is an interesting question. Ideally the parameters are set so that with or without ASICs a miner's hardware costs are completely dominated by DRAM
21:16:43tromp_:the asic will not be made unless it's sufficiently cheaper than any fpga that can saturate the memory interface, to cover its development and fabrication costs
21:17:18adam3us:bramm, tromp: its generally a truism that hw wins, and that hw hackers are more creative and have more tricks than sw people appreciate.
21:18:58zooko:Is "truism" a word for a thing that may or may not be true?
21:19:00adam3us:i am not a silicon optimization expert but for example different types of memory can have better electrical efficiency, density, cost , latency, reliability. so for example what about a ram that can only keep contents for a short period of time
21:19:05tromp_:adam3us: can you give examples of ASIC that needed to be hooked up to multiple DRAM chips?
21:20:01bramm:I wouldn't mind making proofs of work where the result of investing in hardware for them was to make better memory
21:20:13bramm:That would actually have some societal value
21:20:43tromp_:adam3us: unless there is a huge market for such memory chips, they wont be maufactured with the huge econmomies of scale that regular dram is
21:21:14adam3us:bramm: PoWs end up being optimized for their purpose. eg having high unreliability, many millions of times worse than what a CPU could tolerate.
21:22:37bramm:adam3us, Yeah but memory is rather different than CPU. It's much more fundamentally commodity in its functionality. It is of course true that you might be able to make faster memory by making it less reliable
21:22:56tromp_:maybe cuckoo miners would buy up DRAM chips that are faulty (one or more unfixable bad bits) but still useful for cuckoo
21:23:38bramm:tromp_, I would be fine with that, makes memory cheaper for everybody else
21:24:04tromp_:if the bad bit makes gives only 1% false positives, or false negatives but costs a fraction of a flawless chip then that's a great tradeoff
21:24:55tromp_:i dont know what currently happens with faulty dram chips
21:25:27adam3us:tromp: or maybe if the memory is lost after a few seconds? how long do you need it for a cycle to be evaluated with your parameters to be generally "good enough" no-progress
21:26:06tromp_:one cuckoo attemps takes from seconds to let's say 1 minute
21:26:22adam3us:tromp: dont they have like self-test & fuses & a small amount of extra capcity so they can route around bad segments? (not sure)
21:26:53tromp_:yes, i talk about those that exhaust their self-repairing capacity
21:27:36tromp_:which should only be a tiny fraction of a manufacturing run
21:27:47adam3us:tromp: also arent the cache & line sizes & pre-fetch circuitry & pipelining etc all a waste of time for this intentionally random access purpose? wonder how much of the effort in a ram chip goes into that?
21:28:12tromp_:adam3us the waste is in the usual width of 32 or 64 bits
21:28:16bramm:adam3us, It isn't quite so random access as all that, forcing random accesses is difficult
21:28:31tromp_:adam3us a cuckoo optimzed chip would have width 2
21:28:35bramm:tromp_, How is the width a problem? It isn't too hard to pull down 32 bits and look at 2
21:28:55tromp_:bramm: it inflates the power usage of the chip
21:29:46zooko:adam3us: it seems possible that custom hardware could do cuckoo 2X or maybe 10X more efficiently than commodity, but it seems unlikely to me that it would be 10,000X more efficient.
21:29:56tromp_:a cuckoo mining rig would avoid caching alltogether
21:31:33tromp_:i think it will be hard to be 5x more efficient than an fpga hooked up to bare memory dies
21:32:35tromp_:in terms of throughput per watt
21:33:23tromp_:so less than 1 order of magnitude for a semi commodity solution
21:33:47op_null:tromp_: high speed stuff is hard though. as soon as you get off the die you need to be designing your boards very well. the nice thing about Bitcoin ASIC chips is tha you just squirt in power, hook up your SPI and it's done.
21:34:02tromp_:but take that with a grain of salt as i'm far from an expert on this
21:35:05op_null:if your FPGA is in a BGA package you need a many layered board to route out all of the IO you need.
21:35:27op_null:gets uncomfortably complex quite quickly
21:35:57adam3us:tromp: i imagine you defended against it, but one of the surprises that bit momentum hash (basically a partial birthday hash) was that unreliable but smaller memory could be built in sw using a bloom filter. (bytemaster reluctantly paid out $5k bounty for that break and a few other tmto observatiosn)
21:36:53tromp_:adam3us: please read the tmto section in my latest paper. i believe those are way more effective than bloom filters
21:37:06adam3us:tromp, op_null: if you're heading towards maybe an order of magnitude but complex and high NRE, then that risks centralisation if one company gets there with vertical integration intentions.
21:38:19adam3us:tromp: and given the commodity economics where difficulty converges to break even, one order of magnitude might be enough incentive at high bitcoin prices.
21:40:29bramm:On the flip side, the bitcoin-ninja faq claims that the resource which proofs of work should be based on is power, but I still have yet to hear anyone venture any opinion at all on what operations are hard to power optimize on asics
21:42:36adam3us:bramm: there seems to be an economy of scale of sorts from access to multi KW power where residential power is expensive per kWh or hard to get a supply over some 24kW or something. iff the economics worked out for a hw purchase dominated mining that might be a useful defence against power distribution inequality
21:42:49tromp_:adam3us: it might well be enough, but the gap with desktops will be much narrowed
21:43:43bramm:Oh yeah, residential vs. commercial power differences are a real killer
21:43:54tromp_:allowing people with spare cloud computing power to convert to some coins
21:44:01tromp_:even if at a loss
21:44:11bramm:Ideally proofs of work would primarily be based on the hardware people have already bought which is already sitting around depreciating
21:45:51op_null:miners don't depreciate unless the difficulty is rising though.
21:46:39bramm:Miners will depreciate along with all other hardware
21:47:30adam3us:op_null: difficulty will tend to rise by people buying equipment until breakeven.
21:47:52adam3us:op_null: even if hw is not improving faster than memory architecture latency.
21:48:09op_null:why? they don't wear out. their caps will dry out and the bearings in the fans will wear though, but not in any small timespan.
21:49:18bramm:Memory architecture latency is still improving quickly
21:49:26op_null:this ,,diffchange looks like it'll be a decrease too.
21:49:41adam3us:op_null: i guess eventually obsoleted in terms of which equipment to buy by preference by new equipment. however as the capital is already a sunk cost, and we're supposing electrical cost is negligible there is limited reason to switch old equipment off, just add more.
21:50:07op_null:ok that command doesn't work here. the estimate for the difficulty this period is -3.5% anyway.
21:50:33op_null:adam3us: right, I was talking Bitcoin hardware not Cuckoo cycle hardware.
21:56:09adam3us:tromp, bramm, op_null: if it is hw cost dominated, doesnt that hand a perpetual advantage to those who get in there first and get better cost amortizing by mining more equipment longer?
21:56:17Dizzle__:Dizzle__ is now known as Dizzle
21:57:04bramm:If it's *commodity* cost dominated, then most mining will be done by the many machines which are already sitting around doing nothing
21:57:37adam3us:conversely with bitcoin if you made bitcoins by mining earlier before price went up or when mining was further from break even, you have bitcoins, not large mining capacity to dominate the network because bitcoin equipment falls below electrical break even fairly quickly.
21:58:05adam3us:bramm: ie botnets?
21:59:47instagibbs:if ASICs get shoved in random Internet of Things stuff I'm sure ASIC botnets will take off too
22:00:08instagibbs:if it stays in hobbyist/expert prob not
22:00:26tromp_:adam3us: those who get in there first are those who already have hardware with cycles to spare
22:01:05bramm:adam3us, or people with legal botnets, or ordinary end users
22:01:29tromp_:yes, botnets too.
22:01:54tromp_:but at some risk to botnet operators, since a memory-intensive pow may trigger swap hell
22:02:36tromp_:unlike compute intensive pows, which can be run at lower intensity to "fly under the radar"
22:05:45instagibbs:For botnets(in general) what is the most precious resource? Obviously depends on application, but was wondering if there are opportunity costs CPU-wise. CPU mining bitcoin could possibly be just so bad they'll spend cycles on something else
22:06:32adam3us:instagibbs: i think the asic advantage is so steep that even botnets fell below rental cost breakeven or the opportunity cost of spamming or phishing or whatever the deal is these days.
22:07:10instagibbs:that's my intuition, but no evidence. Maybe figure out what botnets today are up to
22:07:40instagibbs:regardless it's a tiny slice if it even exists
22:07:45tromp_:botnets might run cryptoknight or X11 pow which are only moderately slower than GPUs
22:08:09adam3us:some bots even have gpus
22:08:25instagibbs:until my ASIC waterheater gets pwned and contributes to a botnet
22:08:44tromp_:oops, it's called CryptoNight https://en.bitcoin.it/wiki/CryptoNight, the Monero Pow
22:10:14sipa:oh wow i never got the reference to kryptonite
22:12:43tromp_:it's call very confusing, CryptoNight is the PoW of the CryptoNote technology, and there is also an unrelated altcoin called http://cryptonite.info/
22:13:11instagibbs:brb starting CryptoKnight, sounds cooler
22:14:41tromp_:you're starting an altcoin called CryptoKnight with a pow called KryptoNight?
22:15:38instagibbs:haven't planned far enough ahead, working on my logo
22:15:59adam3us:where's coingen when you need it :)
22:23:34op_null:tromp_: I like the CryptoNite (altcoin) PoW "M7". multiplying 7 weird hashes together for "security"
22:24:12instagibbs:that "technique" has been around a while
22:25:28tromp_:it's funny how these hash-mashers usually advertise their concoctions as "super-secure"
22:26:08op_null:"we survive if sha256 is broken!" (but we still use it for transaction hashes just nobody point that out please)
22:26:13instagibbs:well if you think somehow 5 hashes are going to get cracked simultaneously, adding a couple more seems smart
22:26:47op_null:they only change it in the PoW though. not in the millions of other places it's used in Bitcoin.
22:27:04bramm:The purpose of smashing together a bunch of proofs of work is to take up space on the asic
22:27:15adam3us:so i think one useful observation from paul sztorc is that whatever the scheme (PoS, PoW) the same resources will be poured into obtaining the coins, so you'd just as well use simple, predictable and equitable one - ie simple-PoW.
22:27:24op_null:yeah. the X11 stuff got absolutely owned by FPGA farms.
22:27:28gmaxwell:well it's the same superficial design shedpainting. The POW stuff is farily unimportant in the design, but for some reason it's one of the technical things that new and semitechnical people cling to first, have lots of opinions on.. etc. even though its one of the least interesting parts of the system.
22:27:33bramm:But since they can be pipelined in practice it just increases the costs of designing the a sic and doesn't really make it less advantageous
22:28:08op_null:bramm: seriously though X11 FPGAs are a thing, so taking up more space on the die isn't very productive
22:28:20bramm:gmaxwell, That's because any idiot can throw literally any random garbage together and call it a proof of work. It's like designing block ciphers for people who find out about feistel networks
22:28:43adam3us:bramm: it might be worse, because the sha256 asics are power density limited. meaning there is unused space to avoid overheating. that can be filled with the other hashes, and i guess you dont mine continually on all hashes with these concotions so they'll be more dense at similar cost than sha256 ones.
22:28:44bramm:op_null, Yeah I know, like I said all it does is make the thing a little more expensive to design
22:28:49gmaxwell:bramm: taking up space is irrelevant. space is cheap on modern process, compute intensive tasks end up being thermally limited. They increase NRE though, since you must design and test N efficient circuits.
22:29:03instagibbs:Any phrase for what Bitcoin is going through? ASIC Crunch? I need something short-hand that I can point out any PoW coin will have to go through someday
22:29:45gmaxwell:bramm: the same is true about many things in cryptocurrency, there have been plenty of altcoins tha slathered togeather some jibberish tech and pushed out something insecure; some have been been pratically exploited due to it though most of the time people don't bother.
22:29:45op_null:you can even get an FPGA big enough to do the CryptoNite (PoW) stuff on I believe. not playing around hardware though, you're talking $1000 USD a chip with no free samples (yes I tried)
22:30:19op_null:turns out if you ask for a sample of a $1000 FPGA people tend to laugh at you.
22:30:39instagibbs:Security from Free Samples
22:30:41adam3us:gmaxwell: there is safety in numbers for altcoins. people competent to break them cant be bothered and there are too many of them so it becomes tiring. the amusement factor wears out.
22:30:53bramm:gmaxwell, People like claiming to have done real protocol work in other protocols too, I'm familiar with this phenomenon
22:31:17bramm:Generally speaking people wind up copying something else verbatim and adding pointless bullshit on top of it
22:31:33bramm:Either that or they get completely owned in embarrassing ways
22:31:38op_null:instagibbs: MoQ for them is by the number of reels too. unless you're willing to cough up millions of dollars per reel you're not going to be able to do a "small" run of them.
22:33:22bramm:gmaxwell, I think I've already asked you this repeatedly, but do you have any idea what operations might not have big power advantages on asics vs. cpus?
22:36:24gmaxwell:No. Well the question to ask is what operations CPUs already do efficiently. But I think wrt power efficiency most of the losses just come from parts that aren't being used. e.g. the multipliers in intel cpus are surely very power efficient themselves (w/ SIMD units), but not when you count all the idle hardware.
22:47:34op_null:bramm: the answer is probably something non obvious. like gmaxwell was saying idle circuits burn power (transistors are never perfect), so forcing people to have a lot of idle circuits is probably a good way of losing efficiency. don't know how that would work though.
22:47:56adam3us:hypothetically you could make a PoW that proves you have eg an x86 cpu. execute PRNG output and hash the memory state afterwards.
22:48:17adam3us:problem is basically something like a parallela cpu is still order of magnitude better throughput
22:48:29bramm:What about the AES acceleration? That's built in and probably well optimized
22:48:39adam3us:ie think about it a 100core atom is much better for this purpose and n one is making that chip
22:49:11adam3us:bramm problem is there is a lot of circuitry unused if you only want AES.
22:54:40bramm:right but if you're pegging with AES then probably most of the CPU is actually going to AES
22:54:58bramm:I mean, it's a pretty expensive self-contained operation
22:58:03tromp_:the memory coin pow i mentioned earlier, as well as cryptonite, make heavy use of AES
22:59:01op_null:tromp_: keep in mind cryptonite was designed to aid a scam.
23:00:45op_null:the first code for cryptonite was designed to hide the fact that the "2 year old" blockchain was really made in a number of weeks or days.
23:03:30bramm:If you're going to rely on AES power efficiency, you should really use AES power efficiency, and keep it simple
23:06:31adam3us:bramm: i think the problem is unused circuitry has current bleed and of the 1bil plus transistors in a CPU the % of them for AES will be low.
23:07:39bramm:adam3us, I find that implausible, computers seem to use a good order of magnitude extra CPU when they're pegging
23:08:47op_null:I don't think that means all of the transistors are in use. CPUs aren't linear devices, they scale voltage and fequency heavily to stay under thermal and power supply limits.
23:09:41bramm:Well, the AES acceleration is the most plausible thing to rely on for efficiency I know. Next most is multiplication, but that probably is nowhere near as good
23:10:32op_null:heh well, I can't help you much thee, I'm not up to date with anything but microprocessors
23:11:01tromp_:there's a huge installed base of older intel cpus still lacking the native AES
23:11:44tromp_:why limit a pow to recent intel core cpus?
23:11:52adam3us:bramm: if you made an ASIC with nothing but AES it would still have a big J/AES-op advantage because of the 999million transistors doing not much useful to the operation.
23:13:12tromp_:off shopping. bbl...
23:13:49gmaxwell:tromp_: well it should rightly take any new protocol years to get established, so it's okay to be a bit forward looking. E.g. I thought about suggesting two rounds of SHA256 as your siphash alternative since future intel microprocessors will have very fast support for that. (though there is risk there since other parts may implement sha2 support in incompatible ways, e.g. not just two rounds)
23:17:15bramm:Oh I see, you're saying that when the CPU is pegged there's a bunch of extra circuitry other than what's actually running which is turned up as well
23:18:38op_null:almost undoubtably, just by the fact of using lots of power doesn't mean it's all on.
23:20:06adam3us:bramm: well i think if you turn on all ALUs 100% it would temp fail
23:20:27op_null:adam3us: or blow up the power supply.
23:21:22adam3us:bramm: but yes the asic advantage would be lower between something which is microcoded & with extra custom ALU stuff like SSE or AES will be lower, but the factor is huge eh. even GPU to ASIC was like 10,000x. think about CPU to ASIC.
23:21:56adam3us:bramm: a lot of CPU circuitry is used optimizing for single thread performance, branch prediction etc. and clock rates that are suboptimal in terms of throughput.
23:22:23bramm:What is SSE?
23:22:25adam3us:bramm: hence why i was saying a parallela cpu like 200mhz or whatver is optimal but 1000 risc cores.
23:22:31adam3us:bramm: mmx v2
23:22:51adam3us:bramm: fp and integer vector operations.
23:23:09bramm:Oh, yeah, that's highly platform dependent though where AES is likely to be accelerated everywhere
23:23:33op_null:I don't think AMD processors have AES instructions. even for intel AES-NI is pretty new
23:23:36adam3us:bramm: a GPU is much closer to an optimal generic PoW cpu than a GPU.
23:26:52adam3us:bramm: the other track is open hw non-profit to pump out sha256 asics at cost+
23:28:01op_null:adam3us: I hear you can rent masks from bitfury
23:30:09rusty2:adam3us: I wouldn't be surprised to see such a project using Lighthouse; seems like a good fit.
23:30:13rusty2:rusty2 is now known as rusty
23:35:14bramm:Overall, I find the power ratio approach much less non-depressing than the memory reliance approach
23:36:24adam3us:bramm: too many negatives. you mean you like memory reliance?
23:36:43bramm:Yeah I like cuckoo better than AES
23:39:44adam3us:bramm: i think there'd need to be a very clear & strong advantage to have bitcoin consider shifting to a new hash. good enough can beat slightly better for ever due to inertia.
23:40:15bramm:Oh I have no delusions that bit coin is going to shift its proofs of work ever
23:40:44op_null:adam3us: from what I remember some miners also support more than just sha256. they support sha256 + secret tweak, just in case.
23:41:45adam3us:bramm: needs some more economic modelling of whether that would be a good idea, or would have bad economic side effects or other form of centralisation, or some other places the incentive to mine coins would appear - eg rampant bot net hacking. buying and use of more sophisticated 0-days to break into general computers etc.
23:42:44gmaxwell:Many of the first generation mining asics support secret per maker alternative POWs. This is something I went around and one by one encouraged parties to enable in their designs, as a risk mitigation against overproduction by any one maker. Many did. I have no idea if any have continued it in their new designs.
23:42:47bramm:adam3us, Or just conduct the empirical experiment, that's more fun :-)
23:43:14adam3us:bramm: make 1200 altcoins, into 1201? eww.
23:43:47bramm:Well yeah, an alt coin would need to have something more interesting going on that just a different proof of work to be worth doing
23:44:03sipa:too bad
23:44:08sipa:coingen would suffice otherwise
23:44:10gmaxwell:empirical expirements seem to not teach that much for cryptosystems; sometimes they get attacked, sometimes not. Sometimes they're adopted, sometimes not. Technical interestingness and security are only very weakly correlated with results.
23:44:21op_null:probably needs to be a protocol for making "test" altcoins. even more than the current testnet, destroy the economics in a way that it can't possibly gain value.
23:44:33sipa:op_null: you know coingen?
23:44:50op_null:allow anybody to spend a coinbase transaction any time, or something.
23:45:02sipa:oh, it's gone :(
23:45:03adam3us:bramm: i mean lets rather try to figure it out; if the economics actually work for hw cost dominated miningthen that would be interesting as its less sensitive to uneven availability of power & electricity costs.
23:45:04gmaxwell:POW is as I've said before some of the least interesting technical areas here. (We've at time had this channel empty out when people got tired of Yet-another-POW proposal. :) ... tolerance for tromps work is comparatively pretty high.)
23:45:16op_null:sipa: I know it, but that makes functioning altcoins. I'm talking about making test coins that don't work.
23:45:27sipa:for some value of 'work'
23:45:28gmaxwell:sipa: seemed coingen was more profitable to buy and shut down.
23:45:44sipa:gmaxwell: my trust in humanity is restored
23:46:09op_null:there's other wwebsites like coingen.
23:46:12adam3us:seemed like the solution to altcoin spam is MORE, much MORE. too high barrier to entry? need to know how to use a compiler, what an imposition!
23:46:16bramm:gmaxwell, Probably because tromp's work is actually theoretically interesting
23:46:30op_null:sipa: http://coincreator.net/
23:46:44op_null:from 0.075 BTC, and you get to choose the name!
23:46:58op_null:Premine! (for extra charge)
23:48:00bramm:Hey I have a question about hash pre image transactions
23:48:04gmaxwell:bramm: not just that, also because tromp is happy to address concerns (or at least the vast majority of them) instead of just wave his hands. His initial efforts had problems which were fixed... most of the altcoin stuff is utterly unreasoned handwaving. I don't think it's all clear that the approach is advisable, but at least I'm happy to say that it's different and that reasoned people could debate the merits; as opposed to being ...
23:48:10gmaxwell:... obviously stupid or pointless.
23:48:11adam3us:it lives again! (or a clone of it) 2170 coins already?? i wonder if there would be more or less alts if it was free?
23:48:36op_null:adam3us: http://mapofcoins.com/
23:49:23op_null:that's missing a lot though. there's like 15 different altcoins with a weed theme.
23:50:35bramm:When you make a transaction along the lines of 'this coin will go over there as soon as this hash pre image appears', what is the hash function? How long is the pre image?
23:51:09op_null:I'm not sure you can do partial preimages in script without the sub string opcode
23:51:28bramm:I mean a full pre image
23:51:37bramm:To trade between two crypto currencies
23:51:48gmaxwell:bramm: in Bitcoin, it's any of the supported hash functions: sha256(), sha256(sha256()), ripemd16(), ripemd160(sha256()), or sha1(). The input can be up to 520 bytes long.
23:52:16op_null:still no though, the output of a script is a boolean. you can't choose anything about the next output script
23:52:25bramm:gmaxwell, Thanks, that answers my question
23:53:01bramm:er, wait, is it possible to do this or not?
23:53:22op_null:there's hash preimage scripts in the chain already
23:53:46gmaxwell:Example protocol for it is described at https://bitcointalk.org/index.php?topic=193281.msg2224949#msg2224949 (there are a number of variations proposed by various people at various times)
23:53:49bramm:op_null, I didn't understand what you meant with your comment starting 'still no though'
23:54:40op_null:bramm: this coin will go over there as soon as this hash pre image appears' this isn't possible. you can say this output is spendable if SHA(a) == SHA(b) && a != b, but you can't say it must be spent in a particular way.
23:55:31gmaxwell:yea, what you actually asked for isn't how it works. op_null is being helpfully pedantic. :)
23:55:52gmaxwell:see the bitcointalk link for what the protocol looks like.
23:56:00bramm:Thank you, I'll read that link and figure it out
23:56:05bramm:Some time when I'm less sick
23:56:50op_null:gmaxwell: did I mention that the Mastering Bitcoin book teaches people to make output scripts that don't require signatures, but doesn't explain that this is a bad idea?
23:57:22gmaxwell:op_null: I think you are a bad influence on my mental well being, my friend. :)
23:57:39op_null:but it's alright! all the examples are invalid because they use OP_MUL in them.
23:57:40adam3us:op_null: for some reason mastering bitcion makes me think of mastercoin.
23:57:45gmaxwell:Having ulcers from this stuff is no fun.
23:57:46sipa:op_null: lol
23:57:47gmaxwell:op_null: lol