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>
 <CAMhCMoGabEASO9CGc1hAMpYZn4nWH5D8XFs3eFcSSFAitSFUGA@mail.gmail.com>
In-Reply-To: <CAMhCMoGabEASO9CGc1hAMpYZn4nWH5D8XFs3eFcSSFAitSFUGA@mail.gmail.com>
From: Billy Tetrud <billy.tetrud@gmail.com>
Date: Tue, 13 Dec 2022 00:59:27 -0600
Message-ID: <CAGpPWDZkUYW=Qb763TPzUa6yUf217nh0Bo+O9Qyf=WS2pUQUYA@mail.gmail.com>
To: Salvatore Ingala <salvatore.ingala@gmail.com>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000114dad05efb02a41"
Subject: Re: [bitcoin-dev] Merkleize All The Things
Precedence: list

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

Re Verkle trees, that's a very interesting construction that would be super
useful as a tool for something like Utreexo. A potentially substantial
downside is that it seems the cryptography used to get those nice
properties of Verkle trees isn't quantum safe
<https://vitalik.ca/general/2021/06/18/verkle.html>. While a lot of things
in Bitcoin seems to be going down the path of quantum-unsafe (I'm looking
at you, taproot), there are still a lot of people who think quantum
safety is important in a lot of contexts.

On Thu, Dec 1, 2022 at 5:52 AM Salvatore Ingala via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> 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 simpl=
e
> enough for Script to verify it.
>
> For the academic purpose of proving completeness (that is, any computatio=
n
> can be successfully "proved" by the availability of the corresponding fra=
ud
> 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 Disa=
grees
>> 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 vali=
d
>> steps but with different operations, who wins? In other words, Alice cou=
ld
>> present [64, DECREMENT, 63] and Bob could present [64, INCREMENT, 65].
>> Those steps don't match, but both are valid. Is there something to ensur=
e
>> 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 future=
s.
> 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 possibl=
e
> 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 UTX=
O.
> Different choices made by the parties (by providing different data, and
> therefore choosing different branches) would lead to a different leaf, an=
d
> 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 ca=
n
> create contracts where even the function ("program", or "contract") is no=
t
> 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",=
 we
> 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 ope=
n
> 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 furth=
er
> 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
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

--000000000000114dad05efb02a41
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Re Verkle trees, that&#39;s a very interesting constructio=
n that would be super useful as a tool for something like Utreexo. A potent=
ially substantial downside is that it seems the cryptography used to get th=
ose nice properties of Verkle trees <a href=3D"https://vitalik.ca/general/2=
021/06/18/verkle.html">isn&#39;t quantum safe</a>. While a lot of things in=
 Bitcoin seems to be going down the path of quantum-unsafe=C2=A0(I&#39;m lo=
oking at you, taproot), there are still a lot of people who think quantum s=
afety=C2=A0is important=C2=A0in a lot of contexts.</div><br><div class=3D"g=
mail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Thu, Dec 1, 2022 at 5:=
52 AM Salvatore Ingala via bitcoin-dev &lt;<a href=3D"mailto:bitcoin-dev@li=
sts.linuxfoundation.org">bitcoin-dev@lists.linuxfoundation.org</a>&gt; wrot=
e:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0=
.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"l=
tr"><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_attr">On Wed, 3=
0 Nov 2022 at 23:09, Rijndael &lt;<a href=3D"mailto:rot13maxi@protonmail.co=
m" target=3D"_blank">rot13maxi@protonmail.com</a>&gt; wrote:<br></div><bloc=
kquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:=
1px solid 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>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>

--000000000000114dad05efb02a41--