[bitcoindev] LN-GAP : Lightning governed by arbitrary programs

[bitcoindev] LN-GAP : Lightning governed by arbitrary programs

[waxwing/ AdamISZ]

[-- 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 --]