--- Log opened Tue Jun 04 00:00:04 2013
17:08 < petertodd> gmaxwell: At the conference you were talking about creating a SCIP proof of the UTXO set, and how it'd take a crazy amount of EC2.
17:08 < petertodd> gmaxwell: Was that because it would create the proof in one go?
17:09 < petertodd> gmaxwell: My understanding is that you can create a proof that a prooof evaluation program was run, which to me says you should be able to create these proofs on a per-block basis...
17:09 < petertodd> gmaxwell: ...leading to a UTXO set + total PoW proof that is self-checking - IE you don't need the blockchain history at all to trustit.
17:09 < petertodd> *trust it
17:11 < gmaxwell> petertodd: I think that even with the log2 decomposition what we want to do is at the upper edge of the scalablity of the software so far. But since the scaling problems there are mostly on the prover side I was throwing out 'big computation can be obtained'
17:12 < petertodd> gmaxwell: log2 decomposition?
17:13 < gmaxwell> petertodd: do stepwise proofs of every block. Then do pairs of validations of validations.
17:13 < petertodd> gmaxwell: Ah, as in what you were talking about previously was exactly what I'm proposing now.
17:13 < gmaxwell> Yes.
17:14 < petertodd> Ah, and hence the ideas for using the SCIP proofs themselves as your PoW function.
17:15 < petertodd> Speaking of, I was thinking SCIP proofs would be a way you could combine multiple proof-of-sacrifices together into one short proof.
17:17 < petertodd> Another idea I had was you could combine multiple proof-of-sacrifices together into a short proof with a probabalistic proof using a commitment.
17:19 < petertodd> So you have some set of PoX proofs, created successively. Each step you get to drop one of the proofs from the set, but for the proof to be valid the one you drop must match a random nonce in the future, such as the txid of whomever spends the anyone-can-spend txout in your coinbase tx.
17:20 < petertodd> Like how non-interactive zero-knowledge proofs use one-way functions and a pre-selected nonce.
17:49 < petertodd> Ok, so this works: Lets say I make fixed sacrifices of 1BTC. Each sacrifice encodes the txids of two prior 1BTC sacrifices. I want to be able to prove 3BTC in total have been sacrificed, but I don't want to provide three transactions.
17:50 < petertodd> So instead I call the two prior ones left and right, and the rule is if the last bit of the block hash subsequent to my transaction is a 1, I have to provide the left tx proof, if it's a zero, I provide the right one.
17:51 < realazthat> eli got back to me
17:51 < petertodd> I can of course make a fake sacrifice, but because I can't control the next block hash I have an equal probability that I'll waste my sacrifice.
17:51 < petertodd> Oh yeah?
17:52 < realazthat> I asked him very politely about Q&A and joining in irc
17:52 < realazthat> i made sure to say only if he had time
17:52 < realazthat> so his response was that they hitting a deadline this week
17:52 < realazthat> and I should contact him later next week
17:52 < petertodd> Promising!
17:53 < petertodd> Contact him in two weeks then.
17:53 < realazthat> and they working on website
17:53 < realazthat> so he wants it to coincide, perhaps
17:53 < realazthat> + he will release early specs of tinyram
17:53 < realazthat> so I can start working on LLVM backend
17:53 < petertodd> Oh, a website would be good. I was having a heck of a time trying to find info on SCIP earlier today.
17:53 < realazthat> Finally, if you're up to writing a LLVM (or any other compiler) for our TinyRAM spec (which is a very simple and nice virtual machine) we'll be happy to share the spec. It will also go online soon.
17:53 < realazthat> ^^
17:53 < petertodd> Nice!
17:57 < petertodd> Hmm... mind, the problem with my scheme is it's non-recursive; the wager has to be a large fraction of all previous sacrifices... hmm...
18:06 < petertodd> ACtually, no this works: so lets say my sacrifices form a linear list, with a total sacrificed sum at position i of S(i). The rules are now that with propability 1/S(i) I can "cut-the-chain" and do not need to provide the previous link in that list to consider my sacrifice valid.
18:07 < petertodd> The problem is my expected proof size is still long...
18:13 < petertodd> With a tree construction I can keep the proof size small though by picking between n previous sacrifices.
18:17 < petertodd> The other trick, for picking the random number based on the block hash, is you can do a weak proof of work to arbitrarily make it harder to pick the hash. IE run SHA256 n times to make an attacker spend n more resources (in terms of thrown away blocks) to pick the number.
18:20 < petertodd> re: tree, construct a merkle-sum-tree of the prior sacrifices, and randomly pick a single sacrifice out of that n for the one you are required to keep.
18:22 < petertodd> What's interesting, is that provided you have a means to do the commitment and a followup random nonce, you can use this same principle for any proof-of-work system.
18:23 < petertodd> Yet another example of how the very existance of Bitcoin makes Crypto-Magic possible...
--- Log closed Wed Jun 05 00:00:07 2013