Return-Path: Received: from smtp3.osuosl.org (smtp3.osuosl.org [IPv6:2605:bc80:3010::136]) by lists.linuxfoundation.org (Postfix) with ESMTP id 9290EC002D for ; Thu, 1 Dec 2022 08:47:37 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp3.osuosl.org (Postfix) with ESMTP id 6DBCE60E02 for ; Thu, 1 Dec 2022 08:47:37 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 6DBCE60E02 Authentication-Results: smtp3.osuosl.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20210112 header.b=k/ZDILkK X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -2.098 X-Spam-Level: X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Received: from smtp3.osuosl.org ([127.0.0.1]) by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id veMXmumAd5N4 for ; Thu, 1 Dec 2022 08:47:36 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 188C360C05 Received: from mail-lf1-x134.google.com (mail-lf1-x134.google.com [IPv6:2a00:1450:4864:20::134]) by smtp3.osuosl.org (Postfix) with ESMTPS id 188C360C05 for ; Thu, 1 Dec 2022 08:47:36 +0000 (UTC) Received: by mail-lf1-x134.google.com with SMTP id bp15so1396396lfb.13 for ; Thu, 01 Dec 2022 00:47:35 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :from:to:cc:subject:date:message-id:reply-to; bh=lI47GJAoyHjkvKC8TjDiSqNz9giQlUTaHdrUwjT3yWo=; b=k/ZDILkKnqIEPWa9MLwPdfmH1LWNh3Nu3yz/lysTh5Sp3V7NytNU2y6aOOwUloLqSm YlVkKpMyeAcvY7I88DBlm+qORz3IND3XAwRZJTE8bLaWTi15BGHEOFaWSSTNAeFV5ioH mmRaeAxGfxL/It0iMy3pCSDnGPjpdEf3lg5bUUiPSjI4PmX0+qVwvSNzj0h8pSUMpFv3 Jg3mSEb2a8LQzRXpXHKt3XtKx25DJbkheIDArasINMNuQ9XabCrT+KdV/Lq+5z7fCp1M U7/6S2znW2kkMZAqEBgnRe3b0b++sD9isRc7DsT8j2RAA4gbKWr2g5ohj03XBaU9wGFG YHTA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=lI47GJAoyHjkvKC8TjDiSqNz9giQlUTaHdrUwjT3yWo=; b=zmX6xrC0zswfo+eDM4qWrLif7rX4iz6o0HnLN0jtk7cE6ah9QQ/SWjVs3W70oveVc1 AECLIzCWKck3aJmGk5v26kBkm7XiMU7wn4y79mtZo4rvJQXVpMqqhKM8qrrPzeeq1KSv dW7Gt+/G/HcMxz6jl/dkR9ms9BILKryq8GbJ0q/06cSfTkoZ4OYItQ/Z5QvRa2F43q1u woGNScz/ui/SggruKQ8L0cD3mkJZEqROenr5AFMdbMBXhb9ykkxm1nkSP7b0iK9fNuKG RUmerVvg9itg7hLw9DPFGC8emOcBaN4J6mx8TVpD1PUE2PtEh47PIhpawPuQnj8yGAoY sm+Q== X-Gm-Message-State: ANoB5pl9e+zyeDIk/qVuzkBQ9TLvVqZx20gnEv6s67sEpgQ/0u0YoN9Q Z93gkaQKCFTs8tfDZwgDt5+VNXHxH0MwkvX3cff6n9ICgzk= X-Google-Smtp-Source: AA0mqf7c25d6B3wRxavhxemfU4N8c/3Gcm+3utGeS0J9MwgmAJEzcjco5JKsyg9Yfm0YVZ+AwhCrZVHg1axhhNgxTCs= X-Received: by 2002:a19:435c:0:b0:4b0:38f1:1784 with SMTP id m28-20020a19435c000000b004b038f11784mr14697454lfj.335.1669884453390; Thu, 01 Dec 2022 00:47:33 -0800 (PST) MIME-Version: 1.0 References: <0f352f70-c93a-614f-e443-67d198ec2c26@protonmail.com> <7f3674d1-c1ad-9a82-e30f-7cf24d697faf@protonmail.com> In-Reply-To: <7f3674d1-c1ad-9a82-e30f-7cf24d697faf@protonmail.com> From: Salvatore Ingala Date: Thu, 1 Dec 2022 09:47:22 +0100 Message-ID: To: Bitcoin Protocol Discussion , Rijndael Content-Type: multipart/alternative; boundary="000000000000a90efd05eec04528" X-Mailman-Approved-At: Thu, 01 Dec 2022 11:52:14 +0000 Subject: Re: [bitcoin-dev] Merkleize All The Things X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 01 Dec 2022 08:47:37 -0000 --000000000000a90efd05eec04528 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hello Rijndael, On Wed, 30 Nov 2022 at 23:09, Rijndael wrote: > Hello Salvatore, > > I found my answer re-reading your original post: > > During the arbitration phase (say at the i-th leaf node of M_T), any > party can win the challenge by providing correct values for tr_i =3D (st_= i, > op_i, st_{i + 1}). Crucially, only one party is able to provide correct > values, and Script can verify that indeed the state moves from st_i to > st_{i + 1} by executing op_i. The challenge is over. > You are correct, the computation step encoded in a leaf needs to be simple enough for Script to verify it. For the academic purpose of proving completeness (that is, any computation can be successfully "proved" by the availability of the corresponding fraud proof), one can imagine reducing the computation all the way down to a circuit, where each step (leaf) is as simple as what can be checked with {OP_NOT, OP_BOOLAND, OP_BOOLOR, OP_EQUAL}. In practice, you would want to utilize Script to its fullest, so for example you wouldn't compile a SHA256 computation to something else =E2=80= =93 you'd rather use OP_SHA256 directly. > That raises leads to a different question: Alice initially posts a > commitment to an execution trace of `f(x) =3D y`, `x`, and `y`. Bob Disag= rees > with `y` so starts the challenge protocol. Is there a commitment to `f`? = In > other words, the dispute protocol (as I read it) finds the leftmost step = in > Alice and Bob's execution traces that differ, and then rewards the coins = to > the participant who's "after-value" is computed by the step's operation > applied to the "before value". But if the participants each present valid > steps but with different operations, who wins? In other words, Alice coul= d > present [64, DECREMENT, 63] and Bob could present [64, INCREMENT, 65]. > Those steps don't match, but both are valid. Is there something to ensure > that before the challenge protocol starts, that the execution trace that > Alice posts is for the right computation and not a different computation > that yields a favorable result for her (and for which she can generate a > valid merkle tree)? > The function f is already hard-coded in the contract itself, by means of the tree of scripts =E2=88=92 that already commits to the possible futures. Therefore, once you are at state S14, you know that you are verifying the 6th step of the computation; and the operation in the 6th step of the computation depends solely on f, not its inputs. In fact, you made me realize that I could drop op_i from the i-th leaf commitment, and just embed the information in the Script of that corresponding state. Note that the states S0 to S14 of the 256x game are not _all_ the possible states, but only the ones that occurred in that execution of the contract (corresponding to a path from the root to the leaf of the Merkle tree of the computation trace), and therefore the ones that materialized in a UTXO. Different choices made by the parties (by providing different data, and therefore choosing different branches) would lead to a different leaf, and therefore to different (but in a certain sense "symmetric") states. =3D=3D=3D=3D=3D=3D=3D=3D Since we are talking about the fact that f is committed to in the contract, I'll take the chance to extend on this a bit with a fun construction on top= . It is well-known in the academic literature of state channels that you can create contracts where even the function ("program", or "contract") is not decided when the channel is created. Since f is generic, we can choose f itself to be a universal Turing machine. That is, we can imagine a function f(code, data) that executes a program ("code") on the "data" given to it as input. Since we can do fraud proofs on statements "f(code, data) =3D=3D output", w= e could build contracts where the "code" itself is chosen later. For example, one could build a universal state channel, where parties can enter any contract among themselves (e.g.: start playing a chess game) entirely inside the channel. The state of this universal channel would contain all the states of the individual contracts that are currently open in the channel, and even starting/closing contracts can happen entirely off-chain. I believe these constructions are practical (the code of universal Turing machines is not really complicated), so it might be worth exploring further to figure out useful applications of this approach (supercharging lightning?). We should probably start by implementing testnet rock-paper-scissors in MATT, though :) Best, Salvatore Ingala --000000000000a90efd05eec04528 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hello Rijndael,



On Wed, 30 Nov 2022 at 23:09, Rijndael <rot13maxi@protonmail.com> wrote:
=20 =20

Hello Salvatore,

I found my answer re-reading your original post:
> During the arbitration phase (say at the i-th leaf node of M_T), any party can win the challenge by providing correct values for tr_i =3D (st_i, op_i, st_{i + 1}). Crucially, only one party is able to provide correct values, and Script can verify that indeed the state moves from st_i to st_{i + 1} by executing op_i. The challenge is over.

You are correct, t= he computation step encoded in a leaf needs to be simple enough for Script = to verify it.

For the academic purpose of proving = completeness (that is, any computation can be successfully "proved&quo= t; by the availability of the corresponding fraud proof), one can imagine r= educing the computation all the way down to a circuit, where each step (lea= f) is as simple as what can be checked with {OP_NOT, OP_BOOLAND, OP_BOOLOR,= OP_EQUAL}.

In practice, you would want to uti= lize Script to its fullest, so for example you wouldn't compile a SHA25= 6 computation to something else =E2=80=93 you'd rather use OP_SHA256 di= rectly.
=C2=A0

That raises leads to a different question: Alice initially posts a commitment to an execution trace of `f(x) =3D y`, `x`, and `y`. Bob Disagrees with `y` so starts the challenge protocol. Is there a commitment to `f`? In other words, the dispute protocol (as I read it) finds the leftmost step in Alice and Bob's execution traces that differ, and then rewards the coins to the participant who's "after-value" is computed by the step's opera= tion applied to the "before value". But if the participants each present va= lid steps but with different operations, who wins? In other words, Alice could present [64, DECREMENT, 63] and Bob could present [64, INCREMENT, 65]. Those steps don't match, but both are valid. Is there something to ensure that before the challenge protocol starts, that the execution trace that Alice posts is for the right computation and not a different computation that yields a favorable result for her (and for which she can generate a valid merkle tree)?


The function f is a= lready hard-coded in the contract itself, by means of the tree of scripts = =E2=88=92 that already commits to the possible futures. Therefore, once you= are at state S14, you know that you are verifying the 6th step of the comp= utation; and the operation in the 6th step of the computation depends solel= y on f, not its inputs. In fact, you made me realize that I could drop op_i= from the i-th leaf commitment, and just embed the information in the Scrip= t of that corresponding state.

Note that the states S0 to S14 of the= 256x game are not _all_ the possible states, but only the ones that occurr= ed in that execution of the contract (corresponding to a path from the root= to the leaf of the Merkle tree of the computation trace), and therefore th= e ones that materialized in a UTXO. Different choices made by the parties (= by providing different data, and therefore choosing different branches) wou= ld lead to a different leaf, and therefore to different (but in a certain s= ense "symmetric") states.

=3D=3D=3D=3D=3D=3D=3D=3D

Since we are talking about the fact that f is committed t= o in the contract, I'll take the chance to extend on this a bit with a = fun construction on top.
It is well-known in the academic literat= ure of state channels that you can create contracts where even the function= ("program", or "contract") is not decided when the cha= nnel is created.

Since f is generic, we can ch= oose f itself to be a universal Turing machine. That is, we can imagine a f= unction f(code, data) that executes a program ("code") on the &qu= ot;data" given to it as input.
Since we can do fraud proofs = on statements "f(code, data) =3D=3D output", we could build contr= acts where the "code" itself is chosen later.

For example, one could build a universal state channel, where parties= can enter any contract among themselves (e.g.: start playing a chess game)= entirely inside the channel. The state of this universal channel would con= tain all the states of the individual contracts that are currently open in = the channel, and even starting/closing contracts can happen entirely off-ch= ain.

I believe these constructions are practical (= the code of universal Turing machines is not really complicated), so it mig= ht be worth exploring further to figure out useful applications of this app= roach (supercharging lightning?).

We should probab= ly start by implementing testnet rock-paper-scissors in MATT, though :)

Best,
Salvatore Ingala
--000000000000a90efd05eec04528--