Skip to content

Instantly share code, notes, and snippets.

@markblundeberg
Last active December 13, 2019 22:39
Show Gist options
  • Save markblundeberg/a3aba3c9d610e59c3c49199f697bc38b to your computer and use it in GitHub Desktop.
Save markblundeberg/a3aba3c9d610e59c3c49199f697bc38b to your computer and use it in GitHub Desktop.
BIP62 and Schnorr: a new era in BCH privacy and smart contracting

Two new features are coming to Bitcoin Cash soon, hopefully in the May 2019 upgrade. I'd like to take the time to explain why I'm so excited about them. In short, we will be able to do:

  • Payment channels hidden as ordinary payments.
  • Atomic swaps hidden as ordinary payments.
  • Lightning-style payment channel networks too, if we want.
  • Secure chains of unconfirmed transactions involving multiple parties (layer 2).

That all may sound incredible, and I'm going to explain in this document how it is so.

--- Mark B. Lundeberg, 2019 Jan 29 bitcoincash:qqy9myvyt7qffgye5a2mn2vn8ry95qm6asy40ptgx2

Contents

The upgrades

The two important planned features for the May 2019 upgrade are: 1) complete the BIP62 malleability restrictions, and 2) allow users to spend using Schnorr signatures in place of ECDSA signatures. Why is this a big deal?

  • No more third-party malleability: By completing the BIP62 malleability fixes, it will be possible to make P2PKH-spending transactions that cannot be malleated by any third party (miners, relay nodes, etc.). This removes the need for OP_CHECKLOCKTIMEVERIFY timeout clauses. We can also engineer smart contracts to be immune from malleability.
  • Hiding as P2PKH: Schnorr signatures allow very simple multi-party aggregation schemes, where multiple parties collaborate to produce one aggregated signature under one aggregated pubkey, checked with OP_CHECKSIG as in pay-to-public-key-hash (P2PKH) addresses.
  • Avoid second-party malleability: Schnorr signatures cannot be malleated at all, even in the aggregated case, except when all signers collaborate to create a new signature from scratch.

Each of these three aspects is a significant upgrade. Together, however, they make up a massive upgrade: we will be able to make multi-signature transactions, which are not malleable by third parties or unilaterally by a subset of signing parties. This creates the perfect conditions for doing complex off-chain smart contracting. And best of all, those multi-signatures will appear on the blockchain as P2PKH, i.e., indistinguishable from regular payments. Altogether, it's a simpler and more private replacement for complicated 'malleability fix' transaction formats like segwit.

Better payment channels

Review - OP_CLTV payment channels: One of the most basic smart contracts possible on Bitcoin Cash right now is the standard monodirectional payment channel from Alice->Bob, where Alice funds a script with the following pseudocode:

Unlock if Alice and Bob both sign, or,
Unlock if only Alice signs, but provided the transaction is mined after a certain minimum refund timeout.

Alice and Bob can collaborate together so that Bob can create a 'channel update' transaction under the first condition, which sends some funds to Bob, and some funds back to Alice as change. They can make an unlimited number of updates, increasing the payment to Bob every time. When they're done, Bob just publishes the last update. If Bob becomes unresponsive, Alice knows she can get a refund after a certain timeout period, using the refund clause. The refund clause requires OP_CHECKLOCKTIMEVERIFY (OP_CLTV), activated in 2015, and so these are called OP_CLTV payment channels.

Unfortunately the above custom script is very obvious on the blockchain. While the two parties involved may be pseudonymous, it is obvious to any blockchain analyst that a payment channel was created and closed.

Review - Spilman payment channels: Prior to the introduction of OP_CLTV, a simpler approach called Spilman payment channels was considered. This simply used a 2-of-2 OP_CHECKMULTISIG between Alice and Bob, but where Alice and Bob signed a time-locked refund transaction ahead of time, before Alice funded the channel. Unfortunately, Spilman channels are currently insecure on BCH due to malleability: Bob can ask a miner to change the txid of Alice's funding, which would then invalidate the refund and allow Bob to hold all the payment channel funds ransom, indefinitely.

New hidden payment channels: The BCH upgrades change this story. Not only can we use Spilman channels, but they don't even need to use OP_CHECKMULTISIG and can instead be done with regular P2PKH addresses:

  • Spilman channels will be secure due to BIP62 malleability restrictions. Only Alice can malleate her funding transaction, and this would only hurt herself.
  • The Spilman channel's 2-of-2 multisignature (OP_CHECKMULTISIG) can be done using an aggregated signature (OP_CHECKSIG).

I'll repeat that for emphasis: we will be able to do payment channels which merely use P2PKH -- completely indistinguishable from ordinary transactions.

Schnorr-Spilman payment channels protocol

The process in detail:

  • Setup:
    • Alice and Bob generate private keys and an aggregated public key (A+B) with some P2PKH address.
    • Alice creates and signs a funding transaction that creates a coin C at the above address. Alice withholds the signed transaction, but she shares the parameters of coin C (txid, value, and scriptPubKey) with Bob.
    • Alice now creates a refund transaction which spends C back to herself, with nLockTime set to a future date.
    • Alice and Bob work together to sign the refund transaction. Alice keeps a backup of this refund transaction, and Bob makes a note of its refund time (nLockTime).
    • Alice now publishes the funding transaction.
    • Alice and Bob now wait for the funding transaction to confirm on chain.
  • Payments:
    • Alice and Bob create an unsigned transaction that spends C, with part sent to an address controlled by Bob, and the remainder refunded to Alice.
    • Alice and Bob interactively generate a signature, but crucially at the last step, Bob does not share the final signature with Alice and keeps it secret.
    • This can be repeated an unlimited number of times, provided the amount sent to Bob increases monotonically.
  • Closure (normal):
    • Bob chooses the most recent payment transaction (the one with most funds sent to him) and publishes it.
  • Closure (abnormal):
    • Once nLockTime is reached, Alice can publish the refund transaction, which sends all funds back to her.

Graphical illustration

To illustrate the distinction between CLTV payment channels and Schnorr-Spilman channels, I've created the following figures. In these figures,

  • dashed transactions and addresses show paths that are prepared off-chain, but normally do not get published;
  • solid lines show the normal path of transactions that does get published on-chain; and
  • I've highlighted P2SH outputs in pink since they stand out so obviously, i.e., they have a low anonymity set.
  • For simplicity, I've just put "A" and "B" for Alice and Bob however it should be understood that they use a new public key for every step of the process, both for security and privacy reasons.

In the normal CLTV payment, the payment channel coin (the pink box) itself is obvious.

CLTV payment channels
Fig 1: CLTV payment channels.

With a regular Spilman channel, this gets a bit better but the payment channel coin is still locked in a P2SH script, for a 2-of-2 multisignature. I didn't illustrate this, but you can imagine the above but "A & B" inside the pink box.

When we move to Schnorr-Spilman channels, the payment channel coin is now an aggregated signature on Alice and Bob's public key, represented here as "A+B". Instead of the refund transaction being created by Alice alone, it is instead arranged ahead of time by Alice and Bob together.

Schnorr-Spilman channels
Fig 2: Schnorr-Spilman channels.

Hidden atomic swaps (+ high frequency microswapping)

In a previous gist, I described how trustless cross-chain atomic swaps can be hidden inside payment channels. They have an additional advantage over normal swaps in that they are faster to set up, and allow for instant high frequency trades between the involved parties. The same thing can be done with Schnorr-Spilman payment channels, at least on the BCH side of the swap. I've continued the illustration theme from above with Fig 3 below, to show how this works.

On the top you can see a Schnorr-Spilman channel on BCH. On the bottom is a CLTV payment channel on OtherChain (this could also be a 2-of-2 Lightning, Taproot, or Raiden channel).

In the case of a normal closure, the dashed objects do not land on chain, and so the BCH atomic swaps are entirely hidden behind P2PKH transactions on the BCH chain. In the case of abnormal closure, the fancy smart contracts do land on chain.

Ideally, both chains should use such concealed P2PKH payment channel, but this is not absolutely needed for privacy. Even if the other chain uses a more obvious form of payment channel, it is very difficult to find the corresponding BCH transaction.

Atomic swaps in Schnorr-Spilman channels
Fig 3: atomic swaps can be concealed in Schnorr-Spilman channels.

Hidden bidirectional payment channels

It should also be possible to do Poon-Dryja (i.e., Lightning-style) payment channels that rely on punishment-style refund transactions. Chris Pacia hinted on Medium about how this will be secure once BIP62 activates. Note that there is a limitation, insofar that these payment channels have to be unilaterally funded (see Caveat section below).

Again, there is an advantage with Schnorr signatures in that the initial 2-of-2 multisignature can be hidden as a 2-of-2 Schnorr aggregate signature. The refund smart contracts will only land on chain in the case of an uncooperative closure.

I'll skip showing a figure of this setup as it gets quite a bit more complex than regular payment channels, and it is not the point of this article.

Layer 2

In the preceding sections we have only exploited the BIP62's third-party malleability fixes and the possibility to hide multisignatures through aggregation. If you recall however, the introduction mentioned a third point: Schnorr signatures cannot be malleated, except when the all signers involved collaborate to create a new signature.

The fact that an aggregated Schnorr signature cannot be malleated by any strict subset of the parties means that we can build layer 2 (e.g., lightning network) on BCH.

Securing unconfirmed transaction chains

With third party malleability fixes alone, regular OP_CHECKMULTISIG multisignatures are unfortunately still malleable by any of the involved parties. They can simply create a new signature using a new nonce value, varying the sighash type, and so on. This is a problem for chains of unconfirmed transactions, such as in the following example.

Alice enters into a two-stage smart contract with Bob, for simplicity shown here as simple "A&B" which represents a 2-of-2 OP_CHECKMULTISIG. Let's say she builds tx2 and tx3 together with Bob, before she reveals tx1. Bob cannot malleate tx1 (due to BIP62 protection) and Alice has no motive to malleate her own transaction. So, tx1 is safe. With tx2 it is different: one of the signatures (from Bob) can be manipulated. This creates a new transaction (tx2'), whose output Y' is now distinct in transaction ID from the original intended output Y. If tx2' is confirmed instead of tx2, then the tx3 that Alice and Bob created is now useless since it spends a nonexistent coin Y, and it cannot spend Y'. Unfortunately, Bob does have an incentive to do this: he can hold Alice's funds (Y') ransom indefinitely.

Insecure transaction chains using multiple signatures
Fig 4: long transaction chains involving multiple signatures can be malleated by any of the involved parties.

With Schnorr aggregate signatures, Bob can't make that crucial step of changing the signature on his own. The reason has to do with the strong mathematical structure of Schnorr signatures (r, s):

  • For every r there is a unique s value that produces a valid signature.
  • Therefore, the creation of a new signature (distinct r or s) requires changing r to some other r'.
  • The r value is hash-committed into e=H(r|m) which is necessary to check the validity of s. The new value is e'.
  • With a new e', Alice's contribution to s is now useless in calculating the correct new s'.
  • Bob therefore would have to create a new contribution from Alice, which would be equivalent to forging a signature from her key.
  • Thus, a distinct signature can only be created by starting the entire signing process over again, including Alice's cooperation. Alice would of course only want do this if she has first secured a new tx3'.

Secure transaction chains using aggregate signatures
Fig 5: long transaction chains involving aggregate Schnorr signatures are unmalleable.

Making unmalleable smart contracts

Once BIP62 activations are done, it's possible to write smart contracts whose scriptSig inputs cannot be malleated. This may require some care, for example with OP_IF clauses, however I'd node that additional restrictions like SCRIPT_VERIFY_MINIMALIF are not necessary to make non-malleable clauses. I strongly suspect that in all cases, it is easy to convert complex smart contracts into a non-malleable form under BIP62+Schnorr alone. This can be done with input sanitization or script tweaks to take advantage of NULLFAIL (see link).

Caveat: difficulties with order-of-signing and backup transactions

One of the difficulties with BIP62+Schnorr is the order of signing. Consider the following order of operations necessary in BIP62+Schnorr to create a new transaction spending from the Alice+Bob pubkey, along with its backup transaction:

  1. Alice creates unsigned tx1 and gives to Bob.
  2. Alice and Bob sign tx1 but at the end, Alice withholds her s value. She keeps tx1 secret but calculates and shares txid1.
  3. Alice creates unsigned tx2 -- the backup transaction which spends from txid1.
  4. Alice and Bob sign tx2.
  5. Once Alice has tx2, she can reveal tx1 to Bob.

The problem here is that at the end of step 2, Alice is in possession of a fully signed tx1 before Bob has tx2. It's not possible to reverse the ordering since tx2 must include the txid of the fully signed tx1. Thus, tx1 and the order of signing have to be carefully designed, so that the party holding the fully signed tx1 (Alice in this case) cannot harm other parties by publishing it before tx2 is created. This a particularly serious concern for smart contracts involving more than two parties.

A simple tweak like SIGHASH_NOINPUT would be an elegant fix to this problem, as it allows tx2 to be signed before a fully signed tx1 exists. SIGHASH_NOINPUT has other advantages too, for example it would also allow simplified Layer 2 structures like Eltoo's floating transaction mechanism, which doesn't have punishments and doesn't accumulate toxic information. But, that is a topic for another article...

Differences from segwit

The BIP62 + Schnorr approach to layer 2 has some advantages and disadvantages compared to segwit:

  • Our Schnorr signatures require only a very tiny change in wallet code, which means wallet developers can rapidly transition to Schnorr and drop support for ECDSA entirely.
  • With BIP62+Schnorr, smart contract authors must take a more thoughtful approach to prevent malleability, but this is easily accomplished.
  • Segwit makes a total of 66 different kinds of address -- besides the two legacy address types (p2pkh, p2sh), each of the 16 segwit versions has 4 address types (p2wpkhv0, p2sh-p2wpkhv0, p2wshv0, p2sh-p2wshv0, p2wpkhv1, p2sh-p2wpkhv1, p2wshv1, p2sh-p2wshv1, ... p2wpkhv15, p2sh-p2wpkhv15, p2wshv15, p2sh-p2wshv15). Our Schnorr approach only modifies one legacy address class (p2pkh). For privacy reasons, it is desirable to have as few address types in use as possible, so as to not fracture the anonymity set.
  • Backup transactions are easier to set up with segwit, especially in the multi-party case.

Lightning network

Since BIP62 + Schnorr allows Layer 2 constructions, this means a Lightning network should be possible on BCH. Although direct peer-to-peer on-chain transactions and direct payment channels are the primary use case for bitcoin cash, it wouldn't hurt to have a low-value Lightning network for micropayments in situations where direct payment channels could not be set up ahead of time.

@markblundeberg
Copy link
Author

@christroutner Thanks! All of these protocols would be happening off-chain so the existing infrastructure would be none-the-wiser. As far as I know, none of them inspect the signature itself so they won't even care about a Schnorr sig appearing where ECDSA sig normally goes.

@gmaxwell
Copy link

FWIW, the giant abandoned notice on BIP62 is because it doesn't remove all forms of third party malleability. Please stop claiming otherwise.

@markblundeberg
Copy link
Author

@gmaxwell that's correct, even with bip62 it's easy to make transactions that are 3rd-party malleable. But the main thing for me is, with BIP62 adopted you can at least choose to make unmalleable transactions when needed.

I'd also remark that segwit doesn't remove all forms of 3rd party malleability, if using unusual sighash flags... though obviously that's a more cleanly deliberate choice on the part of signers.

@NorwayGH
Copy link

I'm happy to see BCH is heading in the same direction as BTC.

@gmaxwell
Copy link

BIP62 adopted you can at least choose to make unmalleable transactions when needed.

This is not true either. It may be the case that a subset of scripts can be made non-malleable, but even that is not proven and it is known to not be true for scripts in general. BIP62 was abandoned after we continued to find more and more corner cases and realized a fully general true fix was needed rather than attempting to wack-a-mole blacklist sources.

@bitcoinstore
Copy link

gmaxwell, why do you even care?
Mark, thank you for your efforts.

@joshmg
Copy link

joshmg commented Feb 17, 2019

@gmaxwell Do you have any documentation of the corner cases you or your peers have discovered aside from the ones already mentioned in BIP62? From what I'm reading, there's a bit of miscommunication between you and @markblundeberg -- unless there are still-undiscovered malleability methods, it's possible to create scripts that are to enable payment channels, which seems to be a significant point of this HF. I don't think Mark is claiming that all scripts are inherently unmalleable if the user is intentionally (or carelessly) creating scripts that allow malleability (OP_DROP being an easy example).

I'm not trying to be adversarial--if you have any documentation from past discoveries of malleability outside of BIP62 then it would be a useful service to BCH to point them out.

@GreenAppers
Copy link

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment