MIME-Version: 1.0
References: <CAMhCMoH9uZPeAE_2tWH6rf0RndqV+ypjbNzazpFwFnLUpPsZ7g@mail.gmail.com>
 <CALZpt+GVe0XTdWqV=LAcOj=nq+k2DEFqc+sKyxAujLDBR7bYbQ@mail.gmail.com>
 <CAMhCMoEONv3jriBU3qwm0pt75iF_sgra1H2Z4rOF8u+e7hs_cw@mail.gmail.com>
 <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 <salvatore.ingala@gmail.com>
Date: Thu, 1 Dec 2022 09:47:22 +0100
Message-ID: <CAMhCMoGabEASO9CGc1hAMpYZn4nWH5D8XFs3eFcSSFAitSFUGA@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>, 
 Rijndael <rot13maxi@protonmail.com>
Content-Type: multipart/alternative; boundary="000000000000a90efd05eec04528"
Subject: Re: [bitcoin-dev] Merkleize All The Things
Precedence: list

--000000000000a90efd05eec04528
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hello Rijndael,


On Wed, 30 Nov 2022 at 23:09, Rijndael <rot13maxi@protonmail.com> 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

<div dir=3D"ltr"><div dir=3D"ltr">Hello Rijndael,<div><br></div><div><br></=
div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_at=
tr">On Wed, 30 Nov 2022 at 23:09, Rijndael &lt;<a href=3D"mailto:rot13maxi@=
protonmail.com">rot13maxi@protonmail.com</a>&gt; wrote:<br></div><blockquot=
e class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px s=
olid rgb(204,204,204);padding-left:1ex">
   =20
 =20
  <div>
    <p>Hello Salvatore,</p>
    <p>I found my answer re-reading your original post:<br>
      &gt; 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.</p></div></blockquote><div><div>You are correct, t=
he computation step encoded in a leaf needs to be simple enough for Script =
to verify it.</div><div><br></div><div>For the academic purpose of proving =
completeness (that is, any computation can be successfully &quot;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}.<br></div><div><br></div><div>In practice, you would want to uti=
lize Script to its fullest, so for example you wouldn&#39;t compile a SHA25=
6 computation to something else =E2=80=93 you&#39;d rather use OP_SHA256 di=
rectly.</div></div><div>=C2=A0<br></div><blockquote class=3D"gmail_quote" s=
tyle=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);pad=
ding-left:1ex">
    <p>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&#39;s execution
      traces that differ, and then rewards the coins to the participant
      who&#39;s &quot;after-value&quot; is computed by the step&#39;s opera=
tion applied to
      the &quot;before value&quot;. 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&#39;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)?</p></blockquote><div><br></div><div>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.<br><br>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 &quot;symmetric&quot;) states.<br><br>=3D=3D=3D=3D=3D=3D=3D=3D</div><d=
iv><br></div><div>Since we are talking about the fact that f is committed t=
o in the contract, I&#39;ll take the chance to extend on this a bit with a =
fun construction on top.</div><div>It is well-known in the academic literat=
ure of state channels that you can create contracts where even the function=
 (&quot;program&quot;, or &quot;contract&quot;) is not decided when the cha=
nnel is created.<br></div><div><br></div><div>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 (&quot;code&quot;) on the &qu=
ot;data&quot; given to it as input.</div><div>Since we can do fraud proofs =
on statements &quot;f(code, data) =3D=3D output&quot;, we could build contr=
acts where the &quot;code&quot; itself is chosen later.</div><div><br></div=
><div>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.</div><div><br></div><div>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?).</div><div><br></div><div>We should probab=
ly start by implementing testnet rock-paper-scissors in MATT, though :)</di=
v><div><br></div><div>Best,</div><div>Salvatore Ingala</div></div></div>

--000000000000a90efd05eec04528--