# Minimal arbitrarily generic attestations (MAGA)

MAGA is a simple on-chain, privacy preserving attestations protocol. Attestations are associated with an ECDSA signature hash that a user can verify ownership of with a zk proof.

[Github repo here](https://github.com/critesjosh/private-attesations).

This may be best for off chain applications. consider making the time a Public input that invalidates it after X seconds.

the solidity contract could be adapted for specific onchain applications, to make it resistant to front-running the proof public inputs must include any inputs to other solidity functions in the transaction. so for access control, the proof must include inputs for the action to be taken. eg, if its for a vote, the proof must include the vote (for, against), the proposal id and contract, otherwise those could be manipulated by a front runner.

Recursive proofs greatly expand the design space of what's possible. The multisig and voting use cases explored at the bottom of this document are improved greatly when using recursive proofs for aggregation.

## Identifiers

An unlimited number of identifiers can be generated from a single master seed, similar to how [HD wallets work](https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki).

The user would generate their master seed by signing a message with an ethereum wallet. This message should be standardized, so different applications generate identifiers from the same seed.

The `x` ($x_0$) of the pedersen hash of the seed will be the first identifier, $i_0$.

$(x_0, y_0) = pedersen(ecdsa\_signature)$

$i_0 = x_0$

$(x_1, y_1) = pedersen([x_0, y_0])$

$i_1 = x_1$

$(x_2, y_2) = pedersen([x_1, y_1])$

$i_2 = x_2$

fn pedersen(_input : [Field]) -> [Field; 2]

This method has the benefit of not requiring a trusted 3rd party service provider to provide a good UX. A user can generate as many identifiers as the want from a single ECDSA signature and it can all be done client side, in the browser.

This requires a slightly more complex circuit. The circuit will need to have an input that indicates how many times to hash the master seed to return the correct identifier.

**Update:** the number of loop iterations must be determined at compile time, so you can't specify the number of times to hash as an input. As a workaround, we can create several circuits that all do the same thing and just loop different number of times (10, 20, 50, 100, etc) depending on what the user needs. The loop will build an array of the users' identifiers. The user will pass the index for the identifier that they want to check against. See the circuit below for details.

## Attestations

Attestations are stored in an array of `string`s.

It is up to the dapp/attester to encode data in the string however they please. consider [base64](https://github.com/Vectorized/solady/blob/8d868a936ec1a45be294e26de1a64ebfb73c6c20/src/utils/Base64.sol). Base64 encoding reduces storage costs, but increases compute costs for decoding base64, need to test at what storage size base64 becomes more cost effective. They may also want to bind the attestation to a specific `identifier` by including the `identifier` in the attestation data, so it can't be copied and added to another `identifier`.

Users can have unlimited attestations associated with a specific hash, but the more attestations that are collected at one hash, the less anonymous they are. Associations between attestations leaks information.

### Attestation structure

It would be useful to store these structures as events emitted on chain.

#### Schemas

Two types of schema:

- message schema
- signature schema

Schemas are emitted as events when an attestation is added.

event EmitSchema(string schema);

Example:

emit EmitSchema("address,uint16,bytes32");

#### Example schema

Suggested standard encoding for an attestation. Adapt as needed.

| variable | data type | location (bytes index) | description |
|---|---|--- | -- |
| `r` | `bytes32 `| 0-31 | Only required if this is a signed attestion. Users will likely want signed attestations from credible accounts to make the attestation more meaningful. |
| `s` | `bytes32` | 32-63 |
| `v` | `uint8` | 64 |
| `message` | `string` | 65+ | Include arbitrary data that may need to be passed as public proof inputs to a `verifier.verify()` call for replay protection. identifier info should go in here. |

### Message structure

This will vary per use case.

For example, for a multisig, the attester will likely want to link the attestation to the identifier and the multisig wallet address. There are message components that will likely be in most/every attestation:

- Identifier
- MAGA protocol version number / schema

## Solidity Contract

The expected identifier is always the first public input.

This contract can be used for different circuits, the only expectation is that the identifier is the first public input. Adding additional `publicInputs` to the circuit does not change the interface, so `verifyAttestation` should work with many different verifier contracts.

### Interface

interface IMaga {
    
    // processes batches of attestations
    function attest(
        bytes32[] memory _identifiers, 
        bytes[][] memory _attestations) public {}

    // deletes an attestation
    // only callable by attesation signers
    function revokeAttestations(
        bytes32[] memory _identifiers, 
        uint8[][] memory _attestationIndexes, 
        bytes32[][] memory _messageHashes // calculate off-chain for simplicity
    )
    public {}
    
    // _publicInputs[0] - _indentifier
    function verifyAttestation(
        bytes memory _proof, 
        bytes32[] memory _publicInputs, 
        uint _attestationIndex) 
        public
        view
    returns (bytes memory) {}
}

### Implementation

// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.13;

import {UltraVerifier} from '../circuits/contract/plonk_vk.sol';

contract Maga {

    UltraVerifier verifier;
 
    mapping(bytes32 => bytes[]) attestations;
    
    constructor(address _verifier){
        verifier = UltraVerifier(_verifier);
    }

    // possible to batch attestations
    function attest(
        bytes32[] memory _identifiers, 
        bytes[][] memory _attestations) 
    public {
        for (uint i = 0; i < _identifiers.length; i++) {
            for (uint j = 0; j < _attestations[i].length; j++) {
                // push all of the attestations onto the identifier
                attestations[_identifiers[i]].push(_attestations[i][j]);
            }
        }
    }
    
    // This function will only work for attestations that
    // have an associated signature. The attestation can only be revoked 
    // by the account that issued it.
    // Can also batch these calls
    // This function assumes that signatures are located 
    // in the bytes locations discussed (in #attestation-structure) above.
    function revokeAttestations(
        bytes32[] memory _identifiers, 
        uint8[][] memory _attestationIndexes, 
        bytes32[][] memory _messageHashes // calculate off-chain for simplicity
    )
    public {
        for (uint i = 0; i < _identifiers.length; i++) {
            for (uint j = 0; j < _attestationIndexes[i].length; j++) {
                uint8 index = _attestationIndexes[i][j];
                bytes memory attestation = attestations[_identifiers[i]][index];
                uint8 v = uint8(subset(attestation, 128, 0)[0]);
                bytes32 r;
                bytes32 s;
                bytes memory rBytes = subset(attestation, 64, 32);
                bytes memory sBytes = subset(attestation, 96, 32);
                assembly {
                    r := mload(add(rBytes, 32))
                    s := mload(add(sBytes, 32))
                }       
                require(msg.sender == ecrecover(_messageHashes[i][j], v, r, s));
                delete attestations[_identifiers[i]][index];
            }
        }
    }
    
    // _publicInputs[0] - _indentifier
    function verifyAttestation(
        bytes memory _proof, 
        bytes32[] memory _publicInputs, 
        uint _attestationIndex) 
        public
        view
        returns (bytes memory) {
            verifier.verify(_proof, _publicInputs);
            return attestations[_publicInputs[0]][_attestationIndex];
    }
    
    function verifyAttestationFromSafe(
        bytes memory _proof, 
        bytes32[] memory _publicInputs, 
        uint _attestationIndex) 
        public
        view
        returns (bytes memory) {
            // requires a different circuit that takes
            //  multiple ECDSA signatures (from the safe account signers)
            //  the circuit 
            //  1. takes an array of signatures
            //  2. gets the signer addresses for the sigs
            //  3. proves that the signers are owners of the safe
            //  4. proves there are >= the required signatures 
            //  to meet the multisig threshold
            // Waiting on ethereum storage proofs in noir
            // to implement this.

            return attestations[_publicInputs[0]][_attestationIndex];
    }

    // helper function
    function subset(bytes memory _b, uint _startIndex, uint _length) 
        pure 
        internal
        returns(bytes memory) 
    {
        bytes memory newSet = new bytes(_length);
        for (uint i = 0; i < _length; i++) {
            newSet[i] = _b[_startIndex + i];
        }
        return newSet;
    }
}

## Circuit

use dep::std;

// We must know how many identifiers to generate at compile time.
// starting with 20 as an arbitrary number
global NUM_IDENTIFIERS = 20;

// identifier_index should be even since we are getting the 'x' output of flattened array of [x,y] values
// keep identifier as the first input so its always at _publicInputs[0] in the Solidity contract
fn main(identifier : pub Field,
        identifier_index : Field,
        pub_key_x : [u8; 32], 
        pub_key_y : [u8; 32], 
        signature: [u8; 64], 
        message_hash : [u8; 32] 
        ) 
    {
    let isValid = std::ecdsa_secp256k1::verify_signature(pub_key_x, pub_key_y, signature, message_hash);
    assert(isValid == 1);
    
    let mut signature_as_field: [Field; 64] = [0;64];
    for i in 0..signature_as_field.len() {
        signature_as_field[i] = signature[i] as Field;
    }

    let master_seed = std::hash::pedersen(signature_as_field);

    // flattened array of 20 [Field; 2] elements
    let mut identifiers: [Field; NUM_IDENTIFIERS*2] = [0;NUM_IDENTIFIERS*2];
    identifiers[0] = master_seed[0];
    identifiers[1] = master_seed[1];

    let mut target_identifier = 0;

    if(identifier_index > 0) {
        for i in 0..20 {
            // if the target has been found, skip future iterations
            if(target_identifier == 0){
                // multiply by 2 since we are working with a flattened array
                let j = i * 2;
                // new identifier is the hash of the previous
                let prev_identifier = [identifiers[j-2], identifiers[j-1]];

                // hash the previous identifier to get the new identifier
                let new_identifier = std::hash::pedersen(prev_identifier);
                identifiers[j] = new_identifier[0];
                identifiers[j+1] = new_identifier[1];

                if(identifier == identifiers[j]){
                    target_identifier = identifiers[j];
                    assert(target_identifier == identifier);
                }
            }
        }
    } else {
        assert(identifiers[0] == identifier);
    }
}

## Use cases

### Anon multisig

use identifiers as access control for a multisig.

this requires Recursive proofs to work well.

it also requires a new circuit specifically for the multisig use case, where signers indicate the tx details as Public inputs to the circuit.

in the circuit, attestation holders prove they hold the proper attestation (with the multisig address in the signed attestation message) and indicate the tx destination, amount and calldata. these proofs are shared among signers or posted somewhere for availability. once the threshold number of proofs is available, someone can take those and prove that all of the attestion holders are authorized to sign for the multisig.

- inputs to the circuit
- array of identifiers (could be private? but not helpful)
- contract address for multisig
- destination
- value
- calldata

### Voting

similar idea as above with recursion.

this is a bit more difficult because there are censorship concerns.

is there a way to show proof of tally while maintaining privacy and allowing censored votes to be force included on L1?

circuit would have to aggregate all of the vote proofs, for/against totals would be public inputs. if someone is able to sumbit a valid tally proof with a higher total vote count, the previous submitter is slashed and total is invalid. or there is a token incentive for someone to sumbit the tally proof. the window for tally proofs is X days. only the highest vote counr tally proof gets the reward. this incentives people to withhold votes and create valid proofs later. is there a way to timesamp them?

maybe just follow the [snapshot pattern](https://blog.ipfs.tech/2022-08-25-snapshot-ipfs-case-study/#how-snapshot-uses-ipfs) and just put them all of IPFS. snapshot actually has a lot of the same problems as this, so research how they do it (closing votes, allowing people to vote twice, etc). Maybe reach out and see if there is capability for privacy preserving extension to snapshot ([plugin](https://docs.snapshot.org/user-guides/plugins)).

Once we have storage proofs in Noir, voters could prove that they hold a certain number of tokens while casting a ballot and get increased voting weight. There are privacy concerns with this approach. If I have >100 tokens and only 2 other people do as well, if I vote with my full weight, it will be public knowledge that 1 of the 3 of us voted this way. The circuit should allow a user to choose how much to vote with. There might be some way to let people vote in chunks, to be explored further.