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<unsigned char>& 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 <class T>
bool GenericTransactionSignatureChecker<T>::CheckMerkleUpdate(const std::vector<unsigned char>& control, unsigned int out_pos, const std::vector<unsigned char>& point) const
{
//! The internal pubkey (x-only, so no Y coordinate parity).
XOnlyPubKey p{uint256(std::vector<unsigned char>(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<unsigned char>(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<unsigned char> 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 "<n> <point> 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<unsigned int, char>::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 (`<n> <withdraw_point> <OP_MERKLESUB> <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