LSP Fraud Proofs

lsp_fraudproofs.pdf

lsp_fraudproofs.tex

% -*- coding: utf-8 -*-
\documentclass[11pt]{article}
%\usepackage[utf8]{inputenc}
\usepackage{graphics}
\usepackage[margin=1.5in]{geometry}

\usepackage{endnotes}
%\let\footnote=\endnote

\title{\bf{Public Fraud Proofs\\for Just-in-Time Channels.}}
%\date{}

\author{Thomas Voegtlin\\{\tt electrum.org}}
\begin{document}

\maketitle

\begin{abstract}

The game theory of just-in-time channels could be improved using fraud
proofs: publicly verifiable proofs that a LSP stole funds instead of
opening a channel to the intended recipient of a Lightning
payment. The difficulty lies with the requirement for the proof to be
verifiable by third-parties, without having to trust the victim. Here
we propose to use the blockchain as an arbitration layer: if a LSP
does not open the channel quickly enough, the intended recipient of
the funds publishes the preimage of the payment hash on-chain. This
on-chain publication is considered a proof that the LSP received the
preimage at a certain block height.

Fraud proofs can be shared between clients in order to reject
malicious LSPs. In order to ensure that it cannot profitably steal, a
LSP may publicly burn some bitcoins, and use this sacrifice in order
to establish his long-term reputation. The amount that can be trusted
with an LSP should be commensurate with the funds they have burnt to
establish their reputation.
\end{abstract}


\section{Introduction}

Let us consider a user Alice and her Lightning service provider
Bob. Bob receives a HTLC from Carol, for which Alice has the
preimage. Alice and Bob negotiate the opening of a new channel. There
are currently two trust models for this, described in bLIP52
\cite{blip52}:

  - {\em LSP trusts client}: Bob publishes the channel funding
  transaction first.  Alice then reveals the preimage to Bob, by
  sending a {\tt fulfill\_htlc} message.  If Alice does not cooperate,
  Bob will lose some mining fees. In addition, funds sent to the
  channel funding transaction will be immobilized for a while, because
  Bob will have to force-close the channel.

  - {\em Client trusts LSP}: Alice discloses the preimage to Bob
  before the channel funding transaction is broadcast. Alice expects
  Bob to publish the funding transaction upon reception of the
  preimage. In this model, Bob can steal the HTLC (potentially a
  higher amount than the mining fees in the previous model).

Note that the {\em LSP trusts client} model only makes sense if the
client waits until the channel funding transaction has been confirmed;
indeed, if the client reveals the preimage before the transaction is
confirmed, then Bob can claim the HTLC and double spend the channel
funding transaction. Therefore, wallet providers that allow instant
settlement of the payment fall in the {\em Client trusts LSP}
category.



\section{Fraud proofs}

A fraud proof is a proof that Bob has claimed the HTLC without opening
a channel to Alice. If this proof can be verified by anyone, without
having to trust Alice, then it becomes possible for clients to punish
fraudulent LSPs, by stopping doing business with them. Intuitively, a
fraud proof may be formed from 3 parts:
\begin{enumerate}
\item{a commitment by Bob that he will create a channel funding transaction $tx1$, if he receives the preimage of a given hash}
\item{a proof that Alice gave the preimage to Bob}
\item{a proof that Bob spent the inputs of $tx1$ in another transaction $tx2 \neq tx1$}
\end{enumerate}

The difficulty in creating such proofs lies with the second part:
While Alice knows that she gave the preimage to Bob, it is not easy
for her to prove it publicly. The fact that Bob has claimed the HTLC
with Carol could in principle be used, but this information is not
accessible to Alice. In addition, Carol may be conspiring with Bob, or
she may not want to be involved in the construction of the fraud
proof.\footnote{A related proposal \cite{lsps3} creates an
unconditional obligation for the LSP to fund the channel, thus
skipping the second part of the proof. This exposes LSPs to griefing
attacks, where malicious clients request channels and never reveal the
preimage.}


\section{On-chain arbitration}

In order solve this, we propose to use the blockchain as a public
arbitration layer. Alice and Bob use a zeroconf channel with a funding
TXID that is known in advance, so that Alice reveals the preimage
through the {\tt fulfill\_htlc} message. Bob signs and broadcasts the
funding transaction only after he has received the preimage.

If Bob does not broadcast the funding transaction, Alice should
publish the preimage on the blockchain, using an {\tt OP\_RETURN}.
Note that Bob is supposed to watch the blockchain, in case Alice is
non-cooperative and does not communicate the preimage directly.  Using
the blockchain has the advantage of non-deniability: If the preimage
is published on-chain, Bob cannot pretend that he did not receive it.

Not only can the publication of the preimage be verified by anyone,
but it can also be dated to a certain block height. This allows us to
create {\em UTXO commitments} with an expiration date. Indeed the
commitment created by Bob should be valid until a certain block
number, so that Bob is allowed reuse the committed UTXOs if Alice has
not disclosed the preimage after some delay.  Here is how the
non-cooperative path would work:

\begin{enumerate}
\item{Bob receives a HTLC for Alice, from another node Carol. Alice
  and Bob engage in a zeroconf channel opening, funded by Bob, with
  funding transaction $txid$. Once Bob has received the {\tt
    funding\_signed} message, instead of broadcasting the funding
  transaction, Bob discloses the unsigned funding transaction to
  Alice. Alice verifies that it actually funds the channel.}
\item{Bob sends a set of {\em UTXO commitments} to Alice: Bob pledges
  to spend any input of the funding transaction in $txid$, if
  the preimage of $hash$ is published before block $n$:
   $$bob\_signature(prevout, txid, hash, n)$$ UTXO commitments are
  signed by Bob using his public node ID $pubkey$. }
\item{Bob sends a proof of ownership of the UTXOs he committed to
  Alice. Alice checks that Bob owns the UTXOs, and that their sum is
  higher than the payment she is expecting to receive in the HTLC.}
\item{Alice and Bob exchange {\tt channel\_ready}. Alice reveals the
  preimage to Bob, by sending a {\tt fulfill\_htlc} message.}
\item{ Bob claims the HTLC. Alice waits for a few minutes, hoping that
  the funding transaction will be signed and broadcast by Bob. Alice
  then realizes that something is wrong. She publishes the preimage of the
  payment hash in an on-chain {\tt OP\_RETURN} transaction
  output. That transaction must be confirmed before block $n$. If
  Alice does not have bitcoins, she can pay a third-party to perform
  the on-chain publication on her behalf.  }
\end{enumerate}

If Alice publishes the preimage before block $n$, then Bob must spend
the UTXOs according to his commitment.  If Alice has not published the
preimage at block $n$, then Bob can fail the HTLC, and he is allowed
to spend the UTXOs in another transaction. Alice should also publish
her preimage:
\begin{itemize}
\item if Bob double-spends the channel funding transaction while it is in the mempool.
\item
 if block $n$ is getting close and the funding transaction has not
 been confirmed yet, or does not have enough confirmations to Alice's
 taste.
\end{itemize}


Note that Bob does not have a deadline to publish the channel funding
transaction; it may indeed be confirmed after block $n$. However, if
the channel funding transaction does not pay enough fees, Bob will not
be able to double-spend it without creating a fraud proof. To ensure
that the channel will eventually get confirmed, Bob may add a change
output to the channel funding transaction, to be able to CPFP it.



\subsection*{Case 1: Bob spends a committed UTXO in another transaction}

The first case of fraud is if Bob spends a UTXO committed to $tx1$ in
another transaction $tx2$. In that case, the fraud proof consists of 3
parts:
\begin{enumerate}
\item Bob's UTXO commitment: $sig(prevout, txid1, hash, n)$
\item $prevout$ was spent in $tx2 \neq tx1$
\item $tx2$ was confirmed before block $n$, or the preimage of $hash$, was published onchain before block $n$
\end{enumerate}

This proof can be verified by anyone, without having to trust Alice.  


\subsection*{Case 2: Bob does nothing}

Bob claims Alice's HTLC, and does not spend the pledged UTXOs. Alice
publishes the preimage on-chain before block $n$.  In this case, Alice
has lost the HTLC, but Bob cannot spend the UTXO without creating a
fraud proof. Therefore, the UTXOs are unusable, and the amount lost by
Bob is potentially higher\footnote{This works because Bob also sent a
proof of ownership for the UTXOs he committed}.

Note that it would be possible to add a block height deadline for Bob,
and to consider the absence of channel funding at that height to be a
fraud. However, the corresponding proof is not easily verifiable for
light clients, because it would require proof that a UTXO has not been
spent. In addition, adding such a constraint would expose LSPs to
mempool dynamics that are not in their control. Therefore, the current
status quo is probably better; game theory ensures that theft is not
profitable.

\subsection*{Case 3: Bob reuses the same UTXO in multiple commitments}

In this scenario, Bob tries to reuse the same UTXO with several users,
in order to steal more than one payment. In other words, Bob commits
to $hash2$ before the commitment to $hash1$ has expired. In that case,
the fraud proof consists of:
\begin{enumerate}
\item Bob's first commitment:  $bob\_sig(prevout, txid1, hash1, n1)$
\item Bob's second commitment: $bob\_sig(prevout, txid2, hash2, n2)$
\item The preimage of either $hash1$ or $hash2$ was published onchain at block height $h$, with $h < n1$ and $h < n2$
\end{enumerate}

In order to detect this type of fraud, clients will need to share
information about current commitments they receive from LSPs.  If
Alice receives a UTXO commitment from Bob that conflicts with another
commitment that has not expired yet, then Alice knows that Bob is
trying to cheat. However, in order to make that knowledge public,
Alice still needs to publish her preimage onchain.


\section{Skin in the game}

In order to prove that it cannot profitably steal, a LSP may publicly
sacrifice some bitcoins. This is similar to the idea of fidelity bonds
proposed for Joinmarket \cite{fbonds}. This public sacrifice allows
anyone to create some degree of trust, without the need for a prior
reputation, and without having to disclose their identity.

For the game theory to work, the amount that can be trusted with an
LSP should be commensurate with the funds they have spent on their
reputation; if a LSP has sacrificed $X$ bitcoins, they should not be
trusted with more than $X$.  Note that this requirement concerns the
total amount committed by a LSP at a given time, with all clients. If
that amount exceeds the cost of his reputation, a malicious LSP may be
tempted to steal.

Thus, clients will need to detect {\em over-commitments} by LSPs; the
emission of commitments that exceed the amount for which a LSP is
trusted. This can be achieved by exchanging information about current
commitments, which is already required in order to deal with UTXO
reuse (case 3). However, in contrast to UTXO reuse, over-commitment
should not be considered as a case of fraud, again because the
corresponding proof would involve the fact that a UTXO is still
unspent, which is not easily verifiable by light clients.

%A honest LSP should fail the payment, so that the payer can try a
%different one.





\section{Denial of service}

Note that LSPs are susceptible to griefing attacks from clients:
Indeed, Alice may send a payment to herself and never reveal the
preimage to Bob. This means that for the duration of the commitment,
Bob will not be able to use the UTXO he has committed.

However, this type of denial of service has a cost for the attacker,
because the HTLCs used by the attacker will be locked by the LSP for
at least the same duration as the UTXOs commitment\footnote{The
relative locktime of the HTLC received by Bob should be at least $n$
blocks.}. If Bob uses UTXO amounts that are of the same order of
magnitude as the incoming payments (for example no more than twice as
large), then the opportunity cost for the attacker will be comparable
to the cost for the LSP.  This can be achieved if Bob imposes minimum
and maximum payment amounts, and manages a reserve of UTXOs.


Of course, this is quite a constraint. While a classical trusted LSP
can create channels with UTXOs of any size, a LSP that sends UTXO
commitments will need to maintain a reserve of UTXOs of various sizes
in order to meet client requests. Denial of service may still be an
issue, if an attacker can allocate more fund to the attack than LSPs
have in their UTXO set.  Committing UTXOs that are vastly larger than
the planned channel size favors the attacker, by creating asymmetric
liquidity requirements.

\section{Indexing on-chain data}

Bob will need to watch on-chain {\tt OP\_RETURN}s, in case Alice does
not communicate the preimage directly. Alice will need to watch {\tt
  OP\_RETURN}s too, in order to validate fraud proofs received from
other clients.

In order to facilitate that, Electrum servers may index {\tt
  OP\_RETURN} preimage data and serve it to light clients.  Note that
it would be useful to have servers that index UTXO commitments not
only by payment hash, but also by prevout and by node ID. In order to
achieve this, we shall include the complete UTXO commitment in the
{\tt OP\_RETURN}.  For example, the {\tt OP\_RETURN} could contain:
$$(preimage, prevout, txid, n, pubkey, signature)\footnote{Note that this
exceeds the 80-byte standardness limit of old Bitcoin Core versions.}$$

Including the full UTXO commitment, with pubkey and signature, would
allow Electrum servers to collect fraud proofs and serve them to light
clients, without requiring another source of data than the
blockchain. However, an additional communication channel is still 
needed, as will be discussed in the next section.

In order to reduce dataset size, the {\tt OP\_RETURN} should start
with a magic prefix, which would be required for the fraud proof to be
considered valid. In addition, we may require that the {\tt
  OP\_RETURN} in a fraud proof has not been published before the UTXO
birth date. This will reduce the work of verifiers who scan full
blocks.




\section{Sharing UTXO commitments between clients}

In order to deal with UTXO reuse and over-commitments, clients will
need to share UTXO commitments they receive from LSPs.  Including
UTXO commitments in the {\tt OP\_RETURN} data is not sufficient for
that, because that communication channel is too slow.  Indeed, clients
do not expect their LSP to cheat. Thus, they are not going to publish
an {\tt OP\_RETURN} immediately after they have revealed their
preimage. Instead, they will wait, several minutes at best, maybe
several hours if the client needs to have a third-party publish on her
behalf. Thus, if two clients request a channel from a malicious LSP
within a short time window, they will not have a chance to see the
{\tt OP\_RETURN} published by the other client.  This would give a
malicious LSP a chance to reuse the same UTXO with two clients.

In order to prevent that, clients should share UTXO commitments in
real time, using a fast communication medium that does not require
payment of mining fees. One option is to use {\tt Nostr}, which has
built-in indexing capabilities. If clients publish UTXO commitments as
{\tt Nostr} events, and these events are correctly structured, then
{\tt Nostr} relays will be able to index and serve them by $prevout$
and by $pubkey$\footnote{Although it may seem redundant, we still
consider the inclusion of full UTXO commitments in the {\tt
  OP\_RETURN} as useful, because {\tt Nostr} does not offer guarantees
of perennial storage.}.

If UTXO commitments are shared over a fast channel, then UTXO reuse
can be mitigated. If a malicious LSP sends two conflicting commitments
to two clients, at least one of the clients will have time to detect
the fraud.  After she receives a UTXO commitment from Bob, Alice
should wait for a few seconds before she discloses her preimage, in
order to see if she receives a conflicting commitment from other
clients.  Assuming that the exchange of information between clients is
faster than preimage disclosure, this behavior will ensure that at
least one of the two clients will detect the fraud before revealing
the preimage. Thus, the LSP will not be able to receive more than one
preimage, which makes stealing non-profitable for them.

Over-commitments can be detected and mitigated in a similar way. If
Bob is over-committed, Alice may decide to fail the payment, or to
hold the HTLC until previous commitments by Bob have been fulfilled
(that is, until committed UTXOs have been spent).


\section{Conclusion}

Fraud proofs offer a middle ground between the existing {\em LSP
  trusts client} and {\em client trusts LSP} models, with several
advantages:
\begin{itemize}
\item LSPs cannot profitably steal.
\item No loss of mining fees for LSPs if clients are non-cooperative
\item The opportunity cost of a griefing attack is commensurate for the LSP and for the attacker
\end{itemize}

One of the critiques frequently addressed to the Lightning Network is
that it is ``not really decentralized''. Indeed, the comfortable
experience of LSPs opening channels just in time and managing
liquidity for users has led to hyper-centralization of services, with
wallet providers relying on their own node being honest, and not
giving users the freedom to open channels with untrusted nodes.  The
current proposal aims at reducing that trust, so that wallet users
will be able to choose between many competing LSPs, instead of being
locked with a single wallet provider.


\begin{thebibliography}{9}

\bibitem[1]{blip52}
Blip52\\{\tt https://github.com/lightning/blips/blob/master/blip-0052.md}

\bibitem[2]{lsps3}
LSPS3: Promise To Unconditionally Fund 0-conf\\
{\tt https://github.com/BitcoinAndLightningLayerSpecs/lsp/pull/24}

\bibitem[3]{fbonds}
Fidelity bonds\\{\tt https://clay-v.github.io/joinMarketDocs/users/fidelity-bonds.html}

\end{thebibliography}





\end{document}