From: Rijndael <rot13maxi@protonmail•com>
To: Bitcoin Protocol Discussion
<bitcoin-dev@lists•linuxfoundation.org>,
Salvatore Ingala <salvatore.ingala@gmail•com>,
Antoine Riard <antoine.riard@gmail•com>
Subject: Re: [bitcoin-dev] Merkleize All The Things
Date: Wed, 30 Nov 2022 22:09:33 +0000 [thread overview]
Message-ID: <7f3674d1-c1ad-9a82-e30f-7cf24d697faf@protonmail.com> (raw)
In-Reply-To: <0f352f70-c93a-614f-e443-67d198ec2c26@protonmail.com>
[-- Attachment #1: Type: text/plain, Size: 11781 bytes --]
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.
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)?
Thanks!
-rijndael
On 11/30/22 2:42 PM, Rijndael via bitcoin-dev wrote:
> Hello Salvatore,
>
> Really interesting idea. The walk-through of the challenge protocol helped.
>
> In the final state:
>
> [S14. state: h_{A;6}, h_{B;6}]
> - Alice can take all the money if she can open h_{A;6} to a correct "n => n + n" computation step
> - Bob can take all the money if he can open h_{B;6} to a correct "n => n + n" computation step
>
> My understanding of your scheme for encoding execution traces is that each leaf is (previous-state, operation, post-state) So in this case when we get to the conflicting step of the execution traces, alice might reveal something like (x=64, x+x, x=127) and bob might reveal something like (x=64, x+x, x=128). So in order for the covenant to enforce which state-transition is valid (who can spend the money), that means that `x+x` needs to be evaluated in script to tell who has posted the incorrect state. Am I understanding this final step of the bisection protocol correctly?
>
> -rijndael
>
> On 11/12/22 10:04 AM, Salvatore Ingala via bitcoin-dev wrote:
>
>> Hi Antoine,
>> It appears that my explanation of the relationship between the covenant and the bisection protocol is still unclear; I'll do my best to clarify.
>>
>> The bisection's Merkle tree never ends up on-chain, in any form. Therefore, a bigger computation does not end up in a bigger witness size, which is key to the scalability of the approach. Only in the case of a challenge, it will result in a (logarithmically) longer chain of transactions to resolve it. This chain of transactions could be mapped to a root-to-leaf path in the Merkle tree of the computation trace.
>>
>> The actual computation trace (and the corresponding Merkle tree) is only computed by the parties when they execute the computation.
>> What's in the tapleaves is only the valid transitions at the current state of the protocol; that is, the valid transitions in the Finite State Machine (and possibly other valid exit conditions that remove the covenant encumbrance, if any).
>>
>> The bisection protocol only makes sense as a step in a larger protocol that makes use of it.
>>
>> Perhaps presenting the protocol in a less-than-general case might help to understand it. So let's play a simpler game using a protocol that includes a fraud proof.
>>
>> Alice claims that she knows how to multiply by 256, while Bob doesn't believe her. So they make a bet: they each commit 1 coin; then Bob choses a number x; then Alice computes y = 256*x by doubling x eight times (expensive multiplications were disabled in a tragic DDoS accident), and publishes the result y. Bob independently computes 256 * x (he has a friend who is a mathematician, he'll know how to do it). If the result is not y, Bob will start a challenge; otherwise, Alice wins and takes the money.
>>
>> (The example is of course artificial, as redoing the computation in Script is cheaper than executing the fraud proof in this case!)
>>
>> What follows is an actual execution of the protocol. In the following, each [Si] is a UTXO corresponding to some possible FSM node, starting with the S0, the UTXO with 1+1 = 2 coins. Each line with "-" is a possible transition (script in the taptree), specifying what is the next FSM node after the "==>" symbol; the encumbrance in the scripts enforce that the state of the next UTXO is updated correctly (details omitted below), and any other necessary conditions to ensure the integrity of the protocol.
>>
>> =====
>>
>> [S0]: Initial UTXO
>> - only Bob can spend, he must choose his number x ==> S1
>>
>> [S1; state: x]:
>> - only Alice can spend, she publishes her answer y ==> S2
>>
>> [S2. state: x, y]:
>> - after 1 day: Alice won, she can take the money // Happy case! Usually that's the end
>> - Bob disagrees with the answer, post z as his answer. ==> S3
>>
>> The challenge starts here! Let's put some actual numbers. x = 2; y = 508; z = 512.
>>
>> This is what Alice computed:
>>
>> 2 => 4 => 8 => 16 => 32 => 64 => 127 => 254 => 508
>>
>> This is what Bob computed:
>>
>> 2 => 4 => 8 => 16 => 32 => 64 => 128 => 256 => 512
>>
>> At this time, we don't know who is right. They both built a tree that looks like this (ASCII art only working in fixed-width font):
>>
>> ___H18___
>> / \
>> / \
>> H14 H58
>> / \ / \
>> / \ / \
>> / \ / \
>> H12 H34 H56 H78
>> / \ / \ / \ / \
>> H1 H2 H3 H4 H5 H6 H7 H8
>>
>> Remember that each internal node commits to: the state of the computation before the leftmost leaf in the subtree, the state after the rightmost leaf, and the hash of sub-trace for the sub-tree. Each leaf just commits to that intermediate computation step (and the operation, which here is always "double the input"). For example, H4 commits to "16 => 32" according to both Alice's and Bob's computation traces.
>>
>> (From our privileged point of view, we can foresee that the earliest disagreement is on the 6th step of the computation: "64 => 127" according to Alice, "64 => 128" according to Bob).
>>
>> Let's denote h_{A;18} (resp. h_{B;18}) all the information committed to in the node H18, according to Alice (resp. Bob). Similarly for all the other nodes.
>>
>> [S3. state: x, y, z]: Challenge starts!
>> - Alice posts the root of her computation trace h_{A;18} ==> S4
>>
>> [S4. state: x, y, z, h_{A;18}]
>> - Bob posts the root of her computation trace h_{B;18} ==> S5
>>
>> Since they disagree, it must be the case that h_{A;18} != h_{B;18}.
>>
>> [S5. state: x, y, z, h_{A;18}, h_{B;18}]
>> - Alice opens the commitment h_{A;18}, by revealing H14 and H58 (according to her) ==> S6
>>
>> Note that in this last transition (going to S6), the covenant enforces that the child commitments are compatible: the transition is only valid if the starting state of the computation according to h_{A;14} is compatible with h_{A;18} (that is, it's equal to x); similarly the end state of the computation in h_{A;58} must be y, and h_{A;18} can be recomputed from the data provided (ensuring the integrity of the Merkle tree).
>> This is true for all the commitment openings below.
>>
>> [S6. state: x, y, z, (h_{A;14}, h_{A;58}), h_{B;18}]
>> - Bob opens the commitment h_{B;18}, by revealing H14 and H58 (according to him) ==> S7
>>
>> [S7. state: x, y, z, (h_{A;18}, h_{A;14}, h_{A;58}), (h_{B;18}, h_{B;14}, h_{B;58})]
>> // We now need to choose a child where there is disagreement.
>> // If both children don't match, iterate on the left child.
>> - Anyone: if h_{A;14} == h_{B;14} ==> S8
>> - Anyone: if h_{A;14} != h_{B;14} ==> Continue challenge on H14 // Non-executed FSM cases omitted for brevity
>>
>> At this point, the disagreement over the root is settled: Alice and Bob agree on the first half of the computation, but they disagree over the second half. Therefore, in S8 the protocol continues over H58.
>>
>> [S8. state: h_{A;58}, h_{B;58}]
>> // This is analogous to S5, just with half of the computation steps.
>> - Alice opens the commitment h_{A;58}, by revealing H56 and H78 (according to her) ==> S9
>>
>> [S9. state: (h_{A;56}, h_{A;78}), h_{B;58}]
>> - Bob opens the commitment h_{B;58}, by revealing H56 and H78 (according to him) ==> S10
>>
>> [S10. state: (h_{A;56}, h_{A;78}), (h_{B;56}, h_{B;78})]
>> // Like S7, iterate on a disagreeing child
>> - Anyone: if h_{A;56} == h_{B;56} ==> continue challenge on H78 // Non-executed FSM cases omitted for brevity
>> - Anyone: if h_{A;56} != h_{B;56} ==> S11
>>
>> Getting there! The subtree now commits to just two computation steps.
>>
>> [S11. state: h_{A;56}, h_{B;56}]
>> // This is analogous to S5 and S8.
>> - Alice opens the commitment h_{A;56}, by revealing H5 and H6 (according to her) ==> S12
>>
>> [S12. state: (h_{A;5}, h_{A;6}), h_{B;56}]
>> - Bob opens the commitment h_{B;56}, by revealing H5 and H6 (according to him) ==> S13
>>
>> [S13. state: (h_{A;5}, h_{A;6}), (h_{B;5}, h_{B;6})]
>> // Like S7 and S10, iterate on a disagreeing child
>> - Anyone: if h_{A;5} == h_{B;5} ==> S14
>> - Anyone: if h_{A;5} != h_{B;5} ==> continue challenge on H5 // Non-executed FSM cases omitted for brevity
>>
>> We are now at the crucial stage: the commitment corresponds to a leaf of the computation trace Merkle tree.
>>
>> [S14. state: h_{A;6}, h_{B;6}]
>> - Alice can take all the money if she can open h_{A;6} to a correct "n => n + n" computation step
>> - Bob can take all the money if he can open h_{B;6} to a correct "n => n + n" computation step
>>
>> The challenge now ends quickly: Bob's hash commits to the computation step "64 => 128".
>> Instead, Alice's step is the incorrect "64 => 127".
>>
>> It's not difficult to convince oneself that, as long as the hash function is collision-free and the computation is deterministic, only the honest party can provide correct data for this final step.
>> (The bisection protocol can't do anything useful if both parties provide incorrect data; arguably, that is not a very interesting scenario!)
>>
>> Crucially, the operation in the single step is so simple that Script can verify it.
>>
>> =====
>>
>> If you read until here: thank you, this was the first execution of a challenge in MATT covenants!
>>
>> Of course, there are a few things missing in the above protocol:
>> - Bonds should be added in order to incentivize cooperation.
>> - The omitted FSM steps (corresponding to branches of the challenge that were never taken) need to be computed nonetheless when preparing the covenant.
>> - Additional transitions should be added at every step (always allow cooperative behavior; forfait after a timeout if it's the other party's turn).
>> - Some of those consecutive "forced" steps can be contracted in a single step; I felt this sequence is more logical to explain the protocol, but implementations would want to optimize it.
>>
>> Yet, _all_ the code and scripts of the bisection protocol are independent of the actual execution, and can be precomputed (bottom up, starting from the leaves) before the initial covenant is created - therefore, before x, y and z are chosen and committed to.
>>
>> While here each leaf is doing the same operation (doubling a number), it is well-known that arbitrary computation can be decomposed in very simple elementary functions (like NAND gates, if we want to be minimalistic).
>>
>> I hope this helps in clarifying the role of the bisection protocol in smart contracts using MATT covenants.
>>
>> Best,
>> Salvatore
[-- Attachment #2: Type: text/html, Size: 17806 bytes --]
next prev parent reply other threads:[~2022-11-30 22:09 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 [this message]
2022-12-01 8:47 ` Salvatore Ingala
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=7f3674d1-c1ad-9a82-e30f-7cf24d697faf@protonmail.com \
--to=rot13maxi@protonmail$(echo .)com \
--cc=antoine.riard@gmail$(echo .)com \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=salvatore.ingala@gmail$(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