Garbled Circuit and Channel Jamming

[Antoine Riard]

Hi,

Recently, before the EoY vacation to be more precise, I gave a talk on the BitVm
flavors and their advances, which was the opportunity to browse back a bit the
old cryptographic primitive underpinning the claimed advances. One of such primitive
is indeed the old idea of "garbled circuits" and how to order knowledge transfer
among two distrusted parties [0].

What it's interesting for this class of cryptographic protocol is the wide class
of secure multi-party game that can be built from it, and a bit of analysis lets
you modelize quite easily channel jamming as a multi-party game (Alice, Bob, Caroll
the next hop and the blockchain). Few years ago, when with Gleb Naumenko, we studied
the solution design space for jamming, we briefly mentioned how "smart contract"
(a.k.a something something covenant for more expressivity), could be a potential
solution [1] [2].

Looking more on "garbled circuits" made me realize that actually we might have already
the primitives to envision "native contract-based" solutions to the channel jamming
problem, and this with no consensus change. I.e beyond the known "monetary solutions"
and "reputation-based" solutions [3]

This is not the intent of this short post to discuss the merits of the current
reputation-measured channel mitigation, which still have a lot of good properties
like local vs global, monadic vs consensus, non-fungible vs fungible and
lightning-endogenous vs exogenous on some scarce ressource. Rather than it's to
bring some prolegomena of a solution to the problem of a channel jamming, as it has
been said elegantly and succintly:

"The holy grail? is indeed charging fees as a function of the time the HTLC was held.
As for now, we are not aware of a reasonable way to do this. There is no universal
clock, and there is no way for me to prove that a message was sent to you, and you
decided to pretend you didn’t. It can easily happen that the fee for a two-week
unresolved HTLC is higher than the fee for a quickly resolving one". [4]

Solving this problem, in my view, means to reconciliate the off-chain notion
of shared time among the 2 Lightning state machines with the on-chain imperative
notion of time. A effective notion of time enabling one to determine objectively
if an event did happen or not (e.g a message exchange) [0]. All the difficulty
being that off-chain there is no such notion of shared time.

Let's start with a strawman protocol, that is moving one step closer to an
effective notion of shared time among 2 Lightnig state machines.

One way to solve channel jamming would be to have a (taproot) tree of scripts
covering the whole time range for which the funds are locked in the offered
HTLC (so `<cltv_expiry>`). I.e for each block belonging to the cltv_expiry range,
Bob pays Alice a penalty from his `counterparty_balance` (on Alice's commitment_tx)
where "local channel time" is ticked by some monotonic counter. This tree of
scripts would become valid to be spend after some timelock enforced grace delay.

It should be noted, that if the HTLC routing is extending beyond the reach of
Bob, Bob has no guarantee that he will get the HTLC secret before the upper
bound of Alice's cover penaly script is reached on the Alice - Bob channel, e.g
time T + 200

As soon as the offered HTLC has been committed on both parties commitment
transactions (Alice is the latest's one to receive the RAA), Alice and Bob
starts to exchange ping-pong messages where each message is increasing the
monotonic counter. Those messages might have as a data payload the preimage
for which the Alice to Bob offered HTLC is pending.

While Bob might have received the HTLC secret from Caroll at absolute blockchain
time T + 100, and give it to Alice at time T + 110 i.e before the expiration of
the hard `cltv_expiry`, Alice is always in a position to equivocate and said she
never received the preimage from Bob ping-pong message.

So this strawman protocol is obviously broken.

Let's consider the same protocol, with few differences, the ping-pong messages
between Alice and Bob are scheduled on some hearbeat rythm, so message happens
every X, in way that Alice cannot guess if yes or no, a secret exchange did happen
between Bob and Caroll about the next hop HTLC secret.

The penalty scripts are also modified where Bob can now prove a ping message
at time T + 110 has been viewed by Alice, with the correct HTLC secret. So
Alice would make a claim by broadcasting a transaction to claim the output,
and Bob would be able to dismiss the penaly with a valid proof of preimage
transfer.

Other modification, all ping-ping messages sent by Bob from Alice would be
now an oblivious transfer, where Alice would sign all the pongs and the
incremented counter [6], among those pongs would be a ciphered HTLC secret.
This mechanism allows Bob to obtain an off-chain proof (e.g go to unblind the
signed HTLC secret) that Alice has seen a preimage at time T + 110, and they
can now update the HTLC commitment txn, back to the normal flow. If Alice stucks
the channel, she "knows" that she would loss the proving game with Bob.

However, this strawman protocol still present 2 bottlenecks, that are described
in their main lines.

One, there is no guarantee that Alice engage in the heartbeat protocol, so
the HTLC commitment transaction should present some scripting path where the
ping-pong messages are numbered, and if this has not reach some threshold
before the `cltv_expiry`, she got punished on her local balance. One counterparty
should always engaged in the "amnesic" knowledge transfer, under the risk of
on-chain punishment.

Two, Alice and Caroll can always collude to have Bob never getting the HTLC
secret and as such being penalized with the highest fee on the Alice - Bob
channel. Somehow, Bob should be able to produce a proof proving that the
heartbeat protocol has played out in integrality on the Bob-Caroll channel
and that no HTLC secret was ever learn from Caroll. That's where "garbled
circuits" might be useful in minimizing the amount of knowledge leaked from
Bob-Caroll channel to Alice, while still ensuring fairness [7].

To conclude, this short post is advancing the idea that oblivious transfer
class of protocol, might be able to solve the channel jamming issue where
the messages are exchanged without all the parties "knowing" what has been
exchanged, and being punished by on-chain scripts, if the equivocate from
the knowledge transfer they engage into. I'm not making the claim that this
strawman protocol is fully sound game-theoretic wise, though I found if a
shared notions of time can be enforced among 2 Lightning channel counterparties,
the implications are wider than just solving channel jamming.

Anyway, I don't have time to flush more the ideas exposed here [8], though I
was eager to mention them if some people are bored and wish to play with
interesting cryptographic primitives actually solving real-world lightning
problems.

Cheers,
Antoine
OTS hash: 98c12f58d4e39e85427cca156cc548d225b2ecb45296be70a93d3534b77aa1c7

[0] "How to Generate and Exchange Secrets" - Andrew Yao, 1986.
[1] See "Chapter 4 - Solution Design Space" - "Solving channel jamming
issue of the lightning network", Naumenko / Riard, 2022
[2] As the joking goes "Oh a workable solution to a bitcoin problem involving
a consensus change, that's a very ice theoretical paper you've here, sir!".
[4] See for more - "Unjamming Lightning: A Systematic Approach",
Clara Shikhelman and Sergei Tikhomirov, 2022.
[4] https://delvingbitcoin.org/t/fee-based-spam-prevention-for-lightning/1524/2
[5] "If a tree falls in the forest and no one is around to hear it, does it
make a sound ?" "A Network of Micropayments Channels Can Solve Scalability" -
Lightning Network paper.
[6] E.g counter could fit in a nSequence field.
[7] I'm wawing aside the biggest witness trace that Lightning nodes might
have to pay, as one downside of this kind of solution compared to the other
ones.
[8] Yes, the subject would have deserved a real research paper, but writing your
own bitcoin full-node it's real work, no kidding.