--- Log opened Mon Jun 03 00:00:00 2013 00:05 < amiller> PoW is a loaded term 00:05 < amiller> i don't think what you're talkinga bout is meaningful as pow 00:05 < amiller> or at least not for mining 00:06 < realazthat> mmm SCIP can do PoW 00:06 < realazthat> look, I'll quote a Q/A from eli 00:07 < 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:07 < realazthat> Eli: Yes, the only way (assuming you cannot break crypto) is to run P, not Q. 00:08 < realazthat> anyway, this isn't for mining 00:09 < realazthat> 1st, is a work market 00:09 < amiller> if it's not for mining it's fine 00:09 < amiller> i think mining doesn't actually use PoW 00:09 < amiller> but something else 00:09 < realazthat> this could be done right now, in the bitcoin chain with this extension 00:09 < realazthat> mmm 00:09 < realazthat> I dunno then 00:09 < realazthat> I am proposing another method of mining, I don't know if it is sound 00:09 < amiller> i've been working on this a lot 00:09 < realazthat> it would obviously have to be in another chain 00:10 < amiller> basically the work should be incremental 00:10 < amiller> like suppose you were going to put out a bid for work 00:10 < amiller> like a bid for having a gazebo built for your house 00:10 < amiller> and you tell the contractors 00:10 < amiller> both of you start working 00:10 < amiller> it should take you about a month 00:10 < amiller> and whichever one of you finishes first gets paid, the loser gets nothing 00:11 < amiller> the fact that bitcoin is *not* even based on PoW at all means its okay 00:11 < amiller> because each incremental unit of work is so small compared to the latency 00:11 < amiller> that the loss due to duplicated work is pretty low 00:12 < realazthat> mm 00:12 < amiller> now if you break a large computation up into tiny pieces 00:12 < amiller> such that you can get *partial payment for partial work* 00:12 < amiller> then we're back on track 00:12 < realazthat> yes, well I was thinking of something like, 00:12 < amiller> which is in fact exactly what those bootstrap recursive snark things seem to be about 00:12 < amiller> which is really really promising then 00:12 < realazthat> a magic protein folding algorithm, which would take in an IV 00:13 < realazthat> and each worker can do his own part of the work-space 00:13 < realazthat> so the workitself would be tiny peices even 00:13 < realazthat> well 00:13 < realazthat> just different peices 00:14 < realazthat> each worker does a different part of the workspace, say by using some uniquely his as the IV 00:14 < amiller> it's a dos problem if you try to pay people for every single hash they compute 00:14 < realazthat> mmno I am not trying to solve that problem 00:14 < realazthat> the work would still take a long time 00:14 < amiller> so the nice thing about lotteries is that they add some uncertainty and indivisibility but you get a good improvement in communication costs 00:14 < amiller> ok 00:14 < realazthat> just it wouldn't be duplicate 00:15 < amiller> and they can be paid even if they're done in parallel 00:15 < realazthat> but its a good problem you pose 00:15 < amiller> that would mean you'd need a block dag sort of thing 00:15 < amiller> that can merge work 00:15 < realazthat> yeah but reserving payment so its not a race; thats a problem 00:15 < amiller> yeah 00:15 < amiller> it might be possible thouhg 00:15 < amiller> it's an interesting idea 00:15 < realazthat> well with gmaxwell's proposal, 00:15 < realazthat> it would almost surely result in some sort of market 00:16 < realazthat> the mining could be built on top of this, by forcing (via mining protocol) the worker to include H(B) into his IV 00:16 < realazthat> and then you can verify the output against the input 00:16 < realazthat> and you know he started at a certain time 00:16 < realazthat> so you cannot save up work 00:17 < realazthat> and, you would win by chance among all the workers 00:17 < realazthat> now, you can weight it somehow (chances of winning) to make it fair 00:17 < realazthat> ie. long jobs have a higher hash-number-limit 00:17 < realazthat> so the difficulty is less 00:18 < realazthat> so, if H(sig(P)) < basedifficulty+T(P) 00:18 < realazthat> then you win 00:18 < realazthat> and get to mine the block in addition to claiming your payment 00:18 < realazthat> T(P) can be proven 00:19 < realazthat> via the sig 00:19 < realazthat> to be correct 00:19 < amiller> well it stucks if you start late then you have no incentive to participate at all 00:19 < amiller> that's another thing that's better about the tiny increment work 00:19 < realazthat> well you always have incentive because of the normal money 00:19 < amiller> you can always join a pickup game at any time 00:19 < realazthat> the lottery is just a side benefit 00:19 < amiller> okay well then just no incentive with the new thing 00:19 < amiller> uh 00:19 < realazthat> most people won't expect to win the lottery 00:19 < amiller> so you can reserve money before acutally completing the work? 00:20 < amiller> what happens if you just don't complete the work? 00:20 < realazthat> oh so thats a good question 00:20 < realazthat> yes, good problem that remains 00:20 < realazthat> I need to think about that 00:20 < realazthat> mmm 00:20 < realazthat> here is what you can do 00:20 < realazthat> one of several things 00:21 < realazthat> the work job is given like this: 00:21 < realazthat> run P(iv), T(P) is the time bound (it is known/given) in instructions, you must complete it by block Y, or you lose; all those that give it by block Y split the coins 00:22 < realazthat> so you can precalculate if you can complete it ontime 00:22 < realazthat> usually 00:22 < realazthat> if you do, you are guaranteed something 00:22 < realazthat> perhaps this will be too unstable 00:22 < realazthat> but I bet the market would adapt 00:22 < realazthat> make sense? 00:27 < amiller> i don't think the market would adapt i think it would be a pretty bad market 00:27 < amiller> the bitcoin mining market is actually super well behaved 00:27 < amiller> the problem is that i think it would be very difficult to tell what chance you had of winning 00:27 < amiller> also a lot of work would still be duplicated likely 00:28 < amiller> with bitcoin mining because everyone is playing the same game, it's really easy to calculate exactly how much you shoudl win *on expectation* 00:28 < amiller> and by joining pools (which maybe could be made endogenous built-in to bitcoin) you can calculate exactly how much you're going to win real accurate 00:29 < amiller> here if you're the only one working on the puzzle then you'll get the whole thing, if someone else works on it you'll get much much less 00:29 < amiller> and you don't even get a reward for being the first to finish 00:29 < amiller> um 00:29 < amiller> i'm not sure how to fix it but maybe we can at least state clearly what the goals should be here? 00:29 < amiller> the decision to do the work should be rational 00:30 < amiller> meaning before you decide to do the work, you should be able to calculate accurately how much money you will get as a function of the decision to do the work or not do the work 00:30 < realazthat> right that would be very hard 00:30 < realazthat> it depends on the type of job 00:30 < amiller> or if it's probabilistic you should be able to calculate what the distribution is of getting paid 00:30 < realazthat> and how many others are willing to do it 00:30 < amiller> again this is a nice thing that bitcoin mining definitely has 00:30 < amiller> and it's obviously important! because that's a lot of how people bitcoin mine 00:30 < realazthat> yeah, so basically you would try to calculate it this way: 00:30 < amiller> they figure out their hash rate and what they earn and try to figure out how cheap they need power etc 00:30 < realazthat> 1. do you have enough power to solve this ontime? 00:30 < realazthat> if yes, 00:31 < realazthat> 2. how many competitors will split the money with you? A: only way to know is to look at the current power directed at this problem 00:31 < realazthat> ie. look at the power beforehand 00:32 < realazthat> gmaxwell's idea is implemented some version of this type of market will happen 00:32 < realazthat> they might use some other incentive, a more stable/predicted one than I suggested 00:32 < amiller> okay so 00:32 < amiller> how do you look at the power directed 00:32 < realazthat> regardless of mining ideas 00:32 < amiller> this is a big thing i'm interested in with bitcoin 00:32 < amiller> is more realtime info about how hash power is allocated 00:32 < realazthat> you look at the last time this program was offered as a job, 00:33 < amiller> right now you get one sample every 10 minutes 00:33 < realazthat> and you see how many people split the money 00:33 < amiller> are the programs offered according to a fixed schedule 00:33 < amiller> that could help sure 00:33 < realazthat> lets say .. yes 00:33 < amiller> okay 00:33 < amiller> the program could always be split into smaller parts 00:33 < amiller> and those parts would be individually payable 00:33 < amiller> the finer grain you split it the more reliable the estimates are 00:33 < amiller> same with bitcoin mining, it's why people join pools 00:33 < realazthat> yes 00:34 < amiller> the only reason not to split it super fine grain is because of communication overhead 00:34 < realazthat> oh well wrt pools, I had some ideas of trying to support pools as a first class citizen 00:34 < amiller> but other than that the finer you make it the more painless it is for everyone involved 00:34 < realazthat> yeah 00:35 < realazthat> a better solution to making multiple workers do the same job maybe 00:35 < realazthat> hmmm 00:36 < realazthat> ok what about a legit lottery 00:36 < realazthat> this would cloud the chain with a ton of txs perhaps 00:36 < realazthat> but lets go with this a sec 00:36 < amiller> sure 00:36 < realazthat> in order to take a job, 00:36 < realazthat> you have to give a certain amount of btc 00:36 < realazthat> to the pool 00:36 < realazthat> lol mixing a lot of concepts here 00:37 < realazthat> ok 00:37 < realazthat> lets also fix jobs to a T 00:37 < realazthat> so that we know the size at an interval 00:37 < realazthat> and everything happens in intervals 00:38 < realazthat> ok so the only reason to actually have "mining" in such a market, 00:38 < realazthat> is to introduce new coins 00:38 < realazthat> because, 00:38 < realazthat> you can really do away with winning coins 00:39 < realazthat> and just have the winner of the mining lottery (not this new lottery) mint the new block in exchange for the tx fees; and he is chosen by lottery of workers 00:39 < realazthat> mmm so let me think 00:39 < realazthat> ok, so here goes 00:39 < realazthat> lets redo this, forget this lottery concept 00:40 < realazthat> 1. units of work are offered 00:40 < realazthat> 2. workers choose their units of work and complete them 00:40 < realazthat> 1.a assume all the units take ~10 mins or less 00:42 < realazthat> 3. worker results in an answer R + sig(R,P) 00:42 < realazthat> if H(sig(R,P) + R + B) < difficulty, then the worker wins 00:42 < realazthat> and mints the coins 00:43 < realazthat> in addition 00:43 < realazthat> all those who worked get half the winnings 00:43 < realazthat> split among them all 00:43 < realazthat> now only issue is, bluff posts of work 00:43 < realazthat> it needs to cost to post work 00:46 < realazthat> so that is easily solvable I think 00:47 < realazthat> workers who finish ontime split the post for their program at the end of the block; if they completed on before the winner 00:47 < realazthat> so it is a bit risky 00:47 < realazthat> you automatically get more money than regular bitcoin chain 00:47 < realazthat> because all work is paid for ... but only if you finish the work before the lottery winner 00:48 < realazthat> otherwise you hung out dry 00:48 < realazthat> so its a race to finish fast 00:48 < realazthat> which is good 00:49 < realazthat> this all assumes that all the programs are very strictly time bound 00:49 < realazthat> and all must take that long to run 00:49 < realazthat> upper and lower limit 00:49 < realazthat> this could be hard 00:49 < realazthat> I would like to think of adjustment that doesn't require all the different programs to be on interval, in sync 00:52 < realazthat> mmmk I should add this to my doc 00:52 < realazthat> these good ideas 00:52 < realazthat> prolly some big holes still 01:18 < amiller> eh i don't think any of that made much sense 01:18 < amiller> will look again tomorrow :o 01:18 < realazthat> lolk 01:18 < realazthat> I'll try to write up a doc 01:18 < realazthat> and make it public 12:17 < realazthat> mmm amiller, you were saying that it is good to be increment/very small jobs, ie. playing the lottery very often 12:18 < realazthat> why is that an advantage? 12:19 < amiller> because otherwise there's more uncertainty about how much you'll earn for any amount of work 12:20 < petertodd> SCIP idea: use it to prove to "SPV" clients for a proof-of-sacrifice based key-value map that a given view of history is in fact the one with the highest total sacrifice 12:21 < petertodd> If I understand things correctly, this is basically an extension of the idea of using SCIP to generate checkpoint hashes and prove they are correct. 12:22 < petertodd> Probably impractical given how SCIP is going to need a crowdfunded buy of, like, half of Amazon EC2, but it's an interesting concept none the less. 12:35 < realazthat> amiller: mm true indeed; I guess my idea for PoW would have to totally change the dynamics of the system, relying on the compute-market to drive computation/incentive 12:37 < realazthat> petertodd: mmm I don't totally understand the point of sacrifice lol 12:37 < realazthat> I wasn't following the key-value map ideas 12:37 < realazthat> in the chan 12:37 < realazthat> but I'll put in my list 12:38 < realazthat> but I understand what you mean about application of SCIP here 12:39 < realazthat> "probably impractical" - do you mean 'cause SCIP is probably practically slow? 12:39 < amiller> meh, we'll crowdsource the construction of scip proofs via the PoW 12:40 < realazthat> mmm but can u trust that 12:40 < realazthat> er 12:40 < realazthat> i mean, can you trust a 3rd party construction 12:41 < realazthat> anyway, eli confirmed that it might be possible to bring down the construction time via bootstrapping 12:41 < petertodd> realazthat: It's an alternative to proof-of-work basically 12:41 < petertodd> amiller: Sure, but this is an example where you'll want a lot of these proofs. 12:41 < amiller> well they build on each other actually 12:41 < petertodd> Ah, interesting, that may be good enough then. 12:42 < petertodd> I saw the SCIP talk in San Jose, but I don't pretend to understand much of it. 12:42 < amiller> so each block contains a proof that the previous block is valid, and given the validity of the previous block, we have an incremental proof that the current block is valid too 12:42 < realazthat> mmm I don't understand the math obviously lol 12:42 < realazthat> but I think I understand how it would work/ how to use it 12:42 < amiller> i might be overinterpreting it but i think that is really similar to the proof-carrying-data idea in the bootstrapping paper 12:43 < realazthat> mmm 12:43 < amiller> i actually don't think any of eli's stuff itself is so interesting, relative to the recursive SNARK paper 12:43 < realazthat> the way I posed it to eli, 12:43 < petertodd> amiller: I think that would work in this case. Basically you'd want to write a program that shows from block n to m the delta changes in the key:value map were whatever. 12:43 < amiller> right 12:43 < amiller> really eli's contributions are a) a ton of practical improvements which is great and b) you can simulate 'ram' by using merkle trees 12:44 < realazthat> mmm 12:44 < amiller> but at this point we are already used to working out the merkle trees ourselves 12:44 < amiller> or at least we don't assume we have 'ram', we assume we have k-v stores like leveldb 12:44 < realazthat> the practical is important though; because the recursive and bootstrapping stuff seems external to the "base" SNARK implementation 12:44 < realazthat> they can use any implementation, no? 12:44 < amiller> that's true yeah 12:44 < amiller> it's SNARK + blockchains and merkle trees basically 12:44 < realazthat> so I assume that eli would work on that next 12:45 < petertodd> huh, is there a laymans description of what a SNARK is somewhere? 12:45 < realazthat> no, the bootstrapping improvement can possibly be applied generically 12:45 < realazthat> petertodd: he describes it in the talk 12:45 < realazthat> which one did you watch 12:45 < realazthat> there are two of them 12:45 < realazthat> one is very easy 12:45 < petertodd> realazthat: the san jose one 12:45 < petertodd> haven't watched the more in-depth one he did at stanford yet 12:46 < realazthat> mmm yeah 12:46 < realazthat> that was the easy one 12:46 < realazthat> er 12:47 < realazthat> the san jose one was easy to understand IMO 12:47 < realazthat> its really simple, as a user 12:47 < petertodd> yeah, even I understood it :P 12:47 < petertodd> it turned SCIP into a blackbox you could reason about, like hash functions 12:47 < realazthat> right 12:47 < realazthat> exactly 12:48 < amiller> well SNARK is SCIP it's not really any different 12:48 < realazthat> Alice has a program P, you create an SCIP proof for it, give it to Bob, he runs P, and produces a sig(P), and result 12:48 < amiller> the difference i think is that SCIP is about RAM computations (using merkle trees) and SNARK is just about circuits 12:48 < amiller> SCIP is also his name for the whole practical project which includes a gcc compiler 12:49 < amiller> SNARK is a blackbox 12:49 < realazthat> a compiler and a vm 12:50 < realazthat> its actually sig(P,R), with R being the result 12:50 < petertodd> ah, as in SCIP is the project that gives you the tools to easily write SNARK circuits? 12:50 < realazthat> programs 12:50 < petertodd> hiding it all behind a VM model? 12:50 < realazthat> yeah 12:50 < realazthat> yes 12:51 < realazthat> the circuits would be huge though; it is programs 12:51 < realazthat> but they are time bound 12:51 < petertodd> whereas for Bitcoin stuff, it may be worth it to figure out an optimal SNARK circuit directly? (at the cost of maintainability) 12:51 < realazthat> mmm I dunno about that 12:51 < realazthat> er 12:52 < realazthat> emphasis on circuit? or emphasis on optimal, ie custom VM assembly 12:52 < realazthat> yes, to latter 12:52 < realazthat> dunno about former 12:52 < petertodd> I see, circuit is just way too low-level then. So the stuff about merkle trees, basically you'd just extend that vm with some operations that act on them directly, closer to the underlying SNARK model? 12:53 < realazthat> gmaxwell was saying that the compiler is great for bootstrapping a program to tinyram (name of the vm/virtual architecture), but you'd hand-code it for best results 12:53 < realazthat> I dunno 12:53 < realazthat> no, I think you can still use it in a blackbox manner 12:53 < realazthat> on the merkle trees 12:53 < realazthat> I can give an example 12:53 < petertodd> I'm interested 12:53 < realazthat> I had this idea, I proposed it to eli, he responded that it was called "bootstrapping" and was in another paper 12:53 < realazthat> so, one huge problem 12:54 < realazthat> is that although it is succinct, Alice must take T(P) time to generate/compile the program 12:54 < realazthat> which is pretty dumb for verifying a blockchain 12:54 < petertodd> T(P) == polynominal time? 12:54 < realazthat> because, Alice wants Bob to verify the blockchain, so she must spend T(P) time to generate the program and then Bob runs it in T(P) time 12:54 < realazthat> time of program 12:55 < realazthat> P is program 12:55 < realazthat> sorry 12:55 < realazthat> so the program P runs in T(P) time 12:55 < realazthat> Alice must take T(P) time to generate/compile the program 12:55 < realazthat> this is undesirable 12:55 < petertodd> ah I see, so Alice is spending as much time compiling the program as it would take to run basically? 12:55 < realazthat> right 12:55 < realazthat> so there are several easy solutions 12:55 < realazthat> you can do it once 12:55 < realazthat> and it can be reused 12:56 < realazthat> by everyone 12:56 < realazthat> so my idea was, to do it so that it does a sqrt(|B|) of the blockchain (B == blockchain) 12:56 < realazthat> then alice spends sqrt(T(P)) to generate P' 12:56 < realazthat> P' runs on a sqrt(|B|) of the blockchain 12:56 < realazthat> and, 12:56 < realazthat> Bob runs P' sqrt(|B|) times 12:57 < realazthat> so that is essentially called bootstrapping 12:57 < petertodd> what do you mean by "does a sqrt(|B|)" of the blockchain? 12:57 < realazthat> it can be possibly be done generically to any P 12:57 < realazthat> petertodd: lets say there are 100 blocks 12:57 < realazthat> P will verify 0-24 12:57 < realazthat> er 12:58 < realazthat> P' will do that rather 12:58 < realazthat> or 12:58 < realazthat> 0-10 12:58 < realazthat> w/e 12:58 < realazthat> it breaks it down 12:58 < realazthat> and Bob runs P' 10 times 12:58 < realazthat> and covers the whole chain 12:58 < realazthat> now Bob can return all the sigs 12:58 < realazthat> and input/outputs 12:58 < petertodd> right, so we've distributed the problem across multiple people 12:58 < realazthat> and thus P' is chained into P 12:58 < realazthat> well thats also possible 12:59 < realazthat> but now I am thinking just one person 12:59 < realazthat> alice and bob 12:59 < realazthat> bob will verify the blockchain in 10 sized peices 12:59 < realazthat> then return all the sigs, inputs, outputs 12:59 < realazthat> which can be verified 12:59 < realazthat> ie. 12:59 < realazthat> P'(10,20) will verify everything from 10 to 20 13:00 < petertodd> ok, so basically because the program takes polynominal time to run, you're best off running it on a smaller dataset? 13:00 < realazthat> no 13:00 < realazthat> the reason you are better running it on a smaller dataset 13:00 < realazthat> is because the T(P) sent to Bob takes T(P) time to generate 13:00 < realazthat> now alice only needs to spend sqrt(T(P)) time to generate it 13:01 < realazthat> yet it still takes Bob ~ T(P) time to run (by breaking it down and running it on separate peices) 13:01 < petertodd> oh, I see now, so generating the *program* has taken us less time 13:01 < realazthat> yep 13:01 < petertodd> now I get it 13:01 < realazthat> additionally 13:01 < petertodd> so it's a time/proof-size trade-off basically 13:01 < realazthat> we can remove more tradeoff 13:01 < realazthat> instead of sending the many sigs back to alice 13:01 < realazthat> she can send over a sig-verification function 13:02 < realazthat> and ask *Bob* to run the verification 13:02 < realazthat> and just get proof that the verification runs 13:02 < petertodd> yup, and return a sig proving he did so honestly 13:02 < realazthat> so now there is not a lot of communication 13:02 < realazthat> so, 13:02 < realazthat> I told you all this 13:02 < realazthat> because now you can start understanding how it would work with merkle trees 13:02 < realazthat> its very similar I think 13:02 < petertodd> right, that's totally a merkle tree 13:03 < realazthat> you just need to verify the merkle tree works 13:03 < realazthat> not that I understand the applications of that all that well 13:03 < petertodd> interesting 13:03 < realazthat> but anyway, it is improvable upon what eli is doing now; possibly in a blackbox manner 13:03 < realazthat> this is my q to eli 13:03 < 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. 13:03 < petertodd> and my understanding is they'll be able to make the protocol non-interactive with zero-trust in the future? IE right now my understanding is Alice needs to generate the program herself because the person doing so can cheat 13:04 < 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. 13:04 < realazthat> mmm I know stage 1 has several undesirable properties 13:04 < realazthat> stage 2 is the sweet spot, except for alice's generation time 13:05 < petertodd> right, although, in that case alice can be the person offering up the proof right? 13:05 < realazthat> I don't remember all the undesirable properties of stage 1 13:05 < petertodd> like, I'd want you to be able to publish a proof, and I guess the program to verify that proof, showing the sacrifices were valid and formed a proper chian 13:06 < petertodd> running that proof will need to be done relatively frequently 13:06 < realazthat> ah yeah, you can basically verify anything on someone elses computer, without revealing anything with this 13:06 < realazthat> so it has many many possible applications 13:06 < petertodd> yeah, although in this case, none of the data is secret, it's just too bulk to pass around 13:06 < realazthat> yes 13:06 < realazthat> two uses 13:06 < realazthat> SNARK has a use even if it is slow on large computation 13:06 < realazthat> that it is a zero knowledge proof 13:07 < realazthat> but SCIP makes it somewhat reachably practical to do it for offloading work 13:07 < petertodd> yeah, the latter is probably more useful to bitcoin in general 13:07 < realazthat> yes 13:07 < gmaxwell> I think the offloading work cases are a bit dreaming right now. 13:07 < realazthat> hehe 13:07 < realazthat> well PoW doesn't really need it to be fast 13:08 < realazthat> so for that "offloading" it is ok 13:08 < petertodd> not many applications can trade-off a million bucks of EC2 time for less bandiwdth... 13:08 < realazthat> but for some computing-market, or chain validation, then yes 13:08 < petertodd> oh... so make the SCIP computation the PoW... nice 13:08 < realazthat> yes, maybe :D 13:08 < realazthat> you can use any program this way 13:08 < realazthat> like ... something useful 13:09 < petertodd> that has so many levels of magic stacked up.... I don't think I'd trust it... 13:09 < petertodd> but it's a nice dream 13:09 < realazthat> lol 13:09 < realazthat> well if it can be done, someone's gotta do it 13:09 < realazthat> and it is just too cool 13:09 < petertodd> Always a bad thing when the security of your system depends on brand-new technology staying slow... 13:09 < realazthat> not to do :D 13:09 < gmaxwell> realazthat: verifying the pow does need to be fast... as its our hashcash anti-DOS tech. :) 13:09 < realazthat> petertodd: nah, it can be adjusted 13:09 < realazthat> mmm 13:09 < petertodd> realazthat: yes, but only if the technique to make it blazingly fast is public 13:10 < realazthat> gmaxwell: yes, thats a constants/practical matter 13:10 * realazthat so wants to get hands on codes now 13:10 < petertodd> heh, maybe it's best I don't get that code so I actually get some real work done 13:10 < realazthat> lol 13:11 < realazthat> 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? 13:11 < realazthat> (asked to eli) 13:11 < realazthat> Yes, the only way (assuming you cannot break crypto) is to run P, not Q. 13:11 < petertodd> huh, crazy 13:11 < realazthat> so you can turn any useless algorithm into a PoW 13:11 < realazthat> and, you can make the lottery winnings be adjustable 13:11 < realazthat> depending on how you calculate the lottery "numbers" 13:12 < petertodd> oh, that'd be very good for combining multiple PoW's actually 13:12 < gmaxwell> eeh. still, you could optimize the hell out of the scip enviroment. 13:12 < realazthat> gmaxwell: yes :D 13:12 < realazthat> thats like someone running a GPU 13:12 < realazthat> except this is brains 13:12 < realazthat> and might interestingly lead to improvements in SCIP 13:12 < realazthat> lol 13:13 < petertodd> like if you had a hundred low-value PoW's, present a proof that they have been combined honestly, and, say, all depended on some initial value 13:13 < realazthat> ofc incentive is not to publicized 13:13 < petertodd> could be used to reduce varience 13:13 < realazthat> yeah a bunch of conflicting ideas along those lines 13:13 < petertodd> sure lends itself to a merkle-tree structure... 13:14 < petertodd> it'd be interesting if we could somehow make solo-mining low-variance 13:14 < realazthat> also 13:14 < realazthat> a compute market 13:14 < realazthat> this might be possible within bitcoin itself 13:14 < realazthat> https://en.bitcoin.it/wiki/User:Gmaxwell/why_hash_locked 13:14 < realazthat> gmaxwell: doooo that :D 13:15 < realazthat> though I was wondering if it were possible to somehow keep the actual program out of the blockchain 13:15 < realazthat> but thats a side issue 13:15 < gmaxwell> ... 13:15 < gmaxwell> I think you need to read https://en.bitcoin.it/wiki/User:Gmaxwell/why_hash_locked again. The whole point of it is that it makes bitcoin obvlivious to your scip dance. 13:15 < gmaxwell> :) 13:16 < petertodd> oh, shit, and I just realized that this same PoW merging thing applies to proof-of-sacrifice, which basically means you don't need to store the zillions of tiny individual sacrifices... damn 13:16 < petertodd> I've been really stuggling trying to find a decent way to keep my consensus key-value system unbloated... 13:17 < realazthat> gmaxwell: what am I missing? 13:17 < realazthat> why can't u use that to make a job worth running 13:17 < realazthat> and pay out to the 1st person with an answer 13:18 < gmaxwell> There is no need to have the program in the blockchain. 13:19 < petertodd> realazthat: it's a way of forcing the seller to proof they have the data from the output of a program, and at the same time, force them to reveal the decryption key to that data as part of receiving the payment 13:19 < petertodd> realazthat: (I think I got that right) 13:20 < gmaxwell> right. They prove to you that the encrypted output is X, and that the hash of the decryption key is Y. And you make a payment that must provide the value that hashes to Y (the key to decrypt the solution) 13:21 < gmaxwell> For NP problems they don't even have to run the computation inside SCIP, only the validator. 13:21 < petertodd> very cool 13:21 < realazthat> mmm yes 13:22 < realazthat> ok this is interesting too, but not as universal I think 13:22 < petertodd> interesting too how it's dependent on the blockchain being reliably public information 13:22 < petertodd> hard to think of an example where that could be done in a non-bitcoin payment system 13:22 < gmaxwell> petertodd: yea... "if they can spend it, you can get the key they disclosed" 13:22 < realazthat> it would be cool if there was a way to post a SCIP program publically, and have an output script that verifies the answer to release payment 13:22 < realazthat> I guess this is a separate idea though 13:23 < gmaxwell> realazthat: requires putting the validator in the network rules, not really realistic at this time. 13:23 < realazthat> yes 13:23 < realazthat> I mean way later perhaps 13:23 < realazthat> or a way to bootstrap it in 13:23 < realazthat> without putting the validator itself in, I dunno 13:24 < realazthat> it can also be very unsuccinct for bitcoin 13:24 < realazthat> the response signature can be relatively big 13:25 < realazthat> something like a MB or something? I don't remember 13:35 < petertodd> so, the recursive bootstrapping SCIP stuff, any sense of how many months/years we're going to have to wait for it? 13:35 < petertodd> I mean, sounds like you have to implement a SCIP proof verifier within the system for one thing... 14:38 < realazthat> yes 14:38 < realazthat> I mean it seems a bit trivial to try to do my myself 14:38 < realazthat> but eli said there were more complications 14:38 < realazthat> and I didn't read the paper he named in response 14:38 < realazthat> and I prolly wouldn't understand it if it goes into the math 14:38 < realazthat> blackbox for me 14:39 < realazthat> I dunno what problems arise though; it *seems* like one could just ... do it 14:39 < realazthat> petertodd: I hope that if it is feasible, eli would start working on it as stage 3 14:39 < realazthat> I think stage 2 is supposed to be done at the end of august or something 14:39 < realazthat> or maybe that was stage 1 14:40 < realazthat> but things never get done on time :P 14:40 < realazthat> petertodd: mmm I asked eli if he could join us in IRC 14:40 < 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. 14:40 < realazthat> eli: I would be happy to hang out some time with some of my collaborators, how does this work? 14:41 < realazthat> but it seems like he wants a one-time thing 14:41 < realazthat> so I am thinking what the best medium for that is 14:41 < realazthat> #bitcoin-dev Q&A time? 14:41 < realazthat> forums? 14:41 < realazthat> ML? 14:41 < realazthat> I am not really involved in the community 14:41 < realazthat> so I don't know .. 14:43 < realazthat> I guess I could mail him asking him to sign up on the ML and introduce himself 14:43 < realazthat> and point him to the channels in the meantime 14:43 < realazthat> and tell him I'd get back to him about a possible set time 14:43 < realazthat> for a Q&A 14:44 < realazthat> if someone is active on the forums, maybe we can collect questions 14:44 < realazthat> or have a question thread 14:44 < realazthat> dunno if they do this type of thing on the forums 14:47 < realazthat> mmm should I point the webchat client to #bitcoin-dev or #bitcoin-wizards 14:49 < gmaxwell> there is a webchat on the bitcoin.org site that points to bitcoin-dev. 14:56 < realazthat> sent 15:19 < petertodd> realazthat: cool 15:24 < petertodd> Thinking about incentives re: proof-of-sacrifice (PoS) blockchains. Seems to me that the incentive for others to extend your view of history is good enough that people will both keep copies of the chain data, as well as calculate accurate k:v set (UTXO equiv) proofs. 15:25 < petertodd> It doesn't quite feel right though... Making a proof-of-sacrifice block is something you only do occasionally - there isn't any capital involved basically. 15:26 * Luke-Jr suggests PoX for proof-of-sacrifice :P 15:26 < Luke-Jr> as in x.x 15:26 < petertodd> Lol, alright, agreed. 15:27 < petertodd> The other nasty issue is that it's really hard to figure out good incentives not to just spam blocks. You can try to make your sacrifice worth less if it's associated with more data, but that leads to nasty edge cases like a big sacrifice for no data t all. 15:30 < petertodd> On the other hand, I'd argue it's a lot more stable than namecoin, which at any point in time could die due to lack of interest, especially given the huge speculation that it's currency has attracted. 15:32 < petertodd> Having said that, re: data size one nice thing you can do is for the DHT layer or whatever with the actual data the people volunteering their bandwidth have an easy way to filter spam by looking at sacrifice size. 15:33 < petertodd> (remember that PoX is for determining *what* is the valid value for a given key, it doesn't actually have to be associated with storing that value) 15:34 < realazthat> hmmm 15:34 < realazthat> how would namecoin die 15:34 < realazthat> (side interest) 15:34 < realazthat> does it not have merged mining? 15:35 < petertodd> pools turing off merge mining, and someone being an asshole. Running namecoind isn't free. 15:35 < petertodd> Eligius turned off namecoin merge mining a few months back for instance. 15:35 < realazthat> mm 15:36 < realazthat> I was thinking of what merged mining would mean for my SCIP PoW chain idea 15:36 < realazthat> ie. how to take advantage of merged mining 15:36 < realazthat> or, 15:37 < realazthat> how to merge mine in between two such chains 15:37 < realazthat> I have some ideas ... 15:37 < petertodd> Why would SCIP PoW with merge mining be special anyway? 15:38 < realazthat> well 15:39 < realazthat> by SCIP PoW, I mean that mining itself is any useful/non-useful program that the blockchain would run, and use SCIP to prove that the miners are actually doing the work 15:39 < realazthat> so essentially, miners doing something other than hashing 15:40 < realazthat> thus, you can't use hash-mining from bitcoin chain to this chain 15:40 < realazthat> it is simply not the same 15:40 < petertodd> right, and see, that's the thing, because it's not probabalistic a dead simple rule for the merge-mined chain is just "see this merkle path? notice how it leads to a valid PoW in the master chain?" problem solved 15:41 < realazthat> yeah 15:41 < realazthat> so my idea is to work the other way around 15:41 < realazthat> there are two ways to win the lottery 15:42 < petertodd> oh, mind, yeah, mining does need to stay probabalistic... 15:42 < realazthat> 1. you do the work from this chain, and have chance(s) to win 15:42 < realazthat> 2. or you can win in the traditional way 15:42 < petertodd> unless you can some PoX-style DAG structure 15:42 < petertodd> ah, that's just dual PoW functions basically 15:43 < realazthat> yep 15:43 < realazthat> I didn't understand what you were just saying now though 15:44 < realazthat> what is PoX 15:44 < petertodd> proof-of-sacrifice directed-acyclic-graph - point being because it's a graph the mining function *doesn't* need to be probabalistic provided you have a way of merging nodes together 15:44 < petertodd> with a key-value consensus system merging is easy 15:46 < realazthat> mmm 15:46 < realazthat> I have yet to fully understand PoS hehe 15:47 < petertodd> It's really pretty simple, you throw away some Bitcoins in a way that's provable, like spending to an unspendable output. 15:47 < realazthat> right 15:48 < petertodd> Because you are doing something that's costly, you can use it to come to global consensus, exactly like Bitcoin. 15:48 < realazthat> and that gives you a chance to win 15:48 < realazthat> yeah I grasped that 15:48 < realazthat> but I don't see how such a thing ... can begin 15:48 < petertodd> No, there's no chance involved, at least in the key-value maps I'm thinking about. 15:48 < petertodd> Remember we're not talking about coins here, more like a namecoin-type system. 15:49 < realazthat> I am not 100% familiar with the structure of nmc 15:49 < realazthat> I wrote my own bitcoin blockchain parser to learn bitcoin lol 15:49 < petertodd> Namecoin is basically Bitcoin, except with a rule where you can do specially marked transactions that are considered to be associated keys with values, in the case of namecoin, DNS settings. 15:50 < petertodd> (although namecoin can do more than just DNS) 15:50 < realazthat> right, thats what I figured 15:50 < realazthat> and there are rules for what is allowed etc. 15:50 < realazthat> ie. you can't reserve someone elses name 15:50 < realazthat> domain transfer rules etc. 15:51 < petertodd> Yup. I'm saying, ditch the mining and currency part, and do key-value consensus purely by what version of history has the biggest total sacrifice associated with it. 15:51 < realazthat> so who actually mints a block 15:52 < petertodd> A "block" is just one or more key:value settings, potentially just one. 15:52 < petertodd> Specifically Hash(key):Hash(value) probably makes sense. 15:53 < petertodd> And you probably want some rules where once a k:v is set initially, it's associated with a pubkey(s) that must sign for subsequent settings. (like namecoin does) 15:53 < realazthat> ok isn't that a TX 15:53 < realazthat> a block is a bunch of TXs 15:54 < petertodd> Exactly, there's no TX's because there's no currency. 15:54 < realazthat> ok 15:54 < realazthat> so I am just struggling to compare it to bitcoin 15:55 < realazthat> in bitcoin there is a centralization for each block minted 15:55 < realazthat> are you saying there is none here? 15:56 < petertodd> Yeah, anyone with some Bitcoins to sacrifice can trivially make a block in this system. 15:57 < petertodd> Each block includes one or two pointers to previous blocks that they consider canonical history. 15:57 < realazthat> wow 15:57 < realazthat> but thats a lot of different conflicting chains 15:57 < realazthat> oh so you combine it somehow? 15:58 < petertodd> Yeah, just merge them and discard conflicts. 15:59 < petertodd> And people should build on the tip of the highest sacrifice part of the graph they have validated. 15:59 < realazthat> mmm 15:59 < petertodd> The incentive is to do that too, because it makes it harder for an attacker to rewrite what you want history to be. 16:00 < realazthat> so what stops someone really rich from double spending 16:00 < realazthat> mmm 16:00 < realazthat> I guess that would just merge in 16:01 < realazthat> no wait, he can put in a conflict, then weigh his tree down 16:01 < realazthat> with a sacrafice 16:01 < realazthat> sacrifice* 16:01 < petertodd> Well of course you can be 51% attacked. 16:01 < petertodd> But that's always true. 16:01 < realazthat> why is it 51%? 16:02 < realazthat> wait 16:02 < realazthat> in order to get your key/value in, 16:02 < realazthat> you put sacrifice some coins, and store this special key/value transaction 16:02 < realazthat> mmm 16:02 < realazthat> right? 16:03 < realazthat> so if you later redo this, on another chain you own, and spend *more* coins, wouldn't this other chain weigh more? 16:03 < realazthat> ie. have more sacrifice/ 16:03 < realazthat> ? 16:03 < realazthat> I know I am misunderstanding something 16:05 < petertodd> Basically whatever part of the DAG you want to rewrite, you have to spend more than the sum of the sacrifices of that part of the DAG. 16:06 < realazthat> mmm 16:06 < realazthat> I think I am beginning to understand 16:07 < realazthat> a nice illustration would help :P 16:07 < realazthat> so what is the source of new coin? 16:07 < realazthat> how does one get coin in this chain 16:08 < realazthat> or would it work tother with the main chain? 16:08 < realazthat> together* 16:08 < petertodd> Yup, it works only with Bitcoin. 16:08 < petertodd> Remember, there are no coins in this chain. 16:08 < realazthat> right ok 16:08 < realazthat> mm 16:08 < realazthat> destruction of bitcoins ... I don't like it :P 16:09 < realazthat> but i guess its good for everyone else :D 16:09 < realazthat> mmm 16:10 < petertodd> Future stuff can send them to mining fees with a soft-fork. 16:10 < realazthat> ah yeah ok 16:10 < realazthat> or 16:10 < realazthat> oh wait 16:10 < realazthat> what is proof of stake 16:10 < realazthat> sounds like what I was about to propose 16:11 < realazthat> essentially, you give it something temporarily 16:11 < realazthat> and eventually get it back 16:13 < petertodd> yeah, key-value could be done with proof-of-stake too actually 16:13 < petertodd> but proof-of-stake has problems... first of all, usually it turns out nothing is at stake 16:15 < realazthat> howso 16:15 < petertodd> You can often mine both sides of a proof-of-stake fork. 16:16 < realazthat> oh 16:16 < realazthat> and sacrifice? 16:16 < petertodd> sacrifice's can't be undone... 16:16 < realazthat> right 16:17 < realazthat> wow these things are hard to comtemplate automatically like side-channels 16:17 < petertodd> ? 16:17 < realazthat> I wouldn't have thought of that difference easily 16:18 < petertodd> ah, yeah it's a big difference --- Log closed Tue Jun 04 00:00:04 2013