grin 之 Cuckoo Cycle 算法挖矿分析

Cuckoo Cycle 算法

• 作者：John Tromp
• c++: github: https://github.com/tromp/cuckoo
• golang: https://github.com/AidosKuneen/cuckoo
• 解决的问题：给出N个节点（奇偶两行）和M个边，在M个边中寻找一个闭环（即找到一个路径使得一个节点是起点也是终点）如图中的0-5-4-1-0：

image.png

8个节点6个边 一个解决方案

• 特点：即时验证，内存需求可扩展（可抵抗asic）

grin中挖矿过程

两种算法：Cuck(ar|at)oo cycle (抗asic | 对asic友好) (edg_bits : 29|31+)
solution 环型长度 都是42

1. hash1=black2b(header+nonce) 其中参与计算的header未包含pow字段
2. solution,find=cuckoo(hash1)
   cuckoo 把hash1当作SIPHAS0H的种子，然后随机生成M个边，再找出一个环
3. 如果find，就返回一个solution，然后对该solution 计算hash并对比难度值是否符合要求
   1. 如果符合难度值，则广播区块
   2. 如果不符合难度值，重新组装header+nonce，继续步骤1
4. 如果没有find，重新组装header+nonce，继续步骤1

code

• 启动solver，开始挖矿

pub unsafe extern "C" fn run_solver(
    ctx: *mut SolverCtx,
    header_ptr: *const c_uchar,  //不包含pow部分
    header_length: uint32_t,
    nonce: uint64_t,  //随机数
    _range: uint32_t,
    solutions: *mut SolverSolutions, //输出解决方案
    stats: *mut SolverStats,
) -> uint32_t

• new cuckarooctx (19,42)

pub fn new_cuckaroo_ctx<T>(
    edge_bits: u8, // 2^bits 边的图形 2^19
    proof_size: usize, //环形长度 42
) -> Result<Box<dyn PoWContext<T>>, Error>

• 拼接 header+nonce

pub fn set_header_nonce(
    header: &[u8],
    nonce: Option<u64>,
    mutate_nonce: bool,
) -> Result<[u64; 4], Error>

• blake2b(header+nonce)

pub fn create_siphash_keys(header: &[u8]) -> Result<[u64; 4], Error>

• cuckoo图形搜索开始，返回解决方案

pub fn search(nodes: &[u32]) -> Result<Vec<Solution>, String>

• 验证cuckoo solution

pub struct CuckooParams<T>
{
    pub edge_bits: u8, //图形边数量 2^bits
    pub proof_size: usize, //环形边数量
    pub num_edges: u64,
    pub siphash_keys: [u64; 4],
    pub edge_mask: T,
}

fn verify(&self, proof: &Proof) -> Result<(), Error> {
        let nonces = &proof.nonces;
        let mut uvs = vec![0u64; 2 * proof.proof_size()];
        let mut xor0: u64 = 0;
        let mut xor1: u64 = 0;
        for n in 0..proof.proof_size() {
            if nonces[n] > to_u64!(self.params.edge_mask) {
                return Err(ErrorKind::Verification("edge too big".to_owned()))?;
            }
            if n > 0 && nonces[n] <= nonces[n - 1] {
                return Err(ErrorKind::Verification("edges not ascending".to_owned()))?;
            }
            let edge = to_edge!(siphash_block(&self.params.siphash_keys, nonces[n]));
            uvs[2 * n] = to_u64!(edge & self.params.edge_mask);
            uvs[2 * n + 1] = to_u64!((edge >> 32) & self.params.edge_mask);
            xor0 ^= uvs[2 * n];
            xor1 ^= uvs[2 * n + 1];
        }
...
...
...
}

参考：

The Mining Loop

All of these systems are put together in the mining loop, which attempts to create
valid Proofs-of-Work to create the latest block in the chain. The following is an outline of what the main mining loop does during a single iteration:

• Get the latest chain state and build a block on top of it, which includes
  • A Block Header with new values particular to this mining attempt, which are:
    • The latest target difficulty as selected by the evolving network difficulty algorithm
    • A set of transactions available for validation selected from the transaction pool
    • A coinbase transaction (which we're hoping to give to ourselves)
    • The current timestamp
    • A randomly generated nonce to add further randomness to the header's hash
    • The merkle root of the UTXO set and fees (not yet implemented)
      • Then, a sub-loop runs for a set amount of time, currently configured at 2 seconds, where the following happens:
        • The new block header is hashed to create a hash value
        • The cuckoo graph generator is initialized, which accepts as parameters:
          • The hash of the potential block header, which is to be used as the key to a SIPHASH function
            that will generate pairs of locations for each element in a set of nonces 0..N in the graph.
          • The size of the graph (a consensus value).
          • An easiness value, (a consensus value) representing the M/N ratio described above denoting the probability
            of a solution appearing in the graph
        • The Cuckoo Cycle detection algorithm tries to find a solution (i.e. a cycle of length 42) within the generated
          graph.
        • If a cycle is found, a Blake2b hash of the proof is created and is compared to the current target
          difficulty, as outlined in Additional Difficulty Control above.
        • If the Blake2b Hash difficulty is greater than or equal to the target difficulty, the block is sent to the
          transaction pool, propagated amongst peers for validation, and work begins on the next block.
        • If the Blake2b Hash difficulty is less than the target difficulty, the proof is thrown out and the timed loop continues.
        • If no solution is found, increment the nonce in the header by 1, and update the header's timestamp so the next iteration
          hashes a different value for seeding the next loop's graph generation step.
        • If the loop times out with no solution found, start over again from the top, collecting new transactions and creating
          a new block altogether.

Mining Loop Difficulty Control and Timing

Controlling the overall difficulty of the mining loop requires finding a balance between the three values outlined above:

• Graph size (currently represented as a bit-shift value n representing a size of 2^n nodes, consensus value
  DEFAULT_SIZESHIFT). Smaller graphs can be exhaustively searched more quickly, but will also have fewer
  solutions for a given easiness value. A very small graph needs a higher easiness value to have the same
  chance to have a solution as a larger graph with a lower easiness value.
• The 'Easiness' consensus value, or the M/N ratio of the graph expressed as a percentage. The higher this value, the more likely
  it is a generated graph will contain a solution. In tandem with the above, the larger the graph, the more solutions
  it will contain for a given easiness value. The Cuckoo Cycle implementations fix this M to N/2, giving
  a ratio of 50%
• The evolving network difficulty hash.