This article first appeared on Medium.
The nChain # 0488 white paper titled “Evidence of zero-knowledge key declaration” introduces a zero-knowledge proof (ZKP) that proves that a private key, corresponding to a given public key, meets certain requirements, while maintaining the confidential private key. We implemented and applied it to buying a bitcoin vanity address with confidence. It can be generalized to a wide range of applications, where secret information can be bought between mutually suspicious parties without a trusted third party.
Proof of unconscious key statement
As we discussed earlier, zero-knowledge proof allows one party to convince another party that they know a secret validating a statement, while not revealing the secret.
A zero-knowledge proof of key statement (ZKKSP) is a special type of ZKP where the secret is a private key corresponding to a known public key. The private key satisfies additional constraints, such as hashing at a given value.
The nChain white paper presents an effective approach for ZKKSP. Compared to zero-knowledge evidence for general statements such as zk-SNARKS, ZKKSP has several salient advantages:
- ZKKSP does not require a trust setup, an issue that some zk-SNARKS (eg, pairing-based) suffer from.
- The key statement proof in zk-SNARKS requires an elliptical curve multiplication circuit, resulting in extremely computationally demanding proof generation and excessively large proof size on the prover side. On the other hand, ZKKSP removes the circuit by:
- Work in the same ECDSA elliptical curve that the public key is in
- Checking the consistency between the public key and the generated zk-proof; in particular, check consistency with the commitments integrated into the zk-proof¹.
In ZKP, a statement / calculation is usually encoded in an arithmetic circuit, consisting of addition and multiplication gates. As shown in Figure 1, zk-SNARKS contains subcircuits for a hash function and elliptic curve multiplication. The last circuit checks the consistency against the known ECDSA public key. ZKKSP only uses the hash circuit and removes the other circuit, which is at least an order of magnitude larger than the first one. Interested readers can refer to the white paper for more details, which we are omitting here due to limited space.
We fork an existing library called ZoKrates to generate the arithmetic circuit for SHA256. After changing the circuit format, we implement the rest of the key instruction proof as shown in the white paper.
ZoKrates⁴ is a toolkit for zkSNARKs on Ethereum. It consists of a domain-specific language, a compiler, and proof generators and smart verification contracts. Below is a source program written in ZoKrates which verifies sha256 (preimage) == h.
The Prover executes the following commands sequentially to generate a proof.
The prover sends the generated proof in proof.json to the auditor. The verifier runs the following command to verify if the public key matches the hash value. Note that this proof is non-interactive and does not require interaction between the prover and the verifier, thanks to the Fiat-Shamir heuristic.
You can find the full code on our Github.
Application: Generation of outsourced vanity addresses
This section describes the application of ZKKSP to the outsourcing of Bitcoin custom address generation.
Since the search for a custom address can be computationally expensive, it is common for the search to be outsourced. Traditionally, either the buyer gets the required value before the seller gets paid, or the seller gets paid before they release the required value, or they both have to trust an escrow service. By using ZKKSP, selling a vanity address can be made without confidence.
The protocol for this is detailed as follows.
- The buyer and seller agree on the required vanity model and price (in BSV), and establish a communication channel (which does not need to be secure).
- The buyer generates a secure random secret key sk_Band the corresponding elliptic curve public key pk_B = sk_B * G
- Buyer send pk_B to the salesman.
- The seller then performs a search for the required model in the Base58 encoded address derived from pk = pk_B + i * Gchanging I.
- When an address with the required pattern is found, the seller records the value, reports to the buyer and sends it pk_S = i * Gand the SHA256 hash.
- The seller also provides a ZKKSP to the buyer whose pre-image is the private key corresponding to pk_S.
- The buyer checks the proof, and also confirms that the address pk = pk_B + pk_Scorresponding to corresponds to the agreed model. At this stage (by virtue of the evidence), the buyer knows than learning to value I will allow it to derive the full private key from the personal address (sk_B + I), and that particular value is hashed for h = H (i).
- The buyer then constructs a hash-time contract (HTLC) transaction Tx_1which contains an output which contains the agreed charges. This output can be unlocked in two ways:
I. With a seller’s signature and the hash pre-image, I, at any time.
ii. With a signature of the buyer after a specified period (OP_CLTV⁶)
- The buyer then signs and broadcasts this transaction to the blockchain, where it is extracted in bulk.
- Once confirmed, the seller can claim the outgoing charge Tx_1 by providing a transaction Tx_2 providing their signature and value Ito unlock the hash-lock, which is then revealed on the blockchain.
- The buyer calculates the private key of the final vanity address sk = sk_B + i, or pk = sk * G
- If the seller does not provide the value Ibefore a specified OP_CLTV time, the buyer can then provide their signature to collect the charge (to prevent the charge from being lost due to an uncooperative buyer).
The exchange is fully atomic and trustless, meaning the buyer is only paid if they provide a valid secret value ?? which is publicly revealed on the blockchain. Moreover, the full private key is not even known to the seller, due to the split of the private key.
We have shown how to prove a key statement, in which the secret private key is hashed to a given value. Although primitive at first glance, ZKKSP is extremely powerful in enabling many fair atomic exchanges in two general steps:
- The seller proves to the buyer by using ZKKSP that he knows a secret that the latter needs and hashes at a given value;
- The buyer sets up a smart contract that only pays if the hash pre-image is provided.
Note that step 1 is complete off-chain and can be computationally intensive, while step 2 is on chain and extremely light.
The same technique can be applied to require the private key to meet other requirements (i.e. circuits), such as the start or end of a given pattern.
 These can be achieved either with a non-succinct proof system for circuit satisfiability, or with a SNARK based on a discrete log. We implemented the first one.
 Internal gates are for illustration purposes only – real circuits would have thousands of gates.
 The circuit verifies that the output of the hash is equal to the public key EC: the values highlighted in blue are revealed to the verifier, all other values are encrypted.
 ZoKrates Scalable Off-Chain Calculations to Protect Privacy, 2018
 The two preimage and h are divided into two parts, since the basic type field cannot accommodate 256 bits.
 “OP_CLTV” on BSV
This is a joint work between nChain Limited and sCrypt Inc.
Watch: Introducing CoinGeek New York, Kensei: the Gateway to the Definitive Blockchain
New to Bitcoin? Discover CoinGeek Bitcoin for beginners section, the ultimate resource guide to learning more about Bitcoin — as originally envisioned by Satoshi Nakamoto — and blockchain.