LinkG16 and Its Role in zk-creds

zk-creds: Anonymous Credentials with zkSNARKs and NFC

zk-creds is a protocol that outlines a strategy for utilizing zero-knowledge proofs (zkSNARKs) alongside existing identity infrastructure to enhance identity verification. By leveraging the Near Field Communication (NFC) chips embedded in U.S. passports, zk-creds uses the embedded digital signatures to ensure data integrity and authentication.

The protocol operates by extracting key data from the NFC-readable chips, such as specific attributes and their associated digital signatures. This data is then converted into a credential that can be used for identity verification. The key advantage of zk-creds is its ability to authenticate user attributes without disclosing unnecessary information.

Through zk-creds, users can present zero-knowledge proofs that are verified against their original passport, enabling secure and efficient identity verification while preserving the privacy of sensitive information.

How zk-creds Works: Step-by-Step

1. Request Credential: Users initiate the process by scanning their passports, which extracts essential data. This data is formatted into a credential, a Pedersen commitment of attributes, and sent to an issuer.
2. Issue Credential: The issuer verifies the data and issues zk-creds by adding it to a Merkle tree. The Merkle authentication path is returned to the user as their credential.
3. Show Credential: The holder uses the show function with their zk-creds to generate proofs such as birth, expiry, and membership proof.
4. Verify Show: The verifier checks the validity of the proofs, ensuring the user meets some access criteria.

Diagram 1: Issue, Show, Verify Flow

Example Scenario

Imagine a website with a minimum age requirement of 21 years. Using zk-creds, a user can employ their credential to verify their age without disclosing additional personal details. The ‘show function’ generates three proofs:

1. Birth Proof: This proof confirms the user’s age, validating their eligibility.
2. Expiration Proof: This proof ensures that the credential is still in effect and can be used.
3. Membership Proof: This proof verifies that the credential belongs to a specific Merkle tree, proving it has been issued.

The magic happens when we combine a membership proof with access proofs and introduce reusing computed proofs without sacrificing privacy with linkage and blind Groth16 proofs.

Diagram 2: Link Groth16 Example

zk-creds uses the LinkG16 function, which facilitates the validation of a set of Groth16 proofs while preserving their privacy. In the context of zk-creds, this means proofs can be generated independently yet authenticated as coming from the same credential.

The Building Blocks of LinkG16

To fully appreciate and better understand the workings of LinkG16, we first need to explore Groth16, the zero-knowledge proof underpinning the architecture of zk-creds. This zero-knowledge proof scheme is the basis for LinkG16.

Basics of Groth16

1. Convert the questions into a circuit
2. Compile the circuit into the form of Rank-1 Constraint Systems (R1CS).
3. Convert R1CS to Quadratic Arithmetic Program (QAP) format
4. Set up a trusted setup, and generate random parameters, including proving key (PK) and verifying key (VK).
5. Proof generation and verification of zk-SNARK

Diagram 3: Groth16 Flow

Trusted Setup Phase

G16.Setup(bg, desc) → crs: Creates a CRS for a given arithmetic circuit description and bilinear group.

The Groth16 protocol begins with a trusted setup phase, where a Quadratic Arithmetic Program (QAP) representing the computation is generated. During this phase, two essential keys are derived: the proving key, enabling proof generation, and the verification key, facilitating proof verification. This setup phase creates a common reference string (CRS), which acts as a “public key” for creating and verifying proofs.

The Common Reference String (CRS) generated during the setup phase acts as a shared cryptographic parameter and incorporates the proof generation and verification requirements.

Proving Phase

G16.Prove(crs, x, w) → π: Validates that the circuit described by the CRS is satisfied, using x as the public inputs and w as the witnesses.

Using the proving key and private input (witness), the prover executes the proving algorithm to generate a zk-SNARK proof. This proof demonstrates the knowledge of a valid witness that satisfies the computation.

Verification Phase

G16.Verify(crs, π, x) → {0, 1}: Verifies the proof π in relation to the provided public inputs. It returns 1 if the proof is valid, and 0 otherwise.

The verifier uses the verification key, public input, and the proof to verify its validity. The verifier evaluates and confirms the proof's integrity. Acceptance or rejection of the proof is determined based on the validity of this equation.

LinkG16

https://eprint.iacr.org/2022/878.pdf

Groth16 lays the foundation for the construction of a “combined” zero-knowledge proof. A Groth16 linkage proof combines proofs while Blind Groth16 makes it possible to reuse computed proofs without breaking privacy. LinkG16 helps developers avoid managing dynamic circuit parameters or defining all the tools needed in advance. Proof compositions can be built and defined “on-the-fly”, making the system flexible and adaptable.

This allows new proofs to be introduced, linked, and validated without exposing the individual elements of Groth16 proofs or the linked public inputs. Essentially, LinkG16 proof acts like a master key, offering adaptability and making the system more robust and able to meet evolving needs.

Concretely, Blind Groth16 lets us prove that a number of Groth16 proofs are all made with respect to the same credential without revealing the credential.
- Rosenberg, White, Garman, Miers

Constructing and Verifying Linked Proofs

Let’s break down the LinkG16 and LinkVerifyG16 from above. In the proving process, we initially blind each proof. Following this, a new proof is assembled that demonstrates all the original proofs are based on the same private values.

LinkG16.Link(x, {crsi, πi}) → πlink

This function takes a private input x, a set of Groth16 Common Reference Strings (CRSs, represented by crsi), and proofs (πi). It assembles a zero-knowledge proof, linking these inputs together. The output of this function is πlink, a zero-knowledge proof that all πi align with their respective CRSs.

LinkG16.LinkVerify(πlink, {crsi, xi}) → {0, 1}

This function verifies the zero-knowledge proof πlink in relation to the provided public inputs {crsi, xi}. It returns 1 if the proof is consistent, validating that the proof πlink matches with the CRSs and public inputs, and 0 otherwise. This function is similar to G16.Verify, but in the context of the LinkG16 proof system, by applying it to a set of proofs.

LinkG16 offers an innovative way to integrate a membership proof with multiple access proofs in zk-creds, as illustrated in Diagram 2. The composability is especially useful since the membership proof, being the most resource-intensive part of ShowCred, can be reused without compromising privacy. The strategy enables users to build complex combinations of proofs to adapt to evolving requirements.

Conclusion

zk-creds is an innovative approach on privacy-preserving identity verification using zero-knowledge proofs and Near Field Communication (NFC) embedded chips in U.S. passports. Leveraging Groth16 zk-creds provides a secure way to extract and authenticate essential data without over sharing. The key to its functionality lies in the LinkG16 protocol, which allows multiple Groth16 proofs to be linked and verified together while ensuring the privacy of individual proof elements.