当前位置：首页 > news >正文

raft、pow、pos算法（一）

news 来源：原创 2024/9/20 15:32:16

前言
raft 分布式系统中实现共识的一致性算法,kafuka,etcd 等
POW 大饼、姨妈1.0等
POS 姨妈2.0等

1：raft算法
Raft将系统中的角色分为领导者（Leader）、跟从者（Follower）和候选人（Candidate）：
Leader：接受客户端请求，并向Follower同步请求日志，当日志同步到大多数节点上后告诉Follower提交日志。
Follower：接受并持久化Leader同步的日志，在Leader告之日志可以提交之后，提交日志。
Candidate：Leader选举过程中的临时角色。

论文的图片网上抄的
在这里插入图片描述
具体可以参考 https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md
注意点：
1> timeout 时间为 150-300ms
2>2N+1 ,N 为可失效的节点数目

上代码

#include <iostream>
#include <vector>
#include <map>
#include <random>
#include <chrono>enum RaftState { Follower, Candidate, Leader };
enum MessageType { AppendEntries, RequestVote };struct Message {int term;int from;int to;MessageType type;// other fields depending on the message type
};class RaftNode {
public:RaftNode(int id) : nodeId(id), state(Follower), currentTerm(0), votedFor(-1) {// initialize other fields}void BecomeCandidate() {state = Candidate;currentTerm++;// vote for itself and start election}void BecomeLeader() {state = Leader;// start sending heartbeats}void ElectionTimeout() {if (state == Follower) {BecomeCandidate();// send RequestVote RPCs to other nodes}}void ReceiveAppendEntries(const Message &msg) {// update state based on the message}void ReceiveRequestVote(const Message &msg) {// cast vote and respond}void SendMessages() {// send messages to other nodes}void Tick() {// update node statestd::uniform_int_distribution<int> dist(150, 300); // 150-300 millisecondsstd::this_thread::sleep_for(std::chrono::milliseconds(dist(rng)));ElectionTimeout();SendMessages();}private:int nodeId;RaftState state;int currentTerm;int votedFor;// other fieldsstd::mt19937 rng;
};int main() {std::vector<RaftNode> nodes;nodes.emplace_back(RaftNode(0));nodes.emplace_back(RaftNode(1));nodes.emplace_back(RaftNode(2));// start the nodesfor (auto& node : nodes) {std::thread t([&node] {while (true) {node.Tick();}});t.detach();}// run the system for a whilestd::this_thread::sleep_for(std::chrono::seconds(10));return 0;
}

2:PoW，Proof-of-Work，
PoW共识机制是一种通过解决数学难题来证明计算量的方法。在比特币网络中，矿工通过竞争解决一个由哈希算法生成的复杂数学问题来创建新的区块，并将其添加到区块链中。这个过程称为挖矿，解决问题的矿工将获得一定数量的比特币作为奖励。

挖矿算法原理
1>.选择交易：每个区块都包含了一系列的交易记录。矿工首先从未确认的交易池中选择一些交易来打包到待挖的新区块中。
2>构建区块头：区块头是一个包含了交易信息和一些其他数据的数据块，其最重要的部分是称为“默克尔根”的交易哈希值和前一个区块的哈希值。
3>计算难题：矿工需要对区块头进行哈希运算，将其作为输入，通过调整一个称为“随机数”或“Nonce”的值，不断尝试，直到得到一个满足特定条件的哈希值。
4>难度目标：比特币网络会动态调整难题的难度，以确保新区块的平均生成时间约为10分钟。矿工需要找到一个哈希值小于特定目标值的Nonce值，这个目标值由网络当前的难度决定。
5>验证和广播：一旦一个矿工找到了一个满足条件的哈希值，他会将这个新区块广播到整个网络中，其他节点将验证其有效性后将其添加到自己的区块链上。

上代码

package mainimport ("bytes""crypto/sha256""encoding/binary""fmt""time"
)// 定义一个简单的区块结构
type Block struct {Index     intTimestamp int64Bits      uint32PrevHash  []byteHash      []byteNonce     uint64
}// 计算区块的哈希值
func (b *Block) SetHash() {timestamp := []byte(fmt.Sprintf("%x", b.Timestamp))bits := make([]byte, 4)binary.BigEndian.PutUint32(bits, b.Bits)prevHash := b.PrevHashhashData := bytes.Join([][]byte{{b.Index},timestamp,bits,prevHash,{b.Nonce},}, []byte{})hash := sha256.Sum256(hashData)b.Hash = hash[:]
}// 尝试找到满足工作量证明条件的非ce值
func work(block *Block) {for {block.SetHash()if isValidHash(block.Hash, block.Bits) {fmt.Printf(" nonce:%d\n", block.Nonce)break}block.Nonce++}
}// 验证哈希值是否满足工作量证明条件 //这里是前面2个0，真实可能是前面N个0
func isValidHash(hash []byte, bits uint32) bool {target := getTarget(bits)for i := uint32(0); i < target; i++ {if hash[31] == 0 && hash[30] == 0 {return true}hash[31]++if hash[31] == 0 {hash[30]++}}return false
}// 根据难度位返回目标值
func getTarget(bits uint32) uint32 {// 这里的实现是示例，并非真实的比特币实现return (1 << (256 - bits))
}func main() {t := time.Now()genesisBlock := Block{Index:     0,Timestamp: t.Unix(),Bits:      24, // 假设的工作量证明难度PrevHash:  []byte{0x00, 0x00, 0x00, 0x00}, // 假设的前置区块哈希Nonce:     0,}fmt.Println("Mining genesis block...")work(&genesisBlock)fmt.Printf("Genesis Block Hash: %x\n", genesisBlock.Hash)
}

POW 难度值
go 参考 https://github.com/btcsuite/btcd
c++ 参考 https://github.com/bitcoin/bitcoin
在这里插入图片描述
3:POS
Proof-of-Stake，股权证明机制。直接的理解就是通过拥有的股权进行证明。在区块链世界，一般通过币龄来表示，即你拥有的权益更多，持有权益的时间更长，就具备更高的话语权，可以获得更高的收益。

上代码

package mainimport ("fmt""math/rand""time"
)type Node struct {Address stringBalance int
}type Block struct {Index     intTimestamp stringBits      intPrevHash  stringNonce     intHash      string
}var nodes []Node
var chain []Blockfunc NewNode(address string, balance int) Node {return Node{address, balance}
}func NewBlock(bits int, prevHash string) Block {newBlock := Block{Index:     len(chain) + 1,Timestamp: time.Now().String(),Bits:      bits,PrevHash:  prevHash,Nonce:     0,Hash:      "",}return newBlock
}func calculateHash(block Block) string {// 实现具体的哈希计算函数return "hash(" + string(block.Index) + block.Timestamp + string(block.Bits) + block.PrevHash + string(block.Nonce) + ")"
}func proofOfStake(bits int) bool {// 假设每个节点随机选择，并且选择成功的概率与其加密货币量的函数成正比target := (1 << uint(bits)) * uint64(rand.Intn(100))stake := uint64(nodes[rand.Intn(len(nodes))].Balance)return stake >= target
}func main() {// 初始化节点和链nodes = append(nodes, NewNode("node1", 100))nodes = append(nodes, NewNode("node2", 50))nodes = append(nodes, NewNode("node3", 150))// 创世块genesisBlock := NewBlock(10, "0")genesisBlock.Hash = calculateHash(genesisBlock)chain = append(chain, genesisBlock)// 模拟出块for i := 0; i < 10; i++ {if proofOfStake(genesisBlock.Bits) {newBlock := NewBlock(genesisBlock.Bits, genesisBlock.Hash)for !newBlock.HashValid() {newBlock.Nonce++}chain = append(chain, newBlock)genesisBlock = newBlock}}// 打印最终的区块链for _, block := range chain {fmt.Printf("Index: %d, Hash: %s\n", block.Index, block.Hash)}
}// Block 的一个辅助方法，检查nonce和bits是否生成了有效的hash
func (b *Block) HashValid() bool {return calculateHash(*b)[:b.Bits] == strings.Repeat("0", b.Bits)
}