02:22:17OP_NULL:nsh: I can't find where it was talked about, but I don't think it's that. it was something to do with the way you evaluate your peers when they have a higher height than you.
02:23:28OP_NULL:nsh: https://botbot.me/freenode/bitcoin-wizards/2014-11-17/?msg=25672584&page=3
02:28:09OP_NULL:I find those blog posts very tiring to read, especially the one referenced in that link
02:31:14OP_NULL:even just from one post to the next the core concepts chop and change, it's not clear what is whimsy and what is actually being presented as a plan.
04:51:05manaka:are there any papers that better introduce the concept of zero knowledge proofs?
04:51:32manaka:also i am having some trouble understanding the counterparty protocol, are there papers on that?
04:54:04gwillen:gwillen is now known as Guest32116
04:54:05justanotheruser:manaka: does counterparty use zkps?
04:54:22justanotheruser:oh, thats separate
04:54:23manaka:lol i don't think so
04:54:36manaka:that would be something
04:54:47manaka:i do not know of any zkp implementation on bitcoin at the moment.
04:58:59justanotheruser:manaka: https://people.xiph.org/~greg/simple_verifyable_execution.txt
04:59:16justanotheruser:I'm guessing you want that
04:59:22gmaxwell:manaka: a regular digital signature is a
04:59:27justanotheruser:for counterparty, you probably want their whitepaper
04:59:28gmaxwell:zero knowledge proof.
04:59:58justanotheruser:I don't understand very well what counterparty accomplishes though
05:00:06manaka:me neither
05:00:09gmaxwell:manaka: it proves you know a secret without you learning anything about its secret.
05:00:26manaka:i believe it provides a utility of buying lots of issued tokens with the counterparty token.
05:00:30justanotheruser:counterparty, not zkp gmaxwell
05:00:49manaka:but in p2p networks there will always be a possibility for information leakeage gmaxwell
05:01:12manaka:else zkp only proves something exists, i just don't see how useful it can be
05:01:18gmaxwell:justanotheruser: I was responding to the first question. The second is almost completely uninteresting. :)
05:01:44justanotheruser:oh, how zkps are implemented in bitcoin...
05:02:12manaka:use cases for it
05:02:28gmaxwell:manaka: The whole idea of a _zero knowledge_ proof is that there is no leakage. (of course something could implement the protocol wrong or have other software bugs, or a sloppy user or...)
05:03:15gmaxwell:The wikipedia article gives a reasonable overview of the high level concept.
05:05:08manaka:thanks gmaxwell
05:05:39manaka:in your opinion gmaxwell do you think a dht/blockchain hybrid could exist?
05:06:04manaka:or mini blockchain on several subsets of a decentralized hash table?
05:06:38manaka:i just don't think proofs inside a blockchain will ever match the speed of a dht
05:07:58gmaxwell:hm? a blockchain can be seen as a kind of DHT, a D1HT (one hop hash table). This form has the best possible performance.
05:08:25gmaxwell:But, importantly to us, it's also pretty much toe only form of 'dht' that has a real security story in an adversarial model _at all_.
05:08:50gmaxwell:justanotheruser: you think I kid, google the term. :) people write research papers even on things as simple as that.
05:10:03justanotheruser:gmaxwell: this is a bit of a speculative question, but do you think it likely that a zkp will be made that is less computationally intensive than a snark?
05:10:29gmaxwell:(well, it's strictly true that its the only form with a security story, the DHT systems like freenet and CJDNS that have a "friends only" topology, have attack resistance too.. but their usability is poor)
05:10:43gmaxwell:justanotheruser: less expensive in what respect?
05:11:16justanotheruser:gmaxwell: creation
05:13:48gmaxwell:Well the scipr lab folks latest paper is somewhat cheaper for the prover... and lays the groundwork perhaps for further optimizations. The slowness in libsnark (and later work) mostly comes from having perform costly cryptographic operations per element in a circuit describing the function from very primitive parts (e.g. basic boolean or arithemetic gates).
05:14:20gmaxwell:Presumably ZKPs can be created in the same cryptographic framework that do more work per element, and thus could be faster to evaluate.
05:14:24Luke-Jr:justanotheruser: fast verification is more interesting IMO :p
05:14:33gmaxwell:verification is already quite fast.
05:14:49Luke-Jr:gmaxwell: fast enough we can softfork it into bitcoin in the next year?
05:15:14justanotheruser:Luke-Jr: fast and small proofs seem to done
05:15:25justanotheruser:*be done
05:15:53gmaxwell:maybe? there are other barriers than performance though. e.g. the field is not settled on parameters. The latest work requires a different family of curves specially constructed for them which you'd otherwise not prefer (slower in software).
05:16:03justanotheruser:Assuming they're secure. I am wondering about something an average computer could create.
05:16:52gmaxwell:justanotheruser: an average computer can create proofs with the libsnark stuff. At least of small programs like running sha256 64 times. (they apparently have proofs of that taking 30 seconds to create).
05:18:25justanotheruser:gmaxwell: I'm speaking more in terms of a miner creating a proof of the utxo and block with his client easily (even average joe using p2pool)
05:18:58gmaxwell:justanotheruser: who cares how long it takes, you can let such things lag multiple blocks behind.
05:19:32gmaxwell:well 'proof of the utxo' effectively requires a recursive proof to make it tractable at all, which is the latest work I was talking about.
05:20:00Taek:couldn't you also outsource the proof? Announce the winning block, and then have some specialized party create proof?
05:21:35gmaxwell:presumably justanotheruser wants to tie it to mining, but I don't really see a reason to do that.
05:23:51justanotheruser:gmaxwell: I assume it would be tied to mining anyways since a proof should be faster to verify than a block which increases a miners earnings.
05:27:01gmaxwell:nah, blocks are stupidly fast to verify assuming you're connected to the network.
05:27:11gmaxwell:Since you'll have already verified all the transactions already.
05:27:41gmaxwell:and you still need the data since you'll need it to construct a block spending outputs from the prior block.
05:28:55gmaxwell:though sure maybe the logical extension I've suggested before. ... where you never even disclose the transactions, just the final utxo set state....
05:29:05justanotheruser:at the very least, you would have full node security with a thin client as soon as a block comes out
05:29:35gmaxwell:e.g. miner proves "I started with the state of the prior block, applied an unspecified number of permitted transactions, and ended up with this final utxo set state.
05:31:45gmaxwell:justanotheruser: then thin clients could pay people to publish proofs... but really, some number of seconds delay is hardly that interesting... after all 1conf transactions are not irreverable in any case, so your security there is limited by reorgs not the risk if invalid blocks (unless you're talking very high value txn, in which case paying someone to run a full node and create the proofs doesn't seem like a big burden to me)
05:32:33justanotheruser:yeah, it doesn't seem that important for miners to create the proofs unless they want this very small relay time improvement
05:33:49gmaxwell:well in the model where all the tx data are forever hidden it makes sense because utxo that are born and die within a block never need to be visible to history.
05:39:41Guest32116:Guest32116 is now known as gwillen
05:50:56Taek:they don't need to be visible to history unless the proof creation requires knowing the entire history, which I imagine would be true
05:53:07gmaxwell:Taek: no, they don't need to be visible to history unconditionally.
05:53:24gmaxwell:As you already have the proof for that block.
05:56:21Taek:but, when you are trying to figure out the next block, and you have block boxes behind you, how can you be sure that you aren't spending something that was already spent in one of the black boxes? You can create a proof based off of prior proofs?
05:56:40Taek:I guess it could be possible.
05:57:59manaka:have you guys checked out the zero hop distributed hash table?http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=6569861&queryText%3DDistributed+hash+table
06:01:30gmaxwell:Taek: because you know the final utxo state.
06:01:40gmaxwell:If a utxo exists you can spend it, otherwise you can't.
06:02:55Taek:oh right not so magical at all
07:01:28lclc_bnc:lclc_bnc is now known as lclc
07:49:40luny`:luny` is now known as luny
09:05:18kornbluth.freenode.net:topic is: This channel is not about short-term Bitcoin development | http://bitcoin.ninja/ | This channel is logged. | For logs and more information, visit http://bitcoin.ninja
09:05:18kornbluth.freenode.net:Users on #bitcoin-wizards: andy-logbot AaronvanW cbeams damethos LarsLarsen Hunger- askmike xabbix zwischenzug Starduster_ Baz___ wallet42 todaystomorrow bit2017 heath samson_ bosma gwillen TheSeven Dr-G2 ryanxcharles roconnor rfreeman_w DougieBot5000 OP_NULL Greed rusty moa jaekwon altoz coinheavy adlai JohanTitor luny mkarrer__ livegnik nuke1989 aburan28 sneak prepost BananaLotus Graftec d4de iddo c0rw1n cryptokeeper Aquent atgreen Myagui Emcy LaptopZZ Flyer33
09:05:18kornbluth.freenode.net:Users on #bitcoin-wizards: devrandom diametric a5m0 copumpkin SDCDev mortale Cory prodatalab @ChanServ bitname fanquake hashtag_ btcdrak dansmith_btc2 jgarzik epscy digitalmagus PaulCapestany shesek snorkl burcin Shiftos coutts Qfwfq wizkid057 phantomcircuit kgk maaku arowser spinza Nightwolf HaltingState PRab paperbot Dyaheon bbrittain iambernie NikolaiToryzin rasengan forrestv null_radix Luke-Jr nickler bobke_ warptangent mr_burdell Logicwax zibbo Meeh kanzure
09:05:18kornbluth.freenode.net:Users on #bitcoin-wizards: tromp_ SomeoneWeird Krellan tromp__ poggy pi07r_ sipa comboy_ mmozeiko lnovy Taek optimator_ [\\\] waxwing Guest39111 Apocalyptic throughnothing Pan0ram1x petertodd crescendo CryptOprah AdrianG cfields kumavis sl01_ Fistful_of_Coins gmaxwell kinlo ahmed_ BlueMatt doc321R K1773R so weex Anduck Alanius lclc GnarSith [d__d] gnusha_ espes___ hguux_ btc_ jbenet michagogo BigBitz DoctorBTC SubCreative otoburb wumpus artifexd EasyAt starsoccer HM
09:05:18kornbluth.freenode.net:Users on #bitcoin-wizards: hollandais fluffypony fenn jaromil helo Keefe Iriez Eliel jrayhawk huseby phedny MRL-Relay berndj midnightmagic nsh Muis coryfields mappum andytoshi BrainOverfl0w fds4345 gazab warren gavinandresen pigeons nanotube asoltys gribble Graet smooth amiller danneu catcow TD-Linux [Tristan] ryan-c roasbeef harrow abc56889 lechuga_
09:36:09lclc:lclc is now known as lclc_bnc
09:37:33lclc_bnc:lclc_bnc is now known as lclc
10:03:16OP_NULL:it actually looks like DarkCoin will become a nice study of incentives, though I doubt they intend it to be. their "masternode" setup slowly absorbed more and more of the block reward as time goes on. https://github.com/darkcoin/darkcoin/blob/master/src/main.cpp#L1399-1428
10:07:42rabbit2:is it possible to have a security model where a 51% attack requires performing not just 51% of the work going on right now
10:08:02rabbit2:but instead 51% of the work ever performed throughout the blockchain history
10:08:17sipa:how would that work?
10:08:25rabbit2:suppose that miners submit a hash right now
10:08:48rabbit2:and then this hash allows them to create a 'virtual hashing machine'
10:09:08rabbit2:the 'virtual hashing machine' operates as if it is performing hashes in perpetuity
10:09:35rabbit2:the owner of the virtual hashing machine hold it's private key
10:09:44rabbit2:and signs blocks using this private key
10:09:54rabbit2:the virtual hashing machines are non-transferable
10:10:01sipa:you're handwaving
10:10:16sipa:"as if" doesn't work in practice; you need to know how to do that
10:10:41OP_NULL:that's got some weird properties as well. you can't measure hashrate from a single hash. if I'm the person who solved a more than 80 bit block hash, that means I would control most of the networks "hashrate", right?
10:10:42rabbit2:okay, it's actually not that complicate
10:10:56sipa:rabbit2: it gets complicated if you actually try to solve the problems you're handwaving over
10:11:02rabbit2:you hash once and this creates a unit of non-transferable stake that exists in perpetuity
10:11:29rabbit2:you then select a unit of non-transferable stake at random to mine a block
10:11:52rabbit2:the total hashing power available at any one point in time = all hashes performed since the creation of the blockchain
10:11:58sipa:this seems vulnerable to the nothing at stake problem
10:12:00OP_NULL:go back to the bit where the miner makes the hash. how do you know what speed they were mining at? we don't even know what the speed of the network is today.
10:12:25rabbit2:you would need to have a constant level of difficulty
10:12:36sipa:rabbit2: have you heard about the nothing at stake problem?
10:13:02rabbit2:yes, I don't think it is an issue here.
10:13:14rabbit2:You can't credibly trade stake to someone else
10:13:32rabbit2:Whoever created the stake by performing the hash will control it in perpetuity
10:13:36OP_NULL:ah. yeah that doesn't work. if you had the same difficulty today as you had in 2009, you'd be making 288,000,000,000,000,000 hashes a second which you would need to store.
10:14:15rabbit2:OP_NULL: True enough, but let's ignore that problem for the time-being
10:15:02rabbit2:sipa: could you explain why you think nothing at stake would apply here?
10:15:26sipa:rabbit2: you can't prevent using the stake on two competing chains simultaneously
10:15:47OP_NULL:rabbit2: the fact remains that you can't measure absolute hashpower of a miner
10:16:02sipa:that's the essential thing necessary for convergence: you need to force people to expend something, which they lose even if they vote wrong
10:16:18rabbit2:yes, I see what you are saying sipa
10:16:40sipa:if the thing you are expending is defined by the chain itself, it doesn't work, as it exists in equal amounts in other chains
10:16:49sipa:hashing is expending something (calculation power)
10:17:02sipa:spending tokens that are defined by the chain itself don't
10:17:04rabbit2:it is not quite defined by the chain itself because it is actual
10:17:10sipa:it used to be
10:17:34sipa:you can't use your tokens further back than the point where the hash was created, true
10:17:40rabbit2:to make someone expend something you would need to also require a contemporaneous work input to extend a chain
10:18:15rabbit2:That would provide a sufficient incentive not to mine 2 chains at once.
10:19:24sipa:if you can use the rest simultaneously, it doesn't add anythin
10:19:41rabbit2:They would need to enter as separate inputs.
10:20:03sipa:it's not really about incentive... there is no cost to using pre-held stake an infinite number of times, and you don't lose anything by doing so
10:20:28rabbit2:You would have to pay a cost in current work to use your pre-held stake
10:20:38sipa:which cost?
10:20:45sipa:defined by your chain itself again?
10:20:47sipa:or dollars?
10:21:12rabbit2:You would need to submit novel work in conjunction with your tokens in order to extend a chain.
10:21:19sipa:how do they interact?
10:21:24rabbit2:The amount of novel work you need to submit could be quite small
10:21:30sipa:i have X tokens and H hashes, how much is it worth?
10:21:33rabbit2:It could be some version of proof of activity for example
10:21:53sipa:if the amount of novel work is small, then you have the same problem again
10:22:12sipa:because it is cheap to reuse the same tokens in different chains
10:22:24rabbit2:The problem is just discouraging regular miners from mining multiple chains.
10:22:33sipa:you're not discouraging anyone
10:23:10sipa:the measure you use to judge different chains must be proportional to what was lost in creating them
10:23:10rabbit2:Yes, you can reuse the same tokens on different chains. But if each use is costly in terms of current work, you won't want to.
10:23:33sipa:so the PoW is not small
10:23:42sipa:then what do you need the tokens for still?
10:23:44rabbit2:i.e. you would stand a better chance of using all of your current work on the main chain, instead of allocating it to an alternate chain that is less likely to be extended
10:24:05rabbit2:Someone would need the tokens to complete a 51% attack.
10:24:20sipa:if the bottleneck is the proof-of-work, everyone will have plenty of tokens
10:24:30sipa:if the bottleneck is the tokens, you suffer from nothing at stake
10:24:42rabbit2:There doesn't have to be one bottleneck
10:24:51sipa:then stop handwaving :)
10:24:56rabbit2:You can combine two valuable resources
10:25:31rabbit2:Okay, just think of your effective difficulty for current work as 1/(tokens used)^0.5
10:25:34sipa:that still means you've made hashing on multiple chains cheaper
10:26:10sipa:which is the problem we're trying to solve
10:26:23rabbit2:Yes, it is a half-baked idea.
10:26:29rabbit2:I just came up with it a few minutes ago.
10:26:42rabbit2:It solves part of the problem.
10:26:58rabbit2:Anyways nice talking to you I will think more
11:51:24hearn:does anyone happen to know a simple/quick reference for zero knowledge proofs of the correctness of a homomorphic-cryptosystem decryption? like a zkp that a paillier ciphertext was properly decrypted
11:51:33hearn:* hearn suspects gmaxwell would know
12:40:30Alanius:hearn: what is it precisely you're trying to prove? "this plaintext encrypts to this ciphertext" or "I know a plaintext that encrypts to this ciphertext"?
12:41:12hearn:the latter. this post seems relevant and the technique seems simple: http://crypto.stackexchange.com/a/6743
12:41:24hearn:or no sorry
12:41:25hearn:the former.
12:41:48Alanius:then why not release the plaintext and the randomness?
12:41:57hearn:i have a ciphertext that resulted from adding some other ciphertexts together. here is the cleartext sum, and the proof that i did it correctly (Well you can just add the numbers yourself to get the final ciphertext)
12:42:05hearn:yes that's what the linked answer says, pretty much
12:42:09hearn:i didn't realise it would be that simple
12:44:05Alanius:in the case of paillier it's not possible to release the randomness that matches a ciphertext that was produced from homomorphically adding
12:44:20Alanius:because that would require taking discrete logs
12:45:02Alanius:however, you there is a proof saying "I raised this number to the correct exponent and the result is this"
12:45:22Alanius:I think it's called the Damgård-Jurik proof, let me find it for a sec
12:46:34Alanius:it will be in here: ftp://ftp.cs.au.dk/BRICS/Reports/RS/00/45/BRICS-RS-00-45.pdf
12:47:49sipa:oh, hi Alanius!
12:48:08sipa:didn't realize you found the way here :)
12:48:42hearn:Alanius: yes i've seen reference to that kind of proof. need to research it.
12:49:27Alanius:got to go no, good luck
12:49:47hearn:i'm not quite sure how being able to prove that statement helps me, though ...
12:49:54hearn:it doesn't have to be paillier
12:50:02hearn:any additively homomorphic scheme works
12:50:12hearn:exponential elgamal is one i saw referenced as perhaps better suited to this task
15:45:21c0rw1n:c0rw1n is now known as c0rw|away
15:54:12lclc:lclc is now known as lclc_bnc
16:16:08lclc_bnc:lclc_bnc is now known as lclc
17:20:14lclc:lclc is now known as lclc_bnc
17:22:07zooko`:zooko` is now known as zooko
20:04:00luny`:luny` is now known as luny
20:34:05Guyver2:Guyver2 has left #bitcoin-wizards
21:18:55HM:sipa, anyone. what's the EC equivalent of g^b - kg^x in terms of point operations?
21:19:18HM:it's just B - kxG right
21:19:48HM:yeah, nm, i'm going dappy
21:37:03wheninrome:wheninrome has left #bitcoin-wizards
21:51:35kanzure:would it be feasible or desirable to include in the bitcoin transaction serialization a blockhash (covered by the signature) that states which blockhash must be in the history of the blockchain for this transaction to be accepted or considered valid?
21:52:21kanzure:one of the reasons i'm thinking about that is because it would allow certain transactions to be issued only conditionally based on some prior transactions included in previous blocks
21:53:39kanzure:(such that the transaction can't be included in a history that does not have that prior block)
21:57:12kanzure:also, this would be neat because you don't have to reference the immediately preceding block hash, or the exact block hash of some transaction that you want to depend on but rather any block after that point and you'll get mostly the desired effect
21:57:33kanzure:and choosing different blockheights more specifically can occur based on your risk appetite or something.
23:03:50sipa:kanzure: gmaxwell proposed that before, actually :)
23:04:01sipa:HM: yes
23:04:29gmaxwell:kanzure: it's on the altwishlist page of mine, I called it transaction checkpoints.
23:04:58kanzure:could that be done by an opcode?
23:05:53sipa:in theory, sure
23:06:30kanzure:i mean in a way that does not fork the blockchain
23:12:08gmaxwell:kanzure: what I'd suggested there was no so much that it mandated the chain but it only let you collect the fees if it agreed. I suppose a bit could be used to signal stronger behavior... though there is a fungiblity hit if you have it so huge transaction graphs can't be confirmed.
23:21:56c0rw|away:c0rw|away is now known as c0rw|timetravel
23:24:15c0rw|timetravel:c0rw|timetravel is now known as c0rw1n
23:31:17altoz_:altoz_ is now known as altoz