Topic: Trust-free crypto-currency exchange with time-conditional scripts (Read 5578 times)

Merging ideas?
https://bitcointalksearch.org/topic/p2p-exchange-1x-and-nx-a-new-concept-in-the-block-66274

Please outline the significant inefficiencies.

My protocol can be executed approximately as fast as the relevant calculations and network communication take. This means that the brute-force problems which render nLockTime unnecessary, can be small. The brute-force problems need only be solved if one of the participants fails to complete the protocol.

Solving the brute-force problem is like waiting for nLockTime to run out. Giving the other party the solution to the brute-force problem is similar to broadcasting a final version of the transaction.

The time that your coins could be "held at ransom" can be made quite short and, if this is still considered unacceptable, an escalating setup can be envisaged so that both parties have to do roughly comparable amounts of work to "recover" their coins if the protocol falls through.

ByteCoin

I added this to the wiki, thanks.

Er that is quite different from how I read the earlier post.  Now it seems you are basically re-implementing nlocktime without nlocktime in a very inefficient way.

nLockTime alone, without tx replacements, has semantics everyone understands.  It's the same thing as a post-dated check.  Useless now, but will have precise meaning at a future time.

You're proposing, instead of using post-dated checks, I can use checks that we both are convinced will require me to perform some predictable amount of extra work before I can cash it.

This means that someone can still basically hold your coins at ransom, requiring you to burn money to get them back.

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'm not sure what the point of this is; as you point out, it is totally broken/insecure as A can spend the coins.  Clearly A should just broadcast transactions spending both outputs to himself.

You don't need TX replacement at all for the scheme I described, just locktime.  Locktime without replacements has obviously simple semantics: nodes ignore TX with locktime until that time arrives.

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 meant it conceptually. Hashes and public key systems are simpler and more intuitive as well as predating zero knowledge proofs.


That's a theoretical result which hides the impracticality of the implementation. This video explains (at the end) how a 200Mhz Pentium needs to send about 20MB of data and do a total of about 2 hours of computation to prove you hold the preimage of a SHA-1 hash. The problem needs to be implemented in terms of a boolean circuit and the proof is in terms of bit commitments to the values of the wires and manipulation of the commitments.

Jens Groth of Imperial College has recently published a succession of superb papers which bring non-interactive zero knowledge proofs of non-trivial statements into the realms of practicality. If Bitcoin were implemented in terms of operations on appropriate bilinear groups instead of straight elliptic curves and hash functions then schemes such as you describe would be more practical.

ByteCoin

Cool. I'm canceling my proposals that needed a new block chain for this same thing:
https://bitcointalksearch.org/topic/a-decentralized-anonymous-exchange-between-chains-31643
https://bitcointalksearch.org/topic/a-fee-only-chain-before-the-miners-reward-halves-32258

Please feel free to add this as another example to the Contracts page so it doesn't get lost in the forums.

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

Bitcoin was developed and is implemented using pre-zero-knowledge crypto technology.


I think that the incorporation of an appropriate generic zero-knowledge-proving scheme which enables such digital contracts would be revolutionary.


Can arbitrary functions f be proved in zero-knowledge? If not, what are the constraints?
Are the proofs non-interactive? If not, how many rounds do they take?
Is there a scheme for generating arbitrary zero-knowldge proofs? Can you send some references to relevant papers please?
Are all the proofs necessarily probabilistic?

Welcome to the forum!

ByteCoin

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)

oh wow now I understand, I guess nLockTime/tx sequences provide the same functionality (a bit harder to reason about for me; is there something you can do with locktime/tx seqs you can't do with time-conditional scripts?) .

This is quite great though, it means we can have decentralized p2p exchanges between e.g. namecoin/bitcoin.

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.

I see, perhaps the tx sequences and nLockTime already let you do these things.  I do not quite understand the sequence/nLockTime semantics, are they explained clearly somewhere you can link me?  And are you sure they are actually working now?  I thought I had read the "lock time" thing was disabled, and I remember reading the source a few months ago and seeing weird stuff like "non-simple" tx scripts containing more than 2 ops were disabled.

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.

i forgot PW to first account and it's not sending me email... mods pls unnoob this account instead of OP (you can check IP match).

bitlotto: AFAIK you can't condition on block number either in tx scripts.  Either would be fine I guess actually, could be nice to have both.

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

edit note, this stuff can be done without time-conditional scripts using nlocktime as explained in later posts.  still leaving this post so you can see protocol for untrusted exchange
Basically add an "if time < DEADLINE X else Y" condition to the transaction script format.  With this it will be possible to do untrusted transactions between other crypto-currenies as follows:

A and B want to trade bitcoin for blahcoin.

A and B pick keys, send them to each other, and also pick secrets secretA, secretB.   They send each other hashA = hash(secretA), hashB = hash(secretB)

A writes the following TX:

If time < DEADLINE1, spendable by providing:
   string sa s.t. hash(sa) = hashA
   string sb s.t. hash(sb) = hashB
   signature from pubkeyB

else:
   signature from pubkeyA

B writes the same TX to the blockchain for the other thing, with a deadline a few blocks later (so A has more time to spend it).

Now A tells B his secretA.  B can now be nice and tell A his secretB or be a dick and keep secretB to himself.  Infact, let's just say standard protocol is for B to keep secretB to himself.  The point is, B must reveal secretB to spend the coin, thus revealing it to A and letting him spend the other coin.

Once we get this, I can design all sorts of other untrusted trade schemes, but they all need a time condition.  (Unless I'm missing a way to do it now.. if you're smarter than me and see how to do it please let me know!)