00:07:13gmaxwell:sipa: http://0bin.net/paste/avMPb2XvTDNid2zr#vK6LPkvNauP7RGCrCmsd6Ek04W4hpNn3R16kxjuoRbE= this is roughly what I'm talking about for OP_CHECKLOCKTIMEVERIFY
00:07:41gmaxwell:(actually deployment would need to be just slightly more complex because of the need to safely do the soft fork.)
01:11:23amiller:so the worst thing about the hash-value-highway scheme i think
01:11:40amiller:is that for only 2x the expected amount of work, you can make a chain that is really time consuming to check
01:11:43amiller:and never has any back links
01:11:59amiller:er, has only "back" links and no "up" links
01:22:36HM:How on earth would one negate an unsigned 64 int in C or C++?
01:22:50HM:(assuming it's in range)
01:23:57HM: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:03copumpkin:negate?
01:25:08HM:* -1
01:25:15copumpkin:but, uh
01:25:27amiller:what do you mean by "in range" then?
01:26:07HM:an unsigned value between 0 and -INT64_MIN, inclusive
01:26:30zooko:Hm.
01:26:34copumpkin:ah, so you want UINT64_MAX - x?
01:26:59HM:errm, no
01:27:51HM: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:21HM: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:09HM:but you still want to be able to do that because INT64_MIN is a perfectly good signed 64bit value
01:29:51HM:so it's a special case, seems kind of inelegant
01:31:17copumpkin: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:03copumpkin:or maybe I'm just being thick and everyone else understands what you're getting at :)
01:45:54HM: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:00HM:how do you do it?
01:46:29copumpkin:oh, I see, I thought you were trying to stay within the uint type!
01:46:36HM:no of course not
01:46:38copumpkin:I know how two's complement works :P
01:46:48copumpkin:but you can see why I reacted strangely to it now :P
01:51:13HM:afaict you have to do something like: if (x == 128) return -128 else if (x < 128) return -1 * (int8_t) x;
01:59:52copumpkin:actually
02:04:03copumpkin:I think it just works
02:04:17copumpkin:if x == 128
02:05:45copumpkin:(int8_t)x = -128
02:05:49copumpkin:and negating that is -128 still
02:05:57HM:it will in C for chars, because any operation promotes anything less than an int to an int
02:06:36HM:it won't work for 64bit types
02:12:29copumpkin:my point is more that negate on SOME2'SCOMPLEMENT_MIN leaves it untouched
02:13:45HM:bitwise yeah
02:14:02HM:so it's a special case, because all the other values, except 0, change
02:14:09copumpkin:yeah
02:24:00copumpkin:yeah, so err
02:24:21copumpkin:it just works for me :P
02:26:21copumpkin:I'm sort of confused now
02:26:26HM:it doesn't work
02:26:45HM:int64_t i = 9223372036854775808ull;
02:26:56HM:i will be -9223372036854775808
02:27:02HM:but that's undefined behaviour
02:27:17copumpkin:then do it bitwise in unsigned space?
02:27:20HM:then you multiply by -1, and you still get -9223372036854775808
02:27:25HM:but that's also undefined behaviour
02:27:56HM:copumpkin, you still have to check for the edge case, i think
02:27:59copumpkin:why?
02:28:13copumpkin:we know the two's complement math works out, so just do it by hand if you're afraid of undefined behavior
02:28:16HM:because taking the 1s compliment and adding 1 results in the same thing
02:28:33copumpkin:no?
02:29:33justanotheruser:You just have accept that 9223372036854775807 + 1 = -1
02:29:42HM:doing a memcpy is technically undefined behaviour as well
02:29:49copumpkin:~0x8000000000000000 + 1 = 0x8000000000000000
02:32:41copumpkin: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:20HM:it really doesn't
02:34:34HM:because the compiler is allowed to assume signed integers never over or underflow
02:35:03copumpkin:but I was just suggesting doing it in unsigned space and converting at the last minute
02:35:10copumpkin:so you don't need to rely on that
02:38:52HM:umm.... ~128 = 127 + 1 = 128
02:39:01HM:you then do what?
02:39:06HM:casting to signed is undefined
02:39:55copumpkin:*(int64_t*)&x, where x is my bitwise-negated uint64_t
02:39:57copumpkin::P
02:40:15HM:you can do a memcpy or a type pun, but it's still technically undefined.
02:40:27copumpkin:well then I don't know what to tell you. You either have two's complement or you don't
02:40:38copumpkin:if you can't assume the representation of a number you can't do much
02:40:54copumpkin:I don't really care if it's technically undefined. It'll work on all computers
02:41:04HM:;)
02:41:24copumpkin:but seriously, if I can't convert between representations you're pretty much forcing me to put a conditional in there
02:41:33justanotheruser: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:35copumpkin:because it's undefined to call it on a larger number
02:42:51HM:copumpkin, yep, i believe a branch is the only portable way of strictly doing it
02:44:45HM:never compile anything with -Weverything
02:44:58HM:it'll make you want to give up
02:45:08copumpkin:it complains about my solution?
02:48:00HM:I'm pretty sure if you use a C cast the compiler will let you do just about anything
02:48:38HM: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:36Snowleaksange:you want a (signed integer <-> unsigned integer) transform that preserves sort order?
02:52:55HM:sort order? :S
02:55:06Snowleaksange:unsigned 0000 < 0001 < 1110 < 1111, while signed 1110 < 1111 < 0000 < 0001
02:55:26Snowleaksange:maybe misunderstood question
02:56:12copumpkin:a functor from the canonical uint64_t preorder category to the canonical int64_t preorder category
02:56:13copumpkin:* copumpkin runs
03:00:27Snowleaksange: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:28Luke-Jr:writing standards-compliant code is not that hard -.-
03:05:49Snowleaksange:the standards compliant way to bitcast is memcpy()
03:05:55jgarzik:Luke-Jr, bwahahahaha
03:06:05Snowleaksange:http://code.google.com/p/stx/source/browse/trunk/stx/bit_cast.hpp?spec=svn25&r=25
03:14:15HM:its easy to write standards compliant code when the standard doesn't specify what should happen
03:16:04Luke-Jr:I didn't say it was easy, I said it wasn't that hard. :P
03:24:40HM:Ah well, time for bed. thanks for the brainstorming
03:24:47Guest26727:Guest26727 is now known as roidster
03:25:02HM:Anyone looking in to writing a parser should look at Reagel btw. I started playing with it today, it's awesome
03:25:27HM:Ragel even
03:26:22HM:Generates pretty state diagrams right from your code
03:47:40larslarsen:so I have an idea to avoid alts from getting difficulty-jacked
03:48:44larslarsen: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:00larslarsen:with an extremely short block time, like a heartbeat
03:49:40larslarsen: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:44larslarsen:or altcoin or whatever
03:50:40larslarsen:boom... time traveler is stuck with the difficulty everyone else has
03:51:44larslarsen: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:43larslarsen:but this is an atomic block, and timescales should be very accurate too
03:53:47larslarsen:you could alternately produce ZKPs in this chain as well
03:53:56larslarsen:just because nodes are good for that stuff
03:54:30larslarsen:and of course, its just rolling, you discard the end of the chain
03:54:38larslarsen:and tiny super small
03:56:23larslarsen:I call it chain insecurity consensus. Yup, this still secures nothing. At the rate it should!
06:15:41gmaxwell:larslarsen: p2pool also uses the wedge to bitcoin to prevent time travling reorgs.
06:16:03gmaxwell:though it still doesn't prevent isolating someone and mining their difficulty down in realtime.
06:48:10nOgAnOo:nOgAnOo is now known as noganoo
06:49:26noganoo:noganoo is now known as nOgAnOo
08:18:24justanotheruser:justanotheruser is now known as just[dead]
09:41:53just[dead]:just[dead] is now known as justanotheruser
11:11:05avantgeek:avantgeek has left #bitcoin-wizards
11:38:43rdponticelli:rdponticelli has left #bitcoin-wizards
12:10:29jarpiain:jarpiain is now known as Guest87860
14:21:59rastapopuloto:rastapopuloto has left #bitcoin-wizards
14:28:59justanotheruser:justanotheruser is now known as just[dead]
14:35:51Manfred_Karrer:I have a question regarding malleability: Can malleability happen without malicious intention? Like due different implementation or optimization?
14:42:07stonecoldpat:i remember being told that it can
14:42:19stonecoldpat:that it just happens from time to time
14:43:25roidster:roidster is now known as Guest97452
15:31:27Ademan:Manfred_Karrer: yes it can, but it requires some sort of intention
15:32:08Ademan: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:05Ademan: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:20zooko:zooko has left #bitcoin-wizards
16:13:23Guest97452:Guest97452 is now known as roidster
16:28:24maaku:Ademan Manfred_Karrer: transactions can be mutated without any mallicious intention
16:28:32maaku:especially if they are non-canonical to start with
16:29:17maaku: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:31Manfred_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:30maaku: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:43maaku:this is, unfortunately, a serious limitation
16:44:55adam3us: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:36maaku:adam3us: yes, but the changed 1st transaction would invalidate the multisig on the 2nd
16:45:50hearn:gmaxwell: did you see this? http://blog.bifubao.com/en/2014/03/16/proof-of-reserves/
16:46:07maaku:it's a much smaller category of protocols which doesn't require signatures in advance
16:46:09Manfred_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:19gmaxwell: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:51Manfred_Karrer:gmaxwell: ah sounds great! looking forward to it!
17:09:50adam3us: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:18maaku: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:42maaku:gmaxwell's op_maturity lock-time check helps here though
17:13:33just[dead]:just[dead] is now known as justanotheruser
17:14:01adam3us: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:16adam3us:adam3us has left #bitcoin-wizards
17:18:33zzyzx:zzyzx is now known as roidster
17:19:03roidster:roidster is now known as Guest11364
17:44:08larslarsen: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:47gmaxwell:hm? it just gets its chain wiped out by the superior public one.
17:44:57larslarsen:I assumed as much, just making sure
17:45:07larslarsen:The failure here is in mining on useless data
17:45:10gmaxwell:which is slim consolation if its already taken irreversable action.
17:45:20larslarsen:YEs if you're sybiled you have worse problems
17:45:24gmaxwell:no the failure is that the user is now bankrupt...
17:45:25larslarsen:I am concerned about the network as a whole
17:45:44gmaxwell:No you shouldn't though, bitcoin is sybil resistant unless you go @#$@#ing with how the difficulty changes work.
17:45:50adam3us:larslarsen: nodes that are high assurance / high value (eg handling user money) should make attempts to avoid being surrounded
17:46:14gmaxwell:If you're not sybil resistant you're not secure on the modern internet.
17:46:30larslarsen:gmaxwell: I see, so sybiling some nodes could break everything. But not just with one node?
17:46:47adam3us: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:59gmaxwell:It would break everything for that node ... except that the slow difficulty updates protect it.
17:47:21gmaxwell:adam3us: larslarsen is speculating about altcoin ideas which largely undo bitcoin's inherent robustness.
17:47:27gmaxwell:(to sybiling)
17:48:05larslarsen: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:21gmaxwell: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:54adam3us: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:10larslarsen: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:32larslarsen:adam3us: just one non-jammed ULF radio transmitter and we're all good
17:49:41larslarsen:shortwave
17:49:50adam3us:larslarsen: a use for jgarzik microsat
17:50:30gmaxwell: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:36larslarsen: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:28gmaxwell:you need 1bps for bitcoin headers.
17:51:34larslarsen: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:21larslarsen:gmaxwell: I understand what you're saying. The issue is that in pump and dump scams, pools are the tool of choice.
17:52:50adam3us: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:05larslarsen:gmaxwell: I understand what you are saying though, you could seriously break the network if you can do short scale downcalcs
17:53:22gmaxwell: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:06gmaxwell: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:37larslarsen: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:13gmaxwell:S'okay. :)
17:55:50larslarsen: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:34larslarsen: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:48larslarsen:gmaxwell: I will not worry about that, its not my problem.
17:57:00gmaxwell:then simply put an explicit 'backdoor' in your system to dicourage premature use as value.
17:58:06larslarsen:gmaxwell: I was going to make the mining worth almost nothing and follow asigmosoidal curve
17:58:09larslarsen:good?
17:58:18pigeons: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:51phantomcircuit:pigeons, que
17:59:28gmaxwell: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:44larslarsen:gmaxwell: I have heard other people say that
18:00:18larslarsen:gmaxwell: We would be in a better place right now
18:00:37gmaxwell:I don't really know that it matters that much due to trade. It would have been a small improvement.
18:00:54larslarsen:gmaxwell: perhaps psychologically more "fair"
18:01:51gmaxwell: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:01larslarsen: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:12larslarsen:or auction
18:04:37larslarsen: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:56larslarsen:but it limits your use early if you need to move a lot of money around
18:05:30gmaxwell:well there is no way to measure adoption.
18:05:38larslarsen:unless you do arbitrary precision, is anyone doing that? like the really low coinsmax ones?
18:06:20larslarsen:gmaxwell: I know. but its pretty clear bitcoin was not going to 1000 when there was no windows client :)
18:06:37sipa:"when there was no windows client" ?
18:06:40gmaxwell:larslarsen: ...
18:06:44sipa:there has always been a windows client
18:06:45gmaxwell:wtf
18:06:54gmaxwell:The original software was windows only.
18:06:56larslarsen:sipa: I just realized that was probably true after I said it
18:07:06larslarsen:sipa: *I* didnt have one, sorry
18:07:17gmaxwell:(Which is probably a major reasons why I don't own all the bitcoins. :P )
18:07:26larslarsen:gmaxwell: lol
18:07:33hearn:gmaxwell: dude, i fixed bugs in wine early on so it ran on everything :)
18:07:34oakpacific: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:36hearn:you have no excuse :)
18:07:42gmaxwell:(because I could only run it in wine under vnc ... :))
18:07:59larslarsen:gmaxwell: If I was a windows user I would have all the bitcoins then! :)
18:09:08gmaxwell:oakpacific: totally depends on what the 'preimage attack' requires.
18:12:02larslarsen:who knew win32 knowledge would have paid off in this world? It just goes to know you never know
18:12:26hearn:lol
18:12:41hearn:yeah, who could guess that knowing the system that powers >90% of the worlds computers would be useful :)
18:14:16larslarsen:hearn: Yes but, without the kind of zealotry that makes that thinking seem rational, we wouldnt have bitcoin.
18:14:27gmaxwell:'computers' :)
18:15:18oakpacific:gmaxwell: let's say an attack like what we already have on MD5
18:15:37hearn:heh
18:15:56hearn:gmaxwell: do ATM's count?
18:16:43gmaxwell: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:54larslarsen: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:23larslarsen: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:23larslarsen::)
18:19:43gmaxwell: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:46justanotheruser:justanotheruser is now known as just[dead]
18:20:51gmaxwell:Though because we use the sha256^2 even if sha256 itself had the md5 issue, you'd be broken there.
18:22:55oakpacific:gmaxwell: thanks a lot
18:33:17larslarsen:Can an identical signed transaction appear on two networks and both be valid? Is anything other than address letters preventing this?
18:36:59maaku:larslarsen: address letters don't exist at the transaction level
18:38:03sipa:addresses in general don't exist at the protocol level
18:38:06Luke-Jr:^
18:38:30larslarsen:maaku: duh... ok... so I'm going to have to assume its possible
18:38:37larslarsen:maaku: unless someone can tell me why not
18:39:24maaku:larslarsen: the input txids. why would they be the same on two different networks?
18:39:34sipa:larslarsen: for two transactions to be identical, the inputs being spent must also have identical txids
18:39:48larslarsen:maaku: are they malleable?
18:39:55sipa:larslarsen: #bitcoin please
18:40:02larslarsen:maaku: this is an attacker attempting to create the same txid and body on both networks
18:41:32sipa: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:49petertodd:larslarsen: that is possible, even with height-in-coinbase, but really unlikely
19:04:57larslarsen:petertodd: so if I constructed outputs carefully, I could craft inputs of my choosing?
19:05:12petertodd:larslarsen: ?
19:05:39larslarsen:petertodd: I'll take it to #bitcoin and come back when it matters
19:05:50petertodd:larslarsen: thanks
19:08:00amiller:hey so thinking out loud about how to define security for the compact SPV proofs....
19:08:07amiller:suppose you want to check how much work has *buried* a transaction
19:08:23amiller: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:36petertodd:amiller: yeah, not taking burying into account is bad
19:09:03amiller: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:31amiller: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:54petertodd:right - note how the reorg rules of tree-chains is specifically designed to make that question irrelevant
19:10:07petertodd:fork point?
19:11:14amiller: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:25amiller:if you want to do an SPV proof without even having to check all the headers but some subset of them
19:11:39lawlll:hey guys
19:12:16petertodd: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:53amiller:i don't understand what you're talking about tbh
19:13:06petertodd:maybe the same on my end :)
19:13:37petertodd: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:42amiller:the scenario is, i think, you have two sets of headers given to you by nodes
19:14:49amiller:one of them says a transaction is valid, the other one says it's not
19:15:11amiller: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:33amiller:informally, it's alright if the longer chain is *invalid* and you wrongly choose it
19:15:52amiller:because the attacker is assumed to have less than 50% hashpower and the honest people only mine on *valid* chains
19:16:45amiller: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:09gavinandresen_:BlueMatt: pull-tester was stuck on pull 3850, haven't looked at why. But it just failed 3893….
19:17:19amiller: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:30petertodd: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:53amiller:ok, yeah, that's probably still interesting and useful but just not directly related to what i'm trying to address
19:18:26amiller: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:30petertodd:yeah, although it does suggest that what you are trying to address is a subset of a bigger problem...
19:18:59gmaxwell:amiller: I'm reasonably confident that it actually isn't.
19:19:35gmaxwell: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:07amiller:well where we left off yesterday, you had suggested "sequential checking" as the gold standard
19:20:17amiller:and what i asked was, what does sequential checking do when there's an invalid link in the chain
19:20:40amiller: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:54gmaxwell: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:13gmaxwell: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:56amiller: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:27amiller:is that clearly enough sufficient?
19:24:35gmaxwell: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:54lawlll:gmaxwell: how close are we to using bitcoin to solve other real world problems other than being money... ie, smart property/contracts ?
19:50:22gmaxwell:lawlll: why are you repeating the question when I answered you at some length in #bitcoin? :(
19:50:31lawlll:sorry i didnt see the answer
19:50:33lawlll:thought you forgot
19:51:54phantomcircuit:jgarzik, i just realized what is going on here, the http postbacks are being made multiple times almost immediately after the first
19:52:15phantomcircuit:that's probably going to screw up a bunch of peoples systems that dont have proper race condition handling
19:52:40lawlll:lol i hate mirc
19:58:17lawlll:oh i see it now
19:58:20lawlll:thx gmaxwell
20:04:53just[dead]:just[dead] is now known as justanotheruser
20:13:37gavinandresen_:gavinandresen_ is now known as gavinandresen
20:35:09jgarzik_:amiller, what is that storify link, again?
20:35:19amiller:oh for dakami
20:35:20amiller:one sec
20:35:37amiller:http://storify.com/socrates1024/bitcoin-pow-bet-10btc-jgarzik-vs-dakami-may-2014 jgarzik
20:37:40amiller:jgarzik, while we're on the topic of bounties though...
20:38:02amiller: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:21amiller:https://bitcointalk.org/index.php?topic=326559.0
20:38:49amiller:afaict kjj is waiting for you to call it
20:50:40justanotheruser:justanotheruser is now known as just[dead]
20:50:43jgarzik_:* jgarzik_ looks
20:51:13jgarzik_:amiller, no time to play and evaluate
20:51:40jgarzik_:amiller, if you tell me the bounty is satisfied, then I'm happy ;p
20:54:32amiller: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:24amiller: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:26amiller: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:45adam3us: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:38amiller: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:14adam3us: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:16amiller:adam3us, you don't need simulation at all, the cornell folks worked out closed form solutions to all their models
21:06:05adam3us: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:26gmaxwell:amiller: are these closed form solutions to models that lack things like latency?
21:20:46gmaxwell:and don't include things like variance in mining?
21:21:04gmaxwell:a latencyless network of equal speed variance free miners never converges. :P
22:49:53maaku:amiller: you seem to have some very different problem in mind for the hash-value highway than we do
22:50:33maaku:i look forward to reading your security game
22:52:10amiller: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:40amiller: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:30gmaxwell:why are you saying they are nebulous at all.
22:53:35gmaxwell:It's absolutely concrete.
22:53:43gmaxwell:You have to not be able to win at that game I described.
22:54:37amiller:you still haven't answered my questions about it!
22:54:49gmaxwell:perhaps I missed them, freenode was splitting.
22:55:01amiller: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:17amiller:what i suggested most recently is that we make the game about a particular *invalid* transaction
22:55:18gmaxwell:all I'm giving you is an interlinked set of headers.
22:55:59gmaxwell: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:21amiller:right but spv does at least involve fully verifying a chain
22:56:24gmaxwell:which reduces to being able to accurately evaluate which set of headers is the one with the most hashpower behind it.
22:56:28gmaxwell:No, it doesn't.
22:56:38amiller:so we are generalizing spv security a bit
22:56:48gmaxwell:it involves testing membership.
22:56:56amiller: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:21maaku:amiller: we are not concerned with actual connectivity
22:57:32maaku:we are trusting the majority hashpower for that
22:57:34amiller:"one with most hashpower behind it" is also too vague because some of the headers in Chain A might overlap Chain B
22:57:53gmaxwell: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:09gmaxwell:it might overlap but it doesn't matter.
22:58:24gmaxwell:if A+B > A+C then B>C
22:58:42gmaxwell:(at least if things are well formed)
23:00:21maaku: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:25amiller: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:44amiller:that's why i'm suggesting including the fork distance in there
23:02:14maaku:amiller: why? units of work is all that matters
23:02:36amiller:yes but i only had to put in 0.000001 work to completely revise your chain, accoridng to the first defintion
23:02:53amiller: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:58maaku:amiller: you would have had to put in 10.00001 units of work, no?
23:04:03amiller:no
23:04:25amiller:beacuse i just extended yours by a tiny or revised it by 1 block or something
23:04:36amiller:technically that's a different chain, unless you are doing what i said and considering "fork distance"
23:05:17gmaxwell:Sorry, this is incoherent.
23:05:21gmaxwell::-/
23:05:40maaku:amiller: it's irrelevant to any application I can think of
23:06:12maaku:the spv proof summarizes the work from A -> B (my chain) and A -> C (your chain)
23:06:37maaku:we don't care at what point they diverged, just which one has more work
23:07:19amiller:ugh, it *does* matter where they diverge
23:08:42maaku:why? I suspect we'll have to delve into applications to resolve the difference
23:08:51gmaxwell: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:25amiller: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:03amiller: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:19amiller:because it's easy to have a "different" chain that only differs in the last few blocks
23:15:02maaku:amiller: when you need that property (and you don't always), you get it by explicitly identifying the point of departure
23:16:02amiller: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:10maaku: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:32gmaxwell: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:51maaku: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:43gmaxwell: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:57amiller:(yeah, ignoring that ;))
23:18:09maaku: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:33maaku:and the quieting period means that they have to sustain that work to keep a longer chain than the honest nodes
23:19:10gmaxwell: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:39maaku: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:49maaku:which is why i'm not understanding the objection
23:21:55gmaxwell:also, A also did the +epsilon work, so it passes my 'game'.
23:22:56amiller:if transaction is in A then you don't even have to check anything, any security is fine
23:23:03amiller:it means the attacker is trying to convince you of something you already agree with
23:23:31amiller:also maaku your use of A/B differs from gmaxwell's game earlier so it's a bit confusing
23:26:24maaku:amiller: so with pegging, what you provide for a return peg is: SPV(Pin -> Pout(height=X) -> Z1)
23:26:27amiller:i basically want to cast this game as ONLY about evaluating how much work has buried a transaction
23:26:30maaku: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:49maaku:amiller: yes, and our transaction is in A
23:27:10amiller:the game has to be about a conflict then
23:27:11maaku:or rather the initial block, whatever gmaxwell called that
23:27:16amiller:one person tries to prove that A has some amount of work buried
23:27:37amiller: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:57amiller: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:03maaku:amiller: not necessarily, the game is about making fake proofs
23:28:40maaku:so assume that the divergence point is the first connection
23:28:44amiller: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:11maaku:amiller: if you work it out on paper I think you'll see that it reduces to the same problem
23:29:24maaku:you identify the block which has the transaction you want to get rid of
23:30:03maaku:and the attacker builds a fake proof starting from somewhere earlier that appears to be more work
23:30:13amiller: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:29maaku:no
23:30:31amiller: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:49maaku:because the game is about faking work
23:31:02maaku:the fraud stuff is a total application-specific tangent
23:31:22maaku:there may not even be an underlying chain for the attacker
23:31:55amiller: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:37maaku: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:58maaku: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:02maaku:so reusing work from the 'honest' chain (whatever that means) doesn't help you beat the game
23:35:38maaku:because that shared work still counts actual work that was computed by someone , somewhere
23:36:16amiller:it's still bad if that shared work is used both in support of Tx being committed and against Tx
23:36:36amiller:that's why i'm advocating including a particular point in the past as a referent
23:36:52maaku:amiller: I think you're confused
23:36:56maaku:where is the Tx committed?
23:37:19amiller:lets suppose the tx is committed in the honest chain
23:37:33amiller:the attacker is trying to convince you that tx never occurred or that some tx' preempts it
23:37:35maaku: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:01maaku: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:10amiller:right yes.
23:39:19amiller:that's why i want to keep in focus the divergence at the block prior
23:39:34amiller:in my scheme, *every* sample of work is connected directly back to that divergence point
23:39:52amiller:that means that any sample that is used in support of Tx, *cannot* also be used in support of Tx'
23:40:13maaku:I'm not sure it is. you don't commit to the back links prior to hashing
23:40:18amiller:yes you do
23:40:49amiller: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:09maaku:"I propose to also include the hash of the most recent block with higher value than the previous."
23:41:31amiller:right so the back and up links depend only on the previous block
23:41:40amiller:and just like in ordinary bitcoin mining you have to commit to the previous block while mining
23:41:44maaku:so I wait for a high value block that randomly appears
23:41:55maaku:then build one block on top of it at regular difficulty, with an invalid link
23:42:02maaku:*invalid back-link
23:42:13maaku:and use that to construct a skip-list proof
23:42:55maaku:there's no actual connectivity, but you don't know that by just looking at the proof
23:42:59amiller:ok i think i'm following and see where you're going with this
23:43:02amiller:hm
23:44:22amiller:well no i don't think i do still
23:44:40amiller:i don't see how it matters if i build invalid links
23:45:11amiller: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:34amiller: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:49amiller: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:44amiller: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:46maaku:sorry crying baby is pulling me away. we'll have to finish this some other time
23:53:56amiller::]
23:54:11amiller: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:16amiller:hopefully the result helps