区块链算法清单(Blockchain algorithm checklist)

最近学习区块链的知识，学习过程中，了解了区块链中常用的几种算法。有一大胆的想法，把这些算法整理成为一个清单，并找出算法论文，目前市场应用，以及实现代码。如果还有其他的算法或者代币，也欢迎大家推荐加入此清单。

SHA-256

• 介绍：SHA代表安全散列算法（Secure Hash Algorithm），SHA-256是由美国国家安全局(NSA)设计的SHA-2加密散列函数的成员(SHA-2的其他成员有SHA-224、SHA-384、SHA-512)。加密散列函数是对数字数据运行的数学运算，通过将所计算的“散列”与已知的散列值进行比较，人们可以确定数据的完整性。 单向散列可以从任意数据生成，但不能从散列生成数据。在比特币等多个区块链应用中的多个环节被使用。

• 论文：Courtois, Nicolas T., Marek Grajek, and Rahul Naik. "Optimizing sha256 in bitcoin mining." International Conference on Cryptography and Security Systems. Springer, Berlin, Heidelberg, 2014.

• 应用：Bitcoin(BTC)、BitcoinCash(BCH)、Peercoin(PPC)、Zetacoin(ZET)、Universal(UNIT)、Deutsche eMark(DEM)、AUR-SHA(AUR)、DGB-SHA(DGB)

• 算法实现：SHA-256算法要求输入报文的最大长度不能超过2^64bit，输入按512bit分组进行处理，产生的输出是一个256bit的报文摘要。

  SHA256.h

  #ifndef _SHA_256_H
  #define _SHA_256_H
  #include
  using namespace std;
  typedef unsigned int UInt32;
  //六个逻辑函数
  #define Conditional(x,y,z) ((x&y)^((~x)&z))
  #define Majority(x,y,z) ((x&y)^(x&z)^(y&z))
  #define LSigma_0(x) (ROTL(x,30)^ROTL(x,19)^ROTL(x,10))
  #define LSigma_1(x) (ROTL(x,26)^ROTL(x,21)^ROTL(x,7))
  #define SSigma_0(x) (ROTL(x,25)^ROTL(x,14)^SHR(x,3))
  #define SSigma_1(x) (ROTL(x,15)^ROTL(x,13)^SHR(x,10))
  //信息摘要结构
  struct Message_Digest{
      UInt32 H[8];
  };
  //SHA256类
  class SHA256
  {
  public:
      SHA256(){INIT();};
      ~SHA256(){};
      Message_Digest DEAL(UInt32 W[16]);//处理512比特数据，返回信息摘要
  private:
      void INIT();                //初始杂凑值
      UInt32 ROTR(UInt32 W,int n);//右旋转
      UInt32 ROTL(UInt32 W,int n);//左旋转
      UInt32 SHR(UInt32 W,int n); //右移位
  private:
      //信息摘要
      Message_Digest MD;
  };
  
  #endif
  
  

  SHA256.cpp

  #include"SHA-256.h"
  //64个32比特字的常数（前64个素数的立方根小数前32位）
  const UInt32 K[64] = {
          0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
          0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
          0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
          0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
          0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
          0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
          0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
          0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2,
  };
  //初始化杂凑值（前8个素数的平方根小数前32位）
  void SHA256::INIT(){
      MD.H[0] = 0x6a09e667;
      MD.H[1] = 0xbb67ae85;
      MD.H[2] = 0x3c6ef372;
      MD.H[3] = 0xa54ff53a;
          MD.H[4] = 0x510e527f;
      MD.H[5] = 0x9b05688c;
      MD.H[6] = 0x1f83d9ab;
      MD.H[7] = 0x5be0cd19;
  }
  //处理512比特数据，返回信息摘要
  Message_Digest SHA256::DEAL(UInt32 M[16]){
      int i;
      UInt32 T1=0,T2=0;
      UInt32 W[64]={0};
      UInt32 A=0,B=0,C=0,D=0,E=0,F=0,G=0,H=0;
      for(i=0;i<16;i++){
          W[i] = M[i];
      }
      for(i=16;i<64;i++){
          W[i] = SSigma_1(W[i-2])+W[i-7]+SSigma_0(W[i-15])+W[i-16];
      }
      A = MD.H[0];
      B = MD.H[1];
      C = MD.H[2];
      D = MD.H[3];
      E = MD.H[4];
      F = MD.H[5];
      G = MD.H[6];
      H = MD.H[7];
      cout<<"初始:";
      cout<<hex<<A<<" "<<B<<" "<<C<<" "<<D<<" "<<E<<" "<<F<<" "<<G<<" "<<H<<endl;
      for(i=0;i<64;i++){
          T1 = H + LSigma_1(E) + Conditional(E, F, G) + K[i] + W[i];
          T2 = LSigma_0(A) + Majority(A, B, C);
          H = G;
          G = F;
          F = E;
          E = D + T1;
          D = C;
          C = B;
          B = A;
          A = T1 + T2;
          cout<<dec<<i<<":";
          cout<<hex<<A<<" "<<B<<" "<<C<<" "<<D<<" "<<E<<" "<<F<<" "<<G<<" "<<H<<endl;
      }
      MD.H[0]=(MD.H[0]+A) & 0xFFFFFFFF;
      MD.H[1]=(MD.H[1]+B) & 0xFFFFFFFF;
      MD.H[2]=(MD.H[2]+C) & 0xFFFFFFFF;
      MD.H[3]=(MD.H[3]+D) & 0xFFFFFFFF;
      MD.H[4]=(MD.H[4]+E) & 0xFFFFFFFF;
      MD.H[5]=(MD.H[5]+F) & 0xFFFFFFFF;
      MD.H[6]=(MD.H[6]+G) & 0xFFFFFFFF;
      MD.H[7]=(MD.H[7]+H) & 0xFFFFFFFF;
  
      return MD;
  }
  //右旋转
  UInt32 SHA256::ROTR(UInt32 W,int n){
      return ((W >> n) & 0xFFFFFFFF) | (W) << (32-(n));
  }
  //左旋转
  UInt32 SHA256::ROTL(UInt32 W,int n){
      return ((W << n) & 0xFFFFFFFF) | (W) >> (32-(n));
  }
  //右移位
  UInt32 SHA256::SHR(UInt32 W,int n){
      return ((W >> n) & 0xFFFFFFFF);
  }
  

  test.cpp

  #include
  #include"SHA-256.h"
  using namespace std;
  
  typedef unsigned int UInt32;
  typedef unsigned __int64 UInt64;
  typedef unsigned char UChar;
  #define Max 1000//最大字符数
  SHA256 sha256=SHA256();
  Message_Digest M_D;
  UInt32 W[Max/4];//整型
  UInt32 M[16];   //存分组信息
  //压缩+显示
  void compress(){
      int i;
      M_D = sha256.DEAL(M);
      cout<<"哈希值： ";
      for(i=0;i<8;i++){
          cout<<hex<<M_D.H[i]<<" ";
      }
      cout<<endl;
  }
  //添加填充位+添加长度
  void PAD(UChar Y[Max]){
      //x+1+d+l=|x|
      UInt32 i,j;
      UInt32 T1=0,T2=0,T3=0,T4=0;
      UChar temp[Max]={0};
      UInt64 x = strlen((char *)Y);//数据长度
      UInt32 d = abs(55-x) % 64;   //填充长度
      UInt32 n = (x+8)/64+1; //分组数
      UInt32 m = x%64;       //最后组数据长度
      UInt32 l = 8;      
      cout<<"数据长度x:"<<int(x)<<" ";
      cout<<"填充长度d:"<<d<<" ";
      cout<<"分组数量n:"<<n<<" ";
      cout<<"最后长度m:"<<m<<endl;
      //不填充
      for(i=0;i<x;i++){
          temp[i] = Y[i];
      }
      //填充1次1000 0000
          temp[x] = 0x80;
      //填充d次0000 0000
      for(i=x+1;i<x+d+1;i++){
          temp[i] = 0x00;
      }
      //填充长度的63-0位
      for(i=1;i<=l;i++){
          temp[(n*64)-i] = (UChar)(8*x>>(i-1)*8);
      }
      //无符号字符转换为无符号整型
      for(i=0;i<Max/4;i++){
          for(j=0;j<4;j++){
              if(j==0)
                  T1 = temp[4*i+j];
              if(j==1)
                  T2 = temp[4*i+j];
              if(j==2)
                  T3 = temp[4*i+j];
              if(j==3)
                  T4 = temp[4*i+j];
          }
          W[i] = (T1<<24) + (T2<<16) + (T3<<8) +T4;
      }
      //显示16进制数据
      cout<<"16进制数据：";
      for(i=0;i<n*16;i++){
          cout<<hex<<" "<<W[i];
      }
      cout<<endl;
      //分组处理
      for(i=0;i<n;i++){
          cout<<"分组处理:"<<i+1<<endl;
          for(j=0;j<16;j++){
              M[j] = W[(i*16)+j];
          }
          compress();//sha-256压缩
      }
  }
  //主函数
  int main(){
      UChar Y[Max];
      cout<<"请输入要加密的字符串（最大"<<Max<<"个）："<<endl;
      cin>>Y;
      PAD(Y);
  
      system("pause");
      return 0;
  }
  

Scrypt

• 介绍：Scrypt是一个内存依赖型的hash算法。该算法是由著名的FreeBSD黑客Colin Percival为他的备份服务Tarsnap开发的。内存依赖顾名思义会占用很多内存空间，从而减少cpu负荷。由于其内存依赖的设计特别符合当时对抗专业矿机的设计，成为数字货币算法发展的一个主要应用方向。

• 论文：Percival, Colin. "Stronger key derivation via sequential memory-hard functions." Self-published (2009): 1-16.

• 应用：Litecoin(LTC)、Dogecoin(DOGE)、DNotes(NOTE)、Florin(FLO)、Gulden(NLG)、DGB-Scrypt(DGB)、GameCredits(GAME)、Verge-Scrypt(XVG)、Einsteinium(EMC2)、AUR-Scrypt(AUR)

• 算法实现：

  public class ScryptDemo 
  {
      public static void main(String[] args) {
          String originalPassword = "passw0rd";
          String generatedSecuredPasswordHash = SCryptUtil.scrypt(originalPassword, 16, 16, 16);
          System.out.println(generatedSecuredPasswordHash);
           
          boolean matched = SCryptUtil.check("password", generatedSecuredPasswordHash);
          System.out.println(matched);
           
          matched = SCryptUtil.check("passwordno", generatedSecuredPasswordHash);
          System.out.println(matched);
      }
  }
  
  // Copyright (C) 2011 - Will Glozer.  All rights reserved.
  
  package com.lambdaworks.crypto;
  
  import java.io.UnsupportedEncodingException;
  import java.security.GeneralSecurityException;
  import java.security.SecureRandom;
  
  import static com.lambdaworks.codec.Base64.*;
  
  /**
   * Simple {@link SCrypt} interface for hashing passwords using the
   * scrypt key derivation function
   * and comparing a plain text password to a hashed one. The hashed output is an
   * extended implementation of the Modular Crypt Format that also includes the scrypt
   * algorithm parameters.
   *
   * Format: $s0$PARAMS$SALT$KEY.
   *
   * 
   * PARAMS32-bit hex integer containing log2(N) (16 bits), r (8 bits), and p (8 bits)
   * SALTbase64-encoded salt
   * KEYbase64-encoded derived key
   * 
   *
   * s0 identifies version 0 of the scrypt format, using a 128-bit salt and 256-bit derived key.
   *
   * @author  Will Glozer
   */
  public class SCryptUtil {
      /**
       * Hash the supplied plaintext password and generate output in the format described
       * in {@link SCryptUtil}.
       *
       * @param passwd    Password.
       * @param N         CPU cost parameter.
       * @param r         Memory cost parameter.
       * @param p         Parallelization parameter.
       *
       * @return The hashed password.
       */
      public static String scrypt(String passwd, int N, int r, int p) {
          try {
              byte[] salt = new byte[16];
              SecureRandom.getInstance("SHA1PRNG").nextBytes(salt);
  
              byte[] derived = SCrypt.scrypt(passwd.getBytes("UTF-8"), salt, N, r, p, 32);
  
              String params = Long.toString(log2(N) << 16L | r << 8 | p, 16);
  
              StringBuilder sb = new StringBuilder((salt.length + derived.length) * 2);
              sb.append("$s0$").append(params).append('$');
              sb.append(encode(salt)).append('$');
              sb.append(encode(derived));
  
              return sb.toString();
          } catch (UnsupportedEncodingException e) {
              throw new IllegalStateException("JVM doesn't support UTF-8?");
          } catch (GeneralSecurityException e) {
              throw new IllegalStateException("JVM doesn't support SHA1PRNG or HMAC_SHA256?");
          }
      }
  
      /**
       * Compare the supplied plaintext password to a hashed password.
       *
       * @param   passwd  Plaintext password.
       * @param   hashed  scrypt hashed password.
       *
       * @return true if passwd matches hashed value.
       */
      public static boolean check(String passwd, String hashed) {
          try {
              String[] parts = hashed.split("\\$");
  
              if (parts.length != 5 || !parts[1].equals("s0")) {
                  throw new IllegalArgumentException("Invalid hashed value");
              }
  
              long params = Long.parseLong(parts[2], 16);
              byte[] salt = decode(parts[3].toCharArray());
              byte[] derived0 = decode(parts[4].toCharArray());
  
              int N = (int) Math.pow(2, params >> 16 & 0xffff);
              int r = (int) params >> 8 & 0xff;
              int p = (int) params      & 0xff;
  
              byte[] derived1 = SCrypt.scrypt(passwd.getBytes("UTF-8"), salt, N, r, p, 32);
  
              if (derived0.length != derived1.length) return false;
  
              int result = 0;
              for (int i = 0; i < derived0.length; i++) {
                  result |= derived0[i] ^ derived1[i];
              }
              return result == 0;
          } catch (UnsupportedEncodingException e) {
              throw new IllegalStateException("JVM doesn't support UTF-8?");
          } catch (GeneralSecurityException e) {
              throw new IllegalStateException("JVM doesn't support SHA1PRNG or HMAC_SHA256?");
          }
      }
  
      private static int log2(int n) {
          int log = 0;
          if ((n & 0xffff0000 ) != 0) { n >>>= 16; log = 16; }
          if (n >= 256) { n >>>= 8; log += 8; }
          if (n >= 16 ) { n >>>= 4; log += 4; }
          if (n >= 4  ) { n >>>= 2; log += 2; }
          return log + (n >>> 1);
      }
  }
  

参考&代码(Preference&Code)：

• wg/scrypt
• SHA-256算法实现
• Descriptions of SHA-256, SHA-384, and SHA-512