--- Log opened Fri Mar 01 15:37:32 2013 15:37 -!- petertodd [~pete@76-10-178-109.dsl.teksavvy.com] has joined #bitcoin-wizards 15:37 -!- Irssi: #bitcoin-wizards: Total of 4 nicks [1 ops, 0 halfops, 0 voices, 3 normal] 15:37 !niven.freenode.net [freenode-info] channel flooding and no channel staff around to help? Please check with freenode support: http://freenode.net/faq.shtml#gettinghelp 15:37 -!- Irssi: Join to #bitcoin-wizards was synced in 0 secs 15:37 <@gmaxwell> hi. I see you've arrived on wizard time. 15:37 < petertodd> Lol, it's all I seem to be interested in... 15:38 < sipa> a wizard is never late 15:38 < petertodd> It's interesting how this AST idea would have made adding data to transactions a total non-issue. 15:38 <@gmaxwell> Sort of interesting that it would result in some branches being more expensive to excute than others. 15:38 < helo> not a wizard, but enjoy being mystified 15:39 < amiller> imo being able to execute an AST partially is extremely important 15:39 <@gmaxwell> petertodd: well, it would be a one time hash_size scale increase in scriptsigs. 15:39 < amiller> this would entirely remove the concern about nonterminating scripts 15:39 < sipa> and AST have very strong static analysis abilities 15:40 < petertodd> amiller: Yeah, non-terminating would be rejected for having too much AST-related proof data. 15:40 < sipa> so the cpu cost for validation can always be known in advance 15:40 <@gmaxwell> interestingly you could have NP steps in your execution. 15:40 < petertodd> sipa: Well, defined in advance in a opcode cost table. 15:40 <@gmaxwell> If the spender provides a trace of the execution, effectively, then the network is just checking the execution proof. 15:40 < petertodd> gmaxwell: How so? 15:41 < sipa> yup 15:41 < petertodd> Ah, I see, so the algorithm can be NP, provided your n is small enough, and it's still staticly checkable. 15:41 <@gmaxwell> The idea is the network is not a computer, the network is a proof checker for computation the spender did. 15:41 < HM> o_o 15:42 < petertodd> HM is not a wizard... 15:42 <@gmaxwell> :) 15:43 <@gmaxwell> petertodd: I mean we already have NP steps, e.g. checksig. But looking at the network as a generalized proof checker for computation the spender did makes 'checksig' not so special sounding. 15:44 < amiller> i don't see how checksig is np 15:44 < petertodd> So basically a scriptPubKey is now just the AST head, simple enough, a scriptSig should be a list of index/value's, and then you have a scriptTrace, which is essentially the hash of the state of the stack at each step. 15:45 < petertodd> (scriptSig being index values to allow for provided the minimum proof if there could be a lot of potential input data) 15:46 < petertodd> If the scriptTrace includes each opcode executed, it's also staticly analyzable. 15:58 <@gmaxwell> amiller: "provide me a value that makes this ecc signature validation return true". 15:58 < amiller> ah okay i see 15:58 < amiller> yeah. 15:58 < amiller> so that's basically the way of encoding proof of work puzzles within the scripts 15:59 < amiller> it would be really useful to be able to encode a whole chain validation rule within the script 15:59 < amiller> that would be the basic technique to do multichain transactions 15:59 <@gmaxwell> results in ennnnooorrrmmooouuusss signatures. 15:59 < amiller> i don't see why 15:59 < amiller> you can still have ecdsa and hash as primitives 16:00 < petertodd> Yes, but signatures right now are like, 3 steps. 16:00 < petertodd> Unless you are relying on high-level opcodes only. 16:00 <@gmaxwell> doubly so if the other chain is a merklized linked list instead of a merkle mountain or merkle skiplist. 16:01 < petertodd> On the other hand, at least we're honestly forcing them to pay for all that execution. 16:02 <@gmaxwell> 11kbytes/day for a bitcoin SPV proof for just the headers alone. 16:02 < amiller> i don't follow what that consists of 16:02 < petertodd> ...although, it's interesting how now you can run into situations where someone says "Here, I'll pay you by giving you the scriptSig to spend this scriptPubKey" and you need to ensure the protocol knows damn well what kind of proof will be required. 16:02 < petertodd> *how long a proof is requried 16:04 <@gmaxwell> amiller: I make a payment to you conditional on a payment in another chain. To prove it you have to show the fragment, headers after the fragment to show its burried, and headers before the fragment to show its the right chain 16:04 <@gmaxwell> Otherwise I just make N minimum difficulty headers off in forkland and call it a day. 16:04 < amiller> hm 16:05 < amiller> ok i see so that's where the merkle mountain might help 16:05 < amiller> you could encode a looser rule 16:05 <@gmaxwell> if the other chain is something with log n lookup rooted at each block then its less bad. 16:06 < petertodd> Yes, although the merkle mountain chain now needs some idea of how to do random sampling to be sure you didn't just mine some choice headers in the right places. 16:06 <@gmaxwell> Then you want: fragment, next SECURITY_PARAM headers, and a sufficient path to show that the headers are a valid extension of that chain. 16:06 < petertodd> Ideally, which headers are asked for, should be randomly chosen and out of control of the sender. 16:07 <@gmaxwell> petertodd: well what I'd anticipated on my alt chain was making a skiplist where the random backsteps were picked by the apparent difficulty of each block. 16:07 < petertodd> Yes, that would work. 16:08 < petertodd> On the other hand, with merkle mountain, the chain height is provable. 16:08 <@gmaxwell> work being provable is more interesting than height. 16:09 < petertodd> Yes, but height is good for things like "anyone can spend" bonds. 16:09 < petertodd> So I dunno, put in both. :P 16:09 < amiller> even those are probably better off using work but sure 16:10 < petertodd> Ok, so here is a solid AST usage: fidelity bonded ledger refund scriptPubKey's. 16:10 < petertodd> Basically, write a big AST that can accept proofs from anyone wanting a refund, and then only the execution path for the given person being refunded needs to be provided. 16:11 < petertodd> And that path can result in the coins being spent in a way that the remaining people can still get another refund with that txout; IE the txout scriptPubKey will be partially constrained too. 16:12 < petertodd> So the AST itself will encode the bitfield or whatever of remaining tokens to be refunded. 16:12 <@gmaxwell> it simply replaces the terminal leaf with a 0 and then thats required to be the change? 16:13 <@gmaxwell> e.g. a rule that says rebuild this with this node turned to a 0, and thats the change output. 16:14 <@gmaxwell> so as you spend from a AST you could prune the AST to prevent the same code from executing twice. 16:14 <@gmaxwell> kind of a special case for recovery, I can't see another use right now. 16:14 < petertodd> Exactly, or even simplier, the AST includes it's own code in the next AST, and a changing bit of data. 16:15 < petertodd> Now, if these AST proofs are done as an opcode on their own, OP_PARSE_AST, the "what has been spent" thing can basically be just a second AST that puts the stack in the correct way. 16:15 < petertodd> Which means we can implement all this as a soft-fork... 16:16 <@gmaxwell> except for the whole rest of the system which must be replaced, and the security model changes, required to make ginormous signatures viable. 16:16 < petertodd> Finally, rather than provide the whole proof, provide just the hash of, say, the last step of execution, along with an execution counter. The minute that counter hits the limit, script validation stops, yet nodes can still statically analyize how expensive the script could be to spend. 16:17 < petertodd> Not quite as nice, but the scriptSigs are still small. 16:17 < petertodd> (er, sorry, that + the op codes, kinda like a P2SH almost) 16:18 < petertodd> Point is, each op code doesn't need a hash with it for the state of the AST. 16:20 <@gmaxwell> I'm not really following on the ' provide just the hash of, say, the last step of execution, along with an execution counter.' front. 16:21 < petertodd> wait... 16:21 * petertodd doesn't understand the meaning of merkleized... 16:22 < sipa> each node in the AST has a hash associated with it, which depends on that of its subtrees 16:22 < petertodd> yeah, big brain fart there 16:22 < sipa> so the scriptPubKey only needs the root hash 16:22 < petertodd> So basically, scriptSig size is 32 * #of opcodes + leaves 16:22 < sipa> and you provide the path through the tree that needs execution, and hashes of pruned side trees 16:22 < petertodd> (# of opcodes executed) 16:23 < petertodd> Yup 16:24 < petertodd> Actually, with a pile of expensive analyzis, it'd still work, because you would enumerate all the paths through your code... but, that's impractical for anything interesting. 16:24 <@gmaxwell> doesn't have to just be opcodes. The AST could be grouped at the basic block level. E.g. 32 * branches. 16:24 < sipa> yup ^ 16:24 < petertodd> That's reasonable 16:24 < sipa> you'd probably just have one branching opcode 16:24 < petertodd> Yup 16:25 < sipa> that evaluated a boolean, and selects its left or right subtree 16:25 <@gmaxwell> no point in having seperate hashes for each opcode when they are always executed... and no harm in sending a few extra opcodes past an early termination. 16:25 < sipa> and takes a hash for the other 16:25 < petertodd> Yes, and if you hash the strings in reverse order, you can use midstate compression. 16:25 < petertodd> Only provide the proof from the last one you execute. 16:36 <@gmaxwell> random thought what would a txout that had a later specified script be useful for? e.g. you branch to a bit of script that basically checks an ecdsa signature and serialized script on the stack, then OP_EVALS it? 16:38 <@petertodd> That's really useful actually: means you can provide constantly updating refund scripts, that check for some given state of the txout set of something. 16:39 <@petertodd> Without having to screw with on-chain state. 16:40 <@petertodd> So, my bonded bank could say "Here's the script you need to run to get your coins back, but it's only good as long as the refund txouts I'm going to fund it for exist, but I can give you another one later." 16:40 < BlueMatt> but if you can specify any script that is signed, how is it different from just requiring the signature? 16:40 < BlueMatt> because you could otherwise just specify a OP_TRUE script that is signed 16:40 <@BlueMatt> its interesting in that you could give a 3rd party a signed script then they could spend that 16:41 <@petertodd> Because the script itself can check for constantly changing conditions so it can invalidate itself in the future. 16:41 <@petertodd> I was thinking of a crappy version of this with transactions that dependened on special txouts; spend the txout and the transaction is now invalid. 16:41 <@BlueMatt> but in that case, why not just send the coins to them? 16:42 <@petertodd> Because it's for refunds. You want the general case to be done off-chain, with on-chain possible. 16:43 <@petertodd> Basically the bank would control the state of the refund scripts with a single special txout, and then spend it or whatever to invalidate a whole swath of refunds pending in one go. 16:43 <@petertodd> (I'm assuming something like a ISTXOUTUNSPENT opcode) 16:43 <@petertodd> (which has other implications...) 16:43 <@gmaxwell> yea, yuck. :P 16:43 <@petertodd> Hey, give me more than 30 seconds to come up with a use-case... :P 16:44 * BlueMatt isnt sure of all the stuff we are building this on, but I was assuming the standard scripts-only-access-themselves stuff we use now 16:44 <@BlueMatt> maybe I should read scrollback longer.... 16:44 <@petertodd> It is important to keep in mind what Satoshi said ages ago about always allowing transactions to get reorged and accepted into the chain later though. 16:44 <@petertodd> BlueMatt: no, we're getting way more wizard than that. 16:45 <@BlueMatt> thought so...Ill shut up now 16:45 <@petertodd> Nah, just smoke some of this and you'll be good. 16:45 <@BlueMatt> heh, ok 16:45 <@gmaxwell> BlueMatt: well mostly I created this channel for the rocket science which is two steps removed from current Bitcoin. So what bitcoin currently does is only slightly relevant — except to the extent that there is a good reason for it to be done that way. 16:46 <@petertodd> Basically we're gonna create SCAMCOIN and stuff all our dreams into it. 16:46 <@BlueMatt> ok, ok 16:46 <@gmaxwell> I find this stuff important and interesting, but sometimes this discussion floods bitcoin-dev, and I'm concerned that people who are only interested in bitcoin shouldn't get denied access to monitor #bitcoin-dev due to the flood of cryptocoin dreaming. 16:47 <@BlueMatt> thats fair 16:47 <@petertodd> Like, I've contributed maybe 5 lines of code to Bitcoin proper, and 10k lines of dreaming to bitcoin-dev 16:47 <@gmaxwell> plus some of the ideas that the crazy stuff results in are directly applicable to the current system, and we can then bring those back from the mountain tops as required. 16:48 <@petertodd> Lots of this stuff can be done as a soft-fork... 16:49 <@gmaxwell> 'can'... well. Kinda. You can change the script system as a soft fork, but if your change results in 100kb scriptsigs ... thats not a softfork. 16:49 <@gmaxwell> that's not even really 'just' a hardfork, it requires changing the security model. 16:49 <@BlueMatt> anyway...back to the point, if we are accessing outside state, being able to provide signed scripts would be interesting..."either spend this within the timeframe to get out of X, or dont and then you are locked"...assuming signed data can enforce a spend time limit 16:50 <@petertodd> Oh, reminds me, if we define a CHECK_SCRIPT_VERSION type opcode, to be used with new stuff in if endif blocks, we can really change anything but the else if, endif, "invalid even in a block" and finally data encoding opcodes. 16:50 <@BlueMatt> though thats probably not pie-in-the-sky enough... 16:50 <@petertodd> Basically, we're not gonna run out of opcodes. 16:51 <@gmaxwell> BlueMatt: maxtimes create some weird incentives, though I wish I knew the full reasons satoshi didn't want them. 16:51 <@petertodd> gmaxwell: Absolutely, 10k limit on scripts for these dreams... 16:51 <@petertodd> maxtimes? 16:51 <@petertodd> oh, right 16:51 <@BlueMatt> gmaxwell: yea, breaks reorgs sometimes, but I dunno, get the time spent signed by oracle 16:51 <@petertodd> See, my understanding is Satoshi mainy was against the reorg breaking problem. 16:51 <@BlueMatt> s/by oracle/by an oracle/ 16:52 <@petertodd> I dunno, I gotta agree with him there. 16:52 <@BlueMatt> (hopefully oracle isnt your oracle......) 16:52 <@petertodd> You could wind up invalidating everything, on the other hand, tx maleabilty also breaks reorgs... 16:52 * petertodd wonders if satoshi realized tx's were maleable from the beginning 16:53 <@BlueMatt> I dont think that was on purpose, if he did 16:53 <@sipa> i don't think he realized the problems with malleability 16:53 <@gmaxwell> I don't know, he must have known that you could stuff in extra opcode.. I doubt he knew the signatures themselves were malleable. 16:53 <@sipa> he also didn't consider hardforks to be a problem :) 16:53 <@gmaxwell> they would have been less of a problem two years ago. 16:53 <@BlueMatt> to be fair, early in bitcoin's life they werent 16:54 <@gmaxwell> Right. 16:54 <@sipa> indeed 16:54 <@petertodd> He did have the mindset of "one true client" is my understanding. 16:54 <@gmaxwell> That makes hardforks less bad. 16:54 <@sipa> one true full client, atleast 16:54 <@petertodd> He wasn't the one who added RPC right? 16:54 * BlueMatt 's head spins with the amount of cross-client cooperation that would be required for a hardfork now 16:55 <@gmaxwell> BlueMatt: Dunno, the software that is actually maintained is not that long a list. :( 16:55 <@BlueMatt> gmaxwell: even still... 16:55 <@BlueMatt> and its getting better quite quick, too 16:55 <@sipa> bitcoind, bitcoinj 16:55 <@BlueMatt> jgarzik's stuff 16:55 <@sipa> anything else? 16:55 <@sipa> bitsofproof maybr 16:55 <@BlueMatt> not used, but at least maintained 16:56 <@gmaxwell> bitcoind, bitcoinj is all I'm aware of that I believe is complete and maintained right now. 16:56 <@petertodd> jgarzik's stuff has broken scripting too - various really major bugs 16:56 <@sipa> libbitcoin may be still alive 16:56 <@petertodd> (which I need to fix...) 16:56 <@sipa> libcoin too 16:56 <@gmaxwell> bitsofproof,cbitcoin,jeff are incomplete but maintained. then libbitcoin, libcoin, bitcoinjs are complete and unmaintained 16:57 <@BlueMatt> oh, random question, how do people feel about implementing upgradability in bitcoinj so that spv clients can semelessly upgrade to full nodes? 16:57 <@gmaxwell> and purecoin, pybitcoin is incomplete and unmaintained, 16:57 <@petertodd> Even non-mining full nodes scare me 16:57 <@petertodd> Until there are multiple network implementations, propagation bugs can effectively cause forks 16:58 <@gmaxwell> BlueMatt: sounds good? One thing I'd like to see happen with the validation support in bitcoinj is badness proof support. There are three main kinds I'd like to see, and two are possible today. 16:59 <@petertodd> https://github.com/mb300sd/Bitcoin-Tool/ <- this is new too 16:59 <@BlueMatt> gmaxwell: elaborate? 17:00 <@BlueMatt> actually, bbl 17:00 <@gmaxwell> e.g. you're a regular spv node, someone then gives you a message that says 17:00 <@petertodd> https://github.com/mb300sd/Bitcoin-Tool/blob/master/Bitcoin%20Tool/Scripts/Script.cs <- C# script implementation 17:00 <@BlueMatt> Ill read scrollback 17:01 <@gmaxwell> BlueMatt: so then you check the fragment and verify the transaction is in the block .. then run your script checker... and the script fails validation. Then you broadcast the message to all your peers, and add thta block to a blacklist that makes you forever reject it. 17:01 <@gmaxwell> The three kinds of proof that I think are most interesting: Proof that a script doesn't validate, proof that the blocks contain a double spend (just two fragments, the later and earlier spends), and proof that the coinbase took too much subsidy. 17:02 <@gmaxwell> The last can't be done without a protocol change, preferably a hardfork. :( 17:02 <@gmaxwell> but it's really easy with a hardfork. 17:04 <@gmaxwell> In any case, the point of all this is: (1) in a world where most people run SPV nodes, if we have this then even a full honest full nodes would provide strong protection. (2) it would allow reduced nodes to participate in validation some. e.g. check 1% of signatures. 17:07 <@petertodd> "Proof that a script doesn't validate" <- any script proposal that allows for queries of any type needs to take the requirements of SPV proof for those queries into account very carefully. 17:07 <@petertodd> For instance, "Does UTXO exist? (but we're not spending it)" requries the UTXO set proofs. 17:08 <@petertodd> Ugly 17:10 <@petertodd> Easy to force really large proofs too... 17:14 <@amiller> i don't see what you mean easy to force large proofs 17:17 <@petertodd> Consider the scriptPubKey: "UTXO_EXISTS ", 33 bytes, yet each proof for each digest will be hundreds of bytes long, if not even more 17:17 <@petertodd> It's a big multiplier 17:17 <@petertodd> (even worse if the proof has to include the whole script...) 17:17 <@petertodd> (er, I mean transaction) 17:18 <@petertodd> like UTXO exists and it has some given output 17:18 <@amiller> gmaxwell, chanserv op add me so i can massage the channel topic? 17:19 <@sipa> #bitcoin-wizards: smoking cryptographic hasj since 2013 17:19 <@amiller> you can smoke trees and you can smoke hash, but only the bitcoin-wizards smoke hash trees 17:20 * petertodd slow claps 17:20 * amiller passes out 17:20 <@sipa> oh, it's hashish in english; even better 17:20 < weex> oh it's THAT kind of party :) 17:20 <@sipa> amiller: haha 17:25 <@petertodd> Say, everyone heard of that paper due to be released in another month or something on implementing chaum tokens within Bitcoin? 17:25 <@petertodd> Anyone managed a sneak peak of it? 17:25 <@amiller> yeah 17:26 <@amiller> those students came and hung out with me for a while 17:26 <@petertodd> Nice? How does it work? 17:26 <@amiller> my current advisor/host pays their advisor 17:26 <@amiller> well it's got an impractical thing about it 17:26 <@petertodd> ? 17:26 <@amiller> first of all it's a global pool of tokens 17:26 <@amiller> one for the whole chain 17:26 <@amiller> second, in order to avoid double spends, they maintain an already-spent lit 17:26 <@amiller> lsit 17:26 <@amiller> list 17:27 <@amiller> which has to be checked in order to validate each spend. 17:27 <@amiller> that's worst-case O(N) which is horrible 17:27 <@amiller> it would only be O(log N) if they just maintained a balanced merkle tree but that still sucks 17:27 <@petertodd> Yeah, but doable 17:28 <@petertodd> So, there basically the already spend list becomes a consensus thing? 17:28 <@amiller> yes 17:28 <@petertodd> Do they just make the list so big you can pick a coin at random from it? 17:29 <@petertodd> (I mean, the set of !in the list) 17:29 <@amiller> no it's basically like 17:29 <@amiller> uh well basically you can't see the list of things included in the accumulator 17:30 <@amiller> i'm not sure how to answer your question 17:30 <@petertodd> Ok, so there is a global accumulator though, and each transaction increments or decrements it? 17:30 <@petertodd> (this is sounded just like fidelity-bonded ledgers...) 17:31 <@amiller> so basically you deposit an ordinary coin into the accumulator 17:32 <@amiller> a blinded token gets added to the accumulator 17:32 <@petertodd> ok 17:32 <@amiller> now when you want to withdraw a coin, you provide an unblinded token and a proof that your unblinded token corresponds to _one of_ the blinded tokens stored in the accumulator 17:33 <@petertodd> Ah, and there is some crypto magic that lets you prove that? 17:33 <@amiller> yeah 17:33 <@petertodd> (wizardry beyond my beginner wizard level) 17:33 <@amiller> apparently they spent christmas break poring through the complete giant catalog of cryptographic accumulators looking for one 17:33 <@petertodd> I assume then that accumulator can grow to be quite large? 17:33 <@amiller> well the accumulator is just some wacky number field thing 17:34 <@amiller> so basically i don't think it grows at all 17:34 <@amiller> it's almost like folding hashes into hashes 17:34 <@petertodd> Hmm... weird, dunno how that would work. 17:34 <@petertodd> I mean, there is the clever trick of "what's the merkle hash of a 2^256 long string of zeros" but... 17:35 <@amiller> http://www.cs.jhu.edu/~goodrich/cgc/pubs/accum.pdf 17:35 <@amiller> this is one of the popular kinds of accumulators based on RSA numbers 17:41 <@petertodd> Hmm... I'm gonna have to read that very carefully... 17:41 <@BlueMatt> gmaxwell: ahh on the spv side, yes ok that is something Id like to do eventually 17:42 <@petertodd> Now, I assume if you have n items in this accumulator, the size of the underlying data must scale by n somehow right? 17:42 <@petertodd> Or do you accept some small possibility of collissions or something? 17:42 <@BlueMatt> gmaxwell: hmm...actually maybe Ill do that as my next project 17:42 <@petertodd> Oh wait, I found it, page 10: O(n) space 17:44 <@petertodd> Because basically, for fidelity-bonded banks/ledgers, I need to be able to have some audit log thing, and have a similar accumulator so any outsider can see that every token purchase and redemption was valid. Although ideally, proofs that they were invalid would be short too... 17:50 <@amiller> there's gotta be better accumulators than that 17:50 <@amiller> i don't see the point of an O(n) size one 17:51 <@petertodd> Well, presumably that can give you a 100% guarantee against collisions. IE there will never exist S1 and S2 such that A(S1) == A(S2) 17:51 <@amiller> something like that 17:52 <@gmaxwell> BlueMatt: there are two other kinds of proofs I forgot to mention (1) double spend alerts, which might fit into the same framework, and (2) proof that a block spends a txn which wasn't it the prior block's utxo set (which we can't do currently) 17:53 <@petertodd> Ok, lets see if I get the concept right: So one possible accumulator would be to construct a merkle tree of a bit field with one bit for every integer between 0 and 2^256. You can prove you added an integer to that set by showing the leaves for an operation updating the appropriate bit, and you can remove an integer with another set of leaves. (equally any deterministic binary tree works) 17:54 <@petertodd> You can't however take two such accumulators, and merge them in this example, without knowing all the bits involved. 17:54 <@petertodd> (well, without knowing S1 and S2) 17:55 <@petertodd> Equally, assign prime numbers in order, and just multiply your primes together, and then the resulting number is an accumulator. 17:55 <@petertodd> That one you can get the union of S1 and S2 easily, but large n's are a problem. 17:58 < HM> the computation under "a simple scheme" sounds expensive 17:58 <@petertodd> HM: I'm sure people have done better than that :P 17:58 < HM> for the dictionary 17:59 < HM> updates and deletions sound cheap 18:00 * HM continues reading 18:02 <@gmaxwell> BlueMatt: by 'doublespend alerts' I mean the mempool kind. ... in thinking about it it was a little annoying to me that they'd untimately enable miners to mine the more profitable of the two. but I guess attackers could give them directly to miners anyways. 18:10 < HM> I'm guessing the interval trick really doesn't work for transactions 18:10 < HM> to find out if Tx is in S 18:11 <@BlueMatt> gmaxwell: yes, essentially it would be nice to provide alerts which can prove a block is invalid in any of the possible ways a block can be invalid that spv nodes cant identify, though many of those arent possible 18:11 <@BlueMatt> re: doublespend alerts...meh Im still not a big fan of putting those in the standard p2p protocol 18:15 <@gmaxwell> BlueMatt: fine with me. I thought you liked them for some reason. I was only really noting that perhaps they'd fit into the same kind of framework, but perhaps not— they have different DOS exposure since the rest are tied to blocks. 18:16 <@BlueMatt> gmaxwell: no, Ive always been against them (since like...years ago) 19:08 <@petertodd> Alright, I read over the accumulators stuff, and it seems to me that it isn't magic and doesn't help fidelity-bonded foo's. 19:10 <@petertodd> Basically, the key thing is you can use them to add a blinded token to an accumulator, and later prove that the token was in there, but only if every step gets witnessed. 19:10 <@amiller> there's lattice-based accumulators that are even fancier 19:10 <@amiller> i really don't understand this stuff very well either 19:10 <@petertodd> Oh yeah? Hmm... maybe more reading... 19:11 <@petertodd> I didn't see anything about an "authenticated add", but maybe I'm missing something. 19:11 <@petertodd> (specifically, a *signed* blinded token) 19:12 <@petertodd> Ultimately the problem to solve is how to stop the ledger from faking withdrawals. 19:13 <@amiller> i mean you're right that everything has to be witnessed 19:14 <@amiller> like only a valid transaction can update the accumulator 19:14 <@petertodd> Yeah, and you want token-to-token transactions. 19:14 <@petertodd> Although I kinda punt there and assume Tor is available and logs will be made public and randomly audited... 19:15 <@amiller> yeah no token to token transactions... well i mean i guess that wouldn't hurt anything 19:15 <@petertodd> Well, it kills my dream of off-chain tx's. :P But it'd make for a great coin mixer. 19:24 <@gmaxwell> petertodd: whats the problem for you right now? you make a public log available ... the bank can't inflate without it showing up in the log. 19:26 <@petertodd> gmaxwell: Well, the log will have a sum of all chaum deposits made right? Each token redemption will decrement that counter, but there is nothing stopping the bank from creating tokens that didn't correspond with withdrawls, however they're fraud is limited to the amount deposited because of the running sum. 19:27 <@gmaxwell> ah, because the bank can sign in hiding and people can't tell if a newly presented unblinded signature was a previously existing blinded one or just something the bank pulled out of its rear end. 19:27 <@petertodd> ...and actually, I skipped a step, because really any blinded token whose inner part isn't made public, can be fraudulently counterfitted, so clients should unblind their tokens and "register" them. 19:28 <@petertodd> If no clients do that, the bank can create an unlimited number, on the other hand doing so does create information leak possibilities. 19:28 <@petertodd> Exactly 19:29 <@petertodd> Now with an accumulator, I guess you could prove that the token was part of the accumulated value, and thus prove it really dis correspond to a deposit, or even token-to-token exchange. 19:30 <@petertodd> *did 19:30 <@gmaxwell> well, you could— at the cost of some privacy, roll the keys, so that you'd know that the outstanding balance had to all be expressed in some window. 19:31 <@petertodd> Yeah, if not for the chaum part it'd be simple. 19:31 <@petertodd> You can have clients come back and do a unblinded register step for sure. 19:31 <@petertodd> Just hard to get good parameters to maintain privacy. 19:32 <@gmaxwell> at some point this should get built, even if its just a toy insecure form. 19:33 <@gmaxwell> people were talking in #bitcoin-offtopic about building an IRC micropayment bot... 19:33 <@petertodd> Did you read my bonded ledgers thing? 19:33 <@gmaxwell> You send it 1btc.. then you can bot: pay petertodd 0.012345 btc and eventually petertodd can checkout if he likes. 19:33 <@petertodd> The idea of focusing on making a ledger who you are only holding to not allow double-spends to happen is nice. 19:34 <@gmaxwell> Not secure, not private, etc. But it would be insanely useful. It would do micropayments instantly in a way bitcoin cannot, it would avoid blockchain bloat and transaction fees.. etc. Even the weakest forms of your chaum bank stuff would be better than "just trust the bank" 19:35 <@gmaxwell> the bonded ledgers was just the OP code for double spends? 19:35 <@petertodd> Yeah, and if it's just a ledger, you could re-use all the Bitcoin transaction machinery, including machinery to do double-spend proofs. 19:35 <@petertodd> Pretty much, and if the scripting system was just slightly more powerful, you probably wouldn't even need a dedicated opcode. 19:36 <@gmaxwell> I wonder how you could construct its transactions to make the proof of doublespending maximally small? 19:37 <@petertodd> Basically decompose CHECKSIG, allow for string manipulation, and provide a way to constraint was the txout set of a scriptPubKey spend is. 19:37 <@gmaxwell> though I suppose ideally it would work on bitcointransactions so you could use it for both on and off chain doublespending prevention. 19:37 <@gmaxwell> though that presupposes a public ledger which is lame. 19:37 <@petertodd> Well, one key thing would be for signatures to use a hash tree to generate the hashes. You just have to show that the inputs were the same both times, not the outputs. 19:38 <@gmaxwell> yea, I've wanted to define a transaction format that is tree structured— for other reasons: to build altchains that don't validate burried signatures. 19:38 <@petertodd> Public ledger is the easiest, but you don't have to do that. One way would be to use a crypto accumulator ont he set of all txins spent. 19:39 <@petertodd> So you would challenge the ledger periodicly to prove they didn't double-spend your transactions. 19:39 <@petertodd> hmm... actually, that could work very nicely... 19:40 <@petertodd> You do need the ledger to publish some type of "state of the ledger" publicly, in a way that can be retrieved anonymously, but, for instance, that could be done with the ledgers deposit and withdrawl transactions as a smalldata. 19:41 <@petertodd> Basically, for any tx the ledger ever makes, if you find the ledgers signature on it you can simple say "OK, so that's the state of the ledger, now prove to me that you didn't double-spend my input" 19:41 <@gmaxwell> the advantage, e.g. of an irc paybot is better scale for microtxn, and improved privacy (basically privacy more like IRCs: not cryptostrong but ephemerial so long as everyone is playing nice) 19:42 <@petertodd> And when you accept a transaction from the ledger, ask for *that* transctions history, back to where it came from in the blockchain. 19:43 <@petertodd> I assume you've seen reddit's bitcointip right? 19:44 <@gmaxwell> yes. pretty horrible in that it makes a bitcoin txn per tip or at least it did. 19:44 <@gmaxwell> "worst of all worlds: insecure, slow, and non-scalable" 19:44 <@petertodd> Pretty sure it still does; it's blockchain.info based. 19:44 <@petertodd> Especially given the tiny size of tips. 19:45 <@gmaxwell> Yea, b.i — unlike mtgox— doesn't even have a facility for internal transactions. 19:45 <@petertodd> OK, so there's a goal: an library for auditable off-chain transactions. 19:45 <@petertodd> Well, how could b.i and still meet it's security promises? 19:46 <@gmaxwell> by allowing you to have some portion of your balance with b.i instead of in your wallet, of course. 19:46 <@petertodd> Well, sure, but then they need my auditable off-chain tx library. :P 19:46 <@gmaxwell> :) 19:46 <@gmaxwell> mtgox seems to do fine without one. 19:47 <@petertodd> mtgox is big enough to have credibility, of coruse, so is b.i 19:47 <@gmaxwell> What would the audits prove? 19:47 <@petertodd> The audits *could* prove fraud, if caught. 19:47 <@gmaxwell> I mean what kind of fraud. 19:47 <@petertodd> Well, lets say the ledger is internally doing a full blockchain basically, one tx per block. 19:48 <@petertodd> Each block is signed by the ledger, and the blockchain is linked by a merkle mountain range hash system. 19:48 <@petertodd> You also have a UTXO proof system basically. 19:49 <@petertodd> So, one valid query would be to ask "Give me a full transaction history from my tx back to the on-chain tx" 19:49 <@gmaxwell> Right, how do you avoid the proofs not becoming exponential as coins split and merge? 19:49 <@petertodd> It's a good question, likely the ledger can only say "proofs will never be more than 1MiB" or something. 19:50 <@gmaxwell> basically, I'm thinking this hidden blockchain model imposes some performance limits on the dumb-irc-bot-bank that would be unfortunate. 19:50 <@petertodd> I mean, heck, just make the whole thing downloadable, and every year or so just throw it away and start fresh. 19:50 <@petertodd> Yeah, it's a tough one. 19:51 <@petertodd> Double-spend fraud in the ledger is detectable enough, with a spent-UTXO accumulator. 19:51 <@gmaxwell> well what do we really need to prove: that the users balances sum to the deposits, right? What else for that application? 19:51 <@petertodd> Yes, I think that's the biggest one. 19:52 <@petertodd> The other thing is proving that the ledger isn't giving me my money back, although for now that doesn't need to be automatic. 19:53 <@gmaxwell> So, the bot publishes an anonmized list of accounts and their balances. And it publishes sigmessages showing it holds an equal amount of bitcoin. You can see your balance in the public list, 19:53 <@petertodd> Hmm... well if every transaction is in a chain, and updates a balance sum, that helps. At least all the transactions to and from the ledger can be easily audited. (to deposit the ledger would sign your deposit tx as well) 19:55 <@petertodd> Do we need balances, or scriptPubKey txout hashes? 19:55 <@petertodd> (with merkle summing) 19:55 <@gmaxwell> if your balance changes on you and you don't agree... you publish a "fuck you, bot stole my balance"--account key. which people hash to get the anonmized account key, and the bot publishes a list of all the txn to your account, and all withdraws should be signed by you. 19:56 <@gmaxwell> and if the bot can't produce a transaction log that matches the balance sheet, we know it robbed that person. 19:57 <@petertodd> That works easy enough. 19:57 <@gmaxwell> initial deposits into the system could basically be handled by the payment protocol type non-repudation. 19:58 <@petertodd> So basically, the bot can't inflate the balance, provided that every user checks that their balance is shown in the public ledger. 19:58 <@petertodd> The ledger balance must match up to the on-chain balance. 19:58 <@gmaxwell> You go to deposit in, bot says "okay, I'll add 1 btc to account H(pubkey), iff you pay address 1unrelated" --bot ... and if you don't get credited you can cry foul on that too. 19:59 <@petertodd> Yes, my fidelity-bonded ledger thing even had a special UTXO out query opcode for that, to use internally with the ledger. 19:59 <@gmaxwell> I don't think that on chain deposits would actually go in directly. Instead the system would be started off with one account: "bank" and a balance owned by the bank. Payments into the system would go into the bank owner's private wallet, and he'd move funds from the bank internal balance to the user mostly. 20:00 <@petertodd> OK, that's reasonable, and as you say, the deposit includes the promise to move the balance from the bank balance to your one. 20:00 <@gmaxwell> (of course the balance balance could be increased over time, but there wouldn't need to be a 1:1 match. This would also enable people to buy space in the bank using chaum tokens, mtgox codes, or whatever they want— since deposit inside the bank and on the chain are decoupled) 20:01 <@gmaxwell> well whatever they want subject to how automated fraud handling should be. 20:01 <@petertodd> It's still very reliant on that public ledger of all balances, but seems doable. 20:01 <@gmaxwell> the public leger would need to be delayed somewhat, I expect. 20:01 <@petertodd> For privacy? 20:01 <@petertodd> Delaying is fine provided it includes some type of hash linking back to your tx's. 20:02 <@petertodd> You want to be able to prove that a tx you performed should have been included in the master published ledger hash, but wasn't. 20:03 < ielo> hello helo 20:03 < ielo> ielo helo 20:05 <@amiller> i think this use of proving txs is only useful if there's osmething automated that happens 20:05 <@amiller> but this is a good reason to want the big bitcoin blockchain to be capable of metavalidation of other chains 20:05 <@amiller> because something like a doublspend in a minor chain can trigger an insurance payout in a larger chain 20:05 <@petertodd> amiller: This is the toy system - we'll implement automated proofs later. 20:06 <@petertodd> amiller: Basically this is Mt. Gox redeem codes + some auditing. 20:13 <@gmaxwell> petertodd: I guess the balance sheet really ought to be a Merkle-sum-tree.. this way they only publish the root, and only allow users to query their own balance. 20:14 <@gmaxwell> if the whole balance sheet is public you can grok out whos transacting with who by observing matching changes in balance. 20:14 <@gmaxwell> with a Merkle-sum-tree deanonymization requires the users to cooperate to deanonymize each other. 20:16 <@petertodd> On the other hand, with opaque transactions, again, what's to stop the bank from creating inflated ones? But if you can audit that, they someone can just troll through the balance sheet and find them all out anyway. 20:16 <@petertodd> (though granted, movements would be harder) 20:17 <@petertodd> It's funny too how balances that sit untouched, can be relatively safely taken by the ledger in fraud/balance expiry. 20:17 <@gmaxwell> petertodd: I don't follow. The bank pays you 100 btc it doesn't have. You check your balance. Is the root correct? if so, then someone elses root will not be correct. 20:18 <@gmaxwell> well such a system would likely fund itself by periodic fees on inactive accounts, this also prunes the account database. 20:18 <@gmaxwell> (it would make txn paying itself from users—) 20:18 <@gmaxwell> and yea, it could rob inactive users and use that to pay other users... though they'd eventually be able to prove it. 20:19 <@petertodd> I guess that's basically my complaint: it relies on users checking for fraud 100%, and each user has to play their part. 20:19 <@gmaxwell> or rather, challenge it and the bank would be unable to prove it didn't. 20:19 <@petertodd> See, I'd say don't worry about balances, just do a straight up unspent txout list as usual. 20:20 <@gmaxwell> yea, but thats less private and also not so scalable. Proving that the bank has the funds to back itself and proving that it hasn't just randomly taken your money is probably the biggest concerns. 20:20 <@petertodd> Merkle sum the txout of course, but leave it at that. 20:20 <@amiller> i'm interested in something which is that normally there's no incentive to communicate information in a p2p network but in bitcoin there sort of is 20:20 <@gmaxwell> Consider the bank like things that put people's money with pirate. 20:20 <@amiller> in the sense that you want to publish proofs because it makes it easier for other people to build on your block rather than undermining it 20:20 <@amiller> same as wanting to obtain the proofs so you can be sure your'e working on a valid block 20:21 <@amiller> it's obvious how by encoding validation rules / proof of work puzzles you can incentivize both storage and computation 20:21 <@amiller> it's less obvious but still seems plausible that you can incentivize communication this way 20:21 <@petertodd> "Consider the bank like things that put people's money with pirate." <- ? 20:22 <@petertodd> Oh, wait, you mean the funds that took peoples money, and forwarded it to pirate. 20:22 <@gmaxwell> petertodd: when pirate poofed a bunch of other stuff poofed too.. bitcoin businesses and such, that has investors money, even an exchange like thing... 20:22 <@gmaxwell> Yep. Even when they were saying that they hadn't done that. 20:22 <@petertodd> Yeah, I see what you mean, you want to audit the backing funds first. 20:22 < HM> i take it nobody got their money back? 20:22 < HM> last i heard he was actually paying some back ? 20:23 <@gmaxwell> people who were paid before the implosion got paid. 20:23 <@petertodd> HM: he kept saying that to keep people hoping, and not suing him. 20:23 <@gmaxwell> and yea ^ that. 20:23 <@petertodd> (post implosion) 20:24 <@gmaxwell> petertodd: in any case, I think thats the biggest sorts of concerns. The UTXO thing would be better but also more complicated less scalable. 20:24 <@petertodd> gmaxwell: Yeah, I'll agree with you on that. Basically, build a client that makes checking for fraud periodically, and ensure people use it, and you're probably doing pretty well. 20:25 <@gmaxwell> so one thing to do would be for every account to be based on two keys, an encryption key for antifraud, and a signing key for spending. 20:26 <@gmaxwell> the system could public all the antifraud proofs, encrypted.. so that it can't tell whos paying attention. 20:26 <@gmaxwell> Moreover, people could hand over copies of their anti-fraud decryption keys to friends that they don't mind losing some privacy to. 20:26 <@gmaxwell> So the burden of checking could be shared. 20:27 <@gmaxwell> ALTERNATIVELY. the system could pay users to check. 20:27 <@petertodd> How so? 20:27 <@gmaxwell> e.g. you get an inactivity fee if you're not checking. 20:27 <@petertodd> Ah, so if the server doesn't get the occasional query? 20:27 <@gmaxwell> right. if the server doesn't get queries from you it deducts your balance until your balance is gone. 20:28 <@petertodd> So, the signing key can be ECC, and then the encryption key should be a private key, so the bank can't publish your details behind your back. 20:28 <@gmaxwell> If you're still querying though you keep a balance. Rather than prevent the theft we instutionalize it. :) 20:28 <@petertodd> And further more, the ledger should also publish the hash of the current anti-fraud proof, so you can always just give someone the proof, and they can verify it. 20:29 <@petertodd> Ha, I like the institutionalizaiton... Standard expiry time thing. 20:29 <@gmaxwell> Well, one way to prevent theft is to give people an honest way to get the same (averaged) gain permissably and within the rules. :) 20:29 <@petertodd> For sure 20:29 <@gmaxwell> but since everyone knows how it works, they can behave accordingly. 20:30 <@gmaxwell> if the bank can rob you if you don't check— make it permitted to do so. (slowly) 20:30 <@petertodd> Also, note how if the leger is purely balanced based, we actually can do chaum tokens still. 20:30 <@petertodd> A chuam transaction just means an increment in the special outstanding token balance, followed by a decrement. 20:31 <@gmaxwell> right, there could be special accounts for outstanding chaums of different sizes. 20:31 <@petertodd> Yup, powers of two would be good. 20:31 <@gmaxwell> and the chaum validation key could be public. Though you couldn't prove that they weren't overprinting chaums. 20:32 <@gmaxwell> but only users with chaum in hand would have that risk. 20:32 <@gmaxwell> well I suppose you could, but were back to the registering thing. :) 20:32 <@petertodd> Yes, they'd be at risk the second every outstanding chaum token gets redeemed. 20:33 <@gmaxwell> I think people are not that uncomfortable with banks that themselves are single privacy points of failure though. I mean— we have that for everything except cash. Use the bank via tor. 20:34 <@petertodd> Probably true really. 20:35 <@gmaxwell> mostly I'd like to see this on testnet, just as a tool to get more people to dork around with testnet... though if the code were available some fool would run it for real. :P I wish them luck. 20:35 <@petertodd> Oh, and it's interesting: withdrawls can be handled just fine using the "non-backing" store of value basically, in the reverse of deposits. So really without a lot of collusion you'd never figure out where coins are going on-chain. 20:35 <@petertodd> Yes, I think "release the code" is a very, very good model... 20:36 <@gmaxwell> yes, thats a good goal and I'd realized that too. 20:36 <@petertodd> Good. 20:36 <@gmaxwell> it also, again allows for more efficient withdraws.. batched, mtgox code, chaum tokens with some other system. 20:37 <@gmaxwell> The only think provable is that the bank holds a certian amount of money, and technically even that proof would only be available to balance holders, you'd make the txids of the holding txn part of the proof hashtree. 20:37 <@petertodd> That also gets you five types of transactions: in-system, proxy-withdrawl, proxy-deposit, real-withdrawl, real-deposit, with the latter two basically only ever happening for the ledgers main account. 20:38 <@gmaxwell> right. Well, and because the in-system traffic is only checked by the system and the involved users you can have whatever complicated rules you want. In system escrow txn? no problem. 20:38 <@gmaxwell> Reoccuring payments?!@# no problem. 20:39 <@petertodd> You know, you can just give the user a way to sign that they accept the balance on their account too, so you can expire old tx history. 20:39 <@petertodd> With part of that signature being over the master hash. 20:39 <@gmaxwell> indeed, then it actually converges on a consensus system. 20:40 <@petertodd> Include a bitcoin proper blockchain hash, and a timestamp, and you can constrain the time quite nicely too so you can do tx history expiration. --- Day changed Sat Mar 02 2013 12:18 < HM> but the advantage of a stack was scriptSigs and scriptPubkeys are easy to combine 12:18 < HM> and evaluate 12:18 <@sipa> which means it can be merkleized: you associate a hash with every node, and by just having the root hash, you can prove that a particular path through the tree belongs to it 12:18 <@sipa> HM: in practice, that is not the case anymore by far 12:19 <@sipa> plus it is hard to analyse 12:19 <@sipa> and actually terribly complicated to write actually useful complex scripts 12:20 < HM> wait, how does one path on an AST prove anything/ 12:20 < HM> ? 12:20 <@sipa> ok, so imagine you had in your script AST language a construct "if BOOL then X else Y", where X and Y are subtrees 12:20 < HM> how would you do multisig for example as an AST 12:21 < HM> that should be a simple example 12:21 <@sipa> you could have a node that requires a valid signature as input (input just becomes a list of values, and the AST refers to specific elements in it) 12:22 <@sipa> combine two such nodes with an AND, and you have 2-of-2 12:22 <@sipa> combine it with an OR, you have 1-of-2 12:22 <@sipa> use a COUNT operator to compute the number of valid signatures on top of 3 such sigchecks, and compare it with >=2, and you have 2-of-3 12:23 < HM> i'm struggling to see how you refer to vin provided values in a script 12:23 <@sipa> ok, so scriptSig just gets replaced by a list of values - no script or anything fancy 12:23 < HM> sure 12:24 <@sipa> our language has these nodes: DATA(X), with X an integer, returns the input value number X 12:24 <@sipa> AND(X,Y), requires X and Y both to evaluate to true 12:24 <@sipa> CHECKSIG(P,S) checks whether S is a valid signature for pubkey P 12:24 <@sipa> oh, and CONST(X), just a constant 12:24 <@sipa> ok? 12:24 < HM> sure 12:25 < HM> i would be comfortable with C operators and parens , but more power to you :P 12:25 <@sipa> so a normal (forget addresses for a while) pay-to-pubkey would be 12:25 <@sipa> CHECKSIG(CONST(somepubkey),DATA(1)) 12:25 < TD> i feel too muggle-like for this channel 12:25 < HM> siga: yep trivial 12:26 < HM> ok now i have to injerect a question 12:26 <@sipa> HM: ok, 2-of-2 multisig becomes: AND(CHECKSIG(CONST(somepubkey),DATA(1)),CHECKSIG(CONST(otherpubkey),DATA(2))) 12:26 < HM> hmm 12:27 < HM> Ok, as long as you're explicitly indexing params it doesn't matter which order things are evaluated in 12:27 < HM> How does a merkle hash play in this ? 12:27 <@sipa> exactly 12:28 <@sipa> well, first one way to write a 1-of-2 multisig: 12:28 <@sipa> OR(CHECKSIG(const(somepubkey),DATA(1)),CHECKSIG(CONST(otherpubkey),DATA(1))) 12:28 < HM> yup 12:28 <@sipa> nothing surprising, i guess, except that it requires two checksig operators, and one will always fail 12:29 <@sipa> now, what if we add a new operator: IF(bool,X,Y), which returns X if bool==true, and Y if bool==false 12:29 <@sipa> then you could write it as: IF(DATA(1),CHECKSIG(CONST(somepubkey),DATA(2)),CHECKSIG(CONST(otherpubkey),DATA(2))) 12:30 < HM> errr 12:30 < HM> ok... 12:30 <@sipa> so your input would be [true,sigforpubkey1] or [false,sigforpubkey2] 12:30 < HM> that would mean the final value is chosen by the redeemer 12:30 <@sipa> indeed 12:31 < HM> are we talking arbitrary scripts or just bools? 12:31 <@sipa> doesn't matter, you can restrict it to just bools if you like 12:31 < HM> ok 12:31 <@sipa> the observation is here that one of the two subbranches of IF will never be evaluated 12:31 < HM> yep, just like in code 12:32 <@sipa> so, in case the AST is merkleized, you could just provide the hash of the X or Y subtree, instead of its full data 12:32 < HM> and a path 12:33 < HM> derp derp 12:33 <@sipa> well, when spending, you give the script: IF(DATA(1),CHECKSIG(CONST(somepubkey),DATA(2)),HASH(X))) 12:33 <@sipa> + [true,sigpubkey1] 12:33 <@sipa> or the other way around 12:34 <@sipa> and the merkle root (which is what the txout specified) remains valid 12:34 < HM> what is X 12:34 <@sipa> the hash of the subtree CHECKSIG(CONST(otherpubkey),DATA(2)) 12:34 < HM> right, so your partner in multisig has to construct that part of the script 12:34 < HM> slot in their signature 12:34 < HM> then hash it? 12:35 <@sipa> or you (as one of the receivers) just knew the two full pubkeys 12:35 <@sipa> the point is that you never have to disclose the pubkey you didn't use 12:35 < HM> right, i see. so basically you're revealing the script like P2SH but blinding branches for privacy 12:35 <@sipa> bingo 12:36 <@sipa> well, there's some mild data-size advantages as well 12:36 <@sipa> but indeed 12:36 < HM> hmm 12:36 < HM> but if the tree is binary you always reveal half 12:37 < HM> i.e. if it's complex and deep you still reveal quite a lot of the script on one side 12:37 <@sipa> if the tree is larger, you can cut away much larger subbranches 12:37 <@sipa> anyway, the largest scalability advantage is that txouts are always just one hash 12:37 <@sipa> which means the only thing that ends up in the UTXO set is one hash 12:38 <@sipa> of course, inputs become larger, and they still end up in the full blockchain 12:38 < HM> what about the implications for hash collisions 12:38 <@sipa> well, if those are a problem, bitcoin is fucked 12:38 < HM> if one branch is 5 levels deep and requires 1000 keys you still only need 1 hash collision to bypass that entire part of the script 12:39 <@sipa> you mean a preimage, not a collision 12:39 < HM> yes 12:39 <@sipa> well, we already assume our hash functions are preimage-resistant, because block mining would become trivial otherwise 12:39 <@sipa> or faking transactions 12:39 <@sipa> or faking signatures 12:40 < HM> hmm 12:42 < HM> How does OR work when you have OR(Somescript, HASH(DATA(1)) 12:42 < HM> if you complete and evaluate Somescript you're done 12:43 < HM> but HASH(DATA(1)) isn't then required 12:43 < HM> or am I getting confused 12:43 <@sipa> HASH(X) is just raw data, it's not a real operator as X is not an AST 12:43 <@sipa> HASH_x is perhaps better notation 12:44 <@sipa> ans any attempt to actually evaluate HASH_whatever, probably should result in failure 12:44 <@sipa> as you've pruned a part of the subtree that was necessary for evaluation 12:44 < HM> right yeah 12:44 <@sipa> compare it to CONST_x, which always evaluates to x 12:45 < HM> argh 12:45 <@sipa> the HASH_x entries are just necessary to make the merkle root of the AST work out 12:45 <@sipa> they aren't really part of the script 12:45 < HM> if you have AND(X, Y) then you can't send a hash for one side of the script can you? both need to be evaluated 12:46 <@sipa> i suppose that you can replace Y by a HASH entry, if you can guarantee that X will evaluate to false 12:46 <@sipa> (short-circuiting behaviour) 12:46 < HM> but then the entire branch is false and might as well not be there 12:46 <@sipa> it may need to be there, to make the merkle root work out 12:47 < HM> so what non-trivial systems does this allow? 12:48 <@sipa> it allows just as much as our script system now (though in an easier way, imho) 12:48 <@sipa> but it permits selective revealing 12:48 < HM> you could just reveal 2 hashes 12:48 < HM> and provide no data? 12:48 <@sipa> anyway, i think it's best to see IF and HASH as one operator, and make that the only way to do selection 12:49 <@sipa> i.e., have an operator BRANCH1(X,hash) and BRANCH2(hash,Y) 12:49 <@sipa> which take the place of IF(true,X,HASH(Y)) and IF(false,HASH(X),Y) 12:50 <@sipa> afk! 12:52 < HM> you could also have an operator that simple duplicates it's sibling branch, but applied some transformation 12:52 < HM> like adding 1 to the index of data 12:53 < HM> that'd be easier if data could exist in pairs 12:54 < HM> AND(A.part1, B.part1) OR AND(A.part2, B.part2) 12:54 < HM> could be compressed to 12:54 < HM> DUP(AND(A,B)) 12:54 < HM> or something 12:54 <@sipa> basically, you want subroutines :p 12:55 < HM> yeah but without having to have something insane 12:55 < HM> DUPing cousins would be difficult 12:55 < HM> you'd need a tree of data rather than an array 12:55 < HM> so each script node had its own parameters 12:56 <@amiller> well this no longer resembles a stack language so subroutine rather than dup is necessary 12:56 <@amiller> what you probably want is a closure? 12:56 < HM> where do you define your subrouting? 12:57 < HM> subroutine 12:57 <@sipa> amiller: yeah, let's just turn it into a untyped lambda calculus :p 12:58 <@amiller> well hopefully not untyped :x 12:58 <@sipa> church-encoding a pubkey shouldn't be hard! 12:58 <@amiller> no no no i promise i'm not trying to say that's practical :p 13:09 < andytoshi> i dunno, if you treat transaction outputs as "(defun [hash]0 ...)" "(defun [hash]1 ...)" 13:09 < andytoshi> you could build a lispchain 13:10 < andytoshi> wouldn't be much slower than emacs ;) 13:10 * andytoshi runs 13:11 < HM> i think it'd be wise to keep ops to a fixed size and then you can evaluate a script recursively without actually constructing a tree 13:13 <@amiller> anytoshi the cool thing about describing it that way is you can just refer to a function by its hash so that works perfect 13:13 < HM> e.g. the opcode and the immediate value, if any, e.g. DATA(2), was always a fixed size 13:13 <@amiller> yeah that's right, you'd want fixed size opcodes 13:14 < HM> yeah, so your script is always an odd number of bytes/opcodes 13:15 < HM> assuming it's a binary tree 13:15 < HM> the memory you need is basically fixed, you just need a register file 13:24 < andytoshi> amiller: right, an altchain that did this would hardcode its genesis block with a hundred or so utility functions 13:25 < andytoshi> i guess you'd also want a tiny recursion limit to prevent ddossing 13:27 < HM> recursion? 13:28 < HM> why are you allowing recursion 13:28 < andytoshi> HM: because it allows very tiny programs 13:28 < andytoshi> but now that i think about it, i think it's impossible if your functions are all named for their hashes 13:29 < andytoshi> so it's a moot point anyway 13:31 < HM> it also makes the thing difficult to reason about --- Day changed Sun Mar 03 2013 03:37 < amiller> http://bitcoin.stackexchange.com/questions/3313/are-there-bitcoin-password-crackers-i-can-use-to-recover-forgotten-passwords 03:38 < amiller> it would be nice to be able to offer bitcoins for a reward like that directly in a transaction script, eh 07:40 < HM> hmm 07:41 < HM> this is why secret sharing would be a nice feature for high value wallet passwords 07:41 < HM> or some equivalent 08:15 < HM> http://echeque.com/Kong/anon_transfer.htm 08:15 < HM> i've been reading this explanation of blinded tokens using EC 08:16 < HM> Why i follow the logic, and see how the issuer (Toby) can be used to create valid tokens that retain privacy, I don't see how the transformation can't be used to create new tokens from spent ones 08:18 < HM> ah wait, of course you have to pay again 08:18 < HM> derp derp 08:18 < HM> Toby won't do shit for free 08:27 < HM> hmm toby presumably has to blacklist R when calculating kR otherwise both (R, kR) and (q, Q) are valid spendable tokens 08:30 < HM> still, i suppose token IDs and hashes can be of different lengths so you won't mistake one for another 08:40 < HM> I guess Toby just values everything he doesn't hash at 0 09:08 < HM> oh nm, of course R,kR wouldn't be valid anyway 12:00 < HM> Heh, wow.... digital signatures using merkle trees 13:44 < amiller_> hm yeah digital signatures were the first use of merkle trees 13:44 < amiller_> they're pretty limited on their own because they're sort of one-time use only 13:48 < amiller_> eh i'm sort of wrong, anyway this is my favorite summary http://emsec.ruhr-uni-bochum.de/media/crypto/attachments/files/2011/04/becker_1.pdf --- Log closed Sun Mar 03 14:17:21 2013