📅 Original date posted:2023-04-28
🗒️ Summary of this message: A person is interested in a proposal for powerful capabilities using simple opcodes. They ask for an example of encoding a state transition in Bitcoin script for a simple game.
📝 Original message: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 at 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 at lists.linuxfoundation.org> wrote:
>>
>> Hello Rijndael,
>>
>>
>>
>> On Wed, 30 Nov 2022 at 23:09, Rijndael <rot13maxi at 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 at lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Johan Torås Halseth [ARCHIVE] /
npub1pp…hs2fw
2023-06-07 23:20:59
in reply to nevent1q…cjva
Author Public Key
npub1ppn2nhlfdzkw9gw0ytljpef5dpyzsxzw8ffcyykamt32hw6pge0smhs2fwPublished at
2023-06-07 23:20:59Event JSON
{
"id": "9b94869d358b62b8c03a1411a9f04542b3c98546c1f2dd91e4eb44e6af90ebc8",
"pubkey": "0866a9dfe968ace2a1cf22ff20e534684828184e3a538212dddae2abbb41465f",
"created_at": 1686180059,
"kind": 1,
"tags": [
[
"e",
"7f0059a6e0d28ef82dec3f0673b5c245f721dee2278676b8664391d857918bd8",
"",
"reply"
],
[
"p",
"a23dbf6c6cc83e14cc3df4e56cc71845f611908084cfe620e83e40c06ccdd3d0"
]
],
"content": "📅 Original date posted:2023-04-28\n🗒️ Summary of this message: A person is interested in a proposal for powerful capabilities using simple opcodes. They ask for an example of encoding a state transition in Bitcoin script for a simple game.\n📝 Original message:Hi, Salvatore.\n\nI find this proposal very interesting. Especially since you seemingly\ncan achieve such powerful capabilities by such simple opcodes.\n\nI'm still trying to grok how this would look like on-chain (forget\nabout the off-chain part for now), if we were to play out such a\ncomputation.\n\nLet's say you have a simple game like \"one player tic-tac-toe\" with\nonly two tiles: [ _ | _ ]. The player wins if he can get two in a row\n(pretty easy game tbh).\n\nCould you give a complete example how you would encode one such state\ntransition (going from [ X, _ ] -\u003e [ X, X ] for instance) in Bitcoin\nscript?\n\nFeel free to choose a different game or program if you prefer :)\n\nThanks!\nJohan\n\n\n\nOn Tue, Dec 13, 2022 at 2:08 PM Billy Tetrud via bitcoin-dev\n\u003cbitcoin-dev at lists.linuxfoundation.org\u003e wrote:\n\u003e\n\u003e 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.\n\u003e\n\u003e On Thu, Dec 1, 2022 at 5:52 AM Salvatore Ingala via bitcoin-dev \u003cbitcoin-dev at lists.linuxfoundation.org\u003e wrote:\n\u003e\u003e\n\u003e\u003e Hello Rijndael,\n\u003e\u003e\n\u003e\u003e\n\u003e\u003e\n\u003e\u003e On Wed, 30 Nov 2022 at 23:09, Rijndael \u003crot13maxi at protonmail.com\u003e wrote:\n\u003e\u003e\u003e\n\u003e\u003e\u003e Hello Salvatore,\n\u003e\u003e\u003e\n\u003e\u003e\u003e I found my answer re-reading your original post:\n\u003e\u003e\u003e \u003e 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.\n\u003e\u003e\n\u003e\u003e You are correct, the computation step encoded in a leaf needs to be simple enough for Script to verify it.\n\u003e\u003e\n\u003e\u003e 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}.\n\u003e\u003e\n\u003e\u003e 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.\n\u003e\u003e\n\u003e\u003e\u003e\n\u003e\u003e\u003e 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)?\n\u003e\u003e\n\u003e\u003e\n\u003e\u003e 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.\n\u003e\u003e\n\u003e\u003e 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.\n\u003e\u003e\n\u003e\u003e ========\n\u003e\u003e\n\u003e\u003e 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.\n\u003e\u003e 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.\n\u003e\u003e\n\u003e\u003e 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.\n\u003e\u003e Since we can do fraud proofs on statements \"f(code, data) == output\", we could build contracts where the \"code\" itself is chosen later.\n\u003e\u003e\n\u003e\u003e 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.\n\u003e\u003e\n\u003e\u003e 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?).\n\u003e\u003e\n\u003e\u003e We should probably start by implementing testnet rock-paper-scissors in MATT, though :)\n\u003e\u003e\n\u003e\u003e Best,\n\u003e\u003e Salvatore Ingala\n\u003e\u003e _______________________________________________\n\u003e\u003e bitcoin-dev mailing list\n\u003e\u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e\u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev\n\u003e\n\u003e _______________________________________________\n\u003e bitcoin-dev mailing list\n\u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev",
"sig": "f4e3115ec947c8ac09a1c73a06e9ea3233ddcfb5986eec07d9b26f51ebfe3df1a4abcd997861897966ff6f91ae41c563c74ebe46224798e80d602a7ea29af74a"
}