Well, there is a business use case for knowing that if a transaction has not happened by X time, then it definitely will not happen.  A "drop dead date" is absolutely crucial for some contracts.  

And of course, you know how that's implemented today?  It's implemented with a double spend.  If you want to be sure that a transaction  will not go through, you double-spend one of its inputs on something else, thereby guaranteeing that it will not go through. 

This is common in exchange protocols for example.  Usually the counterparty has a time-locked transaction that can get into the blockchain after a certain time; you have up until that time to stop the tx from going through if that counterparty does not perform, and the way you do that is to double spend one of the inputs so that the held tx is invalid.  This does not mean you have committed fraud; it simply means you have retained your money when the counterparty failed to perform. 

The vast majority of reorgs are <6 blocks, which is why confirmation works in the usual case.  Even if the transaction becomes unconfirmed (goes from 7 blocks deep to 2 blocks deep) it's still in the chain and rapidly becomes confirmed again.  Longer reorgs can drop confirmed transactions completely, but when that happens you either resubmit the transaction, or if you can't then you needed a longer confirmation time.

If you wanna be extra sure, the way we want to be extra-sure about coinbase transactions, then tx with an expiry time should take as long to confirm as coinbase transactions.  

But, I don't think of double spends as necessarily fraudulent.  double spends are the "refund if it doesn't work out" transaction in most exchange protocols.  You get your 'stuck' zero-fee transaction out of limbo by killing it with a double spend that replaces it with a fee-paid transaction.  Double spends are the failsafe options that prevent escrows from keeping your money.  And so on.  

Rejecting double spends is a fraud-prevention mechanism in both the negative sense (double spends are "fraudulent or misguided") and the positive sense (we use double spends deliberately to prevent fraudsters from keeping our money).  

So I simply don't buy the idea that an expiry time (equally useful for preventing fraud) is somehow worse than a double spend.

There's still no difference between this and any other transaction that can't get into the reorganized blockchain.  The reorganized blockchain presents a revised view of history, not an internally inconsistent one.  One side or the other of a double spend but not both.  A transaction with expiry time, or not. 

If a reorg happens after you ship someone something they bought using double spent txouts that disappear in the reorg, that's exactly the same problem.  And it doesn't make the system break down, it just makes it prudent to wait for confirmation before shipping.

Okay, I think I get it.

A hash with N initial zero bits corresponds to a probability that something close to 2^N total hashes have been performed, because, on average that's how many hashes it takes to get one with N initial zero bits.

Within the same set of hashes, you "expect" to find around two hashes with N-1 initial zero bits.  Each of these corresponds to a probability that something close to 2^(N-1) hashes have been performed.  If you have two of them, that adds up to 2^N total hashes (same as the work presented by the parent node).  If you have only one, though, your estimate is lowered (by half) and if you have five your estimate is increased (multiply by 5/2). 

Each of these hashes with N-1 initial zero bits is then expected to dominate around two hashes with N-2 initial zero bits. Meaning, if you had two at the N-1 level, you expect around four, and if you had five at the N-1 level, you expect around ten.  And each of these N-2 hashes represents around 2^(N-2) total hashes.  If you expected ten and you find seven, you lower your estimate (multiply by 7/10).  If you expected four and you found seven, you'd raise your estimate (multiply by 7/4). 

And so on, so the more of the "high nodes" on this hash tree you process, the better your estimate gets.  The law of large numbers means each "generation" verified downward from the root of the tree will lead to smaller and smaller adjustments to the estimate, and you probably have a very good idea (within 1%) of the total work by the time you've found the ~50 best hashes. 

This procedure can be carried down to the level of difficulty as of the time the block was mined, below which there's no information so you just have to treat your estimate on the individual blocks as the "truth" or as close as you can get.

So this gives you a way of getting a rapid estimate of the total amount of hashing work that went into a particular blockchain, or into the portion of it discovered since the blockchain fork. 

Okay, I see the value there.

It's also interesting that you could do the same kind of linking on any metric; for example the amount of coin age destroyed by a given block, if that were your measure of "best chain" instead of the number of hashes.

And this is different from any other tx that can no longer be placed in a block after a reorg? 

The crucial consistency property is not violated here.  You never have a transaction getting into a block which later becomes an invalid transaction.  What you're thinking about here is just switching to an alternate view of history where it *never* got into a block, and *isn't* a valid transaction.  That's a reorg, not an inconsistency in either branch.

Hell, maybe the right thing isn't looking at "intervals" as such at all.  Maybe the right thing is looking at the total number of blocks in the blockchain that have timestamps within, say, an hour of the most recent block's time, completely ignoring whether individual blocks are backward, forward, long, short, or whatever.  If there are a lot, it's time to raise difficulty.  If there aren't, it's time to lower difficulty.

It has at least a couple of "consistency" properties I like, anyway.  No matter how anybody jumps back-and-forth in time, if you build up a lot of blocks that have similar timestamps you start getting seriously increased difficulty until you get completely away from that time. 

That's a contradiction in terms.  Your time-travel block cannot have an increased time since last block.  If it did then it would not be a time travel block.  You raise the difficulty the maximum amount by turning in a block shorter than x, and negative time is always shorter than positive x. So the time travel block will always incur a maximum upward difficulty adjustment. 

It certainly is not "fraudulent or gravely mistaken" to resend the same txouts with a fee when your zero-fee transaction has been sitting there for three days unconfirmed!  The fee-paid transaction will go through, and the double spend will kill the zero-fee transaction, and that's exactly what you want to do! 

Worrying about whether an expiry-timed transaction made it into both sides of a fork is no different from worrying about whether a double-spent transaction made it into both sides of a fork. 

If the above diagram is how Darksend works, then I have identified an easily-corrected flaw.

The reverse of the above situation -- in which the Darksend itself "denominates" its outputs -- is simpler and more secure.  Everybody can see whose coins are going into the Darksend, denominated or not, because everybody can see the blockchain.  Denominating them doesn't really help all that much.  

Darksends are examples of the knapsack problem.  Denominating the coins allows the solution to the knapsack problem of the Darksend to be non-trivial.  IE, you can't break it into distinct subproblems because the inputs are equal-sized. So the number of possible solutions is guaranteed to be at least as large as the number of inputs.  But it doesn't guarantee that the solution is Hard, because different size outputs still leak partitioning information.  Worse, the partitioning information can be combined with other information at a later time, to associate the partitions with the inputs, potentially resulting in a unique solution.  Which would mean successfully tracing all the coins through the Darksend.

As an example of what I'm talking about, let's say Alice puts a 10-coin input into the Darksend, along with Bob and Carol and Dave.  And the outputs are 1, 2, 3, 4, 6, 7, 8, and 9 coins.  40 total in, 40 total out.  (I'm ignoring fees for the moment; bear with me). Now Eve, looking at the blockchain, doesn't know who got which coins.   But she knows that the same person who controlled where the 1 went also controlled where the 9 went.  She knows that the same person who controlled the 2 also controlled the 8.  She knows that the same person who controlled the 3 also controlled the 7.  And she knows that the same person who controlled the 4 also controlled the 6.  Because no other combination adds up to everybody controlling the same amount they put in as an input.  There are other ways to make 10 -- for example, 7,2,1 or 6,3,1.  But Eve knows that nobody got those combinations of outputs because that would mean that somebody else didn't get 10.  

This is "partition information" -- there are relatively few solutions to which outputs went together, even if you don't know who controlled which set.  Maybe there are multiple solutions, especially if two or more parties asked for the same denominations of outputs.  But you'll usually find surprisingly few solutions to the partitioning problem.  Additional information can come from later spends and eliminate subsets of the solution space.  A surprisingly small number of spends later, Eve will have the information to reconstruct the Darksend transaction and trace the movement of coins through it.

In order to guarantee that the solution to the Darksend is Hard, it is necessary for it to produce equal-sized outputs.  With equal-sized outputs there is no partitioning information to be had, so a later spend can't provide any new information about the movement of other coins through the Darksend.  

Consider a Darksend where Alice, Bob, Carol, and Dave all put in a single 10 coin input.  It produces a dozen 3.33 coin outputs.  Now, Eve knows that each participant got 3 outputs.  But even if she later associates one of the outputs with an 'Alice' transaction, that doesn't give her any new information about which of the *OTHER* outputs Alice has, or spent, nor allow her to eliminate any possibilities as to which outputs Bob, Carol, and Dave have, or spent.  The partitioning problem is Hard, and remains Hard.

This remains true even if Alice, Bob, Carol, and Dave all put in undenominated inputs that total up to exactly 10 coins each.  Security here is in equality of the amount input, not in the size of the individual txins. Remember, Eve already knows who's putting in which inputs, denominated or not.  As long as each participant puts in a like amount, and the outputs are identically-sized, Eve has no information about the disposition of coins after the send.  

Anyway, my point here is that you can make the problem Hard by doing it the other way round.  Use the Darksend to denominate the coins into equal-size outputs that all come back to you, but then spend those outputs (along with NO OTHER OUTPUTS, not even outputs from other Darksends) in regular transactions, and those regular transactions will be conditionally untraceable. To make them completely untraceable, you don't spend the change from those transactions either; gather the change together until you have a 'denomination-worth' of input, send that into another Darksend, and get a new set of outputs.

Nope.  I claim that if you're jumping back to a time before the last five blocks, you should increase  difficulty by exactly as much as the difficulty has lowered in the last 5 blocks.  Well, plus whatever upward diff adjustment you get for the minimum-time (actually negative-time) block you're turning in. 

The point is that nobody should be able to make long-term changes to the difficulty (especially nobody should be able to lower the difficulty) by going backward and forward in timestamps.  The way to do it is to undo whatever "progress" they've made toward changing the difficulty whenever they jump backward. 

While it's true that jumping back over more blocks means potentially undoing more adjustments and therefore getting a much bigger total change with your back-timestamped block, it won't always be the case that the last N blocks have all been lowering the difficulty - and making a big adjustment anyway would unduly increase the difficulty. 

I still don't see how that's different from the analogous scenario with a zero-fee transaction.  It doesn't get into the blockchain, but stays in the mempool.   The sender makes another transaction using the same coins, so at most one of them will succeed because the second would be a double spend.  Say the second one succeeds.  Then there's a reorg, to a chain where the first one succeeded instead and the second is invalid. 

We have this scenario every day.  I don't see any relevant difference between expiry times and other reasons for tx to fail. 

In theory, you could do something like insert a transaction in the blockchain with a 0.005 BTC txout spendable only by a certain secret key, and then modify the next version of the client to reject as invalid any chain containing a spend of that txout.

And then whomever holds that secret key could attempt to "kill" an alternate blockchain by spending that txout on that fork of the blockchain.

The problem with an idea like this is that if the fork is deliberate and malicious, then the malicious miners on that fork will be aware of the poison pill (because they have the sources) and will flatly refuse to mine that transaction.

I had the same problem.  A boost template expanded to something that contains an operator redefinition that made the resolution ambiguous. 

From time to time I think about "deBoosting" the source, but because there's approximately zero chance of that change going through, I stop thinking about it...

I'm a lucky man.  My father, grandfather and great-grandfather were all hit by lightning, and I got born anyway.

I moved to a nice coastal area where lightning storms are less common, so as not to continue that tradition, btw.  I also don't fix barbed wire fences when storms are moving in, nor ride iron-shod horses across wet high-altitude flatland during a storm, nor....  well, whatever.

With luck like that, I might one day consider buying a lottery ticket. 

But I wouldn't attempt to brute-force a Bitcoin key.  That's just crazy.

The interesting application as far as I can see is not in having clients detect zero-confirmation payments to a given address; it is in having them detect zero-confirmation spends from a given address.

If someone pays for goods with a transaction using a particular set of txin, and In the next ten seconds no other transactions show up in the mempool using any of those same txin, then I am reasonably confident that he's not attempting (or at least will not succeed in) a "double spend" attack.

Because, if it hasn't propagated across the network by ten seconds after I get (and broadcast) my tx, then I assume that because my tx *has* by now propagated across the network, other clients will now refuse to relay any other tx spending the same txins.  

So simply detecting whether a particular txin in a transaction destined for my wallet is spent by any other mempool transaction would be a very rapid way to achieve at least the same degree of certainty on the same schedule that a supermarket gets at the cash register when someone hands them a $20 bill.  Is it counterfeit?  Possibly.  But if the cashier doesn't notice it, the odds are very very low. Likewise, is the coin double-spent?  Possibly, by the time it (doesn't) get into a block.  But if the cashier (or the bitcoin-aware cash register) doesn't notice a competing transaction on the blockchain within ten seconds or less, then the odds are very very low.

I think I don't understand the reorganization issue.

A hypothetical transaction A has an expiry time.  But it gets into a block before the expiry time, so txouts which may later be spent are created, and txins are destroyed. 

Then there's a reorg.  And in the other chain, A did not get into a block before its expiry time, so it was considered invalid.

I don't see how this is different from the ordinary case of a zero-fee transaction that did make it into the blockchain, but then after a reorg to a chain where it didn't make it into the blockchain, doesn't ever make it into the "free" area and eventually gets evicted from everybody's mempool. 

In either case, we see a revised history in which the transaction (and any other tx that depend on it) simply did not happen.  In either case, a replacement transaction can be broadcast. 

What's the problem in scenario A that isn't a problem in scenario B?

Once an output is spent, then everybody on the network knows whatever they need to know to verify that it was correctly spent. 

ie. public keys, number of actual signers, number of potential signers, etc -- all of that stuff.

Up until the output is spent, P2SH keeps all that stuff private (because they're looking at the script hash, not the script).  But in order to spend it somebody has to produce the script, and everybody has to be able to see it to verify that it matches the hash.  And then they have to do whatever the script says, and everybody has to be able to prove that they did it.

There are two simple fixes:  First, update the difficulty only seldom (as Bitcoin does), at intervals such that there is no hope of jumping back across more than one difficulty adjustment nor influencing one that you do cross very much when it's recalculated on crossing the critical block height again.

But given the objective of updating difficulty rapidly enough to be resistant to "raider" mining, you don't want to do that. 

The second fix is even simpler: when you jump back in time, always undo whatever adjustment to difficulty came with any blocks you jump back over. 

Either of these fixes kill time warp exploits dead.

The 11 block median rule is there so that one miner future-stamping his block, or even two or three in a row, can't force everybody to fake the timestamps on following blocks too.  

Dishonest miners would like to advance the time in the blockchain timestamps as far as they can while mining few blocks; that keeps the difficulty down.  If honest miners were not allowed to undo the damage, we would have wildly inaccurate timestamps (it would probably be 2016 already in the blockchain) and artificially low difficulty.  

Okay, I want to fully understand this.  Step By Step, is this how the DarkSend Protocol is actually working?

1.  A 'Master Node' for the current round is algorithmically selected on a (pseudo) random basis based on a hash of information in the blockchain. (so everybody who does it selects the same master node).

2. People who want to participate in a coinmix send the 'Master Node' 0.1 Dark (deposit), a redemption address and a 'redemption code' per input.  

3. The 'Master Node' collects information from the participants about how much they want in outputs and creates a transaction (with no inputs yet).

4. 'Master Node' collects signatures from all participants agreeing to the set of all outputs, and updates the transaction.

5. All participants break connection and connect to the network via a new set of peers, making it harder to associate inputs with outputs via network monitoring.

6. Participants communicate transaction inputs to the master node and the master node updates the transaction again.  

7. Participants now provide signatures (over the whole transaction) to 'spend' inputs.  If all inputs are now valid, the transaction is published.

8.  Everybody breaks connection again, reconnecting via a new set of peers,

9.  If all inputs are now valid as spends, the transaction is published and protocol goes to step 11.

10.  The master node creates a new version of the transaction not including the unsigned inputs, and protocol goes to step 3.

11. For each spent input, participants may now send a message to the master node, giving a nonce which, together with the input spent, forms a preimage for their redemption token.  The master node responds by sending them 0.1 Dark.  

If that's right, then the master node can connect inputs and outputs.  Also, the master node can just take everybody's (or anybody's) deposit and stop.   If the master node is honest, then there is no evidence left outside the master node about which inputs go with which outputs.  If the master node is dishonest, then he can later (after the anonymized coins are spent) make an a ransom demand offering to connect inputs with outputs unless he is paid.  

Surely the master node shouldn't be trusted this much, so I must have it wrong.  Can someone please correct me?

Even if we believe that we need a full-on database for live wallets, we should at minimum save a serialized file (a CSV table with encrypted individual values, for example) that can be written by any version of bitcoin and read by any other.  Using that as the wallet file, we could upgrade or change the database back-end without breaking wallet compatibility.