follow the Satoshi
follow-the-satoshi算法是李啟威在2012年發(fā)明的，算法的原理非常簡單：將所有的權(quán)益組成一棵Merkletree，其形式是非葉子節(jié)點的權(quán)重為左右子樹的權(quán)重之和，葉子節(jié)點的權(quán)重即為某個權(quán)益所有者的權(quán)益值。然后根據(jù)隨機(jī)數(shù)在左右子樹中進(jìn)行選擇。
例如上圖選擇:
- 隨機(jī)數(shù)是65，左邊權(quán)益是50度迂，那么65>50所以選擇右邊
- 執(zhí)行偽隨機(jī)得到20，左邊權(quán)益37猜揪，20<37惭墓，選擇左邊
- 執(zhí)行偽隨機(jī)得到15，左邊權(quán)益27而姐，15<27腊凶，選擇左邊，所以最終選擇出A4作為這一輪的stakeholder拴念。
構(gòu)建
通過質(zhì)押或其他方式產(chǎn)生一組滿足一定條件(達(dá)到一定質(zhì)押比例)的Stakeholder作為葉子節(jié)點钧萍，其質(zhì)押量作為其權(quán)重，用于構(gòu)建一個Merkle樹政鼠。风瘦，將Stakeholder作為葉子節(jié)點，其質(zhì)押量作為其權(quán)重公般，用于構(gòu)建一個Merkle樹万搔。
pub fn create_merkle_tree(stakeholders: Vec<Stakeholder>) -> Vec<Arc<Node>> {
let mut tree: Vec<Arc<Node>> = Vec::new();
tree.resize(stakeholders.len() * 2,Arc::new(Node::default()));
println!("Creating Merkle tree with:{} nodes",tree.len() - 1);
for i in 0..stakeholders.len() {
if let Some(v) = tree.get_mut(i+stakeholders.len()) {
*v = Arc::new(Node::new_node_from_SHolder(stakeholders.get(i).unwrap().clone()));
}
}
for i in (1..stakeholders.len()).rev() {
let mut left: Arc<Node>;
let mut right: Arc<Node>;
let mut h: Hash;
{
left = tree.get(i*2).unwrap().clone();
right = tree.get(i*2 + 1).unwrap().clone();
h = makeNodeHash(left.getMerkleHash().to_slice(),
right.getMerkleHash().to_slice(),
&left.getCoins().to_string().into_bytes(),
&right.getCoins().to_string().into_bytes());
}
if let Some(v) = tree.get_mut(i) {
*v = Arc::new(Node::new_node(Some(left), Some(right), h));
}
}
for i in (1..tree.len()) {
println!("HASH:{:?},Index:{}",tree.get(i).unwrap().getMerkleHash(),i);
}
return tree;
}
隨機(jī)選擇
從該Merkletree的根節(jié)點開始胡桨，以一個隨機(jī)種子，使用偽隨機(jī)數(shù)生成器生成一個小于當(dāng)前樹節(jié)點權(quán)重的隨機(jī)數(shù)瞬雹，如果該隨機(jī)數(shù)小于左子樹的權(quán)重則選擇左子樹繼續(xù)遍歷昧谊，否則選擇右子樹繼續(xù)遍歷，直到選擇某一個葉子節(jié)點酗捌，也即選擇了該葉子節(jié)點所代表的權(quán)益所有者作為下一個出塊的Leader呢诬。
pub fn random_from_fts_Tree(tree: Vec<Arc<Node>>,rnd: &mut StdRng) -> Box<ftsResult> {
let mut merkleProof: Vec<ProofEntry> = Vec::new();
let mut i: usize = 1;
loop {
if tree[i].isLeaf() {
let s = tree[i].getStakeholder();
return Box::new(ftsResult::new_fts_result(s.as_ref().unwrap(),merkleProof));
}
let x1 = tree.get(i).unwrap()
.getLeftNode()
.as_ref()
.unwrap()
.getCoins();
let x2 = tree.get(i).unwrap()
.getRightNode()
.as_ref()
.unwrap()
.getCoins();
println!("left subtree coins:{} right subtree coins:{}",x1,x2);
let r = nextInt(x1 + x2,rnd) + 1;
println!("Picking coin number:{}",r);
if r <= x1 {
println!("Choosing left subtree...");
i *= 2;
merkleProof.push(ProofEntry::new_proof_entry(
tree.get(i+1).unwrap().getMerkleHash(),
x1, x2));
} else {
println!("Choosing right subtree...");
i = 2*i + 1;
merkleProof.push(ProofEntry::new_proof_entry(
tree.get(i-1).unwrap().getMerkleHash(),
x1, x2));
}
}
}
驗證
由于使用的是偽隨機(jī)數(shù)生成器，因此當(dāng)不同生成器使用同一個隨機(jī)種子來生成隨機(jī)數(shù)序列時胖缤，該隨機(jī)數(shù)序列是相同的馅巷。因此驗證的過程與選擇的過程類似，從該Merkletree的根節(jié)點開始草姻，以前面生成的隨機(jī)數(shù)作為隨機(jī)源生成隨機(jī)數(shù)進(jìn)行節(jié)點選擇，然后比較選中的樹節(jié)點的哈希值稍刀，相等則驗證通過撩独。
pub fn verify_fts(merkleRootHash: Hash, res: Box<ftsResult>,rnd: &mut StdRng) -> bool {
let mut resPath: Vec<u8> = Vec::new();
for v in res.getMerkleProof().iter() {
let x1 = v.getLeftBound();
let x2 = v.getRightBound();
let r = nextInt(x1 + x2,rnd) + 1;
if r <= x1 {
println!("0");
resPath.push(0);
} else {
println!("1");
resPath.push(1);
}
}
println!("OK");
let ss = res.getStakeholder();
let mut hx = make_hash(&ss.as_ref().unwrap().toBytes());
for i in (0..res.getMerkleProof().len()).rev() {
let proof = res.getMerkleProof().get(i).unwrap();
let x1 = proof.getLeftBound().to_string().into_bytes();
let x2 = proof.getRightBound().to_string().into_bytes();
let hy = proof.getMerkleHash();
if resPath[i] == 0_u8 {
hx = makeNodeHash(hx.to_slice(),hy.to_slice(),&x1,&x2)
} else {
hx = makeNodeHash(hy.to_slice(),hx.to_slice(),&x1,&x2)
}
println!("Next hash:{}",hx);
}
if Ordering::Equal == merkleRootHash.to_vec().cmp(&hx.clone().to_vec()) {
println!("Root hash matches!");
return true
} else {
println!("Invalid Merkle proof");
return true
}
}
follow the Satoshi算法被用在Cardano的第一個版本中，時間被分為 slot账月，每個 slot 時長為20秒综膀。每個slot只能產(chǎn)生一個塊，若這個塊有問題局齿，或者應(yīng)該產(chǎn)出這個塊的“礦工”(也就是stakeholder的候選人)不在線剧劝，或者產(chǎn)出的塊沒有廣播給大多數(shù)人抓歼，那么這個slot是當(dāng)作廢棄的讥此，也就是會跳過這個slot的塊谣妻。多個slot為一個 epoch，權(quán)益的計算是以每個epoch開始前的歷史來計算，也就是說在這個epoch中所產(chǎn)生的權(quán)益變化不影響當(dāng)前的這個epoch中的slot的出塊者的選擇和其他和歷史相關(guān)的東西。當(dāng)前epoch中所產(chǎn)生的這些歷史只能在以后的epoch中生效辈灼。
參考:
