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
Subject: Re: [bitcoin-dev] Merkleize All The Things
Precedence: list

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