--- Log opened Sun Jun 02 00:00:57 2013 00:01 < amiller> well he was really clear about encouraging people to email him if interested :) 00:01 < realazthat> I have 00:01 < realazthat> thu night 00:03 < realazthat> and he just responded! 00:03 < realazthat> so I was asking the other day, if it is a good PoW 00:04 < realazthat> even if it is an easy problem, just a bad algorithm 00:04 < realazthat> answer is yes 00:04 < realazthat> Q: "Is there a guarantee that there is no way to generate a signature if a correct answer is otherwise found in a quicker manner than running `P`, the original program, via running `Q` instead?" 00:04 < realazthat> A: "Yes, the only way (assuming you cannot break crypto) is to run P, not Q." 00:04 < realazthat> Q: "I heard a rumor that you are using LLVM; if so, is it possible that any/most (possibly restricted?) LLVM programs can be used to generate such a proof (obviously can be done via the defunct "C back end" as well)? If not, disregard this question." 00:04 < realazthat> A: Wrong rumor. The top level uses a gcc backend. But really our pixie-dust is sprinkled after we have assembly code for a specific virtual machine and we would like to get a decent LLVM compiler for it as well. 00:05 < realazthat> mmm I would be interested in doing that 00:05 < gmaxwell> their machine code is really simple. 00:05 < realazthat> yeah 00:05 < realazthat> mmm can you link their stuff on that if there is any? 00:05 < realazthat> I want to see the vm 00:05 < realazthat> tinyram? 00:06 < gmaxwell> shits, mul, add, sub, cmov, add, xor,not, load, store, and ~5? iirc compare operators. 32 32-bit registers. 00:06 < realazthat> mmm 00:06 < realazthat> dunno why they didn't just do LLVM in the first place 00:06 < gmaxwell> (er replace second add with _and_) 00:07 < gmaxwell> because they need to know how to convert each of the operators to a set of constraints on how it updates the program state. 00:07 < realazthat> oh no I know that 00:07 < realazthat> thats fine 00:07 < realazthat> I mean LLVM => tinyram 00:07 < gmaxwell> Ah. Yea, no clue. 00:08 < gmaxwell> probably the compiler person on their team knew gcc internals already? 00:08 < realazthat> this would be a really sweet LLVM backend hehe 00:08 < realazthat> yeah 00:08 < realazthat> as soon as its out, I'll see if I can do something with LLVM 00:08 < realazthat> LLVM has a defunct C backend as well 00:08 < realazthat> but I'd rather see something more direct 00:08 < realazthat> seems simple enough 00:09 < gmaxwell> I imagine a lot of the most interesting stuff will just end up as handcoded tinyram eventually... C gives you rapid bootstrapping. 00:09 < realazthat> mmm maybe 00:09 < realazthat> because of performance? 00:10 < gmaxwell> Yea, at least their first generation stuff requires a lot of fast memory to compile to their constraint program. It's polynomial, but the constants are big enough that hand optimizing will be worth it for many things. 00:11 < realazthat> yeah the 1st gen is .. not optimal 00:11 < realazthat> I saw that slide 00:11 < realazthat> er 00:11 < gmaxwell> also, dunno if you've spent much time looking at compiler output ... well, there are a lot of sins which are more forgivable on modern hardware with things like branch prediction and reordering nearly free register to register motion, etc. compared to this enviroment. 00:11 < realazthat> or do you mean in general, 2nd stage included 00:12 < gmaxwell> No, I meant first. I don't quite fully grasp the performance implications of the second generation stuff. 00:13 < realazthat> mmm, I'll write up a second email with some followup questions 00:13 < realazthat> including my recursion idea 00:14 < gmaxwell> The recusion idea sound like the ram binding stuff itself, to some extent. 00:14 < realazthat> ah I am not familiar with that; probably over my head :/ 00:15 < gmaxwell> (the idea that if you prove the state transistions and you prove the ram state you can arrange these operations in graphs and prove the compositons then the compositions of the compositions) 00:15 < gmaxwell> it's in that paper I linked to the other day. 00:15 < realazthat> ah 00:16 < gmaxwell> It's a little frustrating to me, because I have enough background to undersand basically all of the parts... but the whole of it is a bit too specialized for me to follow in detail. 00:16 < realazthat> yeah I was thinking about how SCIP would work internally (without ever having read anything on it) 00:16 < gmaxwell> er understand. 00:16 < realazthat> heh, for me it is hard to imagine 00:16 < realazthat> but I imagine it is a bunch of cool tricks in this vein 00:16 < gmaxwell> the RS code and proximity proofs for the PCP stuff was pretty mind blowing to me. 00:18 < amiller> does this even need any PCP 00:19 < amiller> i can't figure out how to reconcile all the different terms, many verifiable computing things explicitly say they don't need any PCP which is desirable because PCP usually implies exponentially additional work for Prover 00:19 < gmaxwell> go read Eli's paper on how they solve that. 00:19 < gmaxwell> lemme find link 00:21 < gmaxwell> http://people.csail.mit.edu/madhu/papers/2005/rspcpp-full.pdf and then http://eccc.hpi-web.de/report/2012/045/ 00:23 < amiller> i see "Although we also construct simpler PCPs, our approach by contrast relies on adding algebraic structure instead of combinatorics." 00:23 < amiller> they also mention something by Dinur that presumably also gets quasilinear blowup (which is probably tolerable) 00:28 < amiller> ok so fuck it we'll be able to code a single utxo branch checker and then validate the whole block chain in constant time, that's totally exciting 00:29 < amiller> then the splitting hairs thing is to try to get these proofs constructed collaboratively 00:30 < amiller> they're already set up to be built incrementally which is good 00:30 < gmaxwell> (the second cite I just gave even mentions "recursively compose non-interactive proofs") 00:39 < realazthat> mmm 00:39 < realazthat> that sounds something like what I suggeste 00:40 < realazthat> at least by the name lol --- Log closed Sun Jun 02 02:09:08 2013 --- Log opened Sun Jun 02 02:09:22 2013 02:50 < amiller> every advanced crypto concept is just a) complicated thing b) compicated thing c) merkle tree on top of complicated things d) complicated thing 02:50 < warren> Don't forget the hand waving. 12:09 < realazthat> I invited eli to #bitcoin-dev and #bitcoin-wizards 12:09 < realazthat> dunno if he has the time lol 12:09 < realazthat> but would be cool 22:04 < realazthat> mmk 22:04 < realazthat> got eli's response 22:04 < realazthat> Q: How does SCIP cost O(T(P)) time to generate P' for Alice, if there is no way of knowing how long P will run (halting problem)? I assume there is some bound that must be chosen then? If Bob runs longer then this bound, I assume it will fail? 22:04 < realazthat> eli: Part of the problem definition is a time bound. And we assume wlog that if the execution shoots over it then it fails. Thus, the halting problem is not an issue. 22:05 < realazthat> Q: Why can't a simple 1-level recursion reduce Alice's required generation time? That is, Alice verifies a verification function was run on chained runs of a smaller task, which sum up to P? I think this can get the generation time to sqrt(T(P)). And possibly lower, if it is done with more levels of recursion. 22:05 < realazthat> eli: Good idea, this is known as "bootstrapping" but getting it right is far from trivial. There are a few works on the topic, such as by Paul Valiant (titled "incrementally verifiable computation"), and by Chiesa and Tromer (called "Proof carrying data and heresay arguments") and more recently by them+Bitansky, cannetti, titled Recursive composition and bootstrapping for SNARKS and proof-carrying data. 22:05 < realazthat> PS. if you have time to answer more questions, I would love to chat with you and/or other people knowledgeable/interested about the project on IRC. Several interested people hang out on the freenode network in #bitcoin-dev and #bitcoin-wizards. 22:05 < amiller> righteous 22:06 < realazthat> eli: I would be happy to hang out some time with some of my collaborators, how does this work? 22:06 < realazthat> PPS. I would also love to attempt/start an LLVM backend to tinyram for my personal gratification of playing with LLVM and tinyram. 22:06 < realazthat> Will forward this to my co-PI and let's see how to get it to work, will get back to you on this. 22:06 < realazthat> mmk, now I have to give him instructs on getting on here :D 22:09 < realazthat> I wonder if we should setup some sort of official Q&A 22:10 < realazthat> in #bitcoin-dev 22:10 < realazthat> because his wording indicates a one-time deal 22:42 < amiller> mailing list threads are usually pretty good too 22:55 < realazthat> oh shall I invite him to the bitcoin ML? 22:55 < realazthat> I am not subscribed myself 22:55 < realazthat> subscribed to too many MLs lol 22:59 < amiller> maybe it would be nice to make a forum thread about his talk and how to actually begin a project on it? 22:59 < amiller> if you want to solicit more open ideas / support / help from the community 22:59 < amiller> or if you want to do it mostly yourself you could just pick anyone you can find (maybe people in here i guess) and include them on an email 23:00 < realazthat> mmm 23:01 < realazthat> I assumed there were people talking about this elsewhere on the forums 23:01 < realazthat> I don't really follow them 23:01 < realazthat> but I have his attention, I am just wondering where it is best to direct it 23:01 < realazthat> as for working on applications of it, that's a separate story I think, no 23:02 < amiller> link to the forum threads? 23:03 < amiller> (why not look for them) 23:03 < realazthat> mmmyeah 23:03 < amiller> i'm also not sure where best to direct it 23:03 < realazthat> it seems a bit silent about SCIP hehe 23:03 < realazthat> on the forums that is 23:04 < realazthat> google doesn't turn up much 23:04 < amiller> but i definitely have the sense that it's really exciting to have high powered cryptographers taking nontrivial (grr, adi shamir) looks at bitcoin and offering to help 23:05 < realazthat> well, I'll keep the Q&As I have answers to 23:05 < realazthat> and post them somewhere 23:05 < realazthat> I have some additional Q&As to ask 23:06 < realazthat> so these are the options: 1. make a Q&A time in #bitcoin-dev, 2. direct eli to the ML 3. start a forum thread, direct him to join 23:07 < realazthat> additionally, start a projects/applications list 23:07 < amiller> i say start with the projects/applications list 23:07 < realazthat> eli himself is interested in such a list :D 23:07 < realazthat> such ideas are golden 23:07 < amiller> he wouldn't be able to prepare one himself though, i doubt he's familiar enough with bitcoin jargon or bitcoins needs 23:08 < amiller> from my point of view the big whammy is to validate the whole blockchain all in one snap he seems to get that too 23:08 < realazthat> well, I meant a general SCIP applications list, but yeah, it has a lot to do with a network like bitcoin 23:08 < amiller> but there are also other cool applications that i think gmaxwell understands the best 23:08 < realazthat> mmm gmaxwell has a BIP on that 23:08 < realazthat> to make spend-outs to things that can verify the done a program 23:08 < realazthat> they* 23:09 < realazthat> also, it becomes possible, possibly, to make a bitcoin-like currency that does arbitrary useful work 23:09 < amiller> so i think he's highly unlikely to be able to devote any engineering attention to telling us what applications are helpful for bitcoin and especially not understanding how to implement them in bitcoin 23:09 < realazthat> and even trades in useful work for currency 23:09 < amiller> for that matter i'm not even sure how to make progress in bitcoin with researchy ideas 23:09 < realazthat> right 23:09 < amiller> although that's the topic of this here channel 23:09 < amiller> you can't just say hey we're gonna put this in bitcoin 23:09 < realazthat> when I addressed him, it was wrt applications in general 23:09 < amiller> but it also is shit to say it's just an altcoin 23:10 < amiller> so the question is always what's a good way to go about building proofs of concept that are interesting because they're relevant to bitcoin and may in some wacky future be meaningful to bitcoin and so it's worth trying them out and keeping this community informed about them 23:10 < realazthat> well I'd love to see some of this directly in bitcoin, ie. mining via useful work, but its huge changes 23:11 < realazthat> but gmaxwell's BIP can be done 23:11 < realazthat> also, blockchain verification can be done 23:11 < realazthat> but PoC is always good :D 23:12 < amiller> zerocoin was pretty successful right people enjoyed it 23:12 < amiller> that was just a simple fork of bitcoin that had some bare minimum implementation of the cryptosauce and it validated a few thousand blocks and such 23:12 < realazthat> mmm cool 23:12 < amiller> so it's like similar in spirit to bitcoin, it's not like "launched" as an altcoin with a bunch of bullshit marketing and trying to get people to buy it 23:12 < realazthat> ah yeah 23:12 < realazthat> I have negative views of the altcoins 23:13 < realazthat> except namecoin 23:13 < amiller> right. 23:13 < realazthat> because it actually has a use 23:13 < amiller> so what would be nice is if we can support resaerchers creating arbitary little forks 23:13 < amiller> perhaps we could help them maintain testnets 23:13 < realazthat> mmm I may try doing that soon 23:13 < amiller> and help them present them to the bitcoin community which is full of very interested people etc 23:13 < realazthat> but I've not touched bitcoin code yet 23:13 < realazthat> only RPC 23:13 < amiller> i created a fork of bitcoin for a class 23:14 < amiller> i mean to write up what i did and put it on the forum actually 23:14 < amiller> like thirty undergrads in networking had to implement bitcoin clients as their final project using the cbitcoin lbirary 23:14 < realazthat> mmm is there a fund for finding exploits in bitcoin, like Google has? 23:14 < amiller> i mean they mostly sucked like they are just learning how to use sockets 23:14 < amiller> hm i don't know explicitly about a bitcoin security bounty... 23:14 < amiller> i woulnd't be surprised if bitcoin foundation would be willing to fund something like that 23:14 < amiller> i think it would be nice if bitcoin foundation could be talked into supporting research coins 23:15 < amiller> so zerocoin isn't code released yet 23:15 < amiller> and it doesn't have a running public testnet or tools or anything like that 23:15 < realazthat> yeah I read their site a few days back 23:15 < amiller> but when they're ready to release it it would be awesome if that kind of sets the standard 23:15 < realazthat> can't say I understood how it works 23:15 < amiller> maybe we can look at what they do and ask ourselves what we could do to make it easier for future researchers to do similar proof of concepts or also what they could do differently to make the proof of concept more meaningufl? 23:16 < amiller> i think things like the testnet in a box are remarkably helpful 23:17 < realazthat> definitely would be useful to easily fork bitcoin and research/hack on it 23:17 < amiller> it *is* pretty easy to fork it i guess it's less easy to... i dunno test whether something is actually good or viable? 23:18 < realazthat> yeah you need several nodes prolly 23:18 < amiller> like a good standard benchmark might be to populate it with a bunch of transactions resembling the existing blockchain and measure how long validation takes or something 23:18 < amiller> i'm trying to think of what zerocoin ran into 23:18 < realazthat> mmm bitcoin should have some sort of testing framework down to a tee 23:18 < realazthat> doesn't it? 23:18 < amiller> becuase they add a seriously attractive feature (truly unlinkable transactions) but the cost is pretty high for validation which means it's totally not going to work in practice yet but how can we show that empirically 23:19 < amiller> no bitcoin has an enormous *testing* bottleneck 23:19 < realazthat> ah because afraid to put new things in, big consequences, hard to test 23:19 < realazthat> I joined the -testing ML 23:19 < realazthat> I read an email or two 23:20 < realazthat> yeah I don't envy the responsibility haha 23:20 < realazthat> someone messes up .. significant part of bitcoin network goes nuts 23:21 < realazthat> mmm well 23:21 < realazthat> if SCIP comes out soon, maybe I'll try to do some stuff with it, fork bitcoin, etc. 23:22 < realazthat> but I certainly am not experienced enough to even know what to consider a good test haha 23:22 < amiller> i think SCIP is likely really oversold and is oging to have to go through several iterations of "resaerch prototype" phase before anything practical comes out of it 23:22 < amiller> but it will still be really exciting to go throuhg that process and we should be doing it as aggresively as possible 23:23 < realazthat> well ... 23:23 < realazthat> he did say "stages" himself 23:23 < amiller> including summarizing what's possible for everyone interested 23:23 < realazthat> I am just over-excited about starting to play with it even with suboptimal code 23:24 < realazthat> amiller: mmm I would be curious if making PoW use SCIP, would this help improve SCIPs code by people wanting to do the work faster 23:25 < realazthat> huge incentive hehe 23:25 < realazthat> also huge incentive to keep it quiet though, but still 23:25 < amiller> how od you mean 23:25 < amiller> i have a few ideas of how to combine SCIP with pow 23:26 < realazthat> well SCIP can directly be used as PoW; it guarantees someone ran program P 23:26 < realazthat> so if you make a researchcoin/altcoin with that as mining, 23:26 < realazthat> or, 23:27 < realazthat> you use gmaxwell's BIP to post incentives to complete a particular task for payment 23:27 < realazthat> then peoeple will be running intensive SCIPs for coins 23:27 < realazthat> and SCIP is basically a slow VM 23:27 < realazthat> with relatively high constants 23:28 < realazthat> and room for code improvement 23:28 < realazthat> thus, there would be huge coin insentive to hack on the SCIP code and improve it 23:28 < amiller> we don't really want PoW though :) 23:28 < amiller> because 23:28 < amiller> suppose we could have a really long proof of work 23:28 < amiller> such that as soon as you finished it you were surely going to be a winner 23:28 < amiller> except that 23:29 < amiller> as soon as anyone else finishes faster 23:29 < amiller> you have to discard all your computatoin and start over again! 23:29 < realazthat> ah well you mean for mining 23:29 < amiller> it's really important that the actual work (e.g., just computing a single hash) is really small 23:29 < amiller> yeah 23:29 < amiller> that's what i mean 23:29 < realazthat> ok so thats part of what I mean by significant changes 23:29 < realazthat> so here is my idea(s) on that 23:30 < realazthat> imagine a network that is primarily focuses on trading compute time for work 23:30 < realazthat> using gmaxwell's BIP 23:30 < realazthat> so you can make money by doing work 23:30 < realazthat> nvm mining 23:30 < realazthat> the lottery could be slightly different 23:31 < realazthat> it could be played among all workers 23:31 < realazthat> and you take sha(sig(P)), and have to test that against the upper-limit-number 23:31 < realazthat> so you can't really control that 23:31 < realazthat> and you aren't really mining 23:31 < realazthat> you are trading work for coin 23:31 < realazthat> + a chance to win a lottery 23:32 < realazthat> the guy who wins gets additional coin and mints the block 23:32 < realazthat> so everyone is trading work 23:32 < realazthat> thats the main thing 23:32 < realazthat> its a huge work market 23:32 < realazthat> am I making any sense? 23:33 < realazthat> ofc I miss out a few details 23:34 < realazthat> the sha() must take a few additional params to prove it was started in a recent block, and so can't be reused again and again 23:34 < realazthat> etc. 23:34 < realazthat> there are lots of other issues as well 23:34 < realazthat> I have some of them listed on a page 23:37 < amiller> the work market idea really appeals to me but i don't understand the details 23:37 < amiller> i'd like to read about that 23:37 < realazthat> mmm 23:37 < realazthat> lemme see if I can find gmaxwell's BIP 23:38 < amiller> i think we havea pretty coarse idea about what it takes economically for schemes like this to make any sense 23:38 < amiller> it's real hard to empirically test them 23:39 < realazthat> well the work market could work on the current bitcoin network first I think 23:39 < realazthat> but I don't think people would appreciate deprecating mining :P 23:39 < realazthat> mmm 23:39 < realazthat> yeah 23:43 * amiller waits for cool links 23:47 < realazthat> https://en.bitcoin.it/wiki/BIP_0013 << I *think* this is it 23:47 < realazthat> and maybe 16 23:47 < realazthat> gmaxwell: ding ding 23:48 < realazthat> basically, something that would integrate SCIP into bitcoin, and only pay out to someone who ran a program, and can give a valid response + signature 23:48 < realazthat> ie. scip signature 23:48 < realazthat> which is PoW 23:55 < realazthat> funny, I can't find where gmaxwell linked it to me in my logs :/ 23:57 < realazthat> aha 23:57 < realazthat> got it 23:57 < realazthat> https://en.bitcoin.it/wiki/User:Gmaxwell/why_hash_locked 23:57 < realazthat> amiller: ^^ 23:58 < realazthat> he is using it for the zero-knowledge aspect 23:58 < realazthat> but it could also be used for PoW in the same way as SCIP can be used for both 23:58 < realazthat> I think 23:59 < realazthat> dunno why I thought it was a BIP --- Log closed Mon Jun 03 00:00:00 2013