Rijndael [ARCHIVE] / is on Nostr

⚠️ This account is not associated with a real person. It's an archival account for mailing list messages.
🗓️ Active from 2022-11-26 to 2023-02-02
💬 Posted a total of 6 messages
📚 Participated in the following categories: bitcoin-dev
🔇 Please do not DM this user as it's used for archive purposes only.

Last Notes

2023-06-07 23:19:09

- reply

📅 Original date posted:2023-02-02
🗒️ Summary of this message: The RBG Protocol Project and Taro use "single use seals" for tracking assets anchored to Bitcoin, with the actual application data off-chain, making it cheaper and more scalable. The proposed BIP for non-fungible tokens doesn't document any method for associating data or a right with an ordinal, but inscriptions can be moved entirely off-chain.
📝 Original message:Hi AJ and List,
This reminds me of a series of blog posts Peter Todd wrote a few years
ago about using "single use seals" for tracking (fungible) assets
anchored to Bitcoin[0]. I believe that the RBG Protocol Project and Taro
are both using the same underlying principle.
Having the actual application data offchain, but with a commitment to a
UTXO and then using Bitcoin only as a proof-of-publication system to
prevent double-spends seems like a really good idea. As you point out,
in addition to being cheaper and more scalable, it means that not
everyone on the network has to know that there's an asset involved. It
just looks like plain old bitcoin transfers.
A lot of people have written about or are (I think) working on
implementations of this idea. I really like your suggestion of using
nostr. Clients can keep the asset metadata chains locally in their
client and (re)broadcast them to application-specific nostr relays, or
to general public relays depending on application needs. Maybe there's a
marketplace application that has its own relays and also broadcasts
asset metadata to relays used by popular gallery systems. Or maybe your
client just sends to any relay it sees that doesnt have the event. Big
design space there.
- rijndael
0: https://petertodd.org/2017/scalable-single-use-seal-asset-transfer
On 2/2/23 4:15 AM, Anthony Towns via bitcoin-dev wrote:
> Hi *,
>
> Casey Rodarmor's ordinals use the technique of tracking the identity of
> individual satoshis throughout their lifetime:
>
> On Tue, Feb 22, 2022 at 04:43:52PM -0800, Casey Rodarmor via bitcoin-dev wrote:
>> Briefly, newly mined satoshis are sequentially numbered in the order in
>> which they are mined. These numbers are called "ordinal numbers" or
>> "ordinals". When satoshis are spent in a transaction, the input satoshi
>> ordinal numbers are assigned to output satoshis using a simple
>> first-in-first-out algorithm.
> This is proposed as a BIP at https://github.com/bitcoin/bips/pull/1408
>
> When accompanied by a standard for associating some data or right with
> such an identity, this allows the creation of non-fungible tokens (or
> semi-fungible tokens) whose ownership can be transferred by a bitcoin
> transaction.
>
> The proposed BIP doesn't document any method for associating data or a
> right with an ordinal, but the "ord" tool defines "inscriptions" to fill
> this gap [0], providing a way of including mime-encoded data in a taproot
> witness. To make such an inscription, two transactions are required:
> one paying some sats to a special scriptPubKey that commits to the
> inscribed data, and a second that spends those sats to the owner of the
> newly inscribed ordinal, and in so doing revealing the full inscription.
>
> [0] https://docs.ordinals.com/inscriptions.html
>
> I think, however, that you can move inscriptions entirely off-chain. I
> wrote a little on this idea on twitter already [1], but after a bit more
> thought, I think pushing things even further off-chain would be plausible.
>
> [1] https://twitter.com/ajtowns/status/1619554871166013441
>
> In particular, rather than looking at it as being the owner of the sats
> that inscribes some content on those sats (analogously to signing a $100
> bill [2]), you could look at it as saying "the owner of this thing is
> whoever owns this particular sat" (eg instead of "whoever owns this
> share certificate is a shareholder", it's "whoever owns the $1 bill with
> serial number X is a shareholder").
>
> [2] https://www.espn.com/nfl/story/_/id/14375536/owner-100-bill-autograph-cleveland-browns-qb-johnny-manziel-getting-offers
>
> Implementing that is fairly straightforward: you just need a protocol
> for creating an asset offchain and associating it with an ordinal --
> nothing needs to happen on-chain at all. That is, you can do something
> as simple as posting a single nostr message:
>
> {
> "pubkey": <creator's pubkey>
> "kind": 0,
> "tags": [
> ["ord", "txid:vout:sat"]
> ],
> "content": [jpeg goes here],
> "id": <hash of the above>
> "sig": <signature of id by creator's pubkey>
> }
>
> You can prove current ownership of the message by showing a custody
> chain, that is the transaction specified by "txid" in the "ord" tag,
> then every transaction that spent the given sat, until you get to one
> that's still in the utxo set [3]. You don't need to provide witness
> data or validate any of these tx's signatures, as that is already
> implicit in that you end up at a tx in the utxo set. Just calculating
> the txids and comparing against the output containing the sat you're
> interested in is sufficient.
>
> [3] If the satoshi was lost to fees at some point, you could continue to
> follow ownership by including an entire block in the custody chain.
> But seems better to just consider it as "abandoned" or "lost to the
> public domain" at that point.
>
> This approach allows all the "inscription" data to be entirely off-chain,
> the only thing that requires a transaction on-chain is transferring
> ownership to someone else. That allows the NFT's existance can be kept
> entirely private if desired; it also makes it cheap to create a new NFT
> (you don't need to pay any on-chain fees at all); and it doesn't impose
> an outsized overhead on people who aren't interested in your inscriptions,
> but may be interested either in bitcoin per se, or in other inscriptions.
>
> For things that have real intrinsic value -- equity rights in a company,
> bragging rights for supporting an artist, etc -- this seems like it's
> probably a viable approach: owners can "self-custody" all the information
> about the things they own without having to rely on third parties,
> transfers are no more censorable than any other bitcoin transaction
> (especially if the association of the NFT with some particular sat is
> not widely known), etc.
>
> The "inscription" approach might still be desirable for broadcasting
> information that might otherwise be subject to heavy censorship; presuming
> that the censoring entity isn't also willing and able to censor bitcoin
> itself. It's not clear that there's any "rights" to be owned for such a
> case -- you can't buy the right to be the person that first published
> it, and the point of widely broadcasting the information is so it's
> not a secret only known to a few anymore. Also, claiming ownership of
> such information would presumably make you a target for the censor,
> even if just as an example for others. So I'm dubious of the value of
> associating an inscription with an ordinal for that use case.
>
> It's also possible that the perceived value of the NFT isn't due to
> the inscription, but rather due to the scarcity of the blockspace it
> was inscribed in (eg [4]). This is different from Bitcoin's scarcity
> -- by 2100 or so there'll be a total of 2100T satoshis available,
> but in that same time there will only have been about 4T vbytes of
> blockspace available, and perhaps it could make sense to value spent
> vbytes proportionally, so 4 spent vbytes is worth 2100 sats. In that
> case if you spent 50kvb inscribing a jpeg, perhaps the "rights" to that
> jpeg should be worth the same as 50k/4*2100 sats or 0.26 BTC. Doesn't
> seem like a sound argument to me -- there's always more blockspace being
> created, by fewer and fewer sats being created, and ordinals are far more
> awkward to deal with, but I suppose it's still conceivable, and people
> at least claim to believe it. If it were true, this argument suggests
> the price for blockspace today should be around 2488sat/vB (19.28MBTC /
> 774700 MvB), rather than 1sat/vB.
>
> [4] https://twitter.com/vnprc/status/1619876888687820801
>
> Anyway, comparisons to ordinal inscriptions aside, I think there's
> another interesting point from all this.
>
> Presume you have a tool that implements the nostr ordinal assignment
> suggested above: that is, a small modification of the "ord" tool that
> can track a chain of custody for an ordinal specified in a nostr event
> like the above. That allows you to do NFTs completely unobservably --
> you don't have to publish anything to the blockchain apart from ordinary
> looking transactions to transfer ownership of your NFT. To your benefit,
> that makes it hard for anyone to censor you; but to bitcoin more broadly,
> I think it means that the possibility of coloured bitcoins is largely
> unavoidable and simply something that must be dealt with, rather than
> something we should spend time trying to prevent/avoid. Compare with:
>
>> My personal, and possibly controversial, opinion is that colored coin
>> protocols have no business being on the Bitcoin chain, possibly beyond
>> committing to an occasional batched state update or so. Both because
>> there is little benefit for tokens with a trusted issuer already, and
>> because it competes with using Bitcoin for BTC - the token that pays
>> for its security (at least as long as the subsidy doesn't run out).
>>
>> Of course, personal opinions are no reason to dictate what people should
>> or can use the chain for, but I do think it's reason to voice hesitancy
>> to worsening the system's scalability properties only to benefit what
>> I consider misguided use.
> -- https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-September/019500.html
>
> I don't think this actually results in majorly misaligned incentives
> though: in the nostr-nfts-on-btc world, everyone is still optimising
> bitcoin transactions for the same thing -- transfer of value. It's just
> that in some cases some sats are valued differently than others --
> perhaps my uninscribed sats are worth 0.025 cents each, but you have
> a particular inscribed sat that's worth $100k. But we're both dealing
> just spending utxos and creating new utxos, doing signatures and maybe
> some timelocks or hash reveals. And it's always been possible that
> your transaction transferring $100k won't get charged higher fees than
> my transfer of $50 -- we care about transaction size, not value after
> all. How much does it matter if your tx matters more to your because
> someone wants your particular sat, rather than what could happen today
> where you have a utxo with 4 BTC while my utxo only has 0.002 BTC?
>
> I think the only way to prevent that sort of NFT structure would be
> to have every transaction use fancy zero-knowledge proofs that make it
> impossible to associate who received bitcoin with who spent it -- *even
> if* both the sender and recipient were willing to cooperate to reveal
> that information. I think it would be hard to achieve that while still
> making it easy to audit bitcoin's total supply, but I might be wrong.
>
> Note that off-chain colouring here means that someone can create an NFT
> that you don't want it, and just assign it to a sat that's already in your
> wallet. However, they can do this anyway, by first creating the NFT, then
> sending it to your wallet address. A difference though is that they could
> create an NFT and assign it to the same ordinal/sat as some existing NFT
> that you do value, at which point it's (presumably) impossible to discard
> one without discarding both. But again, this is simply something they
> can do, just be writing a patch to ord and composing a nostr message;
> it's not something you can actually prevent even if you dislike it.
>
> Particularly for semi-fungible tokens, this is perhaps inferior to
> Liquid's multi-asset model -- here if you have a utxo with 1M sats, 500
> of which are inscribed to each represent rights to $1 worth of USDT,
> then rather than acting like a stable coin and being worth $500; it's
> actually worth $500+0.01BTC, which is more like $750, and changes as
> the value of bitcoin changes.
>
> Cheers,
> aj
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

2023-06-07 23:18:57

- reply

📅 Original date posted:2023-02-02
🗒️ Summary of this message: Using OP_RETURN is preferable for data payloads smaller than 80 bytes due to the two-step process and potential censorship of the witness envelope method.
📝 Original message:Hello Christopher,
I think if the protocol that you were designing always had <80 bytes,
I'd prefer the OP_RETURN. I think the "witness envelope" has two major
disadvantages compared to the OP_RETURN method:
1. You need to first spend to he address that commits to the script that
encodes your data payload. So you have a two step process of first
spending to a "commitment" address and then a second spend to "reveal"
your payload. You can CPFP to get them both into the same block, but its
still two transactions, so more cost, etc.
2. Because of the two step process in (1), if for some reason you were
unable to get the "reveal" transaction into a block (for example there's
widespread censorship of transactions that match the format of the
"reveal" script), then you might have money that's stuck in the "commit"
stage of the protocol. The way out of this would be to get your money
out via the keypath or another tapleaf, but then you need to spend money
to cancel a step in your protocol. Of course there could be widespread
censorship of your OP_RETURNs too, but you don't have to spend funds on
the cancellation spends.
I think (2) is actually a pretty weak argument because as we saw in the
full-rbf discussion, as long as there's some threshold number of nodes
in the network that relay transactions to miners, you can probably find
a path to a miner (IIRC the number was on the order of 15% of the
network?). So I think the big reason to pick OP_RETURN over the witness
embedding is that you save a transaction and possibly some
failure-recovery/cancellation logic.
Obviously if your data is larger than 80 bytes, then you probably want
to do the witness-embedding method. If your data smaller, then a
pay-to-contract tweak probably the best thing from a space and
fingerprinting perspective.
- rijndael
On 1/31/23 7:46 PM, Christopher Allen via bitcoin-dev wrote:
> All other things being equal, which is better if you need to place a
> 64-bytes into the Bitcoin blockchain? A traditional OP_RETURN or a
> spent taproot transaction such as:
>
> OP_FALSE
> OP_IF
> OP_PUSH my64bytes
> OP_ENDIF
>
> I know that the anti-OP_RETURN folk would say “neither.” But if there
> was no other choice for a particular protocol, such as a timestamp or
> a commitment, which is better? Or is there a safer place to put 64
> bytes that is more uncensorable but also does not clog UTXO space,
> only spent transaction `-txindex` space?
>
> My best guess was that the taproot method is better, but I suspect
> there might be some who disagree. I'd love to hear all sides.
>
> -- Christopher Allen
>

2023-06-07 23:17:20

- reply

📅 Original date posted:2022-12-05
📝 Original message:Good morning,
That sounds like a very dangerous mode of operation. You can already hand a transaction to a miner privately. I hand a transaction to a miner with some reasonable fee, and then I go and broadcast a different transaction with a minimal fee that spends the same inputs. The whole network (including the miner I handed the tx to) could all be running with a strict first-seen mempool policy, but we can still have a situation where the miner creates a block with a different transaction from what you see in your mempool. If anytime this happens, the nodes running your proposed rule drop the block, then anyone can fork those nodes off the network whenever they want.
Even outside of adversarial settings, Bitcoin doesn't (and doesn't attempt to) promise consistency across mempools. Making a consensus rule that enforces mempool consistency is a recipe for (unintended?) chainsplits.
- rijndael
On 12/5/22 7:20 AM, El_Hoy via bitcoin-dev wrote:
> The only option I see against the attack Peter Todd is doing to opt-in RBF and 0Conf bitcoin usage is working on a bitcoin core implementation that stops propagation of full-rbf replaced blocks. Running multiple of such nodes on the network will add a risk to miners that enable full-rbf that would work as an incentive against that.
>
> Obviously that would require adding an option on bitcoin core (that is not technically but politically difficult to implement as Petter Todd already have commit access to the main repository).
>
> That said, a sufficiently incentivized actor (like Daniel Lipshitz or Muun wallet developers) could work on a fork and run several nodes with such functionality. As far as I understand the percolation model, with 10 to 20 nodes running such a rule would create a significant risk for full-rbf miners.
>
> Regards.
>
> --- Eloy
>
> On Tue, Nov 15, 2022 at 11:43 AM Peter Todd via bitcoin-dev <bitcoin-dev at lists.linuxfoundation.org> wrote:
>
>> On Tue, Nov 15, 2022 at 03:36:08PM +1000, Anthony Towns via bitcoin-dev wrote:
>>> On Tue, Nov 08, 2022 at 01:16:13PM -0500, Peter Todd via bitcoin-dev wrote:
>>> > FYI I've gotten a few hundred dollars worth of donations to this effort, and
>>> > have raised the reward to about 0.02 BTC, or $400 USD at current prices.
>>>
>>> Seems like this has been mostly claimed (0.014btc / $235, 9238sat/vb):
>>
>> I'm turning it back on when (if) the mempool settles down. I've got more than
>> enough donations to give another run at it (the majority was donated privately
>> FWIW). There's a risk of the mempool filling up again of course; hard to avoid
>> that.
>>
>> Right now of course it's really easy to double spend with the obvious
>> low-fee/high-fee method as the min relay fee keeps shifting.
>>
>>> https://mempool.space/tx/397dcbe4e95ec40616e3dfc4ff8ffa158d2e72020b7d11fc2be29d934d69138c
>>>
>>> The block it was claimed in seems to have been about an hour after the
>>> default mempool filled up:
>>>
>>> https://twitter.com/murchandamus/status/1592274621977477120
>>>
>>> That block actually seems to have included two
>>> alice.btc.calendar.opentimestamps.org txs, the other paying $7.88
>>> (309sat/vb):
>>>
>>> https://mempool.space/tx/ba9670109a6551458d5e1e23600c7bf2dc094894abdf59fe7aa020ccfead07cf
>>
>> The second is because I turned down the full-rbf reward to more normal fee
>> levels. There's also another full-rbf double-spend from the Bob calendar, along
>> the same lines: 7e76b351009326a574f3120164dbbe6d85e07e04a7bbdc40f0277fcb008d2cd2
>>
>> I double-spent the txin of the high fee tx that got mined. But I mistakenly had
>> RBF enabled in that double-spend, so while it propagated initially, I believe
>> it was replaced when something (someone?) rebroadcast the high-fee 397dcb tx.
>>
>>> Timeline (utc) to me looks like:
>>>
>>> - 13:12 - block 763148 is mined: last one that had a min fee < 1.5sat/vb
>>> - 13:33 - f503868c64d454c472859b793f3ee7cdc8f519c64f8b1748d8040cd8ce6dc6e1
>>> is announced and propogates widely (1.2sat/vb)
>>> - 18:42 - 746daab9bcc331be313818658b4a502bb4f3370a691fd90015fabcd7759e0944
>>> is announced and propogates widely (1.2sat/vb)
>>> - 21:52 - ba967010 tx is announced and propogates widely, since
>>> conflicting tx 746daab9 has been removed from default
>>> mempools
>>> - 21:53 - murch tweets about default mempool filling up
>>> - 22:03 - 397dcbe4 tx is announced and propogates widely, since
>>> conflicting tx f503868 has already been removed from default
>>> mempools
>>
>> Is that 22:03 time for 397 from your node's logs? It was originally announced
>> hours earlier. From one of my full-rbf nodes:
>>
>> 2022-11-14T14:08:37Z [mempool] replacing tx 764867062b67fea61810c3858d587da83a28290545e882935a32285028084317 with 397dcbe4e95ec40616e3dfc4ff8ffa158d2e72020b7d11fc2be29d934d69138c for 0.00468 additional fees, -1 delta bytes
>>
>>> - 22:35 - block 763189 is mined
>>> - 22:39 - block 763190 is mined
>>> - 23:11 - block 763191 is mined
>>> - 23:17 - block 763192 is mined including 397dcbe4
>>>
>>> miningpool.observer reports both 397dcbe4 and ba967010 as missing in the
>>> first three blocks, and gives similar mempool ages for those txs to what
>>> my logs report:
>>>
>>> https://miningpool.observer/template-and-block/0000000000000000000436aba59d8430061e0e50592215f7f263bfb1073ccac7
>>> https://miningpool.observer/template-and-block/00000000000000000005600404792bacfd8a164d2fe9843766afb2bfbd937309
>>> https://miningpool.observer/template-and-block/00000000000000000004a3073f58c9eae40f251ea7aeaeac870daeac4b238fd1
>>>
>>> That presumably means those pools (AntPool twice and "unknown") are
>>> running with large mempools that didn't kept the earlier 1.2sat/vb txs.
>>
>> To be clear, you think that AntPool and that other exchange is running with a
>> larger than normal max mempool size limit? You mean those miners *did* keep the
>> earlier 1.2sat/vb tx?
>>
>>> The txs were mined by Foundry:
>>>
>>> https://miningpool.observer/template-and-block/00000000000000000001382a226aedac822de80309cca2bf1253b35d4f8144f5
>>>
>>> This seems to be pretty good evidence that we currently don't have any
>>> significant hashrate mining with fullrbf policies (<0.5% if there was a
>>> high fee replacement available prior to every block having been mined),
>>> despite the bounty having been collected.
>>
>> Oh, we can put much lower bounds on that. I've been running OTS calendars with
>> full-rbf replacements for a few months without clear evidence of a full-rbf
>> replacement. While there was good reason to think some miners were mining
>> full-rbf before a few years back, they probably didn't bother to reapply their
>> patches each upgrade. `mempoolfullrbf=1` is much simpler to use.
>>
>> --
>> https://petertodd.org 'peter'[:-1]@petertodd.org
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev at lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20221205/27239496/attachment-0001.html>

2023-06-07 23:17:03

- reply

📅 Original date posted:2022-11-25
📝 Original message:Hello Andrew,
As ZmnSCPxj mentioned, covenant schemes are probably something that you
should be looking at and thinking about. In addition to CTV, I'd also
recommend you take a look (if you haven't already) at
`TAPLEAF_UPDATE_VERIFY`
(https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-September/019419.html).
From your description, it sounds like you may be barking up a similar tree.
Rijndael
On 11/21/22 6:52 PM, ZmnSCPxj via bitcoin-dev wrote:
> Good morning Andrew,
>
>>
>> Can output amounts be mapped to a tap branch? For the goal of secure partial spends of a single UTXO? Looking for feedback on this idea. I got it from Taro.
>
> Not at all.
>
> The issue you are facing here is that only one tap branch will ever consume the entire input amount.
> That is: while Taproot has multiple leaves, only exactly one leaf will ever be published onchain and that gets the whole amount.
>
> What you want is multiple tree leaves where ALL of them will EVENTUALLY be published, just not right now.
>
> In that case, look at the tree structures for `OP_CHECKTEMPLATEVERIFY`, which are exactly what you are looking for, and help make `OP_CTV` a reality.
>
> Without `OP_CHECKTEMPLATEVERIFY` it is possible to use presigned transactions in a tree structure to do this same construction.
> Presigned transactions are known to be larger than `OP_CHECKTEMPLATEVERIFY` --- signatures on taproot are 64 bytes of witness, but an `OP_CHECKTEMPLATEVERIFY` in a P2WSH reveals just 32 bytes of witness plus the `OP_CHECKTEMPLATEVERIFY` opcode.
>
> Regards,
> ZmnSCPxj
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

2023-06-07 23:16:57

- reply

📅 Original date posted:2022-11-30
📝 Original message: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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20221130/8371518e/attachment-0001.html>

2023-06-07 23:16:56

- reply

📅 Original date posted:2022-11-30
📝 Original message: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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20221130/fabd885f/attachment-0001.html>