follow the Satoshi
follow-the-satoshi算法是李启威在2012年发明的，算法的原理非常简单：将所有的权益组成一棵Merkletree，其形式是非叶子节点的权重为左右子树的权重之和，叶子节点的权重即为某个权益所有者的权益值。然后根据随机数在左右子树中进行选择。
例如上图选择:
- 随机数是65，左边权益是50，那么65>50所以选择右边
- 执行伪随机得到20，左边权益37，20<37，选择左边
- 执行伪随机得到15，左边权益27，15<27，选择左边，所以最终选择出A4作为这一轮的stakeholder。
构建
通过质押或其他方式产生一组满足一定条件(达到一定质押比例)的Stakeholder作为叶子节点，其质押量作为其权重，用于构建一个Merkle树。，将Stakeholder作为叶子节点，其质押量作为其权重，用于构建一个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;
}
随机选择
从该Merkletree的根节点开始，以一个随机种子，使用伪随机数生成器生成一个小于当前树节点权重的随机数，如果该随机数小于左子树的权重则选择左子树继续遍历，否则选择右子树继续遍历，直到选择某一个叶子节点，也即选择了该叶子节点所代表的权益所有者作为下一个出块的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));
}
}
}
验证
由于使用的是伪随机数生成器，因此当不同生成器使用同一个随机种子来生成随机数序列时，该随机数序列是相同的。因此验证的过程与选择的过程类似，从该Merkletree的根节点开始，以前面生成的随机数作为随机源生成随机数进行节点选择，然后比较选中的树节点的哈希值，相等则验证通过。
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只能产生一个块，若这个块有问题，或者应该产出这个块的“矿工”(也就是stakeholder的候选人)不在线，或者产出的块没有广播给大多数人，那么这个slot是当作废弃的，也就是会跳过这个slot的块。多个slot为一个 epoch，权益的计算是以每个epoch开始前的历史来计算，也就是说在这个epoch中所产生的权益变化不影响当前的这个epoch中的slot的出块者的选择和其他和历史相关的东西。当前epoch中所产生的这些历史只能在以后的epoch中生效。
参考:
