Merkle木

Merkle木を作りました。

 

public class MerkleTree<T> where T : HASHBASE
{
    public MerkleTree(T[] _hashes)
    {
        hashes = new List<T>();
        tree = new T[1][];
        tree[0] = new T[0];
 
        Add(_hashes);
    }
 
    public List<T> hashes { getprivate set; }
    public T[][] tree { getprivate set; }
 
    public T Root
    {
        get
        {
            if (hashes.Count == 0)
                throw new InvalidOperationException("Merkle_tree_empty");
 
            return tree[tree.Length - 1][0];
        }
    }
 
    public void Add(T[] hs)
    {
        int start = hashes.Count;
        hashes.AddRange(hs);
        int end = hashes.Count;
 
        if (tree[0].Length < hashes.Count)
        {
            int newLength = tree[0].Length;
            int newHeight = tree.Length;
            while (newLength < hashes.Count)
                if (newLength == 0)
                    newLength++;
                else
                {
                    newLength *= 2;
                    newHeight++;
                }
 
            T[][] newTree = new T[newHeight][];
            for (int i = 0; i < newTree.Length; i++, newLength /= 2)
                newTree[i] = new T[newLength];
 
            for (int i = 0; i < tree.Length; i++)
                for (int j = 0; j < tree[i].Length; j++)
                    newTree[i][j] = tree[i][j];
 
            tree = newTree;
 
            end = tree[0].Length;
        }
 
        for (int j = start; j < end; j++)
            if (j < hashes.Count)
                tree[0][j] = hashes[j];
            else
                tree[0][j] = hashes[hashes.Count - 1];
        start /= 2;
        end /= 2;
 
        for (int i = 1; i < tree.Length; i++)
        {
            for (int j = start; j < end; j++)
                tree[i][j] = Activator.CreateInstance(typeof(T), (tree[i - 1][j * 2] as HASHBASE).hash.Combine((tree[i - 1][j * 2 + 1] as HASHBASE).hash)) as T;
            start /= 2;
            end /= 2;
        }
    }
 
    public MerkleProof<T> GetProof(T target)
    {
        int? index = null;
        for (int i = 0; i < tree[0].Length; i++)
            if (tree[0][i].Equals(target))
            {
                index = i;
                break;
            }
 
        if (index == null)
            throw new InvalidOperationException("merkle_tree_target");
 
        int index2 = index.Value;
        T[] proof = new T[tree.Length];
        for (int i = 0; i < proof.Length - 1; i++, index /= 2)
            proof[i] = index % 2 == 0 ? tree[i][index.Value + 1] : tree[i][index.Value - 1];
        proof[proof.Length - 1] = tree[proof.Length - 1][0];
 
        return new MerkleProof<T>(index2, proof);
    }
 
    public static bool Verify(T target, MerkleProof<T> proof)
    {
        T cal = Activator.CreateInstance(typeof(T)) as T;
        cal.FromHash(target.hash);
        int index = proof.index;
        for (int i = 0; i < proof.proof.Length - 1; i++, index /= 2)
            cal = Activator.CreateInstance(typeof(T), index % 2 == 0 ? cal.hash.Combine(proof.proof[i].hash) : proof.proof[i].hash.Combine(cal.hash)) as T;
        return cal.Equals(proof.proof[proof.proof.Length - 1]);
    }
}
 
public class MerkleProof<T> : SHAREDDATA where T : HASHBASE
{
    public MerkleProof() { }
 
    public MerkleProof(int _index, T[] _proof) { index = _index; proof = _proof; }
 
    public int index { getprivate set; }
    public T[] proof { getprivate set; }
 
    protected override Func<ReaderWriterIEnumerable<MainDataInfomation>> StreamInfo
    {
        get
        {
            return (msrw) => new MainDataInfomation[]{
                new MainDataInfomation(typeof(int), () => index, (o) => index = (int)o),
                new MainDataInfomation(typeof(T[]), nullnull, () => proof, (o) => proof = (T[])o),
            };
        }
    }
}