Orchard proving API for hardware wallets

[krnak]

Here I would like to discuss how to connect hardware wallet (HWW) with the Orchard prover, when creating an Orchard transaction.

I consider these two approaches:

1. Synchronized PRGs

A random seed is generated in the HWW and it is used to initialize a PRG on both sides (the host and the HWW). Then actions are constructed, shuffled, shielded, serialized and hashed on both sides, using these PRGs, resulting in the same data. Finally, the host computes a proof while HWW computes signatures.

2. Circuits serialization

Actions are constructed, shuffled, shielded, serialized and hashed only in HWW using a true hardware randomness. HWW also creates circuit data (Circuit and Instance structs) and it sends them to the host, which computes a proof.

Code changes

1️⃣ would require the Builder to use rng in specific fixed order.
2️⃣ would require adding a serialization for the Circuit and Instance structs.

Final notes

1️⃣ uses only pseudo-randomness
2️⃣ seems to be more robust, but also harder to implement
1️⃣ has higher implementation security because everything is recomputed in the original crate

[str4d]

I'm aiming to start thinking about this again once zcashd 4.7.0 is out. To clarify (or remind me), your goal is to use the orchard::builder::Builder type on the HWW itself, rather than using it on the client and then only creating signatures on the HWW? The latter is what I'd assumed all HWWs would want or need to do, i.e. the HWW would receive the "transaction minus signatures" data and then check the given information.

[krnak]

Hello, I definitely don't want to use Builder class on the HWW. The question is whether to use Builder on the client side at all, or rather run only the halo2 prover.

Transaction data are shielded. Verifying these data would equal rebuilding every ActionInfo (given the same randomness) and comparing the result to the original data. This is redundant. Instead I send only ActionInfos into the the HWW and the whole transaction is built and hashed inside of the device.

For better understanding I will try to illustrate two aforementioned approaches.

[krnak]

Approach 1️⃣ (left): synchronized PRGs

• using Builder
• using pseudorandomness

Approach 2️⃣ (right): Circuits serialization

• using only the halo2 prover
• using hardware randomness
• requires Circuit and Action serialization

key: rectangle = data, elipse = functionality

[str4d]

Based on the above diagrams, I'm inclined to go with approach 1️⃣, as it requires serializing strictly less information across the client-HWW connection. I personally would also prefer that both the HWW and client contribute randomness to it (instead of relying solely on the HWW's randomness source).

[str4d]

Probably the most annoying part of 1️ is that it requires synchronizing everything, including e.g. the random shuffle of spends and outputs within actions. That means baking internal decisions in the rand crate impl about how it converts randomness into shuffles into the HWW, which seems... not ideal.

Part of the reason Builder was designed the way it is, was to enable HWWs, multi-signatures, etc. to just operate from the Bundle<InProgress<Unproven, Unauthorized>, V> state, which should contain everything that could be necessary for verifying the correctness of the constructed bundle. I would be interested in seeing what an approach 3️⃣ would look like, that uses the orchard crate's Builder through to Builder::build, then splits into HWW side for verification and signing, and client side for proving. In particular, the interesting flow here is what data specifically the HWW needs to receive in order to satisfy itself that the bundle it is signing is valid.

[krnak]

Hello str4d, I understand the issue. I will think about an approach 3️⃣ and I will let know know in this thread.

[krnak]

Approach 3️⃣ : splitting data for proving (client) and signing (HWW)

I will start from the beginning. From user perspective, transaction is a claim:

I send amount_i ZEC to the recipient address_i with a memo memo_i for every i in {1,..,n} and I offer fee ZEC for this transaction.

Before signing a transaction, HWW let a user to confirm this claim. In particular, HWW let the user to confirm every output tuple (address, amount, memo) (excluding change outputs) and the transaction fee on the device display.

When signing a shielded transaction, HWW must additionally check that shielded data has the same properties as initial transparent data. For sake of simplicity, I will consider a transaction with only Orchard inputs and outputs. For such a transaction, fee equals orchardBalance, which is a public transparent attribute of a transaction. Thus verification of the fee is a peace of cake and the remaining difficulty lies in verifying that Action Descriptions (cv, nf, rk, cm, epk, C^enc, C^out) correspond to the first part of the claim above.

For every output, verification of cm binds shielded data to the tuple (address, amount) and verification of (epk, C^enc, C^out) binds to the memo and it guarantees correctness of the in-band note distribution. Therefore recomputation of components (cm, epk, C^enc, C^out) for every Action Description is necessary and sufficient.

Components (cv, nf, rk) can be trusted. Note that

• Integrity of value commitments is forced by binding signature.
• Freshness of the nullifier is forced by consensus rules.
• Correspondence of the value nullified note and the committed value is forced by zk-proof.
• If rk != ak + [alpha]R , then the signature produced by HWW will be invalid.

Although rk can be trusted, I would recompute it in HWW, since HWW know the ak and the aplha must be send into the HWW anyway.

According to this data flow diagram

HWW needs the following data

• cv, nf, (rk) (Action Description)
• nf_old, alpha, rseed (randomizers)
• (d, pk_d), v_new, memo (output data)

for every Action. Additionally, flags, balance and anchor must be attached to the data. Keys ak and ovk are derived from a seed inside of HWW.

[krnak]

Diagram for approach 3️⃣ :

[krnak]

Hey @str4d, what do you think about approach 3? I would really appreciate any feedback before I start coding.

[krnak]

What I don't like about approach 3 is that a randomness of randomizers (alphas, rseeds, rcvs, permutations...) is not checked by HWW.

This is not a problem in our security model, where the malicious host can break privacy features of a transaction. (We cannot do better , because HWW controls only signed part a transaction and since orchardProof is not part of signed data, randomness of the proof blinders can always be manipulated by the host.)

However, if we can derive randomizers deterministically from some seed and then verify their randomness on HWW, I would prefer to do that. It will strengthen privacy guarantees and reduce communication complexity.

[deepcandles]

@Jarys you may want to join Zcash discord to chat about this.

@str4d As NU5 is deployed now, it would be great if you can help @Jarys with this

[daira]

3️⃣ seems very complicated and difficult to analyse for security to me relative to 1️⃣ and 2️⃣. In both 1️⃣ and 2️⃣, the HWW is building the transaction itself, rather than letting the untrusted client partially create the tx and reverse-engineering its effect. The latter approach has a larger attack surface.

The trade-off between 1️⃣ and 2️⃣ is essentially that 1️⃣ requires RNG synchronization, but has lower HWW <-> client communication and fewer implementation changes on the client side. I don't see that there's a big difference in security properties; it's an engineering decision. My intuition is: if the HWW <-> client communication is very expensive then use 1️⃣, otherwise use 2️⃣. My preference for 2️⃣ as long as the communication will not be too expensive, is informed by the fact that I think stabilizing the RNG usage is quite onerous, whereas the changes needed to serialize the Circuits and Actions are "a simple matter of programming".

[str4d]

NU5 being deployed unfortunately didn't mean I gained any free time 😞 but there is some great analysis here, and we (ECC and ZF) just had a look at this in a meeting in the context of FROST (which has a similar transaction construction problem to solve). I'm going to try and go over this myself in the next week.

[krnak]

Ok, @str4d. Thank you for your feedback @daira.

According to your remarks, I throw over the approach 1️⃣ with sync. PRGs. I am still undecided between 2️⃣ and 3️⃣ .

I like design 3️⃣ because it is much more lightweight, seems to be more natural and it enables parallelization of proving and signing.

After a discussion we had in SatoshiLabs I don't believe that checking randomness is necessary. Randomness is related only to the transaction confidentiality. Since a host knows a full viewing key, he can always break the transaction confidentiality by sending FVK to an attacker, instead of manipulating randomness.

@daira is right that 3️⃣ seems to be complicated to analyze at the first look. However I believe there is a simple argument why checking note commitments, in-band notes distribution and bundle balance should be sufficient. That is the assumption that the tx effect depends only on its outputs.

We will discuss more and let you know. I would be happy to join some of your calls. Mind you I will be off next week.

[krnak]

I tried to implement approach 3️⃣, but I run into some difficulties, so I decided to follow approach 2️⃣, where the whole bundle is constructed by the device.