improve validation of payjoin proposals, and accept a substituted payment output where a change output is present

diff --git a/src/main/java/com/sparrowwallet/sparrow/payjoin/Payjoin.java b/src/main/java/com/sparrowwallet/sparrow/payjoin/Payjoin.java
index a1e752e..6258ee0 100644
--- a/src/main/java/com/sparrowwallet/sparrow/payjoin/Payjoin.java
+++ b/src/main/java/com/sparrowwallet/sparrow/payjoin/Payjoin.java
@@ -2,6 +2,7 @@ package com.sparrowwallet.sparrow.payjoin;
 
 import com.google.common.collect.ImmutableMap;
 import com.google.gson.Gson;
+import com.google.gson.JsonSyntaxException;
 import com.sparrowwallet.drongo.protocol.Script;
 import com.sparrowwallet.drongo.protocol.Transaction;
 import com.sparrowwallet.drongo.protocol.TransactionInput;
@@ -68,7 +69,8 @@ public class Payjoin {
         try {
             String base64Psbt = psbt.getPublicCopy().toBase64String();
 
-            String appendQuery = "v=1&minfeerate=" + AppServices.getMinimumRelayFeeRate();
+            double minFeeRate = AppServices.getMinimumRelayFeeRate();
+            String appendQuery = "v=1&minfeerate=" + minFeeRate;
             int changeOutputIndex = getChangeOutputIndex();
             long maxAdditionalFeeContribution = 0;
             if(changeOutputIndex > -1) {
@@ -87,12 +89,16 @@ public class Payjoin {
 
             String response = httpClientService.postString(finalUri.toString(), null, "text/plain", base64Psbt);
             PSBT proposalPsbt = PSBT.fromString(response.trim());
-            checkProposal(psbt, proposalPsbt, changeOutputIndex, maxAdditionalFeeContribution, allowOutputSubstitution);
+            checkProposal(psbt, proposalPsbt, changeOutputIndex, maxAdditionalFeeContribution, minFeeRate, allowOutputSubstitution);
 
             return proposalPsbt;
         } catch(HttpResponseException e) {
-            Gson gson = new Gson();
-            PayjoinReceiverError payjoinReceiverError = gson.fromJson(e.getResponseBody(), PayjoinReceiverError.class);
+            PayjoinReceiverError payjoinReceiverError = getPayjoinReceiverError(e);
+            if(payjoinReceiverError == null) {
+                log.warn("Payjoin receiver returned a status of " + e.getStatusCode() + " with an unrecognised body");
+                throw new PayjoinReceiverException("The payjoin receiver returned an error (HTTP " + e.getStatusCode() + ").");
+            }
+
             log.warn("Payjoin receiver returned an error of " + payjoinReceiverError.getErrorCode() + " (" + payjoinReceiverError.getMessage() + ")");
             throw new PayjoinReceiverException(payjoinReceiverError.getSafeMessage());
         } catch(URISyntaxException e) {
@@ -116,7 +122,7 @@ public class Payjoin {
         }
     }
 
-    private void checkProposal(PSBT original, PSBT proposal, int changeOutputIndex, long maxAdditionalFeeContribution, boolean allowOutputSubstitution) throws PayjoinReceiverException, PSBTProofException {
+    void checkProposal(PSBT original, PSBT proposal, int changeOutputIndex, long maxAdditionalFeeContribution, double minFeeRate, boolean allowOutputSubstitution) throws PayjoinReceiverException, PSBTProofException {
         Transaction originalTx = original.getTransaction();
         Queue<Map.Entry<TransactionInput, PSBTInput>> originalInputs = new ArrayDeque<>();
         for(int i = 0; i < original.getPsbtInputs().size(); i++) {
@@ -145,10 +151,10 @@ public class Payjoin {
         Set<Long> sequences = new HashSet<>();
         // For each inputs in the proposal:
         for(PSBTInput proposedPSBTInput : proposal.getPsbtInputs()) {
-            if(!proposedPSBTInput.getDerivedPublicKeys().isEmpty()) {
+            if(!proposedPSBTInput.getDerivedPublicKeys().isEmpty() || !proposedPSBTInput.getTapDerivedPublicKeys().isEmpty() || proposedPSBTInput.getTapInternalKey() != null) {
                 throw new PayjoinReceiverException("The receiver added keypaths to an input");
             }
-            if(!proposedPSBTInput.getPartialSignatures().isEmpty()) {
+            if(!proposedPSBTInput.getPartialSignatures().isEmpty() || proposedPSBTInput.getTapKeyPathSignature() != null) {
                 throw new PayjoinReceiverException("The receiver added partial signatures to an input");
             }
 
@@ -174,6 +180,8 @@ public class Payjoin {
                 proposedPSBTInput.setWitnessUtxo(originalPSBTInput.getWitnessUtxo());
                 // We fill up information we had on the signed PSBT, so we can sign it.
                 proposedPSBTInput.getDerivedPublicKeys().putAll(originalPSBTInput.getDerivedPublicKeys());
+                proposedPSBTInput.getTapDerivedPublicKeys().putAll(originalPSBTInput.getTapDerivedPublicKeys());
+                proposedPSBTInput.setTapInternalKey(originalPSBTInput.getTapInternalKey());
                 proposedPSBTInput.getProprietary().putAll(originalPSBTInput.getProprietary());
                 proposedPSBTInput.setRedeemScript(originalPSBTInput.getFinalScriptSig().getFirstNestedScript());
                 proposedPSBTInput.setWitnessScript(originalPSBTInput.getFinalScriptWitness().getWitnessScript());
@@ -212,19 +220,25 @@ public class Payjoin {
         }
 
         TransactionOutput changeOutput = (changeOutputIndex > -1 ? originalTx.getOutputs().get(changeOutputIndex) : null);
+        Script paymentScript = payjoinURI.getAddress().getOutputScript();
 
         // For each outputs in the proposal:
         for(int i = 0; i < proposal.getPsbtOutputs().size(); i++) {
             PSBTOutput proposedPSBTOutput = proposal.getPsbtOutputs().get(i);
             // Verify that no keypaths is in the PSBT output
-            if(!proposedPSBTOutput.getDerivedPublicKeys().isEmpty()) {
+            if(!proposedPSBTOutput.getDerivedPublicKeys().isEmpty() || !proposedPSBTOutput.getTapDerivedPublicKeys().isEmpty() || proposedPSBTOutput.getTapInternalKey() != null) {
                 throw new PayjoinReceiverException("The receiver added keypaths to an output");
             }
 
             TransactionOutput proposedTxOut = proposalTx.getOutputs().get(i);
-            boolean isOriginalOutput = !originalOutputs.isEmpty() && originalOutputs.peek().getKey().getScript().equals(proposedTxOut.getScript());
-            if(isOriginalOutput) {
-                Map.Entry<TransactionOutput, PSBTOutput> originalOutput = originalOutputs.remove();
+            Map.Entry<TransactionOutput, PSBTOutput> originalOutput = originalOutputs.peek();
+            boolean isOriginalOutput = originalOutput != null && originalOutput.getKey().getScript().equals(proposedTxOut.getScript());
+            boolean isPaymentOutput = originalOutput != null && originalOutput.getKey().getScript().equals(paymentScript);
+            // The receiver may have substituted the payment output with one paying to a different script
+            boolean isSubstitutedOutput = !isOriginalOutput && isPaymentOutput && allowOutputSubstitution;
+
+            if(isOriginalOutput || isSubstitutedOutput) {
+                originalOutputs.remove();
                 if(originalOutput.getKey() == changeOutput) {
                     var actualContribution = originalOutput.getKey().getValue() - proposedTxOut.getValue();
                     // The amount that was subtracted from the output's value is less than or equal to maxadditionalfeecontribution
@@ -240,7 +254,7 @@ public class Payjoin {
                     if(actualContribution > getSingleInputFee() * additionalInputsCount) {
                         throw new PayjoinReceiverException("The actual contribution is not only paying for additional inputs");
                     }
-                } else if(allowOutputSubstitution && originalOutput.getKey().getScript().equals(payjoinURI.getAddress().getOutputScript())) {
+                } else if(allowOutputSubstitution && isPaymentOutput) {
                     // That's the payment output, the receiver may have changed it.
                 } else {
                     if(originalOutput.getKey().getValue() > proposedTxOut.getValue()) {
@@ -248,28 +262,57 @@ public class Payjoin {
                     }
                 }
 
-                PSBTOutput originalPSBTOutput = originalOutput.getValue();
-                // We fill up information we had on the signed PSBT, so we can sign it.
-                proposedPSBTOutput.getDerivedPublicKeys().putAll(originalPSBTOutput.getDerivedPublicKeys());
-                proposedPSBTOutput.getProprietary().putAll(originalPSBTOutput.getProprietary());
-                proposedPSBTOutput.setRedeemScript(originalPSBTOutput.getRedeemScript());
-                proposedPSBTOutput.setWitnessScript(originalPSBTOutput.getWitnessScript());
+                if(isOriginalOutput) {
+                    PSBTOutput originalPSBTOutput = originalOutput.getValue();
+                    // We fill up information we had on the signed PSBT, so we can sign it. A substituted output pays to a different script, so this information does not apply to it.
+                    proposedPSBTOutput.getDerivedPublicKeys().putAll(originalPSBTOutput.getDerivedPublicKeys());
+                    proposedPSBTOutput.getTapDerivedPublicKeys().putAll(originalPSBTOutput.getTapDerivedPublicKeys());
+                    proposedPSBTOutput.setTapInternalKey(originalPSBTOutput.getTapInternalKey());
+                    proposedPSBTOutput.getProprietary().putAll(originalPSBTOutput.getProprietary());
+                    proposedPSBTOutput.setRedeemScript(originalPSBTOutput.getRedeemScript());
+                    proposedPSBTOutput.setWitnessScript(originalPSBTOutput.getWitnessScript());
+                }
             }
         }
 
         // Verify that all of sender's outputs from the original PSBT are in the proposal.
         if(!originalOutputs.isEmpty()) {
-            // The payment output may have been substituted
-            if(!allowOutputSubstitution || originalOutputs.size() != 1 || !originalOutputs.remove().getKey().getScript().equals(payjoinURI.getAddress().getOutputScript())) {
+            // The payment output may have been removed without being substituted
+            if(!allowOutputSubstitution || originalOutputs.size() != 1 || !originalOutputs.remove().getKey().getScript().equals(paymentScript)) {
                 throw new PayjoinReceiverException("Some of our outputs are not included in the proposal");
             }
         }
 
+        // Once signed, the fee rate of the payjoin transaction must not be less than the minfeerate we requested
+        double proposalFeeRate = getProposalFeeRate(original, proposal);
+        if(proposalFeeRate < minFeeRate) {
+            throw new PayjoinReceiverException("The fee rate of the payjoin transaction of " + String.format("%.2f", proposalFeeRate) + " sats/vB is less than the requested minimum of " + String.format("%.2f", minFeeRate) + " sats/vB");
+        }
+
         //Add global pubkey map for signing
         proposal.getExtendedPublicKeys().putAll(psbt.getExtendedPublicKeys());
         proposal.getGlobalProprietary().putAll(psbt.getGlobalProprietary());
     }
 
+    /**
+     * Estimates the fee rate of the payjoin transaction once the sender's inputs have been signed.
+     * The extracted proposal transaction already carries the receiver's finalized inputs, so the weight the sender still has to add
+     * is the difference between the signed and unsigned forms of the original transaction.
+     */
+    private double getProposalFeeRate(PSBT original, PSBT proposal) throws PSBTProofException {
+        Transaction signedOriginalTx = original.extractTransaction();
+        Transaction finalizedProposalTx = proposal.extractTransaction();
+        int signedWeightUnits = signedOriginalTx.getWeightUnits() - original.getTransaction().getWeightUnits();
+        if(signedOriginalTx.isSegwit() && finalizedProposalTx.isSegwit()) {
+            //Both transactions include the segwit marker and flag, so don't count them twice
+            signedWeightUnits -= 2;
+        }
+
+        double vSize = (double)(finalizedProposalTx.getWeightUnits() + signedWeightUnits) / Transaction.WITNESS_SCALE_FACTOR;
+
+        return proposal.getFee().doubleValue() / vSize;
+    }
+
     private int getChangeOutputIndex() {
         Map<Script, WalletNode> changeScriptNodes = wallet.getWalletOutputScripts(wallet.getChangeKeyPurpose());
         for(int i = 0; i < psbt.getTransaction().getOutputs().size(); i++) {
@@ -300,8 +343,17 @@ public class Payjoin {
         return (long) (vSize * feeRate);
     }
 
+    private PayjoinReceiverError getPayjoinReceiverError(HttpResponseException e) {
+        try {
+            return new Gson().fromJson(e.getResponseBody(), PayjoinReceiverError.class);
+        } catch(JsonSyntaxException jse) {
+            return null;
+        }
+    }
+
     private static class PayjoinReceiverError {
-        Map<String, String> knownErrors = ImmutableMap.of(
+        //Must be static so it cannot be overridden by the deserialized receiver response
+        private static final Map<String, String> KNOWN_ERRORS = ImmutableMap.of(
                 "unavailable", "The payjoin endpoint is not available for now.",
                 "not-enough-money", "The receiver added some inputs but could not bump the fee of the payjoin proposal.",
                 "version-unsupported", "This version of payjoin is not supported.",
@@ -320,7 +372,7 @@ public class Payjoin {
         }
 
         public String getSafeMessage() {
-            String message = knownErrors.get(errorCode);
+            String message = KNOWN_ERRORS.get(errorCode);
             return (message == null ? "Unknown Error" : message);
         }
     }
diff --git a/src/test/java/com/sparrowwallet/sparrow/payjoin/PayjoinTest.java b/src/test/java/com/sparrowwallet/sparrow/payjoin/PayjoinTest.java
new file mode 100644
index 0000000..6330414
--- /dev/null
+++ b/src/test/java/com/sparrowwallet/sparrow/payjoin/PayjoinTest.java
@@ -0,0 +1,175 @@
+package com.sparrowwallet.sparrow.payjoin;
+
+import com.sparrowwallet.drongo.crypto.ECKey;
+import com.sparrowwallet.drongo.protocol.Script;
+import com.sparrowwallet.drongo.protocol.ScriptType;
+import com.sparrowwallet.drongo.protocol.Sha256Hash;
+import com.sparrowwallet.drongo.protocol.Transaction;
+import com.sparrowwallet.drongo.protocol.TransactionOutput;
+import com.sparrowwallet.drongo.protocol.TransactionWitness;
+import com.sparrowwallet.drongo.psbt.PSBT;
+import com.sparrowwallet.drongo.psbt.PSBTInput;
+import com.sparrowwallet.drongo.uri.BitcoinURI;
+import com.sparrowwallet.drongo.wallet.Wallet;
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.Test;
+
+import java.math.BigInteger;
+import java.util.List;
+
+public class PayjoinTest {
+    private static final ECKey SENDER_KEY = ECKey.fromPrivate(BigInteger.valueOf(1001));
+    private static final ECKey CHANGE_KEY = ECKey.fromPrivate(BigInteger.valueOf(1002));
+    private static final ECKey PAYMENT_KEY = ECKey.fromPrivate(BigInteger.valueOf(1003));
+    private static final ECKey SUBSTITUTE_KEY = ECKey.fromPrivate(BigInteger.valueOf(1004));
+    private static final ECKey RECEIVER_KEY = ECKey.fromPrivate(BigInteger.valueOf(1005));
+
+    private static final Sha256Hash SENDER_UTXO_HASH = Sha256Hash.wrap("1111111111111111111111111111111111111111111111111111111111111111");
+    private static final Sha256Hash RECEIVER_UTXO_HASH = Sha256Hash.wrap("2222222222222222222222222222222222222222222222222222222222222222");
+
+    private static final long SENDER_UTXO_VALUE = 200000L;
+    private static final long RECEIVER_UTXO_VALUE = 150000L;
+    private static final long PAYMENT_VALUE = 100000L;
+    private static final long CHANGE_VALUE = 90000L;
+    private static final int CHANGE_OUTPUT_INDEX = 1;
+    private static final long MAX_ADDITIONAL_FEE_CONTRIBUTION = 5000L;
+    private static final double MIN_FEE_RATE = 1.0d;
+
+    @Test
+    public void unsubstitutedProposalIsAccepted() throws Exception {
+        PSBT original = getOriginalPSBT();
+        Payjoin payjoin = getPayjoin(original);
+        PSBT proposal = getProposalPSBT(getPaymentScript(), PAYMENT_VALUE + RECEIVER_UTXO_VALUE, CHANGE_VALUE);
+
+        payjoin.checkProposal(original, proposal, CHANGE_OUTPUT_INDEX, MAX_ADDITIONAL_FEE_CONTRIBUTION, MIN_FEE_RATE, true);
+    }
+
+    @Test
+    public void substitutedPaymentOutputIsAcceptedWhenChangeOutputIsPresent() throws Exception {
+        PSBT original = getOriginalPSBT();
+        Payjoin payjoin = getPayjoin(original);
+        PSBT proposal = getProposalPSBT(getSubstituteScript(), PAYMENT_VALUE + RECEIVER_UTXO_VALUE, CHANGE_VALUE);
+
+        payjoin.checkProposal(original, proposal, CHANGE_OUTPUT_INDEX, MAX_ADDITIONAL_FEE_CONTRIBUTION, MIN_FEE_RATE, true);
+    }
+
+    @Test
+    public void substitutedPaymentOutputIsRejectedWhenSubstitutionIsDisallowed() throws Exception {
+        PSBT original = getOriginalPSBT();
+        Payjoin payjoin = getPayjoin(original);
+        PSBT proposal = getProposalPSBT(getSubstituteScript(), PAYMENT_VALUE + RECEIVER_UTXO_VALUE, CHANGE_VALUE);
+
+        PayjoinReceiverException e = Assertions.assertThrows(PayjoinReceiverException.class,
+                () -> payjoin.checkProposal(original, proposal, CHANGE_OUTPUT_INDEX, MAX_ADDITIONAL_FEE_CONTRIBUTION, MIN_FEE_RATE, false));
+        Assertions.assertEquals("Some of our outputs are not included in the proposal", e.getMessage());
+    }
+
+    @Test
+    public void changeOutputIsStillCheckedWhenPaymentOutputIsSubstituted() throws Exception {
+        PSBT original = getOriginalPSBT();
+        Payjoin payjoin = getPayjoin(original);
+        PSBT proposal = getProposalPSBT(getSubstituteScript(), PAYMENT_VALUE + RECEIVER_UTXO_VALUE, CHANGE_VALUE - MAX_ADDITIONAL_FEE_CONTRIBUTION - 1);
+
+        PayjoinReceiverException e = Assertions.assertThrows(PayjoinReceiverException.class,
+                () -> payjoin.checkProposal(original, proposal, CHANGE_OUTPUT_INDEX, MAX_ADDITIONAL_FEE_CONTRIBUTION, MIN_FEE_RATE, true));
+        Assertions.assertEquals("The actual contribution is more than maxadditionalfeecontribution", e.getMessage());
+    }
+
+    @Test
+    public void proposalBelowRequestedMinFeeRateIsRejected() throws Exception {
+        PSBT original = getOriginalPSBT();
+        Payjoin payjoin = getPayjoin(original);
+        //The receiver adds an input without increasing the fee, dropping the fee rate of the payjoin transaction
+        PSBT proposal = getProposalPSBT(getPaymentScript(), PAYMENT_VALUE + RECEIVER_UTXO_VALUE, CHANGE_VALUE);
+
+        PayjoinReceiverException e = Assertions.assertThrows(PayjoinReceiverException.class,
+                () -> payjoin.checkProposal(original, proposal, CHANGE_OUTPUT_INDEX, MAX_ADDITIONAL_FEE_CONTRIBUTION, 100.0d, true));
+        Assertions.assertTrue(e.getMessage().contains("is less than the requested minimum"));
+    }
+
+    @Test
+    public void proposalWithOversizedReceiverWitnessIsRejected() throws Exception {
+        PSBT original = getOriginalPSBT();
+        Payjoin payjoin = getPayjoin(original);
+        //The receiver finalizes its input with an oversized witness, dropping the fee rate of the payjoin transaction to around 3.7 sats/vB
+        PSBT proposal = getProposalPSBT(getPaymentScript(), PAYMENT_VALUE + RECEIVER_UTXO_VALUE, CHANGE_VALUE, 10000);
+
+        PayjoinReceiverException e = Assertions.assertThrows(PayjoinReceiverException.class,
+                () -> payjoin.checkProposal(original, proposal, CHANGE_OUTPUT_INDEX, MAX_ADDITIONAL_FEE_CONTRIBUTION, 10.0d, true));
+        Assertions.assertTrue(e.getMessage().contains("is less than the requested minimum"));
+
+        //The same proposal is still accepted where it pays the requested minimum
+        payjoin.checkProposal(original, getProposalPSBT(getPaymentScript(), PAYMENT_VALUE + RECEIVER_UTXO_VALUE, CHANGE_VALUE, 10000), CHANGE_OUTPUT_INDEX, MAX_ADDITIONAL_FEE_CONTRIBUTION, MIN_FEE_RATE, true);
+    }
+
+    private Payjoin getPayjoin(PSBT original) throws Exception {
+        Wallet wallet = new Wallet();
+        wallet.setScriptType(ScriptType.P2WPKH);
+        BitcoinURI payjoinURI = new BitcoinURI("bitcoin:" + ScriptType.P2WPKH.getAddress(PAYMENT_KEY.getPubKeyHash()) + "?pj=https://payjoin.example.com/pj");
+
+        return new Payjoin(payjoinURI, wallet, original);
+    }
+
+    private PSBT getOriginalPSBT() {
+        Transaction transaction = new Transaction();
+        transaction.setVersion(2);
+        transaction.addInput(SENDER_UTXO_HASH, 0, new Script(new byte[0]));
+        transaction.addOutput(PAYMENT_VALUE, getPaymentScript());
+        transaction.addOutput(CHANGE_VALUE, getChangeScript());
+
+        PSBT psbt = new PSBT(transaction);
+        psbt.convertVersion(0);
+        finalise(psbt.getPsbtInputs().get(0), psbt.getTransaction(), SENDER_UTXO_VALUE, getSenderScript(), SENDER_KEY);
+
+        return psbt;
+    }
+
+    private PSBT getProposalPSBT(Script paymentScript, long paymentValue, long changeValue) {
+        return getProposalPSBT(paymentScript, paymentValue, changeValue, 71);
+    }
+
+    private PSBT getProposalPSBT(Script paymentScript, long paymentValue, long changeValue, int receiverSignatureLength) {
+        Transaction transaction = new Transaction();
+        transaction.setVersion(2);
+        transaction.addInput(SENDER_UTXO_HASH, 0, new Script(new byte[0]));
+        transaction.addInput(RECEIVER_UTXO_HASH, 0, new Script(new byte[0]));
+        transaction.addOutput(paymentValue, paymentScript);
+        transaction.addOutput(changeValue, getChangeScript());
+
+        PSBT psbt = new PSBT(transaction);
+        psbt.convertVersion(0);
+        finalise(psbt.getPsbtInputs().get(1), psbt.getTransaction(), RECEIVER_UTXO_VALUE, getReceiverScript(), RECEIVER_KEY, receiverSignatureLength);
+
+        return psbt;
+    }
+
+    private void finalise(PSBTInput psbtInput, Transaction transaction, long value, Script script, ECKey key) {
+        finalise(psbtInput, transaction, value, script, key, 71);
+    }
+
+    private void finalise(PSBTInput psbtInput, Transaction transaction, long value, Script script, ECKey key, int signatureLength) {
+        psbtInput.setWitnessUtxo(new TransactionOutput(null, value, script));
+        psbtInput.setFinalScriptSig(new Script(new byte[0]));
+        psbtInput.setFinalScriptWitness(new TransactionWitness(transaction, List.of(new byte[signatureLength], key.getPubKey())));
+    }
+
+    private Script getSenderScript() {
+        return ScriptType.P2WPKH.getOutputScript(SENDER_KEY.getPubKeyHash());
+    }
+
+    private Script getChangeScript() {
+        return ScriptType.P2WPKH.getOutputScript(CHANGE_KEY.getPubKeyHash());
+    }
+
+    private Script getPaymentScript() {
+        return ScriptType.P2WPKH.getOutputScript(PAYMENT_KEY.getPubKeyHash());
+    }
+
+    private Script getSubstituteScript() {
+        return ScriptType.P2WPKH.getOutputScript(SUBSTITUTE_KEY.getPubKeyHash());
+    }
+
+    private Script getReceiverScript() {
+        return ScriptType.P2WPKH.getOutputScript(RECEIVER_KEY.getPubKeyHash());
+    }
+}