--- Log opened Sat Nov 02 00:00:49 2013
07:17 < adam3us> can you do the opposite of timelock >= time ie timelock < time for an offline time-limited offer?
07:18 < adam3us> (other than using online update to retract the offer by sweeping the funds off the contract txout at the expiry time)
08:17 < sipa> adam3us: bitcoin transactions are pretty intentionally designed to be non-retractable
08:17 < sipa> once valod, always valid
08:17 < sipa> so they can enter a mempool, and later a block, without breaking dependencies afterwards
08:24 < adam3us> sipa: but they are sometimes updateable, and first-spend invalidates later spends (even if the later spends were constructed earlier just not sent to the network)
08:27 < adam3us> sipa: (when sequence is not UINT_MAX), so I guess you could implement a time-limited cheque by giving someone the cheque and yourself spending the txout it relies on if they do not before the time-limit; however bitcoin network doesnt help you
08:29 < adam3us> sipa: eg think of an option as a smart-contract (the right but not the obligation to exercise), it has a time-limit
08:32 < adam3us> sipa: maybe one can use timelock on the non-exercise address, and sequence to allow update; the update is to take the funds, and its the option seller (writers) job to reclaim the funds after expiry, but the timelock prevents him reclaiming the funds early (undermining the buyers right to exercise during the validity period)
08:34 < adam3us> (unrelated) in script hash addresses if someone can find two scripts that has to the same string, thats a problem right?
08:35 < adam3us> eg I could find addr1=RIPE160(SHA256(SIG(a) and y=H(x))) and addr2=RIPEMD160(SHA256(SIG(b)))) where addr1=addr2 is a full birthday collision then I can cheat all those protocols that rely on inter-locked necessary revealing of x to claim
08:37 < adam3us> and I think I can do that for cost O(2^80) which is significantly below the normal bitcoin target of O(2^128), though still above the hashrate - each mine hashcash-sha256^2 is about O(2^62) per 10mins but a big bet in a few years with O(2^70) hashrate and faster miners… O(2^80) is the weak point
08:51 < gmaxwell> "Based on this reasoning, we are planning to go forward with a draft SHA3 FIPS with all the n-bit fixed hashes having capacity = 2n, thus providing n-bit preimage resistance"
09:03 < sipa> adam3us: is a collision enough?
09:03 < sipa> you want at least one of the scripts to be spendable, and the other is not undet your control
09:03 < sipa> sounds more like a constrained preimage to me
09:04 < sipa> just having two scripts, and sending to one and spending by thebother doesn't gain you anything
09:24 < adam3us> gmaxwell: spectacular… that makes SHA3 usable without tweaks for bitcoin hashcash-SHA3 if needed in the future
09:25 < adam3us> sipa: the thing is many of the interlocked protocols like atomic swap, coinswap, iddo/my fair-coin toss rely on this property
09:27 < adam3us> gmaxwell: I hope I did my bit in disabusing Kelsey of the idea, of gaining a tiny % perf for introduction of sqrt(n) attack on preimagine on the crypto list :) but i think the feedback was loud and wide
09:27 < sipa> ah
09:28 < gmaxwell> adam3us: I don't think they do require that property. Like sipa said, having a collision that can't be spent is harmless, since it can never show up in the chain, and thus can't prevent the one that can be spent.
09:28 < adam3us> https://bitcointalk.org/index.php?topic=323443.msg3463719#msg3463719
09:29 < adam3us> gmaxwell: i am talking about two spendable inputs, one bypassing the y=H(x) preimage interlock
09:29 < gmaxwell> adam3us: yes, sure, but thats not a free collision. The collision must be constrained to be spendable. This means it's harder than 2^80. I'd hard to say exactly how much harder.
09:29 < adam3us> gmaxwell: well two script versions basically with the same p2sh output, which you as a participant in an interlocked protocol have incentive and opportunity to create
09:30 < gmaxwell> er s/I'd/It's/
09:30 < adam3us> gmaxwell: there are lots of candidate inputs > 2^80, adnd they are no harder to create than random ones
09:31 < gmaxwell> adam3us: Random scripts are overwhelmingly invalid.
09:31 < adam3us> gmaxwell: its a pure brute force play
09:31 < adam3us> gmaxwell: yeah who said random: just create H(s_i) for i from 1 to a trillion, generate s'_j) for j from 1 to a trillion, store in efficient hash table, repeat
09:32 < gmaxwell> adam3us: sure, I understand. It's a multi-collision with 1:{huge number of targets} so it's closer to 2^80 than 2^160, agreed.
09:32 < adam3us> gmaxwell: where s'_i can spend s_j without needing to know y=H(x), the interlock falls apart if that can be setup before the bet
09:33 < adam3us> gmaxwell: yes, the main thing that makes it more than 2^80 is probably its sqrt(pi/2)*2*2^80 = 1.25*2^81; but realstically the TMTO need makes it > O(2^80) cos you dont have an efficeint way to store that even with bloom filters nor skip tables (as there is no sequence you can use)
09:34 < gmaxwell> In any case, I'd expressed sadness before that we'd specialized P2SH too far, and made it not able to use the 256 bit hashes we have in script.
09:34 < gmaxwell> For coinswap your attack doesn't quite work, because the preimage interlock never needs to be in P2SH.
09:35 < adam3us> gmaxwell: i think p2sh addresses are different serialization than pub key addresses right? otherwise you could bypass it and make AH(Q_i) == AH(s'_j)
09:36 < adam3us> gmaxwell: (where AH=addr-hash(z) = RIPEMD160(SHA256(z))...)
09:36 < gmaxwell> adam3us: you couldn't possibly confuse them, no.
09:37 < gmaxwell> Cute attack: http://7habitsofhighlyeffectivehackers.blogspot.ca/2013/11/can-someone-be-targeted-using-adobe.html
09:39 < adam3us> gmaxwell: what no salt? ;)
09:40 < adam3us> gmaxwell, sipa: but also for my understanding, its optional to use P2SH, you can instead serialize the script in the transaction right? thats another generic work-around (if you care about O(2^80) + TMTO yet)
09:40 < gmaxwell> adam3us: a lot of places "salt" their passwords by adding the name of their site to the hash. :P (because they misunderstand the purpose of salt)
09:40 < sipa> adam3us: P2SH is optional indeed
09:40 < sipa> adam3us: but using it has some advantages regarding size of the UTXO set
09:41 < gmaxwell> adam3us: One of the malleability workarounds I gave requires using p2sh, alas.
09:41 < gmaxwell> (It uses p2sh to make the transaction the attacker would need to mutate indistinguishable, so they'd have to try to mutate all transactions)
09:42 < gmaxwell> But e.g. for coinswap you'd only need to do that for the inital escrows, and the 2^80 attack is irrelevant there.
09:43 < gmaxwell> the hashlock releases don't need to be p2sh.
09:43 < adam3us> gmaxwell: well one defense is if you have 2^80 you have more profitable thing sto do with it: mine
09:44 < adam3us> gmaxwell: but maybe as a component of high stakes poker, if done like the fair-coin-toss with a multi-million pot, maybe if you can precompute something
09:45 < adam3us> gmaxwell: of course the other players should chose their interlock signature keys 1hr before the game
09:47 < adam3us> sipa, gmaxwell: i was wondering about a generic p2sh kind of defence, like in hashcash version 0 it was to find a 2nd preimage to a fairly chosen image, ie find h=H(s,x) and h'=H(s,x,c) where h'/2^(n-k)=h/2^(n-k) ie k leading bits of h and h' match the target 0 string came later as a suggestion from Hal Finney and another guy
09:48 < adam3us> sipa, gmaxwell: so maybe there is a way to force the brute force to work on full preimage and not birthday via the structure of the p2sh calculation
09:49 < gmaxwell> adam3us: sure, you can make life linearly harder by using a 'vanity p2sh address'.
09:50 < adam3us> gmaxwell: as is its yet-another-consideration for the catalog of how-to safely use things (eg dont use p2sh for hashlock)
09:51 < gmaxwell> adam3us: I don't think you can say don't use p2sh for hashlock. But, certantly, you should understand the tradeoffs.
09:52 < adam3us> adam3us: yes, its another place to think about the use-case and think is it strong enough for the time-frame what are the incentives; i think its nicer to say its bullet-proof, knock yourself out for a building block
09:52 < gmaxwell> e.g. if you make the guy that will provide H(x) for the hashlock do so before the public key(s) in the hashlock script are generated, then can he can't search for a p2sh.
09:53 < adam3us> gmaxwell: are you sure? the network doesnt care what you agreed offchain, just that the spender can provide s' st AH(s') = addr, and provide inputs that make s' return true
09:54 < adam3us> gmaxwell: so that only applies to inputs already on the blockchain (i think coinswap does 4 block chain tx, so that maybe the case)
09:55 < adam3us> gmaxwell: eg lets say p2sh = RIPEMD160-128(y=SHA256(s))||y[0..31]
09:55 < adam3us> 128-bit truncate, and expose 32 bits from the inner hash
09:56 < adam3us> gmaxwell: not though hard about but that might screw over the birthday attack… that kind of direction anyway
09:56 < adam3us> gmaxwell: otherwise just 256-bit script hash fixes...
09:56 < gmaxwell> adam3us: You are going to pay to   {something} + preimage of HX.    You are concerned that if the provider of HX gives you the p2sh address for "{something} + preimage of HX" he'll know another p2sh script that lets him redeem without revealing HX.
09:57 < gmaxwell> adam3us: if you say "Tell me HX, I'll tell you the {something} and we'll use that" then the attack doesn't exist.
09:57 < gmaxwell> (under that kind of protocol, at least)
09:57 < adam3us> gmaxwell: i guess HX better be 256-bit hash output also (yes)
09:58 < adam3us> gmaxwell: err no its irrelevant for hashlock if the committer knows two preimages… if either is shown, the other party can unlock with it...
09:58 < gmaxwell> adam3us: doesn't actually matter!
09:58 < gmaxwell> yep.
09:58 < adam3us> gmaxwell: right
09:59 < gmaxwell> well for hash interlock, it matters for some other things.
09:59 < gmaxwell> E.g. it matters for this one: https://en.bitcoin.it/wiki/User:Gmaxwell/why_hash_locked
10:04 < adam3us> gmaxwell: btw i think the above p2sh = RIPEMD160-128(y=SHA256(s))||y[0..31] doesnt work… probably just screen for 32-bit match then O(2^32)*O(2^64)=O(2^80), the only solution i see is a bigger hash
10:05 < adam3us> maybe you can create for similar cost two public keys Q, Q' AH(Q)=AH(Q') and do some mischief to some other script assumptions, eg an expensive way to create signature malleability
10:10 < gmaxwell> adam3us: yea, thats what I meant by a linear cost increase by using a vanity address. Cute idea to use inner agreement.
10:12 < adam3us> gmaxwell: if you revealed RIPE160(y=SHA256(s))||y[0..31] i think that'd do the trick :) and actually its smaller than using 256-bit output
10:13 < adam3us> gmaxwell: (right idea, wrong parameters a few up)
10:14 < adam3us> gmaxwell: kind of like a 2nd, inner, address checksum
10:55 < adam3us> gmaxwell: about coinSwap you mentioned blind sigs but is that necessary?  if each user connects using tor to submit the new address he'd like, and then all users only sign the n of n if their undisclosed but self-chosen address is in the output?
10:59 < adam3us> gmaxwell: starting to have doubts about RIPE160(y=SHA256(s))||y[0..31] isnt that a blackbox 196-bit hash and so attackable with O(2^88).. ignoring the validation method (to check last 32-bits are coming from the inner hash) - its generically blackbox birthday attackable surely!
11:12 < gmaxwell> adam3us: where did I mention blind sigs?
11:12 < gmaxwell> you mean coinjoin.
11:13 < gmaxwell> The reason you (may) need blind sigs is to prevent denial of service attacks. If you do as you describe a trouble maker can continually jam any join operation at basically no cost.
13:32 < adam3us> gmaxwell: no i meant coinswap "It's possible to construct cryptographically-blinded CoinJoins where _no one_ learns whose output is whose (except for each output's owner). CoinSwap results in the participants knowing the linkage."
13:36 < gmaxwell> adam3us: ah, in the coinswap I was comparing to coinjoin. My response applies. :) The reason you (may) want to use blind signing in establishing coinjoins is so you can figure out who is DOSing the join so you can ban them.
13:37 < adam3us> gmaxwell: ah.. duh that was a cross ref to coinjoin, and not coinswap per se
13:50 < gmaxwell> adam3us: the coinswaps are inherently 2-of-2, and so they can't be internally blind (the players still know that the coins are linked).
13:50 < gmaxwell> e.g. you don't know anyones IPs, but you know the connection between this coin and that coin that the swap is intended to conceal.
14:23 < adam3us> gmaxwell: but isnt the coin n of n general case?
14:28 < adam3us> gmaxwell: i was thinking (after coinjoin, before coinswap) that maybe you can p2p coinswap (but didnt get around to trying to figure out how) but that maybe you can chain it, so you get your recipient involved, and you dont learn their address, yet your signature approves it
14:28 < gmaxwell> yes, it should be chainable, but your probablity of failure goes up, and I'm not sure that you can identify the cause of the failure.
14:37 < adam3us> gmaxwell: well eg so in coinjoin A enlists C's help to pay B but A learns B's address.  if C was doing this for multiple users in parallel I was thinking maybe A can blind sign B's payment address, and to th extent there are multiple parallel protocol runs there would be an anonymity set
14:39 < adam3us> gmaxwell: but the hashlock value X being chosen by B and disclosed as part of the payment completion links the payments; however perhaps if C could choose X and use the same X for all the parallel protocol runs unlinkability within the anonymity set could be restored
14:54 < adam3us> gmaxwell: btw (reading coinjoin about zerocoin problems) "Uses an accumulator which grows forever and has no pruning" I think accumulator is fixed size, just 3072-bits.  The users just have to run full nodes and keep updating w_j=g^(x_1*…*x_{j-1}*x_{j+1}*..>*x_n), (omitting x_j which is theirs) so they can prove w_j^x_j==A mod n
14:55 < adam3us> gmaxwell: (but the rest of the critiques I agree, its impractically inefficient)
15:00 < amiller> adam3us, it's not the accumulator which grows unbounded
15:00 < amiller> it's the list of spent serial numbers
15:01 < amiller> you literally have to check a list of serial numbers that have already been spent every time
15:01 < adam3us> amiller: thats true, I expect thats what Greg meant presumably
15:01 < amiller> you can put them in an ever growing tree but eh
15:08 < gmaxwell> Indeed, thats what I mean there. I didn't actually mean the RSA accumulator, I chose my words foolishly. :)  Just that it has an evergrowing database that you can't forget until all the coins are out.
15:08 < gmaxwell> (and if you don't have a way to close off adding new coins, never.)
15:09 < gmaxwell> there are ways around it, e.g. have accumulator's which must have all their coins removed by height whatever or they're forever unrecoverable.
15:10 < gmaxwell> In any case, I wasn't trying to pan zerocoin only highlight that there were non-trivial costs: that its not magic.
20:03 < HM2> hmm NIST reviewing their crypto process
20:03 < HM2> good news i guess
--- Log closed Sun Nov 03 00:00:14 2013