01:26:04pigeons:pigeons is now known as Guest98031
01:29:00gmaxwell:[semi-ontopic] http://mirrors.dotsrc.org/fosdem/2014/Janson/Sunday/NSA_operation_ORCHESTRA_Annual_Status_Report.webm
02:15:27irc.freenode.net:Disconnected from irc.freenode.net (ERROR :Closing Link: S0106c0c1c0894c25.vs.shawcable.net (Ping timeout: 260 seconds))
02:20:18irc.freenode.net:Disconnected from irc.freenode.net (ERROR :Closing Link: S0106c0c1c0894c25.vs.shawcable.net (Connection timed out))
02:25:26irc.freenode.net:Disconnected from irc.freenode.net (ERROR :Closing Link: (Connection timed out))
02:26:40cameron.freenode.net:Users on #bitcoin-wizards: @andytoshi-logbot
03:02:04dickson.freenode.net:topic is: "Bitcoin research, hardfork wishlist, ideas for the future - see also: https://en.bitcoin.it/wiki/Hardfork_Wishlist https://en.bitcoin.it/wiki/User:Gmaxwell/alt_ideas. This channel is logged at http://download.wpsoftware.net/bitcoin/wizards/. For questions about the logs talk to andytoshi."
03:02:04dickson.freenode.net:Users on #bitcoin-wizards: andytoshi-logbot andytoshi jarpiain_ hnz Guest67602 asoltys Guest24999 otoburb__ wyager gribble cpacia pigeons_ go1111111 espes___ matrixfo1 spin123456 tromp_ edulix_ Xarian Krellan__ Alanius Muis_ shinybro_ nsh imsaguy azariah4 tucenaber_ adam3us1 samson_ austinhill ryan-c nessence_ OneFixt [\\\] flotsamuel forrestv bobke trn rdymac qwertyoruiop Sorcier_FXK Hunger- Emcy perrier iddo pajarillo UukGoblin epscy Luke-Jr Krellan jrmithdobbs
03:02:04dickson.freenode.net:Users on #bitcoin-wizards: michagogo|cloud Sangheili Mikalv K1773R c--O-O CodeShark HM_ licnep IOI_ coryfields zacm shesek ironzorg maaku wangbus firepacket midnightmagic shinybro nanotube hno` tt_away crucif0rm salsa poggy warren aksyn jron jgarzik sl01 BlueMatt grazs helo amiller kinlo crescendo rs0_ @ChanServ phantomcircuit Ryan52 Fistful_of_Coins wumpus optimator fagmuffinz gmaxwell petertodd heakins sipa realazthat a5m0 comboy Graet harrow EasyAt typex
03:04:02pigeons:pigeons is now known as Guest77872
03:33:44matrixfo1:matrixfo1 is now known as matrixfox
03:37:09otoburb__:otoburb__ is now known as Guest82291
03:40:02Guest82291:Guest82291 is now known as otoburb`
03:40:43otoburb`:otoburb` is now known as otoburb
04:29:55andytoshi:it's late and there's probably something stupidly wrong about this, but i think i've proven that schnorr sigs are nonmalleable. specifically, a malleability attacker can be used to produce an actual signature forgery. http://download.wpsoftware.net/bitcoin/wizardry/schnorr-mall.pdf
04:31:01andytoshi:(ofc there could still be malleability in the actual encoding of signatures. but that's easy to standardize. what this shows is that there are no algebraic manipulations which allow malleability)
04:46:11ageis_:ageis_ is now known as ageis
04:52:33gmaxwell:andytoshi: I believe your argument is correct. (well the top of Theorem 1 is really all I needed, your later inverted-blackbox argument struck me as maybe a little tortured, but I'm tired too)
04:55:35andytoshi:gmaxwell: thx, good to have your confidence (and that you agree the top of theorem 1 is really the heart of the matter, malleating a sig means somehow malleating the hash). i'll check it over tomorrow and clean it up
04:57:25gmaxwell:I will send flowers to your funeral after you attempt this on DSA. Schnorr is really a tidy protocol compared to DSA.
04:59:46andytoshi:lol, that's why i started on schnorr. (and it still took me many tries to find the right reduction!)
08:05:38nOgAnOo:all are welcome to join www.facebook.com/groups/pandacoin
08:18:17gmaxwell:gmaxwell is now known as Guest92156
08:23:13Guest92156:Guest92156 is now known as gmaxwell
08:42:48maaku:andytoshi: that's great news. ecdsa will be much harder, but baby steps :)
11:32:36fanquake:fanquake has left #bitcoin-wizards
11:33:45gribble:Coinjoin Status: There is no currently open session. Visit https://www.wpsoftware.net/coinjoin/ or http://xnpjsvp7crbzlj3w.onion/ to start one.
11:35:28c0rw1n:oh, this works here? Nice
12:36:16zooko:zooko has left #bitcoin-wizards
13:06:48andytoshi:i've updated the schnorr sig paper to fix some minor typos and give the attacker an arbitrary number of valid sigs to malleate. i reread the argument and i think it's correct.
13:20:52andytoshi:nsh: http://download.wpsoftware.net/bitcoin/wizardry/schnorr-mall.pdf
13:24:03nsh:thanks! :)
13:24:09nsh:how are things, otherwise, andytoshi?
13:24:31nsh:* nsh should catch up on the malleability discussion on the list
13:28:24andytoshi:nsh: things are well, a little busy. don't catch up with the malleability discussions, it's all crazy users saying crap :)
13:32:30nsh:fair point :)
13:58:11freewil:freewil has left #bitcoin-wizards
14:18:05qupop:qupop has left #bitcoin-wizards
14:27:46realazthat:sipa: ping
15:20:30poggy:Have schmorr signitures been used anywhere widely in the wild?
15:23:18sipa:realazthat: pong?
15:25:48realazthat:sipa: regarding the malleability issue,
15:26:39realazthat:I think there is a straightforward solution without resorting to any changes to the bitcoin client
15:27:14realazthat:what I do (though untested code), is store the unconfirmed transactions separately, and keep rechecking them for validity
15:27:38realazthat:if those transactions/deposits get put into a block with a new txid,
15:27:45realazthat:then the old transaction becomes invalid
15:28:02realazthat:and the new transaction is separately debited
15:28:36realazthat:this works, right?
15:29:50sipa:realazthat: well, whenever a transaction is confirmed, you can consider it valid
15:30:00sipa:realazthat: and that can change, even go back from confirmed to unconfirmed
15:30:11sipa:realazthat: the question is when do you consider unconfirmed transactions valid
15:30:18sipa:a/valid/active/ is perhaps a better term
15:30:45realazthat:sipa: erm yeah maybe a bad choice of terminoloy
15:31:05realazthat:I consider a tx pending if it has < required_confirmations
15:31:18realazthat:and debited if it has >= required_confirmations
15:31:27realazthat:what I should have said
15:31:44realazthat:I keep all the outblock-transactions separately
15:31:59realazthat:and recheck their confirmations every heartbeat
15:32:21sipa:as long as you're able to return confirmed transactions back to the unconfirmed set
15:32:22realazthat:and change their status to invalid if their confirmations are 0, which would un-debit them
15:33:06realazthat:sipa: I am making a huge flowchart of how to do it right
15:33:13realazthat:heh its pretty complicated
15:34:52sipa:i think you're making it hard for yourself
15:35:17sipa:just have a set of all wallet transactions, consider them active if they're sufficiently confirmed, don't if they're not
15:35:30sipa:the only issue is when to consider unconfirmed transactions active
15:35:50sipa:either never, or in a way to guarantees that no two conflicting unconfirmed transactions are counted active at the same time
15:36:48realazthat:sipa: if you want to handle forks graciously as well
15:37:05sipa:yes, it does that
15:37:17sipa:(just know that transaction can go back from confirmed to unconfirmed)
15:37:38realazthat:if they are part of a block, I check the blocks, not the transactions individually
15:37:48realazthat:if they are out-of-block, I recheck them individually
16:21:49OneFixt_:OneFixt_ is now known as OneFixt
17:55:14maaku:wow error correcting codes are complicated...
20:21:34phantomcircuit:gmaxwell, 419592.092360 Gh/s
20:21:44phantomcircuit:pretttty sure the cgmienr reporting is broken on this box
21:00:09zooko:zooko is now known as zooko-standup
21:17:48zooko-standup:zooko-standup is now known as zooko
22:02:36gmaxwell:File hash to allow selective disclosure:
22:02:37gmaxwell:First hash the file with hmac(file,'disclosure hash') to obtain a master key.
22:02:40gmaxwell:Use SHA256(master key)=left_subkey|right_subkey to expand the master key in two keys.
22:02:43gmaxwell:Repeat this process in a binary tree manner until you have a key for every byte in the file.
22:02:47gmaxwell:Now for every byte in the file compute hash sha256(byte_n||key_n).
22:02:49gmaxwell:Arrange these values in a tree. The root of the tree is the hash of the file.
22:02:53gmaxwell:This is functionally equal to a normal hash of a file.
22:02:55gmaxwell:The magic is that you can now reveal any byte or range of bytes in the file,
22:02:59gmaxwell:without revealing anything about the others: select your range, disclose
22:03:02gmaxwell:the master keys which are relevant to those ranges and no others, disclose
22:03:06gmaxwell:the data, and disclose the paths connecting the data back up to the root.
22:03:40petertodd:gmaxwell: bit ahead of you: https://github.com/opentimestamps/opentimestamps-server/blob/master/doc/git-timestamps.txt
22:04:01petertodd:the tricky part is avoiding leakage of info about the length of the file
22:06:17gmaxwell:how do you propose avoiding people brute forcing the adjacent bytes if you are commiting one byte at a time?
22:07:11petertodd:gmaxwell: with a master key of course
22:07:18petertodd:(did I miss that detail in my writeup?)
22:07:25petertodd:haven't read it for like a year now...
22:08:09gmaxwell:yea, I think you did, or it's not clear!
22:08:39petertodd:your writeup is certainely more clear! re-reading it it looks like I kinda skipped a detailed explanation of the easier part of the problem...
22:09:11gmaxwell:also my 'master key' is derrived from the file, so no extra nonce needs to be stored and its determinstic.
22:09:54petertodd:gmaxwell: ah, looking at my notebook I had a deterministic nonce, but I think you deserve that one :)
22:10:27petertodd:gmaxwell: one issue with a deterministic nonce is having to scan the file twice - I also had a nonce based on the prior contents of the whole file, rathe than just the hash of the whole file directly
22:10:55gmaxwell:you could do that, but then the proof becomes huge.
22:10:56petertodd:obviously the first bytes pose an issue there...
22:11:20petertodd:no, you just provide whatever the state of that nonce is with your proof
22:12:48petertodd:I mean, that's how my length-hiding version of it works: use the state to figure out how to hide the lgnth of the tree, byte by byte
22:13:29petertodd:(or put another way, deterministically generate some amount of padding from the state nonce, and hash that and the next byte)
22:15:04gmaxwell:if you can play that forward without more data, how do you avoid someone continuing to play it forward? to be clear, the proof in my scheme, if you send, say, the second half of the file (of a power of two lengh) requires sending the data itself, the range, and two sha256 hashes in the proof.
22:16:02petertodd:right, playing it forward is an issue; you can handle that by hashing in both directions, so to speak, so that you need the both directional state nonces.
22:16:08petertodd:doesn't work well with pipes obviously...
22:16:51petertodd:at least the "play it forward" technique doesn't let you play it infinitely forward, as the brute-forcing effort becomes difficult, but it is ugly
22:17:10gmaxwell:but if you use two directional noncese and I show you a byte at the front and a byte at the end, you can merge the two to get the whole file.
22:17:52gmaxwell:I don't have that problem, because I use a tree structured nonce.
22:18:12gmaxwell:so my proof will never be more than constant*log2(length)
22:18:17petertodd:of course, which is a ui issue; the only way past that is to use use a stream cipher and provide the XOR data
22:18:21gmaxwell:(+ data)
22:18:34gmaxwell:and I have no risk of leaking more data if you merge proofs.
22:18:50petertodd:hmm... actually, I'll agree that's an improvement over my technique as written; modulo is the issue of proving length of file
22:19:02gmaxwell:yea, well you could always pad up.
22:19:04petertodd:though maybe my PRNG padding concept could be applied to the tree too
22:19:14gmaxwell:doesn't even need to be PRNG, it could just be zeros.
22:19:23gmaxwell:you'll just never reveal that part.
22:19:29petertodd:no, the PRNG is to determine the length of the padding
22:20:05gmaxwell:in any case I didn't see a reason to hide the length.
22:20:33petertodd:well, sometimes length is useful info, sometimes not
22:20:51gmaxwell:I think the best you can do is obscure it, you can't make it totally unknown.
22:21:02petertodd:right, you can make it unknown within some well-defined range
22:21:47gmaxwell:I'd just assume always pad up to the next large power of two or something.
22:22:46petertodd:more padding == more computation anyway
22:29:52petertodd:hmm... you could do a hybrid scheme, where your tree thing is used for each, say, 1MiB block, but with a incremental nonce based on the concents of all the file. forces the attacker to brute-force a whole block
22:37:05gmaxwell:I don't see why you would need to, what I suggested already requires the smallest possible amount of communications, I think.
22:38:06petertodd:I'm thinking from an implementation point of view - having to potentially buffer gigabytes worth of data in a cat file | treehash scenario is ugly
23:26:38gmaxwell:I cannot believe this argument (second from the bottom): https://github.com/bitcoin/bitcoin/pull/3656
23:28:11phantomcircuit:gmaxwell, :/
23:28:33phantomcircuit:i actually thought that's how it worked all along
23:28:44phantomcircuit:that sentence was terrible
23:29:12gmaxwell:How what worked all along? if they were reusing the inputs they'd have no theft risk (except via social engineering or the like)
23:29:19gmaxwell:(causing them to not reuse the inputs)
23:29:28maaku:gmaxwell: you mean Tux's? (comments are coming fast)
23:29:33phantomcircuit:gmaxwell, i mean that's how i thought it worked like 6 months ago
23:29:37gmaxwell:yea tux.
23:30:45gmaxwell:reusing the inputs has the negative effect that bc.i will show a nasty double spend warning and no node that has accepted the original will accept the reissue, which indeed, is a bummer. This doesn't make it acceptable to do anything else.
23:31:18phantomcircuit:gmaxwell, especially when there are pools that would replace the first with the second
23:31:50gmaxwell:can some other people go and throw in some "you cannot do this" so it's not just me vs magical tux. I am already terrified that he's trying to deflect legal risk at me personally.
23:33:03sipa:gmaxwell: i'm not sure it's on topic there
23:34:11sipa:though he seems to disagree with the reissuing using the same inputs (his argument his basically just "it's hard", not "it's wrong"), the pull request is about the ntxid
23:34:43gmaxwell:if people are going to promote ntxid as a way to reissue then it is really dangerous.
23:34:50sipa:i agree
23:34:51qwertyoruiop:gmaxwell: is magicaltux for real?
23:34:55sipa:but i don't see anyone do that
23:35:18gmaxwell:My reading of MT there was that he was doing exactly that by arguing how hard reissuing correctly is.
23:35:43gmaxwell:he also argued in the private disaster recovery channel that these ID's _completely_ solve the problem he had.
23:36:49qwertyoruiop:i'm no bitcoin wizard but it's a pretty straightforward concept.
23:37:10ironzorg:this channel is only for bitcoin wizards man
23:37:14ironzorg:what were you thinking
23:37:23qwertyoruiop:* qwertyoruiop hides
23:37:28phantomcircuit:gmaxwell, even worse than that ntxid can be the same for logically identical transactions
23:37:46sipa:phantomcircuit: ... that's the purpose?
23:38:08phantomcircuit:er i meant logically distinct
23:38:23phantomcircuit:rare case that the outputs are identical
23:38:25sipa:can you give an example?
23:45:08phantomcircuit:sipa, am i wrong?
23:45:18phantomcircuit:that's totally possible
23:45:50sipa:everyrhing except input scriptSigs is hashed
23:46:52Emcy:how can he direct legal risk at you for his company
23:47:13Emcy:bitcoin licence has all the disclaimers and shit right
23:47:51phantomcircuit:sipa, ah right so im being stupid, the txin prev outpoint would guarantee ntxid to be unique
23:48:39phantomcircuit:sipa, so someone could still change the transaction version to get a mutated transaction with a new ntxid?
23:49:17phantomcircuit:no that would change the signature value
23:49:19phantomcircuit:ignore me
23:49:22phantomcircuit:brain isn't working
23:50:46maaku:is this disaster recovery channel somewhere I need to be?