Zero-Knowledge Key-Statement Proof

Zero-Knowledge Key-Statement Proof

As we have introduced before, a zero-knowledge proof lets one party convince another party that he knows a secret validating a statement, whilst not revealing the secret.

Key Statement with Hashing
  1. ZKKSP does not require a trusted setup, an issue that some (e.g. pairing based) zk-SNARKS suffers from.
  2. Key-statement proof in zk-SNARKS requires an elliptic curve multiplication circuit, resulting in extremely computationally demanding proof generation and excessively large proving key on the prover side. By contrast, ZKKSP removes the circuit by:
  • Working in the same ECDSA elliptic curve than the public key is in
  • Checking consistency between the public key and the generated zk-proof; specifically, checking consistency against commitments embedded in the zk-proof¹.
Figure 1: schematic of a composite circuit for statement 1 in zk-SNARKS²
Figure 2: schematic of a composite circuit for statement 1 in ZKKSP³

Implementation

We fork an existing library called ZoKrates to generate the arithmetic circuit for SHA256. After modifying the circuit format, we implement the rest of key-statement proof as laid out in the white paper.

ZoKrates

ZoKrates⁴ is a toolbox for zkSNARKs on Ethereum. It consists of a domain-specific language, a compiler, and generators for proofs and verification smart contracts. Below is a source program written in ZoKrates that checks sha256(preimage) == h⁵.

sha256.zok: verify sha256(preimage) == h in zokrate

Workflow

The prover runs the following commands sequentially to generate a proof.

Prover generates a proof
Verifier validates a proof

Application: Outsourced Vanity Address Generation

This section describes applying ZKKSP to outsourcing bitcoin vanity address generation.

Bitcoin mainnet address with vanity pattern “nChain”

Summary

We have shown how to prove key statement, in which the secret private key hashes to a given value. While primitive at first glance, ZKKSP is extremely powerful to enable many atomic fair exchanges in two general steps:

  1. Seller proves to buyer using ZKKSP that he knows a secret the latter needs and it hashes to a given value;
  2. The buyer sets up a smart contract that only pays out if the hash preimage is given.

Acknowledgements

This is a joint work between nChain Limited and sCrypt Inc.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
sCrypt

sCrypt

sCrypt (https://scrypt.io) is a company with a mission to provide integrated on-chain smart contracting solutions on Bitcoin SV