In this thesis we discuss the construction and our implementation of a protocol that allows two independent parties a fair exchange of private solutions of NP problems without a trusted third party. The protocol allows verification of solutions of a NP problem using zero knowledge and ensures fairness of exchange, i.e., if one party quits the protocol early, then the two parties must invest comparable amounts of time to retrieve requested solutions. Verification of solutions is based on the garbled circuit protocol and the fair exchange is formed on timed commitments. Our focus was on exchange of messages with respect to the preimage problem of cryptographic hash functions. Assuming that we have enough bandwidth available we are able to exchange shorter messages.