Create overview of the PQ fork

[ChristopherA]

We need to create a new README.md for this fork explaining the concept.

@maaku originally wrote describing the opportunity:

secp256k1 is defined using arithmetic over the prime field of order p.
Point addition is a group operation with order n, where n is also
prime and nearly but not exactly equal to p. With bulletproofs we are
able to make and check in zero knowledge assertions about integer
arithmetic modulo the order of the curve n, of values inside a
Pedersen commitment (vG+rH). As an intuition pump, you can see how
this arises as adding two Pedersen commitments is the same as adding
the underlying committed values and blinding factors modulo the group
size: c1+c2=(v1+v2 mod n)G+(r1+r2 mod n)H.

However what if we want to check curve operations in zero knowledge?
E.g. proving in zero knowledge that you have a signature for a given
message and public key, or the pre-image of a given Pedersen hash.
Such curve operations are over the field Fp, so this proof is of
arithmetic "mod p" not "mod n". Bulletproofs on secp256k1 are ONLY
able to check assertions about integer assertions (technically,
arithmetic circuits) where the computation is done mod n, where n is
the order of the generator of the curve.

So to do a bulletproof of a secp256k1 curve operation we would need to
use a curve whose generator has order p. As it happens, if one took
the equation and parameters for secp256k1 and merely definitionally
swap the values for n and p, you get a totally unrelated curve (no
homomorphisms between them), but for which n and p are swapped. This
curve is given the cutsy name "secq256k1" -- mind your p's and q's! --
and is sortof a "mirror" curve to secp256k1. Adding to Pedersen
commitments in secp256k1 is the same as adding the underlying values
modulo n, whereas the same operation in secq256k1 is modulo p. So
field arithmetic in secp can be represented as arithmetic over
committed values in seq, and vice versa. This allows us to now prove
things about secp curve operations -- signatures, Pedersen hashes,
etc. -- by using a bulletproof in secq.

[Aside: And since the relationship is symmetrical, we can even do
recursive bulletproofs in secp, which prove the existence of a proof
in secq, of an operation that happened in secp, etc. What utility this
has, if any, remains to be seen however.]

[Addendum: secq proofs are not strictly speaking necessary in order to
evaluate statements mod-p instead of mod-n, as you could of course
create a mod-n circuit interpreter for mod-p statements, but we'd
expect that to be hideously inefficient by comparison to native
support. And zero knowledge proofs are already barely efficient enough
to work with natively as it is.]

[maaku]

One interesting application of this technology, should it come to fruition, is in hardware wallet security. RFC-6979, used by secp256k1, specifies a rather complex deterministic algorithm for generating signing nonces using multiple invocations of HMAC-SHA512. Ed25519 simply hashes the private key material with the message being signed. In either application it is not possible to verify that the deterministic nonce derivation was performed correctly without possessing the secret key, which by security assumption is isolated to the hardware signing device. This is a problem because replacing the nonce generator with, say, a biased random number generator would allow an adversary to recover private key material from the signatures observed on the block chain.

However with bulletproofs a proof can be generated by the signing device that shows a given deterministic algorithm was followed for the generation of the nonce used in a given signature, and that proof is verifiable given only the publicly available information consisting of the pubkey, message, and signature. For RFC-6979 such a proof would be 10's of kB in size, take minuites to generate, and 10's of seconds to validate on a modern workstation CPU. The algorithm used by Ed25519 would probably take around 20s to generate a proof 1.5kB in size, and 750ms to validate. The former would be impossible on a constrained hardware wallet, the latter probably doable on the more capable hardware wallets, but with a poor user experience.

If, on the other hand, the Ed25519 approach was taken using Pedersen hashes instead of Blake2b as the hash function, a "secq" bulletproof would be able to verify the nonce derivation of a signature using public data in relatively little time, with fewer resources. The arithmetic circuit would be about a thousand gates, and a proof 1kB in size could be generated in about 0.5s and take 25ms to verify. This Pedersen hash would be composed of "secp" elliptic curve points, so the proof would live on "secq" and require a libsecq256k1 signing and verification library.

With this capability a user of a hardware device could have confidence that the messages being signed are using a deterministic nonce derivation scheme and not leaking key material due to a built-in backdoor or biased random number generator, while at the same time not violating their security assumptions by loading the private key on another device to check. Furthermore the wallet software on the user's phone or computer could check these proofs before broadcasting the signature in a transaction, preventing insecure hardware signers from being used.

Bulletproof aggregation potentially makes it even possible that the hardware signing device maintain an append-only "signature log" which proves in logarithmic space, with incremental signing and linear verification time that EVERY signature created using a master HD wallet key used a properly devised nonce, potentially useful when loading wallet data into a new device, or when generating multiple signatures for large and complex protocols like lightning.

(These numbers are all napkin math, probably reliable on order of magnitude only. See the bulletproofs paper for the benchmark data they're derived from: https://eprint.iacr.org/2017/1066.pdf)

[ChristopherA]

My latest description of project:

Bulletproofs in SecQ

Overview

Recent research on optimization of zero-knowledge cryptographic arithmetic circuits called Bulletproofs has allowed the practical implementation of extremely fast range proofs and other integer proofs under the popular secp256k1 elliptic curve used by the Bitcoin and Ethereum blockchains, as well as many blockchains derived from them.

There is an opportunity to leverage a “mirror” elliptic curve to the secp256k1 curve, that we are calling SecQ, to allow for an entirely new class of bulletproofs that can offer zero-knowledge cryptographic arithmetic circuit proofs about points on a elliptic curve, thus about signatures and keys. These offer powerful new opportunities for zero-knowledge proof protocols.

Motivation and Impact

Many challenges of network security are about trusting the computational results of a potentially untrustworthy computer, without parties revealing information that could cause the security or privacy of one or more parties to be compromised. Zero-knowledge cryptographic circuits offer support for multi-party computation to avoid these problems. Basically these implement computational circuits that resemble the primitives of AND, OR, XOR gates used by silicon processors, but executed by cryptography.

In the past cryptographic circuits have been extremely computationally inefficient, or the proofs themselves have been too large to be useful for many applications. More recently, using a subset of cryptographic circuits known as arithmetic circuits, and in particular the most recent innovation known as Bulletproofs, have been shown to make some proofs practical in performance and size.

Current implementation of Bulletproofs that have been shown to be feasible have been limited to integer proofs (range, set membership, set math, etc.). Taking advantage of some of the unique properties of the secp256k1 elliptic curve, it may now be possible to also offer practical proofs about signatures and keys.

Success of this project offers not only opportunities to increase financial confidentiality by hiding transaction amounts, the spend graph, or both (which range proofs can offer on blockchain), but also increase the security of the signatures and keys themselves, thus offering additional security and privacy guarantees.

Technical Approach

Any arbitrary zero-knowledge proof can be implemented as cryptographic circuit using boolean computation, however, these have been shown to be extremely computational inefficient and impractical. In recent years there have been advances in zero-knowledge proofs that are implemented by subset known as arithmetic circuits which function over a finite field. As elliptic curve cryptography also uses finite fields, some (but not all) zero-knowledge proofs that can be described as arithmetic circuits can be optimized to make them practical.

The most recent advance in this field, known as Bulletproofs (https://ia.cr/2016/263), takes advantage of some of the properties of the elliptic curve known as secp256k1 (or "SecP") which is used by Bitcoin and many other blockchains. Bulletproofs allow us to create practical cryptographic arithmetic circuits where we can compactly assert statements about integer arithmetic done modulo the prime curve n (aka "mod(n)"). In SecP, n is a very large number close 2^256. With this we can create range proofs (is i an integer between x & y), set membership (does integer a exist in a set) and set math (add subtract multiply divide sets of integers).

In particular, range proofs mod(n) have have been shown to be potentially very useful to provide confidentiality for business transactions (See: https://blockstream.com/2018/02/21/bulletproofs-faster-rangeproofs-and-much-more.html). These make zero knowledge assertions about integer arithmetic mod(n), such that they compactly (in one gate) prove that a Pedersen commitment of a scalar value is within a certain range (vG+rH). This arises as adding two Pedersen commitments is the same as adding the underlying committed values and blinding factors modulo the group size: c1+c2=(v1+v2 mod n)G+(r1+r2 mod n)H.

As useful as zero-knowledge integer proofs mod(n) are, it would be very useful if we could offer zero-knowledge proofs about curves. These would allow us to prove in zero knowledge that you have a signature for a given message and public key, or the pre-image of a given Pedersen hash. These curve proofs would require us to make proofs about mod(p), the other parameter of SecP, not mod(n). Thus Bulletproofs in SecP are limited to integers because the group order and the field element size are different.

We could theoretically use existing mod(n) circuits to create a mod(p) circuit interpreter, but we’d expect that to be several orders of magnitude less efficient. In general, zero knowledge proofs are already have are barely efficient enough to run on commodity signing hardware in mod(p) as it is.

Thus to do a Bulletproof of curve operation we would need to use a curve whose generator has order p, which with most elliptic curves is difficult or impossible to find. Fortunately, the choices made by the SecP curve for the values primes n and p are such that we do have an option. As it happens, if one takes the equation and parameters for SecP and merely definitionally swap the values for n and p, you get a totally unrelated curve (no homomorphisms between them), but for which n and p are swapped, and a new generator point G can be found. This make SecQ the ideal curve to use for bulletproofs of SecP's mod(p) curve operations. We give this curve the cutsy name “secq256k1” or SecQ ("mind your p's and q's") -- making this is sort of a "mirror" curve where the field element and group order primes are switched.

Since the relationship between SecP and SecQ curves are symmetrical, we can even do recursive bulletproofs. A zero-knowledge proof could then be constructed from a chain of bulletproofs which alternate between SecP and its mirror curve. For instance in SecP, prove the existence of a proof in SecQ, of an operation that happened in SecP, etc. with each Bulletproof except the last having potentially many outputs which serve as inputs to one or more of the later proofs in the chain. What possibilities this offers, if any, remains to be seen, however, the authors believe these may offer a fruitful future for further exploration of practical zero-knowledge proofs.

[notes:]

• The elliptic curve used by Bitcoin and many other blockchains is known as secp256k1. It is a Koblitz curve defined using equation y^2 = x^3 + 7 over a finite field in the order prime p, where p was chosen in a predictable way as to be a large prime number close to a 32-byte integer (2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1 < 2^256). To do elliptic curve signatures we use point addition as a group operation with order n, where n is also prime and nearly but not exactly equal to p. (See: https://en.bitcoin.it/wiki/Secp256k1). The parameters for secp256k1 are defined in http://www.secg.org/sec2-v2.pdf, but how the group generator point G was chosen is unknown (See: https://bitcointalk.org/index.php?topic=289795.msg3183975#msg3183975). (See also: https://bitcoin.stackexchange.com/a/39148)

[maaku]

Comments inline:

Many challenges of network security are about trusting the computational results of a potentially untrustworthy computer, without parties revealing key material that could cause the security of one or more parties to be compromised. Zero-knowledge cryptographic circuits offer support for multi-party computation to avoid these problems. Basically these implement computational circuits that resemble the primitives of AND, OR, XOR gates used by silicon processors, but executed by cryptography.

I would say “without parties revealing information that could cause the security or privacy of …"

Success of this project offers not only opportunities to increase financial confidentiality (which range proofs can offer on blockchain), but also increase the security of the signatures and keys themselves, thus offering additional security and privacy guarantees.

Maybe alter to “increase financial confidentiality by hiding transaction amounts, the spend graph, or both”

I’m not sure what you mean by “increase the security of the signatures and keys themselves.” Bulletproofs doesn’t add any cryptographic security. Do you mean the trick about a hardware signing exporting a proof that it performed a calculation correctly? I would consider that more assurance about the integrity of tamper-resistant hardware devices than “increase the security of the signatures and keys” which seems to imply added cryptographic guarantees.

We could theoretically use existing mod(n) circuits to create a mod(p) circuit interpreter, but we’d expect that to be hideously inefficient. In general, zero knowledge proofs are already have are barely efficient enough to function in mod(p) as it is.

Replace “hideously inefficient” with “several orders of magnitude less efficient”

Extend “barely efficient enough” to “barely efficient enough to run on commodity signing hardware"

[ChristopherA]

I incorporated the suggested changes in my draft.

@maaku wrote:

I’m not sure what you mean by “increase the security of the signatures and keys themselves.” Bulletproofs doesn’t add any cryptographic security.

Besides the key signing proof idea, what are some other concrete examples/use cases for which mod(p) proofs that SecQ can provide? I suggest that you can prove that one key is derived from another without the risks that BIP32 currently has. mod(p) is also used by signatures, so I assume there are some useful proofs there. Thus my statement "increase the security of signatures and keys themselves". Am I missing something?

An any case, this reveals the weakness of the above in that we need some more productive use cases for SecQ.

[kanzure]

How could you use zero-knowledge proofs of signatures or curves as a way to eliminate a transaction graph (as mentioned above)? What would you be proving-- the equivalency of two sets of transactions where one set is smaller but same outcome?

[ChristopherA]

@jimmysong has a basic python library that implements the curve https://github.com/jimmysong/secq

[apoelstra]

Heads up you cannot directly derive a nonce using a Pedersen hash since the output would be badly non-uniform.

Dan Boneh suggests doing two Pedersen hashes (on the same input, so this can be done with a circuit much smaller than twice the size of a Pedersen hash circuit) and concatenating them (super easy, just multiply by 2^256 and add).

@kanzure by proving something like zcash's Sapling circuit.

[maaku]

@apoelstra That's the plan. Was the description not clear on that point?

[maaku]

@apoelstra Reviewing this, I'm actually wondering if I misinterpreted your heads-up. Are you saying (1) apply a Pedersen hash function twice to the same input in series, or (2) apply two Pedersen hashes (with different generators) and somehow combine the results? I assume "multiply by 2^256 and add" is modulo the prime p?

[real-or-random]

@sipa and I are currently working on this... The idea with the two Pedersen hashes has multiple serious issues:

• The Pedersen hash is designed to be a collision-resistant hash function, but we actually need a pseudorandom function (PRF), which is just a different primitive
• We don't think that the idea with using two PRFs and combining the results as suggested by Dan Boneh is provably secure.

We're currently considering a PRF built on a curve over F_q and its quadratic twist, where q is the order of secp256k1. (But we cannot use the secq curve because its twist is too weak.)

For every field element x, we have that either x is an x-coordinate on the curve or -x is an x-coordinate on the twist. So by computing a PRF on the curve and a second PRF on its twist, and randomly selecting the x-coordinate (and possibly negating) of one of the resulting two curve points gives you a PRF onto bits. The candidate PRFs for the curves are k*H(x) where k is the key and m is the input of PRF. Here, H is a random oracle. I can explain more details if you're interested but it's not really yet stable right now.

[ChristopherA]

@real-or-random or @sipa — any progress on your k*H(x) PRF?

[real-or-random]

There is progress. We're currently working on a draft paper but we don't have anything to show yet.