On Note Discovery and Index Coordination

[nventuro]

Below are some musings that arose from discussions with @spalladino on how the current note discovery scheme could be made more robust in terms of tag index coordination from the basic model we have today.

Note Discovery and Indices Today

The current note discovery scheme relies on tags being computed deterministically by both sender and recipient after agreeing on a shared secret by hashing the secret with an index counter. Both sender and recipient have to keep their counters in sync for note discovery to work: if the sender emits logs with indices that are too high, the recipient may not find those as it will only be looking for tags associated with smaller indices. Additionally, the sender must not repeat indices as that will cause a privacy leak by linking two sets of notes and transactions.

The initial version of note discovery will be relatively simple: the sender will only ever increase its indices and keep track of the last one it used, and the recipient will search for tags with increasing indices and keep track of the largest one it’s seen.

This simple mechanism easily results in problematic situations due to no fault of either party: a sender may send two transactions and have the first one revert, creating a gap in the received indices, or these two transactions may be mined out of order, creating both a temporary gap and a perceived decreasing index.

The current plan is to have the recipient be lax, and search not just for the next expected index but also for indicest past that (to account for gaps) and below that (to account for perceived decreasing indices). The sender will check against the node for the largest index and use that if it’s larger than its copy (to be able to migrate accounts to other devices), and the recipient will reset all indices if it ever detects a chain reorg.

A Path Forward

What’s been described above suffices for early releases, but is not robust enough for production usage. There’s big risk of a sender using indices too low or high, resulting in undiscoverable notes. Low indices could potentially be recovered if the recipient forced an index reset, but high ones can only really be fixed by sending more notes or increasing the recipient search window size. This led us to work on a better scheme.

We propose that the app circuits notify the PXE whenever an index is added. PXE will then store the associated transaction alongside the used index in its database, and then produce an index status based on the status of the transaction. A potential list of statuses might be:

1. free: unused for any tx
2. sent: the tx has been broadcast but not included in a block
3. mined/proven: the tx has been included in an L2 block that is not yet L1-finalized
4. finalized: the tx block epoch has been L1-finalized
5. dropped: the tx was sent but never mined, and the tx max-block-number has expired.

Statuses typically progress to finalized as time goes by (assuming both chains are finalizing). Reorgs can cause txs go to from e.g. mined to sent. Because this happens on chain, both the sender and recipient will eventually agree on the status of these transactions (the recipient will find them as they are the txs that include tagged logs).

The main idea once we have this is the following: the sender will refrain from using more indices if the index to claim is more than some amount N of slots away from the first non-finalized index. In order words, there can only be N in-flight tags at any point in time. This might seem restrictive, but we need to consider that tags are per (sender, recipient, app) tuple, and transactions get finalized after ~50 minutes in the worst case.

The one instance in which multiple tags might be required is when interacting with oneself (since e.g. token transfers to any recipient trigger change notes), but since in that case we’re both sender and recipient we don’t really need that much help coordinating, and we could special-case it.

Because the recipient knows about N, it knows that it never needs to look for more than N tags after the first unfinalized index, and given sufficient time (for txs to finalize) all notes will be found without any on-chain action from neither sender nor recipient.

Known issues

Mined transactions might revert, but we still should not use these indices. Even if the reverted tx is finalized, the tag is still publicly available as part of the TxEffects of the private component of the reverted transaction, which means that reusing it would link the two transactions. Perhaps the node should also track these, so that the recipient can know to skip them.

Expired sent transactions that were never mined are more problematic: they will never go on-chain (since they’re invalid), but some people may have seen them and therefore their tags, given we did broadcast them. Do we reuse the indices and risk linking? The alternative is to somehow communicate to the recipient that they should ignore some index, but this needs to be done over an empty transaction, so that it is not linked to anything else.

Finally, this doesn’t really help when sending transactions at the same time from multiple devices. I don’t think there’s much we can do about that really - we’re doing a best-effort approach without any out of band communication by checking for mined transactions in the node (same as Ethereum wallets when choosing a nonce), and anything beyond that seems too complicated.

Disclaimer

The information set out herein is for discussion purposes only and does not represent any binding indication or commitment by Aztec Labs and its employees to take any action whatsoever, including relating to the structure and/or any potential operation of the Aztec protocol or the protocol roadmap. In particular: (i) nothing in these posts is intended to create any contractual or other form of legal relationship with Aztec Labs or third parties who engage with such posts (including, without limitation, by submitting a proposal or responding to posts), (ii) by engaging with any post, the relevant persons are consenting to Aztec Labs’ use and publication of such engagement and related information on an open-source basis (and agree that Aztec Labs will not treat such engagement and related information as confidential), and (iii) Aztec Labs is not under any duty to consider any or all engagements, and that consideration of such engagements and any decision to award grants or other rewards for any such engagement is entirely at Aztec Labs’ sole discretion. Please do not rely on any information on this forum for any purpose - the development, release, and timing of any products, features or functionality remains subject to change and is currently entirely hypothetical. Nothing on this forum should be treated as an offer to sell any security or any other asset by Aztec Labs or its affiliates, and you should not rely on any forum posts or content for advice of any kind, including legal, investment, financial, tax or other professional advice.

[Jan]

This post is unrelated to the solution above as it deals with constrained tagging while the above relates only to unconstrained tagging.

Implementing onchain non-interactive handshaking approach

After having discussion with Mike, Sean and others I decided that it would make sense to go ahead and implement the onchain non-interactive handshaking approach because:

1. It’s the solution that is the easiest to use for devs as it doesn’t require offchain interaction (you just call a tagging contract, pass in a specific flag to note/event emission functions and you are good),
2. it’s also most likely the easiest solution to implement as it doesn’t force us to somehow associate signing keys with an account.
3. This solution being the least scalable of all (it requires everyone to brute force handshaking logs) is fine as it will take time for the activity to pick up on the network and it’s quite likely that once this becomes a problem we will have learnt a lot of new information that will make the tradeoff space much clearer.

So how does it work?

STEP 1: Emitting handshaking log and nullifier

A wallet figures out whether a sender needs to handshake with a recipient or if it already has been done → if it hasn’t been done it will insert a call to the canonical Handshaker contract as the as the first call in the app payload:

Handshaker::handshake(recipient, hidden_sender)

This is a semi-pseudocode of the Handshaker contract:

#[aztec]
contract Handshaker {
    #[private]
    fn handshake(recipient: AztecAddress, hidden_sender: bool) {
        let sender = context.msg_sender();
        let sender_to_include_in_message = if hidden_sender {
            AztecAddress::zero()
        } else {
            sender
        };

        let shared_tagging_secret_key = unsafe { random() };
        let shared_tagging_public_key = shared_tagging_secret_key * G;

        let recipient_message_plaintext = [sender_to_include_in_message, shared_tagging_secret_key];
        let recipient_message_ciphertext = encrypt(recipient_message_plaintext, recipient);

        // We send a message for the sender as well because we want this to be resistant against the "vicious Mike
        // throwing your laptop into the ocean" attack (I think we'll be able to remove this once we have proper PXE
        // backups)
        let sender_message_plaintext = [recipient, shared_tagging_secret_key];
        let sender_message_ciphertext = encrypt(sender_message_plaintext, sender);

        // We need to call this oracle function to add the handshake to sender's PXE because we need the handshaking
        // secret to be available in the same tx and not after the tx flies through the network.
        add_shared_tagging_secret_key(sender, recipient, shared_tagging_secret_key);

        // The final ciphertext is the concatenation of the recipient and sender ciphertexts.
        let message_ciphertext =
            array_concat(recipient_message_ciphertext, sender_message_ciphertext);

        // We compute and emit the handshake commitment to be able to later on prove that we've handshaked with this
        // recipient. Handshaking is costly so we want the handshake to be valid in both directions and hence we sort
        // the addresses.
        let (address_0, address_1) = crate::util::sort_addresses(sender, recipient);
        let handshake_nullifier = poseidon2_hash([
            "AZTEC_NR::HANDSHAKE_SEPARATOR",
            shared_tagging_public_key.x,
            shared_tagging_public_key.y,
            address_0,
            address_1,
        ]);
        context.push_nullifier(handshake_nullifier);

        // We need to emit the log in public because we need the log contract address to be public for everyone to know
        // what logs to brute-force.
        Handshaker::at(context.this_address())._emit_handshaking_log(message_ciphertext).enqueue(
            &mut context,
        );
    }

    #[public]
    #[internal]
    fn _emit_handshaking_log(message_ciphertext: [bytes; SOME_LENGTH]) {
        emit_log(message_ciphertext);
    }
}

STEP 2: Recipient and sender discovering handshake

1. A contract function is being simulated and a aztec::messages::discovery::discover_new_messages(contract_address) is called,

2. in the oracle handler, before this.executionDataProvider.syncTaggedLogs(contractAddress) is called we would call syncTaggingSecrets() that would:

3. load last_synced_tagging_secrets_block and get all the public logs since that block until the latest synced PXE block node.getPublicLogs(from: last_synced_tagging_secrets_block, last_block_synced_by_pxe, HANDSHAKER_CONTRACT_ADDRESS),

4. we would brute force decrypt both sender and recipient ciphertexts in the logs in TS and add the resulting shared_tagging_secret_key to PXE. (I am aware decrypting in TS here is ugly but we need it to be fast and it’s fine to enshrine the encryption because the tagging contract is enshrined as well.)

STEP 3

STEP 3.a: Tagging for the first time

1. We get the shared_tagging_public_key by calling a newly introduced oracle get_shared_tagging_public_key(sender, recipient, hidden_sender)

2. we sort the addresses (just like in the Handshaker) and prove the handshake commitment exists: prove_nullifier_inclusion(compute_siloed_nullifier(HANDSHAKER_CONTRACT_ADDRESS, poseidon2_hash([“AZTEC_NR::HANDSHAKE_SEPARATOR”, shared_tagging_public_key.x, shared_tagging_public_key.y, address_0, address_1])));

3. we get let shared_app_tagging_secret = context.request_shared_app_tagging_secret(shared_tagging_public_key.hash()). This requires implementing the request_shared_tsk method on context and modifying PXE such that it feeds the correct shared_tagging_secret_key to the kernel circuits for the key validation request,

4. we compute let directional_shared_app_tagging_secret = poseidon2_hash([shared_app_tagging_secret, recipient]);,

5. we compute the tag as poseidon2_hash([directional_shared_app_tagging_secret, 0])

6. we compute and emit the let tag_nullifier = poseidon2_hash(“AZTEC_NR::TAG_SEPARATOR”, sender_nsk_app, recipient, directional_shared_app_tagging_secret, index = 0); (–> the sender_nsk_app hides the contents of the nullifier, whilst keeping it deterministic)

7. we increment the index in PXE by calling newly introduced oracle increment_shared_app_tagging_secret_index(shared_app_tagging_secret) (realized this is not necessary, nor desirable, because we can brute force the index in PXE in step 3.b → this will also makes it resistant to “vicious Mike throws your laptop into the ocean” attack)

STEP 3.b: Tagging for subsequent rounds

1. We call a newly introduced let [directional_shared_app_tagging_secret, last_index] = get_last_tag_nullifier_preimage(sender, recipient, hidden_sender) oracle that brute forces the index (no key validation request is needed now because the shared_app_tagging_secret has been loaded from the preimage) and we prove its inclusion,

2. we compute the tag as poseidon2_hash([directional_shared_app_tagging_secret, last_index + 1])

3. the tag nullifier is computed and emitted tag_nullifier = poseidon2_hash(“AZTEC_NR::TAG_SEPARATOR”, sender_nsk_app, recipient, directional_shared_app_tagging_secret, last_index + 1);

Implementation of 3.a and 3.b in one function:

fn get_next_tag(
    sender: AztecAddress,
    recipient: AztecAddress,
    hidden_sender: bool,
    context: &mut PrivateContext,
) -> Field {
    let shared_tagging_public_key = get_shared_tagging_public_key(sender, recipient, hidden_sender);

    let sender_npk_m = get_public_keys(sender).npk_m;
    let sender_nsk_app = context.request_nsk_app(sender_npk_m.hash());

    // We call the is_first_time_tagging oracle function to determine if this is the first time tagging
    // for [sender, recipient, hidden_sender] inputs. The function computes the tag nullifier with index
    // 0 and checks if it exists in the nullifier tree.
    let first_time_tagging: bool = is_first_time_tagging(sender, recipient, hidden_sender);

    let (nullifier_preimage, app_to_silo_with, directional_shared_app_tagging_secret, index) = if first_time_tagging {
        // Sort addresses to reliably get bi-directional handshake commitment. We do that in an unconstrained function
        // and then we constrain the result to optimize constraints.
        let (address_0, address_1) = sort_addresses(sender, recipient);

        let handshake_nullifier_preimage = [
            "AZTEC_NR::HANDSHAKE_SEPARATOR",
            shared_tagging_public_key.x,
            shared_tagging_public_key.y,
            address_0,
            address_1,
        ];

        let shared_app_tagging_secret =
            context.request_shared_app_tagging_secret(shared_tagging_public_key.hash());
        let directional_shared_app_tagging_secret =
            poseidon2_hash([shared_app_tagging_secret, recipient]);

        (
            handshake_nullifier_preimage, HANDSHAKER_CONTRACT_ADDRESS,
            directional_shared_app_tagging_secret, 0,
        )
    } else {
        // Get the app tagging secret and last index from oracle
        let (directional_shared_app_tagging_secret, last_index) =
            get_last_tag_nullifier_preimage(sender, recipient, hidden_sender);
        let previous_tag_nullifier_preimage = [
            "AZTEC_NR::TAG_SEPARATOR",
            sender_nsk_app,
            recipient,
            directional_shared_app_tagging_secret,
            last_index,
        ];

        (
            previous_tag_nullifier_preimage, context.this_address(),
            directional_shared_app_tagging_secret, last_index + 1,
        )
    };

    let siloed_nullifier_to_prove =
        compute_siloed_nullifier(app_to_silo_with, poseidon2_hash(nullifier_preimage));
    prove_nullifier_inclusion(siloed_nullifier_to_prove);

    let tag_nullifier = poseidon2_hash([
        "AZTEC_NR::TAG_SEPARATOR",
        sender_nsk_app,
        recipient,
        directional_shared_app_tagging_secret,
        index,
    ]);
    context.push_nullifier(tag_nullifier);

    let tag = poseidon2_hash([directional_shared_app_tagging_secret, index]);
    tag
}

pub fn sort_addresses(
    address_a: AztecAddress,
    address_b: AztecAddress,
) -> (AztecAddress, AztecAddress) {
    let (address_small, address_big) = sort_addresses_internal(address_a, address_b);
    assert(address_small.to_field() < address_big.to_field());
    assert(address_small.eq(address_a) | address_small.eq(address_b));
    assert(address_big.eq(address_a) | address_big.eq(address_b));
    (address_small, address_big)
}

unconstrained fn sort_addresses_internal(
    address_a: AztecAddress,
    address_b: AztecAddress,
) -> (AztecAddress, AztecAddress) {
    if address_a.to_field() < address_b.to_field() {
        (address_a, address_b)
    } else {
        (address_b, address_a)
    }
}

STEP 4: Recipient discovering notes

It works the same as until now with the difference that this.executionDataProvider.syncTaggedLogs(contractAddress) syncs logs also based on the constrained tags. Note that this will require us to modify this function. The constrained tags code block of the function will not have to deal with ugly window approach as the tags are guaranteed to be continuous!

DOS attack

Problem of this solution is that it allows anyone to effectively add a sender to PXE which is a DOS vector!

Potential solutions:

1. Enforcing strict handshaking secret expiration upon registration in the HandshakingContract,
2. making the sender pay when registering a handshake in the HandshakingContract,
3. somehow detecting spam in PXE (this seems unfeasible because we need this to be very reliable - otherwise you could just not find legitimate notes!),
4. when a new handshake is found have the user provide feedback whether he wants to add the sender to PXE (this could also be done at some point later).

We will want to expose this the wallet as the wallet will most likely have a valuable info of who is a legitimate sender as that’s where the interaction starts. It has been agreed upon that it’s fine to not think about this in the initial implementation as it’s solvable.

Note
The contents of this post were originally in this PR.