--- Log opened Mon Sep 16 00:00:43 2013
00:49 < amiller> bah my puzzle fix isn't as simple as i thought
00:49 < amiller> this is a little complicated
00:49 < amiller> i basically worked out that outsourcing is possible/encouraged by committing to new transactions before each attempt at mining
00:51 < amiller> because it's easy to put watermarks in the new transactions that would allow a server to basically prove it would be detected if it ran away with a client
00:51 < amiller> if it ran away with a clients' reward*
00:51 < amiller> so my solution is to move the reward-claiming and new transactions outside the work itself
00:52 < amiller> but that implies a problem for consensus
00:54 < amiller> because if you bind the new transactions after the reward it makes converging to a singe block less likely
01:03 < amiller> so i need to have a commitment to some transactions before the work
01:04 < amiller> so that a winning proof of work can be counted as a vote for at most one block
01:04 < amiller> but!!!
01:05 < amiller> the whole stealable/non-outsourceable thing can work if revealing the transactions is optional
01:07 < amiller> agh i guess if one's bad for consensus then the other is too
01:07 < amiller> actually i think it doesn't matter in either case
01:08 < amiller> nevermind
01:09 < gmaxwell> MAGNETS!
01:11 < amiller> anyway tl;dr is that the current way proof-of-work is revealed poses an existential threat to bitcoin because it makes outsourcing effective which leads to decentralized
01:11 < amiller> (which starts with d and that rhymes with p and that stands for pool)
01:11 < amiller> lkasdjflkadjsf
01:12 < amiller> and the main fix is to make it so the proof-of-work is like a digital signature, it doesn't reveal the solution
01:13 < gmaxwell> I am not following. it's already like that.  E.g. if I give you a block header you do not have a solved block.
01:14 < gmaxwell> obviously I can make you give me a solved block but likewise for a digital signature.
01:14 < amiller> no not like that
01:15 < amiller> in order to prevent the outsourcing bogeyman, you need to be able to claim the reward (get your block accepted) without revealing anything about the solution you found
01:15 < amiller> even if it's just the nonce and extranonce
01:15 < amiller> i can pick a random prefix of nonce/extranonce and use that as a watermark
01:16 < gmaxwell> right you want a signature of knoweldge over a valid solution.
01:16 < gmaxwell> which is created posthoc but can't be rebound otherwise.
01:16 < amiller> right
01:17 < gmaxwell> "I have a valid block, and I am bob. Accept my might!"
01:17 < amiller> yeah!
01:17 < gmaxwell> this is also perhaps useful for anti-censorship.
01:19 < gmaxwell> (other miners could still demand other signatures of knoweldge— e.g. prove your solution doesn't include blacklisted txn before we mine on it)
01:19 < gmaxwell> one problem is that you couldn't mine any more transactions until that SoK block is revealed.
01:19 < amiller> yeah so
01:19 < amiller> i think it's not like you just get your block accepted
01:20 < amiller> and reveal the tx at ay point
01:20 < amiller> it's basically you have a choice
01:20 < amiller> you either reveal the transactions
01:20 < amiller> or you have your block mined as an 'empty' block
01:20 < gmaxwell> or steal the generated coin!
01:20 < gmaxwell> ohhh thats cool, except it doesn't work if most of the generated coin is fees.
01:20 < amiller> this means that someone who hears about your block can pretend they didn't get the txs and just mine on top of it
01:21 < amiller> i think even that's fine too
01:21 < amiller> like
01:21 < amiller> the point is to give as much flexibility as possible
01:21 < gmaxwell> (thats, unfortunately, pro-censorship)
01:21 < gmaxwell> amiller: yea but it would be superior if you could still steal the fees.
01:21 < amiller> it's only pro censorship for one block
01:21 < amiller> yeah so the point is
01:21 < amiller> to make the outsource server capable of theivery
01:21 < amiller> it has to be able to steal as much as possible while omitting any detectable watermark
01:22 < amiller> so if it's confident that the fees are public
01:22 < gmaxwell> oh so you have to hide the txn for that. I see.
01:22 < amiller> then they're not watermarks
01:22 < amiller> so really the point is just to allow it to hide as much as it wants
01:23 < gmaxwell> oh thats an interesting point. E.g. it could show some txn, and get the fees on those, but hide other potentially watermarking txn.
01:23 < gmaxwell> I think you can prevent a later miner for censoring.
01:23 < amiller> if you're honest you can prevent later miners from censoring you
01:23 < amiller> by only signing one set of trnasactions after the fact
01:24 < amiller> you could also sign two equivocating sets of transactions and try to split the network
01:24 < amiller> but it wouldn't really have much effect
01:25 < gmaxwell> Maybe there is a way to prevent a third party from gutting a block without producing a watermark.
01:25 < amiller> that's definitely prevented
01:26 < amiller> if you are honest and publish only one set of tx's along with your pow, no third party can create a second set of tx
01:26 < amiller> because the pow still involves a secret that only you know and that you use to sign the txs
01:26 < gmaxwell> gotcha okay.
01:36 < amiller> so, yeah
01:36 < amiller> this can be done pretty easily with discrete log group things
01:37 < amiller> y = g^x  can be used as a hash function
01:38 < amiller> you can check that y is in an arbitrarily small subset of the group, zeros in front and everything
01:39 < amiller> ah, hm, i need to hash the previous block in there too
01:42 < amiller> i'll work it out, i don't think it will be complicated, but it would be simultaneously a signature and proof of work
02:37 < Luke-Jr> gmaxwell: I wonder if anyone has conceived of an imaginary/fictional primary colour before; Google doesn't seem to turn up anything
02:37 < gmaxwell> you mean like a super intelligent shade of blue?
02:38 < gmaxwell> http://en.wikipedia.org/wiki/List_of_races_and_species_in_The_Hitchhiker%27s_Guide_to_the_Galaxy#Hooloovoo
02:39 < gmaxwell> Luke-Jr: there are actual extra-spectral colors, which I'm not sure if that qualifies what you're looking for since they're "real" :)
02:40 < Luke-Jr> gmaxwell: like a colour that cannot be represented with real colours
02:40 < Luke-Jr> yes, those are too real :P
02:41 < gmaxwell> I suppose that you can actually have complex wavelengths as solutions to wave equations, but they're just phase shifts of other colors.
02:42 < Luke-Jr> I'm thinking more along the lines of something beyond what we can conceive of in our mind, but can understand the theory maybe.
02:43 < gmaxwell> well thats why I was thinking of complex wavelength... something where the math worked out but it didn't really make any sense.
02:44 < Luke-Jr> if the math works out, it makes sense :P
02:45 < gmaxwell> But if you don't have _some_ constraint then you are free to say anything, and end up with super intelligent blue or the like.. which isn't all that satisifying.
02:45 < Luke-Jr> depends on the goal.
02:47 < gmaxwell> You end up with something like  Feltrabl a highly controlled and secret color used by Tristero's Empire conspiracy to mark rubbish bins for special collection by their agents as part of their secret message relay network.
03:01 < petertodd> Luke-Jr: Fictional primary color? That's easy, long red. (actually an exercise in a science of color class I took to consider the ramifications of sight if we had a cone that could sense infrared)
03:05 < gmaxwell> I have some marks on my arm that prove that I can sense infrared!
03:05 < petertodd> lol
03:05 < petertodd> ...but only once per eye.
03:05 < gmaxwell> nah, I've got lots of square cm of skin to turn to plasma.
03:06 < petertodd> Sheesh, and I thought I was playing it dangerous with the 1W or whatever it was blue diode laser I was using to make cave formations glow-in-the-dark at Christmas...
03:07 < petertodd> What were you doing with IR lasers anyway? I thought you did light shows...
03:08 < gmaxwell> petertodd: most cost effective way to get lots of green light used to be to frequency double the 1064 nm output of an arclamp pumped NdYAG laser.
03:08 < petertodd> Ah
03:08 < gmaxwell> (and still pretty much is, but they're laser diode pumped now)
03:10 < gmaxwell> because the conversion process is non-linear its much more efficient the higher your peak power is, so not only IR lasers, but ones which are q-switched: microsecond long pulses at 10KHz packing an _average_ power of many watts.
03:10 < petertodd> ...damn....
03:10 < gmaxwell> While realigning one of my lasers I caused some ESD that made the qswitch trigger and got a dump with a peak power output of probably >100kw that grazed my arm, ... also exploded the optics.
03:11 < gmaxwell> BANG.
03:11 < petertodd> Heh, reminds me: I got a chance to visit a laser lab some years back - my arts school had a holography course for decades - and they had some insane 1nS pulsed laser or something in the visible spectrum. Kinda insane to see that flash.
03:12 < gmaxwell> I was always terrified by that thing, even with the qswitch open the continuious IRC circulating beam in the reasonator was probably about 300 watts.
03:12 < petertodd> nuts - should have worn the ESD handcuffs!
03:13 < gmaxwell> and it wouldn't lase with the arclamp turned down too far... maybe I could get the IR down to 10w while working on it, which still will burn you quickly, and blind you instantly.
03:13 < gmaxwell> (obviously I used IR safty goggles)
03:13 < petertodd> That's obvious because I know first hand that you can see.
03:13 < gmaxwell> In florida ESD was almost never an issue due to high humidity…
03:14 < petertodd> hah, very true, not so true here...
03:14 < petertodd> We grudingly have those ESD mats all over the place at work, although I've only used the wrist straps a handful of times.
03:22 < petertodd> gmaxwell: You could have done worse though: http://www.ncbi.nlm.nih.gov/pubmed/9510099
03:24 < gmaxwell> the @#$@$#@$
03:24 < gmaxwell> crazy!
03:25 < petertodd> Heh, my brother's got a few tattoos from the chain of his mountain bike, but that takes the cake...
03:26 < gmaxwell> Nah, I have a tiny scar where a bit of tissue was removed and instantly cauterized. May have even been from a reflection as the optics exploded and not the main beam itself.
03:26 < petertodd> Ha, yeah, depends so much on exactly what happened too; the energy could have easily been absorbed by the smoke emitted.
03:27 < petertodd> I had a scar for ages myself on my thumb due to a photoflash circuit...
11:19 < jgarzik> petertodd, random note, perhaps obvious: USB and PCI traffic may be observed, just like ethernet traffic
11:19 < jgarzik> (recalling conversation a while ago)
19:57 < petertodd> So I think you can do compact NI proofs of colored coins: suppose I have a tx with two colored coin inputs, each worth 1BTC.
19:58 < petertodd> I just need to select one of those txins randomly, and prove (via a proof back to genesis) that it's a real colored coin txin.
19:58 < petertodd> Now if I try to make a false tx proof, with only one real input, I have a 50:50 chance of destroying my colored coin output by spending it to an invalid transaction that doesn't have a valid proof, so when you add it all up I can't get ahead.
19:59 < petertodd> The same applies for n inputs, and equally inputs that aren't equal in value provided I select the inputs in a weighted random fashion.
20:00 < petertodd> As for the random number, the best I can think of is to take the next n blockshashes, computer hash % n, and take the mode to select the input I prove.
20:00 < gmaxwell> meh, it's 50:50 for the cheater though. He doesn't care if four steps down the new NI proof catches the cheating.
20:01 < petertodd> Well, this is the thing: every proof is a full path all the way to genesis of one txin - I don't think I can do better than that. But at least it's just one path, O(n) size.
20:02 < gmaxwell> right but the cheater has 50/50 odds of winning in their cheat.
20:02 < petertodd> Sure, but their expected return is still zero.
20:02 < petertodd> slightly negative including fees
20:03 < gmaxwell> oh because it destroys their coin if they lose.
20:03 < petertodd> exactly
20:08 < petertodd> Now, see this works especially well with mastercoin, because every tx sends a fee to the exodus address.... :/
20:10 < gmaxwell> I think it only does that because ... thats basically the only mental tool that they have available to identify the mastercoin transactions.
20:11 < petertodd> yeah.... as you may have guessed I'm the guy who offered to write them a proper spec
20:11 < petertodd> I don't have high hopes :/
20:15 < gmaxwell> Well, I think you hurt their feelings, since I got a PM saying asking for feedback on their crazy checkmultisig stuff saying that you were demanding a lot of money to tell them the flaws in it. :P
20:15 < sipa> heh, i got the same mail :)
20:15 < petertodd> I'm not exactly surprised. Though he's remarkably friendly to me.
20:15 < sipa> they told me it was you
20:16 < petertodd> Lol, technically I haven't talked about money yet...
20:17 < petertodd> I'm *really* not happy with how he's going about it all, on the other hand, I don't think he's a bad guy, just naive and clueless.
20:17 < petertodd> Not his fault the community is crazy.
20:17 < sipa> he certainly doesn't strike me as a scammer
20:18 < petertodd> Me neither, but I also don't think he's going to wind up making something worth a half million...
20:24 < gmaxwell> sipa: they told you it was me? or that it was peter?
20:24 < sipa> peter
20:25 < sipa> they didn't tell you?
20:25 < gmaxwell> oh yea, sure, and I didn't disbelieve it. I think I said that I wasn't super inclined to give them free consulting as I viewed what they were doing was harmful to and competative with bitcoin.
20:28 < petertodd> gmaxwell: I told him I wasn't as worried about UTXO harm, as I was about the whole thing blowing up and going no-where because it's a bad idea.
20:29 < gmaxwell> That was also my conclusion after it was mentioned they were using a bc.i wallet... I dunno if I said that on the forum. I feel really bad, I suspect everyone involved is just hopeful but misguided.
20:30 < petertodd> Yup. I was pretty harsh in my first post - I wouldn't have in another situation - but given the money involved it deserved bluntness I think.
20:30 < midnightmagic> International journal of network security & its applications is the shittiest online journal I've ever had the displeasure of grovelling through.
20:30 < midnightmagic> (sorry for the interruption)
20:37 < gmaxwell> Yea, indeed, that fact that they were solicitcing (and recieved) a ton of money also reduced my typically overwhelming level of charm.
20:38 < petertodd> And amount of money that makes me more than happy to ask for some too.
21:03 < gavinandresen> "give me money and I'll tell you why your idea sucks" is never going to make friends, though.
21:04 < petertodd> Meh, what I was offering to design wasn't his idea actually. (the tx encoding)
21:26 < jgarzik> hah
21:26 < petertodd> jgarzik: ...says a lot about the project...
22:06 < warren> didn't ecocoin offer money for a security audit?
23:31 < amiller> hm.
23:34 < amiller> you know, my approach would basically end pooled mining
23:34 < amiller> anyway, i have been struggling with this zero knowledge proof of work signature thing
23:34 < amiller> all the straightforward things i came up with just using discrete log tricks don't really work
23:35 < amiller> the ones you can do zero knowledge over directly aren't good crypto hash functions
23:35 < jgarzik> amiller, ending pooled mining would be fine, though it will never happen due to intertia ;p
23:36 < amiller> jgarzik, well if my doom&gloom prediction comes true and hosted mining starts to catch on...
23:36 < amiller> it would be good to have a solution in store!
23:36 < amiller> anyway so i know i can use Pinocchio (or TinyRAM) to do zero knowledge proofs of work generically
23:36 < amiller> the downside is it takes a long ass time to construct the proof, even if verification is pretty efficient
23:37 < amiller> so...
23:37 < amiller> the clever way out is that the use of this zk proof of work is really only needed as a special device to prevent hosted mining
23:37 < amiller> you have to have the "option" of doing a zk PoW, but ordinary users wouldn't actualy have to take that option
23:37 < amiller> you can decide after the fact
23:38 < amiller> empirically it would take about 1 minute to produce the zk PoW for 2xSHA256 using pinocchio
23:38 < amiller> it could be parallelized too
23:38 < amiller> if it's only meant to prevent cloud mining, then it only has to be plausible for a cloud service provider to take that option!
23:40 < nanotube> people already trust pools not to skim/steal. what people /won't/ trust is other miners not to steal. so to really end pooled mining you have to enable other miners to appropriate more than their fair share (or steal entire blocks)
23:41 < amiller> stealing entire blocks is exactly what i'm suggesting
23:41 < nanotube> stealing by pool operator, or by fellow peer miners?
23:41 < amiller> by fellow peer miners
23:41 < nanotube> ah, in that case... carry on. :)
23:42 < nanotube> i just saw you said that a "cloud service provider" can do something, so i assumed that wouldn't include a random fellow miner.
23:42  * nanotube hasn't really been reading this discussion :)
23:43 < amiller> normally you commit to your transactions before you do the mining
23:43 < amiller> but to prevent outsourcing, i want to make it possible to bind to transactions after the fact
23:44 < amiller> also to use the proof of work without revealing anything about the nonce or extranonce you used, all of which might make the work 'detectable'
23:44 < amiller> to prevent outsourcing, there has to be a "perfect temptation" for the miner to claim the work for itself without any risk of getting caught!
23:45 < amiller> basically i'm recommending using the TinyRAM or Pinocchio zero-knowledge-proofs-for-C things
23:45 < amiller> as an alternate way of claiming the work
23:45 < warren> nanotube: solution withholding attacks already happen on pools
23:45 < amiller> warren, solution withholding isn't as good a threat as solution-stealing
23:47 < nanotube> warren: yes, but you don't get any money if you withhold.
23:47 < nanotube> and griefing with no profit (or even a small monetary loss) is practically speaking not a realistic threat.
23:48 < warren> nanotube: it works on competing PPS pools
23:49 < nanotube> well, define 'works'. does anyone actually make any money out of it? :)
23:49 < nanotube> sure you can drive a pool out of business with this. but that's about it.
23:50 < nanotube> amiller: yea, miner being able to grab a solution for himself by ex-post attaching himself as payout would be just right. :)
23:50 < warren> nanotube: I'm just saying that's what happens
23:51 < nanotube> well sure, but as an individual miner, i don't have to care about it. if my pool goes out of business, i just move on.
23:51 < nanotube> (as long as i set up autopayouts to be relatively frequent :) )
23:52 < warren> an interesting phenomenon now is "switch mining"
23:52 < warren> all the coins using the same hash have pools that transparently switch to a different chain that is more "profitable" at that moment
23:52 < warren> causes huge swings of strip mining and stagnation
23:53 < nanotube> hehe nice
23:54 < warren> forget about "51%".... 5000% can be pointed at a target
23:55 < warren> that's why you see them deploying centralized broadcast checkpoints now
23:56 < nanotube> so in other words, being a latecomer with the same hash, you can no longer be decentralized like bitcoin eh
23:56 < nanotube> talk about first mover advantage eh
23:57 < warren> there's a great many scrypt clones based on 0.6.3 now
23:58 < nanotube> hmm
23:58 < warren> and others are deploying with scrypt-jane or other hashes
23:58 < nanotube> the floodgates have opened
--- Log closed Tue Sep 17 00:00:46 2013