aztec3-speccing-bookPROPOSAL
Author: Zac
TODO: put together some data structure that allows contracts to check for the non-existence of data (e.g. a blacklist)
IMPORTANT: this document is supplemented by a Discourse conversation here
Defining semantics to manipulate private state comes with unique difficulties due to its encrypted nature and the fact that private state is UTXO based.
Unlike in Aztec 2, we cannot anticipate the data type of the state value.
If it is a simple numeric type, the contract developer may wish to have a private state slot represent an aggregateable value. It may be aggregateable but only depending on conditional logic.
If it is a struct, perhaps the developer may wish to aggregate subsets of the struct into a single value for a given decryption key.
There will be other usage patterns for UTXOs that develop over time that we cannot predict.
UTXOs add significant complexity to developing and managing a private dapp. Question is: who pays?
The proposal is that we place the complexity burden on contract developers as far as is possible. They are the entity that understand the requirements of their contract and its logic. The protocol's resposibility is to provide clean, easy to express semantics to manipulate UTXOs such that their nature can be abstracted away from app developers.
These are the two 'win' conditions we must hit under this proposal:
All contract state required by a dapp can be accessed via contract getter functions.
UTXO commitments are never passed in as input parameters to an external-facing contract function
As an example of what not to aim for; in Aztec Connect the user must directly supply input/output note commitments to the join-split function.
A private state commitment is defined by the following:
Private state variables can be represented in one of two forms:
mapping(address => Object)mapping(address => UArray(Object))TODO: How do we initialize singleton variables? (i.e. cannot use patter "pull old value out of the state tree and nullify it, there is no old value")
For a singleton variable, the explicit assumption here is that only the user will be making modifications (e.g. the Object type could be a struct, may, dynamic array etc.)
The Object is the type of the storage variable itself (e.g. u64). If it does not fit into a single state commitmet, the variable is split across multiple state commitments (and storage slots).
Simulating arrays is difficult because we need to enable users who are not the array owner to be able to insert objects into the array.
Beause of this, we cannot track an array length (without leaking information, as everybody would need to know it to perform an insert)
Without an array length, we cannot index specific array elements (the user may not know at which index they are inserting into).
insert into the arrayremove array elementsreplace array elements (syntactic sugar that removes an array element and inserts another in its place)A contract function can request a fixed number of elements from the unbounded array.
We can use rust-style Option semantics to represent the fact that the array elements may be either 'real' or 'gibberish' notes.
(pseudocode)
function get(uint number, function SortFunction, function FilterFunction) returns [Option<ObjectType>; number]
The returned array elements are wrapped in a form of Option type with is_some, is_none methods that return boolean values depending on whether the element exists.
The SortFunction defines the ordering used. The function declaration is (pseudocode):
SortFunction(ObjectType left, ObjectType right) returns bool
Function returns true if left is ordered before right.
The FilterFunction acts similarly to the SortFunction and is used to omit UTXOs from the returned array:
FilterFunction(ObjectType v) returns bool
e.g. can be used to omit zero-valued notes.
If no sort/filter functions are provided, default behaviour is to return notes ordered by their position in the state tree.
Q: Is sort, filter sufficient to build up higher-level abstractions like map, reduce?
Q: Is it too confusing for SortFunction and FilterFunction to add constraints? The constraint conditions is weaker than the conditions that apply when operating natively (could call them SortDirective, FilterDirective to make their functions clearer)
The sort/filter functions generate constraints to ensure that the supplied UTXO objects match the criteria.
However we cannot ensure that UTXOs that would have passed the checks have been ommitted.
e.g:
Alice has UTXO's with values [0, 1, 2].
The contract has a getter function that gets 2 UTXOs that are sorted from lowest to largest.
All of
[0, 1],[1, 2],[0, 2]can be supplied as witnesses that satisfy the constraint checks.
It is impossible to enforce sort/filter logic across all UTXOs without iterating over all UTXOs in-circuit, which is not practical. We need to be able to express these limitations clearly to devs as this is a potential security footgun.
We want to be able to support the creation of 'getter' methods that can be used by apps to extract required contract data (e.g. a user's balance of a shielded token).
This requires a method that can get all of a user's notes for a given variable.
We can do this by supporting simulated functions in Noir. These are functions that, when compiled, produce ACIR++, but are not compiled into constraints. i.e. you cannot 'call' these functions in a real transaction.
Simulated functions are not bounded by some Noir rules such as no unbounded loops (this requires extra ACIR++ opcodes that are only valid in a simulated context e.g. conditional branching)
Simulated functions can also access a get-all method on storage variables that returns a vector/dynamic array
get_all(function SortFunction, function FilterFunction) returns Vec<ObjectType>
TODO: use Noir syntax! This uses Solidity-style pseudocode (with rust's Option syntax grafted on…)
private mapping(address => bool) blackList;
function private addToBlackList()
{
blackList[msg.sender] = true;
}
function private checkNotOnBlackList()
{
bool isOnBlackList = blackList[msg.sender];
require(isOnBlackList == false);
}
private mapping(address => UnboundedArray<uint256>) _notes;
private antiset(address) _badPeople;
bool thing_init = false;
function private addBadPerson(address baddie)
{
_badPeople.insert(baddie);
}
function private checkNotBad()
{
require(_badPeople.notPresent(msg.sender));
}
function private gimmeThing()
{
_thing[msg.sender] = 10;
checkInit();
}
function public checkInit()
{
require(thing_init == false);
thing_init = true;
}
o
/**
* combines the user's 2 highest-valued notes into a single note.
*/
function consolidate()
{
[Option<uint256>; 2] storage notes = _notes[msg.sender].get(2, sortNotes, filterNote);
require(notes[0].is_some() && notes[1].is_some(), "not enough notes to consolidate");
notes[0].replace(notes[0].unwrap() + notes[1].unwrap());
// 2 output notes. Could call 'remove' to produce only 1 ouput note.
notes[1].replace(0);
}
/**
* creates a j-s transaction that gives a note to 'to' worth 'value'
*
* Will throw if 2 largest notes are insufficiently large
*
* N.B. we could conditionally consolidate notes here if needed but would increase tx costs
*/
function privateSend(address to, uint256 value)
{
[Option<uint256>; 2] storage notes = _notes[msg.sender].get(2, sortNotes, filterNote);
uint256 valueSum = notes[0].unwrap_or(0) + notes[1].unwrap_or(0);
require(valueSum >= value, "insufficient note values. May need to consolidate");
notes[0].replace(valueSum - value);
// TODO: might need to create a specific option type for an optional-storage var instead of Option. Would be good to have a direct `remove` method on the option that produces a gibberish nullifier if the UTXO is gibberish
notes[1].remove();
// TODO: define syntax that declares the msg seder is not expected to know the viewing key to _notes[to] (e.g. some 'unknown' keyword)
_notes[to].insert(value);
}
/**
* Returns the user's shielded balance.
* Is a simulate-only function that cannot be executed as part of a tx
**/
function getShieldedBalance() simulated returns (uint256)
{
// can only call get_all in simulated functions
uint256[] storage notes = _notes[msg.sender].get_all(sortNotes, filterNote);
uint256 balance = 0;
// can have unbounded loops in simulated functions
for (uint256 i = 0; i < notes.length; ++i)
{
balance += notes[i];
}
return balance;
}
/**
* Computes number of note consolidations required before a user can send a note worth `target`.
* Is a simulate-only function that cannot be executed as part of a tx
**/
function numConsolidationsForSend(uint256 target) simulated returns (uint256)
{
uint256[] storage notes = _notes@self.get_all(sortNotes, filterNote);
// uint256[] storage notes = _notes[msg.sender].get_all(sortNotes, filterNote);
require(notes.length > 0, "insufficient balance");
uint256 count = 0;
uint256 consolidatedValue = notes[0];
for (uint256 i = 1; i < notes.length; ++i)
{
if (notes[i] + consolidatedValue >= target)
{
return count;
}
consolidatedValue += notes[i];
count++;
}
require(false, "insufficient balance");
}
The get method used to extract state adds a significant complexity to ACIR++; the algorithm that is executed during the simulation is different to the algorithm that is constrained when generating a circuit.
getsortFunction and filterFunction functionsnumber, add sufficient fake UTXOsnumber-sized arraygetnumber of UTXO objects as witnessessortFunction and filterFunction functions(TODO: should be moved to protocol architecture spec)
If we want the Noir++ to support 'antisets', datasets where users can prove the non-existence of a key.
We can expose a nullifier set as a basic primitive, but secure non-membership checks require specific a pattern is followed due to the following security requirement:
A unique nullifier can only produce one non-membership check
Non-membership checks are performed by exposing nullifiers to the rollup provider, who then performs the non-membership check into a nullifier set (to avoid race conditions. TODO link to a nullifiers primer)
Repeated exposure of the same nullifier reveals part of the transaction graph; that nullifier can becomes an identifier.
Each antiset is assigned a state slot \(slot_s\) and a nullifier slot \(slot_n\)
An antiset nullifier for a key \(k \in \mathbb{F}\) requires a nullifier \(nonce_k\) and is defined as:
\[ H(k, nonce_k, slot_n, contract) \]
(contract = contract address)
The initial nullifier for a given key \(k\) uses a nonce value of \(0\) i.e. the following nullifier is added:
\[ H(k, 0, slot_n, contract) \]
(as with all nullifier insertions, the inserted nullifier must also pass a non membersihp check)
For an input key \(k\) and \(nonce_k\), the circuit requires a non-membership check over the nullifier \(H(k, nonce_k, slot_n, contract)\)
If \(n > 0\) the circuit must also prove the existence of a leaf in the state tree whose value is
\[ H(k, nonce_k, slot_s, contract) \]
The circuit adds the following leaf to the state tree:
\[ H(k, nonce_k + 1, slot_s, contract) \]
The circuit adds the following nullifier to the nullifier set:
\[ H(k, nonce_k + 1, slot_n, contract) \]
A non-membership check requires adding 1 note to the state tree and 1 note to the nullifier set i.e. not read-only!
If Alice wishes to add Bob to an antiset, she must choose a nullifier key \(k\) that corresponds to Bob's identity.
This is not hiding. [TODO explain how hiding can be done in a semitrusted setting]
-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe