--- Log opened Fri Jun 28 00:00:31 2013
--- Day changed Fri Jun 28 2013
00:00 < gmaxwell> petertodd: I expect it actually is— I mean, thats basically what a linear SVM trained on the netflix prize data produces: a model that predicts what you'll like based on what you've seen regardless of your rating.
00:00 < Luke-Jr> gmaxwell: yeah
00:01 < gmaxwell> but sadly the fact that it forces you to rate means that people provide less data than they could.
00:01 < Luke-Jr> still stick at 4 movies x.x
00:01 < Luke-Jr> wtf, they have Q: The Winged Serpent, but not the Tron sequel?
00:02 < gmaxwell> E.g. right now it suggests that I watch "Legend" which is like ... from the mid 80s. I've seen it and assume I didn't hate it, but I can't usefully rate it.
00:02 < gmaxwell> they have the tron sequel
00:02 < gmaxwell> http://movielens.umn.edu/movieDetail?movieId=82461
00:02 < Luke-Jr> the initial entry needs a search >.>
00:04 < Luke-Jr> grr
00:04 < Luke-Jr> the search from that page won't work until I find 15 either
00:05 < gmaxwell> turn off exclude movies without predictions?
00:06 < Luke-Jr> no, it's the "MovieLens needs at least 15 ratings from you to generate predictions for you." screen
00:06 < Luke-Jr> grr, I missed Short Circuit
00:08 < gmaxwell> I've seen a bunch of good weird movies because of movie lens.
00:08 < jgarzik> petertodd, how so?
00:08 < Luke-Jr> Live Nude Girls (1995) lolwut
00:09 < jgarzik> petertodd, It does need a blockchain piece to ensure a single identity is commited to that
00:09 < jgarzik> petertodd, without a chain, someone could create any number of root records for a given sacrifice pair
00:10 < jgarzik> petertodd, is there any issue beyond that?
00:11 < petertodd> jgarzik: just sent you my reply
00:17 < jgarzik> petertodd, OP.RETURN <txid> seems sufficient proof in the future, if you provide the serialized TX later? by broadcast perhaps ;p
00:19 < jgarzik> petertodd, I do agree that OP_RETURN <master pubkey digest> makes life much easier
00:22 < petertodd> jgarzik: but the txid doesn't prove that the serialized tx was available to anyone but you to mine
00:22 < petertodd> jgarzik: I could never broadcast the txid, and with my %5 hashing power just wait until I find a block
00:24 < petertodd> or even almost zero hashing power if I'm willing to fail the first few times, at no cost other than the fees associated with TX1
00:28 < jgarzik> petertodd, oh, I see your point, agreed
00:29 < petertodd> jgarzik: you're just trying to get around how few people want to allow large OP_RETURN data payloads aren't you?
00:33 < jgarzik> petertodd, yes :)
00:34 < jgarzik> petertodd, having to broadcast the entire tx is burdensome
00:35 < jgarzik> s/broadcast/encode in another tx that is broadcast/
00:35 < petertodd> jgarzik: indeed, but there is no other way
00:35  * jgarzik nods
00:35 < petertodd> jgarzik: also don't forget to take into account signature mutability
00:36 < petertodd> jgarzik: the mined tx might not be identical to the announced one; make sure they spend the same inputs
00:38 < petertodd> adam3us: is http://eprint.iacr.org/2007/433.pdf the state of the art in combining multiple proofs of work?
00:39 < petertodd> adam3us: I could use a scheme to combine proofs-of-* arbitrarily to keep proof size down, but it strikes me as an inherently difficult problem if the proofs are arbitrary
00:41 < adam3us> reading paper, not seen before
00:41 < petertodd> adam3us: thanks
00:48 < adam3us> btw you know multi-sub-puzzle approaches to lower variance are a problem because they create progress, and for bitcoin you cant have progress, or powerful nodes/miners win disproportionately to their power (even more than the proportion their power is higher than a less powerful node)
00:48 < petertodd> for sure; I have very different application in mind
00:49 < amiller_> yeah i know that paper
00:50 < amiller_> the thing is bitcoin is *not* actualy based on a proof of work
00:50 < amiller_> it's based on something else!
00:50 < amiller_> the ideal proof of work (like the one in this constant-verification-effort) is that it takes *precisely* a certain amount of work to complete
00:50 < petertodd> what would you describe what bitcoin is based on?
00:50 < amiller_> but it's more important in bitcoin that the puzzle acts like hashcash rather than that
00:50 < petertodd> s/what/how/
00:51 < amiller_> it has to have high variance and really small trials
00:51 < amiller_> it's better described as a lottery than a proof of work
00:51 < petertodd> "proof-of-ticket-purchase"
00:51 < amiller_> yeah
00:51 < petertodd> "proof-of-wager"
00:51 < petertodd> "proof-of-gambling-problem" :P
00:52 < amiller_> this guy dave levin i've been talking with has some interesting, one thing he likes he calls the 'alibi' problem
00:52 < petertodd> ?
00:52 < amiller_> basically it's easy to prove something happened, but it's harder to prove something didn't happen
00:53 < petertodd> hence the UTXO proof stuff...
00:53 < amiller_> you can do it exhaustively by showing every single thing that *did* happen and showing that a bad thing is not included
00:53 < jgarzik> petertodd, Updated and simplified design, https://en.bitcoin.it/wiki/Identity_protocol_v1    Thanks for the assist.
00:53 < petertodd> or the double-spend problem in general
00:53 < amiller_> but the alternate is to show an "alibi"
00:53 < amiller_> so every time you spend a hash mining on a block, that's a hash that's *definitely* not for some *different* block
00:53 < amiller_> merge mining is sort of the opposite idea though which is interesting too
00:54 < petertodd> so that means that a convincing proof-of-non-double-spend would be to somehow show that all the available hashing power was doing something else
00:54 < amiller_> right
00:54 < amiller_> if suddenly the observed hashpower rate drops by 70%
00:54 < amiller_> then it should be really concerning to everyone
00:54 < amiller_> where did that hashpower go and what's it doing
00:55 < amiller_> but as long as all the asics we estimate have been produced are accounted for you know they're not doing anything else
00:55 < amiller_> something like that
00:55 < petertodd> yeah, yet that's always fuzzy, because there is no engineering way to achieve consensus quickly in a distributed network, let alone a decentralized one
00:56 < petertodd> jgarzik: I have a few edits
00:57 < amiller_> hm, this proposal is pretty neat actually
01:00 < petertodd> jgarzik: also, code wise, you planning on implementing a library or adding it to an existing one or what?
01:01 < petertodd> amiller_: it'll be very interesting to see how the social dynamics of proof-of-sacrifice SIN's work out
01:02 < petertodd> amiller_: and Freenet among other's need them
01:02 < amiller_> yeah.
01:02 < amiller_> it'll be the first new hat in the ring in a long time as far as identities go
01:03 < amiller_> well, besides vanity addresses
01:03 < petertodd> Reminds me: I was thinking that for a lot of social applications the correct metric to compare different sacrifices is probably value*time
01:04 < petertodd> Like, for anti-spam you want to reward the identity that has been around the longest, not just that has sacrificed the most.
01:04 < petertodd> Or if you are trying to figure out which GPG key is probably correct. (in the absense of a consensus key-value store of course)
01:05 < amiller_> there's all sorts of other subtle cues like
01:05 < jgarzik> petertodd, code-wise, the first will be a minimal command line tool just to prove it works
01:05 < amiller_> if it's been in forum sigs on the wayback machine, famous tweets, etc
01:06 < petertodd> jgarzik: cool; I was intending to put fairly generic proof-of-sacrifice code under my yet-to-be-written trustbits library
01:06 < jgarzik> petertodd, thus "version 1"
01:07 < petertodd> jgarzik: "1" is a bit ambitious IMO :P
01:07 < petertodd> jgarzik: version 0
01:07 < jgarzik> petertodd, This is just to get something out there that works.  I imagine a version 2 will appear within 12 months, if people like the concept
01:07 < jgarzik> ;p
01:08 < petertodd> jgarzik: Yeah, mainly I'm thinking to make sure we don't wind up with a bunch of subtley different sacrifice techniques...
01:08 < jgarzik> petertodd, feel free to edit if you think I won't yell and complain ;p
01:14 < petertodd> jgarzik: "Hyphenate or space SIN for easier human reading" <- tricky because base58 has inconsistent length
01:15 < jgarzik> petertodd, IMO it is needed, even so
01:17 < jgarzik> petertodd, disagree with that last.  it should be a miner's fee.
01:18 < petertodd> jgarzik: but then you have to provide proofs of tx existence for every input
01:18 < adam3us> seems to me this paper  http://eprint.iacr.org/2007/433.pdf does not use partial collisions internally
01:18 < petertodd> adam3us: what do you mean by internally?
01:18 < adam3us> it does not even mention partial collisions in their proposed merkle
01:19 < adam3us> i mean the merkle tree hashes below root
01:19 < adam3us> or even in the root
01:19 < adam3us> maybe its unstated assumption?
01:19 < petertodd> jgarzik: although, brainfart, it should be <digest> OP_TRUE in that case
01:19 < adam3us> otherwise it seems to scale to a lot of work you hve to have a massive merkle tree that barely fits in ram
01:20 < petertodd> adam3us: I read that as an unstated assumtpion; it's a mechanism to combine multiple partial collisions
01:20 < adam3us> they talk about a slower hash as an option, but that slows down the verifier
01:20 < jgarzik> petertodd, miner's fee is a requirement.  Can be on T1 if not T2.
01:20 < petertodd> jgarzik: No, the miners fee or anyone-can-spend has to be on T2, because T1 can be mined for free with patience.
01:21 < jgarzik> true
01:21 < adam3us> petertodd: i think they are aiming for space optimality and so maybe they dont like that because if you have internal node including sub-collisions you have to encode the ones you disclose in the P.log(N) nodes in the proof
01:22 < jgarzik> petertodd, OP_TRUE is anyone-can-spend?
01:22 < adam3us> but that would make sense and then you could view their advance as to say that you can more efficiently encode multiple sub-puzzle solutions via their approach to select which sub-puzzles to disclose based on the root hash
01:22 < jgarzik> petertodd, additional, I was trying to think of a way to use 100% standard transactions, perhaps with multisig abuse
01:23 < petertodd> jgarzik: yeah, technically it can be just <digest> but a anyone-can-spend IsStandard() thing would want to add the OP_TRUE so that <digest> can be non-true and to prevent mistakes
01:23 < petertodd> adam3us: yeah, I read it as more of a "I did all this work, and I'm revealing some of it in a way where I can't do less of that work and get away with it"
01:23 < petertodd> jgarzik: I really think we should avoid that...
01:24 < petertodd> jgarzik: just make OP_RETURN with a reasonable payload IsStandard()
01:25 < petertodd> jgarzik: note BTW that a miner can spend an anyone-can-spend output really cheaply: scriptSig="", scriptPubKey=OP_RETURN, value out=0, thus turning the into into fees and sending it to the coinbase
01:26 < petertodd> *thus turning the input into fees
01:26 < adam3us> petertood: so it is an improvement, but one cant use it for bitcoin mining as that is first-past-the post and this has a progress; though it could be ok for other proof of sacrifice
01:27 < petertodd> adam3us: Is it the best known way - in terms of proof-size - to combine multiple proof-of-foo's?
01:27 < adam3us> petertodd: best I've seen yes
01:29 < petertodd> adam3us: OK. See, I've been thinking about proof-of-stake stuff, and it seems to me that one way to give a proof-of-stake-using blockchain SPV verifiability would be to use some kind of proof-of-? combining algorithm.
01:30 < petertodd> adam3us: Proof-of-stake needs a random beacon anyway, so use it to control what part of the merkle tree of previous stake proofs is revealed.
01:31 < adam3us> a space efficient way to prove stake
01:31 < petertodd> Exactly
01:31 < adam3us> petertodd: i guess you need to prove possession of the private keys, and you could just bundle all your money onto one address and then sign with that?
01:32 < petertodd> I've got a tentative design for a way to do distributed consensus based on having nodes pick a subset of the UTXO space to store and verify, and using proof-of-utxo-posession and proof-of-stake combined for the proof-of-? function.
01:32 < jgarzik> petertodd, technically speaking, "fee" can be anyone-can-spend or miner's fee. I'm ok with either.  Want to avoid burn-the-money sacrifice.
01:32 < adam3us> petertodd: or if you do it in parts, using this approach, if the number of stakes is not a power of 2 it may not fully accurate (only to the nearest power of 2?)
01:32 < petertodd> jgarzik: yup, so make it anyone-can-spend and we're good and have small proofs.
01:33 < amiller_> adam3us, in that paper the subsolutions have to be computed sequentially
01:33 < adam3us> petertodd: proof of holding the utxo set could be pretty useful to prevent willfully ignorant miners
01:34 < amiller_> the proof is basically a short sample of the work after you've done it
01:34 < petertodd> adam3us: Yes, even Bitcoin is going to need it because with UTXO proofs in the coinbase you can do distributed low-bandwidth mining without verification.
01:35 < petertodd> adam3us: A nice way to mine anonymously regardless of what the blocksize is, but it undermines the 51% attack security badly.
01:35  * jgarzik makes "anyone can spend" explicit
01:36 < amiller_> there's no good proof of holding the utxo set until you build it into the proof-of-lotto-whatever
01:36 < amiller_> if it's separate it will just be cheaper to have someone lie for you
01:36 < adam3us> amiller_: ok, but only to the extent that parents have to be calculated after their children
01:36 < petertodd> adam3us: power of 2? I should be able to modify that paper to allow for uneven proof values
01:36 < petertodd> adam3us: then add zero-value padding or whatever
01:36 < amiller_> adam3us, no you have to do sequentially as well
01:37 < adam3us> petertodd: probably
01:37  * amiller_ rereads more carefully to make sure
01:37 < amiller_> if not then the way i have in mind is better anyway
01:37 < amiller_> basically the leaves have to be computed sequentially
01:37 < amiller_> and you have to build a merkle tree on top of all the leaves
01:37 < amiller_> and then the proof is a sample of those
01:38 < adam3us> amiller_: the leaves are h(i||s) s is service string, i is node number
01:38 < petertodd> amiller_: Yeah, and for my application the proof-of-holding-the-utxo set needs to really be a proof-of-work in itself to serve as a random beacon; kinda like scrypt in a way.
01:39 < petertodd> amiller_: I was thinking at the very bottom of the merkle sum tree for the UTXO set compute H(utxo | H(block header | nonce)) and call that computation the proof-of-work.
01:40 < petertodd> amiller_: s/block header/prevblockhash/ actually
01:40 < adam3us> amiller_: you could force it to be sequential eg h_i = h(h_{i-1}||s) for the leaves
01:40 < adam3us> amiller_: but why? to make it less parallelizable?
01:41 < petertodd> amiller_: likely with an additional scrypt like thing to make nonce sequential and random access in some way
01:41 < petertodd> amiller_: but defeating ASIC UTXO implementations is optional
01:41 < amiller_> yeah to make it less parallelizable i guess
01:41 < amiller_> if less parallelizable is a goal, which is often is for pow
01:42 < petertodd> Given I'm thinking about including proof-of-stake, I'm certainely leaning against ASICs... :)
01:42 < adam3us> amiller_: i figured its a bit unproductive because you can always parallelize  non-interactive problem by creating lots of problems and runnng them in parallel
01:43 < adam3us> amiller_: it might make asic a little more difficult
01:44 < amiller_> yeah i think you're right now
01:44 < amiller_> i can't remember what it is i had in mind then.
01:44 < petertodd> adam3us: yeah, a proof-of-work for a crypto coin *must* be parallizable to some degree, or you can't have decentralized mining. But you often want the minimum economic production unit to be "one standard CPU + ram" rather than "250um^2" of silicon
01:44 < amiller_> but yeah the idea (i thought was in this paper) was to reduce variance by having the work involve incremental progress
01:45 < adam3us> amiller_: it could make cheating a bit harder (not compting all nodes) especially if the recipient could expect preimage of leaves randoly also
01:45 < petertodd> amiller_: *while* still keeping proof size small.
01:46 < adam3us> there is progress, and it is partially ordered because of the tree, so the result is reducing variance even tho there is some order flexibiliy
01:47 < amiller_> hmm... so i guess then it's fine just there's no reason to make it sequential since that doesn't really reduce parllelism anyway
01:48 < adam3us> petertodd: its a bit related (asic unfriendly pow) i was thinking eg many hash functions (sha1, ripemd, etc) say 64 hash functions; then selecting which hash function to use based on the beacon, or just based on incrementing counter
01:49 < adam3us> the other thing for asic unfriendly is some dynamic behavior, if which operation to execute is data dependent thats CPU behavior
01:49 < petertodd> adam3us: All that does is changes the minimum economic production unit from, say, 50um^2 to ~1500um^2. If anything it could make the ASIC problem worse by increasing the barriers to entry.
01:49 < adam3us> amiller_: i do like their concept of keeping proof size small, that seems likely reusable
01:49 < amiller_> why not just say you want it to be optimal for intel cpus
01:49 < amiller_> and then find some benchmark for intel x86 cpus
01:50 < amiller_> whatever it is they do that they're best at and optimized for and nothing else can dollar for dollar beat them at
01:50 < amiller_> and then build a proof of work around sampling that functionality
01:50 < amiller_> if that's the goal
01:50 < petertodd> adam3us: I *really* think you want solidly memory hard functions where the vast majority of resources are tied up in silicon to store data.
01:50 < adam3us> i think so yes; eg just choose x86 instructions randomly and execute them, hash the result or soething like that
01:51 < adam3us> but gpus are better cpus - most of the silion in a cpu is wasted on single thread performance optimizations
01:51 < adam3us> so i think maybe better to optimize gpus
01:51 < petertodd> adam3us: At least then the best hashs/$ solutions will be met by implementations that take a bunch of memory and wire it up to many cheap microprocessors - something easily doable on a cottage industry level; PCB design and layout is easy.
01:51 < amiller_> imo the only thing that makes sense is to make the pow exercise some functionality we actually *care* about, which basically means utxo proofs
01:52 < adam3us> memory hard i am not sure; cant an asic include the optimal amount of ram also; or 100-port RAM or something special
01:52 < amiller_> everythign else is goofy
01:52 < petertodd> adam3us: They can, but then the ASIC looks like a memory chip and isn't much cheaper than one.
01:53 < adam3us> petertodd: i was thinking many ported memory could be a problem
01:53 < amiller_> hrm i have no idea how many ported ram works
01:53 < adam3us> petertodd: it allows massive reuse of ram, which normal memory doesnt provide
01:54 < amiller_> what do SSDs perform like, vs many ported ram and 'normal' ram
01:54 < adam3us> amiller_: much video ram is dual ported - two independent access channels
01:54 < petertodd> adam3us: Right, but that's why you want to ensure that the problem is random-access-bandwidth limited.
01:54 < petertodd> adam3us: Reuse doesn't do you any good if the data in ram changes constantly.
01:54 < adam3us> petertodd: well thats my point if a normal ram has 4 channels etc, ok; but if i can access 1024 ports simultaneously
01:55 < amiller_> that's really interesting
01:56 < petertodd> adam3us: Although, for a UTXO proof-of-posession/pow hybrid that's an interesting point... your optimal design would likely be a set of multi-ported ram holding the master copy of the UTXO set, which has multi-port access to the slaves which are changed at every new cycle... hmm...
01:56 < petertodd> adam3us: For a pure scrypt-like it's not an issue, but here it is.
01:56 < adam3us> i guess my meta point is never underestimate hardware guys; you can optimize anything in hardware, and its always possible to do better than software
01:57 < adam3us> i'm not a hardware guy, but i did hear there were people working on scrypt asics
01:57 < petertodd> dam3us: I *am* a hardware guy, and that's just not true, at least if you want a large performance/$ increase.
01:58 < gmaxwell> maybe it would help if you were clear about what kind of performance improvement you're talking about.
01:58 < petertodd> gmaxwell: 10x
01:58 < adam3us> right, the best ou can hope for is the perf/$ increase ismodest
01:58 < gmaxwell> petertodd: surely you can agree that special purpose hardware can get 4x to perhaps 10x more price or power efficiency over general purpose stuff no matter what you do algorithimically.
01:59 < petertodd> gmaxwell: Yes, but 4x is manageable in the context of a proof-of-work system IMO. It's the 100x and 1000x speedups that are really scary.
01:59 < gmaxwell> well then you also have to think about process improvements. It's a lot easier to port dram to better processes than other kinds of logic.
01:59 < petertodd> gmaxwell: I accept I can't stop custom hardware entirely, but I can keep to the level where it's a cottage industry where guys doing PCB layouts stuffed with memory and FPGAs can still compete.
02:00 < adam3us> maybe if you could fully exercise the gpu hardware you could force the attacker to build a gpu
02:00 < adam3us> however even then probably much of the hw is junk for the purpose of mining; eg video rendering, vga/dvi etc
02:00 < gmaxwell> in general POW functions will always allow for super regular hardware implementations "10000 copies of this circuit".. and that lowers the costs substantially to get it to a better process.
02:00 < adam3us> so it will be improvable
02:01 < gmaxwell> OTOH, bitcoin asics are _nowhere_ near process state of the art— I don't even mean lithography. There is a lot of optimization that they're not doing on their current process.
02:01 < gmaxwell> yea, just throwing out all the IO hardware you don't care about saves considerable power and area.
02:01 < gmaxwell> (esp power— driving a bunch of IO is power hungry and general purpose hardware doesn't bother power gating most of that stuff)
02:02 < petertodd> gmaxwell: Is that actually true? The Avalon chips are apparently surprisingly dense for the process node they were fabbed on.
02:02 < gmaxwell> petertodd: from talking to them they aren't doing anything exceptionally clever.
02:02 < adam3us> well i guess the other issue is that its probably going to be difficult to design something efficiently verifiable and memory hard and dynamic (requiring CPU-like branching)
02:03 < petertodd> gmaxwell: I'm thinking of a third-party teardown that was done.
02:03 < petertodd> gmaxwell: s/teardown/decapping/
02:03 < amiller_> i don't believe that, i think you can make an efficiently verifiable pow for basically any task
02:03 < adam3us> a problem i see is getting hardware, seems fair chance butterfly are premining the hardware their customers paid for
02:04 < gmaxwell> amiller_: I'm skeptical about non-memory hard validation for memory hard POW. Certantly you can make POWs that allow partial validation.
02:04 < adam3us> and that other manufacturers who put increasing design/fab resources are economically going to do the same
02:05 < adam3us> well eg in the early days of hashcash i was thinking about floating point tweak to SHA1 etc, but then what if your hash function turns out to be attackable
02:05 < amiller_> gmaxwell no that's totally possible, you can just keep doing cut and choose over and over again until it's a constant size sample
02:05 < amiller_> gmaxwell, this constant-verification merkle tree proof of work paper from 2009 has a really general form
02:06 < petertodd> adam3us: ugh... you really don't want to start putting stuff like floating point into your PoW in a hard-consensus system, because that just makes that set of features a nice optimization target.
02:06 < gmaxwell> amiller_: okay thats a different kind of memory hard function than I was thinking of— in that its a read mostly one where the validatior can have a copy which has trustworthy updates.
02:06 < adam3us> well my point is that designing one-way hash function is hard, eg sha0 got broken, md4, md5 got broken etc history is littered with broken hash functions
02:07 < petertodd> amiller_: How well does non-interactive cut and choose work though? You run the risk of putting the work into gaming the cut-and-choose system if you are not careful.
02:07 < amiller_> non-interactive cut and choose is always about making you finish all the work before you make the first cut
02:07 < petertodd> adam3us: All the litter is kinda old though... :)
02:07 < gmaxwell> amiller_: and yea what petertodd says.. I just keep 1 nth the database and do Nx more queries. Often the trade off is non-linear.
02:07 < amiller_> gmaxwell, no, sequential accesses prevents that
02:08 < adam3us> amiller_: are you talking about the coelho paper ("onstant-verification merkle tree proof of work paper from 2009")
02:08 < amiller_> yes
02:08 < amiller_> that doesn't include the sequential access thing
02:08 < adam3us> well i am sure the sha3 competition has some more litter :)
02:08 < amiller_> but it's also not about a memory hard puzzle
02:08 < gmaxwell> amiller_: I don't see how you can enforce sequential access with a memoryless validator.
02:08 < adam3us> one winner, may losers
02:09 < amiller_> gmaxwell, the memory is a merkle tree, the memoryless validator validates merkle tree paths, but the puzzle solve has to access random locations in the memory in sequence
02:10 < gmaxwell> amiller_: right which is fine, but I can just have 1 nth of the tree or you must increase your proof size by ~O(N) to stop me.
02:10 < gmaxwell> I suppose that its sort of like the PCPs though, fairly little N really does a bang up job at preventing me from subsetting.
02:11 < petertodd> gmaxwell: Yup, PCP's was exactly what I was thinking of.
02:11 < amiller_> gmaxwell, no because you can build a merkle tree then cut and choose over that proof too
02:11 < adam3us> i suppose what you are saying about validating anything is true but with a work/validation ratio of N/(P.log(N)) which is not a great ratio
02:12 < gmaxwell> amiller_: I suppose I'll have to walk through that to see how that works to make the proof compact, but I'll take your word for it.
02:12 < adam3us> to do better you have to rely on a pow and those are not general, they require a one-way function of some kind
02:12 < gmaxwell> (To be honest, I was mostly happy with lite proof validation for memoryless nodes)
02:13 < gmaxwell> (e.g. construct your POW so that them memory hard part is burried behind another hash— and you just transmit that intermediate state and storageless nodes just don't veryify the memoryhardness)
02:13 < adam3us> gmaxwell: the idea is populate a merkle tree with pow, then use the hve the verifier use the root hash of the tree to select a subset of paths to validate
02:13 < gmaxwell> adam3us: Thank you for making it clear to me!
02:13 < gmaxwell> Thats elegant.
02:14 < petertodd> gmaxwell: the problem there is how do you make partitioning a node expensive?
02:14 < petertodd> gmaxwell: partitioning them undetectably that is
02:15 < gmaxwell> petertodd: with proofs of cheating which can be bigger because they're only sent in the exceptional case— and it still reduces to non-memory hard POW otherwise. But yea, the non-interactive cut and choose is indeed better than I was thinking and solves the problem.
02:16 < amiller_> hrm, yeah i think there's sort of a glitch where you can just make a small number of your pow's bogus and it's unlikely they'll be included in the sample that gets chosen
02:16 < amiller_> PCP basically addresses this but it does it with enormous error correcting codes that are a huge burden on the prover
02:16 < petertodd> gmaxwell: Yeah - by "partitioning" I'm assuming the node has no communication to anyone to even tell them fraud has been commited. It's a problem in Bitcoin too, but at least we can easily make reasonable assumptions about network hashing power.
02:17 < gmaxwell> yea, I mean, it's not hard to implement big RS codes over in hardware... but kinda defeats the memoryhardness.
02:17 < gmaxwell> FFT multipliers makes such nice circuits.
02:18 < gmaxwell> (staged POW still is useful for anti-DOS)
02:18 < petertodd> adam3us: You know, thinking a bit more about your comment about multi-port ram, it's interesting how if your pow-data set is static, at the extremes the difficulty becomes the routing hardware required to make the multiple ports actually work together nicely.
02:19  * gmaxwell &
02:20 < petertodd> adam3us: In practice though, I think the right approach is to have a master UTXO copy, populate the scratchpad memory for your work function, then do some work that consumes random access bandwith >>>> BW required to populate, then proof via NI cut-n-choose partial merkle proof.
02:21 < petertodd> An optimal hardware design in that case has swiftly diminishing returns, because the non-optimal one only doubles the memory cost.
02:22 < petertodd> The trick is then to have a hashing function at the base of all this that can keep up with the main memory bandwidth.
02:22 < petertodd> IE the cheapest one possible so the slowness of the CPU implementation doesn't matter.
02:29 < adam3us> anyway it seems like the asic problem is an economic problem, and the solution is a not-for-profit that aggressively designs and manufactures state of the art asics and flood the market with them at-cost
02:30 < adam3us> seems to me that the players so far have not had that mindset so we have some kind of mining oligopoly
02:30 < petertodd> That's hopeless for decentralization: the world is rapidly converging to the global economy being able to support exactly 1 chip fab.
02:31 < petertodd> You need to ensure that whatever *commodity* magic that 1 chip fab is producing is as close to optimal as possible hardware for your proof-of-work function.
02:31 < adam3us> if there were enough chipfabs to be non-discriminatory
02:31 < adam3us> u say: adapt the proof-of-work function to what they are building - maybe yes
02:31 < petertodd> There just won't be - you get better performing chips from a chip fab by making the fab more expensive. Thus we used to have hundreds of fabs capable of producing top of the line chips, and that number has been dropping ever since.
02:32 < petertodd> Yes, or more to the point, adapt the pow function to what they have no choice *but* to build. Fortunately memory is incredibly simple.
02:32 < adam3us> at present it seems the oligopoly is existing below that barrier
02:33 < adam3us> ie a non-profit could do what i said for now i think
02:33 < petertodd> It is, only because Intel doesn't make Bitcoin mining gear. When they decide they want to be in that market we'll have a monolopy controlled by Intel.
02:33 < adam3us> come up with the money for some big runs
02:33 < petertodd> Big runs that Intel can deny if they want to.
02:33 < adam3us> tmsc also can compete
02:34 < petertodd> For now they can compete, in the future either they or Intel will lose the race and there will be only one.
02:34 < adam3us> yes that is the limit, but we are far from that limit at the moment
02:34 < adam3us> limit that hw manufacturers will themselves hoard, premine, or refuse to fab or sell competing mining hw
02:34 < petertodd> We're not "far", we're just a few years away. The point is to have a viable pow scheme that can be useful when Bitcoin mining equipment itself becomes regulated.
02:36 < petertodd> ...and really, that's why I'm inclined to make the "work value" be proof-of-work*proof-of-stake, where the former acts as a random beacon for the latter.
02:36 < adam3us> then its what you said: someone really does have to find a way to make a gpu pow
02:36 < petertodd> Why would you want it to be a GPU? They aren't simple. Memory is simple.
02:37 < adam3us> yeah: proof of something they're building anyway for general use
02:37 < adam3us> that doesnt have a big hw/sw advantage
02:37 < petertodd> SRAM, DRAM, DDRAM whatever all consists of one or more banks, where each bank is an xy array of bits. It'll never get simplier than that.
02:37 < adam3us> my worry about ram is ram architecture may not be optimized for pow
02:37 < petertodd> Sure those banks get surrounded by reams of routing logic these days, but the routing logic area is always less than the area of the memory itself.
02:38 < adam3us> such that there maybe soe hw advantage in novel ram architecture that they are not going to make for you
02:38 < petertodd> But that's it, ram architecture can't be optimized for a "fill it up with random junk, access randomly" PoW.
02:39 < petertodd> In fact, what you can do, is use hiarchy: your PoW consists of a *mandatory* selection of powers of two bank sizes over a wide range, so whatever is the bank size of the memory actually out there you meet it. (thus preventing power down tricks)
02:39 < adam3us> well there's a big diff in ram latency l1, l2, l3, main; and most of these memory bound have time-memory tradeoffs too (eg scrypt)
02:40 < petertodd> Yes, which is why you need to target multiple bank sizes to ensure that you force latency into the domain of commodity hardware.
02:45 < petertodd> BTW, so a modern SDRAM chip is basically a set of multiple banks, where each bank is an xy array; SDRAM stands for synchronous DRAM, and the synchronous just refers to how there is a synchronously clocked command/data bus as the interface.
02:47 < petertodd> So what happens on a random access? Well, the memory controller tells the chip "make bank n active", wait, "set row address to x", wait, "set column addr to y", wait, "read", wait, etc. Subsequent chances of row and col are quite a bit faster than the initial activate.
02:48 < petertodd> Why have the banking stuff? That's just because there's a size-speed tradeoff to bank size, make the banks larger and it takes too long for the row select signals to propagate across the surface of the chip due to the higher capacitance.
02:49 < petertodd> More to the point, what that means is the moment you're pool of memory exceeds the size of the largest bank, every work-cycle includes some chance of having to turn the bank on - at a higher level as your working data set gets larger the latency increases.
02:50 < petertodd> The other trick is that if you don't access a given bank of ram the same can *somewhat* power down, but only somewhat. (DRAM still needs to be refreshed)
02:51 < petertodd> Either way, the optimal implementation "band" is very wide and what you're really doing is forcing the memory to exist, even though other than the bus interface it isn't actually getting used all that hard. But that's good, because the optimal bus interface is also a wide band of optimal solutions.
02:53 < petertodd> The power thing is important, because proof-of-work really comes down to proof-of-energy in the end, and we want to ensure that the memory access patterns are such that the data must be in DRAM so that the optimal minimal power design looks like commodity hardware.
02:53 < petertodd> Fortunately for all this stuff, conventional applications also have hideous access profiles where access jumps all over main memory due to how much programmers rely on things like linked lists, so engineers have optimized random access to death already for us.
02:55 < petertodd> Litecoin's scrypt implementation of course screwed all this up simply because the working set was designed to fit into L1 or L2 cache where the optimal implementation is very far from how conventional computers are made. But you know that...
02:57 < petertodd> ...and finally, so for future proofing, have multiple working sets of different sizes each consuming a small portion of total work. Sure you can have a stupidly optimized implementation for a 64KiB working set, but so what if that's just 5% of the work? UTXO storage proofs are nice here, because as amiller pointed out, the working set size is the data you should be good at verifying anyway.
12:16 < amiller_> "<adam3us> [02:31:44] u say: adapt the proof-of-work function to what they are building - maybe yes"
12:16 < amiller_> i say the alternative is to make them do r&d on whatever functionality you want, i.e. whatever helps the network scale
12:16 < amiller_> i think the idea of commodity hardware is unsupportable
12:17 < amiller_> people don't mine because they have spare commodity hardware
12:17 < amiller_> they mine deliberately
12:18 < jgarzik> petertodd, still prefer miner's fee to anyone-can-spend or burn-money.  it's a public good, and the mechanism to sweep donated funds already exists, and is already automated.
12:21 < petertodd> jgarzik: anyone-can-spend *is* a miners fee
12:23 < jgarzik> petertodd, in theory only
12:24 < jgarzik> petertodd, in practice, miners will not update their software just for an experimental project.  a true miner's fee is already supported by the system.
12:25 < petertodd> jgarzik: miners already need to update their software to attempt to redeem the announce-commit sacrifice, the step to collect anyone-can-spend is trivial
12:26 < jgarzik> petertodd, making miners unlikely to adopt either immediately, putting it in the user realm for the first many months
12:27 < petertodd> so what? just add anyone-can-spend to IsStandard() at the same time as adding prunably unspendable
17:21 < amiller_> so if i'm a miner i can generate identities for free, right
17:21 < amiller_> petertodd,
17:22 < amiller_> just pay my own money to myself?
17:22 < petertodd> Of course not: announce-commit means every miner has an equal opportunity to mine the fee.
17:24 < amiller_> i see so i announce it and then it's only the #100th block next that wins it
17:24 < petertodd> Exactly
17:24 < petertodd> Using nLockTime
17:26 < amiller_> i guess it would be pretty impractical to try to reudce the cost of identieis by jsut trying really hard ot be the one that mints that 100th block
17:27 < petertodd> Doesn't even have to be 100th block; mining is a random process so the next block is fine. (unless the sacrificed value >> block reward)
--- Log closed Sat Jun 29 00:00:46 2013