Knowledge-Coin Fair Exchange

What this episode is about

The discussion features Sargis, a prominent figure in cryptography known for his extensive contributions to cryptanalysis and symmetric key security. Highlights include his groundbreaking work on vulnerabilities in major cryptographic schemes, the introduction of concepts such as padding oracles, and his pioneering research in provable security, particularly in metric cryptography, which has influenced both academic and industry practices, including recent adoption by Apple.

Key takeaways

• Sarge's cryptography career proves that breaking stuff can be a noble profession—especially vulnerabilities.
• Padlock oracles? Sarge unlocked TLS 1.2’s secrets and sparked the TLS 1.3 revolution.
• You can teach an old algorithm new tricks: Sarge's decorrelation was a game changer for symmetrically secure crypto.
• Trust issues? Even Microsoft fell victim to Sarge's signature ideas—proof that innovation can backfire.
• Fair exchange online: because chasing down digital fish thieves isn't as easy as it is at the market!

Who speaks in this episode?

• Saradini (Host) · 41 min speaking

What is discussed, and when

1. 0:00 – 5:00: Sargis, Apple Inc., EPFL, TLS 1.2
2. 15:00 – 20:00: Ethereum
3. 20:00 – 25:00: ZKCP
4. 25:00 – 30:00: Optis Swap
5. 35:00 – 40:00: Optis Swap, SOCK
6. 50:00 – 55:00: Ethereum

Notable quotes from "Knowledge-Coin Fair Exchange"

• So hello and welcome everyone. it's my great pleasure to host Saradini from EPFL today. so the almost all of you I think know Sarge but I would like to take this opportunity to briefly.

  about Sargis · at 0:03

• Notion of padding oracles which was actually used to break TLS 1.2 and led community to continue working on TLS 1.3. he has done a lot of crypto analysis work but also he has…

  about TLS 1.2 · at 0:55

• Covers lots of things he also had a lot of impact in industry as far as I know so recently Apple started using his short authentication strings idea which is a way to authenticate public keys.

  about Apple Inc. · at 2:00

• The blockchain is achieving. So I think that in Ethereum it's you need a trusted majority of the stakes this kind of thing. So it depends on what blockchain infrastructure you're using. Okay. So it's a property coming.

  about Ethereum · at 19:43

• So it doesn't it doesn't work it works for very small information. so one idea which is the ID used by ZKCP zero knowledge contingent payment is to reduce to the problem of…

  about ZKCP · at 23:01

• Okay. So the performance of optis swap are here. So for the description function they must use a miracle hash.

  about Optis Swap · at 37:09

• So what we did is that we built on this protocol to have something better hopefully. so that the sock protocol.

  about SOCK · at 38:27

Who and what is mentioned in this episode?

People

• Sargis — Person · Main guest / main speaker (cryptography researcher presenting work on fair exchange) · 1 mention · first at 0:06
  Central figure of the episode: introduced for his cryptanalysis and provable-security contributions, then presents new work on fair exchange and a startup effort.
• Claus Schnorr — Person · Referenced expert / referenced author of a broken hash function construction · 1 mention · first at 0:37
  Mentioned as the designer/author of a hash function (named in the talk) that Sargis reportedly broke during his PhD work.
  Primitives and constructions. His PhD I think was consisting of breaking some hash functions called FFTDH2 bar by Claus Shenor. He also broke some crypton cryp u public key…
• Shor and Revest — Person · Referenced authors (as named in transcript) of a public-key encryption scheme that was broken · 1 mention · first at 0:44
  Cited as proposers of a public-key encryption scheme that Sargis reportedly cryptanalyzed; the transcript likely intends well-known names but is ambiguous as written.
  Hash functions called FFTDH2 bar by Claus Shenor. He also broke some crypton cryp u public key encryption scheme proposed by shore and revest and he broke the reduced version…

Companies & orgs

• Ethereum — Company · Technology infrastructure · 3 mentions · first at 16:42
  Mentioned as a blockchain infrastructure that can be used for fair exchange protocols.
• Apple Inc. — Company · Industry impact · 1 mention · first at 2:04
  Mentioned as using Saradini's short authentication strings idea in their products.
• EPFL — Company · Affiliation · 1 mention · first at 0:06
  Saradini's affiliation, mentioned at the beginning of the podcast.
  So hello and welcome everyone. it's my great pleasure to host Saradini from EPFL today. so the almost all of you I think know Sarge but I would like to take this opportunity to briefly introduce him because I think it is.

Concepts & topics

• SOCK — Concept · Protocol · 1 mention · first at 38:31
  Mentioned as a protocol for fair exchange with a better dispute resolution.
• Optis Swap — Concept · Protocol · 3 mentions · first at 29:19
  Mentioned as an optimistic protocol for fair exchange.
• ZKCP — Concept · Protocol · 1 mention · first at 23:07
  Mentioned as a zero-knowledge contingent payment protocol for fair exchange.
• TLS 1.2 — Concept · Security protocol · 1 mention · first at 0:56
  Mentioned as the successor to TLS 1.2, developed after vulnerabilities were found.

Places & events

• AES competition — Event · Historical context · 1 mention · first at 1:38
  Mentioned as an event where Saradini participated with a proposal.
  Proved the duality between the linear crypto analysis and differential crypto analysis. He has been also in one of the participants of the AES competition where he I think was…

Full transcript with timestamps

0:03 So hello and welcome everyone. Uh it's my great pleasure to host Saradini from EPFL today. Um so the almost all of you I think know Sarge but I would like to take this opportunity to briefly introduce him because uh I think it is good to remind ourselves uh what he has contributed to the to the cryptography community. Uh Sarge is very well known as a cryp analyst. He uh found a lot of vulnerabilities in various different primitives and constructions. His PhD uh I think was consisting of breaking some hash functions called FFTDH2 bar by Claus Shenor. He also uh broke some crypton cryp u public key encryption scheme proposed by shore and revest uh and he broke the reduced version of MD4 and then later on he introduced the notion of padding oracles which was actually uh used to break TLS 1.2 and led community to continue working on TLS 1.3. uh he has done um a lot of crypto analysis work but uh also he has been

1:10 known as the pioneer of symmetric key cryptograph uh provable security specifically in this metric cryptography. Uh so what he did actually he introduced he developed the notion of or the theory of decorrelation which is not super known but it was a big deal back in the times I guess this is what I hear from people mostly and he also proved the duality between the linear crypto analysis and differential crypto analysis. He has been also uh in one of the participants of the AES competition where he I think was the only uh proposal black cipher proposal where he talked about um provable security in the sense of you know protecting against large set of attacks instead of saying oh we we are good against this attack we are good against that attack so he made made a very good proof that uh that covers lots of things he also had a lot of impact in industry as far as I know so recently Apple started using his

2:07 short authentication strings idea which is a way to authenticate public keys. And uh another thing maybe w not widely known or known by few people is that in 2020 Microsoft crypto API library actually introduced a vulnerability to uh for the attackers to take advantage of of the uh not very well taking care of the uh of the signature verifications. Essentially the contribution that Sari did was to the attackers. So the attacker exploited his idea that he introduced in 2004 uh in his paper of digital signature schemes with domain parameters where he essentially said that domain parameters such as the elliptic curve the description elliptic curve has to be part of the public key otherwise the public keys verifies against different curves. uh and attacker essentially use that to to exploit the exploit the library. So uh Saraj is a very uh humble and very reliable person in my opinion very I have been working with him

3:11 for 10 years and I hope to continue working with him. I'm learning a lot from him and uh he cares deeply about scientific rigor before I give it to him give the microphone to him I'm going to say two things that he kept repeating me for 10 years. The first thing is that ask your questions. Better to be clear than making assumptions. The second thing he kept telling me is speak up specifically when science is in on the at the stake. And he's a really uh I think influential perh person in my opinion for scientific rigor. Without further ado, I'm going to give it to thank you for joining again.

3:51 Okay. Thank you very much but so thank you for the introduction. So now I feel a lot of pressure. So uh thank you also for giving me the opportunity to to present my latest uh uh work which kept me busy. So it's about fair exchange. Uh so it's not something new. Uh so that's some work I did together with a new startup company. I'm involved in a creation of this startup company. It's called SEMA science and we are working on the problem of fair exchange and try to uh implement it. So first of all, so what is the fair exchange? So it's very old problem. So imagine that Bob is going to the fish market and wants to buy some fish to Alice. So Alice is studying fish. So for instance, he wants a seab bus. So X is a seab bus and Bob is willing to pay. So they agree that they would exchange a seab bus against some some dollars.

4:54 After their agreement essentially Alis gives a sea bus to Bob. Bob gives the money to Alice and after that they are happy and they they leave after the transaction. So that's an exchange. uh and when you are in a in a fish market uh this protocol is very nice because for instance if after uh receiving the fish Bob tries to leave without paying then maybe Alice can run after Bob and they can solve the problem by by brute force uh methods. Uh so this is normally secure in a in a fish market. Now when we try to do it online, it's not it's not uh the same uh uh the same uh at all uh because if Bob decides to interrupt the transaction after receiving the digital fish, there is no way to run after Bob. Okay. And it can be even worse. Maybe Bob Bob is honest or Bob can claim that he has sent a payment but somehow the network which was malicious decided not to complete the payment and send it to Alice. So in that case we

6:04 don't know who is correct. We don't know if Alice was honest if Bob is honest. So the prior exchange is to make somehow the exchange of the fish against the payment atomic. You don't want to be able to uh dissociate the transfer of the fish with the transfer of the the payment. So we want that either all the honest player receive what they expect during the exchange or no honest player disclose uh what was meant to the counterpart. So we want the exchange to be atomic. Uh that's a description of the fair exchange problem.

6:43 Um it has application. So obviously in a fair commerce. So if you talk about uh selling fishes uh there is a clear application for that. It has application also in a fair certified email fair certified main. You want to exchange essentially the delivery of a mail against a receipt. So you want to to you want Bob to sign a receipt saying that uh he has received the mail no matter what is the content of of the mail. So it it has to be a non-reputable receipt and you want this exchange to be atomic. You don't want Alice to re to get the receipt without delivering the mail to Bob and you don't want Bob to get the mail without giving a receipt. Uh you also have application with contract signing. So you want uh for instance two participants Alice and Bob to sign a contract and you don't want anyone to be able to leave the transaction with a signature of the counterpart without signing signing themselves. Okay. you

7:41 have many other applications. Uh so let's uh give some uh background about fair exchange and we will start by a bit of formalism because apparently I said that we have to be precise. Okay. So we we started we start by some private input. So Alice has some input X. Bob has some input Y. So imagine that X is a fish, Y is some money. And these uh inputs these priority inputs x and y they are characterized by some description. So Alice claims that uh x uh has a description dx and Bob is interested to receive something which has description dx. So dx is the image of x by some kind of description function. So we will have a description function maybe a hash function whatever. Uh so here dx could be could be could mean that x is a c bus of whatever waste and dy is a description of y for instance dy could be the characterization that it's valid money and that it has this amount of money so I don't know how what would be

8:57 the price of a se bus here in a in redund already the order of magnitude I don't know okay

9:06 $50 $50. Okay. So let's say dy says that y correspond to some valid money with within a amount of $50 and dx is cbatas. You we you have some outputs o a for alis o for Bob. Uh the protocol must satisfy the timeliness property. We want that every honest participant eventually terminates. We don't want anyone to be blocked forever in a in a transaction protocol. We want effectiveness. We want that if A and B are honest and if DX is exactly the description of X and DY is the description of Y then at the end of the protocol O A is equal to Y and OB is equal to X. So they exchange X and Y but in the other cases we want that O A and OB both to return some error. Okay. So we have those two uh terminations uh possibilities for the protocol. That's in a case where where A and B are both honest.

10:05 In the other cases, so when there is even in the case of a malicious behavior when Alice is a honest player, we want either there is no leakage on X. She didn't disclose anything about X or the description of what she received at the end is equal to DY. So she's supposed to be happy when she receives something with the description dy. Uh and in the honest case it's similar. So we want either there is no leakage on y or the description of ob is equal to dx. Okay. So we want this fairness property. The fairness property says that we have those two conditions satisfied.

10:50 Uh so in this talk we focus on the knowledge coin exchange. So X is some knowledge. So it will be a digital fish and coin is some payment. So we want to exchange some digital information against a payment. So X is some digital information. DX is a result of applying X to some description function. It can be a hash function. uh ny is some uh payment and dy will characterize what is a valid uh valid payment and which has the the correct amount. Uh maybe uh when we say no leakage on y we may wonder what it means for no leakage about the payment here in that case it would means that the money uh is kept by Bob. No leakage of y means that Bob is keeping the money.

11:42 Okay. So that's uh for the formal introduction. Uh now the the problem of fair exchange it has been a very longlasting problem and one of the early result by in 90 1990 by even and Jacobe so I don't know if anyone so do you remember Jakobi? Yeah he was a former MSR person. Uh I don't know when he left MSR. [sighs]

12:10 15 years ago. 15. Okay. Uh so in 1980 they have proven that fair exchange is impossible. Okay. Fair exchange is impossible. Essentially the idea is that there is always one participant who is the first to be able to get whatever they expect at the end. They they have enough information to reconstruct what they expect and they can decide to stop the protocol at this time and the counterpart in a protocol doesn't have enough information to reconstruct what they expect. So that's essentially the idea of the proof. So it must be unfair for at least one participant in all the cases. So that's when we have only two participants. So the uh interpretation of this impossibility result was to say that we need a third party to achieve fairness.

12:59 And if we have a third party uh if it is a third party which is not trusted it's for instance if we are in a case where alist is malicious and we have a third party who is malicious as well it's as if we had a single malicious alis. So if this third party is malicious it doesn't bring anything new. So we this we need a trusted third party. With a trusted third party we can have fair exchange protocols. Uh now if we imagine that we can rely on a trusted third party the problem of fair exchange becomes trivial because we can have this protocol where Alice gives X to the trusted third party. Bob gives Y to the trusted third party. The trusted third party verify that everything correspond to the description and then a trusted third party redistribute Y to Alice and X to Bob.

13:50 Okay, the problem is trivial. So that's back in 1980. So you may wonder why we are still talking about it. So it's because trusted third parties they are very complicated uh not always available expensive and we want to do something better. So in the late 90s people start introduced a notion of optimistic fair exchange. The notion of optimistic fair exchange consisted of saying that we will have a protocol which made two phases. the optimistic phase and maybe an additional phase which is a dispute resolution with the property that the optimistic phase is very cheap and maybe there is no need for a trusted third party during the optimistic phase and uh if everyone is honest this phase is enough we can stop in this phase so if everyone is honest we have very cheap execution of the protocol but if someone deviates from the protocol then we may run to a dispute resolution and this dispute resolution may be more

14:55 complicated and involve the trusted third party. So in the case of the trusted third party typically uh the optimistic uh protocols involve the trusted third party only during the dispute and we can have protocols like this which are very cheap during the optimistic phase with a complicated dispute resolution. Okay. So, uh something more about impossibility. In 1999, uh uh some people have proven uh uh essentially the connection between fair exchange and consensus. They have proven that if we built a fair exchange protocol, then we can build a consensus protocol out of the fair exchange. And you also have some kind of impossibility result for consensus. uh uh in 1985 there there is there was a FLP serum saying that consensus is impossible under some conditions uh and therefore fiction should be impossible as well but okay so if we satisfy the condition but outside of this condition maybe it's feasible but

16:04 we know now that consensus protocol are very complicated so it's not so easy to achieve a consensus protocol so this result somehow means that the complexity should be the same for fair exchange protocol. So now the question is instead of having trying to develop a protocol which is very complex why don't we use implementation of the consensus protocol because we know that consensus has been implemented. you have many uh many infrastructure which are doing consensus many days uh many times per day on a global scale like the bitcoin infrastructure or the ethereum infrastructure and those uh infrastructure could be used to do some fair exchange so that's uh the idea uh we want to uh go to so what can can we do with an infrastructure uh solving consensus typically You can have smart contract. A smart contract is some kind of trusted execution platform.

17:09 But unlike the trusted execution platform which exist in in hardware in in micro uh microprocessors uh those uh those uh trusted execution platform are extremely expensive. They are very expensive. Every time they run something, you need to spend some gas. You need to pay for the gas and they are extremely slow. So it's a very inefficient platform. Uh so that's uh that's bad news. The good news is that it's very trusted. It's immutable. It will do only what it has been programmed to to do and you cannot re uh revert the the computation. when the computation is done uh you cannot claim that it was not done you cannot undo it so it's immutable uh there is another bad news is that it's fully transparent so smart contract does uh execute some code in a total open environment everybody can see uh what this platform is doing and in particular this uh this smart contract cannot manipulate secret it cannot use

18:23 secret keys because everybody will see the secret key when it uses the secret keys. So a smart contract is a trusted execution platform which cannot sign otherwise everybody would see the signing key and which should not receive any private information otherwise everybody would see this private information. Okay. So that's the kind of trusted third party that we want to use. So you see that the difficulty now is that you cannot use the protocol that we suggested here like give everything to the trusted third party because at this this stage here so Bob can see the X sent to the TDP and just take it so Bob can see it take it and uh and leave without paying for the payment it's another story because once the payment is done the infrastructure uh in a blockchain is making sure that the payment cannot be undone. Okay. But for the digital information, you can steal it from the smart contract. So you

19:25 cannot directly use this type of protocol. So can I just ask what assumptions are you adding for immutability? Is that trusted uh honest majority? [sighs]

19:37 So that's uh blockchain. So what whatever the blockchain is achieving. So I think that uh in Ethereum it's you you need a trusted majority of the stakes uh this kind of thing. So it depends on what what blockchain infrastructure you're using. Okay. So it's a property coming from the consensus. So but in this presentation we just assume that the consensus works. It's secure.

20:07 Yes. So when you're exchanging like some a digital good for money, are you assuming that that's this whatever the underlying cryptocurrency is or is it like flexible?

20:15 It's is in a cryptocurrency. Yes. So it wouldn't generalize to like exchanging other digital goods or anything else is is your is your scheming specifically for good versus

20:26 Okay. So precisely we want to transmit some uh digital information which is characterized by functions that we can implement. So we cannot say I want to exchange a C bus

20:40 against something. But I mean can you say could you exchange two digital files or it has to be currency on one side and a file at the other?

20:47 Two no it's one file against a payment. Yeah. And one file against another file. It's more complicated.

20:55 Much more complicated. So we here we are in the simple case knowledge against a payment in cryptocurrency. So

21:05 yes are you trying to design for the optimistic case or uh yes so I will come back to the solutions that we we have. So what do we have essentially there exists two approaches which already exists. So one approach is based on zero knowledge. So I will briefly go through zero knowledge and the second approach on which we focus is the optimistic approach. So let's first look at what we can do with zero knowledge. Uh so the idea of uh uh protocols based on uh zero knowledge is the trivial ID using a trusted third party except that we have to make sure in which order we are doing this. So we do it by first having the buyer to pay to deposit the money in a trusted third party and then we can uh so the the vendor can see that the payment has been made on a smart contract. So the vendor doesn't have the money yet but can see that the money is there and either nothing happened and the money returned to the buyer or the

22:08 vendor puts X on a smart contract. The smart contract verifies that it correspond to the description and if it does then the buyer can see it and the exchange is complete for the buyer viewpoint and uh the money can be sent to the vendor. Okay, so that's the idea of the protocol but it's not so simple. So it's it's very secure. So it works. Uh there is a problem with privacy because now everybody can see X. It's not only Bob can see X but everybody else. So you have problem with privacy. And for the complexity, it's also a big problem. If X is a file of say 1 GBTE, you you cannot put one GBTE on a blockchain and expect a smart contract to do some processing to to verify that this one gigabyte is correct.

23:01 So it doesn't uh it doesn't uh work it works for very small information. Uh so one idea uh which is the ID used by ZKCP zero knowledge contingent payment is to reduce to the problem of exchanging something small. So how it is done? Uh essentially the vendor will pick a symmetric key. The vendor will hash it and then encrypt X with this key to obtain cipher text and then the vendor will send the hash of the key the cipher text and a zero knowledge proof of knowledge of X and K such that the hash of K is H. The encryption of X under key K is CT and the description of X is DX.

23:47 After that the buyer is convinced that if he gets some pre-image of H, this pre-image of H will help to decrypt the cipher text and obtain some X which has a correct description. Okay. So now the problem boils down to exchanging a pre-image of a hash against a payment. And then we can use the idea of the previous slide. put the money on a smart contract and then put the key on a smart contract. Then the smart contract verifies that the hash correspond to H. So the H was put by the buyer. So the buyer receive H and he say now I want to exchange my payment against the pre-age of this hash. So smart contract can verify it and if it works he makes a payment to the vendor uh and it's u and the buyer gets what they expected. It's secure. Now there is privacy because also anyone can see the key in a smart contract. This communication here it can be done privately between the vendor and the buyer. So the cipher text can be sent

24:55 privately means that we encrypt the cipher text a second time. So uh for observers the observer will see the key but will not see the cipher text. So x is safe and for the complexity so now for the complexity in terms of gas it's very nice. The smart contract only has to receive some small key a symmetric key and to verify the hash of this key. That's something which is reasonable. But the complexity goes here to the zero knowledge proof. So it's a more classical complexity. So now if you have some file of 1 GBTE and you want to have a zero knowledge proof like this, I guess that you're familiar with zero knowledge proof, it won't be so easy. Okay. So uh and this type of protocol was improved. So last year at CCS there was a presentation uh of a new protocol which is based on this ID where essentially they use a very specific hash and a very specific encryption and a very specific description. Okay. So the description

26:02 that they use is a polomial commitment. Uh the hash it's something which is derived from their construction. I don't remember and the encryption is some kind of verifiable encryption. So here you have some kind of verifiable encryption which starts from the description of X and X and which returns many things. So VK is some kind of hash of the key. So the key is something created during this verifiable encryption to obtain the cipher text and you also have a proof so that the buyer can verify the proof and the smart contract will only verify the key with this VK. So they have some kind of construction uh that they call they call they call it a ve it's some kind of verifiable encryption and with that what they reported is that uh okay so first the description function that they use is based on this uh uh vector commitment kg you cannot use another description function the amount of that they need to run the

27:16 smart contract is uh something as 300,000 which is something which is very reasonable. Uh so I think that when they did the estimate last year they obtained something like $10. So maybe it's not so cheap but it's still reasonable $10. So if you want to buy a digital fish of $50 so maybe that's the overhead. uh but nevertheless the gas price has dropped very has dropped a lot and I re I did the computation yesterday and I obtained 20 cents. So here that's represent a cost of roughly 20 cents for the gas price. So they didn't specify the uh gas the gas amount that they need to deploy the smart contract but that should be something within the same order of magnitude and they reported their uh uh their performance to exchange some x of 128 kilobytes that's reasonably that's very small 128 kilobytes and they obtain this complexity for the vendor and the buyer.

28:21 So the vendor need to spend 89 seconds to create the encryption and the proof and the buyer needs 34 second to verify the proof. So it's very long uh and it's the complexity is linear in the size of X. So for the size of X here you can see that it's very small. If you try uh to estimate how much it would cost for one gigabyte, it would take three days of computation for the buyer. Okay, so that's not something which is uh reasonable. Maybe one good news is that the vendor can amortize the cost if he wants to sell X to many uh buyers. Okay, the proof has to be done only once. That's the only good news here. Otherwise, the complexity is quite a lot.

29:14 So that's for the techniques based on uh zon knowledge and now for the optimistic approach. So we have a protocol called optis swap. Optis swap uh is an optimistic protocol and it work in two phase. First there is the optimistic phase where essentially the vendor will pick some key hash it encrypt x. So X will be cut into pieces and all the pieces will be encrypted and you send the cipher text to the buyer and the buyer doesn't have anything to verify. It just receives a cipher text and it's some symmetric encryption. It's nothing complicated. And in addition to this, the vendor put in a smart contract, the hash of the key, the description of X, and also some kind of commitment on a cipher text. And this commitment will be a hash obtained by a Merkel tree hashing. So you put all the pieces of cipher text in a Merkel tree.

30:10 You take the value of the root and you put this root in a smart contract. So the buyer can verify that this R is correct because the buyer has received CT and can do the same computation and verify that R is correct and if it is uh then the buyer will make the payment to the smart contract the vendor will verify that the payment is made and either nothing happened and the uh the uh protocol aborts by returning the money to the buyer or the vendor puts some key on a smart contract. The smart contract will verify that the hash uh is correct here and then the uh buyer will get the key will be able to decrypt the cipher text and to verify the description. So far the smart contract cannot verify anything.

31:01 So either the buyer is happy and the buyer can do either nothing and eventually the money will go to the vendor or the buyer tells to the smart contract that he's happy with what he has seen and uh it it tells the smart contract to make the payment to the vendor. But if the buyer is not happy.

31:24 Yes. Why do we need R there? R. So we will need R later in the next phase. So you need to commit on the cipher text. You the cipher the the smart contract need to have some kind of trace uh corresponding to the cipher text because later the vendor will claim I've sent you this value and the smart contract need to verify. This is why we use a miracle tree. Thank you.

31:52 So if he's not happy uh then he must launch a dispute uh dispute protocol. If there is a dispute so the money will be frozen and we go to the dispute resolution which is more complicated. So let's see how the dispute resolution works. So assume that we have implemented the description function in a form of a circuit. So we have a computational circuit where the leaves of the circuit are the x i's the pieces of x and the root the value of the root is dx. So let's say that the root is node a at the beginning of the dispute the vendor claims that if he evaluates the circuit on x the value of the root is equal to dx but the buyer claims that it's not the case.

32:37 So the vendor claims that the value of this node is something and the buyer disagree then the vendor okay so if you look in the circuit then this this node has two sons let's say B1 and B2 the vendor can claim the value of B1 and B2 the smart contract can verify that if we take we take the claim value for B1 and B2 and if we apply the gate which is on this node you obtain the claim value A and if it is the case then the buyer must say so since since the buyer disagree with this value he must say on which value he disagrees. So maybe he disagrees with both value but he has to to sell at least one value on which he disagree. Let's say he say he says I disagree with the value of B2 then we can iterate and open the sums of B2 and iterate until we reach a leaf. So we will have some a number of iteration which is linear in the depths of a circuit. So yes

33:39 uh in here there is no one malicious right who is when the dispute resolution is gone someone is someone has to claim the other one is malicious right?

33:48 Yes. Okay. So like here I'm describing what they should do if they are honest but we already know that someone is malicious. So maybe someone is deviating and we don't know who

34:00 and the the goal of the discretization that the smart contract needs to figure out who is correct. So here the vendor announce some values here. It doesn't matter what strategy the vendor is doing. The smart contract verifies it and the uh and the buyers is doing the same computations and they essentially try to reach a leaf on which they disagree. It doesn't matter what they do exactly but at the end of the protocol they will reach a leaf and essentially the vendor will claim I claim that the value of this X I is equal to V and the buyer will will disagree

34:39 who pays for the smart contract. Okay so maybe I will come back to this. Okay, that's a good question. Uh so yes, so the price of the smart contract is is also a concern. But here let's look at how it works by assuming that the blockchain is uh free. Uh so here when we reach the leaf so the vendor will claim here is the value corresponding to x i in the cipher text. The smart contract still doesn't know what is a cipher text. So now the vendor say the piece that he had in a cipher text and he also prove it with the Merkel tree that he used before. So here this is where we need the R value.

35:28 So the vendor announce the value of CTI and proves it the uh connection with the R which was sent here and then uh the smart contract can decrypt the CTI and verify that it matches the claim value V. If it is a case then the smart contract decides that the vendor wins otherwise the buyer wins. Okay, that's how we resolve a dispute and we can prove like this that uh the the protocol is fair like a honest participant cannot be deceived by this protocol. Uh so now the complexity depends on the depth of the circuit. So it really depends on what circuit we implement. So remember that this circuit implements the description function that we use.

36:26 So if the description function of X is a hash. So what the author use is that they use a Merkel hash. So they use a description function which is a Merkel hash of X. So if you want X is ABC CD, the circuit will look like this. Okay, it's a very nice circuit, very balanced. uh and in that case the depth is logarithmic in the size of x. Uh if we use shot 256 then the circuit looks like this and it has a depth which is linear in n. So in that case the complexity is terrible. So here it's logarithmic here it's linear.

37:09 Okay. So the performance of optis swap are are here. So for the description function they must use a miracle hash. they don't have so or anything which will get balanced circuit the amount of gas they need for the smart contract has the same order of magnitude so here there is a cost for the deployment and the cost for running uh it's actually cheaper than uh than the FDE so that's for the optimistic part and for the dispute resolution you need some extra uh contract here 2 million gas to deploy and two and a half million roughly of gas to run when X has one gigabyte. So now we can work with one GBTE and the amount of gas we need is not too crazy and it works but we need to use the Merkel hash and we we don't have so much freedom on the description function. If we try to use SH 256, the cost will be multiplied by 700,000. That would be n / log n. Okay.

38:20 Uh and that's uh that would be an instant price. So here come what we did. So what we did is that we built on this protocol to have something better hopefully. Uh so that the sock protocol. So SOCK uh S O X. So X is for exchange. So it's a knowledge coin fair for exchange O for optimistic. Uh now we have a better dispute resolution. It's better in the sense that the complexity is logarithmic in the size of the circuit and not only linear in the depths. So and whatever the circuit so it's universal. You can use whatever description function you want and the complexity will be logarithmic in the size of this circuit even if the circuit is completely imbalanced. And the S is for the notion of sponsor. So it's answer the question who is paying for the smart contract. Okay. So we'll come back to this. Uh the notion of sponsoring is to favor economic inclusion.

39:22 So how does it work? Uh so the idea is very similar to optis swap. So first we need some uh agreement some pre uh preliminary phase where we agree on some terms of the exchange. The agreement must include the description function typically the circuit that we will use and the the the amount to pay. So we will commit to the description the description function and the uh the uh price of the transaction. We will encrypt it with symmetric encryption with a random key and then we will have a commitment. So it's a commitment on a hash of the circuit and a hash of the cipher text. So now we will put the description of the circuit in a ML tree to obtain this hash and the cipher text in another ML tree to obtain this hash and we will commit commit to those hash and we give also the opening information to the buyer so that the buyer can verify that we commit to the right thing. uh so we commit to CT we commit

40:30 to the description circuit then the buyer after verifying the commitment will make the payment on a smart contract and we'll put the commitment value on a smart contract the commit value is something which is very small then if nothing happens the money is returned to the buyer and if something happened it can be that the vendor deposit a key on the smart contract if the key is deposited on smart contract the buyer can see and uh check that if it correspond to what they expected. So the buyer can try to decrypt city and verify the description of uh what is obtained. So either the buyer is not happy and launches the dispute and then we go to dispute resolution but if nothing happen after a while the money goes to the vendor. So it's very similar to of this one.

41:23 So what is uh new is dispute resolution uh which is uh uh a bit different. So now imagine that you have the circuit which implements a description function. So you have some computational gates. You have the value of x and the circuit can be totally arbitrary. So you need some description of the circuit. So let's imagine that you have here gate which depend on x1 x3 a gate which depend on x2 x3 g3 depend on g1 g2 etc. And then you reach a root. Okay. So this circuit when you try to evaluate it you will evaluate the gate in some specific order. So the order is not so important but it must be an order which is computable. So you need the two participant to decide on which order they will evaluate the gate and we will linearize the computation by putting all these gates in this order. So here we put the gates in the order where they are evaluated. So here G1 depends on X1 and X3, g2 depend on on X2 and X3 etc.

42:28 So every gate depends on what was computed before. So we put all the uh gates in this order. Okay. So now uh the idea that we had is that uh we put all the values that we computed until the gate gi in some accumulator. So we will use some cryptographic accumulator to obtain a value wi for every index i. So wi will kind of commit on all computation which were done until the evaluation of gi. So at the beginning of the dispute resolution essentially they agree on W0 is the accumulation of the empty list. They agree on the accumulation of vacuum but they disagree of the accumulation of all the gates. So there is a there is something where they deviate. So they agree on W0 they agree on WN and in this protocol the buyer will say okay so I will claim what is the value at W N half and the vendor will either agree or disagree. So if the vendor disagrees so now they agree on W and they disagree on

43:38 WN half. So the buyer can claim the value for WN4 and maybe the vendor agree so now they agree on WN4 they disagree on WN2 and they can continue by can cut and choose. Yes. What is your definition of an accumulator? This is

43:55 the accumulator. It's a cryptographic accumulator and we can use again a Merkel tree for instance or RSA accumulator.

44:03 It has to be like deterministic I guess. Yes. Exactly. Yes. So we use a deterministic accumulator.

44:12 Is it I'm just trying to think like is it different from like just a hash? Is it's

44:17 it's some kind of hash. Yes. Can we can I just think of it as a hash or do you need extra?

44:21 Uh you need some extra properties. Uh what you will need at the end. So maybe let's see what is happening or something the elements or associativity of some sort.

44:34 So in the end you will have to claim many things. So when you reach a point where you agree on everything until the gate GI minus one and you agree on what is GI, you need to prove you need to disclose what is happening on this gate. You need to uh to to make the consistency of the value of the sun with what is inside here and you need to be able to prove that wi is obtained from what is obtained wi minus one by just adding one more value

45:06 any so it's some accumulator where you need this extra proof and you could always do that with a hash function just by revealing all the inputs but you want to make sure

45:17 so if you have a hash function where you can say that the hash of everything minus one piece uh plus the last piece gives the last the hash of everything then it works here. Okay. So that's uh our dispute resolution and then we implement it. So we have a amount of gas which is maybe a bit more expensive but which is very similar. It's a bit more expensive because we wanted it to be universal. Uh and I think that we are we've missed some some optimization here. Uh when we run the verifier on the buyer, okay, it's a bit slow here. So we tested for 4 megabytes.

46:04 So that's the maximum we could try because we implemented everything in a browser. So it's implemented in JavaScript which is not super fast. Uh so you can see the result here and we were limited by whatever the browser is able to handle as a file. So we tested it up to 4 megabytes but when we want to test with one GB we have to implement another client.

46:28 If you use the Merkel tree as a description function do you still get better than

46:33 uh we didn't try that. Uh but the Merkel tree uh is meaningful here where we look at the dispute and when we look at the dispute the cost of deployment for the uh for the uh smart contract with a dispute resolution is very similar. The deployment is independent on the size but for the execution it depends on how many iteration you need. So here uh apparently it's more expensive than here but it's because it's universal. We didn't want to have a smart contract which works for a specific description function. We have smart contract but we can feed this smart contract with the description and it will run.

47:20 And here that's uh the amount of time which was spent in total by the verifier and the buyer. Okay. Uh so I think I'm running out of time. Uh so what we added also is a notion of sponsoring. So for sponsoring what we wanted is that we wanted to make sure that the vendor would not pay any fee. And if we use a previous protocol the vendor must pay some fee when they put a key in a smart contract. When you put something in a smart contract you need to pay some fee for this uh uh this message. And we don't want also the buyer to pay any fee if for some reason the protocol terminates and aborts.

48:07 Okay, we want the buyer to be able to to spend the money to receive some X and uh and not to spend any money if it doesn't work. Uh so for that reason we introduce the notion of sponsors. So now the sponsor will pay for the fees of the transaction on a blockchain. We will have several types of sponsor. We will have an optimistic f sponsor. This optimistic sponsor is the one taking risk. There is no nothing for free here in the blockchain. Someone needs to pay for the transaction even if the protocol aborts. So if we don't want the vendor to pay and we don't want the buyer to pay, someone else needs to pay. So that would be the optimistic sponsor. So this optimistic sponsor is paying by default all the transaction which happen uh here during this smart contract. So this input this input and and this input there will be paid paid by a sponsor.

49:12 Uh so it's not a big amount but it's paid by by the sponsor and this sponsor is taking risk. So he's investing this payment uh and in exchange he has a promise to receive some tip if the exchange succeeds. So if the exchange succeed the optimistic sponsor makes some profit and we have some other types of sponsor for the dispute resolution which is more expensive. The dispute resolution has more iteration. It is more expensive. We will have a sponsor for the vendor and a sponsor for the buyer. And for those sponsors uh the uh decision to sponsor will be without any risk in the sense that whenever a sponsor is honest and decide to sponsor is ensure to uh make some profit in the end.

50:05 So when there is a dispute there is always someone malicious and we don't want h sponsor to be penalized for for that. So now we have five participant. We have a vendor, a buyer, optimistic sponsor, the sponsor of the vendor, the sponsor of the buyer. The sponsor of the vendor and the buyer are appointed only when the buyer triggers a dispute. So here is the protocol how it was uh in the previous slide and now we introduce the optimistic sponsor which is at the beginning paying some deposit uh to sponsor all those transaction here.

50:43 And now the buyer pays Y plus some tip. And if there is a cancellation, the money is returned to the buyer. Otherwise, if if it completes, then Y goes to the vendor and the tip goes to the sponsor. I didn't put the arrow of the tip to the sponsor. Okay? And for the dispute sponsor, they appointed here. So when the buyer triggers a dispute, he needs to find a sponsor to sponsor the dispute. Then the sponsor for the buyer will deposit some money and if it aborts the money is returned immediately. Okay. So when the sponsor of the buyer is declared here, then the sponsor of the v vendor must also put some money.

51:28 This money is supposed to cover the expenses of the dispute and they both pay. So it means that at the end uh the one who wins will get the money back and we also get the leftover which is unspent from the other. So we need the we have the winner takes all uh approach. Okay. So now we have uh this sponsor and uh the dispute resolution is almost unchanged but now we have an addition problem. Yes. Okay. So I will speed up. Uh so we know that in a dispute resolution a honest participant cannot lose but what can happen is that this dispute resolution is run by two malicious participant and in that case anything can happen. What can happen is that maybe the vendor and the buyer are both malicious.

52:19 Maybe the vendor has some good argument when he is looking for a sponsor for the dispute resolution. So maybe the sponsor of the vendor is honest but the vendor is malicious. sponsor of the vendor was convinced by the argument of the vendor and decided to support the dispute resolution. But during the dispute resolution uh they agree that B would win and in that case the sponsor of the vendor is losing money. So for that we need to modify a bit the dispute resolution by saying that at the end of the dispute resolution if a sponsor loses they can restart the dispute and take the rule of the participant that supported and if they're honest they will win.

52:58 But something else can happen. Uh this something else that maybe in the same configuration now let's imagine that they decide that V wins and the sponsor of the buyer who is by the way also malicious decide to say oh I'm not happy by the output of this dispute resolution and I want to restart it and take uh uh the rule of the buyer and now they decide that SB will win then SV still loses money. So we need again a way for the sponsor of the v vendor to take control and to restart the dispute resolution uh if this happens. So we can prove that with maximum three execution of the dispute resolution we can restore fairness even for the sponsors.

53:43 So that's the tricky thing for the implementation. We have a problem because the notion of sponsoring in blockchain is very recent. So I think it has been just been implemented in Ethereum Ethereum but we didn't we were not able to try it yet. And so to conclude [clears throat] so we have some knowledge coin fair exchange uh which is solved thanks to the smart contract used as a trusted third party. We have a protocol sock uh which works with any description function not only a Merkel hash and we also introduce a notion of sponsor for economic inclusion. So now vendor doesn't need to have uh any digital currency to be able to receive some payment to sell some item. Thank you very much.

54:42 questions is the dispute protocol like does it work with any any other domain or is it just specific to this fair exchange thing?

54:53 So uh actually that's a very good point. So this this is a description of the protocol in the case of fair exchange but this type of dispute resolution is used in some other context like for instance for smart contract offloading. So you have like for instance the L2 layers, the L2 blockchain layers. Uh they they want to reduce the the fees that people pay for transactions on a blockchain. And the idea is that they don't want to put everything on the L1 blockchain. So they want to do everything uh executed by normal uh participants, normal computers.

55:32 Uh but if someone is malicious, he can claim something which is wrong and the other and he has to to to there is a disagreement on the uh execution of the smart contract in that case and they need to restore with a dispute resolution and the dispute resolution is used in that case to restore a dispute in a smart contract offloading and it works in a very similar way. So that's what is done in the arbitrum blockchain. Yes. So [clears throat] I was struck by how similar what you designed looks like credit card transactions with two parties a period where uh you may have a dispute and then the ultimate settlement right because when you pay with a credit card at least in the US it's not effective immediately that the money is moved you have like some time

56:23 and it seems more like a better version of the credit card system or at least one with like more formal dispute resolution processes. Was that an inspiration or is it just a coincidence that it looks like it?

56:36 I think I think that the analogy with credit card is is a bit problematic because with credit card there is a a central authority.

56:47 Yes. Usually we trust the central authority. Okay. And here we don't have the central authority at all. So essentially the the central authority will decide who is right. So we say no we didn't make the payment we have to contact this central authority and based on some uh risk analysis so the central authority will say oh I don't want to look into this and I will just refund a customer uh or they will say no give me a proof so because people are supposed to be responsible for the payment on their credit I I don't know about the US but at least in Europe we are all responsible for whatever happened on our smartphone our credit card if something if if we are under attack so we are still responsible for that.

57:38 Thank you everyone.

Questions about this episode

Who speaks in "Knowledge-Coin Fair Exchange"?

Saradini (Host).

What is "Knowledge-Coin Fair Exchange" about?

The discussion features Sargis, a prominent figure in cryptography known for his extensive contributions to cryptanalysis and symmetric key security. Highlights include his groundbreaking work on vulnerabilities in major cryptographic schemes, the introduction of concepts such as padding oracles, and his pioneering research in provable security, particularly in metric cryptography, which has…

What is mentioned in this Microsoft Research episode?

11 people, works and ideas are mentioned, including Sargis, SOCK, Ethereum, Optis Swap, Apple Inc., ZKCP. Each one on this page links to its own page with every episode that mentions it.

How long is "Knowledge-Coin Fair Exchange"?

The episode runs 58 min; the transcript is about 9,083 words in 83 timestamped sections.

More from Microsoft Research

• All analyzed episodes
• People mentioned on Microsoft Research
• Topics mentioned on Microsoft Research