Re: [bitcoin-dev] Merkleize All The Things

From: Billy Tetrud <billy.tetrud@gmail•com>
To: Salvatore Ingala <salvatore.ingala@gmail•com>,
	 Bitcoin Protocol Discussion
	<bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Merkleize All The Things
Date: Tue, 13 Dec 2022 00:59:27 -0600	[thread overview]
Message-ID: <CAGpPWDZkUYW=Qb763TPzUa6yUf217nh0Bo+O9Qyf=WS2pUQUYA@mail.gmail.com> (raw)
In-Reply-To: <CAMhCMoGabEASO9CGc1hAMpYZn4nWH5D8XFs3eFcSSFAitSFUGA@mail.gmail.com>

[-- Attachment #1: Type: text/plain, Size: 5631 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 6974 bytes --]