path: root/99/519a4b167b6edbde751e40bc08e75061a24aed

Return-Path: <fresheneesz@gmail.com>
Received: from smtp1.osuosl.org (smtp1.osuosl.org [IPv6:2605:bc80:3010::138])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 733F3C002D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 13 Dec 2022 06:59:46 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp1.osuosl.org (Postfix) with ESMTP id 4100981306
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 13 Dec 2022 06:59:46 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org 4100981306
Authentication-Results: smtp1.osuosl.org;
 dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com
 header.a=rsa-sha256 header.s=20210112 header.b=hiWeVrMa
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 smtp1.osuosl.org ([127.0.0.1])
 by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id oueerG5go1t4
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 13 Dec 2022 06:59:45 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org ADC54812E3
Received: from mail-ej1-x632.google.com (mail-ej1-x632.google.com
 [IPv6:2a00:1450:4864:20::632])
 by smtp1.osuosl.org (Postfix) with ESMTPS id ADC54812E3
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 13 Dec 2022 06:59:44 +0000 (UTC)
Received: by mail-ej1-x632.google.com with SMTP id n20so34284184ejh.0
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 12 Dec 2022 22:59:44 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112;
 h=cc:to:subject:message-id:date:from:in-reply-to:references
 :mime-version:from:to:cc:subject:date:message-id:reply-to;
 bh=cLv50uW8sjOq1i7QIdXGHDCQDit2ujnQOqrHA1Ob100=;
 b=hiWeVrMaCkCQ1AXNLGg/z/e5urlBGgVKB9MTl6PjQ3fQk9Y2/l9n0w7jbPa9WYri43
 IcEV7yT/xoih4HFhPKWcyIXloK4wkQsDoQ5C7nAp5TX1Pe4sJTEH4yVhHFMcFw181sGn
 DxvXklCND2fCiwf5x8FXXcKpkZSu6lH3dMoIBxQQtQOk4QSovyHxGGTehJuzK4YEALVD
 H4+jnYwv/wqUDvKwaC9EdMJx3phjVea6NagHikQkIEcXLBeMvBnYLipApEGNZ5jo6GO4
 4IIJ1Zy3YPMd5b/9EON4OAcE96yjQsfSEqtnufwaDotMGxqvvqsLSc+d4EV+NwgGQSsB
 P0CQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20210112;
 h=cc: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=cLv50uW8sjOq1i7QIdXGHDCQDit2ujnQOqrHA1Ob100=;
 b=3cGG5/wG+2M73fMyKAu7uucbxHBVcdFxn70MAzenI1ZPSSYNkT1M6h8T9H4wj8TCS7
 FrjzdZhLJbdKLqCtTDLA1goEjSYpYCBFHHj5rmyDqyV2owW+/Bkgu/xwPB2UQ2PRdwZr
 8O7SDaFcRsyNMwBekzhqmFLG7WB4UC/CAHXpBRzN4ejnTqqDxIkbd3XtXJevtDgP8EMW
 dQbAFWjNREsns7aKGlAmU+T51MLKbk09Yk3DwYii5v0zJ9q1UkTjay/7NrU+ShsfKAsE
 JMTm6C/oh7/rMM6Opp/BoF8jZB4kkQRmHKTqh7rVKXlWl6+W4zi4wRABXwLbX/SAjfux
 f7KQ==
X-Gm-Message-State: ANoB5pkZkpP7u1XAtRmhCAXm1fGpvfC6mKc5X7aUo35Sc8Upqzc0KK/Y
 flBD521/Nkd4tyLaIyos549ADuegnUlyFRNXQ27eZk5+
X-Google-Smtp-Source: AA0mqf4JSsztwYQz+C1FAG4we9o8W4kgcIC8LyJ+/PSjsLOcF5rl4tTlMfB/5IcN8pX0FQP63PTRhSme4KQ5cMWx4KM=
X-Received: by 2002:a17:907:7f1f:b0:7c1:6b1f:e131 with SMTP id
 qf31-20020a1709077f1f00b007c16b1fe131mr559346ejc.557.1670914782611; Mon, 12
 Dec 2022 22:59:42 -0800 (PST)
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"
X-Mailman-Approved-At: Tue, 13 Dec 2022 13:07:59 +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 <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Tue, 13 Dec 2022 06:59:46 -0000

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