00:07:13 | gmaxwell: | sipa: http://0bin.net/paste/avMPb2XvTDNid2zr#vK6LPkvNauP7RGCrCmsd6Ek04W4hpNn3R16kxjuoRbE= this is roughly what I'm talking about for OP_CHECKLOCKTIMEVERIFY |
00:07:41 | gmaxwell: | (actually deployment would need to be just slightly more complex because of the need to safely do the soft fork.) |
01:11:23 | amiller: | so the worst thing about the hash-value-highway scheme i think |
01:11:40 | amiller: | is that for only 2x the expected amount of work, you can make a chain that is really time consuming to check |
01:11:43 | amiller: | and never has any back links |
01:11:59 | amiller: | er, has only "back" links and no "up" links |
01:22:36 | HM: | How on earth would one negate an unsigned 64 int in C or C++? |
01:22:50 | HM: | (assuming it's in range) |
01:23:57 | HM: | you can safely cast to int64 if it's less than INT64_MAX, but if it's equal to -INT64_MIN (9223372036854775808) you can't do that |
01:25:03 | copumpkin: | negate? |
01:25:08 | HM: | * -1 |
01:25:15 | copumpkin: | but, uh |
01:25:27 | amiller: | what do you mean by "in range" then? |
01:26:07 | HM: | an unsigned value between 0 and -INT64_MIN, inclusive |
01:26:30 | zooko: | Hm. |
01:26:34 | copumpkin: | ah, so you want UINT64_MAX - x? |
01:26:59 | HM: | errm, no |
01:27:51 | HM: | Say you use Boost numeric_cast (a range checked cast), you can narrow the lower half of unsigned 64bit values between 0 and INT64_MAX, then just multiply by -1 |
01:28:21 | HM: | but if the value you have is -INT64_MIN, you can't do that because +INT64_MIN isn't representable as a signed 64 bit int |
01:29:09 | HM: | but you still want to be able to do that because INT64_MIN is a perfectly good signed 64bit value |
01:29:51 | HM: | so it's a special case, seems kind of inelegant |
01:31:17 | copumpkin: | I guess I'm just looking for a mathematical spec of what you actually want it to do. Pretend UINT is an unbounded nonnegative integer and INT is a general integer, and you were giving a mathematical expression for what you want to happen to the input. To start with, negation isn't defined on nonnegative integers :) |
01:32:03 | copumpkin: | or maybe I'm just being thick and everyone else understands what you're getting at :) |
01:45:54 | HM: | copumpkin, you have an unsigned 8 bit value, x, between 0 and 128. your machine has only 8 bit signed and unsigned 2s compliment integers. you want the value of -1 * x as a signed 8 bit integer between -128 and 0 |
01:46:00 | HM: | how do you do it? |
01:46:29 | copumpkin: | oh, I see, I thought you were trying to stay within the uint type! |
01:46:36 | HM: | no of course not |
01:46:38 | copumpkin: | I know how two's complement works :P |
01:46:48 | copumpkin: | but you can see why I reacted strangely to it now :P |
01:51:13 | HM: | afaict you have to do something like: if (x == 128) return -128 else if (x < 128) return -1 * (int8_t) x; |
01:59:52 | copumpkin: | actually |
02:04:03 | copumpkin: | I think it just works |
02:04:17 | copumpkin: | if x == 128 |
02:05:45 | copumpkin: | (int8_t)x = -128 |
02:05:49 | copumpkin: | and negating that is -128 still |
02:05:57 | HM: | it will in C for chars, because any operation promotes anything less than an int to an int |
02:06:36 | HM: | it won't work for 64bit types |
02:12:29 | copumpkin: | my point is more that negate on SOME2'SCOMPLEMENT_MIN leaves it untouched |
02:13:45 | HM: | bitwise yeah |
02:14:02 | HM: | so it's a special case, because all the other values, except 0, change |
02:14:09 | copumpkin: | yeah |
02:24:00 | copumpkin: | yeah, so err |
02:24:21 | copumpkin: | it just works for me :P |
02:26:21 | copumpkin: | I'm sort of confused now |
02:26:26 | HM: | it doesn't work |
02:26:45 | HM: | int64_t i = 9223372036854775808ull; |
02:26:56 | HM: | i will be -9223372036854775808 |
02:27:02 | HM: | but that's undefined behaviour |
02:27:17 | copumpkin: | then do it bitwise in unsigned space? |
02:27:20 | HM: | then you multiply by -1, and you still get -9223372036854775808 |
02:27:25 | HM: | but that's also undefined behaviour |
02:27:56 | HM: | copumpkin, you still have to check for the edge case, i think |
02:27:59 | copumpkin: | why? |
02:28:13 | copumpkin: | we know the two's complement math works out, so just do it by hand if you're afraid of undefined behavior |
02:28:16 | HM: | because taking the 1s compliment and adding 1 results in the same thing |
02:28:33 | copumpkin: | no? |
02:29:33 | justanotheruser: | You just have accept that 9223372036854775807 + 1 = -1 |
02:29:42 | HM: | doing a memcpy is technically undefined behaviour as well |
02:29:49 | copumpkin: | ~0x8000000000000000 + 1 = 0x8000000000000000 |
02:32:41 | copumpkin: | anyway, I'm not really sure what the problem is anymore. If you're working in pure two's complement space, just casting and negating works |
02:34:20 | HM: | it really doesn't |
02:34:34 | HM: | because the compiler is allowed to assume signed integers never over or underflow |
02:35:03 | copumpkin: | but I was just suggesting doing it in unsigned space and converting at the last minute |
02:35:10 | copumpkin: | so you don't need to rely on that |
02:38:52 | HM: | umm.... ~128 = 127 + 1 = 128 |
02:39:01 | HM: | you then do what? |
02:39:06 | HM: | casting to signed is undefined |
02:39:55 | copumpkin: | *(int64_t*)&x, where x is my bitwise-negated uint64_t |
02:39:57 | copumpkin: | :P |
02:40:15 | HM: | you can do a memcpy or a type pun, but it's still technically undefined. |
02:40:27 | copumpkin: | well then I don't know what to tell you. You either have two's complement or you don't |
02:40:38 | copumpkin: | if you can't assume the representation of a number you can't do much |
02:40:54 | copumpkin: | I don't really care if it's technically undefined. It'll work on all computers |
02:41:04 | HM: | ;) |
02:41:24 | copumpkin: | but seriously, if I can't convert between representations you're pretty much forcing me to put a conditional in there |
02:41:33 | justanotheruser: | What do you guys not like about Bitmessage? I think it's interesting, but the only flaw I've noticed that they haven't successfully addressed are the flaws in using hashcash |
02:41:35 | copumpkin: | because it's undefined to call it on a larger number |
02:42:51 | HM: | copumpkin, yep, i believe a branch is the only portable way of strictly doing it |
02:44:45 | HM: | never compile anything with -Weverything |
02:44:58 | HM: | it'll make you want to give up |
02:45:08 | copumpkin: | it complains about my solution? |
02:48:00 | HM: | I'm pretty sure if you use a C cast the compiler will let you do just about anything |
02:48:38 | HM: | in C++ you can't do a reinterpret_cast from a signed to an unsigned type, C cast is about the only thing that works unless you go via a pointer |
02:52:36 | Snowleaksange: | you want a (signed integer <-> unsigned integer) transform that preserves sort order? |
02:52:55 | HM: | sort order? :S |
02:55:06 | Snowleaksange: | unsigned 0000 < 0001 < 1110 < 1111, while signed 1110 < 1111 < 0000 < 0001 |
02:55:26 | Snowleaksange: | maybe misunderstood question |
02:56:12 | copumpkin: | a functor from the canonical uint64_t preorder category to the canonical int64_t preorder category |
02:56:13 | copumpkin: | * copumpkin runs |
03:00:27 | Snowleaksange: | i once used a mapreduce framework that only supported unsigned integer maximum value tracking, so used bit transforms to track min/max floats, signed ints, etc |
03:02:28 | Luke-Jr: | writing standards-compliant code is not that hard -.- |
03:05:49 | Snowleaksange: | the standards compliant way to bitcast is memcpy() |
03:05:55 | jgarzik: | Luke-Jr, bwahahahaha |
03:06:05 | Snowleaksange: | http://code.google.com/p/stx/source/browse/trunk/stx/bit_cast.hpp?spec=svn25&r=25 |
03:14:15 | HM: | its easy to write standards compliant code when the standard doesn't specify what should happen |
03:16:04 | Luke-Jr: | I didn't say it was easy, I said it wasn't that hard. :P |
03:24:40 | HM: | Ah well, time for bed. thanks for the brainstorming |
03:24:47 | Guest26727: | Guest26727 is now known as roidster |
03:25:02 | HM: | Anyone looking in to writing a parser should look at Reagel btw. I started playing with it today, it's awesome |
03:25:27 | HM: | Ragel even |
03:26:22 | HM: | Generates pretty state diagrams right from your code |
03:47:40 | larslarsen: | so I have an idea to avoid alts from getting difficulty-jacked |
03:48:44 | larslarsen: | if you do validation as POW as the nodes validate, they can secure a second chain, which secures nothing. The miners have the real chain, the nodes mine a second chain, which is just a bare block header chain |
03:49:00 | larslarsen: | with an extremely short block time, like a heartbeat |
03:49:40 | larslarsen: | then when a given number of hearbeats come in, you recalculate the difficulty on it, and if you notice a major discrepency in the number of confirmations you should see in bitcoin in that time, recalculate it |
03:49:44 | larslarsen: | or altcoin or whatever |
03:50:40 | larslarsen: | boom... time traveler is stuck with the difficulty everyone else has |
03:51:44 | larslarsen: | network functions long enough to recalculate and will start processing real blocks much much sooner, just like if someone designed a magical sliding window timestamp consensus magic armwave |
03:52:43 | larslarsen: | but this is an atomic block, and timescales should be very accurate too |
03:53:47 | larslarsen: | you could alternately produce ZKPs in this chain as well |
03:53:56 | larslarsen: | just because nodes are good for that stuff |
03:54:30 | larslarsen: | and of course, its just rolling, you discard the end of the chain |
03:54:38 | larslarsen: | and tiny super small |
03:56:23 | larslarsen: | I call it chain insecurity consensus. Yup, this still secures nothing. At the rate it should! |
06:15:41 | gmaxwell: | larslarsen: p2pool also uses the wedge to bitcoin to prevent time travling reorgs. |
06:16:03 | gmaxwell: | though it still doesn't prevent isolating someone and mining their difficulty down in realtime. |
06:48:10 | nOgAnOo: | nOgAnOo is now known as noganoo |
06:49:26 | noganoo: | noganoo is now known as nOgAnOo |
08:18:24 | justanotheruser: | justanotheruser is now known as just[dead] |
09:41:53 | just[dead]: | just[dead] is now known as justanotheruser |
11:11:05 | avantgeek: | avantgeek has left #bitcoin-wizards |
11:38:43 | rdponticelli: | rdponticelli has left #bitcoin-wizards |
12:10:29 | jarpiain: | jarpiain is now known as Guest87860 |
14:21:59 | rastapopuloto: | rastapopuloto has left #bitcoin-wizards |
14:28:59 | justanotheruser: | justanotheruser is now known as just[dead] |
14:35:51 | Manfred_Karrer: | I have a question regarding malleability: Can malleability happen without malicious intention? Like due different implementation or optimization? |
14:42:07 | stonecoldpat: | i remember being told that it can |
14:42:19 | stonecoldpat: | that it just happens from time to time |
14:43:25 | roidster: | roidster is now known as Guest97452 |
15:31:27 | Ademan: | Manfred_Karrer: yes it can, but it requires some sort of intention |
15:32:08 | Ademan: | I recall gmaxwell mentioning nodes that would re-canonicalize transactions before relaying them, not sure if that was a hypothetical or not though |
15:36:05 | Ademan: | I'm going to lose my goddamn mind, my laptop picked today, the day of my evening midterm, to die. I have a PDF of the textbook on it and no other way to view it at school today... short of printing up an ass-ton of pages |
15:37:20 | zooko: | zooko has left #bitcoin-wizards |
16:13:23 | Guest97452: | Guest97452 is now known as roidster |
16:28:24 | maaku: | Ademan Manfred_Karrer: transactions can be mutated without any mallicious intention |
16:28:32 | maaku: | especially if they are non-canonical to start with |
16:29:17 | maaku: | it's not hard to imagine someone running custom code accidentally re-serializing transactions during relay in a way that makes them canonical or otherwise does not preserve round-trip serialization |
16:39:31 | Manfred_Karrer: | stonecoldpat, Ademan, maaku: Thanks, I was expecting that... seems to make malleability for any smart contracts depending on tx chains kind of impossible at the moment |
16:41:30 | maaku: | Manfred_Karrer: you should not be participating in any protocol which requires chaining zero-confirmation transactions, unless you are certain you can rewrite the later transactions without invalidating them |
16:41:43 | maaku: | this is, unfortunately, a serious limitation |
16:44:55 | adam3us: | Manfred_Karrer: in some cases you could wait for the first stage transaction to be confirmed before releasing the 2nd (dependent) transaction to the other party (or to the network). often they start as a multisig (so both parties have to cooperate) with a hashlock (to avoid who goes first) & a timelock (to avoid extort) |
16:45:36 | maaku: | adam3us: yes, but the changed 1st transaction would invalidate the multisig on the 2nd |
16:45:50 | hearn: | gmaxwell: did you see this? http://blog.bifubao.com/en/2014/03/16/proof-of-reserves/ |
16:46:07 | maaku: | it's a much smaller category of protocols which doesn't require signatures in advance |
16:46:09 | Manfred_Karrer: | one use-case would be to create a time-locked refund tx from a multisig, so if the other peer will no cooperate that there is a way to get back the funds. using a trusted 3rd party seems to be the only alternative yet... |
16:52:19 | gmaxwell: | Manfred_Karrer: I will have a proposal soon which will improve refunds irrelevant of malleability.. (just need to hammer out with sipa exactly what I'm proposing) |
16:53:51 | Manfred_Karrer: | gmaxwell: ah sounds great! looking forward to it! |
17:09:50 | adam3us: | maaku: yes (change 1st tx would invalidate multisig on 2nd). but party A creates multisig/hashlock/timelock broadcasts as tx1, party B waits for tx1 to be confirmed then signs its half of multisig. makes things slow, but cant malleate that which is already confirmed |
17:11:18 | maaku: | adam3us: yes, but you now have to construct the protocol in a way that doesn't fall apart if one of the parties drops out after the first confirmation (ransom/extortion) |
17:11:42 | maaku: | gmaxwell's op_maturity lock-time check helps here though |
17:13:33 | just[dead]: | just[dead] is now known as justanotheruser |
17:14:01 | adam3us: | maaku: yes. its clearly limiting. above is a slow partial work-around only. some things wont work or will consume more tx to construct and more tx to blockchain which could have stayed off block chain. op_maturity is combining a timelock and a earlier doublespend into one tx. works for that case. but still limiting for other cases. |
17:17:16 | adam3us: | adam3us has left #bitcoin-wizards |
17:18:33 | zzyzx: | zzyzx is now known as roidster |
17:19:03 | roidster: | roidster is now known as Guest11364 |
17:44:08 | larslarsen: | gmaxwell: If a surrounded node returns to the network, with a lowered difficulty (or higher) what happens to it? Obviously its blocks will not be created/accepted in either case. Can this situation be recovered from or is there some kind of +/-2h type rule for difficulty? |
17:44:47 | gmaxwell: | hm? it just gets its chain wiped out by the superior public one. |
17:44:57 | larslarsen: | I assumed as much, just making sure |
17:45:07 | larslarsen: | The failure here is in mining on useless data |
17:45:10 | gmaxwell: | which is slim consolation if its already taken irreversable action. |
17:45:20 | larslarsen: | YEs if you're sybiled you have worse problems |
17:45:24 | gmaxwell: | no the failure is that the user is now bankrupt... |
17:45:25 | larslarsen: | I am concerned about the network as a whole |
17:45:44 | gmaxwell: | No you shouldn't though, bitcoin is sybil resistant unless you go @#$@#ing with how the difficulty changes work. |
17:45:50 | adam3us: | larslarsen: nodes that are high assurance / high value (eg handling user money) should make attempts to avoid being surrounded |
17:46:14 | gmaxwell: | If you're not sybil resistant you're not secure on the modern internet. |
17:46:30 | larslarsen: | gmaxwell: I see, so sybiling some nodes could break everything. But not just with one node? |
17:46:47 | adam3us: | larslarsen: eg maintain tor link over different 3g data, dialup, short-wave whatever to double-check the leading hash-chain (just headers, doesnt take much bandwidth) |
17:46:59 | gmaxwell: | It would break everything for that node ... except that the slow difficulty updates protect it. |
17:47:21 | gmaxwell: | adam3us: larslarsen is speculating about altcoin ideas which largely undo bitcoin's inherent robustness. |
17:47:27 | gmaxwell: | (to sybiling) |
17:48:05 | larslarsen: | adam3us: I mention it because when I asked about a difficulty-jacking-attack prevention to down-calculate the difficulty based not on timestamps but on the number of blocks in a different chain in a given time, he said that p2pool uses the bitcoin heartbeat for timing, but you're still succeptable to being surrounded and have your difficulty worn down in real time |
17:48:21 | gmaxwell: | larslarsen: I thought I explained a day ago that the difficulty slowness to update is important for security to isolation, any idea how I was misunderstood there? (I ask not to pick on your understanding, communication is hard— but to refine my explinations) |
17:48:54 | adam3us: | larslarsen: oh yeah. think i skimmed that earlier. if you do an alt with weak hashrate, you lose (when someone for laughs jumps your hashrate out of your reach or does thousands double-spends before difficulty retarget) |
17:49:10 | larslarsen: | adam3us: I am a big fan of VLF radio communication of the merkle root. Its currently used to communicate with submarines and send the current time out to people's alarm clocks over the power cord as antenna |
17:49:32 | larslarsen: | adam3us: just one non-jammed ULF radio transmitter and we're all good |
17:49:41 | larslarsen: | shortwave |
17:49:50 | adam3us: | larslarsen: a use for jgarzik microsat |
17:50:30 | gmaxwell: | hm? are there actual radio recievers doing that? often the power grid is full of VLF noise and the effective antenna may only be some 100m long as it ends at the pole transformer. |
17:50:36 | larslarsen: | adam3us: his microsat is on the other side of the planet when I need it most (because attackers know where it is) and I can hear a shortwave station from anywhere on the surface of earth, and I can get like a few hundred baud |
17:51:28 | gmaxwell: | you need 1bps for bitcoin headers. |
17:51:34 | larslarsen: | gmaxwell: I didnt not hear that, I just saw the comment about p2pool using it, I thought you hadnt heard my question, netsplits yesterday from bots |
17:52:21 | larslarsen: | gmaxwell: I understand what you're saying. The issue is that in pump and dump scams, pools are the tool of choice. |
17:52:50 | adam3us: | larslarsen: say you have a side-chain that pegs its difficulty to (a low multiple) of bitcoin, its still the case that someone with a garage full of asics can wreck havoc on it, even if they cant do the terracoin ramp difficulty way up and walk away |
17:53:05 | larslarsen: | gmaxwell: I understand what you are saying though, you could seriously break the network if you can do short scale downcalcs |
17:53:22 | gmaxwell: | I think you should stop worrying about those things they are defective on many levels and it is far from clear that its possible to make them secure under a decenteralized consensus at all. |
17:54:06 | gmaxwell: | It's not worth trying to fix things that are inherently broken if doing so risks making the resut insecure if it actually does become useful. |
17:54:37 | larslarsen: | gmaxwell: I have not wasted much brainpower on it, it was an idea that occurred to me last night. I wanted you to kill it so I could stop worrying about it. But I didnt see your responses yesterday. Thank you for crushing it. I'll get back to something useful. |
17:55:13 | gmaxwell: | S'okay. :) |
17:55:50 | larslarsen: | gmaxwell: I want to test out some of your wishlist and I do not want to have people loose real money because of my messing around with features, which could attract speculators (oooh features!) |
17:56:34 | larslarsen: | gmaxwell: but I need to test in the real world eventually, and so I wanted to be prepared for what I saw as a big problem, money being frozen up/extorted/market manipulated by DDOSing a service |
17:56:48 | larslarsen: | gmaxwell: I will not worry about that, its not my problem. |
17:57:00 | gmaxwell: | then simply put an explicit 'backdoor' in your system to dicourage premature use as value. |
17:58:06 | larslarsen: | gmaxwell: I was going to make the mining worth almost nothing and follow asigmosoidal curve |
17:58:09 | larslarsen: | good? |
17:58:18 | pigeons: | heh, NXT said we are closed source, and when we release the source it will have intentional security holes, and people still bought the stuff |
17:58:51 | phantomcircuit: | pigeons, que |
17:59:28 | gmaxwell: | larslarsen: I think if I were to do bitcoin today I might have done something like a sigmoid mining function. (or e.g. a low constant mining until difficulty crossed some level) |
17:59:44 | larslarsen: | gmaxwell: I have heard other people say that |
18:00:18 | larslarsen: | gmaxwell: We would be in a better place right now |
18:00:37 | gmaxwell: | I don't really know that it matters that much due to trade. It would have been a small improvement. |
18:00:54 | larslarsen: | gmaxwell: perhaps psychologically more "fair" |
18:01:51 | gmaxwell: | right, the actual distribution would probably be similar, perhaps even more unequal since the longer ramp may have played better to people who scarfed up a bunch in trade... but it would at least sound more fair. |
18:03:01 | larslarsen: | gmaxwell: I only meant perception. There are studies on how to distribute a limited resource to a large demand "fairly" and first come first serve was seen as most fair, followed by other distribution schemes such as random, or lottery |
18:03:12 | larslarsen: | or auction |
18:04:37 | larslarsen: | I only like sigmosoidal-type curves because its a development process not just of security and code but of economy and community and it just makes sense to me to follow adoption curves |
18:04:56 | larslarsen: | but it limits your use early if you need to move a lot of money around |
18:05:30 | gmaxwell: | well there is no way to measure adoption. |
18:05:38 | larslarsen: | unless you do arbitrary precision, is anyone doing that? like the really low coinsmax ones? |
18:06:20 | larslarsen: | gmaxwell: I know. but its pretty clear bitcoin was not going to 1000 when there was no windows client :) |
18:06:37 | sipa: | "when there was no windows client" ? |
18:06:40 | gmaxwell: | larslarsen: ... |
18:06:44 | sipa: | there has always been a windows client |
18:06:45 | gmaxwell: | wtf |
18:06:54 | gmaxwell: | The original software was windows only. |
18:06:56 | larslarsen: | sipa: I just realized that was probably true after I said it |
18:07:06 | larslarsen: | sipa: *I* didnt have one, sorry |
18:07:17 | gmaxwell: | (Which is probably a major reasons why I don't own all the bitcoins. :P ) |
18:07:26 | larslarsen: | gmaxwell: lol |
18:07:33 | hearn: | gmaxwell: dude, i fixed bugs in wine early on so it ran on everything :) |
18:07:34 | oakpacific: | i got a question: suppose preimage attack against SHA256 is successful, then how easy it's to create two valid txs with the same txid? thanks |
18:07:36 | hearn: | you have no excuse :) |
18:07:42 | gmaxwell: | (because I could only run it in wine under vnc ... :)) |
18:07:59 | larslarsen: | gmaxwell: If I was a windows user I would have all the bitcoins then! :) |
18:09:08 | gmaxwell: | oakpacific: totally depends on what the 'preimage attack' requires. |
18:12:02 | larslarsen: | who knew win32 knowledge would have paid off in this world? It just goes to know you never know |
18:12:26 | hearn: | lol |
18:12:41 | hearn: | yeah, who could guess that knowing the system that powers >90% of the worlds computers would be useful :) |
18:14:16 | larslarsen: | hearn: Yes but, without the kind of zealotry that makes that thinking seem rational, we wouldnt have bitcoin. |
18:14:27 | gmaxwell: | 'computers' :) |
18:15:18 | oakpacific: | gmaxwell: let's say an attack like what we already have on MD5 |
18:15:37 | hearn: | heh |
18:15:56 | hearn: | gmaxwell: do ATM's count? |
18:16:43 | gmaxwell: | oakpacific: the md5 ones are not second preimage attacks, they're collisions that require complete control over the last ~32 bytes of the hashed data. |
18:16:54 | larslarsen: | The blood pressure machine at walmart was a dell. It was bluescreend. I unplugged it and plugged it back in. It needed a password. A blood pressure machine. |
18:17:23 | larslarsen: | you know where you sit there and it tests you for free? I am sure I trust that red button that lets me go again, thanks dell |
18:17:23 | larslarsen: | :) |
18:19:43 | gmaxwell: | You could use them to generate two valid transactions that you created both of which hash to the same thing, the lack of control of the final bytes isn't too much of an issue. But I'm not sure what generating two transactions yourself really accomplishes. Perhaps with some iteration on the attack you could make them functionally different and partition the network. |
18:20:46 | justanotheruser: | justanotheruser is now known as just[dead] |
18:20:51 | gmaxwell: | Though because we use the sha256^2 even if sha256 itself had the md5 issue, you'd be broken there. |
18:22:55 | oakpacific: | gmaxwell: thanks a lot |
18:33:17 | larslarsen: | Can an identical signed transaction appear on two networks and both be valid? Is anything other than address letters preventing this? |
18:36:59 | maaku: | larslarsen: address letters don't exist at the transaction level |
18:38:03 | sipa: | addresses in general don't exist at the protocol level |
18:38:06 | Luke-Jr: | ^ |
18:38:30 | larslarsen: | maaku: duh... ok... so I'm going to have to assume its possible |
18:38:37 | larslarsen: | maaku: unless someone can tell me why not |
18:39:24 | maaku: | larslarsen: the input txids. why would they be the same on two different networks? |
18:39:34 | sipa: | larslarsen: for two transactions to be identical, the inputs being spent must also have identical txids |
18:39:48 | larslarsen: | maaku: are they malleable? |
18:39:55 | sipa: | larslarsen: #bitcoin please |
18:40:02 | larslarsen: | maaku: this is an attacker attempting to create the same txid and body on both networks |
18:41:32 | sipa: | sipa has changed the topic to: This channel is not about Bitcoin today | "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." |
19:02:49 | petertodd: | larslarsen: that is possible, even with height-in-coinbase, but really unlikely |
19:04:57 | larslarsen: | petertodd: so if I constructed outputs carefully, I could craft inputs of my choosing? |
19:05:12 | petertodd: | larslarsen: ? |
19:05:39 | larslarsen: | petertodd: I'll take it to #bitcoin and come back when it matters |
19:05:50 | petertodd: | larslarsen: thanks |
19:08:00 | amiller: | hey so thinking out loud about how to define security for the compact SPV proofs.... |
19:08:07 | amiller: | suppose you want to check how much work has *buried* a transaction |
19:08:23 | amiller: | since that's what really matters if you're checking SPV, you're already not supposed to mine, for exmaple, based on SPV proof alone |
19:08:36 | petertodd: | amiller: yeah, not taking burying into account is bad |
19:09:03 | amiller: | so what you really want to do is make sure that there isn't a *larger* chain that *doesn't* include the transaction |
19:09:31 | amiller: | making sure you establish a path from every sample to the transaction or to a different fork point before the transaction should do that. |
19:09:54 | petertodd: | right - note how the reorg rules of tree-chains is specifically designed to make that question irrelevant |
19:10:07 | petertodd: | fork point? |
19:11:14 | amiller: | i don't think tree chains addresses this at all, we're talking about how to do compact SPV proofs and what the reuirements need to be |
19:11:25 | amiller: | if you want to do an SPV proof without even having to check all the headers but some subset of them |
19:11:39 | lawlll: | hey guys |
19:12:16 | petertodd: | amiller: I mean, it addresses it by further constraining the problem - the different parts of the chain are linked by the common root, so it's not independent in terms of ordering like pure SPV proofs are |
19:12:53 | amiller: | i don't understand what you're talking about tbh |
19:13:06 | petertodd: | maybe the same on my end :) |
19:13:37 | petertodd: | So, when you say "larger" chain, do you mean a larger chain that is a fork to the one you know about, or a larger series of blocks within the chain that you know about? |
19:14:42 | amiller: | the scenario is, i think, you have two sets of headers given to you by nodes |
19:14:49 | amiller: | one of them says a transaction is valid, the other one says it's not |
19:15:11 | amiller: | since you're an SPV node you only want to check O(log n) headers or so and you want to conclude correctly based on work alone |
19:15:33 | amiller: | informally, it's alright if the longer chain is *invalid* and you wrongly choose it |
19:15:52 | amiller: | because the attacker is assumed to have less than 50% hashpower and the honest people only mine on *valid* chains |
19:16:45 | amiller: | so what does it mean to measure the "work" of a supposed chain that might be invalid and not contain a linear sequence of things anyway |
19:17:09 | gavinandresen_: | BlueMatt: pull-tester was stuck on pull 3850, haven't looked at why. But it just failed 3893…. |
19:17:19 | amiller: | and my observation is that if the *honest* work doesn't include the transaction, then it will be impossible to follow backlinks from honest samples of work to the transaction in question |
19:17:30 | petertodd: | amiller: ah, ok, that's not what I as talking about - I was talking about the case where you don't even know that longer chain exists |
19:17:53 | amiller: | ok, yeah, that's probably still interesting and useful but just not directly related to what i'm trying to address |
19:18:26 | amiller: | baiscally i described a scheme that i think is sufficient for htis a year ago called hashvaluehighway and there's been recent interest in improving it, but i can't tell what the improvements are or in more clarity what the requirements are in the first place. |
19:18:30 | petertodd: | yeah, although it does suggest that what you are trying to address is a subset of a bigger problem... |
19:18:59 | gmaxwell: | amiller: I'm reasonably confident that it actually isn't. |
19:19:35 | gmaxwell: | I'm not sure why you're not following my point there. I really think you need to go back to the game I stated before (it works for the burried argument too, with a very slight modification) |
19:20:07 | amiller: | well where we left off yesterday, you had suggested "sequential checking" as the gold standard |
19:20:17 | amiller: | and what i asked was, what does sequential checking do when there's an invalid link in the chain |
19:20:40 | amiller: | because if sequential checking errs out when there's an invalid chain, then there's no cheaper way to do it than checking every link |
19:21:54 | gmaxwell: | amiller: It's okay if you'll accept an invalid proof with a hidden bad link in the game, so long as to create it I had to do equal or more expected hashing to the actual proof. |
19:22:13 | gmaxwell: | The game isn't just that I got you to accept trash, but that I did it with less work than creating non-trash required. |
19:22:56 | amiller: | right, so... the way around that is that if the transaction in question occurs in block B, every *sample* of work used is required to be directly connected back to B. |
19:23:27 | amiller: | is that clearly enough sufficient? |
19:24:35 | gmaxwell: | Maybe. It is but only if you only count the revealed samples, and if you do that you can't hide anything, or the real proof could be more work due to the non-sampled portions. |
19:49:54 | lawlll: | gmaxwell: how close are we to using bitcoin to solve other real world problems other than being money... ie, smart property/contracts ? |
19:50:22 | gmaxwell: | lawlll: why are you repeating the question when I answered you at some length in #bitcoin? :( |
19:50:31 | lawlll: | sorry i didnt see the answer |
19:50:33 | lawlll: | thought you forgot |
19:51:54 | phantomcircuit: | jgarzik, i just realized what is going on here, the http postbacks are being made multiple times almost immediately after the first |
19:52:15 | phantomcircuit: | that's probably going to screw up a bunch of peoples systems that dont have proper race condition handling |
19:52:40 | lawlll: | lol i hate mirc |
19:58:17 | lawlll: | oh i see it now |
19:58:20 | lawlll: | thx gmaxwell |
20:04:53 | just[dead]: | just[dead] is now known as justanotheruser |
20:13:37 | gavinandresen_: | gavinandresen_ is now known as gavinandresen |
20:35:09 | jgarzik_: | amiller, what is that storify link, again? |
20:35:19 | amiller: | oh for dakami |
20:35:20 | amiller: | one sec |
20:35:37 | amiller: | http://storify.com/socrates1024/bitcoin-pow-bet-10btc-jgarzik-vs-dakami-may-2014 jgarzik |
20:37:40 | amiller: | jgarzik, while we're on the topic of bounties though... |
20:38:02 | amiller: | i'm annoyed that ebfull made a really cool simulator and no one is explaining what is expected before calling the bounty claimed. |
20:38:21 | amiller: | https://bitcointalk.org/index.php?topic=326559.0 |
20:38:49 | amiller: | afaict kjj is waiting for you to call it |
20:50:40 | justanotheruser: | justanotheruser is now known as just[dead] |
20:50:43 | jgarzik_: | * jgarzik_ looks |
20:51:13 | jgarzik_: | amiller, no time to play and evaluate |
20:51:40 | jgarzik_: | amiller, if you tell me the bounty is satisfied, then I'm happy ;p |
20:54:32 | amiller: | jgarzik, i'm confident it's satisfied according to what you asked for in the original post - it's a general purpose framework, in addition to simulating selfish mining (it was interactive, you can click on the nodes and such, he also produced a graph), he showed a variety of other strategies like the countermeasure from the selfish mining paper |
20:55:24 | amiller: | it's not really a rush though, i'd rather wait until you browse the forum thread youreslf and at least tinker with the demo here http://ebfull.github.io/ if not the code.. |
21:00:26 | amiller: | i can't actually figure out what that simulation is doing at the beginning, it seems like no mining is simulated... i probably have the wrong link and that's just simulating netwokr formation. |
21:03:45 | adam3us: | amiller: depending on how you code it you dont need to simulate mining. i started writing one just based on probability calcs. (code org got messy so i abandoned it) |
21:04:38 | amiller: | adam3us, yeah that's true, from talking with ebfull though this was meant to be a general purpose network simulator and just got into selfish mining simulation when it became a frenzy |
21:05:14 | adam3us: | amiller: or it seemed more likely that i'd make a mistake in the probability calcs which partly reduces the use of the simulator (to be simple and reliable so you can make predictions or double check pure math predictions) |
21:05:16 | amiller: | adam3us, you don't need simulation at all, the cornell folks worked out closed form solutions to all their models |
21:06:05 | adam3us: | amiller: yep. i tend to write a simulator if i come up with some math prediction. just a sanity check before shouting "fire" :) |
21:20:26 | gmaxwell: | amiller: are these closed form solutions to models that lack things like latency? |
21:20:46 | gmaxwell: | and don't include things like variance in mining? |
21:21:04 | gmaxwell: | a latencyless network of equal speed variance free miners never converges. :P |
22:49:53 | maaku: | amiller: you seem to have some very different problem in mind for the hash-value highway than we do |
22:50:33 | maaku: | i look forward to reading your security game |
22:52:10 | amiller: | yeah my goal originally was to build something like treechains where you can set your own difficulty or at least use a lower difficulty and have a much larger number of proofs of work than you'd actulaly want to check directly |
22:52:40 | amiller: | i definitely didn't have bitcoin-backed altcoins in mind, but it still seems like the requirements (nebulous though they are at this point) are the same. |
22:53:30 | gmaxwell: | why are you saying they are nebulous at all. |
22:53:35 | gmaxwell: | It's absolutely concrete. |
22:53:43 | gmaxwell: | You have to not be able to win at that game I described. |
22:54:37 | amiller: | you still haven't answered my questions about it! |
22:54:49 | gmaxwell: | perhaps I missed them, freenode was splitting. |
22:55:01 | amiller: | your game uses terms like "Chain A" and "Chain B", but they might not actually be chains, so the question is how to handle the case when one isn't even a chain |
22:55:17 | amiller: | what i suggested most recently is that we make the game about a particular *invalid* transaction |
22:55:18 | gmaxwell: | all I'm giving you is an interlinked set of headers. |
22:55:59 | gmaxwell: | and yes, you went on a freeking tangent. The whole discussion is about SPV security, which doesn't involve transaction validation. You're trusting that the majority hashpower is doing the right thing. |
22:56:21 | amiller: | right but spv does at least involve fully verifying a chain |
22:56:24 | gmaxwell: | which reduces to being able to accurately evaluate which set of headers is the one with the most hashpower behind it. |
22:56:28 | gmaxwell: | No, it doesn't. |
22:56:38 | amiller: | so we are generalizing spv security a bit |
22:56:48 | gmaxwell: | it involves testing membership. |
22:56:56 | amiller: | sorry not fully verifying all the transactions in a chain but at least the chainliness of the proof of work is fully validated |
22:57:21 | maaku: | amiller: we are not concerned with actual connectivity |
22:57:32 | maaku: | we are trusting the majority hashpower for that |
22:57:34 | amiller: | "one with most hashpower behind it" is also too vague because some of the headers in Chain A might overlap Chain B |
22:57:53 | gmaxwell: | Right, and I suggest a scheme which allows you to fractionally verify proof of work which cannot be forged with less expected work, so the security assumption of most of the hashpower being honest is unchanged. |
22:58:09 | gmaxwell: | it might overlap but it doesn't matter. |
22:58:24 | gmaxwell: | if A+B > A+C then B>C |
22:58:42 | gmaxwell: | (at least if things are well formed) |
23:00:21 | maaku: | amiller: it's not a loss of security if you can construct an invalid (not connected) spv proof, so long as the work required to generate that proof is >= what would be required to make the chain it purports to summarize |
23:01:25 | amiller: | if you have a chain that is 10 units of work, and i make a chain that is 10.00001 units of work, mine is longer, but i hardly had to do any work to make a longer one |
23:01:44 | amiller: | that's why i'm suggesting including the fork distance in there |
23:02:14 | maaku: | amiller: why? units of work is all that matters |
23:02:36 | amiller: | yes but i only had to put in 0.000001 work to completely revise your chain, accoridng to the first defintion |
23:02:53 | amiller: | what i am suggesting as a better definition, is that if you have a chain that is 10 units of work, and i make a chain that is 10.00001 units of work, and relative to your chain, there are *5* units of work in your chain that differ from mine, then i had to do 5.000001 units of work as attacker. |
23:03:58 | maaku: | amiller: you would have had to put in 10.00001 units of work, no? |
23:04:03 | amiller: | no |
23:04:25 | amiller: | beacuse i just extended yours by a tiny or revised it by 1 block or something |
23:04:36 | amiller: | technically that's a different chain, unless you are doing what i said and considering "fork distance" |
23:05:17 | gmaxwell: | Sorry, this is incoherent. |
23:05:21 | gmaxwell: | :-/ |
23:05:40 | maaku: | amiller: it's irrelevant to any application I can think of |
23:06:12 | maaku: | the spv proof summarizes the work from A -> B (my chain) and A -> C (your chain) |
23:06:37 | maaku: | we don't care at what point they diverged, just which one has more work |
23:07:19 | amiller: | ugh, it *does* matter where they diverge |
23:08:42 | maaku: | why? I suspect we'll have to delve into applications to resolve the difference |
23:08:51 | gmaxwell: | It really doesn't. It matters how deep the thing you care about is in them, yes, but for SPV purposes you only need to identify the one with the most. |
23:12:25 | amiller: | what i'm saying is the requirement you're *saying* you want is that if the attacker has a chain A of total work N+1, and you have a chain B of total work N, then you would like the attacker to have to put in E(N+1) work |
23:13:03 | amiller: | and what i'm saying is that only makes sense if they diverge at the beginning, the only thing you should try to achieve is that if the fork distance is F units behind the front of chain B, then the attacker has to put in (F+1) work |
23:13:19 | amiller: | because it's easy to have a "different" chain that only differs in the last few blocks |
23:15:02 | maaku: | amiller: when you need that property (and you don't always), you get it by explicitly identifying the point of departure |
23:16:02 | amiller: | i'm not adding a new property you want sometimes, i'm clarifying how to interpret the only property you are aiming for |
23:16:10 | maaku: | for example with pegging, you provide a proof that the return peg connects to the original outgoing peg, and that a certain amount of work is built on top of it |
23:16:32 | gmaxwell: | I now understand what you're wrestling with but I think that it's not the right perspective. It's harmless to choose attackers chain if it's subsantivelly identical to the real one. |
23:16:51 | maaku: | then there is a quieting period where someone can step forward and provide a reorg proof showing that the return peg is not in the most-work chain - this does require identifying the point of departure |
23:17:43 | gmaxwell: | e.g. if the attacker's chain is the same as B but has just 0.0001 work added to the end, it's still fine to choose the attacker's chain. (and a regular spv node would do that too, ignoring the quantization that makes adding 0.0001 impossible normally) |
23:17:57 | amiller: | (yeah, ignoring that ;)) |
23:18:09 | maaku: | since when you initiate the peg you require work built on top of it, you are requiring the attacker to exert that much effort |
23:18:33 | maaku: | and the quieting period means that they have to sustain that work to keep a longer chain than the honest nodes |
23:19:10 | gmaxwell: | maaku: I think the peg example might needlessly complicate it, e.g. instead you could just talk about a headers first SPV node in a world of dishonest parties that will feed them gigabyte of diff1 blocks. |
23:20:39 | maaku: | ok, here's a simpler counterpoint: when we're building proofs A -> B vs A -> B + epsilon, the transaction we care about is in A, and so it is in both chains |
23:20:49 | maaku: | which is why i'm not understanding the objection |
23:21:55 | gmaxwell: | also, A also did the +epsilon work, so it passes my 'game'. |
23:22:56 | amiller: | if transaction is in A then you don't even have to check anything, any security is fine |
23:23:03 | amiller: | it means the attacker is trying to convince you of something you already agree with |
23:23:31 | amiller: | also maaku your use of A/B differs from gmaxwell's game earlier so it's a bit confusing |
23:26:24 | maaku: | amiller: so with pegging, what you provide for a return peg is: SPV(Pin -> Pout(height=X) -> Z1) |
23:26:27 | amiller: | i basically want to cast this game as ONLY about evaluating how much work has buried a transaction |
23:26:30 | maaku: | where Pin is the block where the coins moved into the chain, Pout is a block at height X where the coins moved back out, and Z1 adds extra work |
23:26:49 | maaku: | amiller: yes, and our transaction is in A |
23:27:10 | amiller: | the game has to be about a conflict then |
23:27:11 | maaku: | or rather the initial block, whatever gmaxwell called that |
23:27:16 | amiller: | one person tries to prove that A has some amount of work buried |
23:27:37 | amiller: | and someone ELSE tries to prove that the tx is NOT buried by that much work, er rather than there is another chain that does *not* include the Tx and that has more work |
23:27:57 | amiller: | that's where finding a divergence point matters, because you want to show that the divergence point is before the Tx in question |
23:28:03 | maaku: | amiller: not necessarily, the game is about making fake proofs |
23:28:40 | maaku: | so assume that the divergence point is the first connection |
23:28:44 | amiller: | yes but i'm suggesting make it about fake proofs about how much work has buried a transaction (or buried a conflicting transaction or a block without that transaction) |
23:29:11 | maaku: | amiller: if you work it out on paper I think you'll see that it reduces to the same problem |
23:29:24 | maaku: | you identify the block which has the transaction you want to get rid of |
23:30:03 | maaku: | and the attacker builds a fake proof starting from somewhere earlier that appears to be more work |
23:30:13 | amiller: | okay so that's perfect, now we are agreeing that we have found a *latest* block at which for *sure* at this point and beyond, the two chains we are comparing are completely different |
23:30:29 | maaku: | no |
23:30:31 | amiller: | and every sample of work in the two chains are for sure either on one side or the other, there's no risk of overlap or double counting work |
23:30:49 | maaku: | because the game is about faking work |
23:31:02 | maaku: | the fraud stuff is a total application-specific tangent |
23:31:22 | maaku: | there may not even be an underlying chain for the attacker |
23:31:55 | amiller: | i thought we had helped narrow down the problem to the core point, now you're telling me it's a tangent, i disagree highly |
23:33:37 | maaku: | amiller: here's the core point: you are interpreting the game as "can the attacker generate a proof purporting to be N+1 units of work, without *himself* doing that work?" |
23:33:58 | maaku: | when in fact the intended interpretation is: "can the attacker generate a proof purporting to be N+1 units of work without anybody having to do that work?" |
23:35:02 | maaku: | so reusing work from the 'honest' chain (whatever that means) doesn't help you beat the game |
23:35:38 | maaku: | because that shared work still counts actual work that was computed by someone , somewhere |
23:36:16 | amiller: | it's still bad if that shared work is used both in support of Tx being committed and against Tx |
23:36:36 | amiller: | that's why i'm advocating including a particular point in the past as a referent |
23:36:52 | maaku: | amiller: I think you're confused |
23:36:56 | maaku: | where is the Tx committed? |
23:37:19 | amiller: | lets suppose the tx is committed in the honest chain |
23:37:33 | amiller: | the attacker is trying to convince you that tx never occurred or that some tx' preempts it |
23:37:35 | maaku: | the spv proof is a proof of work built on top of the block right? so the proof starts with the block containing the Tx |
23:39:01 | maaku: | so the attacker would have to prove divergence at a block prior, and then build a proof of work built on top of that which is longer |
23:39:10 | amiller: | right yes. |
23:39:19 | amiller: | that's why i want to keep in focus the divergence at the block prior |
23:39:34 | amiller: | in my scheme, *every* sample of work is connected directly back to that divergence point |
23:39:52 | amiller: | that means that any sample that is used in support of Tx, *cannot* also be used in support of Tx' |
23:40:13 | maaku: | I'm not sure it is. you don't commit to the back links prior to hashing |
23:40:18 | amiller: | yes you do |
23:40:49 | amiller: | i think you misunderstood my scheme, which is fair since i didn't describe it very well at all and never gave any code |
23:41:09 | maaku: | "I propose to also include the hash of the most recent block with higher value than the previous." |
23:41:31 | amiller: | right so the back and up links depend only on the previous block |
23:41:40 | amiller: | and just like in ordinary bitcoin mining you have to commit to the previous block while mining |
23:41:44 | maaku: | so I wait for a high value block that randomly appears |
23:41:55 | maaku: | then build one block on top of it at regular difficulty, with an invalid link |
23:42:02 | maaku: | *invalid back-link |
23:42:13 | maaku: | and use that to construct a skip-list proof |
23:42:55 | maaku: | there's no actual connectivity, but you don't know that by just looking at the proof |
23:42:59 | amiller: | ok i think i'm following and see where you're going with this |
23:43:02 | amiller: | hm |
23:44:22 | amiller: | well no i don't think i do still |
23:44:40 | amiller: | i don't see how it matters if i build invalid links |
23:45:11 | amiller: | if there's some divergence point, i have to show you samples that at least link back to something beyond that divergence point |
23:45:34 | amiller: | i think it's possible that i could create a malicious chain that has two conflicting transactions and i could use it to convince you that there is work burying Tx' and also burying Tx'' |
23:45:49 | amiller: | but if the honest chain is burying Tx, there's no way i can reuse samples of honest work to convince you of something different |
23:46:44 | amiller: | so a key part of this game definition c.f. gmaxwell's is that there's at least one chain that is honestly generated and has most of the work. |
23:53:46 | maaku: | sorry crying baby is pulling me away. we'll have to finish this some other time |
23:53:56 | amiller: | :] |
23:54:11 | amiller: | thanks for the discussion! i actually feel a lot better about a couple aspects of this and will trying writing it up now |
23:54:16 | amiller: | hopefully the result helps |