Re: [bitcoin-dev] Solving CoinPool high-interactivity issue with cut-through update of Taproot leaves
Hi, Antoine. It sounds like perhaps OP_CHECKCONTRACTVERIFY can achieve what you are looking for: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-May/021719.html By committing the participants' pubkeys and balances in the dynamic data instead of the taptree one can imagine a subset of online users agreeing to pool their aggregated balances in a new output, while the offline users' funds would remain inaccessible by them in a second output. The way this would work is by spending the coinpool utxo with a transaction having two outputs: one output that is the "remainder" of the previous coinpool (the offline users), and the second output the new coinpool among the online users*. When the offline users are back online, they could all agree to continue using the original coinpool utxo. * assuming Eltoo in case an offline user comes back online and double spends the UTXO. - Johan On Wed, Sep 27, 2023 at 12:08 PM Antoine Riard via bitcoin-dev wrote: > > Hi Zeeman, > > See my comments at the time of OP_EVICT original publication. > > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-February/019939.html > > "I think in the context of (off-chain) payment pool, OP_EVICT requires > participant cooperation *after* the state update to allow a single > participant to withdraw her funds. > > I believe this is unsafe if we retain as an off-chain construction security > requirement that a participant should have the unilateral means to enforce > the latest agreed upon state at any time during the construction lifetime". > > I think this level of covenant flexibility is still wished for CoinPool as a > fundamental property, and this is offered by TLUV or MERKLESUB. > On the other hand, I think OP_EVICT introduces this idea of *subgroup > novation* (i.e `K-of-N`) of a PT2R scriptpubkey. > > To the best of my understanding, I think there is not yet any sound covenant > proposal aiming to combine TLUV and EVICT-like semantics in a consistent set > of Script primitives to enable "cut-through" updates, while still retaining > the key property of unilateral withdraw of promised balances in any-order. > > I might go to work on crafting one, though for now I'm still interested to > understand better if on-chain "cut-through" is the best direction to solve > the fundamental high interactivity issue of channel factory and payment pool > over punishment-based ideas. > > Best, > Antoine > > Le mar. 26 sept. 2023 à 07:51, ZmnSCPxj a écrit : >> >> Good morning Antoine, >> >> Does `OP_EVICT` not fit? >> >> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-February/019926.html >> >> Regards, >> ZmnSCPxj >> >> >> Sent with Proton Mail secure email. >> >> --- Original Message --- >> On Monday, September 25th, 2023 at 6:18 PM, Antoine Riard via bitcoin-dev >> wrote: >> >> >> > Payment pools and channel factories are afflicted by severe interactivity >> > constraints worsening with the number of users owning an off-chain balance >> > in the construction. The security of user funds is paramount on the >> > ability to withdraw unilaterally from the off-chain construction. As such >> > any update applied to the off-chain balances requires a signature >> > contribution from the unanimity of the construction users to ensure this >> > ability is conserved along updates. >> > As soon as one user starts to be offline or irresponsive, the updates of >> > the off-chain balances must have to be halted and payments progress are >> > limited among subsets of 2 users sharing a channel. Different people have >> > proposed solutions to this issue: introducing a coordinator, partitioning >> > or layering balances in off-chain users subsets. I think all those >> > solutions have circled around a novel issue introduced, namely >> > equivocation of off-chain balances at the harm of construction >> > counterparties [0]. >> > >> > As ZmnSCPxj pointed out recently, one way to mitigate this equivocation >> > consists in punishing the cheating pre-nominated coordinator on an >> > external fidelity bond. One can even imagine more trust-mimized and >> > decentralized fraud proofs to implement this mitigation, removing the need >> > of a coordinator [1]. >> > >> > However, I believe punishment equivocation to be game-theory sound should >> > compensate a defrauded counterparty of the integrity of its lost off-chain >> > balance. As one cheating counterparty can equivocate in the worst-case >> > against all the other counterparties in the construction, one fidelity >> > bond should be equal to ( C - 1 ) * B satoshi amount, where C is the >> > number of construction counterparty and B the initial off-chain balance of >> > the cheating counterparty. >> > >> > Moreover, I guess it is impossible to know ahead of a partition or >> > transition who will be the "honest" counterparties from the "dishonest" >> > ones, therefore this ( C - 1 ) * B-sized fidelity bond must be maintained >> > by
Re: [bitcoin-dev] MATT: [demo] Optimistic execution of arbitrary programs
Hi, aj. Thanks for taking a look!
> "O(n log n)" sounds wrong? Isn't it O(P + log(N)) where P is the size
> of the program, and N is the number of steps (rounded up to a power of 2)?
Thanks, you are right. That's a typo, it should indeed be O(log n). n
being the number of steps in the program. I think P doesn't matter
here, as we never put the whole program on-chain, just break it down
into n steps.
> > node = h( start_pc|start_i|start_x|end_pc|end_i|end_x|h(
> > h(sub_node1)|h(sub_node2) )
> But I don't think that works -- I think you want to know h(sub_node1)
> and h(sub_node2) directly, so that you can compare them to the results
> you get if you run the computation, and choose the one that's incorrect.
This denotes only how to create the commitment. When we traverse the
tree, the node scripts enforce that h(sub_n
ode{1,2}) that is consistent with the commitment is in the witness,
achieving exactly what you suggest.
> I'm not seeing what forces the prover to come up with a balanced state
> tree
To achieve this the participants agree up front (when the contract is
created) what is the exact length of the trace (or equivalent the
depth of the tree). If the actual execution is shorter, we fill the
rest with no-ops.
This means that we know the moment the challenge protocol starts the
transactions that are going to be played (kinda like a CTV tree), so
if one of the participants creates a trace from a non-balanced state
tree, it will be rejected by the script at that level. It is indeed
important that the state tree is built in a deterministic way.
> There seems to be an error in the "what this would look like for 4 state
> transitions" diagram -- the second node should read "0|0|2 -> 0|1|4"
Yes, fixed! Thanks :)
- Johan
On Mon, Oct 2, 2023 at 5:10 PM Anthony Towns wrote:
>
> On Fri, Sep 29, 2023 at 03:14:25PM +0200, Johan Torås Halseth via bitcoin-dev
> wrote:
> > TLDR; Using the proposed opcode OP_CHECKCONTRACTVERIFY and OP_CAT, we
> > show to trace execution of the program `multiply` [1] and challenge
> > this computation in O(n logn) on-chain transactions:
>
> "O(n log n)" sounds wrong? Isn't it O(P + log(N)) where P is the size
> of the program, and N is the number of steps (rounded up to a power of 2)?
>
> You say:
>
> > node = h( start_pc|start_i|start_x|end_pc|end_i|end_x|h(
> > h(sub_node1)|h(sub_node2) )
>
> But I don't think that works -- I think you want to know h(sub_node1)
> and h(sub_node2) directly, so that you can compare them to the results
> you get if you run the computation, and choose the one that's incorrect.
> Otherwise you've got a 50/50 chance of choosing the subnode that's
> actually correct, and you'll only be able to prove a mistake with
> 1/2**N odds?
>
> Not a big change, it just becomes 32B longer (and drops some h()s):
>
> node = start_pc|start_i|start_x|end_pc|end_i|end_x|h(sub_node1)|h(sub_node2)
> leaf = start_pc|start_i|start_x|end_pc|end_i|end_x|null
>
> I'm not seeing what forces the prover to come up with a balanced state
> tree -- if they don't have to have a balanced tree, then I think there
> are many possible trees for the same execution trace, and again it would
> become easy to hide an error somewhere the challenger can't find. Adding a
> "start_stepcount" and "end_stepcount" would probably remedy that?
>
> There seems to be an error in the "what this would look like for 4 state
> transitions" diagram -- the second node should read "0|0|2 -> 0|1|4"
> (combining its two children), not "0|0|2 -> 1|0|2" matching its left
> child.
>
> I'm presuming that the counterparty verifies they know the program (ie,
> all the leaves in the contract taptree) before agreeing to the contract
> in the first place. I think that's fine.
>
> Cheers,
> aj
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
