# grin 之 Cuckoo Cycle 算法挖矿分析

tpkeeper · · 726 次点击 · · 开始浏览

##### Cuckoo Cycle 算法
image.png

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

• 特点：即时验证，内存需求可扩展（可抵抗asic）
##### grin中挖矿过程

solution 环型长度 都是42

2. solution,find=cuckoo(hash1)
cuckoo 把hash1当作SIPHAS0H的种子，然后随机生成M个边，再找出一个环
3. 如果find，就返回一个solution，然后对该solution 计算hash并对比难度值是否符合要求
1. 如果符合难度值，则广播区块

#### code

• 启动solver，开始挖矿
``````pub unsafe extern "C" fn run_solver(
ctx: *mut SolverCtx,
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>

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

``````
``````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],
}

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() {
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.

0 回复

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、``单行代码``
• 支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传
##### Cuckoo Cycle 算法
image.png

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

• 特点：即时验证，内存需求可扩展（可抵抗asic）
##### grin中挖矿过程

solution 环型长度 都是42

2. solution,find=cuckoo(hash1)
cuckoo 把hash1当作SIPHAS0H的种子，然后随机生成M个边，再找出一个环
3. 如果find，就返回一个solution，然后对该solution 计算hash并对比难度值是否符合要求
1. 如果符合难度值，则广播区块

#### code

• 启动solver，开始挖矿
``````pub unsafe extern "C" fn run_solver(
ctx: *mut SolverCtx,
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>

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

``````
``````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],
}

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() {
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.