Multisignature Utils

class MultiSigUtils {
    public static void signInput(Transaction tx, int inputIndex, byte[] inputScript, ECKey key) throws AddressFormatException {
        TransactionInput input = tx.getInput(inputIndex);
        Script existingScriptSig = input.getScriptSig();

        int numSigs = Script.decodeFromOpN(inputScript[0]);
        ScriptBuilder builder = new ScriptBuilder();
        Script redeemScript = new Script(inputScript);

        List<ScriptChunk> redeemChunks = redeemScript.getChunks();
        int myIndex = findKeyInRedeem(key, redeemChunks);

        Sha256Hash hash = tx.hashForSignature(inputIndex, redeemScript.getProgram(), Transaction.SigHash.ALL, false);
        TransactionSignature signature = new TransactionSignature(key.sign(hash), Transaction.SigHash.ALL, false);

        List<ScriptChunk> existingChunks = existingScriptSig.getChunks();
        if (existingChunks.size() < 2)
            throw new AddressFormatException("incorrect script size");

        // OP_0 required for redeeming multisig due to bug in CHECKMULTISIG in bitcoind
        builder.op(ScriptOpCodes.OP_0);

        // Collect the signatures
        List<byte[]> sigs = Lists.newArrayList();

        // collect existing signatures, skipping the initial OP_0 and the final redeem script
        for (ScriptChunk chunk : existingChunks.subList(1, existingChunks.size() - 1)) {
            if (chunk.isOpCode() || chunk.data.length == 0) {
                // OP_0, skip
            } else {
                sigs.add(chunk.data);
            }
        }

        // Identify location to insert the new sig
        boolean inserted = false;
        for (ListIterator<byte[]> iter = sigs.listIterator() ; iter.hasNext() ;) {
            byte[] sig = iter.next();
            if (!inserted && myIndex < findSigInRedeem(sig, hash, redeemChunks)) {
                iter.add(signature.encodeToBitcoin());
                inserted = true;
                break;
            }
        }

        if (!inserted)
            sigs.add(signature.encodeToBitcoin());

        for (int sig = 0 ; sig < numSigs ; sig++) {
            if (sigs.size() > sig)
                builder.data(sigs.get(sig));
            else
                builder.op(ScriptOpCodes.OP_0);
        }

        if (!Arrays.equals(existingChunks.get(existingChunks.size() - 1).data, inputScript))
            throw new AddressFormatException("Existing signature script does not end with the input script.  See P2SH standard.");
        builder.data(inputScript);
        input.setScriptSig(builder.build());
    }

    public static int findKeyInRedeem(ECKey key, List<ScriptChunk> redeemChunks) throws AddressFormatException {
        int numKeys = redeemChunks.get(redeemChunks.size() - 2).data[0] - ScriptOpCodes.OP_1 + 1;
        for (int i = 0 ; i < numKeys ; i++) {
            if (Arrays.equals(redeemChunks.get(1 + i).data, key.getPubKey())) {
                return i;
            }
        }
        throw new AddressFormatException("Could not find matching key");
    }

    public static int findSigInRedeem(byte[] signatureBytes, Sha256Hash hash, List<ScriptChunk> redeemChunks) throws AddressFormatException {
        int numKeys = redeemChunks.get(redeemChunks.size() - 2).data[0] - ScriptOpCodes.OP_1 + 1;
        TransactionSignature signature = TransactionSignature.decodeFromBitcoin(signatureBytes, true);
        for (int i = 0 ; i < numKeys ; i++) {
            if (ECKey.fromPublicOnly(redeemChunks.get(i+1).data).verify(hash, signature)) {
                return i;
            }
        }
        throw new AddressFormatException("Could not find matching key for signature");
    }

    static void sortKeys(List<ECKey> keys) {
        final Comparator<byte[]> comparator = UnsignedBytes.lexicographicalComparator();
        Collections.sort(keys, new Comparator<ECKey>() {
            @Override
            public int compare(ECKey k1, ECKey k2) {
                return comparator.compare(k1.getPubKey(), k2.getPubKey());
            }
        });
    }

    // Get an HD Multisig address
    public Address getHdmAddress(List<DeterministicKey> masterKeys, List<ChildNum> path) {
        List<ECKey> keys = Lists.newArrayList();
        for (DeterministicKey key : masterKeys) {
            DeterministicHierarchy hier = new DeterministicHierarchy(key);
            DeterministicKey subKey = hier.get(path, true, true);
            keys.add(subKey);
        }
        Script redeemScript = ScriptBuilder.createMultiSigOutputScript(2, keys);

        return Address.fromP2SHHash(params, Utils.sha256hash160(expectedRedeemScript.getProgram()));
    }
}