Workshop #4 – Home Edition

ZkpComRef: Diagrams and Illustrations

Please start by reading the editorial disclaimer to ensure proper expectations about the process.

Collaboration Instructions

Context. This page was prepared for a breakout session of the ZKProof 4th workshop. The page can be concurrently/collaboratively edited.

Goal. Collect suggestions/sketches for visual material (diagrams, illustrations and other figures) to add to the ZkpComRef. The suggestions can include:

Embeding sketch/draft diagrams, illustrations or other figures.
Providing links/URLs to existing images, including slide presentations
Describe in which sections the ZkpComRef would benefit from a new image

Add your contribution.

Email confirmation: Once finishing your contributions, please send a brief email to editors@zkproof.org to confirm your suggestion (mention the suggestion number and title).

New suggestions: See "Suggestion 0" as an example. Using the "Suggestion X" section in bottom of this page, add as many suggestions as you'd like.
Elements to include: Make sure to include:
- Your name: in "Suggested by <your name(s)>"
- Image: when available, embed an image; it's okay to be only a sketch or screenshot.
- Caption: a very short title below the inserted image (if applicable).
- Suggested destination: Where it would best fit inside the ZkpComRef
- Source and acknowledgments: authors, doi/ref or URL, contributors, other acks.
- Legend: a succinct explanation of symbols, acronyms and other elements.
- Explanation: A (possibly lengthy) explanation of what the figure describes. This may be useful for improved accessibility of the ZkpComRef.
Example sources: Presentation slides (provide URL, slide #); articles (provide doi and/or URL and Figure #); your own artwork (for example, you can draw a sketch illustration in Miro, using password zkproof4miro).
Image embedding: When possible, embed an image in your suggestion section. However, even without an image, an already useful contribution is the simple identification of concepts/examples/sections in the ZkpComRef that would benefit from a new image. You can also show a related image and then suggest the changes it should suffer for better integration in the ZkpComRef.
Suggested search: (among other locations), consider searching through the slide-decks of previous workshops: 2nd workshop, 3rd workshop, 4th workshop

Attribution: It is important that the source of the image be identified, to allow later confirmation that it can be added to the "CC-BY 4.0" licensed ZkpComRef. Als, note that when considering an integration in the ZkpComRef, the suggested images may be heavily adapted.

Example topics for illustrations/diagrams:

relation between ZKProof elements (prover, verifier, statement, witness, language, relation);
circuit representation;
R1CS representation;
ZK security game;
soundness/extractor game;
one of each IT proof system types or subtypes;
one of each type of cryptographic compiler;
backends and frontends;
gadgets: commitment, polynomial commitment, …
each described application;
… any other concept.

Image format:

In this page: An inclusion in .PNG can be easily accomplished by a simply drag-and-drop of the file (which will automatically upload it to imgur.com and then add code to show the image).
By reference or email: The contributed images can be in any format, including raster (png, jpg, …), vectorial (svg, psd, PGF/TikZ, …) and embedded in slides (pptx, odp, pdf, …).
End format: The end format (possibly upon conversion by the editors) for inclusion in the ZkpComRef will be vectorial whenever suitable.

Suggestion 0: Mindmap of IT proof systems

Suggested by : Luís Brandão

Mindmap of IT proofs
Figure X: Various Information Theoretic proof systems

Source and acknowledgments: Mindmap produced by the ZKProof editors, based on the taxonomy described in a blog-post and further feeback by Yuval Ishai.
Suggested location in the ZkpComRef: Chapter "2. Paradigms".
Legend: Fast RS IOPP (aka FRI: Fast Reed-Solomon IOP of Proximity); ILC (Ideal Linear Commitment); IOP (Interactive Oracle Proof); IP (Interactive Proof); IT (Information Theoretic); MPC ([Secure] Multi-Party Computation); PCP (Probabilistically Checkable Proof); QAP (QuadraticArithmetic Program); QSP (Quadratic Span Program); SSP (Square Span Program); ZKP (Zero-Knowledge Proof).
Description: Mindmap diagram, showing various types of IT proof systems suitable for ZKPs. Each node in level 1 is a major paradigm: PCP, MPC-in-the-head, IOP, Linear PCP, Linear IOP, ILC. Various major types can have various sub-tyes, represented as nodes in level 2. Dashed connections represent some type of relation (to later be explained in the ZkpComRef text).

–
Anyone add here additional comments about this suggestion:

Name 1: <some suggestions of what could be better>
Name 2: <some other suggestion of what could be better>
…

Suggestion xx: TEMPLATE

Do not edit or delete this template; instead, copy-paste its content inside one of the available suggestion placeholders below, and then edit it there.

Note: a drag-and-drop of a PNG image here will automatically uploaded it to imgur.com and embed it using markdown code like: ![](<URL here> =400x)

[Embeded image here]
<Insert caption here>

Source and acknowledgments: <names; doi/ref or/and url; acks>
Suggested location in the ZkpComRef: <section x.y>
Legend: <explain any acronyms and symbols>
Description (for accessibility): <detailed explanation of the content>

Suggestion 1: Classic "Cave" explanation of ZKP

Suggested by : Luis Brandao

Note: Consider other possibility of classic explanations about ZKPs
Image:
Proposed title: The ZK Cave
Source: DOI:10.1007/0-387-34805-0_60 –- "How to Explain Zero-Knowledge Protocols to Your Children. Quisquater et al. (1989)
Suggested location in the ZkpComRef: Section 1.1 (Introduction): .
Required complement: In written text, explain the game of asking the thief to come out by a random side. Then associate the concept of ZK to the simulatability in case one would know the key between the two sides of the cave.
Legend/explanation: …
Description: …

Suggestion 2: Many things

Suggested by : Anaïs Querol anais.querol@imdea.org

A collection of many concepts, will be moved to the best suited section.

Roots of unity graphical description

Source and acknowledgments: Vitalik Buterin https://vitalik.ca/general/2018/07/21/starks_part_3.html
Suggested location in the ZkpComRef: <section x.y>
Legend: The balls are the elements of a group G of order 64. The larger ones are also elements of a subgroup H of order 8.
Description (for accessibility): The figure shows a multiplicative group G of order 64 and a subgroup H of order 8. Let g be the generator of G and h the generator of H, then g^8 = h^1.

Polynomials involved in STARKs

Source and acknowledgments: Vitalik Buterin https://vitalik.ca/general/2018/07/21/starks_part_3.html
Suggested location in the ZkpComRef: <section x.y>
Legend: : purple=trace polynomial P, green=interpolant I, red=P-I, yellow=vanishing, pink= quotient
Description (for accessibility): This is an example of how the polynomials involved in STARKs look like. The goal is to prove that a certain computation equals an initial value (y_ini) on the first step and a final value (y_ini) on the last step. Say there are 64 steps, then we define a group G of order 64 and use its roots of unity to evaluate polynomials. We use the purple polynomial P that describes the computation for each of its 64 steps, so among others, P(1)=y_ini and P(g^63)=y_fin. Then the green line is the interpolant, the lowest degree polynomial such that I(1)=y_ini and I(g^63)=y_fin. In red we show P-I, so it has some of its roots in 1 and g^63. We define a vanishing polynomial (yellow), the lowest degree polynomial that equals 0 in 1 and g^63, that is (x-1)(x-g^63). Note P-I also vanishes on those points, so it must be a multiple of the vanishing. If we could prove this, then we would be proving that the trace polynomial equals y_ini at the beginning and y_fin at the end. So we provide the quotient polynomial (pink) P-I/vanishing.

R1CS example
From PPIO https://medium.com/@ppio/zksnarks-zero-knowledge-proof-feb76bf49e1a

SNARK timeline up to 2018
By Anca Nitulescu (another version of https://www.di.ens.fr/~nitulesc/files/Survey-SNARKs.pdf)

∑ protocol
A diagram that shows the ∑ shape of the communication
By Benny Pinkas https://www.youtube.com/watch?v=XT1Pad0DM24

Complexity classes
By Alon Rosen

By wikipedia https://en.wikipedia.org/wiki/Complexity_class

Fiat Shamir transform
By Ron Rothblum

By

Merkle tree Very visual
By https://amisafe.secops.in/merkletree-in-blockchain/

Also by https://twitter.com/KomodoPlatform/status/1022452858678128641/photo/1

Commitment schemes
By Teemu Kanstrén https://medium.com/coinmonks/zero-knowledge-proofs-um-what-a092f0ee9f28

Suggestion 3: IT proof systems (one image for each)

Suggested by : Luís Brandão

Source and acknowledgments: Elette's slides presented at the 4th ZKProof workshop contain variuos images that differentiate between IT systems (PCP, linear PCP, IOP, …). Find other presentations for missing slides.
Title: Each image's title will be the corresponding system type ("Probabilistic Checkable Proof", "Interactive Oracle Proof", …)
At least 5 images of main types: PCP, IOP, Linear PCP, Linear IOP, ILC
At least 13 images of sub-types:
- PCP: classic 3-col ZKP, PCP theorem;
- IOP: Interactive PCP, Fast RS IOPP (IOP of proximity);
- Linear IOP: polynomial IOP; fully-linear IOP, IP-based;
- Linear PCP: Hadamard based; from QAP; from QSP; from SSP; Line-point; fully-linear PCP
Suggested location in the ZkpComRef: Upcoming Section 2.2 (Paradigms / IT proof systems)
Legend: Each image would have a caption similar to the IT proof system it represents
Description:

Suggestion 4: Simple Arithmetic Circuit

Suggested by : Thomas KerberKimberlee Model (kimee@stealthsoftwareinc.com)

Image: Not yet available
Source and acknowledgments: https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649
Suggested location in the ZkpComRef: Section 1.3.1
Legend: <explain any acronyms and symbols>
Description (for accessibility): An Arithmetic circuit representation (i.e. addition and multiplication gates) of the function 'x + x^3 + 5'.
Here is an example circuit for "proof of right triangle". This uses arithmetic gates and the Pythagorean Theorem to show that the prover knows side lengths for a right triangle. Optionally, the hypotenuse could be known by the verifier, and the prover must provide the legs. I've also added the graphviz code which I used to generate the graph.

right triangle circuit

digraph
{
  rankdir=LR;

  leg_a[label="input: leg A"];
  leg_b[label="input: leg B"];
  hypot[label="input: hypotenuse C"];

  neg_1[label="constant: -1"];

  a_2[label="multiply: a^2"];
  b_2[label="multiply: b^2"];
  c_2[label="multiply: c^2"];
  a2_b2[label="add: a^2 + b^2"];
  neg_c2[label="multiply: c^2 * -1"];
  a2b2_sub_c2[label="add: (a^2 + b^2) + (-c^2)"];
  eqz[label="equals zero?"];

  leg_a -> a_2;
  leg_a -> a_2;

  leg_b -> b_2;
  leg_b -> b_2;

  hypot -> c_2;
  hypot -> c_2;

  a_2 -> a2_b2;
  b_2 -> a2_b2;
  c_2 -> neg_c2;
  neg_1 -> neg_c2;

  a2_b2 -> a2b2_sub_c2;
  neg_c2 -> a2b2_sub_c2;
  a2b2_sub_c2 -> eqz;
}

Suggestion 5: R1CS Matrix Representation of Example Arithmetic Circuit

Suggested by : Thomas Kerber

Image:
Source and acknowledgments: https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649
Suggested location in the ZkpComRef: Section 1.3.2
Legend: A, B, and C loosly correspond to the vectors a, b, and c used in reference. Note that constraint vectors and solution vector are flipped versus how they are presented in the reference.
Description (for accessibility): An Arithmetic circuit representation (i.e. addition and multiplication gates) of the function 'x + x^3 + 5'.

Suggestion 6: Visualation of Interaction between (interactive) Prove/Verify Algorithms

Suggested by : Thomas Kerber

Suggested location in the ZkpComRef: Section 1.5
Legend: <explain any acronyms and symbols>
Description (for accessibility): <detailed explanation of the content>

Also recursive composition. See Nick Spooner's excellent illustrations in his "Proofs of proofs: incremental verifiability from recursion and accumulation" slides. Eran Tromer

Suggestion 7: Example nuclear disarmament

Suggested by :Stephen Holmes

(copy-paste here the template)
https://www.nature.com/articles/nature13457.pdf

Suggestion 8: Classical examples

Suggested by : Anaïs Querol anais.querol@imdea.org
Luís Brandão
Stephen Holmes

Here the idea is to provide classical or "real world" examples of zero knowledge proofs or proofs of knowledge to help a wider public grasp the concept. There are a variety of them that could suit different types of audiences depending on their background in math and the scenario: not the same if drinking at the pub or convincing a client. Feel free to add attributions to the original authors.

Where is Waldo

Source and acknowledgments: Design by Nicole Zhu, example by ?
https://blog.goodaudience.com/understanding-zero-knowledge-proofs-through-simple-examples-df673f796d99
Suggested location in the ZkpComRef: 1.1.1 What is a zero knowledge proof?
Legend: Alice wants to convince Bob that she know's where Waldo keeping the location secret.
Description (for accessibility): Alice and Bob share a "Where's Waldo" picture. She wants to convince Bob that she knows Waldo's location without giving him a single hint of where. For this, she brings a huge blank, opaque paper that (at least) doubles the dimensions of the original picture. Then she cuts right in the middle Waldo's silhouette and uses this mask on top of the picture. Then, Bob will be able to check Alice knew where Waldo was, but has no clue about where since the paper covers the whole picture.
Takeaways: This is an example of both ZKP and PoK. Level: easy, no math needed, can be performed.

Iterative distinction experiment And some of its variants
– Colorblind

Source and acknowledgments: Design by Nicole Zhu, example by ?
https://blog.goodaudience.com/understanding-zero-knowledge-proofs-through-simple-examples-df673f796d99
Suggested location in the ZkpComRef: 1.1.1 What is a zero knowledge proof?
Legend:
Description (for accessibility): .
Takeaways: This example gives the hint of a more powerful prover. This is an example of both ZKP and PoK, also interactive proofs. Level: easy but basic probability involved.

The zero-coke vs normal-coke / pepsi vs cocacola

The colorblind example (red ball vs green ball)

The Sudoku?
Proving you have more than x coins with "opaque" coin dispenser (by Dario Fiore, Matteo Campanelli and Anaïs Querol)
https://www.youtube.com/watch?v=U0Y5p9L475Y

Classic "Cave" explanation of ZKP

Suggested by : Luis Brandao

Note: Consider other possibility of classic explanations about ZKPs
Image:
Proposed title: The ZK Cave
Source: DOI:10.1007/0-387-34805-0_60 –- "How to Explain Zero-Knowledge Protocols to Your Children. Quisquater et al. (1989)
Suggested location in the ZkpComRef: Section 1.1 (Introduction): .
Required complement: In written text, explain the game of asking the thief to come out by a random side. Then associate the concept of ZK to the simulatability in case one would know the key between the two sides of the cave.
Legend/explanation: …
Description: …

Suggestion 9: Zero Knowledge Memes

Suggested by : Daniel Thomas

Combine contemporary images with language to communicate ideas beyond the capabilities of either in isolation.
ipfs -
ipfs -
Specific Zk implementation challenges.
Pure alpha ZKP application ideation

Suggestion 10: Blockchain mass txn validation

Suggested by : Stephen Holmes

(copy-paste here the template)![reference link]
https://www.slideshare.net/hellovista/scaling-ethereum-using-zeroknowledge-proofs
(https://i.imgur.com/EQONZzm.png)

___