Verifiable note encryption

[joebebel]

This issue is to add verifiable encryption to the output note encryption. This is necessary because VP-authorized shielded transactions are generated by third parties, and in the current design, that third party always has the option to discard the output note instead of distributing it. The only way to remove this option is to use verifiable encryption for certain fields of the output note.

This should be "opt-in" (as chosen by the VP) because it is not necessary for all transactions, and "opt-out" transactions should be able to avoid any and all potential side-effects from using verifiable encryption.

Practically, the address, value, and randomness commitment components of the note plaintext must be verifiably encrypted, and checked in the VP circuit. In the Orchard protocol, the diversifier is 88 bits, v is 64 bits, and rseed is 256 bits. Unfortunately this is larger than a 256-bit block, so some discussion of block cipher modes might be necessary.

1. We should implement and evaluate this verifiable encryption with both Poseidon and Blake2s.
2. We should evaluate both the performance impact on the circuit size, and also the performance of blockchain scanning

[joebebel]

I had been assuming the asset type would be ~256 bits long, but in the case of NFTs this might be too short (although the 64 bits allocated for v could be reused) so it's possible that we would need to encrypt more than 512 bits of note data.

[joebebel]

We decided output note encryption should go in the VP.

Tasks:

• [ ] Implement in-circuit output note encryption with ElGamal-type encryption
• [ ] Implement in-circuit Poseidon-based note encryption (or at least do some due-diligence on the approach)
• [ ] Implement out-of-circuit decryption for ElGamal-type encryption
• [ ] Implement out-of-circuit decryption for Poseidon-based encryption
• [ ] Compare and benchmark the in-circuit and out-of-circuit performance
• [ ] Document the encryption scheme used in the spec
• [ ] Make tests for the output note encryption scheme

[leontiad]

It would be beneficial for everyone stumbled upon to proposed solutions to have a short paragraph/scheme describing:

1. the problem we are trying to solve in a short way and then unwrapping it and why some other solutions do not work (knowing the requirements for example will clear our things)
2. an enumerated list of the workflow/architecture of the protocol in steps

[joebebel]

Context for this issue:

1. A user VP may, after reviewing the notes spent and created in a transaction, authorize the spending of some notes
2. The transaction builder may omit the output note distribution from the transaction
3. This gives the transaction builder, who may be a third party, the option to prevent the receipt of created notes.

Therefore, we require that user VPs have the ability to verify output note distribution. For example, essential parts of the output note can be verifiably encrypted to the recipient, and the user VP performs this verification.

The requirements can be summarized as:

1. Each output note has an on-chain ciphertext which may be random data, an unverified encryption, or a verified encryption, which should all be indistinguishable.
2. Both the sending and receiving VPs may require verifiably encrypted notes. For example, a sending VP may want to ensure assets from spent notes arrive at the correct destination. A receiving VP might also, however this is probably less important.
3. This verifiable encryption must cover the essential bytes of an output note and be efficient in either the Action circuit or VP circuit

[XuyangSong]

We will use the Poseidon permutation of width 3 in the DuplexSponge mode.

1. Key generation(DH key exchange) 1.1 Get the receiver's public key $K = [k] G$ 1.2 Generate a random $r \in \mathbb{F}_q$ 1.3 Compute the shared encryption key $K_s = [r]K = (K_x, K_y) \in \mathbb{F}_p^2$
2. Encryption The encryption message: $M \in \mathbb{F}_p^l$ The encryption nonce: $N < 2^{128}$ 2.1 Pad the message with zero to a multiple of RATE(2) 2.2 Init the Poseidon state $S = (K_x, K_y, N + l * 2^{128})$ 2.3 Repeat for $0 \le i \lceil l / 2 \rceil$ a) Iterate Poseidon permutation(P) on state $S$: $S \leftarrow P(S)$ b) Absorb two elements of the message: $S[0] = S[0] + M[2i]; S[1] = S[1] + M[2i + 1]$ c) Output two elements of ciphertext: $C[2i] \leftarrow S[0]; C[2i+1] \leftarrow S[1]$ 2.4 Squeeze on S last time to get the MAC: $S \leftarrow P(S)$ 2.5 Add the MAC to the ciphertext: $C.add(S[0])$
3. Decryption Decryption nearly has the same process as encryption except for checking the MAC at the last step.

Reference: Poseidon Paper Duplexing the Sponge Encryption with Poseidon Design of Symmetric-Key Primitives for Advanced Cryptographic Protocols