# General Purpose Gadget: Semantics for Arbitrary Depth Recursive PODs

*gubsheep and Andrew*

This doc presents a design for a "general-purpose semantics" of recursively composable PODs.

This strategy is motivated by the question: "how do you make something like GPC, but it outputs a POD usable by a GPC-like downstream gadget... and another gadget downstream of that gadget, ad infinitum?"

Concretely, we present the **General Purpose Gadget (GPG)**, and the **GPG POD**. A GPG is capable of taking in as input one or more GPG PODs, composing them and transforming them arbitrarily, and then spitting out as output a new GPG POD. It does so while maintaining expressive semantics on the data that are easy to reason about.

This means that this entire loop is "closed" and indefinitely recursive. As a side effect, GPGs and GPG PODs are "self-describing": they don't need any notion of a "configuration" object for a consumer to understand how to interpret and verify them (sidestepping the problem of "how do we aggregate proof configs?"). The semantics and verification process are also *declarative*, which means that you can verify an Nth-order POD without having to know about the graph of operations that even resulted in that POD!

## POD

Within this doc, "POD" is basically a renaming of "PCD." A POD has a `payload`, a `proof`, and a `podType` (these are basically the three fields in PCD).

The payload can be formatted arbitrarily.

## Base POD

A subset of POD types are considered "base PODs." These are simple, first-order PODs, with some minimal opinionatedness on how they are formatted.

A base POD is made up of:

- **Entries**: a set of (K, V) pairs.
- **Proof**: A cryptographic proof about the cryptographic integrity of entries. For the purposes of this Base POD section, think "signature."
- **POD Type**: The type of cryptographic proof. Think "signature scheme (RSA, EdDSA, etc.)." But this could also be "Merkle proof" or something.

Reference example:

{
    "payload": {
        "entries": {
            "attestor": "0x1234abcd",
            "attestee": "0x9876fedc",
            "_signer": "0x9876fedc"
        },
    },
    "proof": {
        "signature": "0x12345678"
    },
    "podType": "eddsa-pod"
}

Note that here, the signer is actually an entry. The verifier for `eddsa-pod` would need to check that a special entry called `_signer` is indeed the signer who correctly verifies from the signature.

A Base POD can be seen as a Complex POD without *statements*. But for some reasons that you'll understand later, we'll draw a distinction between how we think about Base and Complex PODs. (Maybe later we'll find a way to unify them into a single abstraction, but I also don't think that necessarily *needs* to happen.)

## POD Order

The **order** of a POD is how many gadgets downstream of a Base POD it is.

Base PODs are first-order PODs; or equivalently, order-1 PODs. Currently, a GPC outputs order-2 PODs.

## Complex PODs and General Purpose Gadget

Complex PODs are PODs with order greater than one.

The General Purpose Gadget allows you to take in as input a combination of Base and Complex PODs, and output a single Complex POD. The General Purpose Gadget allows you to compose multiple PODs, of arbitrary order, in arbitrary ways. However, it requires a particular opinionated data format for Complex PODs that it takes as input, and that it outputs--call this a "GPG POD."

The General Purpose Gadget can be seen in some ways the "algebraic closure" of General Purpose Circuits. (It also replaces GPC for turning first-order PODs into second-order PODs).

To summarize:

> GPGs can take in a mix of Base PODs as well as GPG-PODs, which are Complex PODs. They output a GPG-POD.

A Complex POD that is output by a GPG is made up of:

- **Payload**, which contains:
- Entries
- This is a list of triples (Origin, Key, Value).
- We'll explain what an origin object is, and what it's made of, below.
- Statements
- This is a list of binary predicates claimed to be true, that looks like: `Predicate(ValueOf(Origin1, Key1), ValueOf(Origin2, Key2)) = true`.
- For example, `Equals(ValueOf("attestation1", "_signer"), ValueOf("attestation2", "watermarkedToKey"))` is a statement that asserts that the signer of attestation1 is the public key that attestation2 is watermarked to.
- **Proof**: a ZK proof. For PODs of order at least 3, these are recursive proofs.
- **POD Type**: The POD type for the PODs outputted by a GPG is a `gpg-pod`.

### Origin

In GPG, every entry has an **origin**. Usually, this refers to a named ancestor POD from which the (K, V) pair in that entry originated, in the ancestor proof chain.

The one exception is that the origin of an entry in a GPG-POD can also be `_SELF_`. This means that this KV pair is introduced in this GPG run. You'll usually do this to introduce new fixed constants that are involved in **statements** that you'll make about other entries.

An origin object contains:

- An arbitrary **name**. This can be any string, so long as no two origin names referenced in the GPG POD that identify different ancestor PODs are the same.
- The **POD Type** of the origin POD.

## General Purpose Gadget

The General Purpose Gadget outputs a GPG POD. The GPG POD has a list of entries and statements, as defined above, and a proof that:

- There exist some PODs that have gone into this proof chain at some point, which for the purposes of verification, will be referred to by the names of various `origin`s referenced in both `entries` and `statements`.
- Each entry in `entries` is a KV pair from the POD that is referred to by the corresponding origin name.
- Each statement in `statements` is true.

**It is possible to write a single ZK circuit for GPG.** This means that the semantics of the GPG-POD feel more declarative. It also means that GPG is a "closed" operation: it takes in GPG PODs (and some special cases for Base PODs and keypairs), and outputs a GPG POD.

**A GPG-POD does not need a "GPG Config" to be interpreted and verifying.** In other words, GPG-PODs are "self-describing": by only looking at the GPG payload, you can understand what is being proven and how to verify it.

**This is very nice!** A GPG basically enables a kind of POD that is self-describing and self-verifying, and that can be composed recursively arbitrarily without the need to introduce new special-purpose machinery. This is somewhat reminiscent of a [Quine](https://en.wikipedia.org/wiki/Quine_(computing)).

### Worked Example

Let's consider the Good Boy POD exercise.

This exercise asks us to model a simple decentralized reputation network:

- There is a list of known, public, trusted attestors: say Google, Microsoft, and Facebook.
- There is a set of users on this reputation network: say Alice, Bob, and Charlie.
- The attestors can issue "Good Boy POD" attestations to users. Having a Good Boy POD means that one of these attestors thinks you are a Good Boy, and that they attest to some data about you. These PODs are Base PODs.
- Users can also issue "Friend POD" attestations to each other. These PODs are also Base PODs. Issuing a Friend POD to someone is basically just signing their public key with your keypair.
- You can prove that you have high reputation by proving that you have Friend PODs from a bunch of people who each have multiple Good Boy PODs.
- In particular, if you have received Friend PODs from two people, each of whom has at least two Good Boy PODs, you can compose these all together into a Great Boy POD that proves that you are a Great Boy.

This is not possible today with our current POD / GPC abstraction. In particular, using a GPC I can generate and issue you a Friend GPCPCD that carries with it the data that I am your friend and that I have received at least two Good Boy PODs, but you can't turn around compose this Friend PCD with other Friend PCDs to generate the desired Great Boy PCD.

This changes with GPG POD. Here's the setup for the POD generation story:

- Bob has received two Good Boy PODs, say from Google and Microsoft.
- Charlie has received two Good Boy PODs, say from Microsoft and Facebook.
- Bob sends Alice a Trusted Friend POD, which basically says, "I'm Bob and I attest that Alice is my friend, and that I have at least two Good Boy PODs".
- Charlie sends Alice a Trusted Friend POD, which basically says, "I'm Charlie and I attest that Alice is my friend, and that I have at least two Good Boy PODs".
- Alice generates a Great Boy POD, which basically says, "I'm Alice and I have at least two Trusted Friend PODs, i.e. Friend PODs from people who each have at least two Good Boy PODs."
- As an extra requirement, let's say that to generate a Great Boy POD, your friend PODs need to be from people who are at least 18 years old.

Alright, so let's start off with some public key identifiers for everyone:

Microsoft: 0xMICROSOFT
Google: 0xGOOGLE
Facebook: 0xFACEBOOK
Alice: 0xALICE
Bob: 0xBOB
Charlie: 0xCHARLIE
Known_Attestors: 0xMERKLEROOT // merkle root of [0xMICROSOFT, 0xGOOGLE, 0xFACEBOOK]

OK, so let's write out some PODs.

Here are the four initial Good Boy PODs:

**Google attesting to Bob**

{
    "payload": {
        "entries": {
            "user": "0xBOB",
            "age": 36,
            "_signer": "0xGOOGLE"
        },
        "statements": {} // empty because this is a base POD
    },
    "proof": {
        "signature": "0x12345678"
    },
    "podType": "eddsa-pod"
}

**Microsoft attesting to Bob**

{
    "payload": {
        "entries": {
            "user": "0xBOB",
            "age": 36,
            "_signer": "0xMICROSOFT"
        },
        "statements": {} // empty because this is a base POD
    },
    "proof": {
        "signature": "0x12345678"
    },
    "podType": "eddsa-pod"
}

**Microsoft attesting to Charlie**

{
    "payload": {
        "entries": {
            "user": "0xCHARLIE",
            "age": 27,
            "_signer": "0xMICROSOFT"
        },
        "statements": {} // empty because this is a base POD
    },
    "proof": {
        "signature": "0x12345678"
    },
    "podType": "eddsa-pod"
}

**Facebook attesting to Charlie**

{
    "payload": {
        "entries": {
            "user": "0xCHARLIE",
            "age": 27,
            "_signer": "0xFACEBOOK"
        },
        "statements": {} // empty because this is a base POD
    },
    "proof": {
        "signature": "0x12345678"
    },
    "podType": "eddsa-pod"
}

Now Bob and Charlie need to produce Trusted Friend PODs for Alice.

First, each of them generates some basic attestation for Alice:

**Bob attesting to Alice**

{
    "payload": {
        "entries": {
            "user": "0xALICE",
            "_signer": "0xBOB"
        },
        "statements": {} // empty because this is a base POD
    },
    "proof": {
        "signature": "0x12345678"
    },
    "podType": "eddsa-pod"
}

**Charlie attesting to Alice**

{
    "payload": {
        "entries": {
            "user": "0xALICE",
            "_signer": "0xCHARLIE"
        },
        "statements": {} // empty because this is a base POD
    },
    "proof": {
        "signature": "0x12345678"
    },
    "podType": "eddsa-pod"
}

Now, Bob combines his basic attestation for Alice with his two Good Boy PODs. In other words, he runs a GPG that takes in as input three (base) PODs: the **Google / Bob Good Boy POD**, the **Microsoft / Bob Good Boy POD**, and the **Bob / Alice Basic Attestation POD**.

The result is something that looks like this:

**Bob's "Trusted Friend" POD for Alice: He attests to Alice, and is someone with at least two Good Boy PODs**

{
    "payload": {
        "entries": [ // array of (Origin, Key, Value) triples
            {
                "origin": {
                    "name": "bob-alice-attest", // name it whatever you want, as long as no conflicts between different PODs
                    "podType": "eddsa-pod"
                },
                "key": "_signer",
                "value": "0xBOB"
            },
            {
                "origin": {
                    "name": "bob-alice-attest", // origins with the same name mean that i'm making claims about the same POD
                    "podType": "eddsa-pod"
                },
                "key": "user",
                "value": "0xALICE"
            },
            { // Bob chooses to disclose his attested age in this POD
                "origin": {
                    "name": "bob-goodboy-1", // name it whatever you want, as long as no conflicts
                    "podType": "eddsa-pod"
                },
                "key": "age",
                "value": 36
            },
            { // introduce a constant in the clear - knownAttestorRoot
                "origin": {
                    "name": "_SELF_", // special origin name for introducing constants
                    "podType": "gpg-pod" // originates in self
                },
                "key": "knownAttestorRoot",
                "value": "0xMERKLEROOT"
            }
        ],
        "statements": [ // array of (Predicate, LeftEntry, RightEntry) triples
            {
                "predicate": "EQUALS",
                "left": {
                    "origin": "bob-alice-attest",
                    "key": "_signer"
                },
                "right": {
                    "origin": "bob-goodboy-1",
                    "key": "user"
                }
            },
            {
                "predicate": "EQUALS",
                "left": {
                    "origin": "bob-alice-attest",
                    "key": "_signer",
                },
                "right": {
                    "origin": "bob-goodboy-2",
                    "key": "user"
                }
            },
            {
                "predicate": "MERKLE_INCLUDES",
                "left": {
                    "origin": "_SELF_",
                    "key": "knownAttestorRoot",
                },
                "right": {
                    "origin": "bob-goodboy-1",
                    "key": "_signer"   
                }
            },
            {
                "predicate": "MERKLE_INCLUDES",
                "left": {
                    "origin": "_SELF_",
                    "key": "knownAttestorRoot",
                },
                "right": {
                    "origin": "bob-goodboy-2",
                    "key": "_signer"
                }
            },
            {
                "predicate": "NOT_EQUALS",
                "left": {
                    "origin": "bob-goodboy-1",
                    "key": "_signer", // could also do contentID
                },
                "right": {
                    "origin": "bob-goodboy-2",
                    "key": "_signer" // could also do contentID
                }
            }
        ]
    },
    "proof": {
        "zkproof": "0x12345678"
    },
    "podType": "gpg-pod"
}

For completeness, let's write out the Trusted Friend POD that Charlie gives to Alice as well:

**Charlie's "Trusted Friend" POD for Alice: He attests to Alice, and is someone with at least two Good Boy PODs**

{
    "payload": {
        "entries": [ // array of (Origin, Key, Value) triples
            {
                "origin": {
                    "name": "charlie-alice-attest", // name it whatever you want, as long as no conflicts between different PODs
                    "podType": "eddsa-pod"
                },
                "key": "_signer",
                "value": "0xCHARLIE"
            },
            {
                "origin": {
                    "name": "charlie-alice-attest", // origins with the same name mean that i'm making claims about the same POD
                    "podType": "eddsa-pod"
                },
                "key": "user",
                "value": "0xALICE"
            },
            { // Charlie chooses to disclose his attested age in this POD
                "origin": {
                    "name": "charlie-goodboy-1", // name it whatever you want, as long as no conflicts
                    "podType": "eddsa-pod"
                },
                "key": "age",
                "value": 27
            },
            { // introduce a constant in the clear - knownAttestorRoot
                "origin": {
                    "name": "_SELF_", // special origin name for introducing constants
                    "podType": "gpg-pod" // originates in self
                },
                "key": "knownAttestorRoot",
                "value": "0xMERKLEROOT"
            }
        ],
        "statements": [ // array of (Predicate, LeftEntry, RightEntry) triples
            {
                "predicate": "EQUALS",
                "left": {
                    "origin": "charlie-alice-attest",
                    "key": "_signer"
                },
                "right": {
                    "origin": "charlie-goodboy-1",
                    "key": "user"
                }
            },
            {
                "predicate": "EQUALS",
                "left": {
                    "origin": "charlie-alice-attest",
                    "key": "_signer"
                },
                "right": {
                    "origin": "charlie-goodboy-2",
                    "key": "user"
                }
            },
            {
                "predicate": "MERKLE_INCLUDES",
                "left": {
                    "origin": "_SELF_",
                    "key": "knownAttestorRoot"
                },
                "right": {
                    "origin": "charlie-goodboy-1",
                    "key": "_signer"
                }
            },
            {
                "predicate": "MERKLE_INCLUDES",
                "left": {
                    "origin": "_SELF_",
                    "key": "knownAttestorRoot"
                },
                "right": {
                    "origin": "charlie-goodboy-2",
                    "key": "_signer"
                }
            },
            {
                "predicate": "NOT_EQUALS",
                "left": {
                    "origin": "charlie-goodboy-1",
                    "key": "_signer",
                },
                "right": {
                    "origin": "charlie-goodboy-2",
                    "key": "_signer"
                }
            }
        ]
    },
    "proof": {
        "zkproof": "0x12345678"
    },
    "podType": "gpg-pod"
}

Finally, Alice uses a GPG to combine these two GPG-PODs into another GPG-POD. Here's the GPG POD that she produces:

**Alice's Great Boy POD: She has attestations from two users who each have at least two Good Boy PODs and who are each at least 18 years old**

{
    "payload": {
        "entries": [ // array of (Origin, Key, Value) triples
            {
                "origin": { // carried over from Bob<>Alice POD entries, but with name remapped
                    "name": "friend1-alice-attest", // names are for convenience, and can be remapped to whatever you want downstream
                    "podType": "eddsa-pod"
                },
                "key": "user",
                "value": "0xALICE"
            },
            {
                "origin": {
                    "name": "friend2-alice-attest", // origins with the same name mean that i'm making claims about the same POD
                    "podType": "eddsa-pod"
                },
                "key": "user",
                "value": "0xALICE"
            },
            { // a constant introduced and named here, so _SELF_
                "origin": {
                    "name": "_SELF_",
                    "podType": "gpg-pod"
                },
                "key": "ageBound",
                "value": 18
            },
            { // a constant introduced and named here, so _SELF_
                "origin": {
                    "name": "_SELF_",
                    "podType": "gpg-pod"
                },
                "key": "knownAttestorRoot",
                "value": "0xMERKLEROOT"
            }
        ],
        "statements": [ // array of (Predicate, LeftEntry, RightEntry) triples
            { // friend1 has a good boy POD
                "predicate": "EQUALS",
                "left": {
                    "origin": "friend1-alice-attest",
                    "key": "_signer"
                },
                "right": {
                    "origin": "friend1-goodboy-1",
                    "key": "user"
                }    
            },
            { // that good boy POD is from a valid attestor
                "predicate": "MERKLE_INCLUDES",
                "left": {
                    "origin": "_SELF_",
                    "key": "knownAttestorRoot"
                },
                "right": {
                    "origin": "friend1-goodboy-1",
                    "key": "_signer"
                }    
            },
            { // friend1 has a second good boy POD
                "predicate": "EQUALS",
                "left": {
                    "origin": "friend1-alice-attest",
                    "key": "_signer"
                },
                "right": {
                    "origin": "friend1-goodboy-2",
                    "key": "user"
                }    
            },
            { // that good boy POD is also from valid attestor
                "predicate": "MERKLE_INCLUDES",
                "left": {
                    "origin": "_SELF_",
                    "key": "knownAttestorRoot"
                },
                "right": {
                    "origin": "friend1-goodboy-2",
                    "key": "_signer"
                }    
            },
            { // those two good boy PODs are different PODs
                "predicate": "NOT_EQUALS",
                "left": {
                    "origin": "friend1-goodboy-1",
                    "key": "_signer",
                },
                "right": {
                    "origin": "friend1-goodboy-2",
                    "key": "_signer"
                }
            },
            { // friend2 has a good boy POD...
                "predicate": "EQUALS",
                "left": {
                    "origin": "friend2-alice-attest",
                    "key": "_signer"
                },
                "right": {
                    "origin": "friend2-goodboy-1",
                    "key": "user"
                }    
            },
            { // ... from a valid attestor...
                "predicate": "MERKLE_INCLUDES",
                "left": {
                    "origin": "_SELF_",
                    "key": "knownAttestorRoot"
                },
                "right": {
                    "origin": "friend2-goodboy-1",
                    "key": "_signer"
                }    
            },
            { // ... and has a second good boy POD...
                "predicate": "EQUALS",
                "left": {
                    "origin": "friend2-alice-attest",
                    "key": "_signer"
                },
                "right": {
                    "origin": "friend2-goodboy-2",
                    "key": "user"
                }    
            },
            { // ... also from a valid attestor...
                "predicate": "MERKLE_INCLUDES",
                "left": {
                    "origin": "_SELF_",
                    "key": "knownAttestorRoot"
                },
                "right": {
                    "origin": "friend2-goodboy-2",
                    "key": "_signer"
                }    
            },
            { // ... that is different from the first.
                "predicate": "NOT_EQUALS",
                "left": {
                    "origin": "friend2-goodboy-1",
                    "key": "_signer",
                },
                "right": {
                    "origin": "friend2-goodboy-2",
                    "key": "_signer"
                }
            },
            { // friend1 and friend2 are different
                "predicate": "NOT_EQUALS",
                "left": {
                    "origin": "friend1-alice-attest",
                    "key": "_signer"
                },
                "right": {
                    "origin": "friend2-alice-attest",
                    "key": "_signer"
                }    
            },
            { // friend1 is at least 18
                "predicate": "GTE",
                "left": {
                    "origin": "friend1-goodboy-1",
                    "key": "age"
                },
                "right": {
                    "origin": "_SELF_",
                    "key": "ageBound"
                }
            },
            { // friend2 is at least 18
                "predicate": "GTE",
                "left": {
                    "origin": "friend2-goodboy-1",
                    "key": "age"
                },
                "right": {
                    "origin": "_SELF_",
                    "key": "ageBound"
                }
            }
        ]
    },
    "proof": {
        "zkproof": "0x12345678"
    },
    "podType": "gpg-pod"
}

Voila! We've outputted a GPG POD by running two GPG PODs through a GPG.

You'll notice that this POD's payload seems very long. This is largely because we have to use a lot of newlines to express the minimal set of statements necessary to even describe a Great Boy POD.

### How does a GPG work? What does it do?

Basically, a GPG takes in one or multiple GPG-PODs (or a Base POD, like an EdDSA POD), and allows you to construct a new GPG-POD. The new GPG-POD initially starts as a blank array of `entries` and `statements`; here's how you fill these up:

- **Copy input entry**: If you have an input POD that had some (O, K, V) entry, you can copy that entry into the output POD's `entries` array. (You can rename the origin if you'd like, so long as you are consistently renaming it everywhere that anything from that POD is referenced).
- **Introduce new entry**: You can add a new (O, K, V) entry to `entries` where O is `_SELF_`, and K and V are set arbitrarily.
- **Copy input statement**: You can copy any statement from any input POD. (Again, you can rename the origin of either left and/or right operands if you'd like, so long as you are consistently renaming it everywhere that anything from that POD is referenced).
- **Execute deduction**: There are a series of deduction rules you can use to produce new statements that get added to the array.
- Take the set of all entries among all your input PODs, as well as the entries you've introduced with `_SELF_` origin. Call this `E_in`.
- You can add a new `EQUALS` statement, if two entries `E_in` have equal values.
- You can add `NOT_EQUALS` similarly.
- You can add `GT`, `GTE`, `LT`, `LTE` if two entries satisfy the appropriate inequality checks.
- You can witness a merkle proof or other inclusion check to get things like `MERKLE_INCLUDES` or `ARRAY_INCLUDES`.
- You can also imagine a set of deductions that could be executed on input statements. Suppose that all the statements among all of your input PODs is called `S_in`
- You can imagine executing a transitivity deduction: A == B, and B == C, so produce the statement A == C. Similarly for things like bounds checks: A > B, B > C, so A > C.
- Note that by allowing statements with 3 operands, we can do things like indexing into arrays etc.
- We can also add things like tuple equality checks, set non-inclusions, and more, especially if we have statements with 3 operands.

So, the GPG circuit accepts the input GPG PODs (as private inputs), the claimed output GPG POD (as public input), and a list of *copy operations*, *introduction operations*, and *deductions* (as private inputs); it then verifies the input PODs, and also verifies that after application of the copies, introductions, and deductions, the output POD is indeed derived properly from the input PODs.