From: Salvatore Ingala <salvatore.ingala@gmail•com>
To: Bitcoin Protocol Discussion
<bitcoin-dev@lists•linuxfoundation.org>,
Rijndael <rot13maxi@protonmail•com>
Subject: Re: [bitcoin-dev] Merkleize All The Things
Date: Thu, 1 Dec 2022 09:47:22 +0100 [thread overview]
Message-ID: <CAMhCMoGabEASO9CGc1hAMpYZn4nWH5D8XFs3eFcSSFAitSFUGA@mail.gmail.com> (raw)
In-Reply-To: <7f3674d1-c1ad-9a82-e30f-7cf24d697faf@protonmail.com>
[-- Attachment #1: Type: text/plain, Size: 4652 bytes --]
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
[-- Attachment #2: Type: text/html, Size: 5624 bytes --]
next prev parent reply other threads:[~2022-12-01 8:47 UTC|newest]
Thread overview: 20+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-11-08 9:17 Salvatore Ingala
2022-11-08 12:01 ` ZmnSCPxj
2022-11-10 9:42 ` Salvatore Ingala
2022-11-08 23:34 ` Bram Cohen
2022-11-09 12:07 ` Peter Todd
2022-11-10 7:39 ` David A. Harding
2022-11-11 21:49 ` Antoine Riard
2022-11-12 15:04 ` Salvatore Ingala
2022-11-30 19:42 ` Rijndael
2022-11-30 22:09 ` Rijndael
2022-12-01 8:47 ` Salvatore Ingala [this message]
2022-12-13 6:59 ` Billy Tetrud
2023-04-28 8:48 ` Johan Torås Halseth
2023-05-01 13:11 ` Salvatore Ingala
2023-05-01 21:15 ` Salvatore Ingala
2023-05-04 8:34 ` Johan Torås Halseth
2023-05-05 21:18 ` Salvatore Ingala
2023-05-26 11:45 ` Johan Torås Halseth
2023-05-28 10:24 ` Salvatore Ingala
2023-05-30 7:34 ` Johan Torås Halseth
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAMhCMoGabEASO9CGc1hAMpYZn4nWH5D8XFs3eFcSSFAitSFUGA@mail.gmail.com \
--to=salvatore.ingala@gmail$(echo .)com \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=rot13maxi@protonmail$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox