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 <rot13m...@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
_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
