Introduction

Welcome to the wiki on

• programmable cryptography
• and advanced decentralisation technologies
• for novel, emergent applications

Why Wiki

1. A single channel to surface projects, tools, and resources related to the above intersections.
2. Education on how these technologies may be used to build novel applications.
3. Coverage on emergent use cases for these technologies.

We use the computational framework from SoK: Programmable Privacy in Distributed Systems to organize the structure of applications and associated technologies.

Contact

The Knot Group is headed by Goblin Oats, grjte and their friends. If you are a friend of a friend and would like to get in touch with us then please reach out to Tonk.

Building applications

Resilient application engineering depends on a shared knowledge base of design patterns that guide development at all levels of the system and software architecture stack. As design patterns have been established for web 2.0 applications, an ecosystem of modular software services has grown to help developers manage and isolate the complexities of different requirements, from auth to databases to hosting and serving applications.

The world of programmable cryptography is just beginning to open, which means that design patterns for leveraging these cryptographic tools haven't been discovered or established yet, and there are limited services or tools available to support non-cryptographers in building applications that make use of programmable cryptography.

A major goal of this wiki is to provide a reference for existing patterns and tools and to help guide the discussion and discovery of what is needed.

A framework for thinking about programmable cryptography

We can think about application design that leverages programmable cryptography in terms of the affordances that programmable cryptography enables, the interactivity requirements between actors in the system, and how private data is shared and managed.

We use the computation framework introduced in the Programmable Privacy SoK, which noted that existing applications with programmable privacy have 3 phases of computation: independent, mediated, and global.

• Independent computation is performed by a single entity and depends on input data that is either public or private but known to that entity (personal private data)
• Mediated computation is used when private data from multiple sources must interact or be combined without being revealed.
• Global computation uses public data in decentralized computation, such as on a blockchain or in a peer-to-peer system.

For our purposes, we prefer to think of these as separate building blocks which may or may not be used in any given application and which do not have strict temporal requirements. In other words, while many applications will begin with an independent computation phase, continue to mediated computation, and end with global computation, others might finish with independent computation or use only 1 of these 3 types. As tools become more robust and applications become more complex, the variety of ways in which these building blocks are combined will increase.

Finally, to this framework we add our final building block: attestations, also known as attested or verifiable data. While some applications will not require input data to be attested to, many more will, which means that we need to understand (and expand) the available sources of attestations and have good tools for manipulating them.

Attestations (verifiable claims)

Attestations are verifiable claims which consist of a statement and a cryptographic proof of that statement. Examples include biometric passports which are cryptographically signed by the issuing government, emails with DKIM signatures by the sending server, claims of group membership with accompanying Merkle inclusion proofs, and computation outputs with accompanying zero-knowledge proofs.

Attestations can be claims about:

• identity, such as birthdate or citizenship, attested by signed government-issued ID
• social facts, such as group membership attested a Merkle proof of inclusion, or network connections attested by signed claims from members of the network
• ownership, such possession of an NFT (attested on-chain) or a house (attested by a digitally signed PDF)
• historical activity

The main challenges with attestations are:

• How to produce new attestations permissionlessly. For example, ZK Email can be used to produce an attestation to ownership of a specific social media handle.
• How to consume attestations permissionlessly. For example, an application requiring a user to be over 18 must verify the attestation before trusting the claim.
• How to transform existing attestations into a more usable or redacted form. For example, an application requiring users to be over 18 should not need to read and verify a signed biometric passport.
• How to compose multiple attestations together into a single attestation that meets the requirements of an application. For example, an application may require membership in a specific group in addition to the over 18 age requirement, and these requirements should still be attested in a single proof.
• How to make them portable across systems, platforms, networks, and computing environments

There is currently no generic widely-used framework for how attestations are produced, consumed, transformed, or composed. The closest existing solution is possibly the Proof-Carrying Data SDK, which can be used by any third-party as long as it provides a zkSNARK circuit for querying about its set of requirements.

Producing attestations

Attestations can be created in two ways:

1. A trusted source issues a new attestation, for example by cryptographically signing a claim, performing a verifiable computation (e.g. zk proof) that does not require verifiable inputs, or adding a person to a private membership group and issuing an inclusion proof. Sources of attestations can be anything from a government (electronic ID) to an individual to a device. We call attestations that rely directly on a trusted source "base" attestations.
2. A new attestation can also be created by transforming an existing attestation, for example by redacting or processing the original claim.

Consuming attestations

Applications consume attestations by verifying the associated cryptographic proof and then taking action based on the claim.

Consuming attestations is simple in the case of a single specific claim, but the question of how to consume attestations becomes more complex when thinking about a framework for composing attestations while maintaining portability across many systems and environments.

Transforming attestations

Attestations can be transformed by first consuming the attestation and then producing a new one using its claims, which can be done using zero-knowledge proofs.

Given a base attestation, the general transformation process is to verify the cryptographic proof of the base attestation (consume the attestation) and then compute the transformed claim from the base claim inside a zk circuit.

For example, ZK Email transforms (signed) emails into attestations to more specific claims that are contained in those emails by first verifying the email's DKIM signature, then proving that the transformed claim is contained in the email body and that the hashed email body is the same as the hash in the signed email header.

Composing attestations

There is no framework that we know of for composing attestations, so this can only be done by writing custom solutions. For example, a single user could combine multiple attestations using recurive zk proof composition. In theory, collaborative SNARKs could be used to combine attestations from multiple parties.

Portability

Because there is no well-defined framework for issuing, consuming, and manipulating attestations, they are not easily portable, and incorporating attestations into an application currently requires custom solutions, although the tools listed below reduce this workload in many cases.

References

• "Stuff with Signatures" by the Cursive Team
• "Thinking about Attestations" by gubsheep

Sources of base attestations

• Apple’s App Attest
• Camera Files
  • Content Credentials
• Credit Card Transactions via EMV
• Emails via DKIM signatures
• Ethereum Attestation Service, including:
  • Coinbase
  • Gitcoin Passport
  • Optimism Bedrock
  • and more…
• Git Commits
• Electronic ID:
  • Biometric Passports (ePassports)
  • Many government ID Cards:
    • A global list of countries with eID
    • EU Residence Cards for foreign nationals
    • eIDAS (future electronic id cards for EU citizens)
    • India (Aadhar)
    • Japan (My Number Card)
    • Taiwan
• Mobile App Data
• NFC Chips
• Onchain Data
• PDFs via Docusign
• Semaphore group membership
• ZK proofs attest to computation results

Tools for manipulating attestations (producing, transforming, consuming)

• Proof-Carrying Data SDK by the PCD Team
• Web proofs: by default, data received over TLS cannot be shared in a verifiable manner, but several projects aim to add a protocol on top of TLS to make the received data verifiable.
  • TLS Notary
  • Pluto
  • Reclaim Protocol
• zkEmail is a highly flexible tool to transform signed emails into attestations to specific claims contained within those emails.
• Gribi The Gribi interface allows for independent cryptosystems to more easily link together functionality without directly coordinating.

Computation framework

We find the computation framework developed in SoK: Programmable Privacy in Distributed Systems a helpful way to organize and think about the structure of these applications.

A summary of the framework via excerpts:

What is it?

Though it seems like there could be endless ways to fit these tools together, there turn out to be many similarities between practical designs. We propose a lightweight framework for describing the architectures of these systems with a three phase computational model for processing sensitive user inputs in batches.

Independent Computation

The first “Independent computation” phase is a local computation by individuals using a combination of public and personal private data. Zero-knowledge proofs and shielded pools are most useful here for user privacy, since users can generate proofs which reference data without revealing that data to a verifier.

Mediated Computation

Second, for functionalities that require aggregation, a privacy-preserving “Mediated computation” phase is executed by protocol operators on the combined user inputs of the batch. To ensure privacy in this phase, it is commonly necessary to incorporate an extra trust assumption in the security model, such as requiring that a quorum of key holders do not collude to decrypt more than they should, or that some secure hardware enclaves operating on confidential data have not been compromised.

Global Computation

Finally, in the “Global computation” phase, the output of the batch is registered and takes effect on the blockchain.

Independent Computation

Independent computation is done by a single entity which knows all input data, both public and private. Independent computation can be used to keep data private from other actors and other parts of an application's architecture. It can also be used for verifiability when

Zero-knowledge proofs

Zero-knowledge proofs (ZKPs) are the most powerful form of independent computation. They enable a Prover generate an output computed over private input data, which is accompanied by a proof of the correctness of the computation, all without ever revealing the private input. A Verifier can then run a quick verification of the proof to verify that the output data was computed as claimed. In other words, ZKPs transform secrets into attestations. For more background, see the definition and resources in the learning section.

Use in programmable cryptography

In programmable cryptography, ZKPs can serve several purposes:

• Transforming secrets into attestations: Zero-knowledge proofs can be used to transform private attestations into public attestations that can be shared or used in mediated and global computations. For example, a ZKP may redact data by proving that private data contains or implies a fact which can be made public.
• Producing attestations from unattested data: ZKPs can also be used to create an attestation from unattested data, either public or private. In this case, the zk proof is being used for its data integrity properties.
• Ensuring data integrity: ZKPs can be used to prove that data is well-formed. This is useful for ensuring the integrity of inputs to other computations (such as FHE) or for providing a verifiable proof that the output from another computation is well-formed.

On its own, ZK is a tool for manipulating attestations. When combined with other types of programmable cryptography, ZKPs are usually used to process inputs to mediated/global computation or to ensure the integrity and verifiability of outputs from mediated computations.

Caveats

Practical challenges & limitations

Mediated Computation

Mediated computation is used when a party's private data is computed over either collaboratively or by another entity. In other words, the holder of the private input data and the entity performing the computation are not the same. A variety of technologies can perform mediated computation over private data to achieve different purposes. These can also often be combined together or with independent computations, such as ZKPs, depending on the requirements of the application.

Fully Homomorphic Encryption (FHE)

Homomorphic Encryption is a cryptographic tool for performing computation over encrypted ciphertexts such that the decryption of the result is equivalent to the result which would be obtained by computing over the plaintext inputs. For more background, see the definition and resources in the learning section.

Use in programmable cryptography

FHE is useful for outsourcing private computation. A user with private data can encrypt it and share it. A remote entity computes over the ciphertext and sends back the result. The user decrypts the result, and the decrypted result of the FHE computation is the same as if the private data had been computed without encryption.

Caveats

• The output is revealed by decrypting it with the decryption key. Thus, the management of the private data is fundamentally a key-management problem. FHE can be combined with an MPC threshold signature scheme to distribute this risk.

Practical challenges & limitations

Secure Multi-Party Computation (MPC)

Secure Multi-Party Computation is collaborative computation over private inputs from multiple parties. It reveals the output to all parties, but keeps each party's input private from the other parties. For more background, see the definition and resources in the learning section.

Use in programmable cryptography

In programmable cryptography it can serve the purpose of:

• computing shared private state, such as managing the state of a game world that is affected by the secret actions of multiple players
• aggregating private inputs from multiple parties

Caveats

• The output is revealed to all participating parties, which can leak information about the private inputs. For example, in an auction where the winning bid is revealed, which can leak information about bidding patterns.
• Parties can collude, and this collusion is impossible to detect or punish, unless the effect of it is so obvious as to be socially noticeable

Practical challenges & limitations

MPC has high communication overhead and is network-bound. Thus, the number of peers, latency, and transmission rates can all lead to delays in computation execution.

It's feasible for networks with:

• limited peers
• low latency
• high transmission rates

Trusted Execution Environments (TEE)

Global Computation

Design Patterns

The following graphics illustrate various applications using the above framework outlined in this wiki. These design patterns are not meant to be exhaustive, but they do help us to generate examples which may ground our understanding.

ZKP2P

zkCreds

MACI

Resources

A growing repository of tools, platforms and products which are tailor made for building the applications concerned here in this wiki.

Tools

Tools are meant for a particular function and by themselves are incomplete. Tools are agnostic of how or where they are used.

Web Data Provenance

ZKML

Identity

ZKDSL

Platforms and Products

Platforms or products offer out of the box solutions and typically come with various built-in constraints about how and where they are used.

Programming languages, compilers, and VMs

FHE

MPC

ZK

Data Provenance

Web Data Provenance

Blockchain Data Provenance

Identity

Applications

An application is a program or piece of software designed to fulfil a particular purpose, but what is the purpose of an application that requires programmable cryptography and advanced decentralisation technologies?

As of today, we only have shallow answers to this question. What has been built or speculated on uses descriptive terms around the technology and features of the technology to describe their purpose:

• It's a protocol
• It gives you provenance and authenticity
• It's a cryptographically simulated server
• It lets you own your data
• It's a decentralized identity system

History tells us this phenomenon is present in every innovation cycle. It means we're in the early days!

Trust Infrastructure

The closest we have is a nascent term for an unknown portion of the application space carved out by programmable cryptography and advanced decentralisation technologies called Trust Infrastructure. This application space is motivated by a need to establish trust between people and systems.

What is Trust Infrastructure? Arnaud Schenk writes:

our goal should be to find ways to increase the surface area for trust building once again. We need new trust infrastructure, adapted to the world as it is.

That idea was expanded upon in a post by Baz, where trustless design and trustful design should both be considered under the umbrella of Trust Infrastructure.

The concept of Trust Infrastructure is undoubtedly inspired by Josh Stark's talk Atoms, Institutions, Blockchains or at the very least it's tapping the same insight.

Seeing the Elephant

Our goal in mapping the application space is to begin to chart the big why here and to identify the remaining gaps we must cross to fulfill the promise of these technologies. We are all seeing pieces of the puzzle, but the complete picture continues to elude.

Realized

Nosh Delivery

Decentralized Food Delivery Cooperative with bootstrapped reputation off existing sharing economy/social trust platforms.

Source

ThatsMe

Prove your identity on social media.

Source

Daisy

Find other influencers to work together on Instagram/TikTok advertising campaigns.

OP Stack RPGF

ZK circuits for Optimism RPGF allocator

Link to Repo

Speakeasy

Privately find and message your undiscovered peers.

Speakeasies are a special new type of private space on the web that you can join - not because you’re invited - but because you’re already qualified.

Source

Backpocket

An app using MPC (multi-party computation) for human connection. This includes discovering common interests, querying your connections, and visualizing communities formed through the Devcon PWA.

Source

Freedom Tool

Online voting systems are the most accessible way for people to participate in democracy, especially for those living under oppressive regimes. However, they typically lack transparency and are prone to Sybil and cyber attacks.

Rarimo has employed zero-knowledge cryptography to address these challenges and built Freedom Tool, a decentralized, transparent, and privacy-preserving online voting tool on blockchain.

Link to Repo

Ketl

ketl is a new exclusive anonymous app built for founders and vcs. Join over 500 of the top founders and vcs in the discussion today.

Link to Repo

Creddd

Creddd is a piece of your onchain reputation. It's created automatically whenever you do things onchain.

It shows, cryptographically, that you've done things you say you've done. It's privacy-preserving; you don't have to reveal your address to use your creddd.

Link to Repo

Postcard

ZK Attested Images and Proof of Location

Link to Repo Link to Repo

ZKP2P

ZKP2P is a trustless and privacy-preserving fiat-to-crypto onramp powered by ZK proofs. This (V2) repo is currently under active development. ZKP2P is currently live in Alpha which is a productionized version with audits and supporting Venmo, a popular P2P payment network in the US.

Link to Repo

ZKSummit 11 Cursive App

Every attendee will get an NFC card alongside their badge, and additional NFC cards will be placed in front of rooms where talks and workshops are held. Tapping another attendee's card allows you to see their contact information, as well as receive a digital signature that verifiably represents the fact that you met them. Tapping a card associated with a talk gives you a digital signature proving you attended that talk. There are 3 main things you can do with these signatures: make zero knowledge proofs, privately compute the things you've done in common with someone else, and aggregate the signatures into one big proof of your entire event experience - ZK Summit Folded!

Link to Repo

zkPoEX

zkPoEX (zk proof of exploit) is a Proof-of-Concept developed at ETH Denver Hackathon with the aim to facilitate communication and collaboration between security experts and teams in the decentralized finance (DeFi) space by enabling white hat hackers to report live vulnerabilities in smart contracts while maintaining the confidentiality of the exploit.

Link to Repo

RWA Verified On-Chain

Jiritsu is a cutting-edge Layer 1 blockchain with a native ZK-MPC oracle designed for real-world assets. May be realized, but the technology is proprietary.

Source

Theoretical Applications

Automated Docusign Escrow Service

Signing a document triggers an exchange of funds or goods. Cryptographic signatures as legally binding contracts.

Data Guilds

Anonymized, aggregate information about users’ interests and characteristics flows to advertisers.

Proof of Watermark

Embed hidden watermarks in media and then prove correct “retrieval” using ZKML or other as evidence for legal action.

Source

Loyalty Rewards

Members earn rewards through behavior such as purchases.

Source

Simulated Digital Twin

Aggregates all your data into a "digital twin" of yourself and then uses AI or matching algorithms to discovery rewarding experiences or execute intent using your data in a privacy preserving manner.

RWA Verified On-Chain

Jiritsu is a cutting-edge Layer 1 blockchain with a native ZK-MPC oracle designed for real-world assets. May be realized, but the technology is proprietary.

Source

Private Dating Apps

Only match people who have very close taboo preferences.

Web2 Vampire Attacks

Airdrop a token to user X if they perform action Z on a web2 platform.

External References

47 use cases to save humanity

Cursive Ideas and Moonshots

Learning

If you are new to the space, the definitions file will be a good place to start. Once you are familiar with the definitions then you can move on to the resources file to dig deeper into either practical or theoretical subject matter.

Commitment schemes

(informally: “Commit-Reveal”)

Technical Description

Commitment schemes consist of two phases:

1. The commit phase, where a value is chosen and committed to — (e.g. the player commits to a value)
   1. Commitments make use of the binding property. This means the sender cannot cheat during the reveal phase and open the commitment to a different value than was initially chosen.
2. The reveal phase during which the value is revealed by the sender, then the receiver verifies its authenticity.
   1. Commitments also make use of the hiding property. This means the receiver cannot open the commitment (and reveal inside) until the sender allows them to do so.

Zero-Knowledge Proofs

A zero-knowledge proof is a way of proving the validity of a statement without revealing the statement itself. The ‘prover’ is the party trying to prove a claim, while the ‘verifier’ is responsible for validating the claim.

A zero-knowledge proof of some statement must satisfy three properties:

Completeness: if the statement is true, an honest verifier (that is, one following the protocol properly) will be convinced of this fact by an honest prover.

Soundness: if the statement is false, no cheating prover can convince an honest verifier that it is true, except with some small probability.

Zero-knowledge: if the statement is true, no verifier learns anything other than the fact that the statement is true. In other words, just knowing the statement (not the secret) is sufficient to imagine a scenario showing that the prover knows the secret. This is formalized by showing that every verifier has some simulator that, given only the statement to be proved (and no access to the prover), can produce a transcript that "looks like" an interaction between an honest prover and the verifier in question.

References

• Intro to Zero Knowledge
• ZK Math Intution
• ZK Whiteboard Sessions
• Resources from the 0xPARC Applied Learning Group
• ZK Docs
• ZK Jargon Decoder
• Proofs, Arguments, and Zero Knowledge by Justin Thaler

Homomorphic Encryption

Homomorphic encryption is a form of encryption that allows computations to be performed on encrypted data without first having to decrypt it. There are multiple types of encryption schemes that can perform different classes of computations over encrypted data

Partially homomorphic: encryption encompasses schemes that support the evaluation of circuits consisting of only one type of gate, e.g., addition or multiplication.

Somewhat homomorphic: encryption schemes can evaluate two types of gates, but only for a subset of circuits.

Leveled fully homomorphic: encryption supports the evaluation of arbitrary circuits composed of multiple types of gates of bounded (pre-determined) depth.

Fully homomorphic: encryption (FHE) allows the evaluation of arbitrary circuits composed of multiple types of gates of unbounded depth and is the strongest notion of homomorphic encryption.

Source

Secure Multi-Party Computation (MPC)

Secure MPC protocols typically use secret sharing at their core, sometimes combined with oblivious transfer. At a high level, the input data is split up into secret shares which are distributed to all parties. Next, a circuit is evaluated in MPC using operation-specific techniques to compute each gate over the secret-shared values. When the circuit evaluation is complete, each party holds a secret share of the circuit’s output, and these can be used to get the output of the computation.

There are a number of generic protocols for MPC, as well as custom protocols for specific use-cases of MPC, such as Private Set Intersection and Threshold Signatures.

Fundamental protocols [source]:

• Yao's Garbled Circuits Protocol
• Goldreich-Micali-Wigderson (GMW) Protocol
• BGW protocol
• MPC From Preprocessed Multiplication Triples
• Constant-Round Multi-Party Computation: BMR
• Information-Theoretic Garbled Circuits
• Oblivious Transfer

Threshold signatures

The idea in a threshold scheme is to divide a secret $S$ into $n$ pieces of data $S_1,...,S_n$ in such a way that:

1. Knowledge of any $k$ or more shares $S_i$ makes $S$ computable.
2. Knowledge of any $k - 1$ or fewer shares $S_i$ leaves $S$ completely undetermined.

[source]

Threshold schemes are the foundation of threshold key cryptography. Threshold cryptosystems protect information by encrypting and distributing secrets amongst a cluster of independent computers that qualify as fault-tolerant. The fault-tolerance of a system simply means the system’s ability to continue operating despite failures or malfunctions.

[source]

Threshold schemes become threshold cryptosystems when combined with a decryption or signature protocol.

Consider a scenario in which $N$ parties each hold shards of a key. The key was used to encrypt some information (such as the location of a secret treasure). These $N$ parties agree to cooperate in decrypting this information only if a player can prove they are located near the secret treasure.

Trusted Execution Environments

A trusted execution environment (TEE) is an area on the main processor of a device that is separated from the system's main operating system (OS). It ensures data is stored, processed and protected in a secure environment. TEEs provide protection for anything connected, such as a trusted application (TA), by enabling an isolated, cryptographic electronic structure and end-to-end security. This includes the execution of authenticated code, confidentiality, authenticity, privacy, system integrity and data access rights.

[source]

While there is a spectrum of functionality across TEEs, the most general case is something like the above. The trusted execution environment is physically isolated from the rest of the hardware. OS and all interfaces into shared RAM, disk etcetera ensure the information is first encrypted, either using hardware keys or some provisioned key that only the trusted environment can access.

This means, in practice, a TEE allows for fully confidential, tamper-proof compute by an untrusted server (e.g. cloud provider). This unlocks a different method for “shared private state” by allowing arbitrary functions to be computed over encrypted data, but in a much more centralised fashion than in MPC.

Combining TEEs with MPC can be a powerful combination when stronger decentralisation guarantees are a requirement and may ameliorate some of the central party risks involved.

In theory, the provider will not be able to see the data or know what the code is computing. However, in practice, physical access to the device does offer unique attack vectors which are less present in the purely cryptographic schemes. Furthermore, the semiconductor industry is tightly controlled. Relying on a few chip manufacturers to securitise the world’s information (even under the presence of auditors) comes with unique risks. Furthermore (and for that reason), in the context of crypto, TEEs may be “memetically suboptimal” as suggested by Justin Drake. We also recommend this counterview from Andrew Miller.

Already TEEs are widely available in mobile phones, but generally limited to supporting biometric ID — for example Apple’s SecureEnclave. Cloud computing platforms are beginning to offer secure, isolated compute environments to their customers.

Overall, trusted execution environments are an appealing option to faciliate shared private state. This is especially true when considering the high cost and caveats of alternative schemes.

References

• The Secret to Understanding MPC (Bain Capital Crypto Whiteboard Series with David Wong)
• Pragmatic MPC
• FHE.org

Literature

This collection of papers is meant to be a guide for new entrants into the field. This is not by any means a comprehensive list. If you think something should be added, please add it.

Foundations

zkSNARKs

On the Size of Pairing-based Non-interactive Arguments

• Paper
• Talk

PlonK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge

• Paper
• Talk

Fast Reed-Solomon Interactive Oracle Proofs of Proximity

• Paper

Delegating Computation: Interactive Proofs for Muggles

• Paper
• Talk

Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency

• Paper

Proof-Carrying Data and Hearsay Arguments from Signature Cards

• Paper

Fast Reductions from RAMs to Delegatable Succinct Constraint Satisfaction Problems

• Paper

Plookup: A simplified polynomial protocol for lookup tables

• Paper

JOLT: SNARKs for Virtual Machines via Lookups

• Paper

ProtoStar: Generic Efficient Accumulation/Folding for Special Sound Protocols

• Paper

FHE

A Fully Homomorphic Encryption Scheme

• Paper

Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based

• Paper
• Talk

Fully Homomorphic Encryption without Bootstrapping

• Paper

TFHE: Fast Fully Homomorphic Encryption over the Torus

• Paper

MPC

How to Generate and Exchange Secrets

• Paper

How to Share a Secret

• Paper

Protocols for Secure Computation

• Paper

How to Play ANY Mental Game

• Paper

Multiparty Computation from Somewhat Homomorphic Encryption

• Paper

Applications and Review

Zerocash: Decentralized Anonymous Payments from Bitcoin

• Paper
• Talk

Verifiable Delay Functions

• Paper
• Talk

ZEXE: Enabling Decentralized Private Computation

• Paper
• Talk

zkLedger: Privacy-Preserving Auditing for Distributed Ledgers

• Paper

Filecoin: A Decentralized Storage Network

• Paper

Arke: Scalable and Byzantine Fault Tolerant Privacy-Preserving Contact Discovery

• Paper
• Talk

SoK: Programmable Privacy in Distributed Systems

• Paper
• ZK Podcast episode

zk-creds: Flexible Anonymous Credentials from zkSNARKs and Existing Identity Infrastructure

• Paper

Applied Cryptography

Learn the foundations of applied cryptography.

General:

• A Graduate Course in Applied Cryptography
• Ronkathon

ZK:

• Proofs, Arguments, and Zero-Knowledge
• Lambda Bootcamp

FHE:

• Course on Advanced Cryptography (FHE)
• FHE-MPC Advanced Grad Course

MPC:

• Pragmatic MPC
• FHE-MPC Advanced Grad Course

Multi-Party Computation

• Do All Roads Lead To MPC? Exploring The End-Game For Privacy Infrastructure
• Secure Multi-Party Computation
• Awesome MPC

Zero-Knowledge Proofs

zk DSLs

Domain-specific languages which allow you to write programs to generate zero-knowledge circuits. Running these circuits executs a proven program. Many of these languages are described as "rust-like" or like o1js are a framework written in typescript.

Noir

• BattleZips-Noir
• Docs
• Awesome Noir

Circom

• Docs
• Learn at 0xParc
• Awesome Circom

o1js

• Docs

General-purpose zkVMs

zkVMs are virtual machines that execute instructions as zero-knowledge circuits. This allows you to write programs in your programming language of choice and have them executed in a zero-knowledge manner.

SP1

• Docs

Risc Zero

• Docs

Valida

• Docs

Investigations

This is where we keep track of active investigations into open questions.

Mobile Proving

Composing Attestations

Failure Modes

ProgCrypto: Risks and Opportunities

Open Questions

• The proofs we generate are a snapshot in time, but often we are more interested in mutations and up-to-date data. How do we keep our data fresh and propagate updates?
• How can we improve the UX of Trust Infrastructure?
  • ZKEmail copy and paste raw data
  • TLSNotary clunky chrome extensions
  • etc
• What other different security design / assumptions are available?
  • Off-loading most work to 3rd party services?

Mobile Proving

The following information comes from a presentation made by Théo Madzou. Mobile Proving is an active area of both research and development. Developer tooling remains in the early days. Here we outline the current state of its practical use and remaining challenges in regards to usability and performance.

Use Cases

• Geolocation: proof of location
  • iOS only gives you high-level access through their API, whereas Android gives you low-level data from the phone's GPS. Web can give you limited access to location. Proving that this data came from the users particular phone requires augmenting this data with something like Apple's App Attest.
• Reading NFC chips: biometric passports and ID cards, debit/credit cards
  • You need a native app to read NFC chips. This makes NFC a "true mobile" use case.
• Taking photos and videos: proof of taking a real photo or video (i.e. not generated by AI)
• Bluetooth: proof of proximity (e.g. contact tracing)
• Secure Element: leverage secure element’s cryptography to improve UX

Current Limitations

The two major constraints facing mobile proving are:

• the limited amount of RAM
• the lack of dedicated, general GPU.

The combination of these two factors means succesful mobile proving requires breaking up proofs into smaller, highly-optimised circuits, sequentially proving them and then aggregating them into a single recursive proof. This typically works around the 2GB RAM limit, but at the cost of additional proving time.

Limited RAM

The major constraint on current mobile proving is the limited amount of RAM on mobile devices. This cannot be alleviated by "swap" because this typically isn't available on mobile devices. Apps will just crash if they run out of memory. It is possible to create a "swap" like affordance but requires manual work and is not directly handled for you by the OS.

Source Source

Based on the images above we see that for the general mobile user, the usable amount of RAM is roughly around ~2-2.5GB. This means mobile proving is an even more constricted environment than in the browser where WASM environments create a limit at 4GB.

It may be possible to declare in the manifest for iOS apps that your app requires a "high" amount of memory. This value is com.apple.developer.kernel.increased-memory-limit.

Large Proving Keys

Depending on the tool stack being used, proving keys may need to be bundled with the app. These tend to be large, for example the key for the RSA circuit in OpenPassport is ~300MB. Either you put it in the binary, which makes the app size large or you download it which takes up lots of mobile data. Furthermore, modular circuits in Circom may have multiple proving keys, which exacerbates the problem.

For Noir (or tooling which uses a universal trusted setup) will require a SRS. This SRS can be large as well (32MB), though it may not be as large as the proving keys in Circom. The proving keys in Noir for the circuits are created on the fly. These proving keys are as large as the proving keys in Circom and are loaded into RAM. They may be several GBs in size and this is a source of pressure on the RAM.

Future Work

Collaborative zkSNARKs We can potentially generate the witness locallyand offload the majority of the computation to a proving committee.

Simplifying Recursion Automating the process of splitting proofs into multiple proofs and aggregating them at the end would streamline the developer flow in mobile proving. o1js is a good reference for how to do this recursion in a developer friendly way.

Projects

React Native Starter Kit MoPro RapidSnark

Contribute

If you would like to contribute to the wiki, we would be happy to see a pull request from you. There are no major guidelines other than to keep things tidy. Make your changes succinct and targeted.

Contact

The Knot Group is headed by Goblin Oats, grjte and their friends. If you are a friend of a friend and would like to get in touch with us then please reach out to Tonk.