--- Log opened Thu Oct 10 00:00:57 2013 02:35 < Luke-Jr> ok, so the BitShares guys said this isn't a secret..: 02:35 < Luke-Jr> memory-hard PoW using the birthday problem 02:36 < Luke-Jr> finding a solution can use GBs of RAM, yet verification is cheap 02:36 < Luke-Jr> thoughts? :p 02:38 < warren> Luke-Jr: time to start your own scam coin! 02:39 < gmaxwell> Luke-Jr: Not a new idea, I think (pollard-rho POW on my alt ideas has that property), I think. But it has a time memory tradeoff so you don't have to be any particular amount of memory hard 02:39 < gmaxwell> e.g. you can half your memory and just search 2x more points. 02:40 < gmaxwell> e.g. say you're trying to find two values with the same initial 32 bits. You decide in advance that you're only going to consider solutions that begin with a 0 bit. 02:41 < gmaxwell> Now you will have to check 2x more values, but you only need half the memory. 02:42 < warren> at some level of TMTO it becomes faster due to memory bandwidth? 02:43 < Luke-Jr> gmaxwell: isn't it exponentially faster the more memory you commit to it? 02:48 < gmaxwell> Luke-Jr: no, alas. Man wikipedia sucks. 02:48 < gmaxwell> lemme find you an actually informative citation 02:49 < gmaxwell> Here: http://eprint.iacr.org/2012/731.pdf 02:49 < Luke-Jr> XD 02:50 < gmaxwell> (for some reason WP doesn't describe pollard rho as applied to general memoryless collision search) 02:51 < Luke-Jr> hmm 02:51 < sipa> perhaps improve it then? :p 02:51 < Luke-Jr> Wikipedia is improvement-resistent. :p (but doesn't hurt to try I guess) 02:51 < Luke-Jr> gmaxwell: I wonder whether memoryless ASIC would be much faster than memory-as-ASIC in this case 02:52 < gmaxwell> nah, this stuff is easy to improve in wikipedia, no one cares about it. :P 02:53 < gmaxwell> In any case, it's not exponential but indeed, it might be interesting. 03:07 < gmaxwell> in any case the short short of the rho algorithim: say you're looking for two hashes with the same 32 bit prefix. You pick a random starting value then truncate the hash output to 32 bits and use that to obtain your next point to check 03:08 < gmaxwell> then you keep going. Eventually you will loop. You can detect the loop in a bunch of different ways. Once you've looped you have a collision. 03:09 < Luke-Jr> hm 03:10 < gmaxwell> but the fact that you have to recompute part of your loop to actually find the other value, as well as the work required to detect the loop means this is slower than if you had the memory (and access to the memory were free). 03:10 < gmaxwell> There are schemes in between memorylessness and full memory that let you choose your tradeoff. 14:02 < amiller> ugh, i'm stuck on atomic cross chain transactions again 14:03 < amiller> https://en.bitcoin.it/wiki/Atomic_cross-chain_trading 14:03 < amiller> does this one work? 14:04 < amiller> it just uses timeouts and refunds and the whole hash of a secret thing 14:04 < amiller> so that a transaction that claims a reward on one chain must necessarily involve publishing enough information to claim the amount on the other chain 14:05 < amiller> and there's a longer timeout on the second chain 14:09 < jgarzik> amiller, as is self-evident, there is nothing really atomic there 14:10 < jgarzik> IMNSHO 14:10 < amiller> i'm willing to assume that the chains are *loosely* synchronized so that 48 hours doesn't elapse on one chain before 24 hours elapses on the other thouhg 14:13 < amiller> i can't come up with any way that one transaction could be completed and the other not 14:18 < amiller> i guess this requires a locktime though 14:19 < jgarzik> yeah 14:19 < amiller> i can't figure out if this would work with existing locktime 14:26 < amiller> gahh, i think this is just unreadable 14:26 < amiller> i can't interpret what "A creates TX1: "Pay w BTC to if (x for H(x) known and signed by B) or (signed by A & B)" 14:26 < amiller> A creates TX2: "Pay w BTC from TX1 to , locked 48 hours in the future, signed by A"" would actually be as a transaction 14:32 < amiller> if then else ops currently work nonstandard, right? 15:19 < amiller> https://gist.github.com/amiller/6923910/raw 15:19 < amiller> i think this works out. 15:19 < amiller> it's different than luxgladius. 15:19 < amiller> i don't know why i didn't come up with this one before while thinking through the luxgladius one though 15:34 < amiller> https://bitcointalk.org/index.php?topic=193281.msg3315031#msg3315031 15:34 < amiller> i can't tell if i'm currently out of my mind or just was previously out of my mind, it's tricky 16:02 < gmaxwell> So here is a fun POW idea: for each UTXO compute X_n = H(UTXO_n || H(header) || nonce) and then search two X_n such that X_n_1 - X_n_2 < target. it's UTXO semi-hard (time/memory tradeoff) but has a compactly checkable proof (just two UTXO fragments) 16:07 < gmaxwell> (oops one side needs to have a nonce of 0 or its not utxo hard, darnit, I had that right initially and then revised my message and broke that) 16:32 < maaku> gmaxwell: why is it valuable to tie UTxO with PoW? 16:34 < amiller> because otherwise there's not much incentive to actually store the UTXO 16:34 < amiller> especially as the UTXO gets much bigger, people might elect not to store it at all 16:35 < amiller> why buy an extra hard drive to hold the utxo, it doesn't help you mine and you could just buy another miner 16:35 < amiller> this isn't as much of a problem as long as the UTXO stays pretty small, which it seems to be doing so far 16:35 < amiller> but this is especially a prerequisite for any altcoinish idea that involves a larger UTXO 16:35 < amiller> and it doesn't hurt to use the mining incentive to incentivize storing the UTXO 16:37 < maaku> hrm, ok is there any reason to have a UTXO-POW if you have UTXO commitments? 16:39 < amiller> yes 16:39 < amiller> even if you odn't need the whole utxo to validate merkle-branch proofs 16:39 < amiller> you still need lots of people to construct/serve those proofs, cheaply 16:40 < amiller> those people can be the miners 16:40 < amiller> use the mining fee to subsidize some of the expense of validation (preparing the proofs) 16:41 < maaku> ok what i mean is if there is soft-fork commitment of the utxo hash to the coinbase 16:41 < maaku> (which is the current plan, i hope) 16:41 < maaku> then they are incentavised to have the UTXO set - their blocks will be ignored otherwise 16:42 < gmaxwell> maaku: imagine you have that.. and people go "ouch, these things are expensive to compute. Oh look, bob will generate them for us for only 0.01% of our mining income, we just need to connect to him to get the latest value".. and you get massive centeralization as a _result_ of your commitment. 16:42 < gmaxwell> but if the POW is UTXO hard then the communications bandwidth required to use bob is proportional to hashrate and prohibitive. 16:43 < maaku> but - different tack here - aren't you then requiring any full node to also maintain the whole utxo set to validate? 16:44 < gmaxwell> maaku: what I described can be validated against a utxo commitment (e.g. in the prior block) 16:45 < maaku> ok 17:00 < maaku> gah, i completely forgot about committing hashes of undo files 17:24 < amiller> does anyone have any idea wtf adam3us is describing 17:24 < amiller> i think it's good but i don't understand it 17:25 < amiller> i understand the idea of having homomorphic commitments to values (like instead of zerocoin, where you have to do one transaction per fixed-unit of currency) 17:27 < amiller> but i can't figure out what it has to do with proof of work 17:28 < gmaxwell> amiller: oh good, its not just me. 17:28 < gmaxwell> well actually I think I have a better idea of what it is than that. 17:30 < gmaxwell> Consider, you can do digital cash via blind signatures... so long as you can trust the blind signing guy to not double sign. So what if your POW were a blind signing algorithim? and the ability to double sign is removed by the difficulty in creating a block and the desire to not have your block invalidated via double signing. 17:30 < gmaxwell> I think thats what he is trying to describe. 17:39 < gmaxwell> amiller: i dunno why you say that "since pooled mining is *not* a systemic threat to decentralization in the same way" ... I think it is one, it's just one of lower magnitude, but not different degree. 17:39 < gmaxwell> the magnitude difference comes from the fact that miners can't vote with their feet, but we see in practice that they already vote with their feet super slowly with pools. 17:39 < gmaxwell> (e.g. stupid dos attacks are visible in the global hashrate) 17:39 < amiller> that's really not inherent to pooling thouhg 17:39 < amiller> just an implementation of it? 17:40 < gmaxwell> yea, you could pool for payments only, and that wouldn't have that risk. 17:40 < gmaxwell> But the cost of running a full node, varrious intelletual friction, etc. are also pro-centeralization. 17:41 < amiller> agreed, sure 17:41 < gmaxwell> but okay, fair point, your idea kills even the least harmful kinds of pooling. 17:41 < gmaxwell> e.g. just pooling payments. 17:42 < amiller> (edited to weaken my apparent endorsement of pooled mining :o) 17:51 < gmaxwell> amiller: https://bitcointalk.org/index.php?topic=309073.msg3315837#msg3315837 18:00 < Luke-Jr> I don't see how that would stop people from outsourcing mining 18:01 < Luke-Jr> on the contrary, it would just make it worse since the companies doing it would be less likely to give their clients any direct control over the miners 18:07 < amiller> i don't follow 18:09 < gmaxwell> Luke-Jr: the idea is that it makes it so the cloud company can easily and invisibly rip off their investors. 18:09 < Luke-Jr> they already can 18:09 < gmaxwell> The motivation may not be obvious to you because they can already do that, amiller is assuming a future world where the investors demand proof. 18:09 < gmaxwell> which they can currently provide. 18:10 < gmaxwell> e.g. if you buy x TH/s of mining the cloud can send you shares to prove that they're mining in a way that will pay you. 18:10 < Luke-Jr> i c 18:10 < Luke-Jr> so basically his idea makes it impossible for them to provide proof :P 18:10 < gmaxwell> Of course, no one does this, or even asks for it. But amiller assumes they will, and proposes to break that. Right. 18:11 < amiller> unbuild it and they wont come 18:11 < gmaxwell> their proof would be worthless because the solutions they find would be rebindable to pay them instead without anyone knowing who did it. 18:11 < Luke-Jr> imo not worth a hardfork <.< 18:11 < amiller> Luke-Jr, time will tell --- Log closed Fri Oct 11 00:00:25 2013