**Workshop \#4 -- Home Edition**

# ZkpComRef: Diagrams and Illustrations

Please start by reading the [**editorial disclaimer**](https://hackmd.io/@workshop4/zcr-disclaimer) to ensure proper expectations about the process.

## Collaboration Instructions

**Context.** This page was prepared for a breakout session of the [ZKProof 4th workshop](https://zkproof.org/events/workshop4/). The page can be concurrently/collaboratively edited.

**Goal.** Collect suggestions/sketches for visual material (diagrams, illustrations and other figures) to add to the [ZkpComRef](https://docs.zkproof.org/pages/reference/reference.pdf). 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.**
:::success
**Email confirmation:** Once finishing your contributions, please send a brief email to [e-mail] 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](https://www.w3.org/WAI/tutorials/images/) 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](https://miro.com/app/board/o9J_lJQRFxQ=/?moveToWidget=3074457357801908784&cot=14), 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](https://community.zkproof.org/t/zkproof-2019-speaker-slides/167), [3rd workshop](https://community.zkproof.org/t/3rd-workshop-slides-and-notes/458/2), [4th workshop](https://community.zkproof.org/t/4th-workshop-slides-and-notes/560)

:::warning
**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 : [name=Luís Brandão]

**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](https://zkproof.org/2020/08/12/information-theoretic-proof-systems/) and further feeback by Yuval Ishai.
- **Suggested location in the [ZkpComRef](https://docs.zkproof.org/pages/reference/reference.pdf):** 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

:::danger
**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](https://docs.zkproof.org/pages/reference/reference.pdf):** \<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 : [name=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](https://doi.org/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](https://docs.zkproof.org/pages/reference/reference.pdf):** 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 : [name=Anaïs Querol [e-mail]]

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](https://docs.zkproof.org/pages/reference/reference.pdf):** \<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](https://docs.zkproof.org/pages/reference/reference.pdf):** \<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 : [name=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](https://docs.zkproof.org/pages/reference/reference.pdf):** 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 : [name=Thomas Kerber][name=Kimberlee Model ([e-mail])]

- **Image:** Not yet available
- **Source and acknowledgments:** https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649
- **Suggested location in the [ZkpComRef](https://docs.zkproof.org/pages/reference/reference.pdf):** 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.


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 : [name=Thomas Kerber]

- **Image:** 
- **Source and acknowledgments:** https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649
- **Suggested location in the [ZkpComRef](https://docs.zkproof.org/pages/reference/reference.pdf):** 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 : [name=Thomas Kerber]

- **Suggested location in the [ZkpComRef](https://docs.zkproof.org/pages/reference/reference.pdf):** 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. [name=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 : [name=Anaïs Querol [e-mail]]
>[name=Luís Brandão]
>[name=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](https://docs.zkproof.org/pages/reference/reference.pdf):** 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](https://docs.zkproof.org/pages/reference/reference.pdf):** 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 : [name=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](https://doi.org/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](https://docs.zkproof.org/pages/reference/reference.pdf):** 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)


___

___

## Suggestion 11: Prover - Verifier interactions, also depicting witness, statement and instance
>Suggested by : [name=Varios]

Note: feel free to add here various links/examples.
- [LegoSNARK slide 2 @ 2nd ZKProof workshop](http://www.dariofiore.it/wp-content/uploads/LegoSNARK-slides-ZKP.pdf)

**(copy-paste here the template)**

__

## Suggestion 12: Unified Theme for diagrams
>Suggested by :

- Suggestion/question: to which extent should we try to ensure uniformity of style?

## Suggestion 13: \<Title Here\>
>Suggested by : [name=your names here]

**(copy-paste here the template)**

___

## Suggestion 14: \<Title Here\>
>Suggested by : [name=your names here]

**(copy-paste here the template)**

___

## Suggestion 15: \<Title Here\>
>Suggested by : [name=your names here]

**(copy-paste here the template)**

___

## Suggestion 16: \<Title Here\>
>Suggested by : [name=your names here]

**(copy-paste here the template)**

___

## Suggestion 17: \<Title Here\>
>Suggested by : [name=your names here]

**(copy-paste here the template)**

___

## Suggestion 18: \<Title Here\>
>Suggested by : [name=your names here]

**(copy-paste here the template)**

___

## Suggestion 19: \<Title Here\>
>Suggested by : [name=your names here]

**(copy-paste here the template)**

___

## Suggestion 20: \<Title Here\>
>Suggested by : [name=your names here]

**(copy-paste here the template)**

---

**Add more placeholders as need be**