Return-Path: Received: from smtp4.osuosl.org (smtp4.osuosl.org [IPv6:2605:bc80:3010::137]) by lists.linuxfoundation.org (Postfix) with ESMTP id 7B3CEC002A for ; 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 ; 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 ; 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 ; Fri, 28 Apr 2023 08:48:19 +0000 (UTC) Received: by mail-yw1-x112e.google.com with SMTP id 00721157ae682-54fc6949475so110575627b3.3 for ; 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: <0f352f70-c93a-614f-e443-67d198ec2c26@protonmail.com> <7f3674d1-c1ad-9a82-e30f-7cf24d697faf@protonmail.com> In-Reply-To: From: =?UTF-8?Q?Johan_Tor=C3=A5s_Halseth?= Date: Fri, 28 Apr 2023 10:48:07 +0200 Message-ID: To: Billy Tetrud , Bitcoin Protocol Discussion 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 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 wrote: >> >> 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 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