Join GitHub today
GitHub is home to over 31 million developers working together to host and review code, manage projects, and build software together.Sign up
Create overview of the PQ fork #1
We need to create a new README.md for this fork explaining the concept.
@maaku originally wrote describing the opportunity:
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)
My latest description of project:
Bulletproofs in SecQ
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.
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.
I would say “without parties revealing information that could cause the security or privacy of …"
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.
Replace “hideously inefficient” with “several orders of magnitude less efficient”
Extend “barely efficient enough” to “barely efficient enough to run on commodity signing hardware"
I incorporated the suggested changes in my draft.
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.
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.
referenced this issue
Aug 14, 2018
@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?
@sipa and I are currently working on this... The idea with the two Pedersen hashes has multiple serious issues:
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.