Re: [bitcoin-dev] Merkleize All The Things

From: "Johan Torås Halseth" <johanth@gmail•com>
To: Billy Tetrud <billy.tetrud@gmail•com>,
	 Bitcoin Protocol Discussion
	<bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Merkleize All The Things
Date: Fri, 28 Apr 2023 10:48:07 +0200	[thread overview]
Message-ID: <CAD3i26AXZKDCH3odhCjpMwzOTGQKSFqH9S+5N9UXNTb7CJHONA@mail.gmail.com> (raw)
In-Reply-To: <CAGpPWDZkUYW=Qb763TPzUa6yUf217nh0Bo+O9Qyf=WS2pUQUYA@mail.gmail.com>

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 PM Billy Tetrud via bitcoin-dev
<bitcoin-dev@lists•linuxfoundation.org> wrote:
>
> 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. 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 = (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 simple enough for Script to verify it.
>>
>> For the academic purpose of proving completeness (that is, any computation can be successfully "proved" by the availability of the corresponding fraud 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 – 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) = 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'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 valid 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'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)?
>>
>>
>> The function f is already hard-coded in the contract itself, by means of the tree of scripts − 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 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 possible 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 UTXO. Different choices made by the parties (by providing different data, and therefore choosing different branches) would lead to a different leaf, and therefore to different (but in a certain sense "symmetric") states.
>>
>> ========
>>
>> 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 can create contracts where even the function ("program", or "contract") is not 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) == 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 open 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 further 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
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev