path: root/67/1dd0f19780310296aff93f1e49c3292d865342

Return-Path: <johanth@gmail.com>
Received: from smtp4.osuosl.org (smtp4.osuosl.org [IPv6:2605:bc80:3010::137])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 7B3CEC002A
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 28 Apr 2023 08:48:21 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp4.osuosl.org (Postfix) with ESMTP id 61E354007C
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 28 Apr 2023 08:48:21 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 61E354007C
Authentication-Results: smtp4.osuosl.org;
 dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com
 header.a=rsa-sha256 header.s=20221208 header.b=ozY+urYE
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -2.099
X-Spam-Level: 
X-Spam-Status: No, score=-2.099 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,
 RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001]
 autolearn=ham autolearn_force=no
Received: from smtp4.osuosl.org ([127.0.0.1])
 by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id 9gB_v5tD1R8m
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 28 Apr 2023 08:48:20 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org DD1C240863
Received: from mail-yw1-x112e.google.com (mail-yw1-x112e.google.com
 [IPv6:2607:f8b0:4864:20::112e])
 by smtp4.osuosl.org (Postfix) with ESMTPS id DD1C240863
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 28 Apr 2023 08:48:19 +0000 (UTC)
Received: by mail-yw1-x112e.google.com with SMTP id
 00721157ae682-54fc6949475so110575627b3.3
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 28 Apr 2023 01:48:19 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=gmail.com; s=20221208; t=1682671699; x=1685263699;
 h=content-transfer-encoding:cc:to:subject:message-id:date:from
 :in-reply-to:references:mime-version:from:to:cc:subject:date
 :message-id:reply-to;
 bh=/NZpNDrkeNYDhtyGzOtndO1weOFBADjh0piOJae0kls=;
 b=ozY+urYEQ/Fe/Ecxba/9+4jup768z+4xu41v4Mnkx+LpvmCUP8wWLw9vk317z3BoTz
 gYX6k8XfgHpM/R/expu2X6VMppB7N7OfUCpJUVmoo00bgBYnhhkIr9e4+S5NY8YQwHP7
 CgpO0YTL0ZydUKJMN50RROImK/Uc/qtxuxMx6yKO87/OltsLj1TVhLzrI0h1EUZy+bi1
 i/C+8uVYPMmaAdt78rlYNiy0RKX+O+e/Yctg2mdmHZHiXfx6U9FoVXepH3EeVkvxruXl
 Hsxk6/RnnYRTm/hUJUMVKADbr2zE5C7MxdSw8nPuB77LfD32Nlxctz5Z8CXn4Q/tfKn9
 WEDA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20221208; t=1682671699; x=1685263699;
 h=content-transfer-encoding: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=/NZpNDrkeNYDhtyGzOtndO1weOFBADjh0piOJae0kls=;
 b=Og7xZueet/dCTUDpqAlkhp9UQnBgOlxg1DcN6BdaX5O9v9japwSAlEzupfDK2ma2lN
 xHCVLaDqDVVcN3nBWqY2OQ86AQkpIBzXQnsJmUZMlAXleVNI36o4t84ohSNtE6BBp2io
 8BQReLF7VA3dekakI+N6mvOhhl/mNfI8exgHLQ93gbJAPS7kdXDKzcRCtowD5bpHd/Rm
 3nJS8Fy7Sh5pMSPCpVAuR9FpPybrFjXISGouozOD2ARrW+Q0XLY+X0jEsQHjPPo6Q4Fi
 E2YJV+5LkEiU+baL8K0ghlleAZrmaL03jyTPLPw+BIHxakPUfawcpgfOyumnSGgowc2k
 bHiQ==
X-Gm-Message-State: AC+VfDwf+w5g0u6SEnPR8QbK90W7vTUMViZ3Kelw3Zlezx+IRrNnzwWb
 OKWr6Q8oWG2gMwTm5DRv9YDFQJUAxDcENWjqem4=
X-Google-Smtp-Source: ACHHUZ7i6FiE1dyXzBjd0lAvBVXfUOmtCtHICP6EqT61sW+WQzyzBpqvKu469G598W+nPknRFaoeD3R3WuEXiWYwG8g=
X-Received: by 2002:a0d:d44f:0:b0:54f:dafd:a369 with SMTP id
 w76-20020a0dd44f000000b0054fdafda369mr2872810ywd.51.1682671698531; Fri, 28
 Apr 2023 01:48:18 -0700 (PDT)
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>
 <CAGpPWDZkUYW=Qb763TPzUa6yUf217nh0Bo+O9Qyf=WS2pUQUYA@mail.gmail.com>
In-Reply-To: <CAGpPWDZkUYW=Qb763TPzUa6yUf217nh0Bo+O9Qyf=WS2pUQUYA@mail.gmail.com>
From: =?UTF-8?Q?Johan_Tor=C3=A5s_Halseth?= <johanth@gmail.com>
Date: Fri, 28 Apr 2023 10:48:07 +0200
Message-ID: <CAD3i26AXZKDCH3odhCjpMwzOTGQKSFqH9S+5N9UXNTb7CJHONA@mail.gmail.com>
To: Billy Tetrud <billy.tetrud@gmail.com>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Mailman-Approved-At: Sat, 29 Apr 2023 16:19:45 +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: Fri, 28 Apr 2023 08:48:21 -0000

Hi, Salvatore.

I find this proposal very interesting. Especially since you seemingly
can achieve such powerful capabilities by such simple opcodes.

I'm still trying to grok how this would look like on-chain (forget
about the off-chain part for now), if we were to play out such a
computation.

Let's say you have a simple game like "one player tic-tac-toe" with
only two tiles: [ _ | _ ]. The player wins if he can get two in a row
(pretty easy game tbh).

Could you give a complete example how you would encode one such state
transition (going from [ X, _ ] -> [ X, X ] for instance) in Bitcoin
script?

Feel free to choose a different game or program if you prefer :)

Thanks!
Johan



On Tue, Dec 13, 2022 at 2:08=E2=80=AFPM Billy Tetrud via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> Re Verkle trees, that's a very interesting construction that would be sup=
er useful as a tool for something like Utreexo. A potentially substantial d=
ownside is that it seems the cryptography used to get those nice properties=
 of Verkle trees isn't quantum safe. 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 va=
lues, 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 simp=
le enough for Script to verify it.
>>
>> For the academic purpose of proving completeness (that is, any computati=
on can be successfully "proved" by the availability of the corresponding fr=
aud 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 {O=
P_NOT, OP_BOOLAND, OP_BOOLOR, OP_EQUAL}.
>>
>> In practice, you would want to utilize Script to its fullest, so for exa=
mple 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 comm=
itment to an execution trace of `f(x) =3D y`, `x`, and `y`. Bob Disagrees w=
ith `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 t=
o the participant who's "after-value" is computed by the step's operation a=
pplied to the "before value". But if the participants each present valid st=
eps but with different operations, who wins? In other words, Alice could pr=
esent [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 be=
fore the challenge protocol starts, that the execution trace that Alice pos=
ts 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 comp=
utation depends solely on f, not its inputs. In fact, you made me realize t=
hat I could drop op_i from the i-th leaf commitment, and just embed the inf=
ormation in the Script of that corresponding state.
>>
>> Note that the states S0 to S14 of the 256x game are not _all_ the possib=
le states, but only the ones that occurred in that execution of the contrac=
t (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 th=
erefore choosing different branches) would lead to a different leaf, and th=
erefore 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 contra=
ct, 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 c=
an create contracts where even the function ("program", or "contract") is n=
ot decided when the channel is created.
>>
>> Since f is generic, we can choose f itself to be a universal Turing mach=
ine. That is, we can imagine a function f(code, data) that executes a progr=
am ("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 ca=
n enter any contract among themselves (e.g.: start playing a chess game) en=
tirely inside the channel. The state of this universal channel would contai=
n 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 Turin=
g machines is not really complicated), so it might be worth exploring furth=
er to figure out useful applications of this approach (supercharging lightn=
ing?).
>>
>> 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
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev