UTXO syntax [3]: support for partial commitments

Aztec
, ,
1

Setting the scene

Aztec connect has a very neat way of allowing someone to create notes for an anonymous person: partial commitments.

Suppose the full commitment is of the form:

commitment = storage_slot * A + value * B + owner * C + salt * D + nonce * E

A,B,C,D,E are generator points for some elliptic curve. This commitment is a Pedersen commitment, and it’s additively homomorphic, meaning we can add data to the hash at some later time.

Keeping with the Aztec Connect example for a moment, suppose everyone’s token balances were declared in a Noir++ contract as a state variable of the form:

// owner => asset_id => balance utxos
mapping(address => mapping(uint => UTXOSet<uint>)) balances;

The storage_slot for balances[alice_address][asset_id] would be something like:

storage_slot = h( h(1, alice_address), asset_id )

The 1 is for example’s sake; the ‘base’ storage slot of the variable, based on the ordering of declaration of the variables in the contract’s scope, similar to how Solidity does it.

Now,

  • Alice wants to remain anonymous.
  • We don’t know what the storage_slot will be, because we don’t know what the asset_id will be which is returned from the bridge contract.
  • Furthermore, we don’t want to reveal Alice’s address; we want her to remain anonymous.

This is an interesting point to pause. Alice’s address is actually contained in two places in my mental model, in this example: the storage_slot AND the owner of the commitment.

So I propose we derive storage slots with homomorphic commitments, so that Alice can embed alice_address in the partial commitment, and then later Bob can complete the storage slot with the asset_id.

So using Pedersen hashes (ish) for h():

storage_slot = h( h(1, alice_address), asset_id ) is modified slightly to:
storage_slot = 1 * X + alice_address * Y + asset_id * Z

Again, X,Y,Z are generator points.

If the storage slot is now a point, we can modify the commitment we wrote at the start, to remove A:

commitment = storage_slot + value * B + owner * C + salt * D + nonce * E

With this, our storage slot can be “completed”.

Continuing:

  • Alice doesn’t know what the value will be until later either.
  • So, Alice creates a partial commitment:
    partial_commitment = 1 * X + alice_address * Y + 
                     owner=alice_address * C + salt * D + nonce * E
  • We can store this partial_commitment as a public state.
  • Some time later, when we know the asset_id and value:
  • Bob comes along and ‘completes’ Alice’s commitment:
    complete_commitment = partial_commitment + asset_id * Z + value * B
    
    = 1 * X + alice_address * Y + asset_id * Z +
      value * B + owner * C + salt * D + nonce * E

    = storage_slot +
      value * B + owner * C + salt * D + nonce * E

Summary

  • Above we describe a little bit of Aztec Connect functionality, but in the context of Aztec3.
  • Expressing every storage slot as an elliptic curve point, gives flexibility for storage slots to be ‘completed’ at some time in the future.

Syntax

So what would Noir++ syntax look like, to give us control over which components of a storage_slot and/or a UTXO’s preimage we can insert some time later (to achieve partial commitment functionality).

My laptop’s about to die, but I’m open to suggestions for syntax…

11 Likes
2

Syntax Proposal:

The UTXO<T> type is aware of its preimage, as data members:

  •   std::optional<grumpkin_point> storage_slot,
  std::optional<T> value,
  std::optional<fr> owner, // x-coord of owner pub key
  std::optional<fr> salt,
  std::optional<fr> nonce,

The std::optionals are so the type is aware of which members have been assigned, to support partial commitments.

Amongst other methods, the type would have:

  • fr commit()
  • grumpkin_point partially_commit()

We also make an underscore ? a special character, for use in this partial commitment context, which means “we’re leaving this empty, to be populated some time later”.

We also create a more “regular-dev-friendly” alias for a grumpkin_point: IncompleteCommitment. (I think “Incomplete” is a more appropriate word than “Partial”, for devs to understand.

Here’s an Aztec Connect defi-deposit example (simplified to only have one type of bridge, so we don’t have to worry about bridge_ids cluttering things):

Edit: I can’t figure out how to show all the code without a scrollbar - please use the scrollbar, because there’s lots of code.

// owner => asset_id => balance utxos
mapping(address => mapping(uint => UTXOSet<uint>)) balances;

// asset_id => total_pending_deposit
mapping(uint => uint) total_pending_deposits;

uint next_defi_interaction_nonce;

// asset_id => current_defi_interaction_nonce
mapping(uint => uint) current_defi_interaction_nonce;

// Basically a claim note, but we don't need notes when we have public state!
struct ClaimDatum {
    uint amount_deposited,
    uint total_deposited,
    uint total_output,
    uint input_asset_id,
    uint output_asset_id,
    IncompleteCommitment incomplete_balance_commitment,
}

// defi_interaction_nonce => all claim data for all claimants of an interaction
mapping(uint => ClaimDatum[]) claim_data;

// Nullify some notes to do a defi-deposit:
private function submit_defi_deposit(uint deposit_asset_id, uint deposit_amount) {
     // Grab notes and spend them.
     UTXO<field>[2] notes = balances[msg.sender].get(2, sort, filter, { owner : msg.sender });

    uint input_note_sum = notes[0] + notes[1];
    require(input_note_sum >= deposit_amount);

    notes[0].remove();
    notes[1].remove();

    // Keep the change.
    balances[msg.sender].insert(input_note_sum - deposit_amount, { owner : msg.sender });

    /*****************************************************************************
     * NEW SYNTAX
     ****************************************************************************/
    // Now we specify a partial commitment, into which the bridge's
    // output asset_id and value can be written:
    // Creates:
    //    partial_commitment = 1 * X + alice_address * Y + 
    //                         owner=alice_address * C + salt * D
    // Note: the nonce (input_nullifier) isn't specifiable at this stage
    // (see later post on this topic) - that makes things fiddly.
    UTXO incomplete_balance_utxo = balances[msg.sender][?].insert(?, { owner: msg.sender });
    IncompleteCommitment incomplete_balance_commitment = incomplete_balance_utxo.partially_commit();

    // Having created the partial commitment, we can call a public function,
    // which can store this partial commitment:
    add_pending_deposit(asset_id, amount, incomplete_balance_commitment);
     
}

public add_pending_deposit(uint asset_id, uint amount, IncompleteCommitment incomplete_balance_commitment) {
    // Get the defi_interaction_nonce for this cohort of deposits:
    if (!current_defi_interaction_nonces[asset_id]) {
        current_defi_interaction_nonces[asset_id] = next_defi_interaction_nonce++;   
    }
    uint current_defi_interaction_nonce = current_defi_interaction_nonces[asset_id];

    // Keep a running total of amounts deposited
    total_pending_deposits[asset_id] += amount;    
 
    // Create a 'claim note' and push it.
    ClaimDatum claim_datum;
    claim_datum.amount_deposited = amount;
    claim_datum.input_asset_id = asset_id;
    claim_datum.incomplete_balance_commitment = incomplete_balance_commitment;
    
    claim_data[current_defi_interaction_nonce].push(claim_datum);
}

public submit_defi_interaction(uint asset_id) {
    // Not shown: make an L1 call depositing `total_pending_deposits[asset_id]`

    uint current_defi_interaction_nonce = current_defi_interaction_nonces[asset_id];
    
    // Store the total deposited in each 'claim datum':
    for (let i = 0; i < claim_data[current_defi_interaction_nonce].length; i++) {
        claim_data[current_defi_interaction_nonce][i].total_deposited = 
            total_pending_deposits[asset_id];
    }

    // reset pending data:
    total_pending_deposits[asset_id] = 0;
    current_defi_interaction_nonces[asset_id] = 0;
}

// Assuming a DeFi interaction took place on L1, and we can read a message
// in the L1->L2 inbox, which tells us the total_output and output_asset_id
public claim_for_all(uint defi_interaction_nonce) {
    // Not shown: reading the message inbox and
    // assigning total_output and output_asset_id to local vars in this function.

    // We'll push new balance commitments, following the claim:
    field[] new_balance_commitments;

    // Complete each value note commitment, one by one:
    for (let i = 0; i < claim_data[defi_interaction_nonce].length; i++) {
        claim_datum = claim_data[defi_interaction_nonce][i];
        
        uint proportion_of_output_owed = 
            (claim_datum.amount_deposited / claim_datum.total_deposited) *
                total_output;

        // Complete the commitment, with new proposed syntax:
        field new_balance_commitment =
            claim_datum.incomplete_balance_commitment.complete({
                mapping_key_2: claim_datum.output_asset_id,
                value: proportion_of_output_owed,
            });

        /*****************************************************************************
         * NEW SYNTAX
         ****************************************************************************/
        // Trying to think of nice syntactic sugar for simply pushing
        // a commitment to the ABI:
        insert_commitment(new_balance_commitment);

        delete claim_data[defi_interaction_nonce][i];
    }
}
19 Likes
3

Q: do we need to define partial commitments at the language level with special syntax? What would need to change for this be delegated to a user-written Noir library?

15 Likes
4

Had a discussion w. Mike about this.

Simplest “solution” to this issue is not to implement anything! The goal here is to reproduce the Aztec Connect defi interaction circuits. However if one requires the claim circuit proof to be computed by a user and not an untrusted third party, all of these issues disappear. Perhaps that’s completely reasonable for a V1.0 release.

Longer term if we want to support using/abusing the additively homomorphic nature of state commitments, we need some special syntax that highlights the fact that doing this is very low-level work that can go pear-shaped very quickly.

i.e. directly adding a commitment to the state tree is similar to, in Ethereum, directly calling the SSTORE opcode. It would highlight the dangers/risk for developers in a manner familiar to them if we borrowed their inline assembly syntax e.g.

function doSomethingDangerous()
{
  inline_acir {
   insert_commitment(...};
  }
}
15 Likes
5

Just thought: gas rebates to anonymous users will require partial commitments. So we will need some syntax to support adding points to Pedersen commitments.

  • User ‘withdraws’ private tokens equal to the gas limit * gas price to the Gas Payment contract.
  • User also provides a partial commitment, which is stored in the contract.
  • Sequencer, in order to pay the gas rebate, ‘completes’ the commitment with the value ((gas_limit - gas_used) * gas_price)
3 Likes
6

About Pedersen hashing vs Pedersen commitments:

As per my discussion with Zac, I like the idea of having a separate Pedersen commitment gadget and use Pedersen hashing (lookup-based) only for Merkle hashing. We didn’t have this distinction in TurboPlonk. There’s two ways we can do Pedersen commitment without using lookup tables in UltraPlonk:

  1. Use TurboPlonk Pedersen gates to compute Pedersen commitments (this is not very efficient, if we want to hash 30 scalars, it should cost us 30x128~4000 gates)
  2. If we can cap up the number of generators the users can use, we can lookup a * G_i for a given scalar a and then use the EC point addition gate to compute the result.

Both of these have trade-offs we will have to make.

2 Likes