Skip to content
This repository has been archived by the owner on Sep 24, 2019. It is now read-only.

Latest commit

 

History

History
302 lines (254 loc) · 15.5 KB

CryptoNight_CN.md

File metadata and controls

302 lines (254 loc) · 15.5 KB

CryptoNight 文档

概要

CryptoNote Standards 介绍了一种点对点的匿名支付系统,本文档是 CryptoNote Standards 的一部分,定义了 CryptoNote 的缺省工作量证明散列函数,CryptoNight。

版权及授权说明

版权所有(c)2013 CryptoNote。 本文档可在知识共享署名3.0许可证(国际)许可权限范围内查询。

许可副本 :http://creativecommons.org/licenses/by/3.0/

目录

  1. 算法介绍
  2. 名词解释
  3. 初始化流程
  4. 内存处理流程
  5. 结果计算流程
  6. 参考内容

1.算法介绍

CryptoNight是一个使用物理内存的高强度hash算法函数。 它的设计适用于GPU,FPGA和ASIC架构上的有效性算力。流程的第一步是初始化大型暂存器与伪随机数据;下一步是算法对暂存器中包含伪随机地址的大量的读/写计算操作;最后一步是将整个暂存器的hash值进行hash效验,验证本次计算产生的价值。

2. 算法定义

hash函数:映射数据的有效计算函数,对于固定大小的数据、构造特定算法行为,产生类似随机数结果

暂存器:在算法过程中,申请用于存储计算时中间值的部分内存

3. 初始化流程

首先,使用参数 b = 1600c = 512 .对输入内容进行Keccak计算 [ KECCAK ]。计算结果的0..31字节用作AES-256密钥[AES],并扩展为10个循环密钥;申请一个分配了2097152字节(2 MB)空间的暂存器;从计算结果的64..191字节处,提取出来数据并分割成8个块,每个块16字节。使用以下步骤对每个块进行加密:

for i = 0..9 do:
block = aes_round(block, round_keys[i])

aes_round() 函数执行一轮AES加密,对本块执行 SubBytesShiftRowsMixColumns 步骤,其结果与round_key进行异或运算。但这不同于AES加密算法,第一轮计算和最后一轮计算没什么不同。

一轮下来得到的计算结果,写入暂存器的前128个字节,然后这些结果再次代入加密循环,再把这次循环结果写入暂存器的第二个128字节里。这里每次往暂存器里写入下一个128字节,都代表对先前写入的128字节内容在新一轮加密的结果。流程一直循环,直到暂存器写满。至此,一次算法的初始化就完成了。

该图表示暂存器初始化:

                               +-----+
                               |Input|
                               +-----+
                                  |
                                  V
                             +--------+
                             | Keccak |
                             +--------+
                                  |
                                  V
   +-------------------------------------------------------------+
   |                         Final state                         |
   +-------------+--------------+---------------+----------------+
   | Bytes 0..31 | Bytes 32..63 | Bytes 64..191 | Bytes 192..199 |
   +-------------+--------------+---------------+----------------+
          |                             |
          V                             |
   +-------------+                      V
   | Round key 0 |------------+---+->+-----+
   +-------------+            |   |  |     |
   |      .      |            |   |  |     |
   |      .      |            |   |  | AES |
   |      .      |            |   |  |     |
   +-------------+            |   |  |     |
   | Round key 9 |----------+-|-+-|->+-----+                 +---+
   +-------------+          | | | |     |                    |   |
                            | | | |     +------------------->|   |
                            | | | |     |                    |   |
                            | | | |     V                    |   |
                            | | | +->+-----+                 |   |
                            | | |    |     |                 | S |
                            | | |    |     |                 |   |
                            | | |    | AES |                 | c |
                            | | |    |     |                 |   |
                            | | |    |     |                 | r |
                            | | +--->+-----+                 |   |
                            | |         |                    | a |
                            | |         +------------------->|   |
                            | |         .                    | t |
                            | |         .                    |   |
                            | |         .                    | c |
                            | |         +------------------->|   |
                            | |         |                    | h |
                            | |         V                    |   |
                            | +----->+-----+                 | p |
                            |        |     |                 |   |
                            |        |     |                 | a |
                            |        | AES |                 |   |
                            |        |     |                 | d |
                            |        |     |                 |   |
                            +------->+-----+                 |   |
                                        |                    |   |
                                        +------------------->|   |
                                                             |   |
                                                             +---+

4. 内存处理流程

在主循环之前,对输入内容进行Keccak计算后取0..31字节和32..63字节进行异或,所得到的32字节结果用于初始化,变量a和b分别各占16字节,这两个变量将用于主循环,主循环进行524,288次迭代,当一个16字节值需要转换成暂存器中的一个地址,将以低字节顺序压入内存,21位低字节用作索引,但是索引中的4个低字节将被清除,以确保地址索引统一16字节对齐。 数据从16字节块中读取并写入暂存器。

迭代流程伪代码:

scratchpad_address = to_scratchpad_address(a)
scratchpad[scratchpad_address] = aes_round(scratchpad [scratchpad_address], a)
b, scratchpad[scratchpad_address] = scratchpad[scratchpad_address],
   b xor scratchpad[scratchpad_address]
scratchpad_address = to_scratchpad_address(b)
a = 8byte_add(a, 8byte_mul(b, scratchpad[scratchpad_address]))
a, scratchpad[scratchpad_address] = a xor 
   scratchpad[scratchpad_address], a

8byte_add() 函数将每个参数表示为一对64位低位值,并将它们组合在一起,以分量形式进行快速模除 2 ^ 64。 其结果返回16字节。

8byte_mul() 函数仅使用每个参数的前8个字节,并分别解析为无符号64位低位字节整数,并相乘。 其结果返回16字节,最后,结果分半,两边的8字节相互交换。

内存处理流程图:

   +-------------------------------------------------------------+
   |                         Final state                         |
   +-------------+--------------+---------------+----------------+
   | Bytes 0..31 | Bytes 32..63 | Bytes 64..191 | Bytes 192..199 |
   +-------------+--------------+---------------+----------------+
          |             |
          |   +-----+   |
          +-->| XOR |<--+
              +-----+
               |   |
          +----+   +----+
          |             |
          V             V
        +---+         +---+
        | a |         | b |
        +---+         +---+
          |             |
   --------------------- REPEAT 524288 TIMES ---------------------
          |             |                            address +---+
          +-------------|----------------------------------->|   |
          |   +-----+   |                               read |   |
          +-->| AES |<--|------------------------------------|   |
          |   +-----+   V                                    |   |
          |      |   +-----+                                 | S |
          |      +-->| XOR |                                 |   |
          |      |   +-----+                           write | c |
          |      |      |    +------------------------------>|   |
          |      |      +----+                       address | r |
          |      +------------------------------------------>|   |
          |      |  +-----------+                       read | a |
          |      +->| 8byte_mul |<--+------------------------|   |
          |      |  +-----------+   |                        | t |
          |      |        |         |                        |   |
          |      |        V         |                        | c |
          |      |  +-----------+   |                        |   |
          +------|->| 8byte_add |   |                        | h |
                 |  +-----------+   |                        |   |
                 |        |         |                  write | p |
                 |        +---------|----------------------->|   |
                 |        |         |                        | a |
                 |        V         |                        |   |
                 |     +-----+      |                        | d |
                 |     | XOR |<-----+                        |   |
                 |     +-----+                               |   |
                 +------+ |                                  |   |
          +-------------|-+                                  |   |
          |             |                                    +---+
   -------------------------- END REPEAT -------------------------
          |             |

5. 结果计算流程

在内存操作完成之后,使用与第一步骤(初始化步骤)分相同的方式,进行Keccak计算,最终结果的32..63字节被扩展成10个AES循环密钥。

从Keccak结果里提取64..191字节,并与暂存器里前128个字节进行异或运算。然后结果以与第一步(初始化步骤)使用相同的方式进行加密,但是使用新的密钥。结果继续与暂存器中的第二个128个字节进行异或运算,依次循环加密迭代。

在暂存器的最后128个字节进行异或运算后,就是流程的最后一次加密,完成后将原本Keccak结果的64..191字节内容,替换为本次加密内容。然后,以b = 1600对整个块内容进行Keccak-f(Keccak排列)。

然后,结果中第一个字节的2个低位比特,用于进行散列函数运算:0 = BLAKE-256 [BLAKE],1 = Groestl-256 [GROESTL],2 = JH-256 [JH] 3 = Skein-256 [SKEIN]。最后将所选的散列函数应用于Keccak最终结果,生成的散列就是CryptoNight算法的计算输出。

结果计算流程图:

   +-------------------------------------------------------------+
   |                         Final state                         |
   +-------------+--------------+---------------+----------------+
   | Bytes 0..31 | Bytes 32..63 | Bytes 64..191 | Bytes 192..199 |
   +-------------+--------------+---------------+----------------+
         |                |             |                |
         |       +--------+             |                |
         |       V        |             |                |
         |+-------------+ |             |                |
         || Round key 0 |-|---+---+     |                |
         |+-------------+ |   |   |     |                |
         ||      .      | |   |   |     |                |
         ||      .      | |   |   |     |                |
         ||      .      | |   |   |     |                |
         |+-------------+ |   |   |     |                |
   +---+ || Round key 9 |-|-+-|-+ |     V                |
   |   | |+-------------+ | | | | |  +-----+             |
   |   |-|----------------|-|-|-|-|->| XOR |             |
   |   | |                | | | | |  +-----+             |
   | S | |                | | | | |     |                |
   |   | |                | | | | |     V                |
   | c | |                | | | | +->+-----+             |
   |   | |                | | | |    |     |             |
   | r | |                | | | |    |     |             |
   |   | |                | | | |    | AES |             |
   | a | |                | | | |    |     |             |
   |   | |                | | | |    |     |             |
   | t | |                | | | +--->+-----+             |
   |   | |                | | |         |                |
   | c | |                | | |         V                |
   |   | |                | | |      +-----+             |
   | h |-|----------------|-|-|----->| XOR |             |
   |   | |                | | |      +-----+             |
   | p | |                | | |         |                |
   |   | |                | | |         .                |
   | a | |                | | |         .                |
   |   | |                | | |         .                |
   | d | |                | | |         |                |
   |   | |                | | |         V                |
   |   | |                | | |      +-----+             |
   |   |-|----------------|-|-|----->| XOR |             |
   |   | |                | | |      +-----+             |
   +---+ |                | | |         |                |
         |                | | |         V                |
         |                | | +----->+-----+             |
         |                | |        |     |             |
         |                | |        |     |             |
         |                | |        | AES |             |
         |                | |        |     |             |
         |                | |        |     |             |
         |                | +------->+-----+             |
         |                |             |                |
         V                V             V                V
   +-------------+--------------+---------------+----------------+
   | Bytes 0..31 | Bytes 32..63 | Bytes 64..191 | Bytes 192..199 |
   +-------------+--------------+---------------+----------------+
   |                       Modified state                        |
   +-------------------------------------------------------------+
                                  |
                                  V
                            +----------+
                            | Keccak-f |
                            +----------+
                             |    |
                 +-----------+    |
                 |                |
                 V                V
          +-------------+  +-------------+
          | Select hash |->| Chosen hash |
          +-------------+  +-------------+
                                  |
                                  V
                          +--------------+
                          | Final result |
                          +--------------+

举例:

    Empty string:
      eb14e8a833fac6fe9a43b57b336789c46ffe93f2868452240720607b14387e11.

    "This is a test":
      a084f01d1437a09c6985401b60d43554ae105802c5f5d8a9b3253649c0be6605.

6. 参考内容

[AES] "Announcing the ADVANCED ENCRYPTION STANDARD", FIPS 197, 2001.

[BLAKE] Aumasson, J.-P., Henzen, L., Meier, W., and R. C.-W. Phan, "SHA-3 proposal BLAKE", 2010.

[GROESTL] Gauravaram, P., Knudsen, L., Matusiewicz, K., Mendel, F.,

Rechberger, C., Schlaffer, M., and S. Thomsen, "Groestl - a SHA-3 candidate", 2011.

[JH] Wu, H., "The Hash Function JH", 2011.

[KECCAK] Bertoni, G., Daemen, J., Peeters, M., and G. Van Assche, "The Keccak reference", 2011.

[SKEIN] Ferguson, N., Lucks, S., Schneier, B., Whiting, D., Bellare, M., Kohno, T., Callas, J., and J. Walker, "The Skein Hash Function Family", 2008.