# Grapevine V2 Spec
Grapevine V2 is a SDK for creating private, provable social graphs using Nova-style folding. It provides the most basic primitives for enforcing relationships, as well as proving degrees of separation away from a given relationship.

Grapevine exists as a Cargo crate `grapevine-rs` and a Javascript package `grapevine.js`. Developers can implement these packages to use any Grapevine identity registry, be it the officially hosted server or one they stand up themselves.

## Grapevine Proofs
Grapevine V2 uses Nova, a uniform IVC folding scheme. This means that each circuit is the exact same as the previous one. However, Grapevine has two different functions:
* Proving an identity
* Proving separation from an identity
Thus, Grapevine circuits use an incrementor to toggle different logic according to whether it is the 1st step or a step > 1.

Eventually, proofs represent chains of provable social relationships. Any grapevine proof will demonstrate:
- the `target` of a proof, or the actual identity a user wants to prove separation from
- the `prover` of a proof, or the identity of the user proving their degree of separation from another user
- the `degree` of a proof, or the number of edges in the social graph that must be traversed to reach the `target` from the `prover`

### Identity Proofs
The first step in a Grapevine proof is to prove an identity. This is quite simple- the user simply verifies a signature over their own public key

It is not really possible to further constrain identity to guard against signature leakage without settling proofs onchain. Thus, it is important to discard the signature used to prove an identity. Perhaps an additional public output could be emitted that is the hash of the user address + a random server challenge. However, this would add outputs to an array already bloated by nullifiers.

### Degree Proofs

### Obfuscation Step
Nova IVC proofs are not zero knowledge. Nova achieves zero knowledge by verifying IVC inside of a Spartan ZK Snark. However, doing so destroys the ability to produce additional increments to the IVC proof.

The solution to this problem is to introduce an "Obfuscation" step at the end of each computation that is passed to an untrusted party. Simply, the prover should pass random data for every single input they can. An `obfuscate` flag is toggled, and the equality constraints that would cause the program to fail are multiplexed away, allowing the proof to succeed. In Grapevine, toggling obfuscation will preserve any of the previous step's outputs, meaning the degree of separation, previous prover, etc. will not change.

This does not necessarily need to be every other step - if a usecase had N folds before being passed to another entity, every N+1 steps could be an obfuscation step. In Grapevine, however, N = 1 and thus an obfuscation instance is folded in every other step. [More info on this practice here](https://hackmd.io/Qc4LQwjYQymuG1WmG4ID_A).

** Note here: there are recently raised concerns about the security of this practice. It is likely that this architecture will need to migrate to the upcoming HyperNova (ZK inside of the IVC), or a non-uniform IVC scheme like Protogalaxy which can safely use obfuscation instances.

## Nullifiers and Auth Signatures
`Nullifiers` are a unique method of marking a relationship in a confidential way. They exist for two purposes:
* Allow either user in a relationship to terminate their relationship and invalidate all downstream proofs
* Allow the two users who know a nullifier to determine that their relationship is part of a degree proof chain

Nullifiers allow users to create retractable, pseudanonymous social graphs. While a user with access to all proofs will be able to identify all proofs that a connection is a part of, they will not be able to determine any other information about the connection itself. Even if Alice has established a relationship with Bob, she has no way to associate any other nullifier to bob.

Conversly, Alice knowing the nullifiers used in each direction with Bob, she can easily identify all proofs that are build with her relationship to Bob (again without learning the interstitial relationships).

*** NOTE HERE: If all proofs are available, and all proofs output the last prover, how can the interstital relationships be private... This can be hidden in a centralized server by only returning proofs based on a query of a given nullifier, but a more complex discovery system may be required onchain***

`Auth Signatures` are methods of enforcing integrity in degrees of separation. At any point, a Grapevine proof will output the [BJJ Address](#Addresses) of the account that generated that proof. In the case where Alice creates an `Identity Proof` (Degree 0), Bob can only create a `Degree Proof` (Degree 1) if he can:
1. Prove knowledge of the message the `Auth Signature` validates
2. Prove the signature is made by the pubkey that hashes into the address outputted by the previous proof
3. Prove scoped ownership over the pubkey that hashes into the address in the message

### Nullifier Generation/ Relationshp Creation
Nullifier generation is done at the point of relationship creation.

1. Alice samples a random element of the BN254 field $Fr$ and encrypts it with the shared secret
2. Alice takes the posiedon hash $H|Nullifier, Address_{bob}|$ and signs it
3. Alice [derives an AES key for bob using ephemeral ECDH](https://github.com/Mach-34/Grapevine/blob/d1c174e2ad0720a11cfd49bbb4105a8889825bd7/crates/grapevine_common/src/crypto.rs#L14) and encrypts the nullifier and the signature
4. Alice [derives an AES key for herself using her own BJJ keypair](https://github.com/Mach-34/Grapevine/blob/ad4fd9016d5aa789a84158e9d7a3c4cb9e69424d/crates/grapevine_common/src/account.rs#L118) and encrypts the nullifier
5. Alice submits both ciphertexts to the API to initiate or approve a relationship

This flow is the same whether sending a relationship request or accepting a request. The submitted ciphertexts would be destroyed on the server if the relationship request is rejected by Bob.

### Nullifiers and Auth Signatures in Circuits
There are two objectives inside the circuit:
1. Constrain the current prover to only build proofs authorized by the previous prover
2. Constrain the nullifier inclusion to be authentically issued by the previous prover

### Circuit Auth Inputs
Contextual public outputs will be piped through every proof iteration:
- `target`: The address of the `Identity Proof` creator
- `prover`: The address of the previous `Degree Proof` creator
- `nullifiers[8]`: The array of nullifiers emitted at each degree of separation
- `degree`: The degree of separation proved by this iteration of the proof

Any instance of a `Degree Proof` circuit will take contextual private inputs:
- `prev_pubkey[2]`: the BJJ public key points for the previous proof's creator, which is only passed publicly as a hashed address
- `pubkey[2]`: the proof creator's pubkey
- `sig_auth[3]`: the signature by the previous prover over the nullifier issued to current prover and the current prover's address, serialized as `[r.x, r.y, s]`
- `sig_scope[3]`: the signature by the current prover over the `Identity Proof` creator's address `target`, serialized as `[r.x, r.y, s]`
- `given_nullifier`: the nullifier given to the prover by the previous proof creator through the relationship establishment flow

#### Note on Degree Bounds:
Nullifiers must be emitted in a public manner such that the entire chain of nullifiers can be audited

This is prohibitively expensive onchain and presents an engineering challenge in the future. Potentially, the number of provable degrees of separation could be limited to 3-4, and further degrees of separation could be inferred using multiple proofs where the last nullifier of one proof matches the first nullifier of another. Another option could be to merkleize the nullifiers and prove construction of the tree onchain or with an additional sidecar proof. This would require storing references to emitted nullifiers for each proof, however, and ultimately presents its own problems in terms of gas costs.

### Circuit Auth Steps

1. The prover computes their own address:
$address_{prover} = H|pubkey[0], pubkey[1]|$
2. The prover computes the message authenticated by `auth_signature`:
$auth_{message} = H|nullifier, address_{prover}|$
3. The prover verifies the

To do this, the prover first reconstructs the message of the auth signature: $H|nullifier, $

Nullifiers are not necessary for proving a degree of separation where relationship termination is not possible. However,

### Nullifier Emission/ Relationship Termination

Nullifiers are implemented in a unidirectional manner. When Alice emits her nullifier for the relationship with Bob, neither Bob nor his downstream connections can create new proofs including this nullifier can be created and existing proofs will be considered invalid (and deleted on the server). However, Alice and her downstream relationships will still be able to create proofs until Bob also terminates their relationship.

** NOTE HERE: if Alice knows both nullifiers, could she emit this nullifier as well? It would work with a trusted client/ server, but Alice could construct a signature over the nullifier at any time. Perhaps onchain the auth signature could be submitted publicly?**

@@ NOTE HERE: If nullifiers are eventually emitted publicly AND signatures are stored publicly, but we want to keep the broken relationship private, we likely need to introduce an additional blinding factor to the auth signature. Otherwise, a user could try a preimage attack searching for the message that is verified by the auth signature. This is likely not important in the current version, though

## Server
Grapevine currently exists as an offchain-only SDK. Thus, a product integrating Grapevine must host a centralized server to facilitate user creation, relationship forming, and continuous proof discovery based on relationship distance rules.

An example of the full service is included in the repository, including a native rust implementation. Servers can use either the Rust crate `grapevine-rs` or the JavaScript package `@grapevine/sdk` to integrate functionality. Rust servers will always be more efficient given the wasm32 target, but will otherwise function the same.

[Nova-Scotia](https://github.com/nalinbhardwaj/Nova-Scotia), the SDK for folding used by grapevine, is not built to support onchain proof generation, but future versions will likely switch to [Sonobe](https://github.com/privacy-scaling-explorations/sonobe) which will enable onchain proof settlement. This version may support a hybrid centralized/ decentralized architecture or even work solely onchain and leave offchain integrations to the developer.

### Registration, Authorization & Authentication
Grapevine accounts exist primarily as a Babyjubjub (Poseidon) Keypair. While Grapevine exists as an off-chain library, users begin by registering with the server. Registration consists of providing the server with a new public key, a new username, and a signature by that key over the username. Registration is only successful if the username and public key are unique to the deployment and if the signature is valid.

Once an account has been registered, it can begin performing any of the core social graph actions in grapevine.

#### Addresses
As mentioned in the circuits section, babyjubjub public keys are derived into addresses to minimize public outputs. The process is similar to [Ethereum addresses](https://ethereum.stackexchange.com/questions/142683/how-to-derive-an-eth-address-from-a-publickey) using zk-friendly options:

$Poseidon(Pubkey.X, Pubkey.Y)$

Note that this implementation does not bother taking only the last 20 bytes of the hash as it is cheaper to simply use the poseidon hash.

**Note Here: Would it be easier to do point compression inside circuit? Would that even fit inside a Fr element? IDK **

#### API AuthZ/AuthN
Each API call handling state updates or reads of user-scoped data requires verification of the identity associated with the call. This is done using a primitive verification of a signed nonce by the caller. The server Auth middleware takes a username and a signature, then checks internal storage for the user's nonce. The check finally takes the hash of the username + the internal nonce, and checks that the signature is produced by the pubkey assigned to that username.

Nonce desync presents a paradoxical problem for privacy leakage. An honest user who somehow got out of sync with the server, or perhaps migrated clients, will be unable to produce a signature for the proper nonce and must therefore be able to publicly request the nonce. Therefore, they must be able to retrieve the nonce without authorization. However, this means any other client can then retrieve the # of requests made by an account, which could potentially be used to predict nullifiers based on volume.

*** NOTE HERE: A potential solution to this could be a two-step unique random challenge issued by the server that the client has to sign. If the client can produce a valid signature for the user's pubkey, then the server can return the nonce in the next API call.

*** NOTE HERE: Could also do a two-step JWT for browser-based calls. This was left out since the initial versions were CLI-only and maybe doesn't need to be included unless the grapevine SDK is repurposed to use a trusted server for all clients (in which case such an auth method would be desirable for web based clients)

###

### Proof Discovery & Degree Propogation
Propogation of degrees of separation is asynchronous. If relationships (but not proofs) exist like so:
Alice <-> Bob <-> Charlie <-> David
David cannot prove 3rd degree separation from Alice until Charlie has proven 2nd degree separation, Charlie cannot 2nd degree separation until Bob has proven 1st degree separation, and Bob cannot prove this relationship unless Alice has made their identity proof.

@NOTE HERE: Should registration necessitate generation of an identity proof to remove friction here? Should registration be a separate API call from Identity proof creation, but hidden under the hood of the UI?

****