OP_CHECKPRIVPUBPAIR

Prior discussion: http://lists.linuxfoundation.org/pipermail/lightning-dev/2015-November/000309.html

Goal: Greatly improve security for payment networks like the 'Lightning Network' (LN) [1]

---

Introduction: To improve privacy while using a payment network, it is possible to use onion-routing to make a payment to someone. In this context, onion-routing means encrypting the data about subsequent hops in a way that each node only knows where it received a payment from and the direct next node it should send the payment to. This way we can route a payment over N nodes, and none of these will know

(1) at which position it is within the route (first, middle, last?)

(2) which node initially issued the payment (payer)

(3) which node consumes the payment (payee).

However, given the way payments in LN work, each payment is uniquely identifiable by a preimage-hash pair R-H. H is included in the output script of the commit transaction, such that the payment is enforceable if you ever get to know the preimage R.

In a payment network each node makes a promise to pay the next node, if they can produce R. They can pass on the payment, as they know that they can enforce the payment from a previous node using the same preimage R. This severely damages privacy, as it lowers the amount of nodes an attacker has to control to gain information about payer and payee.

---

Problem: The problem was inherited by using RIPEMD-160 for preimage-hash construction. For any cryptographic hash-function it is fundamentally unfeasible to correlate preimage and hash in such a way, that

F1(R1) = R2 and F2(H1) = H2, while SHA(R1) = H1 and SHA(R2) = H2.

In other words, I cannot give a node H1 and H2 and ask it to receive my payment using H1, but pass it on using H2, as the node has no way of verifying it can produce R1 out of the R2 it will receive. If it cannot produce R1, it is unable to enforce my part of the contract.

---

Solution: While above functions are merely impossible to construct for a cryptographic hash functions, they are trivial when R and H is a EC private/public key pair. The original sender can make a payment using H1 and pass on a random number M1, such that the node can calculate a new public key

H2 = H1 + M1.

When he later receives the private key R2, he can construct

R1 = R2 - M1

to be able to enforce the other payment. M1 can be passed on in the onion object, such that each node can only see M for that hop. Furthermore, it is unfeasible to brute-force, given a sufficiently large number M.

---

Example:

Given that E wants to receive a payment from A, payable to H. (if A can produce R, it can be used as a prove he made the payment and E received it)

A decides to route the payment over the nodes B, C and D. A uses four numbers M1...M4 to calculate H1...H4. The following payments then take place

A->B using H4 B->C using H3 C->D using H2 D->E using H1.

When E receives H1, he can use attached M1 to calculate R1 from it. The chain will resolve itself, and A is able to calculate R using M1...M4. It also means that all privacy is at the sole discretion of the sender, and that not even the original pair R/H is known to any of the nodes.

To improve privacy, E could also be a rendezvous point chosen by the real receiver of the payment, similar constructions are similar in that direction as well.

---

Caveats:

Currently it is difficult to enforce a payment to a private-public key pair on the blockchain. While there exists OP_HASH160 OP_EQUAL to enforce a payment to a hash, the same does not hold true for EC keys. To make above possible we would therefore need some easy way to force a private key, given a public key. This could be done by using one of the unused OP_NOP codes, which will verify

<private key> <public key> OP_CHECKPRIVPUBPAIR

and fails if these are not correlated or NOP otherwise. Would need OP_2DROP afterwards. This would allow deployment using a softfork.

As there are requests for all sort of general crypto operations in script, we can also introduce a new general OP_CRYPTO and prepend one byte for the operation, so

0x01 OP_CRYPTO = OP_CHECKPRIVPUBPAIR 0x02-0xff OP_CRYPTO = OP_NOP

to allow for extension at some later point.

---

Alternatives:

In the attached discussion there are some constructions that would allow breaking the signature scheme, but they are either very large in script language or expensive to calculate. Given that the blocksize is a difficult topic already, it would not be beneficial to have a 400B+ for each open payment in case one party breaches the contract. (or just disappears for a couple of days)

It is also possible to use a NIZKP - more specifically SNARK - to prove to one node that it is able to recover a preimage R1 = R2 XOR M1, given only H1, H2 and M1. However, these are expensive to calculate and experimental in it's current state.

---

Acknowledgements: Gregory Maxwell for pointing out addition of M1 for EC points is much less expensive Pieter Wuille for helping with general understanding of EC math. Anthony Towns for bringing up the issue and explaining SNARKs

[1] http://lightning.network/

On Fri, Nov 27, 2015 at 09:02:37AM +0100, Mats Jerratsch via bitcoin-dev wrote:

> <private key> <public key> OP_CHECKPRIVPUBPAIR
> As there are requests for all sort of general crypto operations in
> script, we can also introduce a new general OP_CRYPTO and prepend one
> byte for the operation, so
> 0x01 OP_CRYPTO = OP_CHECKPRIVPUBPAIR
> 0x02-0xff OP_CRYPTO = OP_NOP
> to allow for extension at some later point.

This wouldn't be a softfork -- a single prefixed 0x01 byte would just push "OP_CRYPTO" onto the stack... If you had OP_CRYPTO look at the top item on the stack to determine what to do, you could have:

  OP_[0-16] OP_CRYPTO
  OP_PUSHDATA1 [0x11-0xFF] OP_CRYPTO
  OP_PUSHDATA2 [0x00-0xFF] [0x01-0xFF] OP_CRYPTO
  ...

to get 17 different crypto ops in two bytes, and the next 238 in three, and be arbitrarily expandable from there with multibyte pushes.

> Alternatives:
> In the attached discussion there are some constructions that would
> allow breaking the signature scheme, but they are either very large in
> script language or expensive to calculate.

I think that's good enough to try them out in prototypes though -- and presumably if they're demonstrably useful in prototypes that's a good argument for adding a dedicated op code to script?

Are there any other crypto ops that might be worth adding into a BIP for a check-verify crypto toolkit op like this? The only ones that come to mind as having practical uses in the near term are:

 Base-point multiply on secp256k1 (ie, CHECKPUBPRIVPAIR)
 Schnorr-signature of transaction with secp256k1 curve (smaller,
   faster, more-anonymous N-of-N multisig)

But perhaps there's also uses for some of:

General point addition on secp256k1 General point multiply on secp256k1 SHA3-256 / SHA2-512 / SHA3-512 ECDSA/Schnorr signature of value from stack ...?

Then again, I gather that if the segregated witness soft-fork turns out to be plausible, re-enabling/changing/adding *any* sort of opcode could be done as a soft-fork, not just turning a NOP into CHECK_foo_VERIFY... So it might be better to wait and see how that goes before putting too much time into drafting a BIP or similar?

Cheers, aj