p2sh_addr_gen.c

/** \file p2sh_addr_gen.c
  *
  * \brief Generates P2SH addresses.
  *
  * A wallet can only securely accept transactions it can generate addresses
  * for. Otherwise, there is no way a user can be sure that the address is
  * owned by themselves. Thus the code in this file generates P2SH addresses
  * so that P2SH transactions can be performed securely.
  *
  * At the moment, this only supports m-of-n multisignature scripts.
  *
  * This file is licensed as described by the file LICENCE.
  */

#include "common.h"
#include "wallet.h"
#include "sha256.h"
#include "ripemd160.h"
#include "hash.h"
#include "baseconv.h"
#include "ecdsa.h"
#include "hwinterface.h"
#include "p2sh_addr_gen.h"


#ifdef TEST
#include <stdio.h>
#include <string.h>
#endif // #ifdef TEST

#ifdef TEST_P2SH_ADDR_GEN
#include <stdlib.h>
#include "test_helpers.h"
#include "stream_comm.h"
#endif // #ifdef TEST_P2SH_ADDR_GEN

/** The total length of the public key list being parsed, in number of
  * bytes. */
static uint32_t public_key_list_length;
/** Which byte the public key list parser is within a public key list.
  * 0 = first byte, 1 = second byte etc. */
static uint32_t public_key_list_index;

/** Checks whether the public key list parser is at the end of the list
  * data.
  * \return Whether the public key list parser is at the end of the list
  *         data.
  */
static bool isEndOfPublicKeyListData(void)
{
	if (public_key_list_index >= public_key_list_length)
	{
		return true;
	}
	else
	{
		return false;
	}
}

/** Get one byte from the public key list, being careful not to read past the
  * end of the list.
  * \param out The byte that was obtained will be written here.
  * \return false on success, true if trying to read past the end of the list.
  */
static bool getPublicKeyListByte(uint8_t *out)
{
	if (isEndOfPublicKeyListData())
	{
		*out = 0;
		return true; // trying to read past end of list data
	}
	else
	{
		*out = streamGetOneByte();
		public_key_list_index++;
		return false;
	}
}

/** See comments for generateMultiSigAddress() for description of what this
  * does and return values. However, the guts of the public key list parser
  * are in the code to this function.
  *
  * Why use a separate function to do the parsing? So that, upon encountering
  * a parser error, this function can just return to the outer function
  * (i.e. generateMultiSigAddress()), which will mop up any remaining unread
  * bytes from the stream.
  * 
  * \param num_sigs See generateMultiSigAddress().
  * \param num_pubkeys See generateMultiSigAddress().
  * \param supplied_pubkey_num See generateMultiSigAddress().
  * \param public_key See generateMultiSigAddress().
  * \return See generateMultiSigAddress().
  */
static P2SHGeneratorErrors generateMultiSigAddressInternal(uint8_t num_sigs, uint8_t num_pubkeys, uint8_t supplied_pubkey_num, PointAffine *public_key)
{
	uint32_t i;
	unsigned int j;
	unsigned int pubkey_length;
	uint8_t buffer[32];
	uint8_t one_byte;
	HashState hs;
	char address[TEXT_ADDRESS_LENGTH];

	if ((num_sigs < 1) || (num_sigs > 16))
	{
		return P2SHGEN_BAD_NUMBER; // invalid number of required signatures
	}
	if ((num_pubkeys < 2) || (num_pubkeys > 16) || (num_pubkeys < num_sigs))
	{
		return P2SHGEN_BAD_NUMBER; // invalid number of supplied public keys
	}
	if (supplied_pubkey_num >= num_pubkeys)
	{
		return P2SHGEN_BAD_NUMBER; // invalid public key number
	}

	sha256Begin(&hs);
	// Write number of required signatures.
	sha256WriteByte(&hs, (uint8_t)(0x50 + num_sigs)); // OP_1 - OP_16
	// Write public keys. One of them must belong in the wallet.
	for (i = 0; i < num_pubkeys; i++)
	{
		if (i == supplied_pubkey_num)
		{
			sha256WriteByte(&hs, 0x41); // 41 bytes of data follows
			sha256WriteByte(&hs, 0x04);
			// The counters run backwards because Bitcoin expects public
			// keys to be in big-endian format, but they're in little-endian
			// format here.
			for (j = 32; j--; )
			{
				sha256WriteByte(&hs, public_key->x[j]);
			}
			for (j = 32; j--; )
			{
				sha256WriteByte(&hs, public_key->y[j]);
			}
		}
		else
		{
			if (getPublicKeyListByte(&one_byte))
			{
				return P2SHGEN_INVALID_FORMAT; // truncated list
			}
			if (one_byte == 0x04)
			{
				// Uncompressed point.
				pubkey_length = 64;
			}
			else if ((one_byte == 0x02) || (one_byte == 0x03))
			{
				// Compressed point.
				pubkey_length = 32;
			}
			else
			{
				return P2SHGEN_UNKNOWN_PUBLIC_KEY; // unknown public key type
			}
			sha256WriteByte(&hs, (uint8_t)(pubkey_length + 1)); // (pubkey_length + 1) bytes of data follows
			sha256WriteByte(&hs, one_byte);
			for (j = 0; j < pubkey_length; j++)
			{
				if (getPublicKeyListByte(&one_byte))
				{
					return P2SHGEN_INVALID_FORMAT; // truncated list
				}
				sha256WriteByte(&hs, one_byte);
			}
		} // end if (i == supplied_pubkey_num)
	} // end for (i = 0; i < num_pubkeys; i++)

	// The entire list should be exhausted by now. If it isn't then that means
	// that there were more public keys in the list than necessary.
	if (!isEndOfPublicKeyListData())
	{
		return P2SHGEN_INVALID_FORMAT; // junk at end of list
	}

	// Write number of public keys and OP_CHECKMULTISIG.
	sha256WriteByte(&hs, (uint8_t)(0x50 + num_pubkeys)); // OP_1 - OP_16
	sha256WriteByte(&hs, 0xae); // OP_CHECKMULTISIG

	// Generate and display P2SH address.
	sha256Finish(&hs);
	writeHashToByteArray(buffer, &hs, true);
	ripemd160Begin(&hs);
	for (i = 0; i < 32; i++)
	{
		ripemd160WriteByte(&hs, buffer[i]);
	}
	ripemd160Finish(&hs);
	writeHashToByteArray(buffer, &hs, true);
	hashToAddr(address, buffer, ADDRESS_VERSION_P2SH);
	displayAddress(address, num_sigs, num_pubkeys);

	return P2SHGEN_NO_ERROR;
}

/** Generate a multi-signature P2SH address. The address is generated by
  * hashing a list of public keys (among other things). All public keys except
  * for one are read from the stream. The outstanding one is supplied via. the
  * public_key parameter; it's position in the list is indicated by the
  * supplied_pubkey_num parameter.
  *
  * The reason that a public key needs to be supplied is to ensure that the
  * generated P2SH address is at least partially "owned" by the wallet.
  *
  * \param num_sigs The number of required signatures in the multi-signature
  *                 transaction.
  * \param num_pubkeys The total number of supplied public keys in the
  *                    multi-signature transaction. This includes the supplied
  *                    public key.
  * \param supplied_pubkey_num Where in the public key list the supplied
  *                            public key is supposed to be. 0 = first,
  *                            1 = second etc.
  * \param public_key The supplied public key.
  * \param length The length (in bytes) of the public key list to read from
  *               the stream. Exactly length bytes will be read from the
  *               stream, even if the transaction was not parsed correctly.
  * \return #P2SHGEN_NO_ERROR on success, or one of #P2SHGeneratorErrors if an
  *         error occurred.
  */
P2SHGeneratorErrors generateMultiSigAddress(uint8_t num_sigs, uint8_t num_pubkeys, uint8_t supplied_pubkey_num, PointAffine *public_key, uint32_t length)
{
	P2SHGeneratorErrors r;
	uint8_t junk;

	public_key_list_index = 0;
	public_key_list_length = length;
	r = generateMultiSigAddressInternal(num_sigs, num_pubkeys, supplied_pubkey_num, public_key);
	// Always read the entire list, even if there was an error.
	while (!isEndOfPublicKeyListData())
	{
		getPublicKeyListByte(&junk);
	}
	return r;
}

#ifdef TEST

/** Buffer to store the last thing that displayAddress() displayed.
  * This is used in the p2sh_addr_gen.c unit tests, to verify that the address
  * being displayed is correct. */
static char last_displayed_address[1024];

/** Set this to true to stop displayAddress() from outputting to stdout.
  * This is used to stop stdout spam when running the fuzzer. */
static bool suppress_display_address;

void displayAddress(char *address, uint8_t num_sigs, uint8_t num_pubkeys)
{
	if ((num_sigs == 1) && (num_pubkeys))
	{
		sprintf(last_displayed_address, "Got address: %s", address);
	}
	else
	{
		sprintf(last_displayed_address, "Got %d-of-%d address: %s", (int)num_sigs, (int)num_pubkeys, address);
	}
	if (!suppress_display_address)
	{
		printf("%s\n", last_displayed_address);
	}
}

#endif // #ifdef TEST

#ifdef TEST_P2SH_ADDR_GEN

/** A single test case for the P2SH address generator. */
struct P2SHAddrGenTestCase
{
	/** Number of required signatures. */
	uint8_t num_sigs;
	/** Total number of public keys in list. */
	uint8_t num_pubkeys;
	/** Where in the list the supplied public key goes. */
	uint8_t supplied_pubkey_num;
	/** Supplied public key. */
	PointAffine public_key;
	/** Public key list data that will be read from the stream. */
	uint8_t stream[1024];
	/** Size (in number of bytes) of public key list data. */
	unsigned int size_of_stream;
	/** Expected contents of #last_displayed_address. */
	char *expected_result;
};

/** Tests which should be successful. */
struct P2SHAddrGenTestCase good_tests[] = {
{
// This test case was obtained from
// https://bitcointalk.org/index.php?topic=92113.0
2, // num_sigs
3, // num_pubkeys
2, // supplied_pubkey_num
// public_key
{{0xd9, 0xff, 0x13, 0xe7, 0xb4, 0xc8, 0x09, 0x00, 0xb9, 0x00, 0x32, 0x68, 0xe2,
0xfc, 0xcb, 0x9f, 0x34, 0x61, 0x36, 0x73, 0x2f, 0x75, 0x8d, 0xef, 0xb3, 0xae,
0x92, 0x59, 0xd8, 0xbb, 0x3f, 0xeb},
{0xb7, 0xda, 0x7c, 0xba, 0x93, 0xc4, 0xf3, 0xf4, 0xf9, 0x17, 0x5b, 0x0c, 0x6f,
0x58, 0x29, 0xa7, 0xdc, 0x1c, 0xd5, 0x6e, 0xd6, 0xd6, 0x8e, 0xa1, 0xcc, 0x22,
0x0e, 0x84, 0x7f, 0xfc, 0xa9, 0x3d}, 0},
// stream
{0x04, 0xd4, 0xf8, 0x1d, 0x9c, 0x28, 0x41, 0x3d, 0x30, 0x19, 0xa2, 0x02, 0xe6,
0x3a, 0x82, 0x8c, 0x88, 0x4d, 0xca, 0xff, 0xa0, 0x94, 0xa9, 0xe6, 0x6f, 0xb8,
0xde, 0xc6, 0x23, 0xa1, 0x44, 0x5d, 0x3f, 0xe0, 0x99, 0xca, 0x7c, 0x30, 0x87,
0xc1, 0x3a, 0xc6, 0xb6, 0x2a, 0xd7, 0xf5, 0x47, 0xef, 0xf2, 0x5d, 0xf5, 0x52,
0xe9, 0x4e, 0x12, 0xf6, 0xfb, 0xfc, 0x45, 0x35, 0xc1, 0xc2, 0xb4, 0xb7, 0x8a,
0x04, 0x20, 0xc4, 0x1c, 0xb7, 0x22, 0x08, 0x29, 0x43, 0xe7, 0xda, 0x60, 0x25,
0x57, 0xb2, 0xe2, 0x8a, 0x84, 0xeb, 0xad, 0x90, 0xbd, 0xfb, 0xae, 0x84, 0x99,
0xd9, 0xae, 0x77, 0xa3, 0x75, 0x25, 0x70, 0xd7, 0x11, 0x64, 0x9b, 0x2e, 0x54,
0xf8, 0x7b, 0x90, 0x64, 0xb7, 0xdc, 0x72, 0xf5, 0xf9, 0x62, 0x03, 0xa7, 0x82,
0xe8, 0x2c, 0xfc, 0x08, 0xa5, 0xac, 0x57, 0x6d, 0x93, 0x3c, 0xa9, 0x2d, 0xe1},
130, // size_of_stream
"Got 2-of-3 address: 3G2v3VJZ46fjgLMqEF3CzLq3k9FPMgauh4"},

{
// This is a test case generated using the addmultisigaddress RPC call from
// Bitcoin-qt v0.7.1.
3, // num_sigs
3, // num_pubkeys
0, // supplied_pubkey_num
// public_key
{{0xEF, 0xE1, 0xEC, 0x61, 0x16, 0xE7, 0xC1, 0x97, 0x3F, 0x84, 0x61, 0x4C, 0x0D,
0x1E, 0x1C, 0xC5, 0x7C, 0xF0, 0x45, 0xE8, 0xB3, 0x73, 0x9B, 0xFD, 0x52, 0xB0,
0x0D, 0x77, 0x19, 0x4E, 0x87, 0x05},
{0x9D, 0x88, 0xB3, 0x88, 0xFF, 0x3B, 0xC8, 0x32, 0x72, 0x82, 0xD3, 0x4A, 0x8E,
0x32, 0xAA, 0xFA, 0xC0, 0x9F, 0x1F, 0xA3, 0x50, 0xB9, 0xD0, 0x0C, 0xDA, 0xFC,
0xC2, 0x96, 0x3E, 0x41, 0x77, 0x68}, 0},
// stream
{0x04, 0x8A, 0x52, 0x51, 0x81, 0x7D, 0x2B, 0xA7, 0x02, 0x42, 0x70, 0x81, 0x70,
0xC6, 0x11, 0x6D, 0xB5, 0xE1, 0xD6, 0x56, 0xCB, 0xFA, 0xDC, 0xA3, 0x97, 0x28,
0x7A, 0x51, 0xA0, 0xF1, 0x46, 0x5A, 0xCB, 0x6E, 0x01, 0xC7, 0x59, 0x6D, 0xAC,
0x97, 0x4C, 0x43, 0x26, 0x1A, 0x75, 0x1D, 0x84, 0x6D, 0xE7, 0xBE, 0x0B, 0x73,
0x6B, 0xA1, 0xFF, 0x3B, 0xBA, 0x5D, 0xB9, 0xD5, 0x59, 0x7D, 0x5D, 0x47, 0xBC,
0x04, 0x9E, 0xD1, 0x66, 0xDC, 0xA9, 0x11, 0x72, 0x56, 0x15, 0x1D, 0xD6, 0x96,
0x95, 0xF6, 0xDC, 0x11, 0xC2, 0x11, 0x14, 0xE6, 0x37, 0x09, 0x31, 0xDC, 0xA1,
0x03, 0x09, 0xBF, 0x1E, 0x23, 0xE4, 0x0F, 0x4A, 0xA7, 0x63, 0xB7, 0x0A, 0x71,
0x6E, 0xA9, 0xB4, 0x0B, 0xEA, 0xCF, 0x7F, 0x26, 0x83, 0xF6, 0xD0, 0xD6, 0x47,
0x51, 0x78, 0x3B, 0xE5, 0x80, 0x0E, 0x49, 0x5A, 0xAC, 0x56, 0x9E, 0xBE, 0x24},
130, // size_of_stream
"Got 3-of-3 address: 3KiWNCEfw4x8UvhypWccBFU6WRLAqSJbmC"},

{
// This is the above test case, but with the supplied public key in
// position = 1.
3, // num_sigs
3, // num_pubkeys
1, // supplied_pubkey_num
// public_key
{{0xCB, 0x5A, 0x46, 0xF1, 0xA0, 0x51, 0x7A, 0x28, 0x97, 0xA3, 0xDC, 0xFA, 0xCB,
0x56, 0xD6, 0xE1, 0xB5, 0x6D, 0x11, 0xC6, 0x70, 0x81, 0x70, 0x42, 0x02, 0xA7,
0x2B, 0x7D, 0x81, 0x51, 0x52, 0x8A},
{0xBC, 0x47, 0x5D, 0x7D, 0x59, 0xD5, 0xB9, 0x5D, 0xBA, 0x3B, 0xFF, 0xA1, 0x6B,
0x73, 0x0B, 0xBE, 0xE7, 0x6D, 0x84, 0x1D, 0x75, 0x1A, 0x26, 0x43, 0x4C, 0x97,
0xAC, 0x6D, 0x59, 0xC7, 0x01, 0x6E}, 0},
// stream
{0x04, 0x05, 0x87, 0x4E, 0x19, 0x77, 0x0D, 0xB0, 0x52, 0xFD, 0x9B, 0x73, 0xB3,
0xE8, 0x45, 0xF0, 0x7C, 0xC5, 0x1C, 0x1E, 0x0D, 0x4C, 0x61, 0x84, 0x3F, 0x97,
0xC1, 0xE7, 0x16, 0x61, 0xEC, 0xE1, 0xEF, 0x68, 0x77, 0x41, 0x3E, 0x96, 0xC2,
0xFC, 0xDA, 0x0C, 0xD0, 0xB9, 0x50, 0xA3, 0x1F, 0x9F, 0xC0, 0xFA, 0xAA, 0x32,
0x8E, 0x4A, 0xD3, 0x82, 0x72, 0x32, 0xC8, 0x3B, 0xFF, 0x88, 0xB3, 0x88, 0x9D,
0x04, 0x9E, 0xD1, 0x66, 0xDC, 0xA9, 0x11, 0x72, 0x56, 0x15, 0x1D, 0xD6, 0x96,
0x95, 0xF6, 0xDC, 0x11, 0xC2, 0x11, 0x14, 0xE6, 0x37, 0x09, 0x31, 0xDC, 0xA1,
0x03, 0x09, 0xBF, 0x1E, 0x23, 0xE4, 0x0F, 0x4A, 0xA7, 0x63, 0xB7, 0x0A, 0x71,
0x6E, 0xA9, 0xB4, 0x0B, 0xEA, 0xCF, 0x7F, 0x26, 0x83, 0xF6, 0xD0, 0xD6, 0x47,
0x51, 0x78, 0x3B, 0xE5, 0x80, 0x0E, 0x49, 0x5A, 0xAC, 0x56, 0x9E, 0xBE, 0x24},
130, // size_of_stream
"Got 3-of-3 address: 3KiWNCEfw4x8UvhypWccBFU6WRLAqSJbmC"},

{
// This is the above test case, but with one compressed public key in the
// public key list.
3, // num_sigs
3, // num_pubkeys
1, // supplied_pubkey_num
// public_key
{{0xCB, 0x5A, 0x46, 0xF1, 0xA0, 0x51, 0x7A, 0x28, 0x97, 0xA3, 0xDC, 0xFA, 0xCB,
0x56, 0xD6, 0xE1, 0xB5, 0x6D, 0x11, 0xC6, 0x70, 0x81, 0x70, 0x42, 0x02, 0xA7,
0x2B, 0x7D, 0x81, 0x51, 0x52, 0x8A},
{0xBC, 0x47, 0x5D, 0x7D, 0x59, 0xD5, 0xB9, 0x5D, 0xBA, 0x3B, 0xFF, 0xA1, 0x6B,
0x73, 0x0B, 0xBE, 0xE7, 0x6D, 0x84, 0x1D, 0x75, 0x1A, 0x26, 0x43, 0x4C, 0x97,
0xAC, 0x6D, 0x59, 0xC7, 0x01, 0x6E}, 0},
// stream
{0x03, 0x05, 0x87, 0x4E, 0x19, 0x77, 0x0D, 0xB0, 0x52, 0xFD, 0x9B, 0x73, 0xB3,
0xE8, 0x45, 0xF0, 0x7C, 0xC5, 0x1C, 0x1E, 0x0D, 0x4C, 0x61, 0x84, 0x3F, 0x97,
0xC1, 0xE7, 0x16, 0x61, 0xEC, 0xE1, 0xEF,
0x04, 0x9E, 0xD1, 0x66, 0xDC, 0xA9, 0x11, 0x72, 0x56, 0x15, 0x1D, 0xD6, 0x96,
0x95, 0xF6, 0xDC, 0x11, 0xC2, 0x11, 0x14, 0xE6, 0x37, 0x09, 0x31, 0xDC, 0xA1,
0x03, 0x09, 0xBF, 0x1E, 0x23, 0xE4, 0x0F, 0x4A, 0xA7, 0x63, 0xB7, 0x0A, 0x71,
0x6E, 0xA9, 0xB4, 0x0B, 0xEA, 0xCF, 0x7F, 0x26, 0x83, 0xF6, 0xD0, 0xD6, 0x47,
0x51, 0x78, 0x3B, 0xE5, 0x80, 0x0E, 0x49, 0x5A, 0xAC, 0x56, 0x9E, 0xBE, 0x24},
98, // size_of_stream
"Got 3-of-3 address: 3FV38rwGvvWAebuiNrs9RtZ6p3ExXqeb3P"},

{
// This is the like the above test cases, but with more public keys.
16, // num_sigs
16, // num_pubkeys
1, // supplied_pubkey_num
// public_key
{{0xCB, 0x5A, 0x46, 0xF1, 0xA0, 0x51, 0x7A, 0x28, 0x97, 0xA3, 0xDC, 0xFA, 0xCB,
0x56, 0xD6, 0xE1, 0xB5, 0x6D, 0x11, 0xC6, 0x70, 0x81, 0x70, 0x42, 0x02, 0xA7,
0x2B, 0x7D, 0x81, 0x51, 0x52, 0x8A},
{0xBC, 0x47, 0x5D, 0x7D, 0x59, 0xD5, 0xB9, 0x5D, 0xBA, 0x3B, 0xFF, 0xA1, 0x6B,
0x73, 0x0B, 0xBE, 0xE7, 0x6D, 0x84, 0x1D, 0x75, 0x1A, 0x26, 0x43, 0x4C, 0x97,
0xAC, 0x6D, 0x59, 0xC7, 0x01, 0x6E}, 0},
// stream
{0x04, 0x05, 0x87, 0x4E, 0x19, 0x77, 0x0D, 0xB0, 0x52, 0xFD, 0x9B, 0x73, 0xB3,
0xE8, 0x45, 0xF0, 0x7C, 0xC5, 0x1C, 0x1E, 0x0D, 0x4C, 0x61, 0x84, 0x3F, 0x97,
0xC1, 0xE7, 0x16, 0x61, 0xEC, 0xE1, 0xEF, 0x68, 0x77, 0x41, 0x3E, 0x96, 0xC2,
0xFC, 0xDA, 0x0C, 0xD0, 0xB9, 0x50, 0xA3, 0x1F, 0x9F, 0xC0, 0xFA, 0xAA, 0x32,
0x8E, 0x4A, 0xD3, 0x82, 0x72, 0x32, 0xC8, 0x3B, 0xFF, 0x88, 0xB3, 0x88, 0x9D,
0x04, 0x9E, 0xD1, 0x66, 0xDC, 0xA9, 0x11, 0x72, 0x56, 0x15, 0x1D, 0xD6, 0x96,
0x95, 0xF6, 0xDC, 0x11, 0xC2, 0x11, 0x14, 0xE6, 0x37, 0x09, 0x31, 0xDC, 0xA1,
0x03, 0x09, 0xBF, 0x1E, 0x23, 0xE4, 0x0F, 0x4A, 0xA7, 0x63, 0xB7, 0x0A, 0x71,
0x6E, 0xA9, 0xB4, 0x0B, 0xEA, 0xCF, 0x7F, 0x26, 0x83, 0xF6, 0xD0, 0xD6, 0x47,
0x51, 0x78, 0x3B, 0xE5, 0x80, 0x0E, 0x49, 0x5A, 0xAC, 0x56, 0x9E, 0xBE, 0x24,
0x04, 0xAB, 0xCB, 0xBD, 0xB3, 0x29, 0x9F, 0xDE, 0x95, 0x11, 0x81, 0xBC, 0xF0,
0x89, 0xF8, 0x5B, 0x2E, 0x1E, 0x43, 0xB2, 0xFE, 0x08, 0x99, 0x18, 0x3A, 0x55,
0xC0, 0x2F, 0x07, 0x9F, 0xAC, 0x5E, 0x38, 0x73, 0x07, 0x51, 0x23, 0xAC, 0x65,
0x8E, 0x90, 0x68, 0xC8, 0x5F, 0x83, 0x33, 0x93, 0x87, 0x52, 0xCE, 0x3C, 0x8F,
0x0D, 0xFD, 0xD0, 0xF5, 0x59, 0x44, 0xD4, 0xBE, 0xDC, 0x11, 0x13, 0xD7, 0x81,
0x04, 0x3E, 0x4D, 0x76, 0xAA, 0x8B, 0x87, 0xD6, 0x39, 0x11, 0x3F, 0x33, 0x61,
0xF2, 0x19, 0x72, 0xE5, 0xC5, 0x1B, 0xCA, 0xD6, 0x1B, 0x64, 0x80, 0x5A, 0x9F,
0xA4, 0xDE, 0xBE, 0xB0, 0x28, 0xDE, 0x76, 0xE1, 0xD0, 0xFF, 0x44, 0xD8, 0x8E,
0xC2, 0xEB, 0xD0, 0x59, 0xC9, 0x13, 0xFE, 0xF0, 0xCA, 0x19, 0xDA, 0x8A, 0x5F,
0xEE, 0xEC, 0x07, 0xF1, 0x07, 0x76, 0x22, 0x99, 0xF1, 0x80, 0x08, 0xE6, 0xBC,
0x04, 0x7C, 0x0B, 0x2C, 0x68, 0xD2, 0x5E, 0x68, 0x18, 0x03, 0x64, 0xD7, 0xF4,
0xB0, 0xF5, 0x8A, 0x43, 0xB0, 0xD2, 0xF9, 0x0C, 0x10, 0xC3, 0x6B, 0x5D, 0xC2,
0x02, 0xA5, 0xE1, 0x52, 0xD8, 0x98, 0x92, 0x26, 0xD7, 0x18, 0x58, 0x9E, 0x93,
0xA1, 0xDF, 0x7E, 0xE8, 0xF8, 0xFD, 0x5A, 0x07, 0x01, 0x77, 0x5C, 0x8B, 0x82,
0xC5, 0x07, 0x6E, 0x91, 0x4D, 0x0F, 0x5F, 0xBF, 0x89, 0x4E, 0x36, 0x2D, 0xC2,
0x04, 0x78, 0x5E, 0x7A, 0x1C, 0x13, 0x2B, 0xFD, 0x43, 0x2B, 0xE0, 0x1D, 0xBE,
0xAA, 0x8E, 0xEE, 0xE4, 0xEE, 0xC9, 0x63, 0x02, 0x01, 0x4D, 0xF6, 0x4E, 0x5D,
0x63, 0x4E, 0xAE, 0x60, 0x74, 0xB1, 0x3B, 0xE9, 0xE5, 0xAA, 0x70, 0x74, 0xFB,
0xD2, 0x2C, 0xAB, 0x66, 0x5E, 0xD5, 0x03, 0x63, 0xFF, 0x0F, 0x80, 0x85, 0xC5,
0x14, 0xE5, 0xD5, 0xB5, 0xC6, 0x8F, 0x8B, 0x08, 0x95, 0x48, 0x9F, 0x49, 0x13,
0x04, 0x7B, 0xF5, 0xD1, 0x12, 0x9D, 0xD9, 0x6D, 0x28, 0x47, 0x2B, 0x39, 0xD2,
0xE1, 0x51, 0x1A, 0x49, 0xE2, 0x13, 0xD7, 0xDA, 0x0C, 0x0E, 0x04, 0x34, 0xD4,
0x44, 0xE3, 0xB4, 0x7D, 0xF6, 0xE1, 0xB2, 0xC1, 0xED, 0x59, 0xAE, 0x0E, 0xC5,
0xA9, 0x34, 0x7D, 0xCC, 0xAA, 0x58, 0xC8, 0x5D, 0x29, 0xC4, 0x81, 0x92, 0x9E,
0x16, 0xB8, 0x76, 0xDB, 0xA2, 0xAE, 0x81, 0xB9, 0x06, 0xBD, 0x30, 0x4F, 0xAA,
0x04, 0x11, 0xB3, 0x98, 0x0C, 0xA8, 0x66, 0xCC, 0x86, 0x2B, 0xBD, 0x67, 0xBA,
0xA5, 0xA4, 0xA7, 0xAB, 0x85, 0x4A, 0xFD, 0x09, 0x23, 0x50, 0x40, 0xAB, 0x99,
0x6D, 0x0D, 0x9C, 0x8E, 0x4D, 0xBC, 0x31, 0x35, 0x2B, 0x79, 0xD1, 0xAE, 0x81,
0x14, 0x95, 0x54, 0xE9, 0x9D, 0x9B, 0xDB, 0x64, 0x4F, 0x0E, 0x1B, 0xB7, 0xAE,
0x72, 0x97, 0xB4, 0x67, 0x2F, 0x05, 0x8A, 0x1A, 0xEE, 0xD2, 0x47, 0x15, 0x0F,
0x04, 0x53, 0xCA, 0x7B, 0xAD, 0x4D, 0x20, 0xCD, 0x80, 0x81, 0x45, 0x34, 0xBE,
0x3A, 0xE5, 0xD4, 0x06, 0x42, 0x95, 0x15, 0xF3, 0xE3, 0x07, 0x54, 0xA6, 0x4E,
0x2B, 0x4A, 0xF3, 0x6B, 0xBA, 0x58, 0x78, 0xAA, 0x80, 0xB3, 0xB5, 0x68, 0x0A,
0x89, 0x31, 0x3B, 0xD0, 0x13, 0x3E, 0x67, 0x4C, 0xA3, 0x10, 0x18, 0x8F, 0x2A,
0x0E, 0x01, 0x3E, 0xB4, 0x50, 0xD0, 0xD7, 0x56, 0x33, 0xEF, 0x23, 0x34, 0x52,
0x04, 0xA2, 0x13, 0xD9, 0x02, 0x57, 0x30, 0x6E, 0x40, 0x28, 0xB4, 0xA5, 0xB6,
0x6C, 0xEA, 0xEF, 0x1D, 0xA7, 0x16, 0x97, 0xBB, 0x95, 0x8D, 0x3F, 0x55, 0x53,
0x44, 0x32, 0x5D, 0x5D, 0xC1, 0x85, 0x0A, 0xB2, 0x2F, 0xA5, 0xD8, 0x69, 0x04,
0x74, 0x78, 0x2C, 0x1E, 0xB8, 0xE5, 0x78, 0xD1, 0x22, 0x3C, 0x33, 0xC3, 0x18,
0x9E, 0xBD, 0xC4, 0x9C, 0xEC, 0xB9, 0xD6, 0x00, 0x3E, 0xBA, 0x21, 0x87, 0xB5,
0x04, 0x4F, 0xA1, 0x7E, 0x24, 0x5D, 0x9B, 0x3C, 0xE2, 0x59, 0x4B, 0x45, 0x56,
0x82, 0x14, 0x20, 0x4B, 0xCA, 0xAD, 0xAC, 0x00, 0xA2, 0x3A, 0x49, 0xA4, 0x6D,
0xB2, 0x7F, 0xB6, 0x32, 0x5C, 0xF6, 0xF1, 0x29, 0x20, 0x3C, 0x4A, 0xB8, 0xE4,
0x55, 0xA9, 0x0B, 0x8E, 0xED, 0x7D, 0x69, 0x2D, 0xF4, 0xF9, 0x5A, 0xA1, 0x8C,
0xCD, 0xCC, 0x37, 0x80, 0x48, 0xFD, 0xCF, 0xCE, 0xFA, 0x6E, 0x58, 0xF2, 0x05,
0x04, 0xF4, 0x15, 0x74, 0xED, 0xEB, 0x74, 0x7B, 0xD5, 0xEC, 0x1D, 0xE8, 0x6A,
0x4C, 0x95, 0x24, 0x99, 0x7F, 0x6C, 0xE4, 0x2E, 0xA3, 0x76, 0xE6, 0xD6, 0x61,
0xEE, 0x0E, 0xA0, 0xE3, 0xC0, 0x05, 0x68, 0x7E, 0x59, 0x18, 0xD0, 0xF9, 0x34,
0xA0, 0xAD, 0xB0, 0xC2, 0x4A, 0x5D, 0x84, 0xFC, 0x84, 0x2B, 0xBA, 0xE0, 0x1F,
0x6C, 0xF3, 0x40, 0xA0, 0x81, 0x0B, 0xDD, 0xDC, 0x1B, 0x86, 0xD5, 0x48, 0x62,
0x04, 0x9C, 0x9B, 0x0E, 0xAD, 0xB2, 0xDC, 0xC5, 0xEF, 0xC2, 0xEF, 0x76, 0x60,
0x67, 0x84, 0x20, 0x7D, 0x00, 0x61, 0xAF, 0x32, 0xB2, 0x4D, 0xF0, 0xE7, 0x68,
0x06, 0x9C, 0xB6, 0xE6, 0x65, 0xD2, 0x14, 0x0F, 0x32, 0xE1, 0xE5, 0xF2, 0xD8,
0x1F, 0x2A, 0xF5, 0x66, 0x10, 0x74, 0x12, 0xD2, 0x03, 0x23, 0x8F, 0x3D, 0x8E,
0x03, 0x13, 0x91, 0x06, 0x81, 0x2B, 0xC7, 0x64, 0x08, 0x3A, 0x00, 0x23, 0x75,
0x04, 0x3A, 0x8F, 0xA1, 0x0A, 0x41, 0xEC, 0xC0, 0x01, 0x5C, 0xD9, 0x46, 0xEB,
0x9F, 0x36, 0x08, 0x81, 0xDE, 0xF4, 0xCF, 0x37, 0xA7, 0x80, 0x74, 0xE2, 0x44,
0xE0, 0x5A, 0x08, 0x5E, 0x5F, 0x5E, 0xF9, 0x1E, 0xFE, 0x8D, 0x91, 0xB8, 0xC0,
0xF1, 0x56, 0x29, 0xA9, 0xDE, 0x45, 0x1D, 0x22, 0xF2, 0x19, 0x24, 0x14, 0x9A,
0xB4, 0x30, 0x8D, 0x47, 0x13, 0x4D, 0x39, 0xE4, 0x43, 0xFE, 0xA4, 0x05, 0xC0,
0x04, 0x3A, 0xCF, 0xC9, 0xA5, 0x85, 0x3A, 0x99, 0xC8, 0x61, 0x85, 0x8F, 0x0D,
0x10, 0x86, 0x1B, 0x2A, 0x98, 0x90, 0xAD, 0xBC, 0x86, 0xEA, 0x8B, 0x7D, 0x31,
0xFD, 0xB7, 0xCC, 0x7B, 0xC5, 0x87, 0x9C, 0x6C, 0x05, 0x7D, 0x75, 0xB2, 0x88,
0x0A, 0xB2, 0xB0, 0xCE, 0x16, 0xF7, 0xD9, 0xA1, 0xD1, 0x3E, 0x9D, 0x81, 0xA3,
0xD4, 0x77, 0x90, 0x92, 0x90, 0x18, 0x85, 0x84, 0xE6, 0x61, 0x33, 0x41, 0xE2},
975, // size_of_stream
"Got 16-of-16 address: 38tCfHAQxzXXiygokWceu4B8KXtmcTZvvW"}

};

/** The first good test case, but with an extra (junk) byte on the end of the
  * public key list. */
struct P2SHAddrGenTestCase junk_at_end_test = {
2, // num_sigs
3, // num_pubkeys
2, // supplied_pubkey_num
// public_key
{{0xd9, 0xff, 0x13, 0xe7, 0xb4, 0xc8, 0x09, 0x00, 0xb9, 0x00, 0x32, 0x68, 0xe2,
0xfc, 0xcb, 0x9f, 0x34, 0x61, 0x36, 0x73, 0x2f, 0x75, 0x8d, 0xef, 0xb3, 0xae,
0x92, 0x59, 0xd8, 0xbb, 0x3f, 0xeb},
{0xb7, 0xda, 0x7c, 0xba, 0x93, 0xc4, 0xf3, 0xf4, 0xf9, 0x17, 0x5b, 0x0c, 0x6f,
0x58, 0x29, 0xa7, 0xdc, 0x1c, 0xd5, 0x6e, 0xd6, 0xd6, 0x8e, 0xa1, 0xcc, 0x22,
0x0e, 0x84, 0x7f, 0xfc, 0xa9, 0x3d}, 0},
// stream
{0x04, 0xd4, 0xf8, 0x1d, 0x9c, 0x28, 0x41, 0x3d, 0x30, 0x19, 0xa2, 0x02, 0xe6,
0x3a, 0x82, 0x8c, 0x88, 0x4d, 0xca, 0xff, 0xa0, 0x94, 0xa9, 0xe6, 0x6f, 0xb8,
0xde, 0xc6, 0x23, 0xa1, 0x44, 0x5d, 0x3f, 0xe0, 0x99, 0xca, 0x7c, 0x30, 0x87,
0xc1, 0x3a, 0xc6, 0xb6, 0x2a, 0xd7, 0xf5, 0x47, 0xef, 0xf2, 0x5d, 0xf5, 0x52,
0xe9, 0x4e, 0x12, 0xf6, 0xfb, 0xfc, 0x45, 0x35, 0xc1, 0xc2, 0xb4, 0xb7, 0x8a,
0x04, 0x20, 0xc4, 0x1c, 0xb7, 0x22, 0x08, 0x29, 0x43, 0xe7, 0xda, 0x60, 0x25,
0x57, 0xb2, 0xe2, 0x8a, 0x84, 0xeb, 0xad, 0x90, 0xbd, 0xfb, 0xae, 0x84, 0x99,
0xd9, 0xae, 0x77, 0xa3, 0x75, 0x25, 0x70, 0xd7, 0x11, 0x64, 0x9b, 0x2e, 0x54,
0xf8, 0x7b, 0x90, 0x64, 0xb7, 0xdc, 0x72, 0xf5, 0xf9, 0x62, 0x03, 0xa7, 0x82,
0xe8, 0x2c, 0xfc, 0x08, 0xa5, 0xac, 0x57, 0x6d, 0x93, 0x3c, 0xa9, 0x2d, 0xe1,
0x00},
131, // size_of_stream
"Got 2-of-3 address: 3G2v3VJZ46fjgLMqEF3CzLq3k9FPMgauh4"
};

/** Run one unit test.
  * \param test_case Specifies test case data.
  * \param length What to pass as the length parameter of
  *               generateMultiSigAddress().
  * \param expected_return Expected return value of generateMultiSigAddress().
  * \param test_name Text containing name of the test (eg. "good_test1")
  */
static void runTest(struct P2SHAddrGenTestCase *test_data, uint32_t length, P2SHGeneratorErrors expected_return, const char *test_name)
{
	P2SHGeneratorErrors actual_return;

	setTestInputStream(test_data->stream, length);
	actual_return = generateMultiSigAddress(
			test_data->num_sigs,
			test_data->num_pubkeys,
			test_data->supplied_pubkey_num,
			&(test_data->public_key),
			length);
	// Check return value is what was expected.
	if (actual_return != expected_return)
	{
		printf("Test \"%s\" return mismatch\n", test_name);
		printf("  Got: %d, expected: %d\n", (int)actual_return, (int)expected_return);
		reportFailure();
	}
	else
	{
		// Then check that the parser consumed exactly length bytes.
		if (public_key_list_index != length)
		{
			printf("generateMultiSigAddress() consumption mismatch in test \"%s\"\n", test_name);
			printf("  Got: %u, expected: %u\n", public_key_list_index, length);
			reportFailure();
		}
		else
		{
			if (actual_return == P2SHGEN_NO_ERROR)
			{
				// Need to also check if actual address matches expected address.
				if (strcmp(test_data->expected_result, last_displayed_address))
				{
					printf("Address of test \"%s\" doesn't match\n", test_name);
					printf("  Got: %s\n", last_displayed_address);
					printf("  Expected: %s\n", test_data->expected_result);
					reportFailure();
				}
				else
				{
					reportSuccess();
				}
			}
			else
			{
				reportSuccess();
			}
		} // end if (public_key_list_index != length)
	} // end if (actual_return != expected_return)
}

/** Run one fuzzer test. The fuzzer will mutate the stream with insertion,
  * deletion and modification, then run the parser over that stream. The
  * parser should then fail to produce the correct address.
  * \param test_number The fuzzer test number.
  */
static void oneFuzzTest(unsigned int test_number)
{
	int i;
	int j;
	int num_mutations;
	int mutation_number;
	int mutation_location;
	bool failed;
	P2SHGeneratorErrors return_value;
	struct P2SHAddrGenTestCase *source_test_case;
	struct P2SHAddrGenTestCase fuzzed_test_case;

	// Mutate the stream.
	source_test_case = &(good_tests[0]);
	memcpy(&fuzzed_test_case, source_test_case, sizeof(fuzzed_test_case));
	// There is a very small possibility that mutations will undo each
	// other. If that is the case, further mutations are done until the
	// stream no longer resembles the original.
	while ((fuzzed_test_case.size_of_stream == source_test_case->size_of_stream)
		&& !memcmp(fuzzed_test_case.stream, source_test_case->stream, fuzzed_test_case.size_of_stream))
	{
		num_mutations = (rand() % 3) + 1; // between 1 and 3 mutations
		for (i = 0; i < num_mutations; i++)
		{
			mutation_number = rand() % 3;
			if (mutation_number == 0)
			{
				// Mutate: insertion of random character in random spot.
				mutation_location = rand() % (int)(fuzzed_test_case.size_of_stream + 1);
				fuzzed_test_case.size_of_stream++;
				for (j = (int)(fuzzed_test_case.size_of_stream - 1); j > mutation_location; j--)
				{
					fuzzed_test_case.stream[j] = fuzzed_test_case.stream[j - 1];
				}
				fuzzed_test_case.stream[mutation_location] = (uint8_t)rand();
			}
			else if (mutation_number == 1)
			{
				// Mutate: deletion of random character.
				mutation_location = rand() % (int)(fuzzed_test_case.size_of_stream);
				fuzzed_test_case.size_of_stream--;
				for (j = mutation_location; j < (int)fuzzed_test_case.size_of_stream; j++)
				{
					fuzzed_test_case.stream[j] = fuzzed_test_case.stream[j + 1];
				}
			}
			else
			{
				// Mutate: modification of one bit in random spot.
				mutation_location = rand() % (int)(fuzzed_test_case.size_of_stream);
				fuzzed_test_case.stream[mutation_location] ^= (uint8_t)(1 << (rand() & 7));
			} // end if (mutation_number == 0)
		} // end for (i = 0; i < num_mutations; i++)
	} // end while ...

	// Now run the parser. It should never succeed in generating the correct
	// address.
	setTestInputStream(fuzzed_test_case.stream, fuzzed_test_case.size_of_stream);
	return_value = generateMultiSigAddress(
			fuzzed_test_case.num_sigs,
			fuzzed_test_case.num_pubkeys,
			fuzzed_test_case.supplied_pubkey_num,
			&(fuzzed_test_case.public_key),
			fuzzed_test_case.size_of_stream);
	if (return_value != P2SHGEN_NO_ERROR)
	{
		failed = true;
	}
	else
	{
		if (strcmp(fuzzed_test_case.expected_result, last_displayed_address))
		{
			failed = true;
		}
		else
		{
			failed = false; // the parser did succeed in generating the correct address!
		}
	}
	if (!failed)
	{
		printf("Fuzzer test %u unexpectedly succeeded\n", test_number);
		reportFailure();
	}
	else
	{
		// Also check that the parser ate up the correct number of bytes each
		// time.
		if (public_key_list_index != fuzzed_test_case.size_of_stream)
		{
			printf("generateMultiSigAddress() consumption mismatch in fuzzer test %u\n", test_number);
			printf("  Got: %u, expected: %u\n", public_key_list_index, fuzzed_test_case.size_of_stream);
			reportFailure();
		}
		else
		{
			reportSuccess();
		}
	}
}

int main(void)
{
	unsigned int i;
	unsigned int num_tests;
	char test_name[1024];
	struct P2SHAddrGenTestCase test_case;

	initTests(__FILE__);
	srand(42);

	// All good tests should be successful.
	num_tests = sizeof(good_tests) / sizeof(struct P2SHAddrGenTestCase);
	for (i = 0; i < num_tests; i++)
	{
		sprintf(test_name, "good_test%u", i);
		runTest(&(good_tests[i]), good_tests[i].size_of_stream, P2SHGEN_NO_ERROR, test_name);
	} // end for (i = 0; i < num_tests; i++)

	// Truncate public key list. generateMultiSigAddress() should always
	// return P2SHGEN_INVALID_FORMAT.
	for (i = 0; i < good_tests[0].size_of_stream; i++)
	{
		sprintf(test_name, "truncation%u", i);
		runTest(&(good_tests[0]), i, P2SHGEN_INVALID_FORMAT, test_name);
	}

	// Check that parser rejects public key list if there is junk at the end
	// of it.
	runTest(&junk_at_end_test, junk_at_end_test.size_of_stream, P2SHGEN_INVALID_FORMAT, "junk_at_end");

	// Sanity check.
	memcpy(&test_case, &(good_tests[0]), sizeof(test_case));
	runTest(&test_case, test_case.size_of_stream, P2SHGEN_NO_ERROR, "sanity_check1");

	// The parser should not accept corrupted public keys.
	memcpy(&test_case, &(good_tests[0]), sizeof(test_case));
	test_case.stream[0] = 0x00;
	runTest(&test_case, test_case.size_of_stream, P2SHGEN_UNKNOWN_PUBLIC_KEY, "bad_pubkey1");
	memcpy(&test_case, &(good_tests[0]), sizeof(test_case));
	test_case.stream[65] = 0xff;
	runTest(&test_case, test_case.size_of_stream, P2SHGEN_UNKNOWN_PUBLIC_KEY, "bad_pubkey2");

	// Sanity check.
	memcpy(&test_case, &(good_tests[4]), sizeof(test_case));
	runTest(&test_case, test_case.size_of_stream, P2SHGEN_NO_ERROR, "sanity_check");

	// Mess with number of required signatures.
	memcpy(&test_case, &(good_tests[4]), sizeof(test_case));
	test_case.num_sigs = 0;
	runTest(&test_case, test_case.size_of_stream, P2SHGEN_BAD_NUMBER, "num_sigs0");
	memcpy(&test_case, &(good_tests[4]), sizeof(test_case));
	test_case.num_sigs = 17;
	runTest(&test_case, test_case.size_of_stream, P2SHGEN_BAD_NUMBER, "num_sigs17");
	memcpy(&test_case, &(good_tests[4]), sizeof(test_case));
	test_case.num_sigs = 255;
	runTest(&test_case, test_case.size_of_stream, P2SHGEN_BAD_NUMBER, "num_sigs255");

	// Mess with number of public keys.
	memcpy(&test_case, &(good_tests[4]), sizeof(test_case));
	test_case.num_pubkeys = 0;
	runTest(&test_case, test_case.size_of_stream, P2SHGEN_BAD_NUMBER, "num_pubkeys0");
	memcpy(&test_case, &(good_tests[4]), sizeof(test_case));
	test_case.num_pubkeys = 1;
	runTest(&test_case, test_case.size_of_stream, P2SHGEN_BAD_NUMBER, "num_pubkeys1");
	memcpy(&test_case, &(good_tests[4]), sizeof(test_case));
	test_case.num_pubkeys = 17;
	runTest(&test_case, test_case.size_of_stream, P2SHGEN_BAD_NUMBER, "num_pubkeys17");
	memcpy(&test_case, &(good_tests[4]), sizeof(test_case));
	test_case.num_pubkeys = 255;
	runTest(&test_case, test_case.size_of_stream, P2SHGEN_BAD_NUMBER, "num_pubkeys255");
	memcpy(&test_case, &(good_tests[4]), sizeof(test_case));
	test_case.num_pubkeys = (uint8_t)(test_case.num_sigs - 1);
	runTest(&test_case, test_case.size_of_stream, P2SHGEN_BAD_NUMBER, "too_many_sigs");

	// Mess with supplied public key number.
	memcpy(&test_case, &(good_tests[0]), sizeof(test_case));
	test_case.supplied_pubkey_num = test_case.num_pubkeys;
	runTest(&test_case, test_case.size_of_stream, P2SHGEN_BAD_NUMBER, "bad_pubkey_num1");
	memcpy(&test_case, &(good_tests[0]), sizeof(test_case));
	test_case.supplied_pubkey_num = (uint8_t)(test_case.num_pubkeys + 1);
	runTest(&test_case, test_case.size_of_stream, P2SHGEN_BAD_NUMBER, "bad_pubkey_num2");
	memcpy(&test_case, &(good_tests[0]), sizeof(test_case));
	test_case.supplied_pubkey_num = 255;
	runTest(&test_case, test_case.size_of_stream, P2SHGEN_BAD_NUMBER, "bad_pubkey_num3");

	// Run fuzzer.
	suppress_display_address = true;
	for (i = 0; i < 100000; i++)
	{
		oneFuzzTest(i);
	}
	suppress_display_address = false;

	finishTests();
	exit(0);
}
#endif // #ifdef TEST_P2SH_ADDR_GEN