Re: [bitcoin-dev] Merkleize All The Things
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
Re: [bitcoin-dev] Merkleize All The Things
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.
Re: [bitcoin-dev] Ephemeral Anchors: Fixing V3 Package RBF againstpackage limit pinning
Small update. A bit ago I went ahead and implemented ephemeral anchors on top of the V3 proposal to see what the complexity looks like: https://github.com/bitcoin/bitcoin/pull/26403 Roughly 130 loc excluding tests, using OP_2 instead of OP_TRUE to not camp the value that is used elsewhere. Please let me know if you have any early feedback on this! Greg On Thu, Oct 20, 2022 at 9:42 AM Greg Sanders wrote: > So it doesn't look like I'm ignoring a good question: > > No solid noninteractive ideas, unless we get some very flexible sighash > softfork. Interactively, I think you can get collaborative fee bumps under > the current consensus regime and ephemeral anchors. The child will just be > built with inputs from different people. > > On Wed, Oct 19, 2022 at 11:12 AM James O'Beirne > wrote: > >> I'm also very happy to see this proposal, since it gets us closer to >> having a mechanism that allows the contribution to feerate in an >> "unauthenticated" way, which seems to be a very helpful feature for vaults >> and other contracting protocols. >> >> One possible advantage of the sponsors interface -- and I'm curious for >> your input here Greg -- is that with sponsors, assuming we relaxed the "one >> sponsor per sponsoree" constraint, multiple uncoordinated parties can >> collaboratively bump a tx's feerate. A simple example would be a batch >> withdrawal from an exchange could be created with a low feerate, and then >> multiple users with a vested interest of expedited confirmation could all >> "chip in" to raise the feerate with multiple sponsor transactions. >> >> Having a single ephemeral output seems to create a situation where a >> single UTXO has to shoulder the burden of CPFPing a package. Is there some >> way we could (possibly later) amend the ephemeral anchor interface to allow >> for this kind of collaborative sponsoring? Could you maybe see "chained" >> ephemeral anchors that would allow this? >> >> >> On Tue, Oct 18, 2022 at 12:52 PM Jeremy Rubin via bitcoin-dev < >> bitcoin-dev@lists.linuxfoundation.org> wrote: >> >>> Excellent proposal and I agree it does capture much of the spirit of >>> sponsors w.r.t. how they might be used for V3 protocols. >>> >>> The only drawbacks I see is they don't work for lower tx version >>> contracts, so there's still something to be desired there, and that the >>> requirement to sweep the output must be incentive compatible for the miner, >>> or else they won't enforce it (pass the buck onto the future bitcoiners). >>> The Ephemeral UTXO concept can be a consensus rule (see >>> https://rubin.io/public/pdfs/multi-txn-contracts.pdf "Intermediate >>> UTXO") we add later on in lieu of managing them by incentive, so maybe it's >>> a cleanup one can punt. >>> >>> One question I have is if V3 is designed for lightning, and this is >>> designed for lightning, is there any sense in requiring these outputs for >>> v3? That might help with e.g. anonymity set, as well as potentially keep >>> the v3 surface smaller. >>> >>> On Tue, Oct 18, 2022 at 11:51 AM Greg Sanders via bitcoin-dev < >>> bitcoin-dev@lists.linuxfoundation.org> wrote: >>> > does that effectively mark output B as unspendable once the child gets confirmed? Not at all. It's a normal spend like before, since the parent has been confirmed. It's completely unrestricted, not being bound to any V3/ephemeral anchor restrictions on size, version, etc. On Tue, Oct 18, 2022 at 11:47 AM Arik Sosman via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > Hi Greg, > > Thank you very much for sharing your proposal! > > I think there's one thing about the second part of your proposal that > I'm missing. Specifically, assuming the scenario of a v3 transaction with > three outputs, A, B, and the ephemeral anchor OP_TRUE. If a child > transaction spends A and OP_TRUE, does that effectively mark output B as > unspendable once the child gets confirmed? If so, isn't the implication > therefore that to safely spend a transaction with an ephemeral anchor, all > outputs must be spent? Thanks! > > Best, > Arik > > On Tue, Oct 18, 2022, at 6:52 AM, Greg Sanders via bitcoin-dev wrote: > > Hello Everyone, > > Following up on the "V3 Transaction" discussion here > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-September/020937.html > , I would like to elaborate a bit further on some potential follow-on work > that would make pinning severely constrained in many setups]. > > V3 transactions may solve bip125 rule#3 and rule#5 pinning attacks > under some constraints[0]. This means that when a replacement is to be > made > and propagated, it costs the expected amount of fees to do so. This is a > great start. What's left in this subset of pinning is *package limit* > pinning. In other words, a fee-paying transaction cannot enter the mempool
