| 00:04:19 | arbart: | petertodd: So the current alternative you mentioned many times :) is the trusted third-party. That is something like a (logical/trust) network of web wallets? |
| 00:06:26 | petertodd: | arbart: off-chain tx's? it's a third-party, although the nature of the trust involved depends on how you do it |
| 00:09:03 | arbart: | Actually, I just realized, the third parties wouldn't have to trust each other... just trust the math of the bitcoin-nanopayment? |
| 00:10:27 | petertodd: | Sure, but getting acceptance for that is a social problem. |
| 00:12:02 | arbart: | Heh, totally. My thought was the probailistic payments might not be accepted by the average joe, but perhaps it could work for bitcoin banks to settle with each other without needing to exchange records to settle balances (without them all being separate bitcoin txs), |
| 00:13:37 | gmaxwell: | micropayment channels are better for that. |
| 00:14:37 | arbart: | But what are the existing ideas? https://npmjs.org/package/bitcoin-nanopayment is now the closest one I know thanks to visiting here just now :) |
| 00:14:46 | petertodd: | arbart: ah, yeah if you're talking banks u-payments work well. Or ripple actually. |
| 00:15:18 | arbart: | I think it needs to work with bitcoin. Inflation proof. |
| 00:17:01 | arbart: | petertodd: I meant bank as a concept, even if it were a computer algorithm running somewhere. |
| 00:17:23 | petertodd: | arbart: inflation proofing third-party balances is pretty easy actually - you can always have the bank prove your balance is backed by real bitcoins |
| 00:22:50 | arbart: | So is there anyone you've heard developing an open bitcoin bank API / system, meant so anyone (the world) can run an off-chain tx thingies to enable micro-transactions, and enabling a distributed nature of such (to allow people in different countries to implement them however works there), thus using something like probabilistic payments or something to settle bitcoin transfers across the 'banks' in a trustless manner? :) all |
| 00:23:29 | petertodd: | arbart: None that I've heard of - doing all that is a tonne of work and tricky to monetize. |
| 00:23:59 | petertodd: | Small-value payments just aren't worth much... and improvements in blockchian tech, or just the community accepting less decentralization, could easily make all or effort in vain. |
| 00:25:29 | arbart: | Yes, well why i was wondering the state of the art, or I guess opinion on where it is at, in third party ideas, or native bitcoin protocol, or what :) |
| 00:25:55 | petertodd: | arbart: basically state of the art re: what we know can be done is way, way ahead of what people actually do |
| 00:25:57 | arbart: | oh, and they aren't worth much each, but together they are more useful/powerful |
| 00:26:33 | petertodd: | e.g. proving balances are backed by real bitcoins is pretty easy, yet no-one's bothered AFAIK even though there's all kinds of bitcoin funds popping up |
| 00:26:43 | arbart: | Well my mission is to discover all the boundries right now and then find which one I am best suited to help poke at :) |
| 00:27:01 | arbart: | oh interesting point |
| 00:27:37 | petertodd: | well, try writing one of these prove-a-balance schemes! it's reasonably easy, and would be a nice thing for us to be able to show as an example |
| 00:29:55 | arbart: | I can't argue any of that! That's an awesome idea then, thanks :) |
| 00:31:22 | petertodd: | np |
| 00:32:20 | arbart: | What were you thinking then, a whole system? As simple as an rpc call in bitcoind that is something like signs some proof message with the public key? (is that a good way to do it) Or what level of 'system' were you thinking? |
| 00:34:32 | arbart: | Oh, and thank you for the summary of the state of the art then :) Your tree-chain idea though is quite interesting and will plague my thoughts for some time to come I'm sure. |
| 00:35:46 | petertodd: | haha, mine too! |
| 00:36:30 | petertodd: | arbart: doesn't have to be fancy, just something that has some python or whatever functions that takes a list of balances, commits them to a txout, can spit out short proofs, and finally can verify those proofs is enough |
| 00:36:46 | petertodd: | that'd implement everything a cold-storage bitcoin investment fund would need |
| 00:41:31 | arbart: | I know C (enough ++ boost pain that I groked the original Satoshi client) and Java. |
| 00:41:48 | arbart: | Should I be learning python? |
| 00:42:36 | petertodd: | arbart: the python bitcoin libraries aren't great, python-bitcoinlib is one I've done some work on, a javascript implementation of this would probably be more useful to a wider audience |
| 00:44:14 | arbart: | In that case, scarily enough I might take a look at the javascript avenue then :) |
| 00:44:53 | petertodd: | arbart: heh! |
| 01:02:35 | arbart: | petertodd: In your list of requirements, I don't understand the 'commits them to a txout'. By that is it suggested the proof is a transaction that is output (just not published to network, but passed by hand / posted on /investors website)? |
| 01:03:52 | petertodd: | arbart: by "commit" I mean the txout is of some form that makes it impossible to make fraudulent proofs for a second merkle tree |
| 01:05:23 | arbart: | Oh I see, to actually transfer the bitcoins as part of the proof process? |
| 01:05:41 | petertodd: | exactly! otherwise it's just a merkle tree |
| 01:10:57 | arbart: | petertodd: Would you vomit, if I used supernode as a library to do this? |
| 01:11:19 | petertodd: | dunno what supernode is |
| 01:12:03 | arbart: | A BSD licensed java implementatation, not made by google. |
| 01:12:15 | petertodd: | ah, yeah, I dunno much about java anything |
| 01:12:19 | BlueMatt: | is anyone going to the financial crypto conf in march? |
| 01:12:21 | petertodd: | do what you want :) |
| 01:12:23 | petertodd: | BlueMatt: I am |
| 01:12:29 | BlueMatt: | * BlueMatt is pondering going... |
| 01:12:50 | petertodd: | BlueMatt: amiller is booked, and adam back said he was thinking of it |
| 01:12:58 | BlueMatt: | shit, now I have to go |
| 01:13:02 | petertodd: | BlueMatt: hehe |
| 01:13:03 | jtimon: | "commits them to a txout" sounds like "hash 'them' including a hashof a txout" I'm glad to hear I'm not the only one who gets confused when I hear that abstract data is "just simply" '"¿¡commited!?'" to other abstract data. I'm definitely not one of the math guys here, but I miss definitions quite often... |
| 01:13:04 | BlueMatt: | * BlueMatt ponders where to get funding from |
| 01:13:21 | petertodd: | BlueMatt: I'd offer to share a room except I already cheaped out on a single :P |
| 01:13:27 | BlueMatt: | damn |
| 01:13:32 | BlueMatt: | maybe adam3us would |
| 01:13:55 | arbart: | petertodd: Just wondering if that would limit the usefulness to the community much, not sure how people feel on that. I certainly don't like it due to oracle at least. |
| 01:14:04 | petertodd: | BlueMatt: what'd airfare be for you? you can get the student rates for the conf itself right? |
| 01:14:24 | BlueMatt: | yea, I could get student rates I'd think |
| 01:14:42 | petertodd: | arbart: like I said, a javacsript implementation is probably most useful because it can go on a website to show people |
| 01:15:08 | petertodd: | arbart: beyond that, python is probably best, although python btc libs suck |
| 01:15:49 | arbart: | what js lib would you recommend, when I searched it looked the only one wanted node. Are there any that will run in a browser and do what I need? |
| 01:16:12 | petertodd: | BlueMatt: well work out the total cost, decent chance someone could make it happen |
| 01:16:32 | arbart: | jtimon: thanks for that btw, helps me understand my lack of understanding :) |
| 01:16:38 | petertodd: | arbart: I assume whatever kyle drake is using for coinpunk would work? |
| 01:17:04 | petertodd: | jtimon: correct, we need a -wizards glossery |
| 01:17:57 | jtimon: | python libs https://github.com/monetizeio/python-bitcoin didn't got my hands into it yet, but it's maaku's forking from jgarzik, maybe too focused on commited utxo's |
| 01:18:29 | BlueMatt: | petertodd: now...where to get $2k |
| 01:18:31 | jtimon: | petertodd a glosary would be definitely a good thing |
| 01:18:32 | petertodd: | jtimon: I prefer my 'pythonize' branch at https://github.com/petertodd/python-bitcoinlib myself, but I am a little biased... |
| 01:18:44 | petertodd: | jtimon: yup, and spellcheck in my irc client... |
| 01:18:58 | petertodd: | BlueMatt: that's what it is for you? |
| 01:19:06 | arbart: | petertodd: Awesome, thanks for the pointer to coinpunk. |
| 01:19:18 | BlueMatt: | petertodd: well, incl the hotel +/- sharing a room...the flight is ~700 |
| 01:19:31 | petertodd: | arbart: kyle seems pretty competent, so whatever he uses is probably good :P |
| 01:19:33 | BlueMatt: | oh, sorry, +500 for the conf...dur |
| 01:19:59 | petertodd: | BlueMatt: I managed my hotel for like ~$200, but I really cheaped out |
| 01:20:10 | Luke-Jr: | I wish I could cheap out in miami :/ |
| 01:20:11 | jtimon: | well, when I don't understand you is more often because you use foreign terms like I live in your head than because you misspell |
| 01:20:11 | petertodd: | BlueMatt: of course, if you get desperate, ask, and we can swap bookings :) |
| 01:20:27 | Luke-Jr: | I'll be lucky to get hotel alone for under $1000 |
| 01:20:28 | BlueMatt: | petertodd: heh, well I suppose I could look harder at finding a real hotel instead of the conf one..... |
| 01:20:42 | petertodd: | BlueMatt: oh, the conf one is insane, IIRC mine was $40 a night |
| 01:20:50 | BlueMatt: | yea, thought so |
| 01:21:01 | petertodd: | single room, shared kitchen/bath - kinda a hostel |
| 01:21:12 | petertodd: | problem is they seem to be booking out :( |
| 01:21:29 | BlueMatt: | petertodd: yea, I had it on my calendar to figure it out by I forgot until today |
| 01:21:34 | jgarzik: | BlueMatt, RE fin crypto, trying to get core devs there |
| 01:21:44 | jgarzik: | Barbados, March 3-7, IIRC |
| 01:21:48 | BlueMatt: | yep |
| 01:21:56 | arbart: | While I'm a math guy, so I really should learn python, however, one idea I have I have would actually need javascript in browser able to generate transactions, so I guess coinpunk it is :) |
| 01:22:19 | petertodd: | jgarzik: you're gonna make this conf go from academia to bitcoin-central :P |
| 01:22:40 | jgarzik: | hey, I didn't start it |
| 01:22:43 | petertodd: | arbart: python is the one true language :) but yeah, in-browser is great for demos for people |
| 01:23:11 | petertodd: | jgarzik: of course, the actual bitcoin part is like one day out of seven |
| 01:23:24 | BlueMatt: | the foundation is a big sponsor... |
| 01:23:26 | jgarzik: | indeed |
| 01:23:45 | jgarzik: | * jgarzik would probably only come in for the bitcoin part |
| 01:23:57 | jgarzik: | too many confs. if you go to them all, there's no time for real work. |
| 01:24:14 | petertodd: | BlueMatt: dunno I'd say "big" - they're sponsoring a one-day workshop, dunno what that means in terms of the whole thing |
| 01:24:37 | Luke-Jr: | jgarzik: no kidding, it's getting to the point where it's almost once every week it seems |
| 01:24:40 | BlueMatt: | petertodd: well...they have the largest logo, so that means they have no sponsors, really |
| 01:25:04 | petertodd: | BlueMatt: oh yeah? lol, the location is a bit suspect |
| 01:25:11 | jtimon: | another foundation, small sponsor, but funds free software more than PR, get listed can't lose anything http://foundation.freicoin.org/#/donations, sorry for the spam... |
| 01:25:45 | Luke-Jr: | jtimon: huh? |
| 01:27:51 | jtimon: | Luke-Jr was continuing this "the foundation is a big sponsor..." but yeah, sorry for the offtopic (if you're developing complementary currency-related free software [I think you are] then you should definitely get listed there to get 10% matched donations) |
| 01:29:07 | petertodd: | BlueMatt: you should prove your worthyness by writing up a quick app to do a SIGHASH_ANYONECANPAY fund for you to go :) |
| 01:30:10 | Luke-Jr: | petertodd: that also requires the donors to be "worthy" :P |
| 01:33:04 | shesek: | arbart, look into bitcoinjs-lib, vbuterin's fork is the most maintained one |
| 01:33:05 | petertodd: | Luke-Jr: the better the app is, the less worthy the donors need to be! |
| 01:33:05 | shesek: | and it works well in the browser with browserify |
| 01:33:05 | Luke-Jr: | petertodd: oh app :D |
| 01:33:05 | shesek: | (browserify compiles code with nodejs module system to a single js file with all the dependencies) |
| 01:34:22 | arbart: | shesek: thank you very much! |
| 01:34:49 | shesek: | arbart, you welcome |
| 01:35:05 | shesek: | I've been using it quite heavily myself for bitrated, so feel free to ping me if you need any help |
| 01:48:11 | arbart: | shesek: thanks, its not unlikely I'll have to take you up on that offer :) |
| 01:48:47 | shesek: | cool, I'll be glad to help if I can :) |
| 01:52:12 | shesek: | you can also check the code at https://github.com/shesek/bitrated/ to see some examples of using it (its written in coffeescript, though) and how the browserify compilation step works (bin/build-static.sh, or server/assets.coffee for a nodejs server that compiles on-the-fly) |
| 01:53:22 | jgarzik: | shesek, RE bitcoinjs-lib, BitPay's fork of bitcoinjs-server (the node.js fork) is the most maintained |
| 01:53:33 | jgarzik: | in case you are on server, rather than client/browser |
| 01:53:49 | jgarzik: | https://github.com/bitpay/bitcore |
| 01:54:06 | shesek: | oh really? that's great to know, last time I looked at bitcoinjs-server it seemed completely unusable :\ |
| 01:54:26 | shesek: | I ended up using bitcoind with a thin nodejs layer to serve the public api |
| 01:54:42 | jgarzik: | shesek, creaky and old. both bitcoinjs-lib and bitcoinjs-server were 2 years old. no p2sh, no multisig, ... |
| 01:55:05 | jgarzik: | shesek, we need all that, so we picked up maint on the node.js stuff |
| 01:55:21 | jgarzik: | shesek, _most_ is compatible with the browser, but there are a few replacements still needed |
| 01:56:34 | shesek: | have you looked into vbutertin work on bitcoinjs-lib? he got it to a pretty stable state, added new features, and made it compatible as a nodejs modules |
| 01:57:11 | jgarzik: | yes |
| 01:57:21 | jgarzik: | it wasn't complete enough when we looked at it |
| 01:57:50 | jgarzik: | at the time, coinpunk was in bitpay's office, hacking out code to run in browser |
| 01:59:04 | shesek: | oh, cool, I didn't know coinpunk was related to you |
| 01:59:20 | shesek: | you just gave them some work space, or is coinpunk a bitpay project? |
| 01:59:58 | jgarzik: | he worked for us briefly |
| 02:00:33 | arbart: | What's the node.js stuff for? accessing the blockchain? |
| 02:01:55 | shesek: | that, and for handling keys/addresses/transactions/signatures server-side |
| 02:02:44 | arbart: | No current alternative if I want browswer js to parse the blockchain for what I'm doing? |
| 02:04:28 | shesek: | how would that work? you would load the entire blockchain client side? |
| 02:04:29 | shesek: | the client-side libraries allows you to create keys/addresses, construct/sign transactions and all that |
| 02:04:29 | shesek: | communicating with the Bitcoin network/blockchain requires running something on the server that's capable of doing that |
| 02:04:32 | shesek: | I ended up writing https://github.com/shesek/bitcoin-webapi that exposes some minimal APIs that I needed (loading unspent inputs and broadcasting transactions) on top of bitcoind with sipa's #2802 |
| 02:04:49 | shesek: | (address index with searchrawtransaction, https://github.com/bitcoin/bitcoin/pull/2802) |
| 02:10:10 | arbart: | Ok, I understand then. Your coffee script stuff looks pretty cool actually. |
| 02:11:20 | shesek: | its a nifty little language that can give some people a serious productivity boost, but its not for everyone :) |
| 02:12:27 | shesek: | bitrated's source is still a bit messy, but its somewhat organized and commented, so it should give you a good start |
| 04:52:13 | justanotheruser1: | justanotheruser1 is now known as justanotheruser |
| 06:32:41 | justanotheruser2: | justanotheruser2 is now known as justanotheruser |
| 10:54:07 | HobGoblin: | HobGoblin is now known as Guest53151 |
| 10:59:24 | Guest53151: | Guest53151 is now known as UukGoblin |
| 11:53:39 | Muis_: | Muis_ is now known as Muis |
| 13:45:53 | ielo: | ielo is now known as lumos |
| 13:46:01 | gmaxwell: | gmaxwell is now known as Guest31376 |
| 14:00:23 | Guest31376: | Guest31376 is now known as gmaxwell |
| 15:41:22 | wallet421: | wallet421 is now known as wallet42 |
| 17:22:08 | justanotheruser1: | justanotheruser1 is now known as justanotheruser |
| 17:30:32 | jgarzik: | jgarzik is now known as home_jg |
| 17:58:54 | imsaguy: | All you people don't get bitcoin. |
| 17:58:56 | imsaguy: | imsaguy has left #bitcoin-wizards |
| 17:59:18 | gmaxwell: | 0_o |
| 17:59:26 | _ingsoc: | xD |
| 17:59:33 | _ingsoc: | Okay then. |
| 17:59:41 | amiller: | thanks |
| 18:15:05 | midnightmagic: | He's mocking me because I told him most people in #bitcoin* probably don't understand bitcoin. |
| 18:16:39 | gmaxwell: | ah |
| 18:17:58 | tacotime_: | we're way more knowledgeable over here in wizards |
| 18:18:03 | tacotime_: | what's a blockchain? |
| 18:18:05 | amiller: | i just met yet a few more unexpected people who are pursuing bitcoin research |
| 18:18:51 | amiller: | especially a pretty famous programming-languages person who apparently is about to publish a type-theory altcoin proposal |
| 18:19:14 | nsh: | yay |
| 18:19:33 | nsh: | * nsh premines some functorcoins |
| 18:19:44 | amiller: | LOL |
| 18:20:11 | amiller: | it was weird, he was explaining the linear type system that it will use |
| 18:20:22 | amiller: | i said, cool, do you have any particular motivating example in mind |
| 18:20:25 | amiller: | he was like no not at all. |
| 18:20:29 | gmaxwell: | hahaha |
| 18:20:52 | gmaxwell: | but in a cryptocurrency. |
| 18:21:14 | amiller: | "welcome. you'll fit right in here." |
| 18:21:25 | tacotime_: | the screaming robot of cryptocurrencies. |
| 18:21:27 | tacotime_: | hahaha |
| 18:22:22 | nsh: | Linear type systems are the internal language of closed symmetric monoidal categories, much in the same way that simply typed lambda calculus is the language of Cartesian closed categories. More precisely, one may construct functors between the category of linear type systems and the category of closed symmetric monoidal categories.[7] |
| 18:22:27 | nsh: | -- http://en.wikipedia.org/wiki/Substructural_type_system#Linear_type_systems |
| 18:22:44 | nsh: | should be fun... |
| 18:23:50 | amiller: | linear logic is good for modeling resources |
| 18:24:01 | amiller: | for example from one quarter, you can derive two dimes and a nickel |
| 18:24:07 | amiller: | also from one quarter, you can derive five nickels |
| 18:24:22 | amiller: | but that doesn't mean you can take a quarter and derive six nickels and two dimes |
| 18:24:44 | nsh: | kinda like typing with accountancy baked in |
| 18:24:50 | tacotime_: | Hmm. |
| 18:24:56 | amiller: | you could probably express all the conservation rules about no inflation etc using linear logic (though i think it would be overkill) |
| 18:25:01 | tacotime_: | What's the real world application? |
| 18:25:12 | amiller: | well take ethereum scripts for example |
| 18:25:23 | amiller: | maybe you'd like to be able to typecheck them and prove they don't leak value somehow |
| 18:25:31 | tacotime_: | Ah |
| 18:28:08 | tacotime_: | So like proof-carrying code? |
| 18:29:23 | amiller: | i think so (but i'm really not sure) |
| 18:29:43 | gmaxwell: | amiller: I don't know why that really matters inside a cryptocurrency. We shouldn't have code in a cryptocurrency, we should have wittnesses for code other people ran. |
| 18:30:10 | amiller: | i told him about snarks and pinocchiocoin, he knew about pcp proofs |
| 18:31:08 | gmaxwell: | You can think of that stuff just as a performance optimization. |
| 18:31:22 | amiller: | then sure |
| 18:32:14 | amiller: | so when the witnesses about code that other people ran, are about values that are of global importance, like a monetary supply, then applying this sort of conservation logic would be relevant |
| 18:32:50 | gmaxwell: | Well, sure I think it's good to create things using tools for soundness, but there isn't any reason to leave them in inside the witness. |
| 18:33:25 | tacotime_: | You can provide withness for executed code without executing the code yourself to verify it? |
| 18:33:31 | gmaxwell: | type data is precisely the sort of thing you can omit in a witness when extracting it from an execution trace, even before you go the route of converting the execution trace into a snark. |
| 18:34:12 | tacotime_: | I'm unfamiliar with a lot of this "proofs" stuff used for ZRC etc |
| 18:34:21 | gmaxwell: | tacotime_: Yes, thats what a snark is, a proof that code was fairthfully executed which is logarithmic in the length of the exeuction (or smaller, with cryptographic assumptions they can be constant size in the security parameter) |
| 18:34:31 | tacotime_: | Ah, I see. |
| 18:35:45 | andytoshi: | tacotime_: thank you for acting incredulous about that. i wish more people here would explicitly mention how mind-boggling this is :P |
| 18:36:25 | nsh: | once you accept the existence of voodoo magic, it's a relatively trivial corollary |
| 18:36:38 | gmaxwell: | PCP theorem proves that any execution in NP is provable with arbitrary soundness compactly, though PCP doesn't directly give a pratical way to go about doing it. |
| 18:37:07 | tacotime_: | Hahaha. Well, I never used to hang out here so a lot of this stuff is novel to me. I only sat around bitcointalk and the issues over there regarding what they want in altchains is apparently very different. |
| 18:38:12 | tacotime_: | *are |
| 18:38:23 | andytoshi: | gmaxwell: is there a nice paper summarizing the pcp theorem's history and proof? wiki sorta says "it's smeared over 30 years of history, good luck friend" |
| 18:38:23 | amiller: | this stuff is at the front of theoretical cryptography, it should be novel to pretty everyone, it's pretty exciting we have a reason to discuss it at all (which is why even the cryptographers working on it are like, oh this is practical, it's even relevant for bitcoin) |
| 18:38:41 | amiller: | andytoshi, hah. |
| 18:38:55 | amiller: | http://courses.cs.washington.edu/courses/cse533/05au/pcp-history.pdf |
| 18:38:59 | tacotime_: | Thanks |
| 18:39:05 | gmaxwell: | Well I don't think proving in zero knoweldge is _that_ remarkable, that the proofs can be sublinear in size is somewhat remarkable. |
| 18:40:03 | andytoshi: | amiller: thanks! gmaxwell: the sublinearity is weird, it feels like skirting P=NP in the same way as quantum entanglement skirts "can't send signals faster than time" |
| 18:40:19 | nsh: | hehmm |
| 18:40:33 | andytoshi: | that is, there is no actual violation, but it seems like -something- in the platonic realm must be violating it |
| 18:40:50 | amiller: | https://eprint.iacr.org/2012/215.pdf this is the big theoretical result that made SNARKs a hot topic |
| 18:41:00 | amiller: | it's underlying TinyRAM and Pinocchio etc |
| 18:41:24 | amiller: | some of its paragraphs are possible to read... |
| 18:41:39 | nsh: | andytoshi, i had similar intuitive feelings, but hadn't made that analogy. thanks |
| 18:41:44 | gmaxwell: | Thats the GGPR'12 paper. Meh. well, it's not the only thing that made it a hot topic. |
| 18:42:17 | amiller: | hrm, what's the best thing preceding it? |
| 18:42:23 | gmaxwell: | andytoshi: well it can be useful to think about what you give up in both cases. SNARKS in sublinear size 'only' have computational soundness. |
| 18:42:35 | amiller: | proofs for muggles maybe |
| 18:43:05 | amiller: | no proofs for muggles is interactive |
| 18:43:17 | gmaxwell: | Really the major breakthrough that allows sublinear is bootstrapping, which I think was mostly really inspired by the FHE work. |
| 18:43:32 | tacotime_: | I can tell already that I will never understand that paper. But that's what proves the sublinear size and makes 288 byte SNARKs possible? |
| 18:43:55 | gmaxwell: | You can make it non-interative with fiat shamir IIRC, most interactive things can be. |
| 18:44:46 | gmaxwell: | tacotime_: the GGPR'12 technique is constant size proofs. There are a couple of high level ideas that can help you intutively understand why sublinear proofs are possible. |
| 18:45:28 | andytoshi: | fiat-shamir is also really cool philosophically. it's like you summon a random oracle to do the interactive proof with you and publish the transcript |
| 18:47:58 | gmaxwell: | tacotime_: imagine you have a system which can prove the validity of two operations: executing a single instruction AND verifying a proof that the prior state for that instruction. If the proof verficiation is randomized/probablistic, then its not surprising that the proof size can be proportional to security rather than execution size... and then you nest these operations and get a constant size proof. (bootstrapping approach). ... |
| 18:48:04 | gmaxwell: | ... Efficient systems don't work directly in this way, but its an intutive way to see the possiblity. |
| 18:48:13 | andytoshi: | as for SNARKs being "'only' computationally sound", that seems to be strongly analogous to the quantum-entanglement scenario wherein your "faster than light correlation" can only be verified by communicating slower than light |
| 18:48:29 | gmaxwell: | andytoshi: thats why I pointed it out. |
| 18:48:41 | andytoshi: | gmaxwell: yeah, i realize that. but i'm that slow :) |
| 18:49:05 | nsh: | (slow is pretty damn relative here) |
| 18:49:12 | andytoshi: | realize that now* |
| 18:49:57 | gmaxwell: | amiller: yea, fiat shamir is insanely useful. I'm not sure why its not more widely known. It doesn't help that the original papers on it are a bit opaque. |
| 18:50:47 | andytoshi: | the original paper pretends to be about the smart-card scheme, it's really not obvious that there is anything generally useful in there at all until you read it :( |
| 18:51:40 | nsh: | "The heuristic was originally presented without a proof of security; later, Pointcheval and Stern [2] proved its security against chosen message attacks in the random oracle model, that is, under the assumption that random oracles exist. In the case that random oracles don't exist, the FiatShamir heuristic has been proven insecure by Goldwasser and Kalai.[3] The FiatShamir heuristic thus demonstrates a major application of random oracles." - http:/ |
| 18:51:40 | nsh: | /en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic |
| 18:51:50 | gmaxwell: | yea, that article is useless. |
| 18:51:52 | nsh: | * nsh frowns at irc client |
| 18:53:01 | nsh: | kinda provocative that you could have some empirical security difference that implies the existence or not of random oracles |
| 18:53:47 | tacotime_: | Is there a text book somewhere for this sort of stuff? |
| 18:54:32 | jtimon: | gmaxwell, if you were to design a concatenative merklized scripting language (joyscript), what would be important to take into account so that in the future it is "good for snark" |
| 18:54:48 | jtimon: | ? |
| 18:54:50 | gmaxwell: | Basically it says you can take an interactive protocol and make it non-interactive by commiting to your state with a random oracle, then using the random oracle to play the counterparty in the interactive protcol. If the interactive protocol has the right properties then you can instantiate the system with a hash function in the place of the random oracle and make a secure conversion. |
| 18:55:07 | andytoshi: | jtimon: you want to be able to easily bound the time-to-execute for scripts |
| 18:55:32 | andytoshi: | for a concatenative language maybe that is as easy as computing a tree height |
| 18:56:19 | gmaxwell: | andytoshi: only if you can describe an efficient arithemetic circuit for evaluating the concatenative language such that execution = tree height. This seems unlikely to me. |
| 18:59:42 | jtimon: | wouldn't those problems be solved with the instruction counter? |
| 19:00:36 | tacotime_: | Okay, I think it's starting to make sense. We have algorithm A, with non-arbitrary input I and output O. The proof takes input I_ro from a random oracle (hash function) and produces output O_ro using A(I_ro). We can then prove the execution of A(I) for some non-arbitrary input I. |
| 19:00:57 | jtimon: | btw, maaku, I don't think your message got to the concatenative group maybe you had to enter the tahoo group after all |
| 19:01:00 | jtimon: | http://groups.yahoo.com/neo/groups/concatenative/conversations/messages |
| 19:01:29 | tacotime_: | With some small amount of bytes using SNARK, because the proof is logarithmic in size? |
| 19:01:43 | gmaxwell: | jtimon: current constructions for snarks require costly preprocessing which is program generic but specific to the machine beging evaluated and specific to the length of execution. |
| 19:03:06 | tacotime_: | Is that the overall gist of what's going on? |
| 19:03:24 | tacotime_: | My background is in biochem, so sometimes I'm a little slow for CS stuff, forgive me. |
| 19:04:12 | jtimon: | gmaxwell I don't think I understood that, but I'm asking with the hope that those costly executions become cheaper in the future somehow |
| 19:04:51 | gmaxwell: | tacotime_: I'm not sure I followed what you were saying clearly enough there to agree or disagree. Another way to look at it is that program validation and program execution are not the same problem. Imagine making a transcript of a program execution— you write down every instruction that gets run and then the state (memory, registers, etc) along the way. |
| 19:05:09 | gmaxwell: | The result is a transcript— or sometimes called a witness— of the execution. |
| 19:05:43 | andytoshi: | jtimon: the other problem is that the preprocessing step has a security parameter which can be used for forging. this is a serious problem when there is one guy (the coin creator say) who is doing the preproccessing step, but it'd kill the scheme if everybody was doing their own preprocessing |
| 19:05:47 | gmaxwell: | If I give you such a transcript I can ask you if its valid, to tell if its valid you walk through the instructions and then check that the instructions match the rules e.g. that an ADD instruction updates the state in the right way. |
| 19:06:01 | tacotime_: | Right. |
| 19:06:19 | jtimon: | for those who are interested in this joyscript thing, this is the message that maaku (tried to?) send to the concatenative mailing list http://pastebin.com/5ScNX7vy |
| 19:06:29 | gmaxwell: | tacotime_: what all of this stuff is based on is that there exist ways of encoding the transcript so that if you only check a tiny portion of it, that you can become very confident that the whole transcript was faithful. |
| 19:06:48 | jtimon: | andytoshi, I see, like zerocoin's trapdoor |
| 19:06:56 | andytoshi: | yeah exactly |
| 19:07:01 | tacotime_: | Given some non-arbitary input? |
| 19:07:10 | andytoshi: | i had some vague ideas about using a variant of FHE to obtain the security parameter from a random oracle in a zk way (so provable nobody knows it) but i ran into serious conceptual problems when i tried to make these ideas concrete |
| 19:07:59 | gmaxwell: | for any input. well technically what you do is provide the inputs and 'outputs' as inputs and then the whole program just decides to accept (inputs agreed with the program) or not... e.g. convert it into a decision problem. |
| 19:09:02 | tacotime_: | Okay. |
| 19:09:04 | jtimon: | and if anyone is more interested, I can forward what maaku has been discussing with an strong typed concatenative language expert (the guy who wrote that "why concatenative matters" article) [unless you maaku haave some objection to sharing it, which I doubt] |
| 19:09:07 | andytoshi: | basically, you want it to be verifiable that you actually got the security parameter from the oracle -and- you only used it for a specific circuit (zk-snark preprocessing) and couldn't have used it in a circuit which reveals the parameter |
| 19:09:31 | andytoshi: | but these two requirements conflict when you try to implement them in the 'obvious' ways it seems |
| 19:11:40 | andytoshi: | that is, if you tie the parameter to a specific circuit it's hard to make it random (it's hard to make it at all actually). and conversely if you want to make it random it's hard to tie it to a circuit, but if you don't then it's trivial to replace the circuit with one that reveals it, defeating the whole exercise |
| 19:14:53 | gmaxwell: | andytoshi: why can't you just pick a ciphertext input to the circuit at random (e.g. because you don't know the decryption key)? |
| 19:17:39 | andytoshi: | gmaxwell: to implement this "tie the input to the circuit" scheme, my thought was to make the key derivation depend on the circuit |
| 19:18:11 | andytoshi: | but when you do this, it becomes hard (or rather outside the things i'm aware of being possible) to create a decryption key without an encryption key |
| 19:19:06 | andytoshi: | the hope was, i could make the output-decryption key be "111111" or something which clearly has no input-encryption key. then i can put whatever i want as input and what the circuit sees will be random and unknown |
| 19:20:18 | andytoshi: | but it seems implausible that just using 111111 will get me a valid decryption key, since my key derivation is so complicated |
| 19:21:41 | gmaxwell: | I still don't understand how the reencryption used in bootstrapping FHE can even work at all, so that sort of leaves me powerless to speculate about how you can get unknown encrypted with known decryption key FHE. I think it would be very powerful and not just for this if its possible. |
| 19:22:55 | andytoshi: | ditto. i have been trying to meet with brent waters, who has published several papers with craig gentry about FHE, because i'm trying to seduce him into supervising me. but he's been out of the country a lot this semester. whenever i get ahold of him i'll bring this up and maybe he can speculate more intelligently |
| 19:24:38 | gmaxwell: | one of the limitations in all this verifyable computing stuff compared to MPC is that you can't keep secrets from yourself. ... but MPC doesn't really get you security in an anonymous model. if you had what you want you could have a publically verifyable version of everything MPC can do. |
| 19:25:02 | gmaxwell: | For example, you could have a captcha POW coin. |
| 19:27:15 | andytoshi: | yeah, and the mere fact that we could get so much magic out of this suggests its implausibility. but idk, maybe we can get all or partway there. i'd like to spend some time researching this. |
| 19:30:48 | andytoshi: | probably 100% of what we've discussed in the last hour, if you asked me 18 months ago if any of it were possible, i'd have said not a chance. so i'm optimistic. |
| 19:31:43 | gmaxwell: | well, perhaps the existance of one way functions sort of suggests the possiblity of it. |
| 19:32:59 | andytoshi: | my money is on their existence being ZFC-undecidable :P |
| 19:33:53 | andytoshi: | halting-complete rather |
| 19:45:06 | andytoshi: | another problem i thought of is that the key-derivation scheme could be malleable. that is, you can tweak the circuit and this changes the key in some predictable way, so you can still steal information about the input this way. so i thought, the KDF should basically evaluate the circuit but attach to each gate a one-way function which is somehow specific to that gate. and then i started to think |
| 19:45:07 | andytoshi: | it'd be very hard to preserve enough information through all this that i could decrypt the information in the end. |
| 19:45:15 | andytoshi: | decrypt the actual output* |
| 19:46:36 | andytoshi: | maybe you take the encryption key, run it though some shadow version of the circuit made of OWFs, then the output of that could be the trapdoor information needed to decrypt the output |
| 20:47:39 | nsh: | hmm |
| 20:49:45 | nsh: | occurs to me that the dynamics of difficulty adjustment are much more complex now you have pools supporting multiple-coins leading to positive feedback from hopping driving instability |
| 20:51:10 | nsh: | there was a significant first-mover advantage with bitcoin in that slushy liquid hashpower was not even a thing until it was relatively mature |
| 20:51:27 | nsh: | to what extent that is balanced by lessons (theoretically) learned is another question |
| 20:56:35 | maaku_: | nsh: fickle hashpower utterly destroys alts with bitcoin's stock difficulty adjustment algorithm |
| 20:56:51 | nsh: | * nsh nods |
| 20:57:00 | maaku_: | most adjustment algorithms used by alt devs are broken, on the other hand |
| 20:57:15 | nsh: | * nsh looking at vertcoin, which seems to be an actual effort, at least |
| 20:58:04 | nsh: | 67 pages of trollcointalk thread is quite depressing though. wish there was a way to getting the 5-10 posts that are actually worth reading out |
| 20:58:18 | maaku_: | amiller: do you have contact details for th type theory language person? |
| 20:58:32 | maaku_: | that's someone I'd want to talk to about scripting extensions |
| 20:58:33 | yasaii: | yasaii has left #bitcoin-wizards |
| 21:07:46 | maaku_: | nsh: there's also this, which we spent considerable time crafting : https://github.com/freicoin/freicoin/commit/d82a66e10f413bc81889b48a498625829353d701 |
| 21:07:57 | nsh: | looking |
| 21:08:27 | maaku_: | i think gmaxwell would have preferred using bessel functions, but an FIR filter has worked fairly well so far |
| 21:08:43 | nsh: | i recall gmaxwell demurring somewhat. but i guess it's held out pretty well? |
| 21:08:59 | nsh: | right |
| 21:10:12 | maaku_: | it has made the problem go from catestrophic to merely annoying |
| 21:11:39 | gmaxwell: | I watched it for a while and it seemed fairly poorly controled, but I never looked at it before the change. |
| 21:11:44 | maaku_: | there is still a major hopping pool which regularly hits us when profitability creeps up, but only snags a couple of dozen blocks before the difficulty adjusts back up |
| 21:12:32 | gmaxwell: | I'd worry that if there were two of those it might be unstable. but apparently not in practice. |
| 21:13:14 | maaku_: | I don't think there's anyone else using the same filter, but there are mare than two using fast-acting filters |
| 21:13:29 | maaku_: | and that's what the coin hopping pools are doing, jumping back and forth |
| 21:13:46 | maaku_: | i'd be interesting in hearing ideas about a better filter |
| 21:14:05 | maaku_: | although I think there are some fundamental problems here that won't go away |
| 21:14:13 | maaku_: | e.g. there's only so much you can do to mitigate the damage |
| 21:15:41 | gmaxwell: | creating strategic behavior isn't so hot though. |
| 21:19:13 | nsh: | a bunch of coins could probably dampen the effects of pools hopping with a profitability peg |
| 21:19:16 | nsh: | perhaps |
| 21:19:39 | maaku_: | nsh: vertcoin looks like stock bitcoin difficulty adjustment (+ time traveller patch) |
| 21:20:26 | maaku_: | nsh: well, you'd think profitability-seeking is, well, profitable. but it is not |
| 21:20:33 | nsh: | (could be. haven't quite figured out what the NFactor scrypt difference is they're pimping) |
| 21:20:50 | maaku_: | due to coinbase maturity & distribution delays, they get the coins *after* dips in prices due to their activities |
| 21:20:55 | nsh: | right |
| 21:21:09 | nsh: | i doubt the pool operators have analyzed it very deeply |
| 21:21:15 | maaku_: | i've seen people model this, and it's almost always 10% or so worse than mining a single coin |
| 21:21:20 | nsh: | * nsh nods |
| 21:21:49 | maaku_: | although there could be other strategies - e.g., mine the 2nd most profitable coin, in order to stay in frant of the bigger pool hopper |
| 21:21:52 | nsh: | you could probably account for hysteresis to some degree but the uncertainty would eat into the profitability |
| 21:22:14 | nsh: | right, but that's not robust with many players |
| 21:24:10 | maaku_: | it does show that you'd have to do some serious game theoretic analysis to figure out what optimal strategies are |
| 21:24:46 | nsh: | * nsh nods |
| 21:24:48 | maaku_: | and even then, you're battling human psychology, because we know that even the guiding hand of the market has led people to an inefficient strategy in practice |
| 21:25:13 | nsh: | i'm sure there's some law to the effect that people will always find a way to be more irrational than your models |
| 21:25:18 | maaku_: | so, in our case, we actually relied mostly on historical bitcoin data in the creation of our filter |
| 21:25:27 | nsh: | * nsh nods |
| 21:25:31 | maaku_: | we figured it's better to design something which works well at that scale |
| 21:25:52 | maaku_: | than over-optimise to solve this particular problem, which by nature goes away if you are the chief coin (or MM against it) |
| 21:26:05 | nsh: | right |
| 21:26:24 | amiller: | maaku_, i don't want to say any more about it until i get his permission |
| 21:26:26 | amiller: | maaku_, but i showed him your utxo engineering page |
| 21:26:46 | gmaxwell: | maaku_: I'm not sure that I would have used that data in design other than a validation test. The problem you need to engineer for here is a dynamic system problem so just some static data trace from bitcoin doesn't show you data from miners switching on and off in response to the difficulty. |
| 21:27:09 | maaku_: | amiller: well if you want you can show him this too: http://pastebin.com/5ScNX7vy |
| 21:27:13 | maaku_: | it's what I want his opinion on |
| 21:27:19 | maaku_: | and sounds like it might be related |
| 21:27:44 | maaku_: | gmaxwell: we used bitcoin, litecoin, and freicoin data |
| 21:29:37 | maaku_: | and a success metric of how close the chain would have stayed to 10 minute block times |
| 21:31:09 | maaku_: | interestingly the curves (various parameters vs simulated performance) remained the same for all three coins despite the different problems encountered by each. just noisier in the case of litecoin and freicoin |
| 21:31:51 | maaku_: | so we picked the fastest-acting values which were noise free, which by coincidence were also the best for bitcoin |
| 21:36:14 | nsh: | how was noise-free defined? |
| 21:37:52 | gmaxwell: | maaku_: I'd think that what I'd want to do is use the bitcoin/litecoin blockchain and market data to derrivate parameters for a model of miner behavior. (e.g. how fast do miners add and remove hashpower when its (un)profitable.) and then calibrate the control system against the miner model. |
| 21:53:08 | maaku_: | nsh: 1000's of simulations run, results plotted, then eyeballed |
| 21:53:22 | nsh: | right |
| 21:53:24 | maaku_: | so, tight grouping of data points |
| 21:53:40 | nsh: | * nsh nods |
| 21:53:58 | maaku_: | unfortunately all this work is on another hard drive |
| 21:54:03 | maaku_: | or i'd dig up some of the graphs |
| 21:55:17 | nsh: | no worries |