Aztec currently doesn’t have an implemented multisig wallet. We did some research on the possibilities for an Aztec multisig, and we’re not gonna proceed further with its development. The following forum post is an approximate dump of the research and findings.
Overview
An access structure is a complete definition of which sets of participants or entities are granted access to a resource. Those sets are in turn called qualified sets.
Access control for account contracts can be split roughly in authorization and state inspection. Furthermore, different blockchains offer different degrees of mutability for these access structures. For instance, Bitcoin multisigs cannot change the associated public key, and hence the access structure can only become looser, whereas Ethereum multisigs can change signers and thresholds arbitrarily.
In this post, we expand on this topic with considerations specific to Aztec, evaluating trade-offs and their dependence on possible alterations to the Aztec protocol. It’s structured as follows:
- Context: Existing solutions for other blockchains
- Context: current Aztec accounts
- Aztec multisig
- Technical dive
- Computations using the
ivsk - UX of proposal
- Conclusions
Context: Existing solutions for other blockchains
Multisigs are accounts the operation of which requires more than one signature. Most or all currently used multisig protocols implement a threshold scheme. A “t out of n” threshold scheme is a scheme where a set of n participants and an integer threshold t is defined, such that any subset of t or more participants is granted access.
Bitcoin
Bitcoin has many multisig solutions. We’ll focus on two. Since Bitcoin addresses are a commitment to the (stateless) unlocking mechanism, none of these allow for the modification of the access structure.
FROST
Individual Bitcoin accounts rely on the OP_CHECKSIG opcode, which takes a public key and a Schnorr signature of the TX (ECDSA if it’s legacy) as input and returns whether the signature is valid for the provided public key.
FROST is a threshold signature scheme that produces a public Schnorr key and n shares (or shards) of the corresponding private key (Adi Shamir - How to share a secret), in such a way that t participants can produce a valid normal Schnorr signature for any message, without needing to reconstruct the underlying private key in the process.
These kind of multisig are indistinguishable from normal wallets from the outside, but they require heavier off-band communication.
OP_CHECKMULTISIG
There’s also an OP_CHECKMULTISIG opcode that takes
- the number of signers
n npublic keys- the threshold parameter
t tsignatures
as input, and returns whether thetsignatures are valid signatures bytdistinct signers for the transaction.
These kind of multisigs are not only transparent to the fact that they’re a multisig, but also reveal the access structure and which signers approved each transaction.
Ethereum
Ethereum uses ECDSA signatures for transaction validation. Since there are threshold schemes for ECDSA signatures as well, their use would allow for the construction of a multisig that’s indistinguishable from normal EOAs analogous to FROST-based Bitcoin multisigs.
Most interestingly though, since each contract’s code and the manipulation of their state is arbitrary on Ethereum, this allows for the construction of more malleable multisigs. In contrast, Bitcoin multisigs, as well as any multisig based on a cryptographic scheme, have a constant set of participants and threshold, which only allows access structure changes that increases qualified sets, as new cryptomaterial can be produced, but old cryptomaterial cannot be assumed to be deleted.
The most well known example of programmable multisigs in Ethereum are Safe wallets. Amongst more complex behaviour, they allow removing or adding signers, as well as changes to the threshold parameter.
Monero
The previously reviewed blockchains are public state, meaning state inspection is granted to anything. So, access control is only available for authorization.
Monero, like Aztec, faces a distinct challenge with respect to state inspection, as it requires yet one more secret to restrict state inspection. In the case of Monero, this is the viewing key. When a note is made for a Monero wallet, it gets encrypted to the wallet’s public viewing key, and the cyphertext is logged publicly. The receiver then performs trial-decrypt on every cyphertext for note discovery.
Monero multisigs deal with this restriction by simply sharing the viewing key amongst all the participants. For spending, it uses a cryptographic threshold scheme over the spending key like the ones we’ve seen before.
Generalities and summary
All of these options require a private communication channel between the participants, to at least communicate the transaction signing intent.
The following table sums the previous information up
| Blockchain | Method name | Public signers | Can tighten access structure |
|---|---|---|---|
| Bitcoin | FROST | No | No |
| Bitcoin | OP_CHECKMULTISIG |
Yes | No |
| Ethereum | Safe | Yes | Yes |
| Monero | - | No | No |
Context: current Aztec accounts
Aztec contracts have three protocol-enshrined keys:
- Nullifier key for note spending
- Incoming viewing key, used for deriving the address key
- Address key for note discovery and decryption
Of these, the nullifier and incoming viewing keys can be chosen arbitrarily at contract deploy/declaration time, whereas the address key is a deterministic commitment to the entire contract (including code, private function verification keys, and nonce).
The final contract address is a commitment to all of this, as depicted in this picture.
A more in-depth explanation on those keys can be found in the docs’ keys section.
Authorization control
Since Aztec has native account abstraction, Aztec account contracts are usually contracts for which an entrypoint function is defined, which performs access control before executing the payload. Further, well defined app contracts will ask for an authwit before allowing further actions on behalf of the user, such as transferring a token or emitting a vote. The implementation of the authwit mechanism is left up to the account contract developer.
In the standard Aztec Schnorr account, the account’s public signing key is privately stored, and authorization is done by expecting a valid Schnorr signature for the action, which is provided via oracle.
The nullifier key acts as further authorization control, as it’s required for the nullification of notes.
State inspection control
This is performed by using the address key.
- Log encryption: the sender picks an ephemeral key pair (
eskandepk) and AES128-encrypts the log to the Elliptic-Curve Diffie-Hellman shared secret constructed with theeskand the recipient’s public address key (their Aztec address). Depending on the contract’s logic, this may or may not be constrained. - Log tagging: The receiver’s and sender’s address private and public keys are used through Elliptic-Curve Diffie-Hellman to generate a shared secret bound to the sender-receiver pair, which is then mixed together with an incremental nonce and the app contract that emits the log in order to construct random-looking tags which the recipient can use for note discovery. This is currently not constrained.
The on-chain side and the device side
Account contracts require two pieces of code:
- On-chain Noir code for the account contract
- Code that runs on the device to ask the user for confirmation and to produce the corresponding authwits and feed them via oracle calls
E.g., as mentioned earlier, the Schnorr account’s authorization code expects a Schnorr signature of the “outer hash” (a commitment to the authorized payload). Thus, correspondingly, the TypeScript code for the Schnorr account contract performs the Schnorr signature when requested for an AuthWit.
Aztec multisig
By virtue of being both private and Turing-complete, Aztec brings forth the possibility of implementing a multisig that simultaneously preserves signer anonymity and allows for the tightening of the inspection and authorization access structures, which needn’t even be the same structures. However, the specifics regarding Aztec’s protocol-enshrined handling of inspection control make said tightening challenging, and call for work-arounds.
The following sections detail a possible approach to the construction of said multisig.
Technical dive
An Aztec multisig has to deal with the protocol-defined keys as well as the contract’s authorization, in order for the participants to perform authorization and state inspection, in a way that respects the required access structure. This access structure can ideally be made looser (by decreasing the threshold or increasing the number of participant) or tighter, by increasing the threshold or removing a participant.
As we’ll see, it is tightening the access structure that’s actually harder.
Authorization
Since account abstraction allows running arbitrary code in the entrypoint, implementing threshold authorization schemes is easy and flexible from the smart-contract perspective.
On one hand, the already existing Schnorr account contract can be used in combination with the FROST protocol to perform multisig transactions. If the signing key is made mutable, the account can then include another entrypoint that, upon consensus, updates this signing key. This allows changes to any parameters of the threshold scheme. The development and communicational complexity is offloaded from Noir code to the device-side implementation of the FROST cryptographic protocol.
On the other hand, the account contract can be made so that instead of storing a single public key, it stores a set of valid signatures and an integer for the threshold, the on-chain code can perform the check for the signatures explicitly. This increases on-chain code complexity but decreases communicational overhead.
In both cases, every authwit that’s required by the transaction requires the production of t authwit shares. FROST authwit shares are numbers that don’t constitute themselves a valid signature, but are aggregated by the protocol in order to produce a valid final signature, while the other option’s authwit shares are indeed just valid Schnorr signatures.
The flow would be as follows:
- A single user communicates the intent to execute a TX to the other participants.
- Participants simulate the transaction, in order to see the side effects and, if they agree on the proposal, produce the required authwit shares.
- A prover is chosen to perform the proving in their hardware, and the authwit shares are sent to them. This prover can be anyone, and at a worse case scenario may choose not to prove the TX. If the authwit shares are instead broadcasted to everyone else, any participant can perform the proving individually.
Regarding the nullifier key, this can be safely shared amongst all participants. Holding the nullifier key as an outsider of the multisig (e.g. some who has been removed) doesn’t compromise authorization restriction, given that well formed contracts will ask for an authwit before mutating any state.
It does allow for the computation of a note’s nullifier, given its content. This opens the door to two attack vectors:
- Computing known notes nullifiers, in order to know when the multisig has spent them. This can be mitigated by re-emitting the notes.
- Brute-forcing over possible note values (e.g., 10 USD notes). This is not a concern if each note is accompanied by a proper random number.
State inspection
Note discovery and decryption is done through the enshrined address secret key (address_sk henceforth). This key itself is not arbitrary, but derived from contract data as follows:
The leaves that lead to the definition of partial_address pertain knowledge of the contract itself, and should thus be known by every participant of the multisig. The missing keys are:
ivsk: incoming viewing secret keyovsk: outgoing viewing secret key (obsolete)nsk: nullifier secret key
The derived value address_sk = pre_address + partial_address is the one used afterwards for all state inspection related computations. The nsk and ovsk (which is obsolete anyways) can be safely shared by all multisig participants, leaving us with the question of what to do with the ivsk and, consequently, the address_sk.
If the ivsk is generated and distributed to all multisig users, just like Monero, this forbids the removal of any participant from the state inspection access set.
For some use cases, this could be non-negotiable. E.g., a donation address may be stored in users’ address book and used blindly. Private treasury migration may also be risky in itself, even though it’s doable.
This can be resolved or mitigated in at least four ways:
- Protocol-level key rotation for the decryption key (
address_sk) - Produce the
ivskand perform access control inside a TEE - Produce the
ivskand perform access control using the TACEO network - Threshold-share the
ivskin the same way FROST threshold-shares a private Schnorr signing key.
Protocol-level key rotation would work the same way as class_id rotation (which uses the ContractInstanceRegistry), and would introduce a lookup cost to all transactions. Pondering such a decision is out of scope for this post.
TEE and TACEO multisigs would enforce access structure at the TEE or TACEO node level, and could actually be reduced to the task of doing the computations for a normal account contract afterwards. In both cases, trust is offloaded to the TEE vendor or the TACEO node network.
Threshold-sharing the ivsk in a t out of n threshold scheme allows for the removal of up to t-1 participants without them being able to collude in order to reconstruct the ivsk. After this, the computations required for normal account operation must be performed without reconstructing the ivsk in between. These computations are done in order to construct the address_sk, which is in turn used for log decryption and log tagging as explained in the Aztec account contracts recap. The address_sk wouldn’t be reconstructed either, but rather a t of n sharding of the address_sk can be computed from the t of n sharding of the ivsk. The details of those computations are expanded on in the appendix below.
These computations could be done leveraging TACEO’s modules for Multi-Party Computation (mpc-core and mpc-net) libraries, which allow for threshold computations for the operations required by the protocol.
Taking into account that t participants are required in order to use the secret as well, the combined restriction that the secret be usable and that it not be reconstructable by removed participants actually limits the number of expelled participants to min(t, n-t).
Computations involving the ivsk
In this section we review the computations involving the ivsk, in order to properly justify how the wallet would be set up and how it would operate under the hood.
These computations, in turn, involve the computation of many intermediate values, each of which will be assigned one of the following visibility values:
- Public: can be known by anyone
- Internal: can be known only by multisig members
- Private: can be known only by their individual owner
- Opaque: can’t be known by anyone
The graphs will reflect visibility level with the following colors
graph TD
style Public fill:#fff,color:#000
style Internal fill:#9c3,color:#000
style Private fill:#777,color:#000
Opaque
The variables’ visibility can always be demoted to a more public aspect.
Operations are represented as follows
graph BT
op1[[operation]] --> result
style op1 fill:#008b8b
parameter1 --> op1
parameter2 --> op1
With the exception of the multiplication times the group generator g, or projection (of a 2D group element) towards the x or y axes, which are denoted as follows
graph BT
field_element -- times g --> group_element
group_element -- .x --> x_coordinate
group_element -- .y --> y_coordinate
The details as to how the operations to be depicted (including the implicit visibility demotion) can be performed in a threshold way is out of scope for this post. The interested reader is encouraged to learn further from MPC documentation, of which TACEO’s background material or mpc-core are a good starting point.
Address derivation
In practice, an account contract’s address is computed as follows:
graph BT
ivpk --> keys_hash
other_public_keys --> keys_hash
partial_address --> pre_address
keys_hash --> pre_address
pre_address -- times g --> address
ivpk --> address
style ivpk fill:#fff,color:#000
style other_public_keys fill:#fff,color:#000
style keys_hash fill:#fff,color:#000
style partial_address fill:#9c3,color:#000
style pre_address fill:#9c3,color:#000
style address fill:#fff,color:#000
The incoming viewing secret key doesn’t enter any circuits directly, but rather through its public counterpart. The computation of the ivpk is performed as follows
graph BT
ivsk -- times g --> ivpk
style ivpk fill:#fff,color:#000
Log encryption and decryption
For encryption, the multisig generates an ephemeral Grumpkin secret-public key pair (esk, epk), and performs ECDH between this and the receivers public Aztec address to construct a shared secret. This secret is used to AES128 encrypt the plaintext.
In this instance, the prover has the freedom to choose the esk, so this value is identified as private. If encryption is constrained, the circuits ensure encryption is done properly. Otherwise, the multisig participants don’t have the certainty that encryption is done properly, but can send the plaintext off-band in order to make sure note delivery is performed correctly.
graph BT
mul[[mul]] --> shared_secret
esk --> mul
recipient_public_address --> mul
aes128[[aes128.encrypt]] --> log_cyphertext
shared_secret --> aes128
plaintext --> aes128
style mul fill:#008b8b
style shared_secret fill:#777,color:#000
style esk fill:#777,color:#000
style recipient_public_address fill:#9c3,color:#000
style aes128 fill:#008b8b
style plaintext fill:#9c3,color:#000
For decryption, the reverse process is done. The private input to ECDH is the discrete logarithm of the public address, i.e., the address_sk. This can be computed as follows, using the previously computed pre_address:
graph BT
add1[[add]] --> address_sk
style add1 fill:#008b8b
ivsk --> add1
pre_address --> add1
style pre_address fill:#9c3,color:#000
It is important that address_sk remain opaque after computation, as it’s the secret used to decrypt all logs. After doing this, ECDH can be used between the ephemeral public key epk and address_sk to recover the shared secret.
graph BT
mul[[mul]] --> shared_secret
epk --> mul
address_sk --> mul
aes128[[aes128.decrypt]] --> log_plaintext
shared_secret --> aes128
cyphertext --> aes128
style mul fill:#008b8b
style shared_secret fill:#9c3,color:#000
style epk fill:#fff,color:#000
style aes128 fill:#008b8b
style log_plaintext fill:#9c3,color:#000
style cyphertext fill:#fff,color:#000
The shared_secret can be safely made internal, as it’s only useful for that specific log, and all the current participants of the multisigs ought to be able to read it.
Tags
Tag computation is the most complex of the operations.
graph BT
pos1[[poseidon2]]
style pos1 fill:#008b8b
pos1 --> tag
app_tagging_secret --> pos1
recipient_public_address --> pos1
index --> pos1
pos2[[poseidon2]]
style pos2 fill:#008b8b
pos2 --> app_tagging_secret
app_address --> pos2
tagging_secret_point -- .y --> pos2
tagging_secret_point -- .x --> pos2
mul1[[multiplication]] --> tagging_secret_point
style mul1 fill:#008b8b
recipient_public_address --> mul1
address_sk --> mul1
style recipient_public_address fill:#9c3,color:#000
style app_address fill:#9c3,color:#000
style index fill:#9c3,color:#000
style tag fill:#9c3,color:#000
Here tagging_secret_point and app_tagging_secret remain opaque in the most conservative of cases. A compromise solution would demote the visibility of one of them, which would allow either computing all tags from a specific sender or all tags from a specific sender through a specific app respectively, even after removal.
UX of proposal
Communication channel
The multisig operation requires the following communication channels to be set up in order for the backend to perform the MPC magic described above
- E2E-encrypted communication between all participants
- A broadcast channel
How these are established and set up is out of scope for this post.
Multisig creation
- Creator chooses multisig parameters: signers, threshold, and
nsk, and privately communicates them to all participants. - Participants set up the communication channels.
- Backends generate a
tofnsharding of theivsk. - Backends compute (and distribute internally) the
ivpkwhich, together with the other public keys and code, allow them to compute the contract address required for deployment. - Participants generate and distribute a sharding of the
address_skfrom the sharding of theivskand the other internally known values. - Any of the participants deploys the Aztec contract.
Log discovery and decryption
- A participant broadcasts the intent to scan for notes coming from a specific sender through a specific app to the other participants. This translates into the need to compute tags for note discovery (a parametrizable amount of them)
- All remaining participants chose to approve or deny. If a threshold of approvals is reached, the backends perform the threshold protocol required to obtain the tags, which are then internally distributed.
- Backends scan the logs for the computed tags. When finding one, the backends broadcast the intent to decrypt the log.
- If a threshold is reached, the AES128 ephemeral shared key for the log is threshold-computed and distributed to active participants. As a design choice, the multisig backend can assume that if the user consents to tag production, then they also consent to log decryption.
- The final plaintext is distributed to all participants.
Proposal construction
Any participant may craft a proposal for a multisig action, amongst which there are:
- Tag computation, with parameters:
- Sender
- Contracts to listen to
- Numbers of tags to compute ahead
- Multisig parameters modification, with parameters:
- Signers to add
- Signers to remove
- New threshold
- Arbitrary transaction execution
The backend should deal with the communications required by the MPC protocol, querying the user for consent before the coordination of every one of these actions is started. In the case of transaction execution, the backend should also ask the user for consent for the AuthWits in the same way that a normal account contract would.
Conclusions
We’ve seen that out of the access control keys and methods, the nullifying key can be shared freely and authorization is completely flexible. The decryption secret (address_sk) is however constant, which prevents easy tightening of the inspection access structure.
The possible solutions or mitigations to this are:
- Allow viewing key rotation
- Use external resources to off-load custody of the viewing key and impose access control at the endpoints of that. The following resources are mentioned
- TEEs
- TACEO
- Use threshold secret sharing to reduce trust assumptions on individual users
Option 1 is optimal for this use case, but imposes tradeoffs whose exploration is out of scope for this research, and the decision ultimately depends on protocol management.
Option 2 is dependent on external resources and, as such, wouldn’t be a pure Aztec solution.
We delved further on option 3 and found it to be technically viable. What it allows is technically not an inspection access structure tightening, but under good parameters (high threshold, and high participation) and/or low requisites (low participant replacement) it allows for the practical removal of up to min(t, n-t) participants from the multisig.
The expected UX has been explored as well, and looks similar to what’s already available for Ethereum/Bitcoin multisigs.
Going forward
A proper analysis of market fit is still due, in order to understand what the priority for multisigs in Aztec should be, which in turn would aid decisions regarding either protocol-level key rotation, or continuing the development of the multisig through any of the mitigated paths.
The tools for building the currently-proposed mitigated multisigs are available, so a PoC could be a good starting point to verify the UX hypotheses.