using System;

using System.Text;

using System.Security.Cryptography;

using System.Numerics;

using System.Linq;

using System.Collections.Generic;

​

public class Program

{

    static 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 static 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 static 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 static 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("-", "");

    }

}

​

public static class Extensions

{

    public static T Dump<T>(this T src, string text)

    {

        Console.WriteLine(text);

        Console.WriteLine(src.ToString());

        return src;

    }

}