Implementing Mithril in a light wallet

[jpraynaud]

This discussion is a first draft of the design we have imagined for light wallet implementation of Mithril.
We are expecting contributions and feedback in order to create the best possible use-case.

Why

The Mithril team is attempting to define how light wallet users could benefit from Mithril certification.

Today, light wallet users rely on third party providers to retrieve these information, and they must trust them.
Can the Mithril protocol be used as a trustless provider for these UTxO information?

The problem we are trying to solve can be summarized with the question:

How can light wallet users gather certified and up to date UTxOs associated to their addresses?

What

Assumptions

We are assuming that the users are interacting with the blockchain in the following manner:

• They use a wallet that is running in a light environment (e.g. an app on a smartphone or an app in the browser a la Lace).
• They are interested in retrieving information about their own UTxOs only.

Note: For ease of presentation, we will focus on the usage by Lace.

The current Trusted setup

How it works

Currently, Lace is interacting with a remote backend to retrieve the wallet balances, as explained below:

• A call is made to the backend with the addresse(s) as argument.
• The backend returns a JSON response with the associated UTxOs.
• The response is parsed by Lace and displayed in the user's wallet.

This is an example request that is sent by Lace to the backend:

  $ curl 'https://backend.live-preprod.eks.lw.iog.io/utxo/utxo-by-addresses' \
  -H 'content-type: application/json' \
  --data-raw '{"addresses":["addr_test1qqgt54zugznxw8xnk3ksatawedm4ssgmf5m2866kfv9rqarsfhuszdts7fl49ej6vcmqetds07f73jl9awc34pgdsf8sf2ymt2"]}' 

This is the response from the backend:

[
    [
        {
            "address": "addr_test1qqgt54zugznxw8xnk3ksatawedm4ssgmf5m2866kfv9rqarsfhuszdts7fl49ej6vcmqetds07f73jl9awc34pgdsf8sf2ymt2",
            "index": 0,
            "txId": "c5ccfa0e8ec12553908ef4fbdc38bcd2e2b902188b30c26b4d383e96bad0f5a4"
        },
        {
            "address": "addr_test1qqgt54zugznxw8xnk3ksatawedm4ssgmf5m2866kfv9rqarsfhuszdts7fl49ej6vcmqetds07f73jl9awc34pgdsf8sf2ymt2",
            "value": {
                "coins": {
                    "__type": "bigint",
                    "value": "10000000000"
                }
            }
        }
    ]
]

This is the wallet balance displayed in Lace:

Summarized flow

sequenceDiagram
    actor User
    User->>Lace: Can you show the balances of my address(es)?
    Lace->>Backend: Can you send me UTxOs for this address(es)?
    Backend-->>Lace: Yes, here are the UTxOs (and please just trust me)!
    Lace->>User: Yes, here are your balances (and please just trust me)!

Loading

Security guarantees

There is no proof that the UTxO are genuine, i.e. the wallet user must trust the backend provider.

The proposed Trustless setup

How it would work

Coarse-grained level

Lace would interact as before with its backend to retrieve non certified UTxOs. It would then interact with a a Mithril client running in the browser (e.g. as WASM), as follows:

• A call is made to the Lace backend with the addresse(s) as argument (same as in trusted setup).
• The backend returns a JSON response with the associated UTxOs (same as in trusted setup).
• The response is parsed by Lace and displayed in the user's wallet (same as in trusted setup).
• A call is made to the Mithril client with the addresse(s) and their UTxOs to validate as arguments.
• The Mithril client makes the cryptographic verifications and returns a JSON output with the verified UTxOs. ⁽¹⁾
• The response is parsed by Lace.
• Lace verifies that the there is no discrepancy between the UTxOs sent and the UTxOs that are received from the Mithril client:
  • If there is a discrepancy, it waits and calls once again the Mithril clinet after a delay.
  • If at least an UTxO is not valid, an error message is displayed to the user.
  • If there is no discrepancy and all the UTxO are valid, Lace displays a Certified by Mithril badge next to the corresponding wallet balance.

Fine-grained level

Under the hood, the Mithril client verifies the cryptographic proofs and the associated Mithril certificates that it retrieves from a Mithril aggregator:

• A call is made to the Lace backend with the addresse(s) as argument (same as in trusted setup).
• The backend returns a JSON response with the associated UTxOs (same as in trusted setup).
• The response is parsed by Lace and displayed in the user's wallet (same as in trusted setup).
• A call is made to the Mithril client with the addresse(s) and their UTxOs to validate as arguments.
• The Mithril client does the following operations:
  • A call is made to the Mithril aggregator with the addresse(s) and their UTxOs as argument.
  • The Mithril aggregator returns a JSON response with the associated UTxOs and a cryptographic proof. ⁽¹⁾
  • The response is parsed by the Mithril client.
  • The Mithril client verifies that the UTxOs received are identical to the UTxOs sent:
    • If they are different, it waits and calls once again the Mithril aggregator after a delay.
    • If they are identical, it verifies locally the cryptographic proof for each UTxO (more details below):
      • If the cryptographic proof is not valid, the UTxO is not appended to the response sent back to Lace.
      • If the cryptographic proof is valid, the UTxO is appended to the result response sent back to Lace.
  • The Mithril client returns a JSON output with the verified UTxOs.
• The response is parsed by Lace.
• Lace verifies that the there is no discrepancy between the UTxOs sent and the UTxOs that are received from the Mithril client:
  • If there is a discrepancy, it waits and calls once again the Mithril clinet after a delay.
  • If at least an UTxO is not valid, an error message is displayed to the user.
  • If there is no discrepancy and all the UTxO are valid, Lace displays a Certified by Mithril badge next to the corresponding wallet balance.

This is an example request that would be sent by Mithril client to the Mithril aggregator:

  $ curl 'https://aggregator.release-preprod.api.mithril.network/aggregator/artifacts/utxo/utxo-by-addresses' \
  -H 'content-type: application/json' \
  --data-raw '{"addresses":["addr_test1qqgt54zugznxw8xnk3ksatawedm4ssgmf5m2866kfv9rqarsfhuszdts7fl49ej6vcmqetds07f73jl9awc34pgdsf8sf2ymt2"]}' 

This is an example of the response that would be sent by the Mithril aggregator:

[
    [
        {
            "address": "addr_test1qqgt54zugznxw8xnk3ksatawedm4ssgmf5m2866kfv9rqarsfhuszdts7fl49ej6vcmqetds07f73jl9awc34pgdsf8sf2ymt2",
            "index": 0,
            "txId": "c5ccfa0e8ec12553908ef4fbdc38bcd2e2b902188b30c26b4d383e96bad0f5a4"
        },
        {
            "address": "addr_test1qqgt54zugznxw8xnk3ksatawedm4ssgmf5m2866kfv9rqarsfhuszdts7fl49ej6vcmqetds07f73jl9awc34pgdsf8sf2ymt2",
            "value": {
                "coins": {
                    "__type": "bigint",
                    "value": "10000000000"
                }
            }
        },
        {
          "certificate_hash": "dcf7c25da5388220483bc5fd2ddf2a06bcc0afe9f0f384858928a5af2bb9ca14",
          "merkle_root": "8b75feb906c9cec95ea08eecff5b651afb9e1fec506b216288127b1e3c5ca687",
          "merkle_proof": "0372c34332c3231322c3138362c3133372c3134372c3231302c33372c3130382c3130352c3135382c3234302c3233302c34322c322c33302c302c37372c36382c3139302c3230392c3137332c35322c3234362c3139302c31342c38362c3232382c3131322c3230302c3135342c37322c3230362c3235322c3233342c38362c32332c33332c392c31322c36372c3234352c3234352c33352c3137392c3134392c3130322c34322c3133342c3231352c36382c33362c3233362c3131342c38372c3135372c3134332c35392c3138372c3130302c3233382c3134335d2c22706f70223a5b3136312c3138342c3137352c3136312c34302c3137312c36382c3138332c3138372c32362c3136382c3135382c3136302c31382c33372c3130342c3136392c33372c3233312c38332c3235312c32322c3234312c3138312c35332c3133362c3231312c3131342c3232362c35372c3133362c3137382c3232382c3132392c3130342c362c31382c3232392c3234372c3134332c3136372c3130322c35392c3930"
        }
    ]
]

The response includes a new entry for each address with the information needed to verify the validity of the UTxO retrieved:

{
  "certificate_hash": "dcf7c25da5388220483bc5fd2ddf2a06bcc0afe9f0f384858928a5af2bb9ca14",
  "merkle_root": "8b75feb906c9cec95ea08eecff5b651afb9e1fec506b216288127b1e3c5ca687",
  "merkle_proof": "0372c34332c3231322c3138362c3133372c3134372c3231302c33372c3130382c3130352c3135382c3234302c3233302c34322c322c33302c302c37372c36382c3139302c3230392c3137332c35322c3234362c3139302c31342c38362c3232382c3131322c3230302c3135342c37322c3230362c3235322c3233342c38362c32332c33332c392c31322c36372c3234352c3234352c33352c3137392c3134392c3130322c34322c3133342c3231352c36382c33362c3233362c3131342c38372c3135372c3134332c35392c3138372c3130302c3233382c3134335d2c22706f70223a5b3136312c3138342c3137352c3136312c34302c3137312c36382c3138332c3138372c32362c3136382c3135382c3136302c31382c33372c3130342c3136392c33372c3233312c38332c3235312c32322c3234312c3138312c35332c3133362c3231312c3131342c3232362c35372c3133362c3137382c3232382c3132392c3130342c362c31382c3232392c3234372c3134332c3136372c3130322c35392c3930"
}

The validity of the UTxO is given by the following information:

• merkle_root: the root of the Merkle tree used to store the whole UTxO set.
• merkle_proof: the Merkle proof used to verify that the given UTxO is part of the Merkle tree with aforementioned Merkle root. ⁽²⁾
• certificate_hash: the unique identifier of the Mithril certificate signing the aforementioned Merkle root. ⁽³⁾

In order to verify these information, Lace would need to verify it with a light Mithril client running in the browser (in WASM) as an intermediary step before displaying the wallet balance (this would be repeated for each address UTxO returned by the backend):

• the Mithril client verifies that the Merkle proof matches the Merkle root ✔.
• the Mithril client verifies that the Merkle root is signed by the pointed Mithril certificate ✔.
• the Mithril client verifies that the Mithril certificate is part of a valid Mithril certificate chain ✔. ⁽⁴⁾

This is the way the wallet balance could be displayed in Lace:

Summarized flow

sequenceDiagram
    actor User
    participant Lace
    participant Mithril Client
    participant Backend
    User->>Lace: Can you show the balances of my address(es)?
    Lace->>Backend: Can you send me UTxOs for this address(es)?
    Backend-->>Lace: Yes, here are the UTxOs (and please just trust me)!
    Lace->>User: Yes, here are your balances (and please just trust me)!
    loop
        Note over Lace: Until a proof for the same UTxO(s) is received
    	Lace->>Mithril Client: Can you verify the authenticity of these UTxOs?
    	Mithril Client-->>Lace: Sorry, I don't have any proof yet... Can you try again later?
    end
    Mithril Client-->>Lace: No, the UTxOs do not match their cryptographic proofs...
    Mithril Client->>Lace: Yes, I have verified all the cryptography and made sure the UTxOs are authentic!
    Lace->>User: Your balance is now certified by Mithril!

Loading

Detailed flow

sequenceDiagram
    actor User
    participant Lace
    participant Mithril Client
    participant Mithril Aggregator
    participant Backend
    User->>Lace: Can you show the balances of my address(es)?
    Lace->>Backend: Can you send me UTxOs for this address(es)?
    Backend-->>Lace: Yes, here are the UTxOs (and please just trust me)!
    Lace->>User: Yes, here are your balances (and please just trust me)!
    loop
        Note over Lace: Until a proof for the same UTxO(s) is received
    	Lace->>Mithril Client: Can you verify the authenticity of these UTxOs?
    	Mithril Client->>Mithril Aggregator: Can you send me UTxOs for this address(es) and their associated cryptographic proofs?
    	Mithril Aggregator-->>Mithril Client: No, there are no certificate for them yet, try again later...
    	Mithril Aggregator->>Mithril Client: Yes, here are the UTxOs and their associated cryptographic proofs!
    	loop
        	Note over Mithril Client: Until the genesis certificate is reached
        	Mithril Client->>Mithril Aggregator: Can you send me the certificate associated to this hash?
        	Mithril Aggregator->>Mithril Client: Yes, here is the certificate you requested
    	end
    	Mithril Client-->>Lace: Sorry, I don't have any proof yet... Can you try again later?
    end
    Mithril Client-->>Lace: No, the UTxOs do not match their cryptographic proofs...
    Mithril Client->>Lace: Yes, I have verified all the cryptography and made sure the UTxOs are authentic!
    Lace->>User: Your balance is now certified by Mithril!

Loading

Security guarantees

This setup would provide a cryptographic proof that the UTxO are genuine. This means that the security provided is equivalent to the security of the Mithril protocol, i.e. the wallet user does not need to trust the backend provider.

Notes

⁽¹⁾: The delay before a UTxO can be certified depends greatly of the finality of the Cardano chain itself (i.e. 2160 blocks or ~12 hours). However, we think that we could probably shrink this delay by leveraging the properties of the Mithril protocol itself. Our research team is actively investigating this subject.

⁽²⁾: The best option would be to rely on a Sparse Merkle Tree that would provide proofs of membership and proofs of non membership. A proof of non membership would be used in case no UTxO is associated to the address.

⁽³⁾: For more information about the Mithril protocol, please refer to this document https://mithril.network/doc/mithril/mithril-protocol/protocol.

⁽⁴⁾: The Mithril client communicates with a Mithril aggregator to retrieve a certificate chain, and makes sure that is is valid. For more information about the certificate chain, please refer to this document https://mithril.network/doc/mithril/mithril-protocol/certificates.

[abailly-iohk]

We really need to engage with light wallet users and developers in order to understand exactly what's the need. I wonder if providing the UTxO is really that important, perhaps they would rather want a certified history of their wallet's transactions (and then compute the UTxO themselves because it's trivial)?

But apart from that, this is a great writeup covering the core technical issues at stake with this feature.

[jpraynaud]

Thanks @abailly-iohk!

Providing a certified history of the wallet's transaction instead of the UTxO themselves would allow to get fine grain certification on the activity of the address not only on the balance. We'll try to include this idea in the proposal 👍

[rhyslbw]

rather want a certified history of their wallet's transactions (and then compute the UTxO themselves because it's trivial)?

This is a good direction. I'll check why we're fetching UTxOs independently in Lace rather than computing from history

[HeinrichApfelmus]

(Apologies for jumping in, I randomly noticed this discussion in my Github notifications.)

I have a question: How much resources does the Mithril client use when verifying the certificate chain?

I'm asking because there is a fundamental trade-off between trust and speed. Light wallets can be fast because they trust a third party (here: Lace backend) to provide accurate information. A wallet that does not want to trust a third party will have to invest resources into verification. For example, one option is to trust a local cardano-node to do all the verification, but thanks to a more efficient algorithm, Mithril can provide the same service for less resources — my question is: for how much?

For comparison, at the time of this writing, a cardano-node requires in the ballpark of ~2 days and ~100 GB of disk space to download and verify the current ledger state all the way back to genesis. When the Mithril client verifies the certificate chain all the way back to genesis, how long does this take and how much memory does this use?

[jpraynaud]

We have indeed run some early experiments in this issue #1254 (comment).

We have successfully verified the current certificate chain produced on the mainnet in a browser with a Mithril client compiled in WASM:

• Download and verification of a chain of 16 certificates in 45s
• CPU average consumption by the browser process of 91% on one core
• Memory max consumption used by the browser process of 150MB

The machine used for these tests is running Linux Ubuntu 22.04 (8 cores CPU / 64GB RAM / 2TB SSD / 500Mbps Fiber), and the browser used is Brave (Chromium).

The time needed to verify the certificate chain will increase by ~3s at every epoch (~5days) with this sequential verification.
However, the verification process can be cached as there is no need to verify multiple times the same certificates.

Overall, the verification process is likely to be very light in terms of duration, CPU and memory usage on the end user machine.

This is a screenshot of the verification of the certificate chain in the browser done with our proof of concept:

[HeinrichApfelmus]

Thanks!

The time needed to verify the certificate chain will increase by ~3s at every epoch (~5days) with this sequential verification.

At 3s per epoch, synchronizing to Mainnet (~440 epochs) would take ~22 minutes. On a mobile phone, that probably means ~1h.

However, the verification process can be cached as there is no need to verify multiple times the same certificates.

Well, that is true for the cardano-node, too. 😂 What is the size of a single Mithril certificate for storing on disk?

[abailly-iohk]

At 3s per epoch, synchronizing to Mainnet (~440 epochs) would take ~22 minutes. On a mobile phone, that probably means ~1h.

Mithril did not existed at Genesis, so there won't be that many epochs until 5 years :)

Well, that is true for the cardano-node, too. 😂 What is the size of a single Mithril certificate for storing on disk?

The JSON for a single certificate is 450k with hex-encoded binary data. I would expect it to take a third of that size serialised on disk

[HeinrichApfelmus]

Mithril did not existed at Genesis, so there won't be that many epochs until 5 years :)

Ah, I see. If I understand correctly, the Mithril genesis certificate is signed by the Mainnet genesis keys, which is as good as a regular genesis file.

The JSON for a single certificate is 450k with hex-encoded binary data. I would expect it to take a third of that size serialised on disk

With 73 epochs in a normal year, a size of 450k would mean ~33 MB per year. That's very reasonable. 👍

[abailly-iohk]

If I understand correctly, the Mithril genesis certificate is signed by the Mainnet genesis keys, which is as good as a regular genesis file.

Not yet, but we are working on it :)