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.