For time you could use a certain block # as the end. They are made on average 1 every 10 minutes. Or use the time inside the block. The problem is that the time inside the block can vary. https://en.bitcoin.it/wiki/Block_timestamp

Seems like the same thing can be done currently as follows:

A generates Tx1 with an output that can be unlocked by either (keyA and keyB) OR (secretA, secretB, and keyB). He does not broadcast it. He then generates Tx2 with Tx1 as the input with sequence number 0, an output that can be unlocked by keyA, and an nLockTime of sometime in the future. Because the sequence number of the input is 0, the transaction won't be finalized until the time encoded in nLockTime. He then signs Tx2 with keyA and sends it to B. B signs it and sends it back. A now broadcasts Tx1 and Tx2. After making sure a similar scheme is conducted on the other crypto network, he reveals secretA to B. B now reissues Tx2 using secretA, secretB, and keyB, but with nLockTime of 0, finalizing it, and an output of his choosing. A sees secretB in the broadcast transaction, and uses it to unlock the coins on the other network.

The wiki page https://en.bitcoin.it/wiki/Contracts has a good overview. The page https://en.bitcoin.it/wiki/OP_CHECKSIG also has a good overview of the different types of signature.

And yes, I think some of these features are currently disabled in the client. Hopefully they will be activated when the need for them arises though, and since they are already part of the protocol, it would probably be easier than making a new addition.

bump now this got moved.  Also I'll point out this scheme can be used to sell arbitrary computer-verifiable information for bitcoins (the entire purpose/advantage of "crypto-money" IMO) without requiring any trust.

1) I announce to the world I am willing to PAY for an input x s.t. f(x) = 1 for some function f.
2) You say "I have such an x".  You prove it to me in zero-knowledge.  (this step not needed, only next is needed)
3) You pick a random key K and compute y = Enc(K,x) and h = hash(K).  You send me h and y, and then
prove to me in zero knowledge that there exists K s.t. f(Dec(K,y)) = 1 and h = hash(K).
4) Using the protocol above, we do an untrusted trade of bitcoins for K (i.e., I write a TX that can only be spent by your pubkey AND publishing an inversion of h)

Er nothing in bitcoin requires ZK.  The point is the protocol in my above post can be carried out offline between two parties, only needing the blockchain to do the hash-for-btc trade.  It's also a bit weird calling things like ECDSA and SHA2 "pre-zero-knowledge", when ZK was a product of the golden-age of theoretical crypto research in the 1980s.  :-)

Anything provable is provable in ZK (infact, that is the title of the paper proving the result)[1].

The notion of provable there is quite general, including interaction.  Note that the simple scheme above "prove to me there is an x s.t. f(x) = 1",
the prover need only hand you such an x and not interact with you.   Such a "non-interactive" proof can be turned into a ZKP with a single
round of interaction.[2]  More complicated proof systems that began with interaction can be made zero-knowledge (and will still require interaction).

Clearly the limit is f needs to be a function you could write as code.  Easy examples are "x is a key to break this code" or other crypto-related problems.  But f can be quite complex; it could be some kind of computer vision algorithm that takes an image as input and detects the presence of some object, and then you could prove to someone in zero knowledge that you possess such an image without revealing it.

There is indeed a notion of non-interactive ZKP, but it's a bit weird and assumes both parties have access to a common source of random bits (e.g., both can listen to radio waves or both can observe a stock ticker or both can observe a geiger counter);  the one-round items are much simpler and intuitive.  

All such systems are probabilistic, and they must be.  Informally, you might think of a ZKP as a way someone can convince you something is true, but you still can't go prove it to anyone else.  This includes tape-recording your conversation with the prover.  If the protocol were not probabilistic, you would be able to convince your friend by just replaying the conversation.  The "magic" of ZKP comes from the fact that you put the prover in a situation where he must commit to something on which he will be randomly tested on later, and he does not know in advance exactly how.  On the other hand, if the prover knew in advance what test you would pick he could easily cheat.  So a fundamental part of why a ZKP convinces you is because the test you chose was random. You are convinced the test you chose was random, because, you chose it randomly.  The point is now trying to convince your friend with the transcript requires you to prove to your friend that your choice was random.  But how can you prove to someone that some fixed string was generated randomly?

I included links to the two classic papers, but TBH they will not be accessible to non-experts.  If you want to learn more wikipedia article is a good start, followed by googling for something like "zero knowledge proof lecture notes".  One exception is the "cave" example on wikipedia is dumb IMO and I look forward to the day people stop using it.  The highest-voted answer at [5] with billiard balls is a good example, and actually if you only are going to look at one thing, read that (just the green answer, ignore the others).

[1] http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC04/BGGHKMR89.pdf
[2] http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.120.6506
[3] http://en.wikipedia.org/wiki/Zero-knowledge_proof
[4] http://en.wikipedia.org/wiki/Non-interactive_zero-knowledge_proof
[5] http://mathoverflow.net/questions/22624/example-of-a-good-zero-knowledge-proof

Cool. I'm canceling my proposals that needed a new block chain for this same thing:
https://bt.irlbtc.com/view/31643
https://bt.irlbtc.com/view/32258

The following method comes close to trust-free crypto-currency exchange without time-conditional scripts or nLockTime.
It is practical on the current Bitcoin network and needs no additional script commands or features enabled.

A and B want to exchange crypto-currencies.
A generates a secret S and sends H to B where  H=hash(S).
Either A or B or both create two transactions Z, one on each crypto-currency for negligible or zero value which are spendable by revealing S, the value that hashes to H.
At this point A who knows S can spend both Zs but there's little incentive to do so given that the gain is so small or zero.
A sends B a transaction that pays B which also includes the relevant Z as one of the inputs.
This transaction is incompletely signed as A does not reveal S.

B checks the transaction to verify that knowledge of S would make it a valid transaction and sends A a transaction that pays A which includes the relevant Z as one of the inputs.
A signs Z by revealing S on the transaction crediting him and publishes the completely signed transaction.
B looks at the published transaction to discover S, signs Z on the transaction crediting him and publishes the completely signed transaction.

Unfortunately, as soon as A publishes B's transaction crediting himself, A can also publish a transaction which spends the input that credits B before B can publish A's transaction crediting him.... I doubt there's a way round this without nLockTime.

If the network agreed that the signed inputs from partially signed transactions could not be "double" spent until some short expiry period had elapsed then the above scheme would be secure. It would probably be a smaller and less worrisome change than implementing nLockTime and transaction replacement.

ByteCoin

I believe I have a way to overcome the lack of nLockTime. Firstly let's observe that A can use the scripting language to pose B a problem to which A knows the solution, and which B can quickly verify is very likely to have a solution, and for which B cannot feasibly do any precomputation to calculate the solution faster than brute force.

One example of this would be for A to challenge B to provide a number X in some random interval of size 2^N such that hash160(X) falls in some interval of size 2^(160-M).

There seems to be no faster way to independently find a solution than for B to perform a number of hashes roughly equal to 2^M. If N is somewhat larger than M then anyone can verify that it's extremely likely that a solution exists. If the random interval is chosen over the range of 160 bit numbers and if N is significantly smaller than 160 it's unlikely that B will have chosen to precompute the hashes of any values in the interval.

So the proposal in my last post would have worked if there was something preventing A spending the inputs crediting B.
To solve this we arrange that before the start of the procedure B poses A a brute-force problem as defined above to prevent A spending the inputs crediting B without either the solution from B or alternatively exhaustively searching for the solution. B must be able to bound the amount of time A must spend to perform the exhaustive search as this will dictate how long B will wait for A to complete the next stage of the protocol. If A does not follow the protocol within a short-enough period of time then B will terminate or unwind the protocol.

There now needs to be some incentive for A to promptly sign Z by revealing the secret S after B has sent the the transaction crediting A, otherwise there's nothing preventing A performing the exhaustive search to spend the inputs of the transaction crediting B.
To solve this, we arrange that when A sends B the partially signed transaction A also sends an easier brute-force problem for B. When B constructs the transaction crediting A, he makes it so that it is alternatively redeemable by B if B has solved A's brute-force problem.
As soon as B sends this transaction to A he starts work on A's brute-force problem.

If A doesn't immediately sign Z by revealing S then B is very likely to solve A's problem before A solves B's problem. This means that B can recover the funds that were going to go to A and some time later A will solve B's problem and recover the use of the funds that were intended for B.

If A does immediately sign Z by revealing S then A must also publish a transaction which spends the transaction crediting A as B will be trying to solve A's problem and if B is successful before the A spends it then B will spend it instead.

So now B, knowing S can reveal the answer to the problem he posed A in order to allow the redemption of A's inputs to the transaction crediting B. B publishes A's transaction which credits him.

This isn't the clearest explanation nor am I sure that it's the simplest solution but I lack the time to improve it at the moment.

ByteCoin

I added this to the wiki, thanks.

Merging ideas?
https://bt.irlbtc.com/view/66274.0