LINQPad Merkle Tree Algo

void Main()
{
	foreach (var txSet in Enum.GetValues(typeof(TransactionSet)))
	{
		Console.WriteLine("\n\n\n");
		"".PadRight(120, '=').Dump($"Performing test on {txSet}");
		PerformTest((TransactionSet)txSet);
	}
}

public void PerformTest(TransactionSet transactionSet)
{
	List<string> transactions = GetTransactions(transactionSet).Select(c => c.ToString()).ToList();
	uint transactionsCount = ((uint)transactions.Count);
	bool transactionCountIsOdd = (transactionsCount & 1) == 1;
	uint higherBitPosition = (uint)(sizeof(uint) * 8 - (BitOperations.LeadingZeroCount(transactionsCount - 1) + 1));
	uint safePoint = ((uint)Math.Pow(2, higherBitPosition));
	uint itemsToConsider = transactionsCount - safePoint;

	(string.Join(" ", transactions).ToUpper() + $"\n{"".PadLeft((int)safePoint * 2, '_')}" + $"{"".PadLeft((int)itemsToConsider * 2, '~')}").Dump("Transactions");
	transactionsCount.Dump($"Transaction Count. Is Odd? {transactionCountIsOdd}");
	Convert.ToString(transactionsCount, 2).PadLeft(32, '0').Dump("Transaction Count (Binary)");
	safePoint.Dump("Safe Point (transaction before this Nth transaction, starting from left, cannot be manipulated)");
	itemsToConsider.Dump("Number of transactions that could be manipulated)");
	ComputeMerkleRoot(transactions).Dump("Computed Merkle Root");

	string transactionToFind = transactions.Last();
	//	int lastTransactionIndex = transactions.Count - 1;
	int transactionIndexToCompare = transactions.Count - 2;
	int expStep = transactionCountIsOdd ? 2 : 1;

	int numberOfChecks = 0;
	while (expStep < itemsToConsider)
	{
		numberOfChecks++;
		$"comparing {transactionToFind} with {transactions[transactionIndexToCompare]}".Dump();
		if (transactions[transactionIndexToCompare] == transactionToFind)
		{
			"".PadRight(120, '-').Dump($"FOUND MALLEABLE BLOCK: {transactionToFind} found both on last position and at position {transactionIndexToCompare}. Checks performed: {numberOfChecks})");
			return;
		}

		transactionIndexToCompare -= expStep;
		expStep <<= 1;
	}

	"".PadRight(120, '+').Dump($"SAFE BLOCK!!!! Checks performed: {numberOfChecks}");
}

public enum TransactionSet { Valid1, Mal1, Valid2, Mal2, Valid3, Mal3, Valid4, Mal4, Valid5, Mal5, Valid6, Mal6 }

// Define other methods, classes and namespaces here
public IEnumerable<char> GetTransactions(TransactionSet transactionSet)
{
	switch (transactionSet)
	{
		case TransactionSet.Valid1:
			return "ABCDEFGH".Concat("I");
		case TransactionSet.Valid2:
			return "ABCDEFGH".Concat("IL");
		case TransactionSet.Valid3:
			return "ABCDEFGH".Concat("ILM");
		case TransactionSet.Valid4:
			return "ABCDEFGH".Concat("ILMN");
		case TransactionSet.Valid5:
			return "ABCDEFGH".Concat("ILMNOPQR");
		case TransactionSet.Valid6:
			return "ABCDEFGH".Concat("ILMNOPQR").Concat("ST");
		case TransactionSet.Mal1:
			return "ABCDEFGH".Concat("II");
		case TransactionSet.Mal2:
			return "ABCDEFGH".Concat("ILIL");
		case TransactionSet.Mal3:
			return "ABCDEFGH".Concat("ILMMILMM");
		case TransactionSet.Mal4:
			return "ABCDEFGH".Concat("ILMNILMN");
		case TransactionSet.Mal5:
			return "ABCDEFGH".Concat("ILMNOOOO");
		case TransactionSet.Mal6:
			return "ABCDEFGH".Concat("ILMNOPQR").Concat("STUVZJKX").Concat("WYWY");
	}

	throw new ArgumentException("Invalid transaction set");
}

// not a bitcoin double hash, not important for POC code
public string ComputeMerkleRoot(IList<string> hashes)
{
	if (hashes.Count == 0) return String.Empty;

	bool oddHashes = (hashes.Count & 1) == 1;
	//ensure to allocate one more item if hashes are odd.
	List<string> hashesList = new List<string>(oddHashes ? hashes.Count + 1 : hashes.Count);

	for (int i = 0; i < hashes.Count; i++)
	{
		hashesList.Add(hashes[i]);
	}

	// if odd, duplicate last element
	if (oddHashes)
	{
		hashesList.Add(hashes[hashes.Count - 1]);
	}

	var hashAlgo = HashAlgorithm.Create("SHA256");
	int elementsCount = hashesList.Count;
	while (elementsCount > 1)
	{
		int newHashPosition = 0;
		for (int pos = 0; pos + 1 < elementsCount; pos += 2)
		{
			string pairOfHashes = hashesList[pos] + hashesList[pos + 1];

			hashesList[newHashPosition++] = ASCIIEncoding.Unicode.GetString(hashAlgo.ComputeHash(ASCIIEncoding.Unicode.GetBytes(pairOfHashes)));
		}

		if (newHashPosition > 1 && (newHashPosition & 1) == 1)
		{
			hashesList[newHashPosition] = hashesList[newHashPosition - 1];
			newHashPosition++;
		}

		hashesList.RemoveRange(newHashPosition, elementsCount - newHashPosition);
		elementsCount = newHashPosition;
	}

	return BitConverter.ToString(ASCIIEncoding.Unicode.GetBytes(hashesList[0])).Replace("-", "");
}

this is the result

Performing test on Valid1

========================================================================================================================


Transactions

A B C D E F G H I
________________~~


Transaction Count. Is Odd? True

9


Transaction Count (Binary)

00000000000000000000000000001001


Power of 2 mask

00000000000000000000000000001000


Is transaction count a power of two?

False


Safe Point (transaction before this Nth transaction, starting from left, cannot be manipulated)

8


Number of transactions that could be manipulated)

1


Computed Merkle Root

31B29F06A728206AD0FAB67F8BB4FDFF8A37B2AEB97658BF9104B522BE22FDFF


SAFE BLOCK!!!! Checks performed: 0

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++






Performing test on Mal1

========================================================================================================================


Transactions

A B C D E F G H I I
________________~~~~


Transaction Count. Is Odd? False

10


Transaction Count (Binary)

00000000000000000000000000001010


Power of 2 mask

00000000000000000000000000001000


Is transaction count a power of two?

False


Safe Point (transaction before this Nth transaction, starting from left, cannot be manipulated)

8


Number of transactions that could be manipulated)

2


Computed Merkle Root

31B29F06A728206AD0FAB67F8BB4FDFF8A37B2AEB97658BF9104B522BE22FDFF
comparing I with I


FOUND MALLEABLE BLOCK: I found both on last position and at position 8. Checks performed: 1)

------------------------------------------------------------------------------------------------------------------------






Performing test on Valid2

========================================================================================================================


Transactions

A B C D E F G H I L
________________~~~~


Transaction Count. Is Odd? False

10


Transaction Count (Binary)

00000000000000000000000000001010


Power of 2 mask

00000000000000000000000000001000


Is transaction count a power of two?

False


Safe Point (transaction before this Nth transaction, starting from left, cannot be manipulated)

8


Number of transactions that could be manipulated)

2


Computed Merkle Root

5206D7B70C172F920DCCD033FDFF44E62574E25BE25D953B4792330B7B7EF0F7
comparing L with I


SAFE BLOCK!!!! Checks performed: 1

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++






Performing test on Mal2

========================================================================================================================


Transactions

A B C D E F G H I L I L
________________~~~~~~~~


Transaction Count. Is Odd? False

12


Transaction Count (Binary)

00000000000000000000000000001100


Power of 2 mask

00000000000000000000000000001000


Is transaction count a power of two?

False


Safe Point (transaction before this Nth transaction, starting from left, cannot be manipulated)

8


Number of transactions that could be manipulated)

4


Computed Merkle Root

5206D7B70C172F920DCCD033FDFF44E62574E25BE25D953B4792330B7B7EF0F7
comparing L with I
comparing L with L


FOUND MALLEABLE BLOCK: L found both on last position and at position 9. Checks performed: 2)

------------------------------------------------------------------------------------------------------------------------






Performing test on Valid3

========================================================================================================================


Transactions

A B C D E F G H I L M
________________~~~~~~


Transaction Count. Is Odd? True

11


Transaction Count (Binary)

00000000000000000000000000001011


Power of 2 mask

00000000000000000000000000001000


Is transaction count a power of two?

False


Safe Point (transaction before this Nth transaction, starting from left, cannot be manipulated)

8


Number of transactions that could be manipulated)

3


Computed Merkle Root

CB70A2912D2424FF1F925C7D874AB6682652649E684310346496EAB8610BBB29
comparing M with L


SAFE BLOCK!!!! Checks performed: 1

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++






Performing test on Mal3

========================================================================================================================


Transactions

A B C D E F G H I L M M I L M M
________________~~~~~~~~~~~~~~~~


Transaction Count. Is Odd? False

16


Transaction Count (Binary)

00000000000000000000000000010000


Power of 2 mask

00000000000000000000000000010000


Is transaction count a power of two?

True


Safe Point (transaction before this Nth transaction, starting from left, cannot be manipulated)

8


Number of transactions that could be manipulated)

8


Computed Merkle Root

CB70A2912D2424FF1F925C7D874AB6682652649E684310346496EAB8610BBB29
comparing M with M


FOUND MALLEABLE BLOCK: M found both on last position and at position 14. Checks performed: 1)

------------------------------------------------------------------------------------------------------------------------






Performing test on Valid4

========================================================================================================================


Transactions

A B C D E F G H I L M N
________________~~~~~~~~


Transaction Count. Is Odd? False

12


Transaction Count (Binary)

00000000000000000000000000001100


Power of 2 mask

00000000000000000000000000001000


Is transaction count a power of two?

False


Safe Point (transaction before this Nth transaction, starting from left, cannot be manipulated)

8


Number of transactions that could be manipulated)

4


Computed Merkle Root

3B778256093581FCC23149351479FFC8AB745B22AC3FBA85EA024F0FA3AEFA02
comparing N with M
comparing N with L


SAFE BLOCK!!!! Checks performed: 2

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++






Performing test on Mal4

========================================================================================================================


Transactions

A B C D E F G H I L M N I L M N
________________~~~~~~~~~~~~~~~~


Transaction Count. Is Odd? False

16


Transaction Count (Binary)

00000000000000000000000000010000


Power of 2 mask

00000000000000000000000000010000


Is transaction count a power of two?

True


Safe Point (transaction before this Nth transaction, starting from left, cannot be manipulated)

8


Number of transactions that could be manipulated)

8


Computed Merkle Root

3B778256093581FCC23149351479FFC8AB745B22AC3FBA85EA024F0FA3AEFA02
comparing N with M
comparing N with L
comparing N with N


FOUND MALLEABLE BLOCK: N found both on last position and at position 11. Checks performed: 3)

------------------------------------------------------------------------------------------------------------------------






Performing test on Valid5

========================================================================================================================


Transactions

A B C D E F G H I L M N O P Q R
________________~~~~~~~~~~~~~~~~


Transaction Count. Is Odd? False

16


Transaction Count (Binary)

00000000000000000000000000010000


Power of 2 mask

00000000000000000000000000010000


Is transaction count a power of two?

True


Safe Point (transaction before this Nth transaction, starting from left, cannot be manipulated)

8


Number of transactions that could be manipulated)

8


Computed Merkle Root

C2B5E9B41A9C923764ECA60A789106FE226BFDFF90B8EC8CDAAE503E649357FB
comparing R with Q
comparing R with P
comparing R with N


SAFE BLOCK!!!! Checks performed: 3

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++






Performing test on Mal5

========================================================================================================================


Transactions

A B C D E F G H I L M N O O O O
________________~~~~~~~~~~~~~~~~


Transaction Count. Is Odd? False

16


Transaction Count (Binary)

00000000000000000000000000010000


Power of 2 mask

00000000000000000000000000010000


Is transaction count a power of two?

True


Safe Point (transaction before this Nth transaction, starting from left, cannot be manipulated)

8


Number of transactions that could be manipulated)

8


Computed Merkle Root

A55997EAA03B5003245D0B92320F48ED3F70FDFF5EBBFF373F52504CFCF0FDFF
comparing O with O


FOUND MALLEABLE BLOCK: O found both on last position and at position 14. Checks performed: 1)

------------------------------------------------------------------------------------------------------------------------






Performing test on Valid6

========================================================================================================================


Transactions

A B C D E F G H I L M N O P Q R S T
________________________________~~~~


Transaction Count. Is Odd? False

18


Transaction Count (Binary)

00000000000000000000000000010010


Power of 2 mask

00000000000000000000000000010000


Is transaction count a power of two?

False


Safe Point (transaction before this Nth transaction, starting from left, cannot be manipulated)

16


Number of transactions that could be manipulated)

2


Computed Merkle Root

A5A7B8E0C2D7424C6E801AE85942286FA9502BC896AC466CF7BB27E8D41D4F42
comparing T with S


SAFE BLOCK!!!! Checks performed: 1

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++






Performing test on Mal6

========================================================================================================================


Transactions

A B C D E F G H I L M N O P Q R S T U V Z J K X W Y W Y
________________________________~~~~~~~~~~~~~~~~~~~~~~~~


Transaction Count. Is Odd? False

28


Transaction Count (Binary)

00000000000000000000000000011100


Power of 2 mask

00000000000000000000000000010000


Is transaction count a power of two?

False


Safe Point (transaction before this Nth transaction, starting from left, cannot be manipulated)

16


Number of transactions that could be manipulated)

12


Computed Merkle Root

D410E10378718E88C837899BD1A4607D56EC63A661E2C30BBD2FE008C86F34F5
comparing Y with W
comparing Y with Y


FOUND MALLEABLE BLOCK: Y found both on last position and at position 25. Checks performed: 2)

------------------------------------------------------------------------------------------------------------------------