Add no_std support

[bigspider]

Which crate is this feature request for?

payjoin

Please describe the feature you'd like to see added.

In order to use the library in embedded devices, no_std support is usually a prerequisite.

(I see there was a previous attempt)

[DanGould]

Hey @bigspider are you asking in relation to a particular integration need, or just in general have noticed that no_std support is missing?

[bigspider]

Hi @DanGould,
I might experiment with it within Vanadium at some point - although I admit I haven't yet done the homework so I'm not sure what parts of this crate are indeed needed on a signing device.

More broadly, I haven't seen a discussion of what it would take to support PJ transactions securely in hardware signers, as adding external inputs is generally problematic. The host machine is assumed compromised, and there are some attacks where the host lies about the 'external' inputs that are actually internal.

I suppose SLIP-19 proofs of ownership as implemented by Trezor would also work for PJ, but I was wondering if there is an easier/lighter solution?

[nothingmuch]

More broadly, I haven't seen a discussion of what it would take to support PJ transactions securely in hardware signers, as adding external inputs is generally problematic. The host machine is assumed compromised, and there are some attacks where the host lies about the 'external' inputs that are actually internal.

The fallback transaction serves as an ownership proof WRT the sender's inputs in the sender's original PSBT, and the partially signed payjoin PSBT with which the receiver replies covers the receiver's inputs, so there are no ownership proofs required in BIP 78 or 77.

A receiver's payjoin signer can take the fallback transaction, mutate it as per the state machine with its own inputs and adjust its self spend output in one atomic operation, only producing signatures for inputs it knows are its own and that it added. The host would provide the list of usable inputs but would not construct the payjoin transaction.

The sender's payjoin signer could similarly compare its own fallback transaction and only sign the previously signed inputs. That original psbt (which is actually fully signed) is just a normal payment transaction, so can be signed securely as normal. It, along with the auxiliary information could be HMAC'ed by the HWW, and then given again by the host during the re-signing, unambiguously identifying the inputs.

See the receiver & sender's checklists in the BIPs for more details.

This leaves the scenario where a HWW is tricked into payjoining with itself, which should not result in theft as in the attack described by instagibbs. I'm not sure how to prevent that.

In the multi sender single receiver multiparty experiment there are/were no liveness guarantees at all, so ownership proofs were also omitted. In this setting it's not possible to do this securely.

I suppose SLIP-19 proofs of ownership as implemented by Trezor would also work for PJ, but I was wondering if there is an easier/lighter solution?

In the future we will likely use BIP 322 for inputs-first multiparty transaction construction. IIRC trezor supported BIP 322 with an ownership tag, not just SLIP 19, are both widely supported? IIUC BIP 322 is slightly simpler because the signing code paths can be reused

[bigspider]

The fallback transaction serves as an ownership proof WRT the sender's inputs in the sender's original PSBT, and the partially signed payjoin PSBT with which the receiver replies covers the receiver's inputs, so there are no ownership proofs required in BIP 78 or 77.

For coinjoins, ownership proofs are indeed used to prove non-ownership of the other inputs. Hardware signers can already verify ownership of its own inputs (same way as they check change addresses - by deriving them based on the BIP32 paths in the PSBT).

While it's true that attacks are non-trivial if you only sign inputs that you can verify as your own (e.g. you have to convince the user to approve signing two different transactions, pretending that it's actually the same), non-ownership proofs avoid those altogether.

A receiver's payjoin signer can take the fallback transaction, mutate it as per the state machine with its own inputs and adjust its self spend output in one atomic operation, only producing signatures for inputs it knows are its own and that it added. The host would provide the list of usable inputs but would not construct the payjoin transaction.

The sender's payjoin signer could similarly compare its own fallback transaction and only sign the previously signed inputs. That original psbt (which is actually fully signed) is just a normal payment transaction, so can be signed securely as normal. It, along with the auxiliary information could be HMAC'ed by the HWW, and then given again by the host during the re-signing, unambiguously identifying the inputs.

I'll have to think more about this. HMAC proves that something was already seen/appproved before, but not that other versions of it weren't produced. An attacker could in principle create multiple unfinished PJ transactions, and therefore have several unfinished versions of it to choose from. Not sure if there's an attack here, but I'll be paranoid until I understand the protocol (that's on me).

See the receiver & sender's checklists in the BIPs for more details.

BIP 78 claims that hardware signers can't verify the sender checklist, which I don't quite understand - the goal of implementing PJ in Vanadium would be to always strictly increase security versus a software wallet implementation (otherwise, it's not really interesting to do it in hardware).

In the future we will likely use BIP 322 for inputs-first multiparty transaction construction. IIRC trezor supported BIP 322 with an ownership tag, not just SLIP 19, are both widely supported? IIUC BIP 322 is slightly simpler because the signing code paths can be reused

I don't think either is widely supported, but I don't think BIP-322 can be used to prove non-ownership of transaction inputs.

[nothingmuch]

For coinjoins, ownership proofs are indeed used to prove non-ownership of the other inputs. Hardware signers can already verify ownership of its own inputs (same way as they check change addresses - by deriving them based on the BIP32 paths in the PSBT).

HWW can't do that in the absence of such metadata without incurring a costly linear scan of up to 2^32 address (all hardened and non hardened keys) per path, and the space of paths is practically unbounded, so if the BIP 32 paths are omitted or changed adversarially, they could be tricked into not recognizing their own coins.

While it's true that attacks are non-trivial if you only sign inputs that you can verify as your own (e.g. you have to convince the user to approve signing two different transactions, pretending that it's actually the same), non-ownership proofs avoid those altogether.

If a [edit: stateless] signer only produces ownership proofs it will trivially recognize (by HMACing), then logically it follows that if all inputs all have ownership proofs, those that aren't recognized must belong to other users wallets. This is the logic of SLIP 19.

Unfortunately this can't be the case for BIP 78 and 77 as they do not require ownership proofs at all. However because they are two party protocols, and because of strict rules about how the PSBTs are transformed, you can still have the same assurances [edit: as when authorizing a unilateral transaction]:

1. for the sender's original PSBT / fallback txn, assume all inputs are owned by the user, same as in a unilateral tx
2. for the receiver's proposal, verify that fallback txn's spent inputs go to the payment output, if they actually belong to the receiver then no loss of funds other than fees occurs. any newly added inputs must belong to the receiver (which should transform into the payjoin PSBT and sign the inputs ~atomically). the payjoin psbt, if fully signed by the receiver (which is actually the sender) would then waste more fees and create two outputs owned by the receiver, but apart from the fee cost again no funds will be lost
3. the sender can then evaluate the payjoin psbt in the context of its fallback PSBT (which it could get from the host, and verify it is an authentic intermediate state of the protocol by the HMAC i alluded to, even though the state was saved by the host). only unsigned inputs in the payjoin psbt will be signed by the sender, and only if those exact same inputs were signed in the fallback psbt.

(steps 1 & 3 done only by sender, 2 by receiver)

I'll have to think more about this. HMAC proves that something was already seen/appproved before, but not that other versions of it weren't produced. An attacker could in principle create multiple unfinished PJ transactions, and therefore have several unfinished versions of it to choose from. Not sure if there's an attack here, but I'll be paranoid until I understand the protocol (that's on me).

it should not be a problem due to the monotonicity of the input sets, both the fallback and payjoin txns of a single protocol run would be mutually exclusive. concurrent runs of the protocol are either mutually exclusive or completely independent.

BIP 78 claims that hardware signers can't verify the sender checklist, which I don't quite understand - the goal of implementing PJ in Vanadium would be to always strictly increase security versus a software wallet implementation (otherwise, it's not really interesting to do it in hardware).

I believe BIP 78 is just wrong about this, but is correctly alluding to the fact that HWWs can't do coin selection and can't access prior state of protocol execution without assistance from the host. I believe that the HMAC on the state addresses the latter concern, the HWW would refuse to continue unless the host convinces it that it's resuming a valid state, and this reduces to the concerns of just a normal unilateral payment.

I don't think either is widely supported, but I don't think BIP-322 can be used to prove non-ownership of transaction inputs.

BIP 322 can commit to additional data, so an ownership tag like in SLIP 19 can be included, my suggestion just potentially simplifies the "generic signed message format" implementation requirement. iirc wasabi 2 implemented bip 322 with the new format and used dummy SLIP 19 tags for its ownership tags, and that trezor implemented actual ownership tags for their HWW coinjoin support. in this setting, the ownership proofs mainly protect the coordinator from malicious input registrations (liveness issue, users can trust the coordinator with that), protect HWWs from these memento (the movie) like theft attacks, so only trezor implemented that, and finally were intended to allow users to verify each others inputs at least partly and obtain authentic previous output values, a goal which was not at all realized.

[nothingmuch]

#1190

[caarloshenriq]

I'm working on this as part of bitcoin developer launchpad by vinteum, I'm almost done , will just go through a round of review by the vinteum community and open a PR in the next few days.

[DanGould]

Great find, even. Thanks for your hustle.

[benalleng]

@caarloshenriq Following the proof that we can succesfully run on embedded hardware with https://github.com/benalleng/payjoin-pico2 and https://github.com/caarloshenriq/payjoin-blackpill-test I would like you to spec out what an e2e payjoin test would look like using no_std. After-which we can generate some harness to test with our respective devices. At that point I will be satisfied with the no_std feature and be willing to merge #1615 and close this.

[caarloshenriq]

Thanks @benalleng.

Here is how the e2e flow would work.

Two boards connect to a host machine over serial, one acting as sender and the other as receiver. The host starts a regtest node and funds a wallet on each side, but does not participate in any payjoin decision making.

The sender device builds the original PSBT and the payjoin request using the no_std payjoin logic, then sends the resulting bytes to the host over serial. The host relays those bytes to the receiver device.

The receiver device runs the full no_std receiver flow. It validates the proposal, decides which inputs and outputs to contribute, builds the final proposal PSBT, and signs its own inputs. It sends the signed proposal back to the host, which relays it back to the sender device.

The sender device finalizes the PSBT by combining both sets of signatures and sends the final signed PSBT back to the host. The host broadcasts it on regtest and checks that it confirms with the expected inputs and outputs from both sides.

The same firmware runs on both boards, since the payjoin logic itself does not depend on which board it runs on. Only the serial driver and flashing process differ between the Black Pill and the Pico 2, and that stays in our personal repos.

One question before I start building this. payjoin-cli already has an e2e test at payjoin-cli/tests/e2e.rs. Would it make sense to add an equivalent payjoin/tests/e2e.rs in this repo for the no_std harness, or do you think this needs to live in a separate repo given the hardware dependency?

[caarloshenriq]

After-which we can generate some harness to test with our respective devices.

Update: I put together a test harness for this. It builds payjoin with --no-default-features --features "v2,alloc" for thumbv7em-none-eabihf and runs on real hardware (tested on an STM32F411CEU6, Cortex-M4F).

Happy to add more boards if anyone wants to run it on theirs.