MIME-Version: 1.0
References: <CAMhCMoH9uZPeAE_2tWH6rf0RndqV+ypjbNzazpFwFnLUpPsZ7g@mail.gmail.com>
 <CALZpt+GVe0XTdWqV=LAcOj=nq+k2DEFqc+sKyxAujLDBR7bYbQ@mail.gmail.com>
In-Reply-To: <CALZpt+GVe0XTdWqV=LAcOj=nq+k2DEFqc+sKyxAujLDBR7bYbQ@mail.gmail.com>
From: Salvatore Ingala <salvatore.ingala@gmail.com>
Date: Sat, 12 Nov 2022 16:04:20 +0100
Message-ID: <CAMhCMoEONv3jriBU3qwm0pt75iF_sgra1H2Z4rOF8u+e7hs_cw@mail.gmail.com>
To: Antoine Riard <antoine.riard@gmail.com>
Content-Type: multipart/alternative; boundary="000000000000d2bb2d05ed475239"
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Merkleize All The Things
Precedence: list

--000000000000d2bb2d05ed475239
Content-Type: text/plain; charset="UTF-8"

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

--000000000000d2bb2d05ed475239
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><font face=3D"monospace">Hi Antoine,<br>It appears that my=
 explanation of the relationship between the covenant and the bisection pro=
tocol is still unclear; I&#39;ll do my best to clarify.<br><br>The bisectio=
n&#39;s Merkle tree never ends up on-chain, in any form. Therefore, a bigge=
r 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 resu=
lt 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.=C2=A0<br><br>The actual computation trace (a=
nd the corresponding Merkle tree) is only computed by the parties when they=
 execute the computation.<br>What&#39;s in the tapleaves is only the valid =
transitions at the current state of the protocol; that is, the valid transi=
tions in the Finite State Machine (and possibly other valid exit conditions=
 that remove the=C2=A0covenant encumbrance, if any).<br><br>The bisection p=
rotocol only makes sense as a step in a larger protocol that makes use of i=
t.<br><br>Perhaps presenting the protocol in a less-than-general case might=
 help to understand it. So let&#39;s play a simpler game using a protocol t=
hat includes a fraud proof.<br><br>Alice claims that she knows how to multi=
ply by 256, while Bob doesn&#39;t believe her. So they make a bet: they eac=
h commit 1 coin; then Bob choses a number x; then Alice computes y =3D 256*=
x by doubling x eight times (expensive multiplications were disabled in a t=
ragic DDoS accident), and publishes the result y. Bob independently compute=
s 256 * x (he has a friend who is a mathematician, he&#39;ll know how to do=
 it). If the result is not y, Bob will start a challenge; otherwise, Alice =
wins and takes the money.<br><br>(The example is of course artificial, as r=
edoing the computation in Script is cheaper than executing the fraud proof =
in this case!)<br><br>What follows is an actual execution of the protocol. =
In the following, each [Si] is a UTXO corresponding to some possible FSM no=
de, starting with the S0, the UTXO with 1+1 =3D 2 coins. Each line with &qu=
ot;-&quot; is a possible transition (script in the taptree), specifying wha=
t is the next FSM node after the &quot;=3D=3D&gt;&quot; symbol; the encumbr=
ance in the scripts enforce that the state of the next UTXO is updated corr=
ectly (details omitted below), and any other necessary conditions to ensure=
 the integrity of the protocol.<br><br><br>=3D=3D=3D=3D=3D=C2=A0<br><br><br=
>[S0]: Initial UTXO<br>=C2=A0 - only Bob can spend, he must choose his numb=
er x =3D=3D&gt; S1<br><br>[S1; state: x]:<br>=C2=A0 - only Alice can spend,=
 she publishes her answer y =3D=3D&gt; S2<br><br>[S2. state: x, y]:<br>=C2=
=A0 - after 1 day: Alice won, she can take the money =C2=A0 =C2=A0 // Happy=
 case! Usually that&#39;s the end<br>=C2=A0 - Bob disagrees with the answer=
, post z as his answer. =3D=3D&gt; S3<br><br>The challenge starts here! Let=
&#39;s put some actual numbers. x =3D 2; y =3D 508; z =3D 512.<br><br>This =
is what Alice computed:<br><br>=C2=A0 2 =3D&gt; 4 =3D&gt; 8 =3D&gt; 16 =3D&=
gt; 32 =3D&gt; 64 =3D&gt; 127 =3D&gt; 254 =3D&gt; 508<br><br>This is what B=
ob computed:<br><br>=C2=A0 2 =3D&gt; 4 =3D&gt; 8 =3D&gt; 16 =3D&gt; 32 =3D&=
gt; 64 =3D&gt; 128 =3D&gt; 256 =3D&gt; 512<br><br>At this time, we don&#39;=
t know who is right. They both built a tree that looks like this (ASCII art=
 only working in fixed-width font):<br><br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0___H18___<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 / =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 \<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0/=
 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 \<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 H14 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 H58<br>=C2=A0 =C2=A0 =C2=A0 =C2=
=A0 / \ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 / \<br>=C2=A0 =C2=A0 =C2=
=A0 =C2=A0/ =C2=A0 \ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 / =C2=A0 \<br>=C2=
=A0 =C2=A0 =C2=A0 / =C2=A0 =C2=A0 \ =C2=A0 =C2=A0 =C2=A0 =C2=A0 / =C2=A0 =
=C2=A0 \<br>=C2=A0 =C2=A0 H12 =C2=A0 =C2=A0 H34 =C2=A0 =C2=A0 H56 =C2=A0 =
=C2=A0 H78<br>=C2=A0 =C2=A0 / \ =C2=A0 =C2=A0 / \ =C2=A0 =C2=A0 / \ =C2=A0 =
=C2=A0 / \<br>=C2=A0 H1 =C2=A0H2 =C2=A0H3 =C2=A0H4 =C2=A0H5 =C2=A0H6 =C2=A0=
H7 =C2=A0H8<br><br>Remember that each internal node commits to: the state o=
f 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 j=
ust commits to that intermediate computation step (and the operation, which=
 here is always &quot;double the input&quot;). For example, H4 commits to &=
quot;16 =3D&gt; 32&quot; according to both Alice&#39;s and Bob&#39;s comput=
ation traces.<br><br>(From our privileged point of view, we can foresee tha=
t the earliest disagreement is on the 6th step of the computation: &quot;64=
 =3D&gt; 127&quot; according to Alice, &quot;64 =3D&gt; 128&quot; according=
 to Bob).<br><br>Let&#39;s denote h_{A;18} (resp. h_{B;18}) all the informa=
tion committed to in the node H18, according to Alice (resp. Bob). Similarl=
y for all the other nodes.<br><br>[S3. state: x, y, z]: Challenge starts!<b=
r>=C2=A0 - Alice posts the root of her computation trace h_{A;18} =3D=3D&gt=
; S4<br><br>[S4. state: x, y, z, h_{A;18}]<br>=C2=A0 - Bob posts the root o=
f her computation trace h_{B;18} =3D=3D&gt; S5<br><br>Since they disagree, =
it must be the case that h_{A;18} !=3D h_{B;18}.<br><br>[S5. state: x, y, z=
, h_{A;18}, h_{B;18}]<br>=C2=A0 - Alice opens the commitment h_{A;18}, by r=
evealing H14 and H58 (according to her) =3D=3D&gt; S6<br><br>Note that in t=
his last transition (going to S6), the covenant enforces that the child com=
mitments 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&#39;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 (en=
suring the integrity of the Merkle tree).<br>This is true for all the commi=
tment openings below.<br><br>[S6. state: x, y, z, (h_{A;14}, h_{A;58}), h_{=
B;18}]<br>=C2=A0 - Bob opens the commitment h_{B;18}, by revealing H14 and =
H58 (according to him) =3D=3D&gt; S7<br><br>[S7. state: x, y, z, (h_{A;18},=
 h_{A;14}, h_{A;58}), (h_{B;18}, h_{B;14}, h_{B;58})]<br>=C2=A0 // We now n=
eed to choose a child where there is disagreement.<br>=C2=A0 // If both chi=
ldren don&#39;t match, iterate on the left child.<br>=C2=A0 - Anyone: if h_=
{A;14} =3D=3D h_{B;14} =3D=3D&gt; S8<br>=C2=A0 - Anyone: if h_{A;14} !=3D h=
_{B;14} =3D=3D&gt; Continue challenge on H14 // Non-executed FSM cases omit=
ted for brevity<br><br>At this point, the disagreement over the root is set=
tled: Alice and Bob agree on the first half of the computation, but they di=
sagree over the second half. Therefore, in S8 the protocol continues over H=
58.<br><br>[S8. state: h_{A;58}, h_{B;58}]<br>=C2=A0 // This is analogous t=
o S5, just with half of the computation steps.<br>=C2=A0 - Alice opens the =
commitment h_{A;58}, by revealing H56 and H78 (according to her) =3D=3D&gt;=
 S9<br><br>[S9. state: (h_{A;56}, h_{A;78}), h_{B;58}]<br>=C2=A0 - Bob open=
s the commitment h_{B;58}, by revealing H56 and H78 (according to him) =3D=
=3D&gt; S10<br><br>[S10. state: (h_{A;56}, h_{A;78}), (h_{B;56}, h_{B;78})]=
<br>=C2=A0 // Like S7, iterate on a disagreeing child<br>=C2=A0 - Anyone: i=
f h_{A;56} =3D=3D h_{B;56} =3D=3D&gt; continue challenge on H78 // Non-exec=
uted FSM cases omitted for brevity<br>=C2=A0 - Anyone: if h_{A;56} !=3D h_{=
B;56} =3D=3D&gt; S11<br><br>Getting there! The subtree now commits to just =
two computation steps.<br><br>[S11. state: h_{A;56}, h_{B;56}]<br>=C2=A0 //=
 This is analogous to S5 and S8.<br>=C2=A0 - Alice opens the commitment h_{=
A;56}, by revealing H5 and H6 (according to her) =3D=3D&gt; S12<br><br>[S12=
. state: (h_{A;5}, h_{A;6}), h_{B;56}]<br>=C2=A0 - Bob opens the commitment=
 h_{B;56}, by revealing H5 and H6 (according to him) =3D=3D&gt; S13<br><br>=
[S13. state: (h_{A;5}, h_{A;6}), (h_{B;5}, h_{B;6})]<br>=C2=A0 // Like S7 a=
nd S10, iterate on a disagreeing child<br>=C2=A0 - Anyone: if h_{A;5} =3D=
=3D h_{B;5} =3D=3D&gt; S14<br>=C2=A0 - Anyone: if h_{A;5} !=3D h_{B;5} =3D=
=3D&gt; continue challenge on H5 // Non-executed FSM cases omitted for brev=
ity<br><br>We are now at the crucial stage: the commitment corresponds to a=
 leaf of the computation trace Merkle tree.<br><br>[S14. state: h_{A;6}, h_=
{B;6}]<br>=C2=A0 - Alice can take all the money if she can open h_{A;6} to =
a correct &quot;n =3D&gt; n + n&quot; computation step<br>=C2=A0 - Bob can =
take all the money if he can open h_{B;6} to a correct &quot;n =3D&gt; n + =
n&quot; computation step<br><br>The challenge now ends quickly: Bob&#39;s h=
ash commits to the computation step &quot;64 =3D&gt; 128&quot;.<br>Instead,=
 Alice&#39;s step is the incorrect &quot;64 =3D&gt; 127&quot;.<br><br>It=
9;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.<br>(The bisection protocol c=
an&#39;t do anything useful if both parties provide incorrect data; arguabl=
y, that is not a very interesting scenario!)<br><br>Crucially, the operatio=
n in the single step is so simple that Script can verify it.</font><div><fo=
nt face=3D"monospace"><br></font></div><div><font face=3D"monospace">=3D=3D=
=3D=3D=3D<br><br>If you read until here: thank you, this was the first exec=
ution of a challenge in MATT covenants!<br><br>Of course, there are a few t=
hings missing in the above protocol:<br>- Bonds should be added in order to=
 incentivize cooperation.<br>- The omitted FSM steps (corresponding to bran=
ches of the challenge that were never taken) need to be computed nonetheles=
s when preparing the covenant.<br>- Additional transitions should be added =
at every step (always allow cooperative behavior; forfait after a timeout i=
f it&#39;s the other party&#39;s turn).<br>- Some of those consecutive &quo=
t;forced&quot; steps can be contracted in a single step; I felt this sequen=
ce is more logical to explain the protocol, but implementations would want =
to optimize it.<br><br>Yet, _all_ the code and scripts of the bisection pro=
tocol are independent of the actual execution, and can be precomputed (bott=
om up, starting from the leaves) before the initial covenant is created - t=
herefore, before x, y and z are chosen and committed to.<br><br></font><spa=
n style=3D"font-family:monospace">While here each leaf is doing the same op=
eration (doubling a number), it is well-known that arbitrary computation ca=
n be decomposed=C2=A0in very simple elementary functions (like NAND gates, =
if we want to be minimalistic).</span><font face=3D"monospace"><br><br>I ho=
pe this helps in clarifying the role of the bisection protocol in smart con=
tracts using MATT covenants.</font><br></div><div><font face=3D"monospace">=
<br></font></div><div><font face=3D"monospace">Best,</font></div><div><font=
 face=3D"monospace">Salvatore</font></div></div>

--000000000000d2bb2d05ed475239--