grin 之 Cuckoo Cycle 算法挖矿分析

tpkeeper · · 726 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

Cuckoo Cycle 算法

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

  • 特点:即时验证,内存需求可扩展(可抵抗asic)

两种算法: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


  • 启动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
          • 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.




查看原文:grin 之 Cuckoo Cycle 算法挖矿分析

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

726 次点击  
加入收藏 微博
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传