Put extra field in the protocol: enforce sorted TLV format (with restricted tags) about research-lab

[UkoeHB]

UPDATE

Here are some additional, minor thoughts, I had.

1. Reserve the first 32 tags for protocol-specific tags. This means all tags 0x0#, and 0x1# belong to the protocol.
2. Ban use of padding bytes 0x00 outside of fields.
3. Put encrypted payment IDs in type field 0x05 with non-declared length 8 (no length byte).
4. Mandate non-declared extra nonce length 32 (no more subfields, just 0x02 then 32 bytes similar to the public key tag 0x01). Unencrypted payment IDs can still be supported by implementations that really want to, assuming minor changes to parsing.

[UkoeHB]

Pseudo code for verifying a transaction has sorted TLV format.
enforced_sorted_TLV_extrafield_pseudocode.txt

UPDATE: added sorting, made check_extra_tags_found() O(N).
UPDATE2: fixed indexing. Note that to extend types and lengths beyond 254 I do a simple sum, but there may be more utility to encode them as varints.
UPDATE3: moved getting a value's length to a new function
UPDATE4: simplified code around getting types and lengths
UPDATE5: start extraIndex at -1

//Pseudocode for verifying enforced sorted TLV format in extra field


//---------------------------------------------------------------------------------
//cryptonote_config.h

#define HF_VERSION_BEGIN_ENFORCING_EXTRA_FIELD	13


//---------------------------------------------------------------------------------
//tx_extra_enforced.h

#define EXTRA_TAG_PADDING					0x00
#define EXTRA_TAG_TX_PUBLIC_KEY				0x01
#define EXTRA_TAG_EXTRA_NONCE				0x02
#define EXTRA_TAG_ADDITIONAL_PUBLIC_KEYS	0x04
#define EXTRA_TAG_ENCRYPTED_PAYMENT_ID		0x05

#define EXTRA_TAG_FIRST_UNRESTRICTED		0x20

//---------------------------------------------------------------------------------
//validate_protocol_expectations.cpp


namespace validate_consensus_protocol
{
	namespace transactions
	{
		function bool check_tx_semantic(transaction tx)
		{
			int current_hf_version{get_hf_version()};

			...

			//at one point the field was not enforced in any way, so there was no need to validate it
			if (current_hf_version >= HF_VERSION_BEGIN_ENFORCING_EXTRA_FIELD) then
				if !(extra_field::extra_field_format_is_valid(tx, current_hf_version)) then
					return false;

			...

			return true;
		}

		namespace extra_field
		{
			function bool check_extra_tags_found(unsigned intVector tags_found, transaction tx, int hf_version)
			{
				if (hf_version >= HF_VERSION_BEGIN_ENFORCING_EXTRA_FIELD) then
				{
					unsigned int num_outs{tx.num_outs};
					unsigned intVector count_tags[EXTRA_TAG_FIRST_UNRESTRICTED]; //initialize to all 0s

					for (int tags_foundIndex; tags_foundIndex = 0 to size(tags_found) - 1)
					{
						if (tags_found[tags_foundIndex] < EXTRA_TAG_FIRST_UNRESTRICTED) then
							count_tags[tags_found[tags_foundIndex]] += 1;
					}

					//should only be one lone tx public key
					if (count_tags[EXTRA_TAG_TX_PUBLIC_KEY] > 1) then
						return false;

					//should only be one lone extra nonce
					if (count_tags[EXTRA_TAG_EXTRA_NONCE] > 1) then
						return false;

					//should only be one lone extra tx public keys
					if (count_tags[EXTRA_TAG_ADDITIONAL_PUBLIC_KEYS] > 1) then
						return false;

					//should only be one lone encrypted payment ID
					if (count_tags[EXTRA_TAG_ENCRYPTED_PAYMENT_ID] > 1) then
						return false;
					else if (num_outs == 2) then
						//encrypted payment ID expected
						if !(count_tags[EXTRA_TAG_ENCRYPTED_PAYMENT_ID] == 1) then
							return false;
				}

				return true;
			}

			//get value/length and number of its bytes; if a byte is 255 then we add the next byte to it, and so on
			function unsigned int get_extra_field_value_or_length(const int &extraIndex, const byteVector &extra_field, unsigned int &num_bytes, const unsigned int& field_size)
			{
				unsigned int add_length{1};	//1 by default to force the while loop to start
				unsigned int value_length{0};

				//the '+ 1' is because we begin by looking at the byte next to our initial extra index
				while ((value_length % 255 == 0) && (add_length != 0) && (extraIndex + num_bytes + 1 < field_size))
				{
					num_bytes += 1;

					add_length = extra_field[extraIndex + num_bytes];
					value_length += add_length;
				}

				return value_length;
			}


			//all the rules around different restricted extra field types are here; return false for disallowed types or behaviors
			//updates extraIndex to land on the last byte of a value's field
			function bool pass_over_extra_field_value_length(int &extraIndex, unsigned int test_type, byteVector extra_field, unsigned int field_size, int hf_version)
			{
				if (hf_version >= HF_VERSION_BEGIN_ENFORCING_EXTRA_FIELD)
				{
					unsigned int type_length{0};
					unsigned int num_length_bytes{0};

					type_length = get_extra_field_value_or_length(extraIndex, extra_field, num_length_bytes, field_size);

					if (test_type < EXTRA_TAG_FIRST_UNRESTRICTED) then
					{
						switch(test_type)
						{
							case EXTRA_TAG_PADDING

								//padding bytes disallowed
								return false;
							
							case EXTRA_TAG_TX_PUBLIC_KEY

								if (num_length_bytes == 0) then
									return false;

								//the transaction public key is 32 bytes, and has no length byte
								extraIndex += 32;

							case EXTRA_TAG_EXTRA_NONCE

								if (num_length_bytes == 0) then
									return false;

								//the extra nonce is 32 bytes, and has no length byte
								extraIndex += 32;

							case EXTRA_TAG_ADDITIONAL_PUBLIC_KEYS

								if (num_length_bytes == 0) then
									return false;

								//the additional public keys is 32 bytes per key, and length is number of keys
								extraIndex += (32*type_length + num_length_bytes);

							case EXTRA_TAG_ENCRYPTED_PAYMENT_ID

								if (num_length_bytes == 0) then
									return false;

								//the encrypted payment ID is 8 bytes, and has no length byte
								extraIndex += 8;

							case else

								//other restricted tags disallowed
								return false;
						}
					}
					else
					{
						if (num_length_bytes == 0) then
							return false;

						//straightforward TLV is expected for all non-restricted types
						//+num_length_bytes moves index to position of last length byte, then value length moves to last byte of value
						extraIndex += (type_length + num_length_bytes);
					}
				}

				return true;
			}


			//enforced sorted TLV format
			function bool extra_field_format_is_valid(transaction tx, int hf_version)
			{
				if (hf_version >= HF_VERSION_BEGIN_ENFORCING_EXTRA_FIELD) then
				{
					byteVector extra_field{tx.extra};
					int extraIndex{-1};
					unsigned int field_size{size(extra_field)};
					unsigned intVector tags_found;
					unsigned int temp_type{0};
					unsigned int num_type_bytes{0};
					unsigned int prev_type{0};

					//loop ends when we land on the last byte (or go past the field size)
					while (extraIndex < field_size - 1)
					{
						//get type
						temp_type = get_extra_field_value_or_length(extraIndex, extra_field, num_type_bytes, field_size);

						//move extra index to last byte of the type
						extraIndex += num_type_bytes;

						//types should be in ascending order, duplicates are allowed at this stage
						if (temp_type < prev_type) then
							return false;

						//get length, and skip to the end of this type's value field; it returns false due to invalid types or when a length byte is expected but not found
						if !(pass_over_extra_field_value_length(extraIndex, temp_type, extra_field, field_size, hf_version)) then
							return false;

						tags_found.push_back(temp_type);

						//move on to the next type
						prev_type = temp_type;
					}

					//in case we have requirements around which tags should be in the field
					if !check_extra_tags_found(tags_found, tx, hf_version) then
						return false;

					//these only line up when TLV format is obeyed, i.e. when the last byte of the last type field is the last byte of the extra field
					return extraIndex == (field_size - 1);
				}

				return true;
			}
		}
	}
}
//---------------------------------------------------------------------------------

[Mitchellpkt]

Here's what we've observed in practice, recently: