Day changed Fri Mar 01 2013
 -!- amiller [~socrates1@li175-104.members.linode.com] has joined #bitcoin-wizards
 < amiller> okay
 <@gmaxwell> Hi!
 <@gmaxwell> sipa: thats a very cool idea, though it's lame that the basic blocks are likely always smaller than the hashes... so it would have high overhead.
 <@gmaxwell> ... But I guess it would just be scriptsig overhead.
 -!- petertodd [~pete@76-10-178-109.dsl.teksavvy.com] has joined #bitcoin-wizards
 <@gmaxwell> hi. I see you've arrived on wizard time.
 < petertodd> Lol, it's all I seem to be interested in...
 < sipa> a wizard is never late
 -!- helo [helo@unaffiliated/helo] has joined #bitcoin-wizards
 < petertodd> It's interesting how this AST idea would have made adding data to transactions a total non-issue.
 <@gmaxwell> Sort of interesting that it would result in some branches being more expensive to excute than others.
 < helo> not a wizard, but enjoy being mystified
 < amiller> imo being able to execute an AST partially is extremely important
 <@gmaxwell> petertodd: well, it would be a one time hash_size scale increase in scriptsigs.
 < amiller> this would entirely remove the concern about nonterminating scripts
 < sipa> and AST have very strong static analysis abilities
 -!- BlueMatt [~BlueMatt@unaffiliated/bluematt] has joined #bitcoin-wizards
 < petertodd> amiller: Yeah, non-terminating would be rejected for having too much AST-related proof data.
 < sipa> so the cpu cost for validation can always be known in advance
 <@gmaxwell> interestingly you could have NP steps in your execution. 
 < petertodd> sipa: Well, defined in advance in a opcode cost table.
 <@gmaxwell> If the spender provides a trace of the execution, effectively, then the network is just checking the execution proof.
 < petertodd> gmaxwell: How so?
 < sipa> yup
 < petertodd> Ah, I see, so the algorithm can be NP, provided your n is small enough, and it's still staticly checkable.
 <@gmaxwell> The idea is the network is not a computer, the network is a proof checker for computation the spender did.
 -!- HM [~HM@cpc12-woki7-2-0-cust244.6-2.cable.virginmedia.com] has joined #bitcoin-wizards
 < HM> o_o
 -!- HM [~HM@cpc12-woki7-2-0-cust244.6-2.cable.virginmedia.com] has left #bitcoin-wizards []
 < petertodd> HM is not a wizard...
 <@gmaxwell> :)
 <@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.
 < amiller> i don't see how checksig is np
 < 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.
 < petertodd> (scriptSig being index values to allow for provided the minimum proof if there could be a lot of potential input data)
 < petertodd> If the scriptTrace includes each opcode executed, it's also staticly analyzable.
 <@gmaxwell> amiller: "provide me a value that makes this ecc signature validation return true".
 < amiller> ah okay i see
 < amiller> yeah.
 < amiller> so that's basically the way of encoding proof of work puzzles within the scripts
 < amiller> it would be really useful to be able to encode a whole chain validation rule within the script
 < amiller> that would be the basic technique to do multichain transactions
 <@gmaxwell> results in ennnnooorrrmmooouuusss signatures.
 < amiller> i don't see why
 < amiller> you can still have ecdsa and hash as primitives
 < petertodd> Yes, but signatures right now are like, 3 steps.
 < petertodd> Unless you are relying on high-level opcodes only.
 <@gmaxwell> doubly so if the other chain is a merklized linked list instead of a merkle mountain or merkle skiplist.
 < petertodd> On the other hand, at least we're honestly forcing them to pay for all that execution.
 <@gmaxwell> 11kbytes/day for a bitcoin SPV proof for just the headers alone.
 < amiller> i don't follow what that consists of
 < 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.
 < petertodd> *how long a proof is requried
 <@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
 <@gmaxwell> Otherwise I just make N minimum difficulty headers off in forkland and call it a day.
 < amiller> hm
 < amiller> ok i see so that's where the merkle mountain might help
 < amiller> you could encode a looser rule
 <@gmaxwell> if the other chain is something with log n lookup rooted at each block then its less bad.
 < 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.
 <@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.
 < petertodd> Ideally, which headers are asked for, should be randomly chosen and out of control of the sender.
 <@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.
 < petertodd> Yes, that would work.
 < petertodd> On the other hand, with merkle mountain, the chain height is provable.
 <@gmaxwell> work being provable is more interesting than height.
 < petertodd> Yes, but height is good for things like "anyone can spend" bonds.
 < petertodd> So I dunno, put in both. :P
 < amiller> even those are probably better off using work but sure
 < petertodd> Ok, so here is a solid AST usage: fidelity bonded ledger refund scriptPubKey's.
 < 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.
 < 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.
 < petertodd> So the AST itself will encode the bitfield or whatever of remaining tokens to be refunded.
 <@gmaxwell> it simply replaces the terminal leaf with a 0 and then thats required to be the change?
 <@gmaxwell> e.g. a rule that says rebuild this with this node turned to a 0, and thats the change output.
 <@gmaxwell> so as you spend from a AST you could prune the AST to prevent the same code from executing twice.
 <@gmaxwell> kind of a special case for recovery, I can't see another use right now.
 < petertodd> Exactly, or even simplier, the AST includes it's own code in the next AST, and a changing bit of data.
 < 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.
 < petertodd> Which means we can implement all this as a soft-fork...
 <@gmaxwell> except for the whole rest of the system which must be replaced, and the security model changes, required to make ginormous signatures viable.
 < 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.
 < petertodd> Not quite as nice, but the scriptSigs are still small.
 < petertodd> (er, sorry, that + the op codes, kinda like a P2SH almost)
 < petertodd> Point is, each op code doesn't need a hash with it for the state of the AST.
 <@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.
 < petertodd> wait...
  * petertodd doesn't understand the meaning of merkleized...
 < sipa> each node in the AST has a hash associated with it, which depends on that of its subtrees
 < petertodd> yeah, big brain fart there
 < sipa> so the scriptPubKey only needs the root hash
 < petertodd> So basically, scriptSig size is 32 * #of opcodes + leaves
 < sipa> and you provide the path through the tree that needs execution, and hashes of pruned side trees
 < petertodd> (# of opcodes executed)
 < petertodd> Yup
 < 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.
 <@gmaxwell> doesn't have to just be opcodes. The AST could be grouped at the basic block level. E.g. 32 * branches. 
 < sipa> yup ^
 < petertodd> That's reasonable
 < sipa> you'd probably just have one branching opcode
 < petertodd> Yup
 < sipa> that evaluated a boolean, and selects its left or right subtree
 <@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.
 < sipa> and takes a hash for the other
 < petertodd> Yes, and if you hash the strings in reverse order, you can use midstate compression.
 < petertodd> Only provide the proof from the last one you execute.
 -!- mode/#bitcoin-wizards [+o sipa] by gmaxwell
 -!- mode/#bitcoin-wizards [+o petertodd] by gmaxwell
 -!- mode/#bitcoin-wizards [+o amiller] by gmaxwell
 -!- mode/#bitcoin-wizards [-s+tc] by ChanServ
 <@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?
 <@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.
 <@petertodd> Without having to screw with on-chain state.
 <@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."
 < BlueMatt> but if you can specify any script that is signed, how is it different from just requiring the signature?
 < BlueMatt> because you could otherwise just specify a OP_TRUE script that is signed
 -!- mode/#bitcoin-wizards [+o BlueMatt] by gmaxwell
 <@BlueMatt> its interesting in that you could give a 3rd party a signed script then they could spend that
 <@petertodd> Because the script itself can check for constantly changing conditions so it can invalidate itself in the future.
 <@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.
 <@BlueMatt> but in that case, why not just send the coins to them?
 <@petertodd> Because it's for refunds. You want the general case to be done off-chain, with on-chain possible.
 <@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.
 <@petertodd> (I'm assuming something like a ISTXOUTUNSPENT opcode)
 <@petertodd> (which has other implications...)
 <@gmaxwell> yea, yuck. :P
 <@petertodd> Hey, give me more than 30 seconds to come up with a use-case... :P
  * 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
 <@BlueMatt> maybe I should read scrollback longer....
 <@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.
 <@petertodd> BlueMatt: no, we're getting way more wizard than that.
 <@BlueMatt> thought so...Ill shut up now
 <@petertodd> Nah, just smoke some of this and you'll be good.
 <@BlueMatt> heh, ok
 <@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.
 <@petertodd> Basically we're gonna create SCAMCOIN and stuff all our dreams into it.
 <@BlueMatt> ok, ok
 <@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.
 <@BlueMatt> thats fair
 <@petertodd> Like, I've contributed maybe 5 lines of code to Bitcoin proper, and 10k lines of dreaming to bitcoin-dev
 <@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.
 <@petertodd> Lots of this stuff can be done as a soft-fork...
 <@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.
 <@gmaxwell> that's not even really 'just' a hardfork, it requires changing the security model.
 <@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
 <@BlueMatt> though thats probably not pie-in-the-sky enough...
 <@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.
 <@petertodd> Basically, we're not gonna run out of opcodes.
 <@gmaxwell> BlueMatt: maxtimes create some weird incentives, though I wish I knew the full reasons satoshi didn't want them.
 <@petertodd> gmaxwell: Absolutely, 10k limit on scripts for these dreams...
 <@petertodd> maxtimes?
 <@petertodd> oh, right
 <@BlueMatt> gmaxwell: yea, breaks reorgs sometimes, but I dunno, get the time spent signed by oracle
 <@petertodd> See, my understanding is Satoshi mainy was against the reorg breaking problem.
 <@BlueMatt> s/by oracle/by an oracle/
 <@petertodd> I dunno, I gotta agree with him there.
 <@BlueMatt> (hopefully oracle isnt your oracle......)
 <@petertodd> You could wind up invalidating everything, on the other hand, tx maleabilty also breaks reorgs...
  * petertodd wonders if satoshi realized tx's were maleable from the beginning
 <@BlueMatt> I dont think that was on purpose, if he did
 <@sipa> i don't think he realized the problems with malleability
 <@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.
 <@sipa> he also didn't consider hardforks to be a problem :)
 <@gmaxwell> they would have been less of a problem two years ago.
 <@BlueMatt> to be fair, early in bitcoin's life they werent
 <@gmaxwell> Right.
 <@sipa> indeed
 <@petertodd> He did have the mindset of "one true client" is my understanding.
 <@gmaxwell> That makes hardforks less bad.
 <@sipa> one true full client, atleast
 <@petertodd> He wasn't the one who added RPC right?
  * BlueMatt 's head spins with the amount of cross-client cooperation that would be required for a hardfork now
 <@gmaxwell> BlueMatt: Dunno, the software that is actually maintained is not that long a list. :(
 <@BlueMatt> gmaxwell: even still...
 <@BlueMatt> and its getting better quite quick, too
 <@sipa> bitcoind, bitcoinj
 <@BlueMatt> jgarzik's stuff
 <@sipa> anything else?
 <@sipa> bitsofproof maybr
 <@BlueMatt> not used, but at least maintained
 <@gmaxwell> bitcoind, bitcoinj is all I'm aware of that I believe is complete and maintained right now.
 <@petertodd> jgarzik's stuff has broken scripting too - various really major bugs
 <@sipa> libbitcoin may be still alive
 <@petertodd> (which I need to fix...)
 <@sipa> libcoin too
 <@gmaxwell> bitsofproof,cbitcoin,jeff are incomplete but maintained. then libbitcoin, libcoin, bitcoinjs are complete and unmaintained
 <@BlueMatt> oh, random question, how do people feel about implementing upgradability in bitcoinj so that spv clients can semelessly upgrade to full nodes?
 <@gmaxwell> and purecoin, pybitcoin is incomplete and unmaintained,
 <@petertodd> Even non-mining full nodes scare me
 <@petertodd> Until there are multiple network implementations, propagation bugs can effectively cause forks
 <@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.
 <@petertodd> https://github.com/mb300sd/Bitcoin-Tool/ <- this is new too
 <@BlueMatt> gmaxwell: elaborate?
 <@BlueMatt> actually, bbl
 <@gmaxwell> e.g. you're a regular spv node, someone then gives you a message that says <block XXX is bad, here is a transaction and a fragment, run your script checker and you'll see>
 <@petertodd> https://github.com/mb300sd/Bitcoin-Tool/blob/master/Bitcoin%20Tool/Scripts/Script.cs <- C# script implementation
 <@BlueMatt> Ill read scrollback
 <@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.
 <@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.
 <@gmaxwell> The last can't be done without a protocol change, preferably a hardfork. :(
 <@gmaxwell> but it's really easy with a hardfork. 
 <@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. 
 <@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.
 <@petertodd> For instance, "Does UTXO exist? (but we're not spending it)" requries the UTXO set proofs.
 <@petertodd> Ugly
 <@petertodd> Easy to force really large proofs too...
 <@amiller> i don't see what you mean easy to force large proofs
 -!- weex [~weex@fsf/member/weex] has joined #bitcoin-wizards
 <@petertodd> Consider the scriptPubKey: "UTXO_EXISTS <DIGEST>", 33 bytes, yet each proof for each digest will be hundreds of bytes long, if not even more
 <@petertodd> It's a big multiplier
 <@petertodd> (even worse if the proof has to include the whole script...)
 <@petertodd> (er, I mean transaction)
 <@petertodd> like UTXO exists and it has some given output
 <@amiller> gmaxwell, chanserv op add me so i can massage the channel topic?
 <@sipa> #bitcoin-wizards: smoking cryptographic hasj since 2013
 <@amiller> you can smoke trees and you can smoke hash, but only the bitcoin-wizards smoke hash trees
  * petertodd slow claps
  * amiller passes out
 <@sipa> oh, it's hashish in english; even better
 < weex> oh it's THAT kind of party :)
 <@sipa> amiller: haha
 -!- amiller changed the topic of #bitcoin-wizards to: Bitcoin research, hardfork wishlist, ideas for the future - see also: https://en.bitcoin.it/wiki/Hardfork_Wishlist https://en.bitcoin.it/wiki/User:Gmaxwell/alt_ideas
 <@petertodd> Say, everyone heard of that paper due to be released in another month or something on implementing chaum tokens within Bitcoin?
 <@petertodd> Anyone managed a sneak peak of it?
 <@amiller> yeah
 <@amiller> those students came and hung out with me for a while
 <@petertodd> Nice? How does it work?
 <@amiller> my current advisor/host pays their advisor
 <@amiller> well it's got an impractical thing about it
 <@petertodd> ?
 <@amiller> first of all it's a global pool of tokens
 <@amiller> one for the whole chain
 <@amiller> second, in order to avoid double spends, they maintain an already-spent lit
 <@amiller> lsit
 <@amiller> list
 <@amiller> which has to be checked in order to validate each spend.
 <@amiller> that's worst-case O(N) which is horrible
 <@amiller> it would only be O(log N) if they just maintained a balanced merkle tree but that still sucks
 <@petertodd> Yeah, but doable
 <@petertodd> So, there basically the already spend list becomes a consensus thing?
 <@amiller> yes
 <@petertodd> Do they just make the list so big you can pick a coin at random from it?
 <@petertodd> (I mean, the set of !in the list)
 <@amiller> no it's basically like
 <@amiller> uh well basically you can't see the list of things included in the accumulator
 <@amiller> i'm not sure how to answer your question
 <@petertodd> Ok, so there is a global accumulator though, and each transaction increments or decrements it?
 <@petertodd> (this is sounded just like fidelity-bonded ledgers...)
 <@amiller> so basically you deposit an ordinary coin into the accumulator
 <@amiller> a blinded token gets added to the accumulator
 <@petertodd> ok
 <@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
 <@petertodd> Ah, and there is some crypto magic that lets you prove that?
 <@amiller> yeah
 <@petertodd> (wizardry beyond my beginner wizard level)
 <@amiller> apparently they spent christmas break poring through the complete giant catalog of cryptographic accumulators looking for one
 <@petertodd> I assume then that accumulator can grow to be quite large?
 <@amiller> well the accumulator is just some wacky number field thing
 <@amiller> so basically i don't think it grows at all
 <@amiller> it's almost like folding hashes into hashes
 <@petertodd> Hmm... weird, dunno how that would work.
 <@petertodd> I mean, there is the clever trick of "what's the merkle hash of a 2^256 long string of zeros" but...
 <@amiller> http://www.cs.jhu.edu/~goodrich/cgc/pubs/accum.pdf
 <@amiller> this is one of the popular kinds of accumulators based on RSA numbers
 <@petertodd> Hmm... I'm gonna have to read that very carefully...
 <@BlueMatt> gmaxwell: ahh on the spv side, yes ok that is something Id like to do eventually
 <@petertodd> Now, I assume if you have n items in this accumulator, the size of the underlying data must scale by n somehow right?
 <@petertodd> Or do you accept some small possibility of collissions or something?
 <@BlueMatt> gmaxwell: hmm...actually maybe Ill do that as my next project
 <@petertodd> Oh wait, I found it, page 10: O(n) space
 <@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...
 <@amiller> there's gotta be better accumulators than that
 <@amiller> i don't see the point of an O(n) size one
 <@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)
 <@amiller> something like that
 <@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) 
 <@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)
 <@petertodd> You can't however take two such accumulators, and merge them in this example, without knowing all the bits involved.
 <@petertodd> (well, without knowing S1 and S2)
 <@petertodd> Equally, assign prime numbers in order, and just multiply your primes together, and then the resulting number is an accumulator.
 <@petertodd> That one you can get the union of S1 and S2 easily, but large n's are a problem.
 < HM> the computation under "a simple scheme" sounds expensive
 <@petertodd> HM: I'm sure people have done better than that :P
 < HM> for the dictionary
 < HM> updates and deletions sound cheap
  * HM continues reading
 <@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.
 < HM> I'm guessing the interval trick really doesn't work for transactions
 < HM> to find out if Tx is in S
 <@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
 <@BlueMatt> re: doublespend alerts...meh Im still not a big fan of putting those in the standard p2p protocol
 <@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.
 <@BlueMatt> gmaxwell: no, Ive always been against them (since like...years ago)
 <@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.
 <@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.
 <@amiller> there's lattice-based accumulators that are even fancier
 <@amiller> i really don't understand this stuff very well either
 <@petertodd> Oh yeah? Hmm... maybe more reading...
 <@petertodd> I didn't see anything about an "authenticated add", but maybe I'm missing something.
 <@petertodd> (specifically, a *signed* blinded token)
 <@petertodd> Ultimately the problem to solve is how to stop the ledger from faking withdrawals.
 <@amiller> i mean you're right that everything has to be witnessed
 <@amiller> like only a valid transaction can update the accumulator
 <@petertodd> Yeah, and you want token-to-token transactions.
 <@petertodd> Although I kinda punt there and assume Tor is available and logs will be made public and randomly audited...
 <@amiller> yeah no token to token transactions... well i mean i guess that wouldn't hurt anything
 <@petertodd> Well, it kills my dream of off-chain tx's. :P But it'd make for a great coin mixer.
 <@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. 
 <@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.
 <@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.
 <@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.
 <@petertodd> If no clients do that, the bank can create an unlimited number, on the other hand doing so does create information leak possibilities.
 <@petertodd> Exactly
 <@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.
 <@petertodd> *did
 <@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.
 <@petertodd> Yeah, if not for the chaum part it'd be simple.
 <@petertodd> You can have clients come back and do a unblinded register step for sure.
 <@petertodd> Just hard to get good parameters to maintain privacy.
 <@gmaxwell> at some point this should get built, even if its just a toy insecure form.
 <@gmaxwell> people were talking in #bitcoin-offtopic about building an IRC micropayment bot...
 <@petertodd> Did you read my bonded ledgers thing?
 <@gmaxwell> You send it 1btc.. then you can bot: pay petertodd 0.012345 btc    and eventually petertodd can checkout if he likes.
 <@petertodd> The idea of focusing on making a ledger who you are only holding to not allow double-spends to happen is nice.
 <@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"
 <@gmaxwell> the bonded ledgers was just the OP code for double spends?
 <@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.
 <@petertodd> Pretty much, and if the scripting system was just slightly more powerful, you probably wouldn't even need a dedicated opcode.
 <@gmaxwell> I wonder how you could construct its transactions to make the proof of doublespending maximally small?
 <@petertodd> Basically decompose CHECKSIG, allow for string manipulation, and provide a way to constraint was the txout set of a scriptPubKey spend is.
 <@gmaxwell> though I suppose ideally it would work on bitcointransactions so you could use it for both on and off chain doublespending prevention.
 <@gmaxwell> though that presupposes a public ledger which is lame. 
 <@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.
 <@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.
 <@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.
 <@petertodd> So you would challenge the ledger periodicly to prove they didn't double-spend your transactions.
 <@petertodd> hmm... actually, that could work very nicely...
 <@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.
 <@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"
 <@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)
 <@petertodd> And when you accept a transaction from the ledger, ask for *that* transctions history, back to where it came from in the blockchain.
 <@petertodd> I assume you've seen reddit's bitcointip right?
 <@gmaxwell> yes. pretty horrible in that it makes a bitcoin txn per tip or at least it did.
 <@gmaxwell> "worst of all worlds: insecure, slow, and non-scalable"
 <@petertodd> Pretty sure it still does; it's blockchain.info based.
 <@petertodd> Especially given the tiny size of tips.
 <@gmaxwell> Yea, b.i — unlike mtgox— doesn't even have a facility for internal transactions.
 <@petertodd> OK, so there's a goal: an library for auditable off-chain transactions.
 <@petertodd> Well, how could b.i and still meet it's security promises?
 <@gmaxwell> by allowing you to have some portion of your balance with b.i instead of in your wallet, of course.
 <@petertodd> Well, sure, but then they need my auditable off-chain tx library. :P
 <@gmaxwell> :)
 <@gmaxwell> mtgox seems to do fine without one.
 <@petertodd> mtgox is big enough to have credibility, of coruse, so is b.i
 <@gmaxwell> What would the audits prove?
 <@petertodd> The audits *could* prove fraud, if caught.
 <@gmaxwell> I mean what kind of fraud.
 <@petertodd> Well, lets say the ledger is internally doing a full blockchain basically, one tx per block.
 <@petertodd> Each block is signed by the ledger, and the blockchain is linked by a merkle mountain range hash system.
 <@petertodd> You also have a UTXO proof system basically.
 <@petertodd> So, one valid query would be to ask "Give me a full transaction history from my tx back to the on-chain tx"
 <@gmaxwell> Right, how do you avoid the proofs not becoming exponential as coins split and merge?
 <@petertodd> It's a good question, likely the ledger can only say "proofs will never be more than 1MiB" or something.
 <@gmaxwell> basically, I'm thinking this hidden blockchain model imposes some performance limits on the dumb-irc-bot-bank that would be unfortunate.
 <@petertodd> I mean, heck, just make the whole thing downloadable, and every year or so just throw it away and start fresh.
 <@petertodd> Yeah, it's a tough one.
 <@petertodd> Double-spend fraud in the ledger is detectable enough, with a spent-UTXO accumulator.
 <@gmaxwell> well what do we really need to prove: that the users balances sum to the deposits, right? What else for that application?
 <@petertodd> Yes, I think that's the biggest one.
 <@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.
 <@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, 
 <@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)
 <@petertodd> Do we need balances, or scriptPubKey txout hashes?
 <@petertodd> (with merkle summing)
 <@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.
 <@gmaxwell> and if the bot can't produce a transaction log that matches the balance sheet, we know it robbed that person.
 <@petertodd> That works easy enough.
 <@gmaxwell> initial deposits into the system could basically be handled by the payment protocol type non-repudation.
 <@petertodd> So basically, the bot can't inflate the balance, provided that every user checks that their balance is shown in the public ledger.
 <@petertodd> The ledger balance must match up to the on-chain balance.
 <@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.
 <@petertodd> Yes, my fidelity-bonded ledger thing even had a special UTXO out query opcode for that, to use internally with the ledger.
 <@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.
 <@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.
 <@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)
 <@gmaxwell> well whatever they want subject to how automated fraud handling should be. 
 <@petertodd> It's still very reliant on that public ledger of all balances, but seems doable.
 <@gmaxwell> the public leger would need to be delayed somewhat, I expect.
 <@petertodd> For privacy?
 <@petertodd> Delaying is fine provided it includes some type of hash linking back to your tx's.
 <@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.
 < ielo> hello helo
 < ielo> ielo helo
 <@amiller> i think this use of proving txs  is only useful if there's osmething automated that happens
 <@amiller> but this is a good reason to want the big bitcoin blockchain to be capable of metavalidation of other chains
 <@amiller> because something like a doublspend in a minor chain can trigger an insurance payout in a larger chain
 <@petertodd> amiller: This is the toy system - we'll implement automated proofs later.
 <@petertodd> amiller: Basically this is Mt. Gox redeem codes + some auditing.
 <@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.
 <@gmaxwell> if the whole balance sheet is public you can grok out whos transacting with who by observing matching changes in balance.
 <@gmaxwell> with a Merkle-sum-tree deanonymization requires the users to cooperate to deanonymize each other.
 <@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.
 <@petertodd> (though granted, movements would be harder)
 <@petertodd> It's funny too how balances that sit untouched, can be relatively safely taken by the ledger in fraud/balance expiry.
 <@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. 
 <@gmaxwell> well such a system would likely fund itself by periodic fees on inactive accounts, this also prunes the account database.
 <@gmaxwell> (it would make txn paying itself from users—)
 <@gmaxwell> and yea, it could rob inactive users and use that to pay other users... though they'd eventually be able to prove it.
 <@petertodd> I guess that's basically my complaint: it relies on users checking for fraud 100%, and each user has to play their part.
 <@gmaxwell> or rather, challenge it and the bank would be unable to prove it didn't.
 <@petertodd> See, I'd say don't worry about balances, just do a straight up unspent txout list as usual.
 <@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.
 <@petertodd> Merkle sum the txout of course, but leave it at that.
 <@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
 <@gmaxwell> Consider the bank like things that put people's money with pirate.
 <@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
 <@amiller> same as wanting to obtain the proofs so you can be sure your'e working on a valid block
 <@amiller> it's obvious how by encoding validation rules / proof of work puzzles you can incentivize both storage and computation
 <@amiller> it's less obvious but still seems plausible that you can incentivize communication this way
 <@petertodd> "Consider the bank like things that put people's money with pirate." <- ?
 <@petertodd> Oh, wait, you mean the funds that took peoples money, and forwarded it to pirate.
 <@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...
 <@gmaxwell> Yep. Even when they were saying that they hadn't done that.
 <@petertodd> Yeah, I see what you mean, you want to audit the backing funds first.
 < HM> i take it nobody got their money back?
 < HM> last i heard he was actually paying some back ?
 <@gmaxwell> people who were paid before the implosion got paid.
 <@petertodd> HM: he kept saying that to keep people hoping, and not suing him.
 <@gmaxwell> and yea ^ that.
 <@petertodd> (post implosion)
 <@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.
 <@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.
 <@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.
 <@gmaxwell> the system could public all the antifraud proofs, encrypted.. so that it can't tell whos paying attention.
 <@gmaxwell> Moreover, people could hand over copies of their anti-fraud decryption keys to friends that they don't mind losing some privacy to.
 <@gmaxwell> So the burden of checking could be shared.
 <@gmaxwell> ALTERNATIVELY. the system could pay users to check.
 <@petertodd> How so?
 <@gmaxwell> e.g. you get an inactivity fee if you're not checking.
 <@petertodd> Ah, so if the server doesn't get the occasional query?
 <@gmaxwell> right. if the server doesn't get queries from you it deducts your balance until your balance is gone.
 <@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.
 <@gmaxwell> If you're still querying though you keep a balance. Rather than prevent the theft we instutionalize it. :)
 <@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.
 <@petertodd> Ha, I like the institutionalizaiton... Standard expiry time thing.
 <@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. :)
 <@petertodd> For sure
 <@gmaxwell> but since everyone knows how it works, they can behave accordingly.
 <@gmaxwell> if the bank can rob you if you don't check— make it permitted to do so. (slowly)
 <@petertodd> Also, note how if the leger is purely balanced based, we actually can do chaum tokens still.
 <@petertodd> A chuam transaction just means an increment in the special outstanding token balance, followed by a decrement.
 <@gmaxwell> right, there could be special accounts for outstanding chaums of different sizes.
 <@petertodd> Yup, powers of two would be good.
 <@gmaxwell> and the chaum validation key could be public. Though you couldn't prove that they weren't overprinting chaums.
 <@gmaxwell> but only users with chaum in hand would have that risk.
 <@gmaxwell> well I suppose you could, but were back to the registering thing. :)
 <@petertodd> Yes, they'd be at risk the second every outstanding chaum token gets redeemed.
 <@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.
 <@petertodd> Probably true really.
 <@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. 
 <@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.
 <@petertodd> Yes, I think "release the code" is a very, very good model...
 <@gmaxwell> yes, thats a good goal and I'd realized that too.
 <@petertodd> Good.
 <@gmaxwell> it also, again allows for more efficient withdraws.. batched, mtgox code, chaum tokens with some other system.
 <@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.
 <@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.
 <@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.
 <@gmaxwell> Reoccuring payments?!@# no problem.
 <@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.
 <@petertodd> With part of that signature being over the master hash.
 <@gmaxwell> indeed, then it actually converges on a consensus system.
 <@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 Sun Mar 03 2013

 <@gmaxwell> It occured to me that for the sum-hash-tree stuff that we're not constrained to any particular binary tree geometry, so we should prefer ones that result in each split having half the coins on each side. This minimizes the amount of balance information leaked.
 <@gmaxwell> But we also don't want any branches becoming too long, since that would make the proofs fat. 
 <@gmaxwell> I think this can be used to build a sutiable tree: http://en.wikipedia.org/wiki/Package-merge_algorithm
 <@gmaxwell> The 'alphabet' is the accounts, the probablity of the 'symbols' is balance/total. The length limit would be set to some small multiple of log2(n). The resulting huffman codewords are just the branching decisions in the binary tree.
 <@gmaxwell> amusingly, I saw a nice package-merge implementation a few days ago and thought "what else could I use this for?"
 <@gmaxwell> Another fun thing is that the banks own balance can be split up any number of ways, since the bank doesn't have to worry about producing compact proofs for it... so it could be divided up to fill in any unmatched branches.
 < petertodd> Although by that point, you almost might as well say the banks balance is just whatever is in error in the sum tree.
 <@gmaxwell> ::nods:: sure, just trying to maximally conceal the balance distribution. So grafting on (parts of) the bank balance anywhere in the tree that helps is useful.
 < petertodd> One interesting model, would be if multiple entities held their own private keys, with the bank quickly querying them to do the actual signing, in which case the banks balance is just a set of accounts that happen to have keys associated with them, unlike normal accounts.
 < petertodd> Such entities would have to be on-line to do a trade, but they could provide liquidity basically.
 < petertodd> Might be too complex to explain, but it's interesting.
 <@gmaxwell> (likewise, large accounts— which already tend to have short proofs— could have their balances split in two, assuming the clients were setup to accept fragmented balance statements)
 <@gmaxwell> (at the limit, you divide every account down to the base units, ... but then the proofs are rather enormous, but you leak nothing under all conditions)
 < petertodd> Yeah, basically the accounts become chaum token amounts...
 < petertodd> Probably simple enough to just have client support for more than one account basically.
 < petertodd> The server doesn't need to know accounts are being split up.