00:01:57sipa:such theory
00:03:12gmaxwell:maybe I can extract some data from the gridseed folks to allow for a scrypt asic cost model that includes energy.
00:03:53gmaxwell:(what I can't just extract from their data sheets is how the energy usage scales with the memory hardness parameter, not without knowing how much of their power is used by the dram vs the rest.)
00:09:13Luke-Jr:Anyone have any tips on boarding in Miami Beach? :/
00:09:44sipa:don't tell them you have a bomb
00:12:24jps:sipa: the NSA will never let Luke-Jr board the plane now
00:12:41Luke-Jr:NSA has no authority over that :P
00:13:35sipa:TSA...NSA... just 3 bits difference
00:15:11jps:I'm sure those guys get a shot at the no-fly list
00:24:33petertodd:gmaxwell: I'm thinking of just hiring someone with ASIC design experience to look at this stuff frankly
00:25:16petertodd:gmaxwell: the EE I was talking to yesterday said he had some contacts
00:25:24gmaxwell:petertodd: actually having built a scrypt asic trumps abstract expirence. :P
00:27:49petertodd:adam3us: the FPGA overhead might get closer to ASIC overhead, but only in the sense of power limitations - you'll never get similar space limitations unless ASIC tech changes pretty drastically in ways that are rather unpredictable
00:28:38petertodd:gmaxwell: the ASIC was a single performance point - scrypt is tunable after all
00:29:29gmaxwell:petertodd: yes, but my _suspicion_ now that I've though about it is that the power usage per user-tolerance-unit will go down as memory usage increases.
00:29:46gmaxwell:esp once memory usage is high enough to not fit in cache on commodity hardware.
00:30:29petertodd:gmaxwell: as is mine, but does that make asics more or less attractive? potentially *less* if commodity dram can be tuned the way we want it to be
00:31:48gmaxwell:I don't follow your argument but I suspect its on an entirely different subject matter than I'm talking about. I'm specifically concerned with scrypt as a KDF here, and I think this thinking invalidates the argument given in the scrypt paper, and that the result might be that scrypt reduces security against a well funded attacker cracking your password.
00:31:52petertodd:gmaxwell: e.g. scrypt with 4GiB might stress random access latency so much that everything but the ram doesn't matter at all
00:32:35petertodd:gmaxwell: no, I'm talking about KDF's - they're an easier problem that ASIC-hard PoW functions
00:34:24gmaxwell:petertodd: right, and if the power costs dominate after N months of operation, and the custom cracker has 10 fold lower power usage than an alternative one that used the same amount of user-tolerance budget but used sha256, then it wouldn't be a win.
00:36:22petertodd:gmaxwell: that's the thing though, your random access related hardware needs to run at full power and high speed, so the rest of the system may not be a big difference in terms of power
00:36:53petertodd:gmaxwell: of course, down the road FRAM tech could blow all these assumptions out of the water too
00:38:35gmaxwell:petertodd: well one way of looking at it once thinking about energy— given commodity hardware is actually often made using state of the art technology, the task is to make the most use of the hardware the user has— so how can you make commodity hardware use the most energy possible. Grinding against dram is _not_ the way to do that.
00:39:08gmaxwell:on a desktop PC, sitting in a tight inner loop on the SIMD registers in the cpu is.
00:39:43petertodd:gmaxwell: Are you sure about that? Because I'm not.
00:40:06maaku:what gmaxwell just said is definately, 100% true
00:40:16maaku:waiting on the ram bus idles the CPU
00:40:19petertodd:gmaxwell: that *might* be true if the SIMD registers were power limited, but that's not at all a given
00:40:31petertodd:maaku: ram uses power to access
00:41:00maaku:very, very little power by comparison
00:41:02gmaxwell:it does but the power distribution is just not compariable. you're talking about 20w vs 100 watts.
00:41:05petertodd:gmaxwell: the problem is if you're algorithm ever winds up not being power limited, then someone can go build an ASIC for it
00:41:37gmaxwell:petertodd: yea sure, the assumption I started out with is that the commidity hardware is already an efficient implementation of everything it does, which isn't true... indeed.
00:42:01gmaxwell:But to the extent its true the KDF problem is just a matter of using all thats available... use the most gates the most power.. etc. make the most use.
00:42:39petertodd:gmaxwell: yeah, and that's an enormous problem. I'm sure you can make a PoW/KDF algorithm that targets *a* cpu family and uses it 100%, but that's not very interesting - you'd just as easily use a KDF with very tunable params to economically stay ahead of attackers with ASIC-dev costs
00:42:46poggy:is it plausable that energy costs would be a limiting factor or is this just a mental exercise?
00:43:02petertodd:poggy: it's plausible, but not certain
00:43:20gmaxwell:And if power costs dominate, you probably don't want to touch the memory at all... because the computer cannot burn 100watts accessing ram. and even if you imagine that its ALU is 4x less efficient than an optimized one, it probably still can burn more efficiency-weighed-power in the ALU.
00:44:05gmaxwell:poggy: it is the case that for computation tasks operating longer than a few months energy is more expensive than fabrication with modern processes.
00:44:25poggy:ah ok
00:44:27gmaxwell:How that balances out exactly is another question.
00:44:47gmaxwell:You have to run for a long time before fabrication is negligible.
00:45:02petertodd:gmaxwell: but look at the system as a whole: quite possible the lower power density of ram per unit area is irrelevant on a system wide level because you can't necessarily remove head from higher density effectively anyway
00:45:41gmaxwell:that works against the user, not against the attacker.
00:46:38petertodd:no, it works against the attacker for PoW for sure: removing low-grade heat cheaply with fans costs very little. For KDFs, that's less certain.
00:47:12petertodd:remember for PoW one argument for decentralization is that the heat can be useful - of course if someone comes out with a ASIC process that can run at hotter temps...
00:47:23gmaxwell:oh I misunderstood what you were saying, I was not arguing in terms of unit area.
00:47:32gmaxwell:I'm arguing in terms of whats actually in a PC.
00:47:50poggy:are there any hybrid functions?
00:47:57gmaxwell:e.g. how much attacker joules can 1 second of a PC possibly require.
00:48:08poggy:requiring both memory and gpu(or whatever)
00:48:34gmaxwell:And I believe that large memory memory hard requires fewer attacker joules simply because the PC only has— say— 20 watts of ram.
00:48:48petertodd:gmaxwell: ah, well that's a better argument come to think of it.
00:49:24petertodd:gmaxwell: although like I say, for the KDF use-case you might as well just make a whole bunch of them, targetted to specific cpu's
00:49:35petertodd:gmaxwell: use whatever one the user happens to have
00:50:56petertodd:gmaxwell: and... might as well make it memory-hard too, and get that extra 20W
00:52:22gmaxwell:petertodd: the premise under scrypt is really two fold: memory technology is uniform decreasing the attackers advantage, and that computers have a lot of gates as memory. Counter arguments are that once you are talking about power memory for a cracker might not be as uniform as thought, and when talking about power a computer doesn't actually have that much memory.
00:54:09petertodd:gmaxwell: yes, I'm not claiming that's a good premise, I'm claiming that in the case of a KDF *because* you have so much algorithm agility (make it a library!) optimal is to use a per-cpu-arch algorithm like your suggestion and make it depend on memory as well
00:54:36petertodd:gmaxwell: which means the salsa20 core in scrypt probably should be replaced by a series of algorithms that do well on simd
00:55:11petertodd:gmaxwell: dunno if you noticed but I did change my mind there :P
00:55:11gmaxwell:yea, sure, I don't think anything I've argued suggests that using memory is terrible, just that it may not be as automatically good as it seemed.
00:55:52petertodd:anyway, my *main* argument is that neither of us knows much about digital logic technology so...
00:56:42gmaxwell:sort of troubling that it seems no one has explored the energy cost angle on this. :-/
00:56:56gmaxwell:would be ironic if the recommended scrypt parameters lowered attack costs.
00:57:33petertodd:meh, wouldn't be the first time
01:46:25phantomcircuit:huh that's interesting
01:46:34phantomcircuit:gmaxwell, i think cex.io moved all their hardware
01:47:11gmaxwell:phantomcircuit: interesting!
03:00:00wallet42:wallet42 is now known as Guest95284
03:00:00wallet421:wallet421 is now known as wallet42
03:25:04_ingsoc_:_ingsoc_ is now known as _ingsoc
03:38:59_ingsoc:Does anyone remember that guy who talked about rewarding miners for putting energy into the grid?
03:45:57justanotheruser:_ingsoc: seems interesting, but not sure how you can prove you put energy into the grid
03:47:10_ingsoc:That was the problem if I remember correctly, needed some physical layer.
08:42:46_ingsoc:_ingsoc is now known as Guest12197
09:27:37_ingsoc:So, get a hold of this Ethereum!
11:00:10nOgAnOo:Special ones.. I am loving ou now.
11:23:37ssshhh:ssshhh has left #bitcoin-wizards
11:48:07Coinsey221:Coinsey221 has left #bitcoin-wizards
12:32:32gmaxwell:adam3us: schnorr multisignature seems to be naturally sidechannel busting.
12:32:52gmaxwell:adam3us: e.g. you do 2-of-2 with the hardware wallet signing first... and the final R,S could be anything.
12:33:36gmaxwell:and avoids the other complexities with the device knowing what its signing when the signature is blind.
12:33:37adam3us:gmaxwell: yes. i mentioned two variants of the wallet observer thing on https://bitcointalk.org/index.php?topic=428494.new#new
12:34:06adam3us:gmaxwell: the basic one that brands talks about uses blind sig so the wallet has no subliminal channel
12:34:50adam3us:gmaxwell: but using brands ZKP issuing protocol, you can also prove to the wallet what it is blind signing, so it can show it on screen for approval with a hw wallet with screen like trezor, and STILL not have a subliminal channel
12:35:30adam3us:gmaxwell: i'm sure brands covered that somewhere in his thesis, the guy is exhaustively inventive.
12:36:09adam3us:gmaxwell: but yeah the subliminal channel freedom is beautiful thing to have as a building block
12:37:51gmaxwell:adam3us: Right but I believe that a regular 2 of 2 threshold signature has the same sidechannel elimination effect without requring the ZKP proof of what its signing.
12:38:25adam3us:gmaxwell: ah gotcha. yes that appears to be true also :) and nice and simple
12:52:17adam3us:gmaxwell: btw other than adding cc other authors, about the private key issue, another step could be to make an ID / RFC on EdDSA as a complement to the safe curve focused ID that Watson Ladd on IRTF CFRG is doing. i thnk the lowest 3 bits=0 is just a optimization, I dont immediately see why that cant be removed and multiply by 8 somewhere in the verification relation, and the bit 254 I think is just defensiveness
12:53:34adam3us:gmaxwell: ie bit 254 is not necessary for security, just that the montgomery ladder start at bit 254 whether its 0 or 1 to avoid a timing side-channel. thats all if anyone had time/energy for an RFC process but it would be a natural way to extract feedback from the algorithm authors
15:25:10wallet421:wallet421 is now known as wallet42
15:28:15roidster:roidster is now known as Guest66358
17:25:18jtimon:maaku,what if we start with the private chains? http://freicoin.freeforums.org/freimarkets-t717.html#p6913
17:25:47jtimon:not sure if wrong forum or not...I'll say the same on #freicoin just in case
19:12:38petertodd:lol twister: https://groups.google.com/d/msg/twister-dev/h2ukT1msggc/Jbh-UPYPGiIJ
19:12:44petertodd:"May someone suggest a good free captcha generator for text that is OCR
19:12:59petertodd:apparently they have a namesquatting problem...
19:13:24petertodd:they also have implemented ripple-style soft-consensus to prevent rewrite attacks
19:13:53gmaxwell:uh.. how does that work with anonymous participation?
19:14:08petertodd:good question!
19:14:15petertodd:that's the lead dev suggesting that!
19:15:13petertodd:they don't even use namecoin-style two-stage commit-reveal, so an attacker can watch the network for new name registrations and register all new names for themselves
19:16:49petertodd:I almost want to fire up some ec2 instances and 51% the network with empty blocks just to see how they'll react - it's a social experiment at this point
19:17:06Luke-Jr:I think I like how with namecoin, if two people register the same name concurrently, both lose their coins ;)
19:17:17gmaxwell:I take it this isn't merged mined?
19:17:21petertodd:gmaxwell: nope
19:17:31gmaxwell:sha256 pow?
19:17:50petertodd:gmaxwell: and they changed the block header so standard scryptminers don't work, but with some effort you can still modify litecoin scrypt miners to mine it
19:18:01gmaxwell:ah. scrypt.
19:18:02petertodd:gmaxwell: they added CBlockHeader.nHeight
19:18:25gmaxwell:and just made the header a bit longer or?
19:18:35petertodd:but they left nVersion=2 and the supermajority code in for nVersion=2!
19:18:38petertodd:gmaxwell: yup
19:18:54gmaxwell:that probably actually won't break the gridseed asics, the work generator is apparently microcoded.
19:19:00petertodd:gmaxwell: I haven't looked into how hard it'd be to adapt a scrypt miner to that
19:19:04petertodd:gmaxwell: oh nice!
19:19:34gmaxwell:(they have an on chip work generator and increment logic which is apparently all microcoded)
19:20:54petertodd:gmaxwell: amir was trying to convince them to just use namecoin
19:21:26gmaxwell:namecoin codebase is nearly unmaintained. :(
19:21:39petertodd:twister codebase is worse than unmaintained
19:23:01gmaxwell:hopefully once scrypt mining asics exist in large enough quantities to have driven everyone off gpu mining people will go back to making merged mined things.
19:23:43petertodd:meh, merge-mining is no perfect solution either - just makes it easy to be attacked early on
19:24:05gmaxwell:petertodd: changes who can attack, for something which isn't compeating with bitcoin it's probably fine.
19:24:40petertodd:gmaxwell: you can be in trouble by competing with another merge-mined system you realize...
19:25:24gmaxwell:perhaps, but it's not clearcut. if 60% of your hashrate is really bitcoin miners who totally don't give a shit about any of these things attacking becomes hard.
19:25:47gavinandresen:gmaxwell: I think scrypt mining asics will just drive people to a wakier-proof-of-work-coin (Quark maybe).
19:26:42petertodd:gmaxwell: easy to start offering people >100% paying shares to quickly buy hashing power for an attack
19:26:51gmaxwell:gavinandresen: Thats a point! "DDD coin's Proof Of Work involves ringing peoples doorbells and running."
19:27:10gavinandresen:gmaxwell: lol
19:33:10petertodd:gmaxwell: anyway, I think I've got my "tree-chains" concept in decent shape: blockchian is a sharded tree, each node in the tree has left and right leaves that are half the difficulty of the parent node/chain. have participants have consensus about the contents of the blocks in the parent chain, and the blockheaders for left and right. the rule for left and right child chains is that full-diff PoW solution "locks" the order of the chain, so ...
19:33:16petertodd:... re-ordering takes 51% with respect to the parent work. However contents are subject to 25% majority. You solve the "lost-data" problem by allowing the mining of a challenge - a tx that you want to see mined - and that tx must either be proved to be not minable (e.g. succinct MMR TXO) or prove that the tx was mined. If nothing happens, eventually the child chain can be re-orged.
19:34:20Guest72236:Guest72236 is now known as jarpiain
19:34:30petertodd:Security guarantees are resistant to 50% attack for re-ordering transactions, 25% for censorship - however you can pay higher fees/work to force a tx to get mined. Done recursively you *will* get to the point where the PoW effort is too low to be secure, but at least that's an adjustable parameter.
19:34:53petertodd:It looks like merge-mining in a sense, but the challenge rule improves the security guarantees.
19:35:30petertodd:Dunno yet how you'd spend coins from one multi-level deep child chain to a different one - easy to think of cases where you allow inflation attacks.
19:37:04petertodd:gmaxwell: Note how all this is easiest to think about with per-tx work - IE one block == one tx. Also easiest to think about it in practice as a token transafer system - how you'd use it with unrestricted values is an interesting question given the inflation issue.
22:17:50arbart:what is the state of the art of enabling microtransactions?
22:22:59sipa:bitcoin (at the protocol level) isn't designed for microtransactions
22:27:49phantomcircuit:arbart, trust a third party
22:27:55phantomcircuit:remember that the transactions are micro
22:30:57sipa:#bitcoin-dev please, btw
22:31:18arbart:sipa, cool, that is what i was wondering then i guess
22:31:42arbart:and alright, what is the purpose of this channel then, I thought it was similar?
22:33:04Luke-Jr:this channel is more like extreme advanced stuff that isn't really practical :p
22:33:33arbart:well that is what I like :)
22:33:58sipa:arbart: oh, i misread your line
22:34:21sipa:i thought you said "what is the state of enabling microtransactions", which would apply to bitcoin-as-it-exists today
22:34:34sipa:for state-of-the-art, there are some more interesting ideas
22:34:40sipa:like probabilistic transactions
22:34:58arbart:yes, now you are talking :) why i came here
22:36:56gmaxwell:probablistic transactions are more of a social/political challenge than a technical one. (I think the lottery protocols iddo/adam3us worked on can basically be applied directly to create a probablistic payment)
22:37:17arbart:ah interesting, i didn't find this before, now searching 'probabilistic transactions', i find much stuff! sipa, thank you already!
22:37:59sipa:arbart: gmaxwell certainly has more state about it than i do
22:39:21arbart:gmaxwell: what is the social/political challenge you see with it?
22:39:57Luke-Jr:arbart: 'probabilistic transactions' essentially means 9 times out of 10, you get nothing, and the 1 other time you get a penny
22:40:17gmaxwell:arbart: Many people seem to not regard a probablistic payment as a payment.
22:41:35arbart:ok, i'm starting to see. reading https://bitcointalk.org/index.php?topic=62558 right now.
22:43:53sipa:gmaxwell: many seem to not regard playing lotto as paying tax either
22:46:00gmaxwell:sipa: People are implementing batch DSA verification in this thread: https://bitcointalk.org/index.php?topic=427025.0
22:46:04arbart:it is interesting so far :)
22:46:29arbart:i understand it now
22:47:41sipa:gmaxwell: how do they overcome not knowing R.y?
22:47:54arbart:i think i am in -wizards and not -dev is because stuff like that gmaxwell is good to have, but not enough a solution, something more extreme :) is needed
22:48:57gmaxwell:sipa: brute force.
22:49:20arbart:i suppose it is hard to tell though, that looks interesting, and combined with pruning and all, might be enable native nanotransactions
22:50:03petertodd:arbart: pruning doesn't make the bandwidth problem go away unfortunately
22:50:07gmaxwell:sipa: basically you guess the sign and test and apparently this still comes out ahead.
22:50:19gmaxwell:arbart: native nanotransactions
22:50:27gmaxwell:doesn't really sound sensible in a global consensus system.
22:50:47gmaxwell:Now, you can do things to perform them non-globally and that perhaps becomes more interesting.
22:50:50arbart:hmm :)
22:50:57petertodd:arbart: now, an interesting question is if you really need global consensus? I think there are blockchain structures that don't
22:51:00arbart:ahh, right
22:51:17gmaxwell:So there are a couple paths to relaxing that which have different tradeoffs.
22:51:22petertodd:arbart: right now just trusting a third-party is probably far more practical
22:51:45arbart:maybe global checkpointing, but only local is interested in the details usually, etc?
22:52:00petertodd:arbart: trusting third-parties and non-global-consensus blockchains have interesting convergence re: security I suspect
22:52:13gmaxwell:are you just stringing words togeather? :P
22:52:17arbart:i understand the third-party thing, another avenue im interested in
22:52:19petertodd:arbart: global *ordering* is a better term
22:52:50petertodd:arbart: heh, lets see if I can explain my pet idea to you re: tree-chains... so imagine you have a blockchain, and you merge mined two child chains with it, left and right.
22:52:57arbart:only out of the necessity you think is there
22:52:57petertodd:arbart: you know what merge-mine means?
22:53:31arbart:ok, i get that term
22:53:50arbart:petertodd: not yet
22:54:23petertodd:mining: I find a pow solution so that my block will be part of the consensus
22:54:55petertodd:merge-mining: the rules of the system let me re-use a pow solution from a different consensus system, letting me do one bit of work, yet get two blocks from two different systems
22:54:56arbart:ok, intuitive :)
22:55:40petertodd:merge-mining is implemented by just letting you prove the block solution for sytem #2 by showing a merkle path through some tree that terminates in the blockheader for system #1
22:55:51petertodd:(namecoin does this)
22:56:11arbart:ok, i was guessing that, so i think i got it :)
22:56:55petertodd:right, so we have the parent chain, and two child chians, left and right, got that? you can mine the parent chain, or the parent chain and the left chain, or parent and right chain (in our system)
22:57:05arbart:petertodd: was just about to prod you :)
22:57:15petertodd:basically it's *exclusive*, you can only mine the left *or* right child chain (or neither)
22:57:31arbart:oh ok, noted
22:58:03petertodd:this means the work done on these child chians will tend to be half that of the parent (assuming the reward is halved for instance)
22:58:44petertodd:however, this also means that a given miner only needs the data, and thus bandwidth, cost of the parent and one child. so the total # of transactions in both children can be higher and the system still works
22:59:06petertodd:the downside is that transactions in either child chain have less security, it only requires 25% of the hashing power to reorg that chain as the parent chain
22:59:20petertodd:got that?
22:59:53arbart:oh wow, yes, a load balancing mechanism :) thinking about the security aspect though
23:00:50petertodd:yeah, so we've figured out how to make it more scalable, now, what about the security? well, lets make a new rule! if a pow solution for a child chain *also* meets the difficulty of the parent, we say that block is fixed - it's only allowed to be reorganized if the parent chain itself gets reoganized
23:01:14petertodd:now it takes 50% of total hashing power to attack the child chain right? nope
23:01:19petertodd:can you guess why?
23:01:21arbart:i guess im missing the reorganized part
23:02:04petertodd:reorg just means work is done to extend a block other than the current best block, so when your node learns about the longer chain, suddenly the shorter one is made invalid by definition
23:02:14arbart:well at least because only half the network is working on each side of the chain?
23:02:17petertodd:remember, the problem bitcoin is trying to solve is consensus on what's the longest chain
23:02:36arbart:ah nice okay, was just missing that definition
23:02:42petertodd:arbart: sure, but an attacker can still get some hashing power somehow and reorg one of those child chians, and they only need 25% of the total hashing power to do that
23:02:43arbart:or word i mean
23:03:40arbart:ah right, half of half, got it now.
23:04:04Luke-Jr:petertodd: you coming to Miami?
23:04:23petertodd:so here's the question: with this fancy "parent chain locks things" scheme, why can the child chain be still attacked with just 25% hashing power?
23:04:33petertodd:Luke-Jr: isn't that, like, right now?
23:04:38Luke-Jr:petertodd: tomorrow :p
23:04:52petertodd:Luke-Jr: heh, nah, tomorrow's my last day of work, couldn't make it
23:05:12petertodd:Luke-Jr: how long does it go? I guess I could strictly speaking... :P
23:05:13Luke-Jr:Saturday and Sunday is the main conference! :p
23:05:24petertodd:Luke-Jr: heh, nah, too tight
23:05:27arbart:hmm, that is a sucky result, a good question to analyze, in order to make sure it is right :)
23:05:30Luke-Jr:Friday is just the pre-conference thing
23:05:43petertodd:arbart: Well, lets think this through: what does attack mean anyway?
23:06:14petertodd:arbart: So, I could attack the chain by making only empty blocks and make it useless, I could also attack it by reorganizing it and double-spending transactions... but there's one other thing I can do.
23:06:29arbart:well the value of what they are attacking is also half i suppose. that counts for enough to throw the game theory?
23:06:42Luke-Jr:petertodd: the first case is debatable
23:06:54petertodd:arbart: maybe! but what if they're just assholes and want to burn the world?
23:07:02petertodd:arbart: we might as well know how much said assholes need to spend
23:07:12arbart:so the one you didn't list is to just not allow new txs to be added?
23:07:19petertodd:Luke-Jr: for sake of argument, we'll say empty blocks are an attack
23:07:25petertodd:arbart: yup
23:07:26gmaxwell:"making only empty blocks and make it useless"
23:07:36arbart:ok, heh, that is the main one i knew about
23:07:46petertodd:arbart: oh, sorry, no, there's one I didn't list that's more subtle
23:08:03arbart:petertodd: ok, i understand, and agree with that knowledge being valueable!
23:09:01petertodd:arbart: I'll give you a hint: this rule where a particularly good PoW "locks" in the chain, how would you actually implement that?
23:10:09arbart:oh my, so put in their own entire child chain?
23:10:46petertodd:well, here's the big thing: in this scheme I'm assuming that miners mining these child chains also have full consensus on the parent, and all associated data
23:10:58arbart:i wondered about the exact implementation of what you asked there, but did not forumlate or see how it is done yet.
23:11:09petertodd:yeah, implementation is critical
23:11:32arbart:i was thinking it wouldn't be that easy for my fear there
23:11:41petertodd:see, I'm thinking that the fact that a child block was found would be known from examining *just* the parent blockchain, IE, put the child blockheaders in the parent blocks
23:12:42arbart:makes sense, it is a worked on (child) block with provable difficulty, some hash of it in the parent blockchain, something like that right?
23:13:24petertodd:yup, and importantly, by just examining the parent blockheaders+part of the blocks, you can come to consensus about the state of the child blockchain without knowing what the actual blocks are, just like SPV mode in bitcoin
23:14:22petertodd:and remember that miners who don't care about the particular child chain aren't checking the contents of the child chain's blocks, only that the child blockheaders are valid
23:15:06arbart:its like sharding but in bitcoin, i really like it
23:15:55petertodd:well, it sounds good... but there's a nasty problem with what I've described: What happens if a child-chain miner mines an invalid block, or mines a block and never gives anyone the actual block data?
23:16:35petertodd:Remember, we said the rule was that once the blockheader met the parent chain difficulty, it when in that chain and locked in that version of history so that we had 50% attack security rather than just 25%
23:17:07arbart:yes, i often wonder about that (the data block, where is it published? a concurrent distributed datastore?)
23:17:36petertodd:Excellent question! It's only "published" by giving it to other miners, there's no central place where a block goes.
23:18:03petertodd:So here we've accidentally created a system that grinds to a halt if a blockheader gets in the parent chain - with full difficulty - but the block itself never gets distributed. Ooops!
23:18:23arbart:i see, it is provable and thus accepted, but then missing
23:18:39arbart:arg :/
23:19:34petertodd:However, we can fix this, with what I call a challenge: Mine another full-difficulty block that basically says "OK, I want this tx to be mined, and it spends these txouts. Prove that either the tx has been mined in the child chain, or that it's invalid. If you do neither, then we relax the rules and let the chld chain get reorganized anyway."
23:20:32petertodd:Or, equally the challenge could be "Where the !@#$ is block n? Stick it in this chain so we can all see it, and if you don't, we get to reorganize the chain."
23:21:30arbart:Oh, I get it now :)
23:21:41petertodd:With either version of the system (or both!) you still get the property that reorganizing the chain is hard *if* enough child-chain miners actually have the data - they can easily meet that challenge.
23:22:04petertodd:If the data gets lost somehow, or hidden maliciously, or whatever, then at least the system can recover and move on.
23:22:55petertodd:With the former version, where you can force a tx to be mined, you can always pay something like 2x the fees to get a tx mined even if some >25% attacker is trying to make the chian useless with empty block - not perfect, but better than nothing.
23:23:53petertodd:And of course, once you imagine a parent with two children... you can recurse this as deep as you want for as many tx's/second as you want.
23:24:42arbart:I was thinking recursive the whole time :)
23:24:47petertodd:hehe, good
23:25:27arbart:so who issues the challenge block? what basic condition triggers it?
23:25:58petertodd:Anyone can by mining a block meeting the parent PoW difficulty with the special challenge data in it.
23:26:45petertodd:Now, I'd expect that in a working implementation, you'd just make it possible for the 75% majority to see "Hey! Someone really wants a tx mined! Lets make it into a challenge."
23:32:40arbart:A challenge block would just have additional challenge code in it, so the miner is not forgoing tx fees and such?
23:33:56arbart:I do understand the tree-chain part itself and think it is a great idea.
23:33:58petertodd:Good question! I dunno exactly - challenges in themselves are probably possible to use in certain types of attacks. I mean, heck, you're forgetting the even bigger question of "How do I turn this crazy thing into a useful currency transaction system?"
23:35:03petertodd:For instance, can a tx on child left-left-left spend a txout from child right-right-right? Probably, with succinct merkle-path proofs. (like the (U)TXO stuff that people are working on) But what happens on a re-org? Didn't that just cause inflation?
23:35:16petertodd:(specifically double-spend inflation)
23:36:15arbart:This thing? are you referring to Bitcoin? I think it already is :) Tree-chains would augment it to enable killer apps beyond our imagination.
23:36:38petertodd:arbart: Or if not that, to enable killer headaches beyond our imagination. :P
23:37:14arbart:So tree chains might change the nature of Bitcoin as it is? I assumed txs would be rejected if they added inflation. But I think what you are raising then is things like that that would require checking the data? :)
23:38:02petertodd:Ah, but how does the miner on right-right-right know that spending a txout on left-left-left added inflation? Remember, they don't have the blockchain data, they just have a SPV-style proof that the txout existed and was spent.
23:39:22arbart:Yes, I'm seeing what you mean.
23:42:14petertodd:Heh, tough problem 'eh? I've got some ideas, but I'm not sure you can come up with a scheme that makes such systems have transactions as simple as bitcoin.
23:43:07petertodd:But anyway, given I seem to be able to explain it to some random passerby, it's an idea probably good enough to write up and publish. :) So thanks!
23:45:20arbart:It is indeed. If there was a clean recovery from missing blocks you mentioned, and an easy way for an arbitrary node to get any blocks inbetween two points (so alice on right-right-right, bob on left-left-left) in order to verify the merkle-path proofs and all :), that would solve inflation and make it no different than bitcoin as is (well, an evolution, so hard fork as in new version of client, but not incompatible)
23:45:50petertodd:arbart: Crazy thing is you can probably do this as a *soft-fork* even!
23:45:50arbart:If you have it as a pet idea, do you think it is possible? or just interested in mentally checking every so often? :)
23:46:41petertodd:Well remember, the problem isn't getting the blocks, the problem is prohibiting those blocks from getting reorganized, and the txouts getting respent elsewhere.
23:47:01petertodd:Fundementally the system just doesn't have full consensus, and without that it's hard to prevent double-spends.
23:47:14arbart:I was kinda thinking that as you described it. It could be phased in and if not affecting inflation or security, Etc, would be accepted as simply a new version that enhances tx scaling.
23:47:49arbart:I see, possible friction :)
23:49:23petertodd:Yup. Now one possible solution is to move coins around in steps: IE, make left-left-left miners also be forced to mine right-right-right blocks in some pattern, and then move value through that path... but that's inconvenient and takes a long time.
23:49:25arbart:I see, and what bitcoin does is solve the double-spend. I agree that is not something to compromise.
23:50:38petertodd:Yes, although at least we did figure out how to solve double-spending locally and hiarchically. For instance, I could have a transaction spending some 1/4-value token and some 1/2 value token in a parent chain, where the 1/4 value move can only happen if the 1/2 value one does. (but not the other way around)
23:51:29petertodd:Also interestingly, if you have a scheme of binary-sized tokens Adam Back pointed out awhile back that you can easily wind up with something pretty much as private as zerocoin.
23:51:31arbart:Oh that is interesting
23:51:49petertodd:Tokens are kinda inconvenient, but it's a possibility.
23:52:37petertodd:Also, keep in mind that the system as described has inflation as the failure mode, that's stil better than "your tx got reversed and your money vanishes"
23:54:36arbart:Oh I see, interesting. I suppose as long as it is not really possible to purposely cause it in meaningful amounts as an attack.
23:55:18petertodd:well, it's still an attack on the system, arguably, but not an attack on an individual, arguably
23:56:38arbart:Yes, it does seem to eliminate the individual attack.