Risk mitigation for fully offline payments

Background

Motivation

I got an opportunity to think about fully offline transactions and it seems there is a real demand for it. Especially for the offline event, we see the people don't get enough bandwidth to pay at the shop even if a mobile internet provider brought the antenna and they end up using traditional cash. This method is not 100% complete but it's a good start to think about it as we assume the condition that we are dealing with are the network glitches or congestions. Also I wanted to go through the power of zk-SNARKs and RSA signature to see how they can be applied to real world applications that can be understandable for non-cryptographers. Let's dive into it.

Prerequisites

We need to make transactions possible when both the user who wants to use the coins previously bought online and the merchant who receives the coins are completely offline.
User experiences need to feel natural like traditional QR code payment.
Either the user or the merchant can be trustable.

Limitations

Even though we mitigate the risks, there is no way we can make these transactions to be as safe as a normal payment transaction system due to our expected conditions.

Both the user and the merchant are offline.
Which means no trusted third party can be involved and no broadcasting mechanism when they communicate.
The user and the merchant use traditional smartphones to interact. Any kind of additional devices or cards cannot be acceptable. (no TEE)

User flow

Tradtional

UserA charges coins online.
UserA goes to the store.
UserA scans QR-code at the store.
UserA types the amount of the coins that need to be paid.
UserA shows the screen to the merchant.
UserA swipes the toggle and rings the success tone.

Proposal for offline payment

UserA charges coins online.
UserA goes to the store.
UserA scans QR-code at the store.
UserA types the amount of the coins that need to be paid.
UserA shows the screen to the merchant.
MerchantA scans the QR-code that is shown on the user screen.
success

What data in the QR-code

Proof of the user identity.
Proof of the user balance exceeds the number that user is trying to pay.
Signed transaction.

Method

Focuses on how the data in the QR-code is created. Basically we combine the RSA signature and zk-SNARKs proofs to realize secure and privacy focused payment.

Participants

$T$ : Trusted Server
$M$ : Merchant
$U$ : user

Definitions

$S i g n_{T} (M)$ represents $M$ will be signed with $p r i v k e y_{T}$ .
$H a s h (M)$ represents $M$ will be hashed with MiMC hash function.

How the proof of the user identity works

Prepare phase (online)

Sharing the key to the public from the trusted server.
1. T publishes $p u b k e y_{T}$ to all the parties for signatures.
Sign the pubkey that the user owns to give the ability to prove itself for the user.
1. U creates keys and sends $p u b k e y_{U}$ to T.
2. T creates a signature $S_{T U} = S i g n_{T} (p u b k e y_{U}, U s e r I D)$ and sends it back to U.

Payment phase (offline)

User proves itself to the merchant.
1. U creates a signature SMTU=SignU(timestamp) and sends it to M along with:
  1. $p u b k e y_{U}$
  2. $U s e r I D$
  3. $t i m e s t a m p$
  4. $S_{T U}$
2. M verifies as follows:
  1. $S_{T U}$ is valid and signed by T.
  2. $S_{M T U}$ is valid and signed by U.
  3. $n o w () - t i m e s t a m p < e x p i r a t i o n t i m e$

How the proof of the user balance works

Prepare phase (online)

Sharing the keys to the public from the trusted server.
1. T publishes $p u b k e y_{T}$ to all the parties for signatures.
2. T publishes $P K (p r o v i n g k e y)$ , $V K (v e r i f i c a t i o n k e y)$ to all the parties for zk-SNARKs.
Sharing the circuit of zk-SNARKs that proves the user has more coins than the number that the user is trying to pay.
1. T publishes the circuit to all the parties. (See later section.)
Generating a commitment and a signature to prove the coin amount of the user.
1. (See later section.)

Payment phase (offline)

User proves holding more coins than the number that the user is trying to pay.
1. U creates zk-SNARKs proof.
2. M verifies.

How the signed transaction works

Just sign the transaction that has enough information with $S_{M T U}$ that previously presented. Transmit this signed transaction to the server once the user or the merchant go online and the server checks the transaction’s validity and duplication, then the server writes to the ledger.

How the proof of the user balance works

Why do we need this

Under our offline situation, the user needs to tell the merchant that he has enough coins to pay. So one obvious simple way is getting a signature* for the total amount from the trusted server and providing it to the merchant. But the problem is this is telling the user balance to the merchant, even though the amount of balance that user holds is privacy. So instead of that, we can use zero knowledge proof to prove the user’s coin balance is equal or greater than the payment amount without revealing the user’s coin balance.

*Even if a signature has an expiration period, still users can make fraudulent payments by modifying the app. so we need to mitigate this risk by business requirements.

What is zero knowledge proof (here we assume zk-SNARKs)

Here is an example of how it works:

Let’s say there is a function which is $f$ and Prover knows the values that satisfy $f (x, y) = z$ . The aim of ZKP is to let the Verifier understand that the Prover knows such $x$ , $y$ , $z$ without revealing $y$ to the Verifier. We say $y$ is private and $x, z$ are public.

Prover calculates the proof of $f (x, y) = z$ and that proof doesn’t contain any information about $y$ . Then, the Verifier could receive the proof and verify if the proof satisfies the statement, which is “ $y$ exists for $x$ , $z$ and satisfies $f (x, y) = z$ ” or not.

It’s worth noting that the size of the proof is irrelevant to the calculation cost of $f$ or can be made small enough to be logarithmic. Also, the cost of verification is similar to the proof size, meaning the Verifier can efficiently verify the statement much faster than calculating the actual $f (x, y)$ .

How to apply this

Version 1: Simply applied

First, we design the $f$ (circuit) that satisfies our simple requirement that the amount of coins is more than payment value $N$ .

f (Amount, N) = {\begin{matrix} 1 & if Amount \geq N \\ 0 & otherwise \end{matrix}

private variables: $Amount$
public variables: $N$

Then the prover uses this circuit to make a proof, send it to the merchant, and the merchant can verify the user has enough coins without knowing the amount of coins.

Version 2: Make the user cannot lie

The problem with version 1 is that the user can lie about their amount of coins since $Amount$ is provided by the user. What we can do is use a trusted server to provide a signature of $Amount$ . Here, we describe how we create such a signature that can be used for proving the statement, since the signer (trusted server) never knows the payment value $N$ . In the next section, we will see how we can use this signature to let the merchant trust the user’s balance.

Commitment

We use a commitment scheme to ensure the user is using the same $Amount$ such that it was signed by the trusted party. The commitment scheme is quite simple. Here is an example of a commitment:

Alice and Bob are playing a guessing game. First, Alice tells Bob to guess what the number Alice has in her mind, which is $n \in {0, 1}$ . To keep the promise, Alice uses a hash function to generate the commitment data $C = H a s h (n)$ and passes it to Bob. Here we note, Bob cannot know $n$ from $C$ . Then, Bob guesses the number and tells it to Alice. Finally, Alice reveals what she had, and Bob confirms that the $C$ that Alice previously provided was actually $H a s h (n)$ . This is how the commitment scheme works.

In our protocol, $n$ would be $Amount$ and we can make a commitment from it. One key difference is that the user never actually reveals $Amount$ to the merchant but proves it in the zk-SNARKs circuit. Also, we let T sign a commitment to verify that the commitment is legitimate.

Generate Commitment (trusted party)

C = H a s h (Amount, UserID, r)

$r$ : random blind factor

Sign the commitment (trusted party)

S_{TUC} = S i g n_{T} (C)

Now we design the circuit:

f (Amount, N, UserID, R, C) = {\begin{matrix} 1 & if Amount \geq N and C = H a s h (Amount, UserID, R) \\ 0 & otherwise \end{matrix}

private variables: $Amount, UserID, R$
public variables: $N, UserID, Commitment$

This proves that the amount of coins is enough and that the commitment is valid. After verifying the proof, the merchant would verify the signature of the commitment as well:

v e r i f y (S_{TUC}, C)

What are the risks

What they cannot do

1) Double spending to the same merchant

The user needs to provide the total amount of the payment that happened to the merchant.
And the merchant would check the total amount is the same as expected on the local.
In this way, the maximum amount of double spending is capped to the amount that the user previously charged. (for each merchant)

2) Fake identity.

3) Merchant fakes User-X paid multiple times to them.

4) Merchant/User modifies payment amount.

5) User uses the amount more than the user charged.

What they can do

Double spending to multiple merchants if the merchants are not synchronized yet.

Thoughts

It's hard to make this possible without having special hardware or trusted third party but I think it's still valuable to consider how to mitigate the risks more. Also the probability of illegal action is low since all the merchants that they interact with need to be offline when they try to do something illegal. Here we assume the maximum offline time for each merchant is pretty short as we try to deal with the condition like network glitches.

Some more considerations

maximum offline time after acquiring a signature.
maximum one time signature expiration.
maximum amount of payment.
broadcast blacklist to all the merchants. Once we detect the illegal activity, it will be broadcasted to the online merchants immediately.
maximum number of payments.
Sync device time periodically.
Use TEE.

Future

The future of offline payment is on TEE (Trusted Execution Environment). Even though consumer devices like iOS has Secure Enclave to provide limited TEE that can sign bytes without knowing the private key, that is not programmable and atomic operation is not allowed. We can provide complete offline payment functionality combined with this method once we have programmable TEE on consumer devices.

Note

zk-SNARKs POC code: https://gist.github.com/leq6c/040d4acd9cc13c6b86978527719ab0ec