Hi AJ, Thanks for finally putting the pieces together! [0] We've been hacking with Gleb on a paper for the CoinPool protocol [1] during the last weeks and it should be public soon, hopefully highlighting what kind of scheme, TAPLEAF_UPDATE_VERIFY-style of covenant enable :) Here few early feedbacks on this specific proposal, > So that makes it relatively easy to imagine creating a new taproot address > based on the input you're spending by doing some or all of the following: > > * Updating the internal public key (ie from P to P' = P + X) > * Trimming the merkle path (eg, removing CD) > * Removing the script you're currently executing (ie E) > * Adding a new step to the end of the merkle path (eg F) "Talk is cheap. Show me the code" :p case OP_MERKLESUB: { if (!(flags & SCRIPT_VERIFY_MERKLESUB)) { break; } if (stack.size() < 2) { return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION); } valtype& vchPubKey = stacktop(-1); if (vchPubKey.size() != 32) { break; } const std::vector& vch = stacktop(-2); int nOutputPos = CScriptNum(stacktop(-2), fRequireMinimal).getint(); if (nOutputPos < 0) { return set_error(serror, SCRIPT_ERR_NEGATIVE_MERKLEVOUT); } if (!checker.CheckMerkleUpdate(*execdata.m_control, nOutputPos, vchPubKey)) { return set_error(serror, SCRIPT_ERR_UNSATISFIED_MERKLESUB); } break; } case OP_NOP1: case OP_NOP5: template bool GenericTransactionSignatureChecker::CheckMerkleUpdate(const std::vector& control, unsigned int out_pos, const std::vector& point) const { //! The internal pubkey (x-only, so no Y coordinate parity). XOnlyPubKey p{uint256(std::vector(control.begin() + 1, control.begin() + TAPROOT_CONTROL_BASE_SIZE))}; //! Update the internal key by subtracting the point. XOnlyPubKey s{uint256(point)}; XOnlyPubKey u; try { u = p.UpdateInternalKey(s).value(); } catch (const std::bad_optional_access& e) { return false; } //! The first control node is made the new tapleaf hash. //! TODO: what if there is no control node ? uint256 updated_tapleaf_hash; updated_tapleaf_hash = uint256(std::vector(control.data() + TAPROOT_CONTROL_BASE_SIZE, control.data() + TAPROOT_CONTROL_BASE_SIZE + TAPROOT_CONTROL_NODE_SIZE)); //! The committed-to output must be in the spent transaction vout range. if (out_pos >= txTo->vout.size()) return false; int witnessversion; std::vector witnessprogram; txTo->vout[out_pos].scriptPubKey.IsWitnessProgram(witnessversion, witnessprogram); //! The committed to output must be a witness v1 program at least if (witnessversion == 0) { return false; } else if (witnessversion == 1) { //! The committed-to output. const XOnlyPubKey q{uint256(witnessprogram)}; //! Compute the Merkle root from the leaf and the incremented by one path. const uint256 merkle_root = ComputeTaprootMerkleRoot(control, updated_tapleaf_hash, 1); //! TODO modify MERKLESUB design bool parity_ret = q.CheckTapTweak(u, merkle_root, true); bool no_parity_ret = q.CheckTapTweak(u, merkle_root, false); if (!parity_ret && !no_parity_ret) { return false; } } return true; } Here the main chunks for an " OP_MERKLESUB" opcode, with `n` the output position which is checked for update and `point` the x-only pubkey which must be subtracted from the internal key. I think one design advantage of explicitly passing the output position as a stack element is giving more flexibility to your contract dev. The first output could be SIGHASH_ALL locked-down. e.g "you have to pay Alice on output 1 while pursuing the contract semantic on output 2". One could also imagine a list of output positions to force the taproot update on multiple outputs ("OP_MULTIMERKLESUB"). Taking back your citadel joint venture example, partners could decide to split the funds in 3 equivalent amounts *while* conserving the pre-negotiated script policies [2] For the merkle branches extension, I was thinking of introducing a separate OP_MERKLEADD, maybe to *add* a point to the internal pubkey group signer. If you're only interested in leaf pruning, using OP_MERKLESUB only should save you one byte of empty vector ? We can also explore more fancy opcodes where the updated merkle branch is pushed on the stack for deep manipulations. Or even n-dimensions inspections if combined with your G'root [3] ? Note, this current OP_MERKLESUB proposal doesn't deal with committing the parity of the internal pubkey as part of the spent utxo. As you highlighted well in your other mail, if we want to conserve the updated key-path across a sequence of TLUV-covenanted transactions, we need either a) to select a set of initial points, where whatever combination of add/sub, it yields an even-y point. Or b) have the even/odd bit re-committed at each update. Otherwise, we're not guaranteed to cancel the point from the aggregated key. This property is important for CoinPool. Let's say you have A+B+C+D, after the D withdraw transaction has been confirmed on-chain, you want A+B+C to retain the ability to use the key-path and update the off-chain state, without forcing a script path spend to a new setup. If we put the updated internal key parity bit in the first control byte, we need to have a redundant commitment somewhere else as we can't trust the spender to not be willingly to break the key-path spend of the remaining group of signers. One solution I was thinking about was introducing a new tapscript version (`TAPROOT_INTERNAL_TAPSCRIPT`) signaling that VerifyTaprootCommitment must compute the TapTweak with a new TapTweak=(internal_pubkey || merkle_root || parity_bit). A malicious participant wouldn't be able to interfere with the updated internal key as it would break its own spending taproot commitment verification ? > That's useless without some way of verifying that the new utxo retains > the bitcoin that was in the old utxo, so also include a new opcode > IN_OUT_AMOUNT that pushes two items onto the stack: the amount from this > input's utxo, and the amount in the corresponding output, and then expect > anyone using TLUV to use maths operators to verify that funds are being > appropriately retained in the updated scriptPubKey. Credit to you for the SIGHASH_GROUP design, here the code, with SIGHASH_ANYPUBKEY/ANYAMOUNT extensions. if ((output_type & SIGHASH_GROUP) == SIGHASH_GROUP) { // Verify the output group bounds if (execdata.m_bundle->first == execdata.m_bundle->second || execdata.m_bundle->second >= tx_to.vout.size()) return false; // Verify the value commitment if (VerifyOutputsGroup(tx_to, cache.m_spent_outputs[in_pos].nValue, execdata.m_bundle->first, execdata.m_bundle->second)) return false; for (unsigned int out_pos = execdata.m_bundle->first; out_pos < execdata.m_bundle->second + 1; out_pos++) { bool anypubkey_flag = false; bool anyamount_flag = false; std::map::const_iterator it; if ((output_type & SIGHASH_GROUP_ANYPUBKEY) == SIGHASH_GROUP_ANYPUBKEY) { it = execdata.m_anypubkeys.find(out_pos); if (it != execdata.m_anypubkeys.end() && it->second == 1) { anypubkey_flag = true; } } if ((output_type & SIGHASH_GROUP_ANYAMOUNT) == SIGHASH_GROUP_ANYAMOUNT) { it = execdata.m_anyamounts.find(out_pos); if (it != execdata.m_anyamounts.end() && it->second == 1) { anyamount_flag = true; } } if (!anypubkey_flag) { ss << tx_to.vout[out_pos].scriptPubKey; } if (!anyamount_flag) { ss << tx_to.vout[out_pos].nValue; } } } I think it's achieving the same effect as IN_OUT_AMOUNT, at least for CoinPool use-case. A MuSig `contract_pubkey` can commit to the `to_withdraw` output while allowing a wildcard for the `to_pool` output nValue/scriptPubKey. The nValue correctness will be ensured by the group-value-lock validation rule (`VerifyOutputsGroup`) and scriptPubkey by OP_MERKLESUB commitment. I think witness data size it's roughly equivalent as the annex fields must be occupied by the output group commitment. SIGHASH_GROUP might be more flexible than IN_OUT_AMOUNT for a range of use-cases, see my point on AMM. > The second scheme is allowing for a utxo to represent a group's pooled > funds. The idea being that as long as everyone's around you can use > the taproot key path to efficiently move money around within the pool, > or use a single transaction and signature for many people in the pool > to make payments. But key path spends only work if everyone's available > to sign -- what happens if someone disappears, or loses access to their > keys, or similar? For that, we want to have script paths to allow other > people to reclaim their funds even if everyone else disappears. So we > setup scripts for each participant, eg for Alice: > > * The tx is signed by Alice > * The output value must be at least the input value minus Alice's balance > * Must pass TLUV such that: > + the internal public key is the old internal pubkey minus Alice's key > + the currently executing script is dropped from the merkle path > + no steps are otherwise removed or added Yes the security model is roughly similar to the LN one. Instead of a counter-signed commitment transaction which can be broadcast at any point during channel lifetime, you have a pre-signed withdraw transaction sending to {`to_withdraw`,`to_pool`} outputs. Former is your off-chain balance, the latter one is the pool balance, and one grieved with the updated Taproot output. The withdraw tapscript force the point subtraction with the following format (` <33-byte contract_pubkey> OP_CHECKSIG) > A simpler case for something like this might be for funding a joint > venture -- suppose you're joining with some other early bitcoiners to > buy land to build a citadel, so you each put 20 BTC into a pooled utxo, > ready to finalise the land purchase in a few months, but you also want > to make sure you can reclaim the funds if the deal falls through. So > you might include scripts like the above that allow you to reclaim your > balance, but add a CLTV condition preventing anyone from doing that until > the deal's deadline has passed. If the deal goes ahead, you all transfer > the funds to the vendor via the keypath; if it doesn't work out, you > hopefully return your funds via the keypath, but if things turn really > sour, you can still just directly reclaim your 20 BTC yourself via the > script path. Yes, that kind of blockchain validation semantic extension is vaudoo-magic if we want to enable smart corporation/scalable multi-event contracts. I gave a presentation on advanced bitcoin contracts two years ago, mentioning we would need covenants to solve the factorial complexity on edge-case [4] Bitcoin ledger would fit perfectly well to host international commerce law style of contracts, where you have a lot of usual fancy provisions (e.g hardship, delay penalty, ...) :) > First it can't tweak scripts in areas of the merkle tree that it can't > see -- I don't see a way of doing that particularly efficiently, so maybe > it's best just to leave that as something for the people responsible for > the funds to negotiate via the keypath, in which case it's automatically > both private and efficient since all the details stay off-chain, anyway Yeah, in that kind of case, we might want to push the merkle root as a stack element but still update the internal pubkey from the spent utxo ? This new merkle_root would be the tree of tweaked scripts as you expect them if you execute *this* tapscript. And you can still this new tree with a tapbranch inherited from the taproot output. (I think I could come with some use-case from lex mercatoria where if you play out a hardship provision you want to tweak all the other provisions by a CSV delay while conserving the rest of their policy) > And second, it doesn't provide a way for utxos to "interact", which is > something that is interesting for automated market makers [5], but perhaps > only interesting for chains aiming to support multiple asset types, > and not bitcoin directly. On the other hand, perhaps combining it with > CTV might be enough to solve that, particularly if the hash passed to > CTV is constructed via script/CAT/etc. That's where SIGHASH_GROUP might be more interesting as you could generate transaction "puzzles". IIUC, the problem is how to have a set of ratios between x/f(x). I think it can be simplified to just generate pairs of input btc-amount/output usdt-amount for the whole range of strike price you want to cover. Each transaction puzzle has 1-input/2-outputs. The first output is signed with SIGHASH_ANYPUBKEY but committed to a USDT amount. The second output is signed with SIGHASH_ANYAMOUNT but committed to the maker pubkey. The input commits to the spent BTC amount but not the spent txid/scriptPubKey. The maker generates a Taproot tree where each leaf is committing to a different "strike price". A taker is finalizing the puzzle by inserting its withdraw scriptPubKey for the first output and the maker amount for the second output. The transitivity value output group rule guarantees that a malicious taker can't siphon the fund. > (I think everything described here could be simulated with CAT and > CHECKSIGFROMSTACK (and 64bit maths operators and some way to access > the internal public key), the point of introducing dedicated opcodes > for this functionality rather than (just) having more generic opcodes > would be to make the feature easy to use correctly, and, presuming it > actually has a wide set of use cases, to make it cheap and efficient > both to use in wallets, and for nodes to validate) Yeah, I think CHECKSIGFROMSTACK is a no-go if we want to emulate TAPLEAF_UPDATE_VERIFY functionality. If you want to update the 100th tapscript, I believe we'll have to throw on the stack the corresponding merkle branch and it sounds inefficient in terms of witness space ? Though ofc, in both cases we bear the tree traversal computational cost ? Really really excited to see progress on more powerful covenants for Bitcoin :) Cheers, Antoine [0] For the ideas genealogy, I think Greg's OP_MERKLE_UPDATE has been circulating for a while and we chatted with Jeremy last year about the current limitation of the script interpreter w.r.t expressing the factorial complexity of advanced off-chain systems. I also remember Matt's artistic drawing of a TAPLEAF_UPDATE_VERIFY ancestor on a Chaincode whiteboard :) [1] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-June/017964.html [2] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016249.html [3] A legal construction well-spread in the real-world. Known as "indivision" in civil law". [4] https://github.com/ariard/talk-slides/blob/master/advanced-contracts.pdf Le jeu. 9 sept. 2021 à 02:42, Anthony Towns via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> a écrit : > Hello world, > > A couple of years ago I had a flight of fancy [0] imagining how it > might be possible for everyone on the planet to use bitcoin in a > mostly decentralised/untrusted way, without requiring a block size > increase. It was a bit ridiculous and probably doesn't quite hold up, > and beyond needing all the existing proposals to be implemented (taproot, > ANYPREVOUT, CTV, eltoo, channel factories), it also needed a covenant > opcode [1]. I came up with something that I thought fit well with taproot, > but couldn't quite figure out how to use it for anything other than my > ridiculous scheme, so left it at that. > > But recently [2] Greg Maxwell emailed me about his own cool idea for a > covenant opcode, which turned out to basically be a reinvention of the > same idea but with more functionality, a better name and a less fanciful > use case; and with that inspiration, I think I've also now figured out > how to use it for a basic vault, so it seems worth making the idea a > bit more public. > > I'll split this into two emails, this one's the handwavy overview, > the followup will go into some of the implementation complexities. > > > > The basic idea is to think about "updating" a utxo by changing the > taproot tree. > > As you might recall, a taproot address is made up from an internal public > key (P) and a merkle tree of scripts (S) combined via the formula Q=P+H(P, > S)*G to calculate the scriptPubKey (Q). When spending using a script, > you provide the path to the merkle leaf that has the script you want > to use in the control block. The BIP has an example [3] with 5 scripts > arranged as ((A,B), ((C,D), E)), so if you were spending with E, you'd > reveal a path of two hashes, one for (AB), then one for (CD), then you'd > reveal your script E and satisfy it. > > So that makes it relatively easy to imagine creating a new taproot address > based on the input you're spending by doing some or all of the following: > > * Updating the internal public key (ie from P to P' = P + X) > * Trimming the merkle path (eg, removing CD) > * Removing the script you're currently executing (ie E) > * Adding a new step to the end of the merkle path (eg F) > > Once you've done those things, you can then calculate the new merkle > root by resolving the updated merkle path (eg, S' = MerkleRootFor(AB, > F, H_TapLeaf(E))), and then calculate a new scriptPubKey based on that > and the updated internal public key (Q' = P' + H(P', S')). > > So the idea is to do just that via a new opcode "TAPLEAF_UPDATE_VERIFY" > (TLUV) that takes three inputs: one that specifies how to update the > internal public key (X), one that specifies a new step for the merkle path > (F), and one that specifies whether to remove the current script and/or > how many merkle path steps to remove. The opcode then calculates the > scriptPubKey that matches that, and verifies that the output corresponding > to the current input spends to that scriptPubKey. > > That's useless without some way of verifying that the new utxo retains > the bitcoin that was in the old utxo, so also include a new opcode > IN_OUT_AMOUNT that pushes two items onto the stack: the amount from this > input's utxo, and the amount in the corresponding output, and then expect > anyone using TLUV to use maths operators to verify that funds are being > appropriately retained in the updated scriptPubKey. > > > > Here's two examples of how you might use this functionality. > > First, a basic vault. The idea is that funds are ultimately protected > by a cold wallet key (COLD) that's inconvenient to access but is as > safe from theft as possible. In order to make day to day transactions > more convenient, a hot wallet key (HOT) is also available, which is > more vulnerable to theft. The vault design thus limits the hot wallet > to withdrawing at most L satoshis every D blocks, so that if funds are > stolen, you lose at most L, and have D blocks to use your cold wallet > key to re-secure the funds and prevent further losses. > > To set this up with TLUV, you construct a taproot output with COLD as > the internal public key, and a script that specifies: > > * The tx is signed via HOT > * CSV -- there's a relative time lock since the last spend > * If the input amount is less than L + dust threshold, fine, all done, > the vault can be emptied. > * Otherwise, the output amount must be at least (the input amount - > L), and do a TLUV check that the resulting sPK is unchanged > > So you can spend up to "L" satoshis via the hot wallet as long as you > wait D blocks since the last spend, and can do whatever you want via a > key path spend with the cold wallet. > > You could extend this to have a two phase protocol for spending, where > first you use the hot wallet to say "in D blocks, allow spending up to > L satoshis", and only after that can you use the hot wallet to actually > spend funds. In that case supply a taproot sPK with COLD as the internal > public key and two scripts, the "release" script, which specifies: > > * The tx is signed via HOT > * Output amount is greater or equal to the input amount. > * Use TLUV to check: > + the output sPK has the same internal public key (ie COLD) > + the merkle path has one element trimmed > + the current script is included > + a new step is added that matches either H_LOCKED or H_AVAILABLE as > described below (depending on whether 0 or 1 was provided as > witness info) > > The other script is either "locked" (which is just "OP_RETURN") or > "available" which specifies: > > * The tx is signed via HOT > * CSV -- there's a relative time lock since the last spend (ie, > when the "release" script above was used) > * If the input amount is less than L, fine, all done, the vault can > be emptied > * Otherwise, the output amount must be at least (the input amount minus > L), and via TLUV, check the resulting sPK keeps the internal pubkey > unchanged, keeps the merkle path, drops the current script, and adds > H_LOCKED as the new step. > > H_LOCKED and H_AVAILABLE are just the TapLeaf hash corresponding to the > "locked" and "available" scripts. > > I believe this latter setup matches the design Bryan Bishop talked about > a couple of years ago [4], with the benefit that it's fully recursive, > allows withdrawals to vary rather than be the fixed amount L (due to not > relying on pre-signed transactions), and generally seems a bit simpler > to work with. > > > > The second scheme is allowing for a utxo to represent a group's pooled > funds. The idea being that as long as everyone's around you can use > the taproot key path to efficiently move money around within the pool, > or use a single transaction and signature for many people in the pool > to make payments. But key path spends only work if everyone's available > to sign -- what happens if someone disappears, or loses access to their > keys, or similar? For that, we want to have script paths to allow other > people to reclaim their funds even if everyone else disappears. So we > setup scripts for each participant, eg for Alice: > > * The tx is signed by Alice > * The output value must be at least the input value minus Alice's balance > * Must pass TLUV such that: > + the internal public key is the old internal pubkey minus Alice's key > + the currently executing script is dropped from the merkle path > + no steps are otherwise removed or added > > The neat part here is that if you have many participants in the pool, > the pool continues to operate normally even if someone makes use of the > escape hatch -- the remaining participants can still use the key path to > spend efficiently, and they can each unilaterally withdraw their balance > via their own script path. If everyone decides to exit, whoever is last > can spend the remaining balance directly via the key path. > > Compared to having on-chain transactions using non-pooled funds, this > is more efficient and private: a single one-in, one-out transaction > suffices for any number of transfers within the pool, and there's no > on-chain information about who was sending/receiving the transfers, or > how large the transfers were; and for transfers out of the pool, there's > no on-chain indication which member of the pool is sending the funds, > and multiple members of the pool can send funds to multiple destinations > with only a single signature. The major constraint is that you need > everyone in the pool to be online in order to sign via the key path, > which provides a practical limit to how many people can reasonably be > included in a pool before there's a breakdown. > > Compared to lightning (eg eltoo channel factories with multiple > participants), the drawback is that no transfer is final without an > updated state being committed on chain, however there are also benefits > including that if one member of the pool unilaterally exits, that > doesn't reveal the state of anyone remaining in the pool (eg an eltoo > factory would likely reveal the balances of everyone else's channels at > that point). > > A simpler case for something like this might be for funding a joint > venture -- suppose you're joining with some other early bitcoiners to > buy land to build a citadel, so you each put 20 BTC into a pooled utxo, > ready to finalise the land purchase in a few months, but you also want > to make sure you can reclaim the funds if the deal falls through. So > you might include scripts like the above that allow you to reclaim your > balance, but add a CLTV condition preventing anyone from doing that until > the deal's deadline has passed. If the deal goes ahead, you all transfer > the funds to the vendor via the keypath; if it doesn't work out, you > hopefully return your funds via the keypath, but if things turn really > sour, you can still just directly reclaim your 20 BTC yourself via the > script path. > > > > I think a nice thing about this particular approach to recursive covenants > at a conceptual level is that it automatically leaves the key path as an > escape mechanism -- rather than having to build a base case manually, > and have the risk that it might not work because of some bug, locking > your funds into the covenant permanently; the escape path is free, easy, > and also the optimal way of spending things when everything is working > right. (Of course, you could set the internal public key to a NUMS point > and shoot yourself in the foot that way anyway) > > > > I think there's two limitations of this method that are worth pointing out. > > First it can't tweak scripts in areas of the merkle tree that it can't > see -- I don't see a way of doing that particularly efficiently, so maybe > it's best just to leave that as something for the people responsible for > the funds to negotiate via the keypath, in which case it's automatically > both private and efficient since all the details stay off-chain, anyway > > And second, it doesn't provide a way for utxos to "interact", which is > something that is interesting for automated market makers [5], but perhaps > only interesting for chains aiming to support multiple asset types, > and not bitcoin directly. On the other hand, perhaps combining it with > CTV might be enough to solve that, particularly if the hash passed to > CTV is constructed via script/CAT/etc. > > > > (I think everything described here could be simulated with CAT and > CHECKSIGFROMSTACK (and 64bit maths operators and some way to access > the internal public key), the point of introducing dedicated opcodes > for this functionality rather than (just) having more generic opcodes > would be to make the feature easy to use correctly, and, presuming it > actually has a wide set of use cases, to make it cheap and efficient > both to use in wallets, and for nodes to validate) > > Cheers, > aj > > [0] https://gist.github.com/ajtowns/dc9a59cf0a200bd1f9e6fb569f76f7a0 > > [1] Roughly, the idea was that if you have ~9 billion people using > bitcoin, but can only have ~1000 transactions per block, then you > need have each utxo represent a significant number of people. That > means that you need a way of allowing the utxo's to be efficiently > spent, but need to introduce some level of trust since expecting > many people to constantly be online seems unreliable, but to remain > mostly decentralised/untrusted, you want to have some way of limiting > how much trust you're introducing, and that's where covenants come in. > > [2] Recently in covid-adjusted terms, or on the bitcoin consensus > change scale anyway... > https://mobile.twitter.com/ajtowns/status/1385091604357124100 > > [3] > https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki#Constructing_and_spending_Taproot_outputs > > [4] > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-August/017231.html > > [5] The idea behind an automated market maker being that you setup a > script that says "you can withdraw x BTC if you deposit f(x) units of > USDT, or you can withdraw g(x) units of USDT if you deposit x units > of BTC", with f(x)/x giving the buy price, and f(x)>g(x) meaning > you make a profit. Being able to specify a covenant that links the > change in value to the BTC utxo (+/-x) and the change in value to > the USDT utxo (+f(x) or -g(x)) is what you'd need to support this > sort of use case, but TLUV doesn't provide a way to do that linkage. > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >