* [bitcoindev] LN-GAP : Lightning governed by arbitrary programs
@ 2026-10-04 14:51 waxwing/ AdamISZ
0 siblings, 0 replies; only message in thread
From: waxwing/ AdamISZ @ 2026-10-04 14:51 UTC (permalink / raw)
To: Bitcoin Development Mailing List
[-- Attachment #1.1: Type: text/plain, Size: 10937 bytes --]
Hi list,
Paper
https://github.com/AdamISZ/ln-gap/blob/master/docs/paper/lngap-short.pdf
(my words)
and
Repo: https://github.com/AdamISZ/ln-gap (AI generated 95% , see note at
start of README)
The party trick here is: play chess in a Lightning channel and have the
winner get the pot, "trustlessly". Same for blackjack, which is more
interesting as a hidden information game. Non-party-trick applications, in
a moment.
Before we address the scare quotes in the room, let's mention the main
concept: you can always play such challenge-response games on bitcoin
itself, up to some complexity limit, leveraging the idea that "to disprove
something can be exponentially smaller than to prove something", so like, i
show one piece on one square of the chessboard that proves your move is
illegal; things like that. But playing those games on chain for 50 rounds
is basically never practical/desirable/economic/scalable. So you obviously
*want* to do it in a channel or similar.
The problem with that is that, as the paper's conclusion says "Lightning
cannot adjudicate silence". So stalling forces games onchain. Fine for
Lightning's own game, which only has like 3 rounds. The trick here is to
adjudicate silence, and specifically adjudicate only that, in what's called
a "venue".
The basic picture for resolving disputes:
(wrong move or no move) -> Alice posts tx 'claim' that says 'no move or
wrong move from Bob on move d' -> (optional) Bob posts tx 'rebuttal' that
says 'here is my move for move d and here is its attestation by the venue'
-> (optional) Alice posts 'disproof' that says 'here is the exact predicate
in your move that is illegal' or 'here is proof that the venue attests you
didn't post the move in time'.
You end up with usually zero, but max 3 transactions (4 depending on how
you squint at it), hence O(1), independent of the complexity of the program
under dispute (more on that below; it's not true naively, due to e.g. stack
limits, if you do it straightforwardly, though chess and similar work fine).
(The biggest of those transactions turns out to be 'rebuttal', but it tends
to be no more than 20-40 kvB which is fine; as noted, stack limits are what
you tend to hit first.)
So back to this "trustlessly" claim:
Interestingly, a "venue" does not have to be a proof of publication
*ledger*. That is, it doesn't need to enforce unique history (but proof of
publication or not *is* the idea). It just needs to say "Signed message X
was or was not published before time T" and that's it. Equivocation would
be addressed by the signature from the contract participant. The venue
doesn't need to know what X means (a la client side validation).
So as a single point of failure such a 'venue' would not be great. Alice
and Bob are in a contract. Vernon the venue colludes with Bob. Alice makes
a move, Bob stalls, Alice posts the "he stalled" claim transaction onchain,
Bob then posts his valid move as a rebuttal in the next transaction, and
his move is legal, so Alice cannot disprove, and *cannot* post "the venue
said he didn't post his move on time" because Vernon refused to provide
that. So collusion enables stalling and prevents its punishment.
But even this crap version has the property that Vernon never gets to hold
the money, which removes some classes of attack, and allows contracting in
pure bitcoin terms on complex contracts. And on slower timescale games,
Vernon's lying about the move being published can even be entirely
publically provable, burning reputation, future fee stream and possibly a
timelocked bond.
What LN-GAP as documented and coded does: the venue is a committee
(realistically up to hundreds not more for technical reasons; the demos use
5) drawn, perhaps randomly, from a larger set. They can post timelocked
bonds to participate. Crucially, they can atomically receive fees over
channels using something I'm calling "EC-OTS", see paper for details, with
their publications, so there is a positive incentive to participate.
Liveness is 1 of n, i.e. only one committee member has to be willing to
publish your move/state update. But a threshold majority must attest the
fact that you didn't move before your deadline, and it's that that can
resolve the 'stalling' problem. For actually posting illegal moves/state
transitions, we apply the 'disproving is smaller' principle above:
demonstrate illegality on one leaf of a tapscript tree.
Anyway the paper argues for how some combination of public entities with
reputations to lose (and who don't have nasty custody of user funds issues;
they don't even know what the contracts adjudicate, for that matter - their
lawyers will be happy!), with some anonymous but timelocked-bonded entities
as a committee; the latter subset help with the liveness argument, but can
more easily be sybiled; the former help with credibility due to high
reputation burn (vs low value timelocked burn, probably, for anon entities;
though you *could* argue for all-anon, too).
Running as a member of the venue is extremely lightweight; no computation
burden, no history burden. What *is* burdensome for both contract
participants and venue members is: liveness is leaned on heavily. You lose
if you go offline for a long enough period.
Applications: games are fun and are the obvious application of the idea,
being multi-round, defined ruleset interactions. Others: consider the
classic filecoin application, but with a twist: the service provider offers
the user a contract where they prove they're holding the 1TB file every 1
day with some merkle proof scheme, and the user is required to pay on that
schedule, but with a twist: if the service provider cannot provide the
proof one day, they have to give up a big deposit (effectively insurance
payout that compensates the user for loss of valuable files). This latter
mechanism is distinctive to this scheme; neither filecoin/sia nor some
other schemes that have been proposed do this "adjudicate silence" part to
pay back the aggrieved party.
Proof of computation is similar to proof of storage. A note of comparison:
garbled circuits schemes, while very heavy in general, can do the one-off
resolution of a payment via a complex computation, without infrastructure
like 'venues'. But they don't solve stalling (not that they are claimed
to). A similar comment about ZKCP. Lots of little nuances there, but,
sidetrack.
Where it gets really interesting is where I try to justify "arbitrary". As
in, any program of any complexity. This is clearly nonsense for a program
with a very large internal state, because Bitcoin Script does not support a
stack size of greater than 1000, even if taproot cleverly gives you the
ability to resolve an ungodly large amount of predicates via its MAST style
tree.
In Section 7 of the short paper, it's argued that you can do the same thing
as BitVMX [1], which is an extension of the original BitVM idea [2], that
is: you can resolve a dispute over a computation with a bisection. BitVMX
does that onchain, and you're talking non-trivial, say, 30 rounds. If we do
that bisection *off-chain* we're basically using the venue in the same way
as above, thereby keeping an O(1) footprint onchain in dispute (although to
be fair it's already O(log n), but even that may be impractically large).
The codebase currently just holds a proof of concept example that it's
possible, though it's close to the stack limit [3] . This could work for
literally *any* guest program, hence the 'arbitrary programs' claim of the
title.
I briefly muse about how that could enable things like bridges to rollups,
I guess in theory that might make sense, albeit it's a radical reimagining
of what 'bridge' even is (the coins don't go anywhere; liquidity is
required etc). Which brings me to my final comments:
A big part of this whole line of thinking is "even though a bilateral
contract with fixed liquidity is of course extremely limited, it buys a lot
in terms of privacy, scale, speed from being Lightning-style". Bilateral
contracts are not multilateral contracts but it is not at all crazy to
imagine doing the same type of thing with shared facts, shared across
multiple such contracts. Imagine e.g. auctions. I was originally quite
enthused about that idea specifically, but got sidetracked :)
The venue, as noted in the paper, has a DLC oracle flavor to it (indeed the
EC-OTS observation is very similar to the DLC observation), but it's as
proposed a very specific kind of oracle: it attests the timing of a
self-certifying fact (the mover's move and their signature) rather than an
external world event. So the whole 'committee of oracles' that is often
discussed for DLCs can make even more sense here as they're only
responsible for recording what, at slower timescales, is just objectively
true.
Cheers,
AdamISZ/waxwing
[1] https://arxiv.org/abs/2405.06842 BitVMX-CPU
[2] idea goes way back, Arbitrum, TrueBit and probably some academic papers
much earlier, I forget
[3] I quote some concrete details from the long version of the paper:
"The program is BitVMX’s Groth16 verifier, a RISC-V build of a
pairing-based verifier, checking a RISC0 [12] proof that a STARK receipt of
a guest program is valid. On a genuine proof it halts with success after
478,727,216 steps. Challenged, BitVMX’s search code takes 29 rounds (some
nine minutes off chain), which is a contract of 119 depths: 2,058
pre-signed transactions, with 1,919 disprove leaves and 62 prove leaves at
the final depth of the first phase. All 59 moves of that phase were sealed
by the venue, and on regtest the dispute was the claim (220 vB), the
rebuttal (24.3 kvB, as re-measured on a smaller program: its size depends
on the heads, not the program) and the proof of the halting ecall (58.5
kvB). The on-chain cost does not depend on the program’s length. The leaves
are large (a prove leaf is about 228 KB of script, at a peak stack of 948
of the 1,000 allowed), but they depend only on the contract’s keys, so they
are built once per contract and channel updates reuse them." Notice here
that again the stack size is the real limit. Also note that the performance
do not depend on the complexity of the guest program, since what we're
disputing is the groth16 proof.
--
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/d10324a6-8067-427e-aa31-5886dd22e4fen%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 11135 bytes --]
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2026-10-04 14:55 UTC | newest]
Thread overview: (only message) (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2026-10-04 14:51 [bitcoindev] LN-GAP : Lightning governed by arbitrary programs waxwing/ AdamISZ
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox