00:00:02	andytoshi:	gmaxwell: good point, i didn't mention progress freeness nearly as much as i should've (though it is in there). i didn't think of high variance, i'll have to muse on that
00:00:27	gmaxwell:	andytoshi: I think they are precisely the same characteristic, but two different angles-of-motivation for them.
00:00:41	gmaxwell:	but maybe there is some example that could be made that makes them different characteristics.
00:01:12	gmaxwell:	Also, perhaps that paper is a place to put the nothing-at-stake argument? (A "what about proof of stake?") ... it was pointed out to me that it's not adequately published.
00:01:14	andytoshi:	gmaxwell: yeah, that's my feeling based on having thought about it for 90 seconds, but i'll try to make that concrete
00:01:34	andytoshi:	oh, really good call on PoS, that completely skipped my mind
00:01:50	amiller:	andytoshi i'm bugged by this line: "it is halting-complete to create an algorithm which runs at the same speed on general-purpose and dedicated hardware, so ultimately ASIC resistance is futile."
00:02:06	amiller:	how is that halting-complete, those seem unrelated?
00:02:28	andytoshi:	amiller: oh, i thought you would be ;) i had a half-baked idea for how they were related
00:03:08	gmaxwell:	as an aside, I think we should do on bitcoin.org what the tor project does: we ought to have a directory of academic work on bitcoin, in particular we can use it to list work the technical community considers good— and for work we consider poor, list it along side the rebuttals. We can also publish scientific work from the community that hasn't been published in normal academic channels.
00:03:11	andytoshi:	along the lines of, to require general-purpose hardware, you have to use it in full generality. i meant to elaborate or remove that, and forgot to do either
00:04:14	amiller:	gmaxwell, that sounds useful, there's the bitcoin wiki research papers page but that just has links basically and isn't curated at all
00:06:07	gmaxwell:	andytoshi: the argument I usually make WRT specialization gap is that if nothing else specialized hardware can very get some factor— say of 2— in efficiency, if nothing else than by eliminating perpherials. and because of the market forces of POW consensus a relatively small gap is probably all you need for one to dominate. I don't know how to make a more concrete argument out of that.
00:07:06	andytoshi:	amiller: ok, what i had thought was, you can write any algorithm in vhdl and compile it to hardware which beats a general-purpose machine at efficient mining. so to write something beyond this, you need to go beyond TC e.g. go to a computing model with a higher ordinal. hence halting-complete. but now i'm thinking about that more clearly and i don't see that it makes any sense :}
00:08:48	gmaxwell:	I think it's likely you can design to very precisely match some common hardware in an efficient way which is hard to get a large multiple on... but doing that while also being free of algorithimic short cuts including "approximation speedups" seems very hard.
00:08:57	gmaxwell:	SHA256 is not even free of approximation speedups.
00:09:33	gmaxwell:	By approximation speedups I mean that instead of SHA256 you implement SHA256' which is only identical to SHA256 sometimes but it faster (/less gate area) by enough to compensate.
00:09:38	andytoshi:	oh, i think gmaxwell is right. if you try to think too mathematically, you can imagine a PoW which somehow requires to run a universal circuit. then your special-purpose hw is a general-purpose machine, so in principle you get no speedup
00:10:01	amiller:	andytoshi, a sort of consistent theme in your answers is that the ideal optimal mining configuration for a puzzle would be one that has zero/low startup/equipment cost, and basically just uses energy
00:10:21	andytoshi:	yeah, that is what i believe. but i understand that is something of a controversial thesis
00:10:25	gmaxwell:	E.g. for sha256 already all unrolled miners eliminate the last several rounds of the function (not needed to tell if the first 32 bits are 0)
00:10:45	andytoshi:	i meant to teach the controversy a bit, but my premise didn't appear explicitly so i wasn't sure how to bring it up
00:10:57	gmaxwell:	Another example is that I think in the later adders you may be able to eliminate carry logic profitably.
00:11:04	maaku:	andytoshi: i'm not sure it's controversial so much as people just don't start with that premise
00:11:25	amiller:	andytoshi, it's pretty interesting, i sort of like that point, the alternative is also folkore here though which is that, having to invest in up front hardware cost leads to more incentive to secure the system etc.
00:11:37	gmaxwell:	but for non-cryptographic pow they are usually dripping with approximation potential.
00:12:21	gmaxwell:	amiller: there is also the informal belief I have, however, that upfront costs are amortized.
00:12:58	amiller:	gmaxwell, i don't quite get what you mean by that, or what the implication is for decentralized vs centralized effect?
00:12:59	gmaxwell:	(though I suppose you can combine it with that investment folklore to say that you get the most amortization the longest you operate!)
00:13:00	maaku:	well the argument that upfront costs leads to centralization is pretty straight forward
00:13:17	amiller:	oh
00:13:28	maaku:	the "uses energy" argument goes back to the entropy arguments I made above ^^
00:14:44	gmaxwell:	amiller: basically that a pow that costs X upfront and Y/unit ongoing ... the X is actually completely irrelevant in the infinitely long term. This basically undermines the entire scurity argument for scrypt if you assume the attacker will operate for a sufficiently long time, esp since for modern silicon process the power costs very rapidly go past the mfgr. costs (e.g. in two months of operation, even talking retail prices for ...
00:14:50	gmaxwell:	... hardware).
00:16:10	gmaxwell:	(I'm getting 2 months basically from what gpus cost to buy vs run, but it seems to hold for other stuff too)
00:16:14	amiller:	the thing that's strange to me is that if there's zero startup cost, you get basically hashes per dollar paying for computation, and dollars per hash in reward
00:16:16	maaku:	gmaxwell: sure, but if the smallest economically compmetative miner equipment costed $1MM to buy a single unit, where would average joe get the up front loan to buy it?
00:16:37	amiller:	there's no reason to go faster or slower and have more/less hashpower
00:16:56	andytoshi:	iirc (sorry if i'm recalling wrong) tromp's scheme was supposed to be so memory heavy that your speed was limited by the speed of light rather than processing speed, and your energy usage would be nil. tromp argued this was good from an environmental perspective but it made this amortization problem much much worse
00:17:03	gmaxwell:	right, which is idea, it's scale free.. everyone can play at every size.
00:17:05	maaku:	amiller: local variations in amount of computation hash/dollar gets you
00:17:20	amiller:	so instead, the cost of hardware up front is what makes it harder to go faster
00:17:33	amiller:	generlaly people prefer their money now so if it costs the same you might as well buy as much as you can up front
00:17:47	gmaxwell:	andytoshi: thats my recollection but I thought it was impossible to discuss this with tromp (sorry), and I haven't well formalized the amortization argument yet.
00:18:36	amiller:	andytoshi, i like the part about the thermodynamic limit as a good thing, that at some limit it's cheaper to put your heat generators far apart rather than constantly heating the same space, i can't figure out if that's the case at rasoable scales though
00:18:59	gmaxwell:	(I'm pretty convinced that the amortization argument is ... uh asymptotically true... figuring out how much it actually applies in the real, finite, world will take some difficult analysis)
00:19:00	amiller:	for most reasonable scales, you get the opposite bonus for having centralized cooling in data center i think...
00:19:52	andytoshi:	gmaxwell: well, he and petertodd got into an argument about laying out ram so the speed of light didn't matter, and (a) i didn't understand that argument and (b) i didn't care because i think there exists an algorithm for which petertodd is wrong, and that's interesting in itself. then then people were arguing over each other and crossing issues and that was the cause of the impossibility in arguing
00:19:55	andytoshi:	with tromp, it was just too hectic
00:20:01	andytoshi:	maybe we have highlighted him enough that he'll come by and clarify :)
00:20:49	tromp_:	i'm back, but will have to go have dinner soon
00:21:12	andytoshi:	amiller: hmm, interesting. i assumed (but don't know) that if you are computing at the thermodynamic limit, that's the most efficient way for you to turn electricity into heat
00:21:28	gmaxwell:	andytoshi: peter's argument was that you can lay out the circuit geometry so that it's effectively mux-power-consumption limited not speed of light limited. E.g. having a non-blocking switching network physically laying on top of the memory cells so that in an n-deep pipeline all cells are readable.
00:21:31	andytoshi:	amiller: so you have way higher density than a data center, and density is your friend (you want a solid block of comptronium)
00:21:31	tromp_:	i think arguments about upfront vs operational costs shld take into account that most hardware becomes obsolete in3-5 years
00:21:49	andytoshi:	and that's what the heat dissipation prevents
00:21:53	tromp_:	and in case of PoW asics, much faster than that
00:22:15	tromp_:	i printed out your paper, andytoshi, and will read it tonight
00:22:21	maaku:	tromp_: that will only be true for about 50 years
00:22:26	tromp_:	thanks for clearly laying out the arguments
00:22:29	amiller:	it's a really neat paper, i like having all those ideas in one place.
00:22:46	andytoshi:	maaku and i did some envelope calculations, i think in the absense of reversible computing or algorithmic speedups, bitcoin asics are within sight of the thermodynamic limit
00:22:49	andytoshi:	i.e. what maaku just said
00:22:56	maaku:	andytoshi: I would really love if you boiled down many of the things which go on here to whitepapers like that
00:23:02	tromp_:	maaku: it's not that relevant to hypothesize about decades ito the future
00:23:10	gmaxwell:	tromp_: even if you assume 3-5 years (which is _not_ believed to hold up since moores law is expected to fail, esp since we're now basically ~4 density doublings from single atom gates) we're already at a point on 28nm where power costs are greater than mfgr costs in a couple months. So 3 years is a long time relative to that.
00:23:14	tromp_:	or at least not interesting to me
00:23:19	maaku:	tromp_: it is on -wizards ;)
00:23:44	andytoshi:	amiller, maaku: i would love to write more as well, they are reasonably quick to write (i need 4-5 uninterrupted hours) and they help me a lot. but ofc i am in academic mode, my free time is spent unwinding :)
00:23:51	gmaxwell:	thermodynamic limit for sha256 should be easy to calculate.
00:24:02	gmaxwell:	at least if you assume a particular adder topology.
00:24:13	andytoshi:	i assumed 10000 bit flips per hash ;)
00:24:18	gmaxwell:	you can also get gate transiction power use for varrious technology pretty easily.
00:24:20	tromp_:	the thermo dynamic limit can only be approached by computing very slowly
00:24:29	c0rw|awa_:	c0rw|awa_ is now known as c0rw1n
00:25:46	gmaxwell:	mining is a bit different from regular computing in that we can tolerate 'approximation' very well.
00:25:53	gmaxwell:	e.g. you can use highly faulty hardware.
00:26:09	gmaxwell:	and typical mining equipment is run at speeds where it has an observed error rate on the order of 1%.
00:26:50	topynate:	^ did not know that. wow.
00:26:55	gmaxwell:	(and mining software actually dynamically controls the clock to achieve the best goodput... though it's a little more complicated when you care about h/j goodput instead of h/s goodput)
00:27:23	tromp_:	when i have digested and pondered andytoshi's arguments, i'll probably add a section to my whitepaper discussing it
00:27:53	tromp_:	does the faq accurately represent your viewpoint as well, gmaxwell?
00:28:00	gmaxwell:	probably.
00:28:29	gmaxwell:	I'd really like to figure out how to formalize the amortization argument. I am absolutely convinced that it reweighs the balances in this stuff somewhat, but I'm not so sure how much.
00:28:32	tromp_:	ok, i'll go grab that dinner now. and keep heated arguments out of this channel::)
00:29:04	maaku:	tromp_: where are you located?
00:29:18	tromp_:	as my homepage says, in Long Island
00:30:18	maaku:	ah, late dinner then
00:31:48	andytoshi:	meanwhile i'll remove that halting-complete comment which i now believe is false, add some comments on pos, and think about high variance. ...after i do some homework
00:33:07	gmaxwell:	I kinda feel like it should also make the pow-shedpainting-is-boring argument. :)
00:33:26	amiller:	hey andytoshi one more suggestion, i think for the no useful-proof-of-work section, i disagree with your argument and prefer a different argument
00:34:05	amiller:	the argument i like is that if there is a way to get value (or someone willing to pay for it) for the work itself, then it subsidizes an attacker who can work on mining a double-spendy attack fork, and still sell the work to whoever benefits from it even if the attack fails
00:34:52	andytoshi:	ah, this is what i meant by failing to align incentives, maybe i should clarify that
00:35:09	gmaxwell:	yea, I think I have been previously convinced that work for public good is potentially viable because it lacks the above problem... but even most efforts for that fail because they're not approximation free, progress free, optimization free, etc.
00:36:19	gmaxwell:	But I think things like timelock encryption or amiller's storage of public good could potentially work or be close enough.
00:38:19	gmaxwell:	amiller: did you eventually have some more thoughts on the user controlled storage where I ask you to store CSPRNG data, and make my life easier... I didn't think your linear code helped you, because knoweldge of my CSPRNG allows me to interpolate the linear code with fewer inputs. (in fact, the linear code may spread out the benefit of my CSPRNG data so that I don't have to be as picky about my location in storage space in order to ...
00:38:26	gmaxwell:	... benefit from it)
00:53:46	amiller:	gmaxwell, yeah that linear code is absolutely not enough for aribtrary user data
00:54:45	gmaxwell:	I think it's fine for something which a clear 'not really user controlled' identity, like the blockchain or a specific library.
00:54:53	amiller:	on the other hand, for the user-submitted updateable data, to make it so you don't have to constantly reencode the entire dataset, we are suggesting to use a specific linear code that basically does mix in thoroughly
00:55:59	amiller:	i can't find the link to it though 1 sec
00:56:28	gmaxwell:	I assume its some kind of locally decodable code... but I don't see how 'mix in thoroughly' helps— if I know all of some fraction of the data 'for free' then thats one or more less degree of freedom, and so I can get away with not knowing something else.
00:57:01	amiller:	it's not locally decodable
00:57:16	gmaxwell:	oh interesting.
00:57:42	amiller:	it's basically the "Butterfly tranfsorm" of this paper http://www.tablusqa.com/rsalabs/presentations/hourglass.pdf
00:57:52	amiller:	an instance of an "hourglass tranfsorm"
00:58:25	amiller:	the point of an hourglass transform is that it should be pretty easy to convert the entire source dataset into the entire encoded dataset in linear or n log n time
00:58:28	gmaxwell:	(I'm familar with butterfly networks, ... you end up with factorizations like that in any fft like transform)
00:58:57	amiller:	but it should be about equally hard to compute even an individual piece of the output from just the source
00:59:31	gmaxwell:	interesting! but then you've made access hard!
00:59:48	amiller:	access is *already* super hard and we don't have any specific solution to that!
01:00:15	gmaxwell:	hahah. "We've stored your data very reliably everywhere, but no one can access it."
01:00:19	amiller:	by super hard i mean you can reconstruct the entire source dataset from a fraction of the encodings
01:00:40	amiller:	the way our game works is almost like, okay there's been a major catastrophe and 2/3 of the world is a crater
01:00:55	amiller:	all the remaining people are now online and can participate honestly in an interactive recovery procedure
01:01:44	gmaxwell:	you should call this holographic storage just to @#$@ with people trying to search for other things. :)
01:11:38	nsh:	* nsh muses
01:16:07	nsh_:	nsh_ is now known as nsh
01:24:55	gmaxwell:	from #bitcoin
01:24:57	gmaxwell:	18:21 < snowsilence> gmaxwell: Here's a question: Are there any noteworthy
01:25:00	gmaxwell:	questions you'd like to see asked, that you'd be really passionate about
01:25:03	gmaxwell:	responding to, aside from all the basic repetition that comes up here?
01:25:05	gmaxwell:	18:21 < gmaxwell> snowsilence: it's a good question but not really one I can
01:25:09	gmaxwell:	do justice too off the cuff. I should probably write a Frequently Unasked
01:25:12	gmaxwell:	Questions page, because I absolutely do think a lot of the things people
01:25:15	gmaxwell:	are talking about are "missing the mark".
01:27:05	andytoshi:	that's a really cool question
01:28:36	gmaxwell:	I think it's somewhat inherently an opinion-piece question, but it sounds like something I should do that other folks might have opinions on.
01:29:33	gmaxwell:	another related idea is having a FQA (frequently questioned answers) e.g. a rebuttal to common FAQ answers that are considered not very accurate. (e.g. in the spirit of the deliciously snarky C++ FQA)
01:37:20	c0rw1n:	c0rw1n is now known as c0rw|sleep
01:50:19	tacotime:	andytoshi, Sorry I'm lagging on the creation of a formal alt-chain idea index. I had some financial issues this week and not a lot really got done.
01:50:26	tacotime:	But I still plan to do it.
01:56:45	andytoshi:	tacotime: no worries, i have been lagging on reading that PoS+PoW paper you sent me..
02:05:16	tacotime:	Not a problem, take your time. :)
02:27:24	Luke-Jr:	[01:50:19] andytoshi, Sorry I'm lagging on the creation of a formal alt-chain idea index. I had some financial issues this week and not a lot really got done. <-- doesn't this already exist?
02:27:43	Luke-Jr:	I mean, there's the list of actual altcoins, the Hardfork Wishlist, and gmaxwell's collection of alt ideas…\
02:27:51	Luke-Jr:	covers all possible interpretations of that IMO
02:30:42	kanzure:	maybe he means an index for valuation of alt-chain ideas
02:30:56	kanzure:	(i hope not)
02:31:21	Luke-Jr:	XD
02:33:42	andytoshi:	Luke-Jr: we are talking about a list of copycat alts, the decisions they made, and why they were (potentially or actually) destructive
02:33:52	andytoshi:	bad ideas, not good ones :)
02:35:06	kanzure:	"your idea is morally bad because: [ ] your hash rate leaves all of your users open to attack, [ ] you have poorly implemented elliptic curve cryptography, ...."
02:35:19	Luke-Jr:	andytoshi: i c.
02:35:57	Luke-Jr:	kanzure: ☐ you are too stupid for me to try to figure out what category your stupidity fits into
02:36:09	kazcw:	[ ] you are illegally distributing only binaries of a GPL-derived work
02:36:17	Luke-Jr:	☑ all of the above
02:36:42	kanzure:	"and this time i mean it"
02:36:45	Luke-Jr:	kazcw: actually, there was a scamcoin that violated the MIT license..
02:36:55	Luke-Jr:	I DMCA'd their butt
02:37:00	kanzure:	should probably also include something about malware being included
02:37:13	kanzure:	maybe one about "because we already broke your obfuscation-security, and it still isn't fixed"
02:37:15	Luke-Jr:	arguably, scamcoins are inherently malware
02:39:49	kanzure:	"[ ] your code is based on assumptions that violate the laws of thermodynamics"
02:40:11	Luke-Jr:	lol
02:40:51	nsh:	could make a comprehensive flow diagram leading inexorably to the part where value is lost
02:41:01	kanzure:	what do you mean?
02:41:47	kanzure:	(also i'm sure markets can act irrational even in the face of technical flaws)
02:42:36	nsh:	presumably you can merge the trajectories of all alts with predictable failure routes with junctions of common misapplication/mistake
03:48:35	jcb1:	andytoshi: very nice write-up on PoW. Another argument against "useful" PoW is that anything useful is inevitably going to be more useful/interesting to some people than others. This requires solving a social choice function in a decentralized way, which we don't know how to do.
03:50:19	jcb1:	andytoshi: also I think you should say miners are "motivated not *solely* by the block reward", with the result that mining is more valuable for some miners than others. I don't get the "others encroaching on their work" argument
04:09:56	andytoshi:	jcb1: i mean, e.g. what if the PoW is useful for finding oil based on satellite images? if i want the oil, i want to be the only one searching for it.
04:10:51	andytoshi:	i think it's OK if different miners value the reward differently. it's only if many miners value the reward at or near zero that you have a problem
04:15:40	jcb1:	the encroaching makes more sense given the oil example, perhaps it could use more explanation in your write-up since that proposal strikes me as a bit out-there
04:20:12	jcb1:	I don't think it's a catastrophe if some miners get more or less utility from the "useful PoW". It's equivalent to some miners being able to mine more cheaply today (cheaper electricity, colder climate, etc.). But I think it's certainly not a good property and works against the tendency to decentralization
05:07:27	jaekwon1:	i suspect it might be possible to take advantage of useful work in a PoW scheme.
05:08:12	jaekwon1:	the problem with useful work is that usually it isn't possible to embed the previous blockhead (hash) in the useful work to be done.
05:09:06	warren:	gmaxwell: any URL describes the multiple failures of bitshares to come up with a memory hard algorithm that was easy to break?
05:09:18	warren:	err, that ended up easy to break
05:09:45	jaekwon1:	but it might be possible in some kinds of work, like molecular folding. you might, for example, be able to include the hash as extraneous DNA, where the useful DNA and blockhead-hash (random useless) DNA get folded together to hopefully form interesting DNA.
05:10:17	jaekwon1:	or, if you can't embed the blockhead-hash in the useful work, how about a scheme as follows:
05:11:00	jaekwon1:	do some useful work, if you find a solution, use the fitness of the solution to give yourself a decreased difficulty target.
05:11:45	jaekwon1:	that way, you only need to publish the useful work solution along with your mined block, and, others would still be incentivized to build off of your block rather than steal your work.
05:22:04	kanzure:	jaekwon1: i spent a bunch of time in a molecular biology lab using dna to do computation
05:22:18	kanzure:	jaekwon1: lots and lots of pcr reactions and gel imaging..
05:22:47	kanzure:	jaekwon1: http://diyhpl.us/~bryan/papers2/ellington/Modelling%20amorphous%20computations%20with%20transcription%20networks%20-%202009.pdf
05:23:22	jaekwon1:	*to form interesting protein molecules, i mean
05:24:31	kanzure:	oh i see, you don't mean actual dna for computing. how unfortunate.
05:25:00	kanzure:	(dna is very very good at parallelization, if you can afford to print out enough synthetic molecules with your sequences-of-interest)
05:44:46	jaekwon1:	scratch that, i can't find a good way to incentivize other miners to build off your block rather than attempt to steal your work. i wonder if it works if the useful-work solution first gets embedded into the blockchain as proof-of-existence (e.g. a hash of your solution), you wait a couple blocks, and then submit your useful work solution to redeem your reward.
05:45:25	jaekwon1:	kanzure: very cool. i'll check out that paper. i'm not very knowledgeable in molecular bio though.
05:47:24	jaekwon1:	of course you can't secure your blockchain with useful work, but you can subsidize it.
05:48:23	gmaxwell:	sipa: bitflipped sha512 works fine.
05:52:32	Snowleaksange:	you totally can do useful-PoW
05:53:19	Snowleaksange:	biggest issue w implementing is candidate useful work
05:53:30	Snowleaksange:	dr pande of folding at home is working with curecoin
05:53:45	Snowleaksange:	but unfortunately their design is retarded
05:53:59	Snowleaksange:	electric sheep coin is best candidate i know of
05:54:30	warren:	adam3us: ping
05:56:02	adam3us:	warren: hello
05:56:55	Snowleaksange:	also cool @ dna compting, i read about how they can indo mass/parallell xna/dna transcription and reverse, a Genetic Algorithm formalism in a testtube
05:57:00	warren:	adam3us: not sure if this was asked before, do you know if savitch's theorem is relevant to the goal of some scam coins to implement a memory-hard PoW that is fast to validate?
05:57:02	Snowleaksange:	induce
05:57:58	warren:	adam3us: (validation requiring less memory and is thus faster)
05:59:22	jaekwon1:	snowleaksange: candidate useful work? and by useful work, do you mean, arbitrary easy-to-verify useful work?
06:00:04	Snowleaksange:	i meant open source distributed computing project
06:00:06	adam3us:	warren: i am not sure. it seems like practical considerations of power density being a limiting factor which is a quite hardware level concept are playing a big factor, re what gmaxwell was saying about the performance of scrypt asic vs scrypt gpu (being a big speedup) relative to sha256 asic vs gpu.
06:01:14	warren:	adam3us: huh, script is a bigger speedup than sha256?
06:01:52	jaekwon1:	link for electric sheep coin?
06:02:04	Luke-Jr:	warren: obviously?
06:02:17	warren:	adam3us: I'm asking from a pure computational complexity point of view, not talking about scrypt.
06:02:26	adam3us:	warren: also that simplicity can be good. yes thats what gmaxwell said with the sample scrypt asic he had. his rationale for why this might be is sha256 is power density limited (lots of space between sha256 circuits or it would overheat)
06:02:55	Snowleaksange:	i was just suggesting electric sheep coin because electric sheep is one of few open source distributing computing projects
06:03:20	Snowleaksange:	distributed
06:03:25	adam3us:	warren: yes i understand. its an abstract question about the existence of a better or optimal asic resistant algo and if there is some fundamental limiting principle. i am not sure
06:04:23	warren:	Oh, I was more curious about the mathematics, if that particular theorem is relevant.
06:04:49	adam3us:	warren: for example bitshares momentum hash seems plausible initially because it is able to have memoryless verification while incurring memory to compute, and he can limit the time memory trade off via the size of the sha256 sub-proofs
06:05:23	warren:	Bitshares tried and failed to implement slow memory-hard mining that validates quickly. One mathematician heard about their goal and suggested the maximum difference between complexity of mining and verification may be limited by Savitch's theorem.
06:06:12	warren:	adam3us: I haven't been following bitshares, were their later attempts not broken?
06:06:30	jaekwon1:	adam3us, warren: bitshare's momentum hash failed?
06:06:54	warren:	jaekwon1: something like ~3 of their attempts were broken within minutes, is what I hear.
06:07:32	adam3us:	warren: i was initially thinking that would be broken because more memory would give you quadratic speedup. but the memory that can be used is constrained as they define it that all the candidates have to come from a limited search space, so when its exhausted they have to start again
06:08:21	adam3us:	warren: yes that much is true, they proposed a number of previous versions that were quickly broken on the forum. even this momentum hash was shown to have a tmto where they thought it would not
06:08:38	warren:	how bad is the TMTO, and people are using it now?
06:09:52	adam3us:	warren: if i understood the tmto the idea was to use a bloom filter to make a compressed but slightly unreliable memory. because it uses much less memory then it fits into a gpu work unit cache. so while it loses some efficiency because of the unreliability of the bloom compressed ram; it gets like 100x from using lots of cores. the guy who claimed the bounty was able to show its a net win
06:10:24	adam3us:	warren: i dont know if that got coded up properly into efficient gpu code or not. but the bitshares guy was convinced enough to pay out $5k bounty i think
06:10:48	adam3us:	warren: that was a fail because he was aiming for CPU only
06:11:08	jaekwon1:	ah, that actually makes sense.
06:11:10	Snowleaksange:	i think basic idea of useful-pow is just replace nonce with useful_work(nonce)
06:11:33	warren:	Snowleaksange: can useful pow's be validated without external data?
06:11:35	adam3us:	warren: but i think maybe that is not a good indication for ASIC hardness of momentum. presumably that tmto can be used at hw level also
06:11:56	warren:	adam3us: not following
06:12:45	Snowleaksange:	depends warren, if it was just searching digits of pi for messages from god then yeah, but if it ssomething like seti@home gonna have to organize p2p input database
06:12:47	adam3us:	warren: i mean if tmto works on software, its a tool that can be used at hw, maybe with more extreme trade offs, because they can use custom hw to do lots more work, and get away with very little ram eg
06:13:59	Snowleaksange:	or use central authority
06:14:34	adam3us:	warren: i dont know enough about complexity classes to have an opinion on this savitch theorem implications for existence or not of inherently memory consuming pow with low memory verification. i guess you saw also cuckoo hash by tromp__
06:14:50	adam3us:	warren: sorry cuckoo cycle (based on cuckoo hash)
06:17:08	adam3us:	warren: i think gmaxwell argument was if the memory hw required per compute hw was small enough to fit within the blank space required to not overheat the chip, then it doesnt really slow the hw down. and i guess it ends up being much more parallel and faster than you can do on a GPU
06:18:05	adam3us:	warren: i do like the objective of momentum - consume memory to create, but consume very little memory to verify.
06:18:50	warren:	It sounds like if it became extremely popular someone would have incentive to make custom hardware to have a big advantage.
06:21:36	adam3us:	warren: yes. gmaxwell would be useful to have the actual stats on the scrypt asic as its sample hw that i guess is not widely available yet. about momentum yes. petertodd and i were discussing that generally hw wins, and sw people dont know about all the hw tricks. so maybe eg multi-port RAM or different types of RAM optimized for the use-case. its hard to predict the advantage of custom hw against a given algorithm.
06:23:35	warren:	adam3us: today is the first I heard about, "X11 was originated with DarkCoin and is a combination of 11 hashing functions. It is primarily CPU minable with GPU miners now available. It makes an excellent alternative to Scrypt mining and is particularly attractive in light of the upcoming widespread availability of Scrypt ASIC mining units."
06:23:38	adam3us:	warren: even if one targetted say amd gpus, and made the PoW be to execute an instruction sequence pseudo randomly generated on a sequence of RAM states, so that it requires dynamic execution and an actual risc core to run; still hw can win by making a stripped down GPU
06:24:06	warren:	It strikes me that if these 11 algorithms are easily mineable in GPU, it would be possible if it become profitable enough to implement that in ASIC too.
06:24:23	warren:	and that sounds easier to do than momentum
06:25:26	adam3us:	warren: yes i saw that one for some reason came up in another discussion. it does seem likely that eg if the unused space due to heat can be filled with the other hashes, then it can all be pipelined together and no slowdown. the ony cost is replicating different hash functions which doesnt seem particularly hard
06:25:40	Snowleaksange:	i think you can even do arbitrary compute coin
06:26:16	Snowleaksange:	like people schedule useful computations on miners thats used as pow
06:26:19	adam3us:	warren: i was thinking people might be setting their hopes in primecoin PoW as another option because it involves bignums
06:26:34	warren:	is there a but?
06:26:48	Snowleaksange:	its not really the blockchain logic thats difficulty here but organizing all the other details
06:26:49	adam3us:	Snowleaksange: useful pow is difficulty, and maybe fails definitionally - if it has value
06:27:12	adam3us:	warren: probably. eg there are SSL accelerated/bignum accelerator hw. so probably that can be done also
06:27:36	warren:	adam3us: earlier attempts of momentum were broken by simple algebra?
06:27:38	adam3us:	warren: seems like a game of cat and mouse where hw wins if there eventually is enough incentive to build the hw
06:28:03	Snowleaksange:	why do you say that adam3us?
06:28:38	adam3us:	warren: i forgot the details but the breaks were quite simple. they were throwing out ideas on the forum and then people were breaking them.
06:29:26	adam3us:	Snowleaksange: because if it had usefulness you could be paid for the utility computing so there is no opportunity cost (its free to you maybe)
06:29:53	Snowleaksange:	hmm i see
06:30:27	Snowleaksange:	another practical criticism is this gonna max the tolerable time/compute-power to verify a block
06:30:28	adam3us:	Snowleaksange: besides its very hard to do. i dont think there is any known efficient way to prove generic work was done
06:30:55	Snowleaksange:	adam3us; repeatin git.
06:31:58	adam3us:	Snowleaksange: verification time is interesting yes. that was why momentum's design idea was quite interesting (require memory to compute but not to verify).
06:33:19	adam3us:	warren: i suppose someone (ideally with hw experience) should go approximate optimized hw end-game for cuckoo cycles, momentum, ceolho's merkle hash, primecoin, scrypt, sha256 etc and pronounce which is likely offering the least asic hw advantage
06:34:33	warren:	slow verification is deadly to a network
06:34:59	Snowleaksange:	whats the maximum block verification time could be tolerated?
06:35:09	Snowleaksange:	100 ms on 2ghz cpu?
06:35:39	adam3us:	warren: but hearn suggested before when this was bought up that eg scrypt 128kB was fast enough (tho slower than sha256) that it idnt make much dif as the main overhead was ecdsa sig verificationsand there are many ecdsa per block and one PoW
06:37:02	Snowleaksange:	maybe even 1 second
06:37:13	Snowleaksange:	thats a lot of useful work
06:40:01	Snowleaksange:	also would need to fetch data to verify a block tho in the interesting cases
06:40:13	Snowleaksange:	which is a legit nightmare but solvable
06:51:03	Snowleaksange:	or totally easy if just serve the input off an agreed central website. many would find that aspect underwhelming but it makes a simpler proof-of-conept
06:55:54	Snowleaksange:	i could patch bitcoind up for this pretty quick. or if anyone else would like to do that. i could instead structure electric sheep calculations for use w such a bitcoind
06:59:41	gmaxwell:	Snowleaksange: you appear to be emitting jibberish right now.
07:02:05	Snowleaksange:	ok gmawell let me know if you have more detailed query
07:02:41	warren:	adam3us: for sync it's not a big deal, greater latency does increase natural orphans and the reduces the cost of attacks
07:03:53	Snowleaksange:	turingcoin
07:06:07	wumpus:	do androids emit gibberish about electric sheep?
07:06:54	adam3us:	warren: but you verify ecdsa sigs on a block before building on it (after verifying the PoW) and so hearn's claim that the cost is dominated by ecdsa sig verify would apply to verification latency
07:08:26	warren:	adam3us: point being if you have slow verification you disavantage a network even before it begins to become even slower due to large blocks
07:08:37	gmaxwell:	adam3us: normally for a block recieved at the tip of the chain there is ~no ecdsa done at all.
07:10:22	adam3us:	gmaxwell: but isnt block validation including verifying the scripts are valid? hm i suppose the tx were already validated in the context of isStandard() and isValid() for relaying and that is cache so that a block can be instaverified?
07:11:02	gmaxwell:	adam3us: right, the signature checking is cached.
07:11:04	adam3us:	warren: ok then i can see the heavier verification primarily would (presumably slightly only) affect orphan rate
07:28:07	warren:	adam3us: pm
07:28:36	adam3us:	warren: sure. but note as i recall the idea about power density explanation is gmaxwell's
07:28:52	warren:	k
08:18:23	justanot1eruser:	Is there anywhere I can read an in depth explanation of the attack on PoW where you find winning histories?
08:26:10	Snowleaksange:	http://turingcash.com/ ;)
08:50:23	c0rw|sleep:	c0rw|sleep is now known as c0rw1n
08:53:56	irc.freenode.net:	Disconnected from irc.freenode.net (ERROR :Closing Link: S0106c0c1c0894c25.vs.shawcable.net (Ping timeout: 252 seconds))
08:55:08	leguin.freenode.net:	topic is: This channel is not about Bitcoin today | "Bitcoin research, hardfork wishlist, ideas for the future - see also: https://en.bitcoin.it/wiki/Hardfork_Wishlist https://en.bitcoin.it/wiki/User:Gmaxwell/alt_ideas. This channel is logged at http://download.wpsoftware.net/bitcoin/wizards/. For questions about the logs talk to andytoshi."
08:55:08	leguin.freenode.net:	Users on #bitcoin-wizards: andytoshi-logbot espes__ OneFixt_ cajg shinybro justanot1eruser antephialtic adam3us drmanbrodude hearn RoboTeddy samson_ Graet _ingsoc draino shesek Hunger- TheSeven irclouis go1111111 nsh Logicwax emsid |Ryan52 spinza tromp__ bobke_ koval- mkarrer_ gribble c0rw1n paperbot jcb1 edulix rdponticelli so eristisk dansmith_btc d34th [Tristan] lnovy arubi ascent_ Emcy rdymac mike4 pigeons gavinandresen [\\\] forrestv maaku ageis jrmithdobbs
08:55:08	leguin.freenode.net:	Users on #bitcoin-wizards: hiatobr mr_burdell K1773R Elriel imjonathan kanzure kazcw otoburb midnightmagic BCB a5m0 harrow randomwalker justusranvier UukGoblin LarsLarsen topynate coryfields sl01 andytoshi HM shadders ewust petertodd typex Sorcier_FXK zacm stqism Dyaheon realazthat epscy CodeShark bedeho digitalmagus8 trn stonecoldpat copumpkin postpre ryan-c Luke-Jr mmozeiko iddo gmaxwell dogeplops firepacket rs0 Alanius phantomcircuit comboy lechuga_ area
08:55:08	leguin.freenode.net:	Users on #bitcoin-wizards: optimator hno wumpus jron asoltys azariah4 nezZario Mikalv sbp tucenaber nikitab nikitab_ mhanne Snowleaksange poggy tacotime kaptah sipa artifexd kinlo helo EasyAt pajarillo michagogo|cloud airbreather flammit Muis keus Krellan weex lianj nanotube Sangheili warren jcorgan BlueMatt grzs Fistful_of_Coins Anduck roasbeef amiller heakins @ChanServ
11:32:09	justanot1eruser:	Snowleaksange: so turingcash is a bitcoin fork with a new PoW?
13:41:33	maaku:	maaku is now known as Guest84133
13:46:40	andytoshi:	justanot1eruser: if you mean the attack on PoS where you grind stake, i'll add a blurb about it to my PoW doc, it's conceptually nothing crazy
14:56:01	wallet42:	wallet42 is now known as Guest59014
14:56:01	wallet421:	wallet421 is now known as wallet42
15:34:16	Guest84133:	Guest84133 is now known as maaku
15:41:13	zzyzx:	zzyzx is now known as roidster
15:41:42	roidster:	roidster is now known as Guest44183
16:10:44	andytoshi:	gmaxwell: what do you mean by "approximation free" and "optimization free"? my intuitive reading is that they are the same
16:11:47	gmaxwell:	By approximation free I mean you can use faulty-sha256() instead of sha256() ... and just try more times, if its faster enough to make up for the faultyness, then it's subject to an approximation speedup.
16:12:15	gmaxwell:	Optimization free means that you can't go twiddle the algorithim around inside and make it much faster while computing the same thing.
16:13:45	gmaxwell:	maybe they're just two sides of the same coin, but I think it's important to note that in the context of POW 'optimization' means a lot more than it does in other cases.
16:15:05	gmaxwell:	e.g. sometimes people suggest using a generic 3sat random problem generator and 3sat solver as POW. but if they did that, I'd replace the solver with a hurestic solver that can't work on most problems but is super fast on what it works on... and grind the problem generator. So much for driving innovation in 3sat solvers. :)
16:17:02	andytoshi:	ah, gotcha. i'll find a way to work that into my faq
16:17:39	gmaxwell:	if you go find my attack on the first proshares POW, I gave two attacks: one was an optimization that cut the memory usage from 128m to 8k— an optimization which didn't change the function. The other was an approximation that made it memoryless (and faster) at the expense of only being right most (? iirc) of the time.
16:27:09	jps_:	jps_ is now known as jps
16:39:23	andytoshi:	ok, i have pushed a new version of the mining doc https://download.wpsoftware.net/bitcoin/asic-faq.pdf
16:39:28	andytoshi:	changes: add "about this doc" which states the thermodynamic thesis and that pow is boring; add section on poisson process/progress freeness; add section on optimization and approximation freeness (cite gmaxwell); remove halting-complete comment; add PoS section
16:39:55	andytoshi:	the only stuff i'm unsure about is the PoS section, because i'm not terribly familiar with it
17:00:03	tacotime:	Is proof of stake really related to this stuff?
17:00:12	tacotime:	It seems like a separate paper on its own.
17:02:40	andytoshi:	tacotime: no, but this was supposed to be a #bitcoin-level faq and it turns up in the same kinda conversations
17:02:49	tacotime:	Ah
17:03:08	andytoshi:	people like asic-resistance for "seize the means of production", they like pos for environmental reasons, it's the same ideology ;)
17:10:39	gmaxwell:	andytoshi: one of the things that amuses me about the "seize the means of production" ... is that the gpu mining space is basically a total monopoly— it's AMD or the highway. If you did manage to make a gpu only asic proof (tm) ... you'd be looking at hundreds of millions in R&D to match it. At least in the mining asic space there is a bunch of competition.
17:16:52	tacotime:	I think when SHA256d ASICs are widely available (as they're quickly becoming), the whole "ASIC resistance" furor will quickly die down.
17:18:17	gmaxwell:	tacotime: people will hook onto whatever advantages they can argue to pitch their altcoins. It doesn't matter if they're good... just that they make for good PR.
17:18:23	koval-:	koval- is now known as koval
17:18:52	gmaxwell:	which is sad in that boring superficial stuff that panders to common misunderstandings tends to make for better PR than more subtle deep advantages.
17:20:42	tacotime:	Well, I hope scam coin profitability starts to approach zero after long enough, too. As Bitcoin continues to close in on double digit USD values, I feel like the hype has been dying down around cryptocurrencies in general.
17:22:34	tacotime:	I have a feeling we'll probably just settle on one "GPU mineable" coin for the people who still want to keep their GPU farms mining (...me) and move forward with our lives.
17:23:57	tacotime:	My opinion is kind of neutral as to whether or not different proofs of work are bad, but it has gotten really boring and aside the point.
17:24:35	tacotime:	*proof of work hashing algorithms, really
17:25:38	gmaxwell:	yea. my feeling too. There are ways that things can be better or worse, but generally it's pretty boring and most of it seems to be shed painting, pushing around small advantages and biases... not terribly interesting.
17:26:35	gmaxwell:	will be sort of darkly amusing if altcoins loudly promoting how they're going to replace bitcoin ultimately kills funding to this whole space.
17:34:59	midnightmagic:	virtually no altcoin AFAICT has basically any expertise in cryptography engineering; the differences are a matter of public perception, which means eventually that which is in love with altcoins will either realign with bitcoin, or align with whatever btc v2 ends up being. Funding it seems to me is almost irrelevant if the developer population size continues to be immortal in the open source sense.
17:36:27	midnightmagic:	although I am heartily amused with what's going on in the coin->coin "trading" laundries.
17:36:58	kanzure:	there's a bunch of people with gpu rigs that are looking for altcoins because they want to be mining. so anything that PRly panders to that desire is going to get a lot of eyeballs.
17:39:08	kanzure:	so i think that their attention might be fueling some of the altcoin craze. interestingly, there might be a way to steal their attention by paying a flat rate for their equipment time. so that will cut off the bottom of that market.
17:39:23	gmaxwell:	kanzure: well one thing that should happen is someone should give them another way to monetize their GPUs.
17:39:46	gmaxwell:	I have no clue why someone hasn't done this yet... your miner should be able to switch to compute jobs if they pay more than mining.
17:40:19	kanzure:	a market like cex.io where buyers can point miners to different stratum urls would be nice
17:40:27	midnightmagic:	I thought it was kind of primitively available in some pool that was doing exactly that..
17:40:34	kanzure:	(so there would need to be a stratum pass-through proxy thing)
17:40:37	midnightmagic:	multitool? multi.. hrm.
17:40:52	kanzure:	multipool.us is just a coin switching pool based on exchange rates, difficulty, etc.
17:41:29	kanzure:	but it's a single stratum url and it's up to the pool operator to choose the distribution of work
17:42:03	gmaxwell:	yea, but mining is just more of the same stuff. I mean people talk about wanting to have 'productive' POWs, but they don't even seem to bother implementing these productive functions in a way that people could pay miners to run them, regardless of the extra complexity of making it a POW.
17:42:16	tacotime:	gmaxwell: Ripple has a thing like that over at https://www.computingforgood.org/
17:42:29	tacotime:	But I don't want XRP :P
17:42:30	kanzure:	what happened to all the boinc stuff?
17:42:53	gmaxwell:	yea, but not really. it's just the boinc stuff, e.g. a charity thing, not actually a compute service where you can buy and sell resources.
17:43:18	kanzure:	oh interesting, i had assumed that boinc had a way of tracking actual resource usage or something
17:43:56	kanzure:	in retrospect i can see why this assumption is bad :)
17:47:03	midnightmagic:	Imagine that. Mass-cooperative GPU power.
17:47:04	midnightmagic:	* midnightmagic shudders.
17:49:06	nsh_:	nsh_ is now known as nsh
18:10:33	nsh:	amiller_, is there anything i can read about the thorough-mixing redundant information syndication work you were talking about with gmaxwell recently?
18:10:49	nsh:	("holographic storage" as it was (evilly) dubbed)
19:09:25	bobke_:	bobke_ is now known as bobke
19:26:41	gmaxwell:	an argument for covenants, and delegation in script. It would be nice if your public key could sign a 'sweep script' which could be used to redeem any coin paid to you and send it on to a different address of yours. allowing sweeping without keeping a private key online.
19:28:41	nsh:	* nsh nods
19:29:20	hearn:	gmaxwell: that reminds me. i was wondering if SCIP would let us resolve the old “can bitcoin pow be used to achieve some social good” question. e.g. if you had a program that folded a protein, could the block PoWs be a proof that you ran lots of foldings, possibly collapsed up into a tree by running proof verification itself under the prover (i.e. you collapse a tree of proofs into a single root proof)
19:32:23	gmaxwell:	hearn: not clear, there are a couple of challenges. From a theoretical perspective, the PCP theorm says that the statement is true, not that you did the underlying work. It's not hard to construct examples where you could algorithmitically optimize the prover work (e.g. short cut it), but maybe it doesn't matter in practice. The other issue is, of course, all this stuff starts off with an insane (e.g. 10000x) slowdown, so the ...
19:32:30	gmaxwell:	... benefit of doing something 'useful' but very slowly might not be so great.
19:33:04	gmaxwell:	but indeed it might be useful for speeding up slow verification.
19:33:34	hearn:	right. it seems like giving people a monetary incentive to optimise proving is not so bad - not much different to optimising by making ASICs
19:33:42	hearn:	except that it’s a lot more useful than SHA256 ASICs
19:33:57	sipa:	hardware SCIP chips!
19:34:06	hearn:	why not?
19:34:31	hearn:	i bet parts of it are quite amenable to hardware. given that their latest version has a kind of universal circuit ….
19:34:54	Luke-Jr:	sipa: I did mention that to a few ASIC manufs ;)
19:35:58	gmaxwell:	right now the prover granularity is pretty poor. e.g. you're not very progress free if a single attempt takes 1 minute.
19:36:16	hearn:	progress free?
19:37:09	gmaxwell:	fastest miner usually/always wins.
19:38:00	hearn:	oh, i see
19:38:02	nsh:	"To guarantee this, the computation of proof-of-work must be progress free, that is, the proof-of-work calculation at time T should not depend on any part of a calculation at time T < T ."
19:38:27	nsh:	(that's a bit notationally unclear, btw, andytoshi)
19:38:41	andytoshi:	there should be a ' after the first T..
19:38:45	sipa:	T < T_now ?
19:38:52	sipa:	ah
19:38:53	nsh:	oh, there is. copypaste problem
19:38:54	nsh:	sorry
19:39:30	nsh:	* nsh blames pdf
19:40:51	hearn:	actually i’m not sure i see that. if the input space is very large and miners explore it randomly, does 1 minute vs 0.001 seconds to run the calculation make a big difference? as long as you can abort and restart when a new block is found, it seems like it should not advantage fast miners any more than regular pow does
19:43:25	nsh:	* nsh could do with a deeper understanding of the exact relation between poisson process and decentralization
19:44:03	kazcw:	wouldn't it incentivize continuing to work on a competing block (until the end of the PoW attempt) when a new block comes out?
19:44:35	hearn:	i don’t think so. not if the first-seen rule is kept
19:44:51	sipa:	it mostly encourages cartelization/pooling, as your hardware is unable to do a single try in ~minutes, it is completely useless (much more than proportionally)
19:44:52	hearn:	even if you finish your current program and by luck also find a good solution, you still arrived 30 seconds too late
19:44:57	nsh:	the smaller the progress granularity the better incentive to include freshly-relayed transactions
19:50:33	nsh:	so i can intuit vaguely that in the limit of progress-free work running-time and computational-resource are continuously commensurate and that reduces cartel advantage but it's less clear how the incentive changes exactly as this granularity increases and at what scales the effect become dominant
19:50:35	gmaxwell:	hearn: I don't know how fast it needs to be in practice, it needs to be very small per try with respect to the interblock time. But I don't have a better critieria than that.
19:50:43	nsh:	* nsh nods
19:51:35	sipa:	minute seems to long already; it would result in several % loss compared to proportional, afaict
19:51:37	nsh:	(these are the things that more scientifically-varying alts could help discern)
19:53:55	nsh:	"e.g. by using a bad multiplexer which cannot demux certain bitstrings." <- interesting... is this a viable approximation method?
20:04:24	kanzure:	heh counterparty users run into a problem where their ability to transact is limited by the number of (non-zero balance) addresses they control, something like 2**(n-1) where n is block height since they received the asset will define the maximum number of addresses they can control (and thus their throughput per-block for sending assets). they should really allow for multiple outputs.
20:08:11	kanzure:	oh i guess you can reach a reasonable limit within a few hours anyway
20:08:23	kanzure:	s/few hours/few hours of blocks/
20:21:00	Guest43376:	Guest43376 is now known as amiller
20:22:20	amiller:	hearn, a lot of what you're asking is addressed in the permacoin paper http://cs.umd.edu/~amiller/permacoin.pdf
20:23:03	amiller:	especially the part about what loss do you get when you have to restart due to someone else finding a solution in the middle of you making one attempt
20:23:33	nsh:	amiller_, is there anything i can read about the thorough-mixing redundant infor
20:23:41	gmaxwell:	nsh ^
20:23:42	nsh:	mation syndication work you were talking about with gmaxwell recently?
20:23:48	nsh:	ah
20:23:54	nsh:	* nsh reads
20:24:04	gmaxwell:	I didn't know the link or I would have answered earlier. :)
20:24:10	nsh:	* nsh smiles
20:24:32	amiller:	well the thorough mixing part isn't really in there, that discussion was about a problem with this paper i still need to fix.
20:24:45	nsh:	ok
20:32:46	andytoshi:	nsh: the "bad multiplexer" i was imagining was to just splice the wires together, then you can read 11 or 00 but not 01 or 10 ;) and you can do it twice as fast
20:33:25	nsh:	* nsh nods
20:33:35	andytoshi:	imagine that you had part of your algorithm where 90% of the time two bits were equal, maybe there's an advantage there. but idk, i'm not a hw guy and i'm just making things up
20:33:46	nsh:	right, plausible though
20:34:25	nsh:	it'd be interesting to make a programming language with fine-grained probabilisticness controls
20:34:34	BCB:	any of you wizards know how to hash a block header?
20:34:35	andytoshi:	thx amiller, i care about this question too because i want a snarkcoin
20:34:35	nsh:	maybe such exists already
20:35:00	nsh:	/topic [...] Hunting of the Snarkcoin
20:35:04	nsh:	:)
20:37:00	nsh:	heh, this is pretty funny: http://blog.pecuniology.com/2013/12/
20:37:07	nsh:	"A Proof-of-Snark (POS) protocol deters denial of service attacks and other service abuses such as spam on a network by requiring some original snark from the service requester, usually meaning a sardonic summary of the request, typically in the form of dry or biting understatement."
20:40:31	andytoshi:	"It is critical that the summaries be true, otherwise they do not summarize the blocks with which they are associated, placing the system at risk." classic
20:43:23	nsh:	* nsh smiles
20:53:54	midnightmagic:	nsh: HAHA thanks for the link. :)
20:57:59	gmaxwell:	andytoshi: so, on asic-faq how and why is it used. The cost of POW also puts a floor on the returns for an attack for an attack to be profitable. For the subset of attackers motivated by profit a sutiable POW can make some kinds of attack non-viable.
20:59:47	nsh:	yw:)
21:01:25	gmaxwell:	andytoshi: I'm not sure about your " ASIC’s bring with them a risk of manufacturer centralization, such as what we
21:01:28	gmaxwell:	currently see with Bitcoin"
21:01:55	phantomcircuit:	i give up
21:01:58	phantomcircuit:	stupid nvidia drivers
21:02:05	phantomcircuit:	back to nouveau
21:02:07	gmaxwell:	the comparison for "ASICs" in bitcoin is cpus and gpus, and the latter are more centeralized than bitcoin asics are. (in that there are more viable bitcoin asic makers than ... AMD)
21:02:46	gmaxwell:	maybe the latter comments do enough to undo any confusion there.
21:02:57	phantomcircuit:	gmaxwell, have you played with the spondoolie box yet?
21:03:36	gmaxwell:	phantomcircuit: yea it's great.
21:03:47	gmaxwell:	though... loud.
21:04:04	gmaxwell:	andytoshi: another issue with primecoin is that the proofs are rather large, I believe.
21:04:41	gmaxwell:	andytoshi: on memory hardness deirable you should perhaps mention TMTO.
21:05:00	gmaxwell:	(as potentially an example of an optimization-freeness failure)
21:06:43	gmaxwell:	andytoshi: I think amiller actually coined "nothing at stake" (but if he says it was me I'll buy that, but I think it was him.)
21:06:57	phantomcircuit:	gmaxwell, really? i thought it was relatively quiet :P
21:07:17	amiller:	yes i claim full credit for "the problem with every existing proof-of-stake scheme is that nothing is at stake"
21:07:39	gmaxwell:	thats good because I've been pretty consistently blaming you for it. :)
21:07:43	amiller:	:p
21:08:02	gmaxwell:	phantomcircuit: it's a lot louder than the cointerra box at least... easily the loudest miner I've ever used.
21:08:25	phantomcircuit:	gmaxwell, the fans dial back if the machine gets cooler
21:08:33	phantomcircuit:	possibly you're just running it hotter than i am
21:09:36	phantomcircuit:	i had it in a room in an office that is very cold due to retarded hvac
21:09:43	gmaxwell:	might also be a firmware difference, I'm not on the very latest firmware becaues every time I've updated it through the webui has bricked it.
21:09:59	phantomcircuit:	all the ducts vent into closed office space, sensors are in the common area
21:10:00	gmaxwell:	(requiring a recovery via the microsd)
21:10:07	phantomcircuit:	result, offices are 60F
21:10:19	phantomcircuit:	gmaxwell, hmm yeah this is running the latest one
21:10:33	phantomcircuit:	i think these are all a bit "developmenty"
21:10:49	phantomcircuit:	this one has some broken chips (which they knew about before shipping it)
21:12:24	gmaxwell:	ah, this unit is 100% though they've recommended I run it in quiet mode because I have it on 110v. I'm really darn near out of power right now.
21:12:57	phantomcircuit:	gmaxwell, lol yeah the PSU is rated below what they're actually doing
21:13:48	gmaxwell:	its latency is not quite as good as the cointerra box, but still quite acceptable.
21:15:32	gmaxwell:	amiller: is there an updated version of that systemizing knowledge bitcoin overview paper? I found a copy on github but the last commit was months ago.
21:15:50	phantomcircuit:	gmaxwell, yeah it seems like it's all around a much better system than the cointerra machines
21:16:03	amiller:	no not yet, i'll let you know when i finish the next draft which i promised everyone else i'd do this week
21:18:22	gmaxwell:	phantomcircuit: yea, I wish they were better priced however.
21:18:46	gmaxwell:	Their initial price was high but okay, but as they sold out they moved into preorder land while holding the prices costant. fucking @#$@#$@ miners.
21:22:06	andytoshi:	amiller: cool, i'll update with your citation
21:22:24	andytoshi:	gmaxwell: today there are like 2 asic manufacturers i thought? also can you remind me what TMTO stand s for?
21:22:35	phantomcircuit:	gmaxwell, im thinking their production cost is somewhere around $1.5/Gh/s
21:22:50	phantomcircuit:	i believe the lowest anybody can go is about $1/Gh/s
21:23:07	phantomcircuit:	28nm they save on the components
21:23:08	gmaxwell:	time memory trade off. E.g. a plain collision POW can be done in a memory-full way or you can use some more computation and do it in a less memory or nearly memoryless way.
21:23:12	phantomcircuit:	40nm they save on the chips
21:23:27	andytoshi:	oh that's right
21:23:29	phantomcircuit:	in the end i think $1/Gh/s is close to what the marginal cost per unit is for both
21:24:27	gmaxwell:	andytoshi: BFL, knc, bitfury, bitmain (who's chips may be really bitfury in disguise), cointerra, hashfast, and spondoolies all have their own chips fabricated (with the noted concern). There are some additional ones I'm less familar with that others might chime in with.
21:25:02	nsh:	/topic Chips Challenge
21:25:09	andytoshi:	oh, excellent. i'll change that to "as we saw with Bitcoin during the initial ASIC rollout" then
21:25:10	gmaxwell:	andytoshi: the cuckoo cycle one supposidly is TMTO optimization free, but I only know the claim.
21:26:17	phantomcircuit:	gmaxwell, im 99% certain bitmain it bitfury
21:26:40	phantomcircuit:	gmaxwell, blackarrow doesn't even have a finished design yet
21:27:17	phantomcircuit:	the 21e6 guys dont seel to the public
21:27:28	phantomcircuit:	but apparently their initial design just completely didn't work
21:27:45	phantomcircuit:	and some rumors about them blowing 10m to build out crazy watercooling shit
21:29:59	gmaxwell:	phantomcircuit: I do note the spondoolies box follows my favored design, — sea of low cost chips.. none of this crazy multichipmodule and water cooling crap.
21:31:12	phantomcircuit:	gmaxwell, i did notice that their heatsink doesn't work exactly right
21:31:36	phantomcircuit:	a few of the chips run at 113C while the rest are around 70C
21:32:32	Luke-Jr:	gmaxwell: sipa: did anyone ever discuss pegging which can handle side-chain to side-chain transfers?
21:34:23	phantomcircuit:	that reminds me
21:39:11	phantomcircuit:	with a merged chain
21:39:27	phantomcircuit:	once you've gone past a block in which the block was also valid in bitcoin
21:39:53	phantomcircuit:	it would be nice if that couldn't be reorganized without the bitcoin block also being reorganized
21:39:58	phantomcircuit:	(or is this already the case?)
21:40:09	gmaxwell:	if thats how the merged thing wants to work. But thats not how namecoin works.
21:40:56	gmaxwell:	and yea, that may have advantages though it does make the systems non-independant.
21:55:56	zzyzx:	zzyzx is now known as roidster
21:56:26	roidster:	roidster is now known as Guest23156
21:57:59	phantomcircuit:	gmaxwell, it would basically act as a checkpoint
21:58:03	phantomcircuit:	unfortunately the part of the network that does namecoin merged mining is also the part most people are worried about
21:58:06	phantomcircuit:	i believe basically half the network is doing merged mining
21:58:25	sipa:	i heard like 90%
21:58:37	gmaxwell:	it's mid-80 percent of the hashrate when you measure.
21:59:04	phantomcircuit:	guess it went up since i last checked
21:59:10	phantomcircuit:	it was like 50% the first time i looked
21:59:18	phantomcircuit:	at the time that was like 85% ghash.io
22:00:16	gmaxwell:	you might have looked during the span when some of the large pools had stopped running it.
22:01:16	phantomcircuit:	probably
22:01:18	phantomcircuit:	i thought it was weird
22:03:04	andytoshi:	updated asic-faq.pdf with amiller credited for "nothing at stake", a note about TMTO added ("it complicates analysis"), changed bitcoin's asic centralization to past-tense, and added a note about primecoin having large proofs
22:04:18	phantomcircuit:	blargh primecoin
22:04:34	phantomcircuit:	momentovps had the biggest problem with people cpu mining primecoin
22:04:40	gmaxwell:	hm. andytoshi did you verify that? I believe they do but I'm not completely sure of it.
22:05:06	gmaxwell:	(in theory they could be made small by only commiting to their non-determinstic initilization, but I don't think thats what they do)
22:05:12	andytoshi:	i ran it for a few days, i'll check the source..i recall it taking forever to sync despite having no transactions
22:05:32	gmaxwell:	yea, well part of that is because they do @#$@ primality checking for verification.
22:05:40	andytoshi:	:}
22:05:51	gmaxwell:	(hurray: not totally crazy, they use determinstic randomness so the network would be consistently wrong if it were wrong)
22:06:45	andytoshi:	hey, nice, i wondered about that
22:13:19	andytoshi:	fwiw if you run getblock, it returns a long hex string "primeorigin" which seems like an initialization state
22:21:04	|Ryan52:	|Ryan52 is now known as Ryan52
22:21:38	andytoshi:	ok, i think the contents of the proof are in main.h:1281, it's one extra bignum
22:21:41	andytoshi:	// Primecoin: proof-of-work certificate
22:21:43	andytoshi:	// Multiplier to block hash to derive the probable prime chain (k=0, 1, ...)
22:21:45	andytoshi:	// Cunningham Chain of first kind: hash * multiplier * 2**k - 1
22:22:05	andytoshi:	that's not so big, i'll just say the proofs are expensive to validate
22:43:20	gmaxwell:	I had a thought last night on how more powerful script could allow a non-interactive coinjoin.
22:44:22	gmaxwell:	basically if you assume that script had pairing crypto operations (needs G1 multiply, add, and pairing) and really powerful covenants:
22:45:36	gmaxwell:	someone starts a coinjoin by spending a coin and delegating it to a script that verifies that an aggregate signature matches the transaction.
22:46:16	gmaxwell:	then other people join by updating the first signature to add additional inputs and outputs to the aggregate signature, and in their script specifying that their coin can be spent by a transaction including it in the aggregate signature.
22:46:22	gmaxwell:	so you can just pass around the coinjoin.
22:46:38	gmaxwell:	the require that scripts be able to inspect each other in a transaction is particularly ugly, however.
22:48:10	gmaxwell:	perhaps thats not very clear, I think I might be the only person around here who has fully internalized the operation of one way aggregate signatures.
22:48:50	sipa:	i still haven't spent time trying to grasp the properties that pairing crypto provides
22:50:07	Luke-Jr:	hm, nobody answered me :<
22:50:39	sipa:	maaku mentioned that, i think
22:50:48	andytoshi:	yeah, i have the OWAS paper like 3 months away in my buffer :(
22:51:20	gmaxwell:	there are a bunch of ways to think about what pairing crypto does. E.g. not very useful, but correct ones like how over the integers A * B = Z preserves the linearity of Z with respect to A and Z with respect to B. But that doesn't really help get an intution for the cryptographic properties.
22:53:19	andytoshi:	i found the discussion in boneh's IBE paper about how DDH is super easy in the face of a pairing and CDH in one group reduces to the other, helpful for crypto intuition
22:54:23	andytoshi:	also the way it is used in that IBE paper gives a feel for what it can accomplish. though the "3-party shared secret" scheme we sometimes talk about is even simpler
22:55:35	andytoshi:	https://crypto.stanford.edu/~dabo/papers/bfibe.pdf <-- thx adam for that
22:56:20	antephialtic:	The textbook I learned crypto from has a few pretty good sections on pairings. Hoffstein's intro to mathematical cryptography, sections 5.8-5.10
22:57:29	gmaxwell:	Sadly, A lot of the older pairing papers spend a bunch of time talking about supersignular curves and other internals stuff which not needed for using the constructs, and also not very relevant to the particular curves and pairings we'd use today.
23:00:56	andytoshi:	(those things are in the appendix of the paper i linked)
23:05:01	gmaxwell:	in any case, as a total blackbox the OWAS stuff is trivial say you have a set of tuples {message1,pubkey1,signature1}, {message2,pubkey2,signature2}, ... with an ordinary paring short signature... the OWAS stuff just gives you a way to aggregate the signatures, → {message1,pubkey1}, {message2,pubkey2}, ... , signature_composite and a new verification procedure. (which is the same as the original normal signature in the single ...
23:05:08	gmaxwell:	... message case)
23:05:44	gmaxwell:	(and some security proof that tells you that if you can deaggregate the composite signature you can solve a computation DH problem in the relevant group)
23:06:21	gmaxwell:	the aggregation isn't just one shot you can take a signature_composite and keep adding more signatures to it.
23:07:14	gmaxwell:	the neat thing about the OWAS bitcoin paper is this rather clever idea of how you can use this to create a kind of mixing ring...
23:08:01	gmaxwell:	were you add two messages to the aggreate: one proving your identity, and the other signing your message. Then other people add their pairs of messages, and you can no longer tell which identity goes with with which message.
23:08:30	gmaxwell:	but someone cannot disassemble the signature to rebind your identity to a mixing-ring that lacks your message.
23:12:18	gmaxwell:	there are perhaps some other interest applications for this stuff... e.g. jamming resistant networks. without OWAS you can make your messages contain a hash of all prior messages, so someone can't undetectably censor prior messages without censoring yours... but if you use OWAS then third parties could aggregate your messages with other messages such that censorship is an all or nothing thing.
23:17:40	phantomcircuit:	lol i just noticed something
23:17:51	phantomcircuit:	ovh randomly forces 1gbps servers to renegotiate to 100mbps
23:17:55	phantomcircuit:	sneaky
23:18:08	gmaxwell:	may just be faulty not sneaky.
23:18:26	phantomcircuit:	gmaxwell, possibly
23:18:41	phantomcircuit:	but the switch is supported to auto renegotiate if there's a fault like that
23:18:53	phantomcircuit:	i guess i need to run a cron script to renegotiate every hour
23:18:55	phantomcircuit:	:/
23:24:25	justanot1eruser:	andytoshi: based on the name I would guess that's what I'm referring to
23:29:43	andytoshi:	justanot1eruser: cool, at the end of https://download.wpsoftware.net/bitcoin/asic-faq.pdf there is now a section on 'nothing at stake'
23:35:36	phantomcircuit:	gmaxwell, i was wrong the switch is broken
23:35:42	phantomcircuit:	their bandwidth meter shows me having used no bandwidth for a month
23:35:45	phantomcircuit:	brilliant work
23:39:23	justanot1eruser:	andytoshi: cool, thanks
23:40:54	maaku:	andytoshi: meh ... proof-of-stake wasn't always and shouldn't imho be associated with mining
23:41:56	gmaxwell:	^ hm. thats a point. The nothing-at-stake problem only arises out of POS for consensus.
23:42:11	maaku:	the original proof-of-stake discussions were mostly about using PoS voting to select checkpoints (e.g. imagine GHOST with PoS votes adding weight instead of stale blocks)
23:42:24	andytoshi:	maaku: the original point of this doc was to answer #bitcoin questions about alternate mining schemes, i think PoS fits into that category
23:42:43	gmaxwell:	yea, there is that jdillion proposal for setting block sizes where you use POS to get permission to increase the block sizes.
23:42:44	maaku:	then ppcoin/peercoin went off the crazy end by using it for consensus
23:43:02	andytoshi:	oh, i didn't know the historical order there
23:43:10	gmaxwell:	andytoshi: it might be worthwhile to just have a mention that PoS may be useful for non-consensus things without these issues.
23:43:12	maaku:	andytoshi: yes, but you could make it an educational moment, is what I'm saying
23:43:46	maaku:	proof of stake is pretty awesome (provided we can solve the vote censoring problem...), just not for mining/consensus
23:44:06	gmaxwell:	maaku: jdillion solved the censoring problem by making the vote one sided.
23:44:32	andytoshi:	lol, and now we're into -wizards stuff that i don't know about..
23:44:49	andytoshi:	if one of you guys wants to write a "what is PoS good for?" entry, i'm happy to include it
23:45:07	maaku:	gmaxwell: I'll have to go read that again. I think I was aware of these issues the first time around
23:46:01	gmaxwell:	On this is point petertodd and I were talking about that PoS parameter voting thing and refind it some. The revised idea is this: when a block is found the hash determinstically selects a couple prior txouts. Those selected txouts can now produce a signed message, including the block hash (so they can't be precomputed), indicating their vote, which can be included in subisquent blocks.
23:46:20	maaku:	"However, it does not appear that there is a viable way to achieve consensus through proof of work" <-- should be proof of stake, no?
23:46:34	andytoshi:	oh :P yes
23:47:25	gmaxwell:	The argument as to why you could adjust the block limits through this procedure is that the votes only allow you to increase, the fact that someone can censor out increase votes is not terribly relevant since the censors can just exclude transactions.
23:47:52	maaku:	ah
23:48:58	maaku:	unfortunately not relevant to my republicoin quest :( but a cool result
23:49:08	gmaxwell:	the refinement with the determinstic subset is to keep the scaling sane. The refinement with including the block hash in the signed message is so the miners can't demand you precreate your vote before including your transaction in a block in the first place.
23:49:13	gmaxwell:	yea, not a general tool.
23:49:21	gmaxwell:	and sadly probably too complex to bother implementing.
23:55:37	maaku:	gmaxwell: the description of non-interactive pairing coinjoin is very clear, and very cool
23:56:41	maaku:	Luke-Jr: the version of pegging I have in mind is 100% symmetrical, so it doesn't matter what chain you are moving to/from
23:56:50	maaku:	you can have arbitrary graphs of value movements
23:58:13	gmaxwell:	I just dont know if it's reasonable to make transaction introspection powerful enough to actually do that though... the OWAS part is trivial to implement. I'm not quite sure how "Go look in scriptsig0 and make sure the prefix has hash x and value y someplace in the suffix" would look like.
23:59:27	andytoshi:	maaku: i added a "is proof of stake good for anything?" question to the asic faq to say "lots of stuff, just not distributed consensus"
23:59:40	maaku:	andytoshi: cool, thanks
23:59:46	gmaxwell:	yea, thats good.