Try โ€‚โ€‰HackMD

Transparent UTXOs for Private ERC20

First, we give a brief overview of the traditional public ledger accounting models and then discuss the private UTXO model and how to modify it so that we can integrate with ERC20 tokens and other smart contracts.

Ledger Models

To store value on a distributed ledger, we have two standard data structures at our disposal:

  1. Account Model: a map from a set of accounts to a set of balances
  2. UTXO Model: a set of claims that represent unspent transaction outputs

Account Model

The account model is the simplest of the two and the one that should be familiar to most people. Consider three people, Alice, Bob, and Charlie, who keep a ledger between them:

Account Balance
Alice 8000
Bob 5000
Charlie 4000

Supposing that Alice wants to send 300 to Charlie, she would build the following transaction

 [ALICE 300]
โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”
[CHARLIE 300]

and sign it with her private key so that everyone knows that she approves of this transaction. She would then log the transaction in the ledger transaction history and update the state of the ledger as follows:

Account Old Balance Transaction New Balance
Alice 8000 -300 7700
Bob 5000 5000
Charlie 4000 +300 4300

Now that the table has been updated, the transaction is finished. Formally, we can define the account model as a map of the following kind:

type AccountSet = Map<PublicKey, Balance>;

UTXO Model

The UTXO model works more directly with the underlying transactions themselves by using them to create and destroy claims for future spending. Let's consider the same situation as above but now in the UTXO model:

UTXO Owner Balance UTXO Owner Balance
U0 Alice 3100 U5 Charlie 368
U1 Charlie 1950 U6 Charlie 1025
U2 Bob 2923 U7 Charlie 657
U3 Alice 521 U8 Bob 283
U4 Alice 4379 U9 Bob 1794

Each UTXO represents a spendable asset which can be an input to a transaction. Notice that if we sum up all the UTXOs owned by each individual, they sum up to the original account balances above. Now if Alice wants to build a transaction that sends 300 to Charlie, she first has to claim some existing UTXOs, say U3, and build a new UTXO for Charlie, say U10.

 (U3)[ALICE 521]
โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”
(U10)[CHARLIE 300]

This transaction on its own would burn 221 so, Alice can build another UTXO for herself with the change:

          (U3)[ALICE 521]
โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”
(U10)[CHARLIE 300] (U11)[ALICE 221]

To update the ledger, Alice will strike U3 from the ledger and append U10 and U11.

UTXO Owner Balance UTXO Owner Balance
U0 Alice 3100 U6 Charlie 1025
U1 Charlie 1950 U7 Charlie 657
U2 Bob 2923 U8 Bob 283
U3 Alice 521 U9 Bob 1794
U4 Alice 4379 U10 Charlie 300
U5 Charlie 368 U11 Alice 221

Now, when Charlie goes to spend his new 300 he can use any one of his UTXOs U1, U5, U6, U7, or U10, and in any combination. Alice has burned U3 and minted U10 and U11, and in doing so, has given ownership of some portion of her money to Charlie.

Formally we can define the UTXO model as a structure of the following kind

struct Utxo {
    address: PublicKey,
    balance: Balance,
}
type UtxoSet = MultiSet<Utxo>;

We can denote the Utxo data structure with the following short hand as above,

UTXO := [PublicKey Balance]

Private Transactions

To build a ledger which supports private transactions, we will consider a private version of the UTXO model above. Privacy should manifest itself in (at least) these two requirements:

  1. Participants are kept anonymous
  2. Balances and transaction amounts are kept secret

Here we will present the semantics of a private UTXO model which achieves these two requirements but we will not go into the details of how this is achieved with standard cryptographic constructions. We can denote a private UTXO as follows:

pUTXO := [S(PublicKey) S(Balance)]

where S(x) means that the data x is only known to the sender and receiver of that particular UTXO. Consider the following example transfer from Alice to Bob

[S(ALICE) S(10)] [S(ALICE) S(5)]
โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”
 [S(BOB) S(13)] [S(ALICE) S(2)]

where Alice sends Bob 13 leaving her with a change of 2. Notice that none of the public keys or asset amounts are leaked in this transaction: Alice knows everything about the transaction, Bob only knows about his UTXO, and everyone else is kept oblivious. Once Alice generates this transaction, she builds a proof that this transaction is well-formed and adds the two output UTXOs to the ledger, and two certificates that destroy the old UTXOs (without revealing which ones they are).

The existence of a private UTXO model solves the two challenges above, namely, participants are anonymous by the fact that their public keys cannot be associated to their UTXOs, and the transaction amounts are also kept secret. A users balance is just the sum of their UTXO values and because the values are secret, so is their sum.

Transparent UTXOs

In order to make private UTXOs compatible with smart contracts, we need to attach some public data to them since these contracts can only be executed in public. The transparent UTXO is defined as an extension of the private UTXO as follows:

tUTXO := [S(PrivateKey) S(Balance) P(Balance)]

where P(x) means that the data x is public. Here's an example transaction with transparent UTXOs:

          [S(ALICE) S(30) P(50)]
โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”
[S(BOB) S(20) P(20)] [S(ALICE) S(40) P(0)]

notice that Bob has received 40 from some sender unknown to him which has deposited 20 publicly and 20 privately.

Transparent UTXOs are more general than private UTXOs since we can convert any private UTXO into a transparent one by injecting zero public data without leaking any information:

[S(pk) S(a)] -> [S(pk) S(a) P(0)]

Any transaction which converts between UTXOs like the following

[S(pk) S(a) P(b)] -> [S(pk) S(c) P(d)] where (a + b) = (c + d)

has a leak-value equal to d. More generally, for multiple inputs and outputs the leak-value of a transfer is equal to the sum of the output transparent values.

NOTE: The transparent values of input UTXOs is not leaked in any transaction since none of the input UTXOs are ever revealed.

Private ERC20

We can now give smart contracts the ability to modify the public part of a transparent UTXO. ERC20 contracts (and most smart contracts with user balances) are typically implemented using the account model. To integrate with an account-based smart contract, first we produce a minting transaction which spends some existing transparent UTXOs, removing them from the ledger, and generates a new transparent UTXO. Then, instead of registering this UTXO on the ledger, we can give it to the contract by creating the account entry:

[S(pk) S(a) P(b0)] -> { address: string(S(pk)S(a)), balance: b0 }

and adding this entry to the account table. Since the address string is indistinguishable from a random string, we have built a new account which cannot be traced back to its original owner. Now, whenever the owner of pk wants to privatize those tokens back into a transparent UTXO they present a proof that they can reconstruct the account string S(pk)S(a) and the smart contract will deposit the new UTXO into the private ledger

{ address: string(S(pk)S(a)), balance: b1 } -> [S(pk) S(a) P(b1)]

with the balance update from b0 to b1. The owner of pk can then spend this UTXO as usual as a part of a private transfer protocol. We have the following roundtrip interface:

             [S(pk) S(a) P(b0)]
โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€” [insert account]
{ address: string(S(pk)S(a)), balance: b0 }
โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€” {contract calls}
                     ...
โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€” {contract calls}
{ address: string(S(pk)S(a)), balance: b1 }
โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€” [remove account]
             [S(pk) S(a) P(b1)]

When the transparent UTXO is returned back to the ledger, its data is deleted from the contract and by the nature of the private UTXO protocol, it will never return to the contract since each UTXO is unique.

To extend the ERC20 interface, we just need to add two contract function calls insertAccount and removeAccount which do this conversion.

Transparent Multi-Asset UTXOs

To support UTXOs which can hold multiple kinds of assets we add some extra information to the transparent UTXOs

tmUTXO := [S(PublicKey) S(Balance Id) P(Balance Id)]

where Id can either be some identifier from a canonical list of asset IDs or it can be ? to represent an unknown asset ID. Here are three canonical examples (omitting the public keys):

1. [S(5 ABC) P(0   ?)]
2. [S(3 ABC) P(5 ABC)]
3. [S(0   ?) P(5 ABC)]

Each of these examples denote one of the three classes of multi-asset transparent UTXOs:

  1. Shielded (S): All of the asset data is secret.
  2. Fixed-Transparent (FT): The asset ID is transparent but it cannot be changed since the secret ID is fixed as the known ID. The secret asset balance can be anything.
  3. Mutable-Transparent (MT): The secret balance and secret ID must be 0 and ? respectively, the public side can be modified arbitrarily.

These are the only allowed types of multi-asset transparent UTXOs which can be safely used in smart contracts. Here's an example of a swap contract execution trace (omitting public keys and addresses):

    [S(0 ?) P(23 ABC)]
โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€” [insert account]
{ balance: (23 ABC), .. }
โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€” {swap}
{ balance: (15 XYZ), .. }
โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€” [remove account]
    [S(0 ?) P(15 XYZ)]

Similarly, for liquidity pool contributions an execution trace may look like:


[S(0 ?) P(10 ABC)] [S(0 ?) P(10 XYZ)]
โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€” [insert account]
  { balance: (10 ABC) (10 XYZ), .. }
โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€” {provide liquidity}
   { balance: (10 pairABCXYZ), .. }
โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€” [remove account]
      [S(0 ?) P(10 pairABCXYZ)]

where pairABCXYZ is some representative share of the ABC-XYZ liquidity pool.

In the case of multiple kinds of assets associated to the same account, like in the liquidity pool example, we need a more complex semantics for insertAccount and removeAccount to keep track of multiple addresses and/or combined addresses.