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 { get; private set; } public T[][] tree { get; private 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 { get; private set; } public T[] proof { get; private set; } protected override Func<ReaderWriter, IEnumerable<MainDataInfomation>> StreamInfo { get { return (msrw) => new MainDataInfomation[]{ new MainDataInfomation(typeof(int), () => index, (o) => index = (int)o), new MainDataInfomation(typeof(T[]), null, null, () => proof, (o) => proof = (T[])o), }; } } }