03:07:58kefkius:Would it be at all feasible to implement merge-staking (like merge-mining) in PoS chains, or is that ridiculous?
03:09:30NikolaiToryzin:NikolaiToryzin is now known as stqism
03:11:34stqism:stqism is now known as NikolaiToryzin
03:13:55nsh:kefkius, to what end?
03:25:43kefkius:It wouldn't really achieve anything. Mostly wondering if it would be possible to have your coin age on chain A, and be able to stake on chain B
03:26:28justanotheruser:kefkius: I was thinking about this. Without having stake-stamps or whatever you want to call you DMMS confirmed by a PoW first, it is completely insecure and even with that there are security problems
03:27:29nsh:well obviously the bottom layer of turtles are floating on buffer of hot air coming from asic heatsinks
03:28:23nsh:but nothing technically stops stake, or any other measurable/calculable function of blockchain parameters from propagating from chain to subchain
03:30:23nsh:i think the problem is that the relationship between algorithmic subsidization on the basis of such functions and economic behaviour prefiguration is unclear, and may require empirical determination
03:31:17nsh:and a means of dynamically adapting those algorithms without affecting the value or security stability of the system is technically challenging
03:39:26gmaxwell:kefkius: sure why not, but it wouldn't be any less broken than POS in general. :)
03:41:39nsh:(broken as a replacement for proof-of-work)
03:41:58kefkius:gmaxwell: With enough effort, we could make it even more broken
03:42:31gmaxwell:"We have the technology"
03:42:52gmaxwell:but, sure, no challenge in that, just add complexity and you're almost certian to become more broken.
03:43:15justanotheruser:gmaxwell: I don't think PoS backed by PoW is broken in the same way PoS bootstrapping is.
03:44:32justanotheruser:If I have a PoS sidechain that requires I make a transaction confirming the PoS in a PoW parent chain then I cannot stake grind since presumably the proof for the next block would be dependent on the PoW of the parent.
03:44:50kanzure:the observation that random bits of software can be forced together in a way that might technically compile is really uninteresting both in the software world and whatever niches of that which bitcoin occupies....
03:45:03kanzure:what is the advantage of that additional complexity there?
03:45:26justanotheruser:I'm doubting this would be useful though since a PoW parent could censor PoS that they aren't getting paid for.
03:48:32gmaxwell:justanotheruser: security reduces to POW there, ultimately...
03:51:33justanotheruser:gmaxwell: yeah, the security is through PoW. The arguable advantage I have been able to think of is that that is one less chain a PoW miner has to keep track of and less chains would have to be verified meaning easier verifying of pools blocks by miners.
03:51:46penny:penny is now known as Guest48119
03:52:27justanotheruser:s/chains would have to be verified meaning/chains to verify means/
05:11:58gmaxwell:andytoshi: interesting that there were no useful answers given to this: https://moderncrypto.org/mail-archive/curves/2014/000203.html
05:58:46penny:penny is now known as Guest77313
06:20:39dansmith-:dansmith- is now known as dansmith_btc
07:38:18[\\\\]:[\\\\] is now known as [\\\]
08:02:25rs0:rs0 has left #bitcoin-wizards
09:03:07penny:penny is now known as Guest40318
09:05:14verne.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:14verne.freenode.net:Users on #bitcoin-wizards: andy-logbot Guest40318 justanot1eruser berndj torsthaldo aburan28 damethos cbeams [\\\] mortale koshii copumpkin [7] todaystomorrow Dr-G Graftec shesek Adlai Flyer9933 zwischenzug samson_ roconnor e4xit PRab phantomcircuit Aquent HaltingState spiftheninja hashtag_ wiretapped spinza kefkius Keefe kyletorpey Transisto ebfull Guest56997 nuke1989 Luke-Jr waxwing sekoe iddo Baz__ zenojis mmozeiko SDCDev tacotime PaulCapestany pi07r ryanxcharles
09:05:14verne.freenode.net:Users on #bitcoin-wizards: btcdrak digitalmagus grandmaster2 fragiletag midnightmagic sl01 satoshi393 nsh wizkid057 Muis Alanius Guest1930 arowser LarsLarsen go1111111 fanquake sipa paperbot altoz Anduck poggy Jokosh NikolaiToryzin cfields coryfields super3 Sangheili mappum hollandais jbenet epscy bosma kjj21__000 eric DoctorBTC Taek Cory sneak EasyAt warptangent Hunger- optimator_ Starduster kumavis heath andytoshi dgenr8 BrainOverfl0w fds4345 gazab Iriez bbrittain
09:05:15verne.freenode.net:Users on #bitcoin-wizards: BigBitz Apocalyptic emsid Starsoccer throughnothing warren tromp_ null_radix gavinandresen dansmith_btc Meeh GnarSith kyuupichan stonecoldpat Nightwolf AdrianG Logicwax mr_burdell Eliel zibbo_ tromp SomeoneWeird kgk firepacket Dyaheon myeagleflies wumpus K1773R pigeons nanotube Grishnakh lnovy asoltys weex_ Fistful_of_coins kanzure gribble Krellan kinlo a5m0 superobserver phedny artifexd fenn [d__d] LaptopZZ gnusha HM_ espes__ CryptOprah Graet
09:05:15verne.freenode.net:Users on #bitcoin-wizards: burcin livegnik gmaxwell _2539 hguux bobke petertodd smooth BlueMatt @gwillen michagogo jrayhawk_ yoleaux amiller crescendo btc_ @ChanServ lechuga_ abc56889 harrow so ahmed_ Gnosis pajarillo roasbeef ryan-c otoburb helo_ [Tristan] TD-Linux catcow danneu
09:55:04kefkius_:kefkius_ is now known as kefkius
10:13:44austinhill:Just wanted to thank @gavinndresen @gwillen@luke-Jr Corrine DashJR, Mathias Dybvik Shad Kfir, @midnightmagic, Patrick Strateman Daniel Folkinshteyn, Shaul Kfir and the many other #bitcoin-wizards who have contributed to the ideas that formed Blockstream.com and your contributions to the whitepaper we released
12:49:48andytoshi:gmaxwell: huh. i guess i should subscribe to that group
12:50:55andytoshi:gmaxwell: i don't get it, there is a standard NIZK "i know what of N discrete logs" i think due to cramer that you can just fiat-transform
12:51:48andytoshi:s/what/one/
13:56:55fanquake:fanquake has left #bitcoin-wizards
15:06:45andytoshi:standard interactive proof of knowledge* ... then you FS it to get a nizk :)
15:29:11penny:penny is now known as Guest19684
16:36:08spiftheninj:spiftheninj is now known as spiftheninja
16:51:29spiftheninja:spiftheninja has left #bitcoin-wizards
19:29:43midnightmagic:I'm curious who austin hill is now. :)
19:30:06midnightmagic:but, you're welcome, for the tiny bit I did do, in case you're still listening
19:33:55zooko:Austin Hill is the CEO of Blockstream.
19:52:45midnightmagic:oh
19:59:18gmaxwell:So fun observation today: If you use RFC6979 as specificed with schnorr it introduces a vulnerability that schnorr doesn't have natively (though a somewhat fanciful one)
19:59:54nsh:.wik RFC6979
19:59:55yoleaux:"In cryptography, the Elliptic Curve Digital Signature Algorithm (ECDSA) offers a variant of the Digital Signature Algorithm (DSA) which uses elliptic curve cryptography." — http://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
20:00:08gmaxwell:6979 computes K = HMAC(counter||priv||H(message),zeros)
20:00:48gmaxwell:so if I can find message and message' that are collisions for H() and I can get you to sign both of them, I get your private key.
20:01:01zooko:Nice.
20:01:13gmaxwell:Schnorr doesn't generally have problems with collisions because the hash is randomized.
20:02:14gmaxwell:(pieter is working on schnorr for libsecp256k1 (https://github.com/bitcoin/secp256k1/pull/87), the interface isn't high level enough to do determinstic signing yet.
20:04:58zooko:Wait, isn't `k` used only for the signature on `message`?
20:08:48gmaxwell:zooko: right but H(message) == H(message') in my example, so if I ask you to sign both of them you'll get the same K, and in schnorr the signature computes e = H(message||r) which will be different in each case.
20:10:01gmaxwell:so you will sign two different messages with the same K in that example. It's not a serious vulnerability in that it assumes the attacker can construct a H() collision with two messages that you'll sign; but that is not something schnorr is normally weak against.
20:10:37zooko:I'm not very strong on this stuff. Isn't... Ohhh, H(message||r). I see.
20:11:22zooko:Mildly surprised to see Thomas Pornin leave that in there. Couldn't it have been HMAC(k, m) instead of H(m) in 3.2.a.?
20:12:14gmaxwell:zooko: well the design was basically to take a pre-existing CSPRNG _exactly_ and apply it to DSA.
20:12:33justanotheruser:I hope no implementations use a hashing algorithm with known collisions :P
20:12:54gmaxwell:In the DSA case you're hosed if an attacker can produce collisions on H() since he'll make message' an evil forgery and ask you to sign message and just copy your signature.
20:19:54sipa:i'm interested whether a hash function could be constructed that is secure against preimage attacks (or at least as good as current designs are assumed to be), but not secure against collision at all
20:20:04zooko:sipa: !!
20:20:19zooko:sipa: the answer is: it is so easy that about half of all secure hash functions ever deployed have achieved it. ;-)
20:20:42zooko:Or to put it another way: it is questionable whether we really know how to make collision-resistant hash functions, but pre-image-resistant hash functions are a dime a dozen.
20:20:42sipa:well, yes
20:21:00zooko:I have an unpublished note about this: https://tahoe-lafs.org/~zooko/preimage-attacks-color.html
20:21:26zooko:My personal take-away is that if your thing can be invulnerable to collisions, then it is a huge step up.
20:21:43justanotheruser:sipa: wouldn't that imply the the set of preimages had to be as big as the set of hashes?
20:22:18sipa:hmm, md5 is further broken than i believed
20:22:31sipa:2^24.1 for a collision, while the expectation would be 2^64
20:22:51justanotheruser:actually I read that backwards
20:23:33justanotheruser:sipa: thats easy. sha256 % 2^246
20:24:05sipa:oh? produce me a collision for that? :p
20:24:25justanotheruser:sipa: well there are only 1024 possible hashes...
20:24:32sipa:no, 2^246
20:24:43sipa:if there are only 1024 possible hashes, then preimage is trivial too
20:25:19justanotheruser:lol, I need to go to bed. yes, sha256 % 2^20 or something
20:25:55justanotheruser:however, finding a preimage would be through finding a collision, right?
20:25:58sipa:justanotheruser: that still has the same expectations as usual... O(n) work for a preimage, O(sqrt(n)) for a collision
20:26:08sipa:no?
20:26:30sipa:a preimage is find me an input for a specific hash (or for the same hash as a specific input)
20:26:38sipa:a collision is find me two inputs with the same hash
20:26:41justanotheruser:yeah
20:26:44sipa:they're separate problems
20:26:48justanotheruser:I know
20:27:05sipa:i don't see how you would use a collision search to find a preimage
20:29:46justanotheruser:sipa: aren't collisions a subset of preimages found anyways?
20:30:24sipa:huh? they're a superset
20:30:27justanotheruser:you can just aren't bounded to a specific preimage rather, two preimages you can define when finding a collision
20:30:37justanotheruser:right, superset
20:30:39sipa:if you can find preimages, you can of course also find collisions
20:30:57justanotheruser:please excuse me, I am a bit sleep deprived :P
20:32:47justanotheruser:hmm. you could make a really hackey hash function where the hashes aren't uniformly distributed.
20:34:15justanotheruser:If you're performing a preimage attack against a website, the website may be resistant since they require users passwords to hash to the secure values, however finding a collision in small range where, lets say 1/1000 hashes evaluate the the same value.
20:34:24justanotheruser:If you want a poorly written hash function, there it is
20:35:04sipa:that also makes preimages easy :)
20:35:54justanotheruser:sipa: yeah, I'm slaughtering the definition. You can find a preimage in the insecure range and its still a preimage.
20:36:10justanotheruser:is there something desirable about such a hash function?
20:36:25sipa:well there seem to be use cases that do not require collision resistance
20:36:55justanotheruser:Is there no proof collision finding in a hash function of log(preimage finding time) worst case?
20:36:55sipa:if a hash function can be constructed that is much more efficient, at the cost of collision resistance, but without sacrificing preimage resistance, that may be worth it
20:37:31sipa:sqrt(),i hope
20:37:48justanotheruser:lol, like I said, sleep deprived
20:38:02justanotheruser:but ou would like log time wouldn't you? :) Lets pretend thats why I said it
20:38:04sipa:sqrt(2^256) is still pretty infeasible
20:39:57justanotheruser:livin in log(2^256) mining paradise
20:41:47justanotheruser:that is an interesting problem. Have you thought of any solutions?
20:43:33sipa:seems MD5 would be a good candidate :p
20:43:45sipa:best known preimage attack has 2^123 complexity
20:44:50justanotheruser:do you think being easy for collisions is an actual property of the function though?
20:45:16justanotheruser:or is it just that preimage attacks haven't been discovered to match
20:46:17zooko:blake2 is faster than md5 [*
20:46:24zooko:] while also being collision-resistant [**].
20:46:27zooko:[*] sometimes
20:46:29zooko:[**] probably
20:46:37gandalf:could maidsafe become a sidechain?
20:46:53gandalf:FYI: maidsafe doesn't have a blockchain
20:47:07gandalf:they use transaction managers which only track last states
20:47:10justanotheruser:gandalf: if it doesn't have a blockchain it can't be a side "chain"
20:47:15justanotheruser:you could have a two way peg though
20:47:20gandalf:how?
20:47:37justanotheruser:by coding a two way peg
20:48:10gandalf:how fast would that be?
20:48:15justanotheruser:?
20:49:09gandalf:gandalf has left #bitcoin-wizards
20:50:17andytoshi:justanotheruser: you can derive much of modern crypto from nothing but one-way functions / one thing you -can't- (that we know of) is a CRHF
20:50:31manaka:does anyone know what super3 storj meant when they said the network would gain from forks?
20:51:04sipa:andytoshi: CRHF?
20:51:13andytoshi:sipa: collision resistant hash function
20:51:18sipa:oh, duhh
20:51:25andytoshi:sorry, still reading scrollback, didn't realize that acronym hadn't appeared :)
20:52:00manaka:https://www.youtube.com/watch?v=nO-fZgsovgI 26:00
20:52:27justanotheruser:andytoshi: we are discussing hash functinos vulnerable to collisions but not preimages
20:52:46andytoshi:justanotheruser: yes, so a OWF that is not a CRHF
20:53:06sipa:andytoshi: but even a one-way function is an assumption :)
20:53:12Apocalyptic:"we are discussing hash functinos vulnerable to collisions" // that's redundant, a hash function has by design collisions
20:53:33andytoshi:sipa: sure, but it seems like a safer one :)
20:53:40manaka:how could forks of a blockchain get a piece from the original blockchain?
20:53:44andytoshi:most of modern crypto implies OWF's ... the implications go in both directions
20:53:45justanotheruser:andytoshi: not just not a CRHF (which I assume implies sqrt time for finding a collision), but something log or constant probably.
20:53:47Apocalyptic:the interesting thing to study is how easy it is to find them
20:53:56sipa:Apocalyptic: "vulnerable" in this context means "worse than the theoretical best bound"
20:53:59justanotheruser:manaka: #bitcoin
20:53:59paperbot:ConnectionError: HTTPConnectionPool(host='localhost', port=1969): Max retries exceeded with url: /web (Caused by : [Errno 104] Connection reset by peer) (file "/usr/local/lib/python2.7/dist-packages/requests/adapters.py", line 375, in send)
20:54:17Apocalyptic:sipa, fair enough
20:54:23andytoshi:Apocalyptic: yes, "vulnerable" means "there exists a PPT algo which can find a collision with nonnegligible (i.e. inverse polynomial) probability"
20:54:28justanotheruser:while at the some time taking O(N) time to find a preimage
20:54:45manaka:what do you mean justanotheruser? the new fork would be completely different perhaps rebranded
20:54:54andytoshi:justanotheruser: usually you talk of complexity in terms of the security parameter (e.g. 256) rather than the search space
20:55:09justanotheruser:on a side note, are there any inductive hash functions
20:55:18andytoshi:justanotheruser: so it's O(2^λ)
20:55:26justanotheruser:I see
20:56:04justanotheruser:manaka: I mean questions you are asking belong in #bitcoin
20:56:46andytoshi:interestingly a QC wolud let you do a preimage attack with quadratic advantage ... idk what it gets you for collisions
20:57:05andytoshi:mabye then in a quantum computer world collisions and preimages would be equally difficult?
20:57:21andytoshi:(for a CRHF)
20:59:03justanotheruser:interesting
21:00:25justanotheruser:so those who care about preimages only would have to quadruple rather than double their security parameter
21:00:49justanotheruser:only describes preimages in that sentence
21:02:34phantomcircuit:gmaxwell, fortunately you're not hashing attacker supplied messages
21:03:37gmaxwell:andytoshi: n^1/3 http://arxiv.org/abs/quant-ph/9705002 (I think elsewhere it's proven to be tight)
21:04:06phantomcircuit:also
21:04:06phantomcircuit:http://www.goodwinprocter.com/Publications/Newsletters/Client-Alert/2014/1015_Software-Companies-Now-on-Notice-That-Encryption-Exports-May-Be-Treated-More-Seriously.aspx
21:04:07phantomcircuit::/
21:04:38justanotheruser:time to make a book of qr codes
21:04:51gmaxwell:phantomcircuit: yea, doesn't apply to open source software (see berinstein v us), doesn't apply to authentication rather than encryption.
21:05:58phantomcircuit:gmaxwell, good to know
21:06:05paperbot:ConnectionError: HTTPConnectionPool(host='localhost', port=1969): Max retries exceeded with url: /web (Caused by : [Errno 104] Connection reset by peer) (file "/usr/local/lib/python2.7/dist-packages/requests/adapters.py", line 375, in send)
21:06:55phantomcircuit:gmaxwell, the nice thing about how signing is used within bitcoin is that the message is largely not attacker selected
21:15:41zooko:gmaxwell: djb says that is incorrect: http://cr.yp.to/hash/collisioncost-20090823.pdf I haven't the knowledge necessary to judge if that's correct.
21:15:58zooko:bbiab
21:24:40gmaxwell:zooko: yea, I actually think I was only aware of BMT due to reading that, but normally real details like the cost of the underlying hardware are unhelpfully ignored in asymptotic analysis. andytoshi's question though was is quantum preimage and collision the same speed, seems unlikely not.
21:25:31gmaxwell:er BHT.
21:26:25gmaxwell:zooko: IIRC DJB's argument is that there is a hidden machine size variable in it, and if you build classical computers with the same level of parallelism and use state of the art techniques you get similiar/better time performance. E.g. saying quantium isn't cost effective for these problems using fairly reasonable guesses at the costs of quantium logic vs classical.
21:27:25gmaxwell:so not that you can't do searches in time n^1/3, but that classical machines with enough free parallelism can too. :)
21:51:58davidlatapie:davidlatapie has left #bitcoin-wizards
23:05:28phantomcircuit:2014-11-03 22:56:12 ERROR: CheckInputs() : tried to spend coinbase at depth 66
23:05:28phantomcircuit:2014-11-03 22:56:12 ERROR: AcceptToMemoryPool: : ConnectInputs failed 39b5b867aa65fb1a1d3b8db628dff25a329e32ea069674110ae9f59e68f203be
23:05:29phantomcircuit:2014-11-03 22:56:12 ERROR: CheckInputs() : tried to spend coinbase at depth 66
23:05:29phantomcircuit:2014-11-03 22:56:12 ERROR: AcceptToMemoryPool: : ConnectInputs failed dbfaca00ba435f33489294206b5d358e6d57570913e5026e5e18c69076ae528a
23:05:33phantomcircuit:wat
23:15:53gmaxwell:either an out of sync node, or yet another mtgox-grade dim bulb who shouldn't be writing wallet code...
23:18:31gmaxwell:phantomcircuit: so for 39b5b867aa65fb1a1d3b8db628dff25a329e32ea069674110ae9f59e68f203be one of the inputs is exactly 100 blocks deep now.
23:19:11gmaxwell:likewise for the other txn
23:19:57gmaxwell:but considering that you got that message like .. 20 minutes ago. ... hm, even then it shouldn't have been depth 66. I think your node is out of sync.
23:20:29phantomcircuit:gmaxwell, must be
23:20:49phantomcircuit:that's better than the alternative at least :)
23:48:54bryanvu_:bryanvu_ is now known as bryanvu