Schnorr and taproot (etc) upgrade
6 messages, 14 to 18 Dec 2018. Started by Anthony Towns.
Anthony Towns (2), Russell O'Connor (2), Johnson Lau (2)
Hi *,
(All the following is heavily informed by talking with other smart people, and while probably all the clever ideas are theirs, any nonsense and mistakes are certainly my own. I guess I'll pretend there were Chatham House rules or something to avoid any blame/responsibility accidently landing on their shoulders? Anyway, I hope discussing this in public turns out more useful and productive than disastrous and bikesheddy :)
Rusty wrote "Without a concrete taproot proposal it's hard to make assertions". I'm not going to offer a completely concrete proposal, but fwiw, here's my thoughts on what should be included in the segwit v1 proposal, which I think might be concrete enough for discussion purposes:
- introduce 33-byte v1 witness addresses should encode a secp256k1 ECC point (P), spendable either by:
- a direct schnorr signature (s,R) on that point
(s*G = R + H(R,P,txdigest)*P), with the 1-byte sighash per the
other thread indicating exactly what goes into the tx digest, etc
- a script (s), the witness data for the script (wit(s)),
with a taproot/merkle path to the script (P,path(S,s)),
satisfying the taproot condition (Q = P + H(P,S)*G)
- the taproot scripts should get a version, and since you have to provide P anyway in order to spend by a script, you've got 7-bits spare in the byte that encodes the evenness/oddness of P, so that gives you v1.0 to v1.127 for free. So if we define script version 0 initially, and just automatically accept any script with a later version, we can soft-fork arbitrary script upgrades without bumping the segwit (major) version.
- we should replace the ECDSA CHECKSIG/CHECKMULTISIG ops with new Schnorr ops. A name that's been suggested for the new ops is "CHECKDLS" for discrete-log-signature; I'm using that.
Rather than CHECKMULTISIG, a simple, more general approach seems to be "CHECKDLSADD" which takes a signature, a number, and a pubkey, and increments the number if the signature is valid, and leaves it untouched if not. So "2 of 3 multisig" becomes "0 <p> CHECKDLSADD <q> CHECKDLSADD <r> CHECKDLSADD 2 EQ", eg. That means replacing the current four CHECK(multi)SIG(verify) opcodes, with three opcodes: CHECKDLS, CHECKDLSVERIFY and CHECKDLSADD.
To make batch verifiability of signatures work, the only acceptable invalid signature for CHECKDLS or CHECKDLSADD needs to be an empty vector; anything else should fail the script/transaction/block.
- adding OP_MASK to support script masking via sighash per the other thread; note this only matters for the new CHECKDLS opcodes, since for direct signatures on the scriptPubKey, there is no script to mask. This means it's completely changeable with new script versions, if desired.
- making (almost) all the currently invalid opcodes upgradeable with what I'm calling "OP_SUCCESS" semantics [0], so that we have more flexibility than OP_NOP gives us. An approach for those semantics that seems fairly easy to analyse is to treat script processing as going in phases:
1. tokenise; check push sizes and overall script size
2. if any OP_SUCCESS appeared; succeed
3. if banned opcodes appeared; fail (OP_VERIF, OP_VERNOTIF?)
4. otherwise, run the script; fail if there's an error
5. if there's exactly one, non-zero item on the stack; succeed
6. otherwise; fail
(Obviously an implementation can do these in parallel if that's more efficient)
That way any of the "OP_SUCCESS" opcodes can be replaced by any normal opcode (eg addition, a different sort of signature checking, push tx or blockchain data to the stack) in a soft-fork; and you can easily be sure that the new functionality is a soft-fork (as long as you're not trying to change how pushes work)
[1]
This even means you could use an OP_SUCCESS opcode to signal an upgrade of other opcodes, eg an OP_ARITH64BIT that upgrades OP_ADD etc to support arithmetic on 64 bit inputs.
- and that's it.
I think this is a fairly modest collection of changes:
signature/address stuff: - schnorr - new sighash (including "noinput") - taproot - merkelized-scripts - avoid weird CHECKMULTISIG behaviour upgradeability: - script minor versions - OP_SUCCESS
I think there's a good reason to bundle all those together: the signature stuff go together with a new address version, and the upgradeability stuff helps reduce the need to do more new address versions.
Well, it's modest at least compared to what's conceivable: there are a *lot* of other neat ideas that could theoretically be done in the same soft-fork, but IMHO are better left for later, eg:
- graftroot, g'root, cross-input signature aggregation - non-interactive half-signature aggregation - re-enabling opcodes (CAT, MUL, XOR, etc) - check-sig-of-msg-on-stack, push txdata, other covenant-y things - different cryptosystems (eg, 384 bit curves for better protection against future quantum computing advances; conceivably pairing curves?) - "EVAL" and similar language features - [etc]
As far as how those things could get done in future, this collection of features leaves four ways to make further improvements:
- new segwit version (v2-v16)
(needed for graftroot, signature aggregation, different signature
systems)
- different length segwit v1 pubkey
(could be used to provide a hash instead of the actual taproot point,
or use a larger ECC curve)
- new segwit v1 script version (v1.0-v1.127) (needed for big redesigns/simplifications of script)
- additional opcodes (OP_SUCCESS replacement)
(can be used to re-enable disabled opcodes like MUL/CAT/XOR/etc;
can be used to add more complicated things like CHECKSTACKDLS,
or PUSHTXDATA; can be used to try out different signature
schemes)
I think its worth noting that OP_SUCCESS upgrades could be developed/deployed in parallel, since you just need to choose an opcode to take over and (presumably) a versionbit to signal when the new behaviour gets activated. The other methods require agreeing on everything that's going to go in the new version, which needs a bit more coordination.
[2]
Anyway, to get back to the intro sentence, and to give an example of how I think v1 addresses will work, here's my take on Eltoo in a taproot world:
Funding tx:
inputs: <whatever>
outputs:
...
i. pay to Q = P+H(P,S)G
P = muSig(A,B)
S = "MASK <500M> CLTV <P> CHECKDLSVERIFY"
...
Update tx n:
nlocktime = 500M + n
inputs:
1. Funding tx, or Update tx m, m<n;
witness: P, (S or Sm),
sig(P, sighash=in_scriptmask:"MASK VERIF CLTV <P> CHECKDLSVERIFY")
outputs:
1. pay to Qn = P+H(P,Sn)G
Sn = "MASK <500M+n+1> CLTV <P> CHECKDLSVERIFY
Settlement tx n:
inputs:
1. Update tx n (unknown txid);
witness: sig(Qn, sighash=in_scriptpubkey)
nseq = csv delay
(note: Qn != Qm unless n=m, because Sn != Sm)
outputs:
1: pay A's balance to A
2: pay B's balance to B
3..n: HTLC paying to B: see below
Cooperative close:
inputs:
Funding tx, sig(Q, sighash=in_all+out_all)
outputs:
1..n: as agreed
(I'm assuming you create "Update tx 0" and "Settlement tx 0" to pay yourself back if setup fails, prior to publishing the funding tx. The eltoo paper has a "trigger" phase for that purpose instead, aiui. Also, these two txs don't actually need to use NOINPUT, because they directly spend from the funding tx)
As far as the HTLC outputs go... For SHA256 preimages, you prepare a taproot address Q=P+H(P,SH), where SH is the merkle root for the tree of two scripts, "<t> CLTV <A> CHECKDLSVERIFY" and "HASH160 <h> EQUAL <B> CHECKDLSVERIFY". For secp256k1 preimages, your address is P'=muSig(A,B,n*G) for some value n that just ensures you have different keys for each htlc, and you prepare two pre-signed transactions, spending the settlement output (whose txid is unknown), both signed with sighash committing to the scriptPubKey and a single output. One pays A and has a partial signature from B and nTimeLock set to the timeout; so A can complete the signature and claim after the timeout; the other pays B and has a conditional partial signature from A, which B can complete upon finding out the preimage.
The settlement and pre-signed-HTLC-spend transactions all make use of the NOINPUT-commit-to-scriptPubKey varaint in this arrangement; so it does seem like it's probably useful in practice; scriptless scripts make the direct-signature path pretty useful.
Cheers, aj
[0] aka OP_RETURNTRUE https://bitcointalk.org/index.php?topic=1106586.0 aka OP_RETURNVALID https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-March/015838.html
[1] The "drawback" to this approach is that it means that you can't
partially verify a script if you think you know what the first few
opcodes mean; so if a script upgrade has happened but your node hasn't
upgraded, even if you see a transaction in a block with what you
think is "<p> OP_CHECKDLS OP_SUCCESS", you don't check the signature.
[2] One thing that could be feasible would be to have some simple
OP_SUCCESS upgrades (like enabling CAT/XOR/etc or adding
CHECKSTACKDLS) specced, implemented, and tested, and have them
activate at the same time as schnorr/taproot/etc, while keeping them
as an independent feature at the BIP/concept/implementation levels.
The idea there is that if it turns out they're not ready in time,
schnorr/taproot/etc don't need to get delayed, and the others can
just be enabled when they're ready later using a separate version bit.
I'm not sure if there's anyone who's interested in shepherding/doing
the spec/implementation for any of the more straight-forward features
like that, though.On Fri, Dec 14, 2018 at 8:39 AM Anthony Towns via bitcoin-dev < bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (2 lines)
> 5. if there's exactly one, non-zero item on the stack; succeed >
Unless it is too much bikeshedding, I'd like to propose that to succeed the stack must be exactly empty. Script is more composable that way, removing the need for special logic to handle top-level CHECKSIG, vs mid-level CHECKSIGVERIFY.
Quoted text (10 lines)
> On 16 Dec 2018, at 7:38 AM, Russell O'Connor via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote: > > On Fri, Dec 14, 2018 at 8:39 AM Anthony Towns via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org <mailto:bitcoin-dev@lists.linuxfoundation.org>> wrote: > 5. if there's exactly one, non-zero item on the stack; succeed > > Unless it is too much bikeshedding, I'd like to propose that to succeed the stack must be exactly empty. Script is more composable that way, removing the need for special logic to handle top-level CHECKSIG, vs mid-level CHECKSIGVERIFY. > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation•org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
I proposed the same in BIP114. I wish Satoshi had designed that way. But I’m not sure if that would do more harm than good. For example, people might lose money by copying an existing script template. But they might also lose money in the same way as CHECKMULTISIG is disabled. So I’m not sure.
Another related thing I’d like to bikeshed is to pop the stack after OP_CLTV and OP_CSV. The same pros and cons apply.
On Mon, Dec 17, 2018 at 3:16 PM Johnson Lau <jl2012@xbt•hk> wrote:
Quoted text (3 lines)
> > I proposed the same in BIP114. I wish Satoshi had designed that way. >
Thanks. I probably read that and internalized it and forgot you wrote it.
Quoted text (8 lines)
> But I’m not sure if that would do more harm than good. For example, people > might lose money by copying an existing script template. But they might > also lose money in the same way as CHECKMULTISIG is disabled. So I’m not > sure. > > Another related thing I’d like to bikeshed is to pop the stack after > OP_CLTV and OP_CSV. The same pros and cons apply. >
This one is almost a no-brainer I think. Nearly every instance of OP_CSV is followed by an OP_DROP and we'd save 1 WU per OP_CSV if we pop the stack afterwards.
On Mon, Dec 17, 2018 at 10:18:40PM -0500, Russell O'Connor wrote:
Quoted text (5 lines)
> On Mon, Dec 17, 2018 at 3:16 PM Johnson Lau <jl2012@xbt•hk> wrote: > But I’m not sure if that would do more harm than good. For example, people > might lose money by copying an existing script template. But they might > also lose money in the same way as CHECKMULTISIG is disabled. So I’m not > sure.
Well, if CHECKSIG* and CHECKMULTISIG* are all disabled in favour of CHECKDLS, CHECKDLSVERIFY and CHECKDLSADD with both different names and different opcodes, copying a script template opcode-for-opcode from v0 to v1 will always fail. (With taproot, this doesn't necessarily mean you lose money, even if the script is impossible to ever satisfy, since you may be able to recover via the direct signature path)
Quoted text (5 lines)
> Another related thing I’d like to bikeshed is to pop the stack after > OP_CLTV and OP_CSV. The same pros and cons apply. > This one is almost a no-brainer I think. Nearly every instance of OP_CSV is > followed by an OP_DROP and we'd save 1 WU per OP_CSV if we pop the stack > afterwards.
It's definitely bikeshedding so whatever; but to me, it seems like it'd be easier for everyone to have it so that if you've got the same opcode in v0 script and v1.0 script; they have precisely the same semantics.
(That said, constructions like "<n> CLTV <p> CHECKSIGVERIFY" that avoid the DROP and work when you're expected to leave a true value on the stack won't work if you have to end up with an empty stack)
Cheers, aj
Quoted text (33 lines)
> On 18 Dec 2018, at 12:58 PM, Anthony Towns <aj@erisian•com•au> wrote: > > On Mon, Dec 17, 2018 at 10:18:40PM -0500, Russell O'Connor wrote: >> On Mon, Dec 17, 2018 at 3:16 PM Johnson Lau <jl2012@xbt•hk> wrote: >> But I’m not sure if that would do more harm than good. For example, people >> might lose money by copying an existing script template. But they might >> also lose money in the same way as CHECKMULTISIG is disabled. So I’m not >> sure. > > Well, if CHECKSIG* and CHECKMULTISIG* are all disabled in favour of > CHECKDLS, CHECKDLSVERIFY and CHECKDLSADD with both different names and > different opcodes, copying a script template opcode-for-opcode from v0 > to v1 will always fail. (With taproot, this doesn't necessarily mean you > lose money, even if the script is impossible to ever satisfy, since you > may be able to recover via the direct signature path) > >> Another related thing I’d like to bikeshed is to pop the stack after >> OP_CLTV and OP_CSV. The same pros and cons apply. >> This one is almost a no-brainer I think. Nearly every instance of OP_CSV is >> followed by an OP_DROP and we'd save 1 WU per OP_CSV if we pop the stack >> afterwards. > > It's definitely bikeshedding so whatever; but to me, it seems like it'd > be easier for everyone to have it so that if you've got the same opcode > in v0 script and v1.0 script; they have precisely the same semantics. > > (That said, constructions like "<n> CLTV <p> CHECKSIGVERIFY" that avoid > the DROP and work when you're expected to leave a true value on the > stack won't work if you have to end up with an empty stack) > > Cheers, > aj >
I think you mean <p> CHECKSIGVERIFY <n> CLTV, but this works only for simple script. Most likely you need a DROP if you use IF or CODESEPARATOR.
However, if we change the rule from “one true stack item” to “empty stack”, CLTV/CSV popping stack will make more sense. So I think either we change all, or change nothing.
The “true stack item” and CLTV/CSV as NOP are tech debt. Fixing them in new script version makes script creation easier and sometimes cheaper, but the fix itself creates further tech debts in the code. So I don’t have strong opinion on this topic.