--- Log opened Sat Jun 01 00:00:54 2013
11:51 < amiller> gmaxwell, here's the thing that's a little tricky about eli ben sasson's stuff
11:51 < amiller> there's a preprocessing phase that has to be as large as the time-bound on the number of steps of the computation
11:51 < amiller> so if there are 200,000 blocks
11:52 < amiller> then you have to do 200,000 steps of preprocessing to compile the verifier basically
11:52 < amiller> the one time cost of preprocessing the checker isn't any easier than a one-time step of preprocessing the whole blockchain
11:53 < gmaxwell> amiller: Eli's reponse to that was to suggest to break it and cascade it.
11:53 < amiller> there's like other possible tradeoffs like maybe you only use SCIP to do a smaller chunk
11:53 < amiller> yeah
11:53 < amiller> maybe we can have blockchain voting on what's the hash of a valid SCIP program?
11:54 < gmaxwell> (I talked to him specifically about that...)  Maybe, his thinking was like "well duh you'd just fix it into the system" ... kinda defeats the point though. :P
11:54 < amiller> awesome quote from his video "i don't know who the central authorities in bitcoin are, but they can do the preprocessing"
11:57 < gmaxwell> supposedly they know how to solve the poly in steps ACSP compile time part, and just have the engineering of building it to go.
11:57 < amiller> do you mean they can get *less* than linear compile time?
11:57 < amiller> someone else told me that too and i couldn't find the citation
11:59 < gmaxwell> amiller: yea, they say they can get to poly in just the length of the program for the compile on the verifier.. I believe this is the subject of their upcomming paper.
13:48 < petertodd> amiller: re: timestamping that's why the zookeyv key-value system I've been talking relies on you being able to determine if someone *could have* created a key-value associated timestamped earlier with a higher sacrifice than the one you just did
13:48 < amiller> sounds a bit like zookeeper :p
13:48 < amiller> which is also basically a distributed consensus kv store
13:48 < petertodd> Or zucchini
13:49 < petertodd> Oh, apache ZooKeeper? Interesting
13:49 < amiller> i don't think i follow the 'sacrifice' reasoning very well, or at least there's some reason it doesn't sit well with me
13:49 < petertodd> What part are you not following?
13:49 < petertodd> (I need a diagram really...)
13:49 < amiller> but as long as you have a *could have* determination then i'm basically ok with the protocol w.r.t. the timestamp thing
13:50 < amiller> well what's the simplest sacrifice protocol to discuss as an example
13:50 < amiller> like fidelity bonds?
13:50 < petertodd> Yeah, and because sacrifices build upon one other, the could have determination doesn't have to be too expensive.
13:50 < petertodd> fidelity bonds turned into a terrible bit of concept confusion... fidelity bonds are an abstract idea, the sacrifice methods are the important thing
13:50 < petertodd> Like announce-commit sacrifices, or anyone-can-spend coinbase txouts.
13:51 < petertodd> Or just sending coins to unspendable outputs...
13:51 < amiller> so what security property do you get from a sacrifice
13:52 < amiller> what kind of decision am i going to make based on the presence of a sacrifice where i won't make that decision if i don't see the sacrifice
13:52 < petertodd> Well, in a PoW blockchain the state of the blockchain is determined by total work right? So in a PoS blockchain the state of the blockchain is determined by total sacrifice.
13:53 < amiller> yeah and to the best i can intuit, the security of the blockchain has to do with an assumption that an attacker has a bounded budget
13:53 < petertodd> Yup, which is true for proof-of-work and proof-of-sacrifice fundementally. (the latter is just transferrable proof-of-work after all)
13:53 < amiller> and the (rational) miners receive as payment (the price of their rewards) an amount exactly equal to the computational costs of mining
13:54 < petertodd> Yup. Now a proof-of-sacrifice blockchain intended to work as a currency probably is infeasible, but as a namecoin replacement it makes sense.
13:55 < amiller> i don't see why it should be different if the security statement is the same... but anyway go on
13:55 < amiller> so if we assume bitcoin *is* the money and namecoin is the blockchain of discussion
13:56 < petertodd> Yeah, then the proof-of-bitcoin-sacrifice version of namecoin basically removes the "coin" part of namecoin.
13:57 < amiller> so the attacker is assumed to have a bounded budget *in bitcoins*
13:57 < petertodd> Exactly
13:57 < amiller> and namecoin transaction fees are paid in bitcoins?
13:58 < amiller> and they are paid to miners who sacrifice their own bitcoins in return for the transaction fees such that those balance out?
13:58 < petertodd> Well... there aren't really transaction fees in this model. Blocks are then just lists of keys and values, potentially with signatures if make a system where the initial key-value setting includes a pubkey for additional settings. (as namecoin does)
13:59 < petertodd> It also means the blockchain can be organized as a directed acyclic graph, with priority given to key-value entries in block with the highest total sacrifice.
13:59 < amiller> well what is the attackers budget related to/
14:00 < petertodd> Because each block is associated with a sacrifice, the attackers budget is to outspend all the sacrifices already made for the existing blockdag.
14:01 < amiller> what is the incentive for creating a sacrifice?
14:02 < petertodd> Doing so lets you make a block with key-value associations.
14:02 < petertodd> What's interesting, is the amount of sacrifice can be set low until an attacker comes along.
14:02 < amiller> is there no incentive for sacrifice?
14:03 < petertodd> Ha, yes, other than outspending an attacker!
14:03 < petertodd> *Socially* the system really needs ways for interested parties to easily get together and create a sacrifice.
14:03 < amiller> so it would be a bit like bitcoin without mining fees
14:03 < amiller> without blockreward
14:03 < amiller> just blocks and pow and no reward
14:03 < petertodd> Like an assurance contract, but that's tricky
14:03 < petertodd> Yup
14:04 < amiller> ok
14:04 < amiller> so the fundamental difference really isn't about substituting work for coin, but substituting incentives for no-incentives
14:05 < petertodd> For instance, if I were to register petertodd.zookv, I'd probably sacrifice 1BTC because, why not? Now in doing so, I'd make all prior blocks 1BTC more difficult to re-write.
14:06 < petertodd> See, namecoin is interesting here. Why would a miner mine namecoin? To get namecoins which will hopefully be valuable in the future because they can be used to register names.
14:06 < petertodd> There was a *lot* of speculation going on in the namecoin space...
14:06 < amiller> could i do something like
14:06 < amiller> sacrifice 0.00000001 btc for a ton of names
14:06 < amiller> and then one 10 btc block on top
14:06 < amiller> and then it would take 10btc to reverse any of the names
14:07 < petertodd> Exactly
14:07 < petertodd> See, you can also do key-value without a blockchain, where what is the canonical mapping is simply the highest sacrifice.
14:07 < petertodd> But I suspect that has bad social properties...
14:08 < amiller> so lets say i buy a name soc1024.com
14:08 < amiller> for a 0.1 or something
14:08 < amiller> if someone else buys it for 0.11
14:08 < amiller> i still lost my 0.1 right
14:08 < amiller> it was sacrificed in bitcoin and so gone forever
14:08 < petertodd> Yeah, in a non-blockchain version of k-v that's exactly what happens.
14:09 < amiller> what if auction sites worked that way
14:09 < amiller> like on ebay
14:09 < amiller> you can bid on an item
14:09 < amiller> and you lose that much money even if you get outbid
14:09 < petertodd> In a blockchain version, you'd have a rule where the first k-v created includes a pubkey, and subsequent modifications require a valid signature. (up to some expiration time or something)
14:09 < amiller> and every time you bid higher you lose the sum of all of your bids
14:09 < petertodd> There's gotta be a whole whack of economic analysis on that kind of auction...
14:09 < amiller> doesn't it seem like a horribly perverse auction
14:10 < amiller> i don't know how to say specifically what is wrong though
14:10 < petertodd> It does, which is why I think a blockchain/dag based system where you build on each others sacrifices is the only sane way to do it.
14:10 < amiller> ok let me try to understand how that would work
14:11 < amiller> (i'm trying to piece together the parts above where you mentioned it, but please start again on explaining the dag version?)
14:12 < petertodd> The dag version just has a rule where if two blocks have a set of k-v settings that don't conflict, they can be merged back together to form canonical history.
14:13 < petertodd> Because these are sacrifices, it's good to ensure that people won't lose their sacrifice just because someone else made one at the same time.
14:13 < amiller> i see
14:14 < petertodd> The other key detail, is that building on each other's sacrifices gives a strong incentive to broadcast them.
14:15 < amiller> if i pretend that there's no latency and nothing happens at *exactly* the same time then the dag isn't any different than the first way
14:15 < petertodd> Sure, the dag is just to get around the fact that there is latency involved. Potentially multiple blocks worth of latency in the case of announce-commit sacrifices.
14:16 < amiller> so if it has some undesirable economic property even with no latency it's still present even with the dag
14:16 < amiller> i'm trying to think of how to approach analyzing this economically...
14:16 < amiller> normally in auctions the design is to get the best price for the auctioneer
14:17 < amiller> and people participating in the auction usually make a decision like
14:17 < petertodd> Ok, so think of it this way: we want the system to provide the best rewrite security, especially over time, for the purchaser of the k-v map.
14:17 < amiller> basically they have to have a maximum amount of money they would pay to own the item
14:18 < amiller> and then the system lets them express that
14:18 < amiller> because if the price of the item is above what they'd pay then they don't get it and they don't lose money
14:18 < amiller> if it's below or equal what they pay then they might get it
14:19 < petertodd> Yes, excellent! So by including a rule where k-v maps only come into affect after n blocks, you just need to watch the blockchain, and if it looks like someone else is trying to rewrite history you can stop them with a further sacrifice.
14:20 < amiller> i wouldn't bother if i think it's probably someone else's problem and it's not wroth it to me, there's a public good contribution thing going on there
14:21 < petertodd> Yup, and it's easy to determine if it's someone elses problem too. Yet if that someone else further upps the sacrifice amount, they've helped you anyway.
14:21 < amiller> how might i decide how much it's worth it to me
14:21 < amiller> like
14:22 < amiller> maybe i get some kind of income for every day that the name points to me
14:22 < amiller> like if someone hacked my business url then i'd sue for lost business damages proportional to how many days it was broken or something like that
14:22 < petertodd> Well, if you're running silkroad.zkv...
14:25 < amiller> hm
14:25 < petertodd> What's really interesting, is if the dag structure ensures that only conflicting key's in conflicting blocks are ignored, but the rest of the mapping is left untouched, if, say, the system gets used and early on silkroad.zkv is registered, a later rewrite history attempt can replace it, but every other mapping will have been strengthened by the attack.
14:26 < amiller> oh so
14:26 < amiller> so i buy soc1024.com for 0.1
14:26 < amiller> a few days later 100btc in total have been sacrificed *on top* of that
14:26 < amiller> so now the cost to an attacker to rewrite me should be 100.1 and i'm pretty safe
14:26 < amiller> *but*
14:27 < amiller> the attacker could *just* rewrite mine for 0.11 and merge along with everything else
14:27 < amiller> so it would only cost him 0.11 to rewrite me? in that case i'm not very safe
14:28 < petertodd> Nope, the attacker would have to spend >100.1 BTC to rewrite yours, but if he does, any k-v setting that he didn't try to rewrite now takes >200.2 btc to rewrite.
14:28 < amiller> could i just register all the names all at once
14:29 < amiller> maybe it would be helpful to make a simulation or demo of this
14:29 < amiller> a board game
14:29 < petertodd> Of course you could. You probably want, at least initially, for the rules to include a namecoin-like minimum sacrifice amount.
14:29 < petertodd> Like 0.1BTC per k-v initial setting.
14:29 < amiller> my intuition is that this is an absolutely horrible idea but i'm trying to be methodical :p
14:30 < petertodd> Heh, my intuition is that this is an absolutely horrible idea, but the alternatives may be worse.
14:30 < amiller> that *there are worse alternatives* i'd agree with :)
14:30 < petertodd> lol
14:31 < amiller> i still have high hope though for something really good
14:31 < petertodd> I really don't like how namecoin became mainly a speculative thing, but such is life.
14:31 < amiller> yeah, same
14:31 < amiller> i think it's really important
14:31 < amiller> it's actually the best other-than-money application i can think of for public crowdsource networks like generalized bitcoin
14:31 < petertodd> For sure, and not just for DNS names.
14:32 < amiller> i guess it's not a good sign if i can't even think of a clear way to say that this scheme is deficient in some way
14:32 < amiller> this is really tricky to analyze
14:32 < petertodd> I think the thing is froma  *technical* point of view it obviously works. But does it work socially? Hard to say.
14:33 < petertodd> Speaking of, something I didn't say to you is blocksize - I think there needs to be a mechanism where blocks in the scheme are either directly limited in size, or for the data to get progressively less important as the size goes up somehow.
14:34 < petertodd> Also the sacrifice should be calculated per byte consumed.
23:05 < realazthat> gmaxwell: is it perhaps possible to send the verifier itself as the SCIP program
23:05 < realazthat> and instead of verifying the actual program,
23:06 < realazthat> you verify that the verifier ... verifies the hashes of the outputs of small sections of the program
23:06 < realazthat> like,
23:06 < realazthat> instead of running on the entire blockchain
23:07 < realazthat> P(B)
23:07 < realazthat> you chain P_i(B_i, S_i),
23:07 < realazthat> S_i being the state of P_(i-1) at completion
23:08 < realazthat> and the guy validates the signatures of this
23:08 < realazthat> and you verify that he verified each of them
23:08 < realazthat> then your T is T(verification)
23:08 < realazthat> mm
23:08 < realazthat> nvm that can still be a lot
23:09 < realazthat> I think you might be able to get sqrt(T) out of that
23:10 < realazthat> by spliting the blockchain into sqrt(|B|) for each B_i
23:15 < amiller> i think sqrt(T) is reasonable sure
23:15 < amiller> i'm trying to find papers that talk about lower preprocessing time
23:15 < amiller> i have two leads
23:16 < amiller> one is bootstrappable/recursive SNARKs
23:16 < amiller> http://eprint.iacr.org/2012/095.pdf
23:16 < realazthat> yeah I think this is one level of recursion
23:16 < realazthat> my idea
23:17 < realazthat> so, can a SNARK be reused?
23:18 < realazthat> or must each use of it have some sort of unique random challenge?
23:18 < amiller> and
23:18 < amiller> http://eprint.iacr.org/2013/229.pdf
23:18 < amiller> a snark can be reused yeah
23:18 < realazthat> ah ok cool
23:18 < amiller> basically think of it as compiling a circuit once
23:19 < amiller> and then you can choose different inputs to the circuit and then verify the whole thing in one step
23:19 < realazthat> mmm so why don't they build this recursion idea directly into it
23:19 < amiller> a circuit is like a C program except with all the loops unrolled, it's like definitely the *worst case* execution
23:19 < realazthat> so as to reduce the initial setup time
23:20 < amiller> maybe that's possible
23:21 < realazthat> it would slightly increase the poly's of the runtime I think
23:21 < amiller> i don't have a good intuition for how either of these two papers work
23:21 < realazthat> ah me neither, but I think I intuitively understand the recursion idea
23:22 < amiller> how is it not cheating though lol
23:22 < realazthat> what do you mean cheating?
23:22 < amiller> what is it you compile exactly in the first step
23:22 < amiller> how do you get larger computations out of it
23:22 < realazthat> oh I'll writ it up
23:22 < realazthat> I have it on scrap paper
23:26 < amiller> In attempting to construct the reduction we seek, we encounter the following problem: an arbitrary
23:26 < amiller> machine M running in time t (on some input x) may in general use a large amount of memory (possibly as
23:26 < amiller> large as t), hence na¨ıvely breaking its computation into smaller computations that go from one state to the
23:26 < amiller> next one, will not work — the resulting nodes may need to perform work as large as t (just to read the state).
23:26 < amiller> To deal with this obstacle, as a first step, we invoke a result of Ben-Sasson et al. [BSCGT12] showing
23:26 < amiller> how to use Merkle hashing to transform any M to a new “computationally equivalent” machine M0
23:26 < amiller> that
23:26 < amiller> “outsources” memory and dynamically verifies its consistency. (See Remark 7.4.) As a second step, we can
23:26 < amiller> then engineer a compliance predicate for ensuring correct computation of M0
23:26 < amiller> , one state transition at a time.
23:27 < realazthat> oh yeah I haven't considered memory
23:29 < amiller> well lets just assume we have merkle utxo implemented so that there's no memory needed
23:29 < amiller> so validating a single *update* takes only log M time or so where M is some bound on the number of outstanding utxos at any time
23:29 < amiller> and validating the blockchain really just consists of T of those
23:30 < amiller> really the merkle UTXO isn't much different of a solution than the merkleization result [BSCGT12] mentioned up there
23:30 < amiller> i still don't see how to do the recursive combination yet
23:30 < amiller> we could compile a circuit that does a single update but then we'd need T of those proofs
23:31 < amiller> or if we unroll the loop then we can compile a circuit that does all T blocks at once but then that's a pain to preprocess (even worse than *linear* to preprocess)
23:31 < amiller> so i can't figure out how to read this recursive composition step if it actually gets us better than linear
23:33 < realazthat> http://codepad.org/bBPyKcWw
23:33 < amiller> i should try to undersatnd this proof carrying data PCD and Ram Compliance Theorem which seem fundamental here
23:33 < amiller> obviously the goal is to write one tiny program that inserts/deletes one item into a utxo that has some maximum size like log(21e8) satoshis
23:34 < amiller> and then check a proof that any arbitrary number T of them are done correctly in sequence with only a single operation!
23:36 < amiller> ok no i don't follow this code
23:36 < realazthat> questions?
23:36 < realazthat> P' does the work
23:36 < realazthat> V' is what needs be verified
23:37 < realazthat> V' verifies that all the sigs that Pi produces are correct
23:37 < amiller> yes but it's not clear where the compilation occurs from this code
23:37 < amiller> the preprocessing step
23:37 < realazthat> you do preprocessing on V'
23:37 < amiller> SCIPVerify also requires compilation
23:37 < realazthat> yes
23:37 < amiller> if you give it different arguments
23:37 < realazthat> thats the recursive part
23:37 < amiller> so you SCIPVerify the SCIPVerify program
23:37 < realazthat> yes
23:38 < amiller> okay so that doesn't get you a cost savings
23:38 < Luke-Jr> wait, was there code for SCIP released? :o
23:38 < gmaxwell> 20:19 < amiller> a circuit is like a C program except with all the loops unrolled, it's like definitely the *worst case* execution
23:38 < gmaxwell> ^ no, that is _NOT_ how Eli's stuff works.
23:38 < amiller> yeah ram compliance theorem and whatnot
23:38 < gmaxwell> Yea.
23:39 < gmaxwell> Thats why its log() instead of quadratic (or exponential) in the program size on the prover.
23:41 < realazthat> amiller: why do you say it doesn't get a time savings?
23:41 < amiller> well if i think of this  SCPVerify as working just on circuits
23:41 < amiller> then the problem is that the SCPVerify function itself has to have a worst case running time
23:41 < realazthat> you break P into sqrt(|B|) peices
23:41 < realazthat> yes even so
23:42 < realazthat> mmm wait
23:42 < amiller> so if it is able to take itself as input
23:42 < realazthat> well SCIPVerify runs in O(|s|) time
23:42 < amiller> then it can't process itself using less gates than its own size
23:42 < realazthat> mmm
23:43 < realazthat> er
23:43 < realazthat> O(s)
23:43 < realazthat> yeah that would make it seem impossible
23:44 < realazthat> well wait
23:44 < realazthat> then there would slightly two different versions of SCIPVerify
23:44 < realazthat> SCIPVerify(Pi) << this would be hardcoded in the one used in V'
23:44 < realazthat> it runs in O(s) time
23:45 < realazthat> so V' runs in O(n*s) time, where s = |P|
23:46 < realazthat> if n = sqrt(|B|) and P runs on B (blockchain) T \in O(|B|), and Pi runs on a section sqrt(|B|), and Pi \in O(sqrt(T))
23:47 < realazthat> so V' should run in O(sqrt(|B|)*s)
23:47 < realazthat> am I making zero sense lol
23:48 < amiller> zero sense proof
23:48 < amiller> nah that might make sense
23:49 < amiller> so there's code about to be released by microsoft research for SNARKs
23:49 < realazthat> oh cool
23:49 < amiller> but like you have to feed it circuits and so it's kind of a ridiculous game of unrolling loops and proving to the compiler that you use bounded ram and bounded time and such
23:50 < amiller> so this proof carrying data concept is i think different
23:50 < amiller> but builds on it
23:50 < amiller> in which case maybe this is possible after all i guess
23:50 < realazthat> mmm
23:50  * realazthat wants codes to play with
23:52 < amiller> Coming... This Summer... The Fancy Crypto Drama you've been waiting for
23:52 < realazthat> lol
23:53 < amiller> Faster Verification! Shorter Proofs! Zero Interaction!! and *ZERO KNOWLEDge*
23:53 < gmaxwell> I hate the culture around movies we have— there is so much _super_ interesting stuff we can't make movies out of because we don't know how to show someone doing anything intellectual in a movie.
23:53 < realazthat> I've been thinking on ways to make a blockchain that does useful work, trades work jobs for coins, etc.
23:54 < realazthat> gmaxwell: mmm
23:54 < amiller> right on realazthat that's my favorite overall thought
23:54 < gmaxwell> "quick, cue the photomontage of sciency shit" "fuck, they're doing crapytography, there is nothing to show but paper!"
23:54 < realazthat> Traveling Salesman
23:54 < realazthat> haven't watched it though
23:54 < amiller> lol Traveling Salesman the Musical
23:54 < realazthat> http://en.wikipedia.org/wiki/Travelling_Salesman_(2012_film)
23:54 < realazthat> lol
23:54 < amiller> everyone's sad when he leaves because they know he wont ever be back again
23:54 < gmaxwell> yea, I'm aware of that movie, haven't found a way to see it.
23:55 < gmaxwell> hahah
23:55 < realazthat> gmaxwell: same haha
23:55 < gmaxwell> amiller: plot twist: the optimal path was also a hamiltonian!
23:57 < realazthat> mmm someone get eli into this channel :P
23:57 < realazthat> or #bitcoin-dev
23:58 < amiller> aahahahah that is a good plot twist
--- Log closed Sun Jun 02 00:00:57 2013