1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103

// Descriptor wallet library extending bitcoin & miniscript functionality
// by LNP/BP Association (https://lnp-bp.org)
// Written in 2020-2021 by
//     Dr. Maxim Orlovsky <orlovsky@pandoracore.com>
//
// To the extent possible under law, the author(s) have dedicated all
// copyright and related and neighboring rights to this software to
// the public domain worldwide. This software is distributed without
// any warranty.
//
// You should have received a copy of the Apache-2.0 License
// along with this software.
// If not, see <https://opensource.org/licenses/Apache-2.0>.

//! Lexicographic sorting functions

use std::cmp::Ordering;

use bitcoin::{self, secp256k1};
use bitcoin::{
    util::psbt::PartiallySignedTransaction as Psbt, Transaction, TxIn, TxOut,
};

pub trait LexOrder {
    fn lex_order(&mut self);

    fn lex_ordered(mut self) -> Self
    where
        Self: Sized,
    {
        self.lex_order();
        self
    }
}

impl LexOrder for Vec<secp256k1::PublicKey> {
    fn lex_order(&mut self) {
        self.sort()
    }
}

impl LexOrder for Vec<bitcoin::PublicKey> {
    fn lex_order(&mut self) {
        self.sort()
    }
}

impl LexOrder for Vec<TxIn> {
    fn lex_order(&mut self) {
        self.sort_by_key(|txin| txin.previous_output)
    }
}

impl LexOrder for Vec<TxOut> {
    fn lex_order(&mut self) {
        self.sort_by(|left, right| txout_cmp(left, right))
    }
}

impl LexOrder for Transaction {
    fn lex_order(&mut self) {
        self.input.lex_order();
        self.output.lex_order();
    }
}

impl LexOrder for Psbt {
    fn lex_order(&mut self) {
        let tx = &mut self.global.unsigned_tx;
        let mut inputs = tx
            .input
            .clone()
            .into_iter()
            .zip(self.inputs.clone().into_iter())
            .collect::<Vec<(_, _)>>();
        inputs.sort_by_key(|(k, _)| k.previous_output);

        let mut outputs = tx
            .output
            .clone()
            .into_iter()
            .zip(self.outputs.clone().into_iter())
            .collect::<Vec<(_, _)>>();
        outputs.sort_by(|(a, _), (b, _)| txout_cmp(a, b));

        let (in_tx, in_map): (Vec<_>, Vec<_>) = inputs.into_iter().unzip();
        let (out_tx, out_map): (Vec<_>, Vec<_>) = outputs.into_iter().unzip();
        tx.input = in_tx;
        tx.output = out_tx;
        self.inputs = in_map;
        self.outputs = out_map;
    }
}

fn txout_cmp(left: &TxOut, right: &TxOut) -> Ordering {
    if left.value < right.value {
        Ordering::Less
    } else if left.value > right.value {
        Ordering::Greater
    } else {
        left.script_pubkey.cmp(&right.script_pubkey)
    }
}