第一天下 林添毅 美图基于以太坊框架下的+DPoS+算法的实现和思考 v1,1

blockchain

2018/10/12 发布于 技术 分类

文字内容
1. 美图基于以太坊 DPoS 算法实现 林添毅 技术经理
3. •  简介 •  以太坊基础 •  DPoS 实现
4. 工作经历
5. 我们做了什么 ✓ 基于以太坊实现了了 DPoS 算法并开源到Github ✓ 为美图 ⻉贝客钱包 提供基础服务, ⽬目前⽀支持 ERC20, BTC, EOS ✓ ⾃自研公链 正在落地阶段 代码地址: Github (h*ps://github.com/meitu/go-ethereum)
6. 为什么做改造 ✓ 通过深⼊入源码为美图钱包提供更更好的基础服务 ✓ 技术储备,为公司后续在区块链领域布局做好铺垫 ✓ 开源代码,回馈社区
7. •  简介 •  以太坊基础 •  DPoS 实现
8. 整体流程
9. 发送交易 eth.SendTransaction({ from: 0x1234, to: 0x5678, nonce: 1, gas: 100000, gasPrice: 10000000000, value: 100000000000000 }) from 转账发起⽅方 to 收款⼈人 nonce 单调递增计数器器, 防⽌止⼀一笔交易易被反复执⾏行行 gas 允许这笔交易易使⽤用的最⼤大 gas 值 gasPrice gas 的单价 value 转账的数⽬目
10. 交易
11. 共识算法 ✓ PoW(Proof of Work) hash(B) ⩽ M/D (1), 其中 D ∈ [1, M], hash = sha256 ✓ PoS(Proof of Stake) hash(hash(Bprev), A, t) ⩽ balance(A) * M/D 其中 hash = sha256 ✓ DPoS(Delegated Proof of Stake) topN(sort(candidate’s votes))
12. 区块 以太坊的区块由三个部分组成: ✓ 块头,包含了了 PoW 算法的随机数, 难度以及⼏几个⽤用来存储交易易树和余额树的根 ✓ 引⽤用的叔块,以太坊缩短了了出块时间, 为了了安全性引⼊入奖励叔块的机制 ✓ 交易易,记录当前块所打包的交易易,其他节点通过回放交易易来更更新余额
13. 块头 核⼼心⼏几个成员: ✓ nonce PoW 算法的随机数 ✓ stateRoot 全局,存储余额以及合约账户 ✓ transacYonRoot 每个块独有,存放交易易 ✓ ReceiptRoot 每个块独有,存放交易易收据 (图片来自: h*ps://medium.com/@preethikasireddy/how-does-ethereum-work-anyway-22d1df506369 )
14. Merkle Trie ✓ ⾃自下⽽而上构造树的节点 ✓ 修改任意节点会影响到节点对应所有⽗父节点
15. MPT(Merkle Patrica Trie) ✓ 具备 Merkle 树⼀一样的防篡改属性 ✓ 路路径具备索引功能
16. MPT(Merkle Patrica Trie)
17. UTXOs
18. 账号模型对比 UTXOs 的优点: ✓ 具备更更⾼高的隐私性 ✓ 并⾏行行性更更好 ✓ 防 “双花” Accounts 的优点: ✓ 节省空间 ✓ 简单且兼容性好 ✓ 对于智能合约更更友好
19. •  简介 •  以太坊基础 •  DPoS 实现
20. 为什么选择 DPoS ✓ DPoS 不不需要算⼒力力成本、简单且性能好, 更更加适合 DAPP 落地 ✓ 以太坊正在往 PoW + PoS ⽅方向演进 ✓ 为社区提供⼀一种新的选择
21. 整体流程
22. 角色转换
23. 投票 eth.SendTransaction({ type: Vote, from: 0x123456778, to: 0x123566884, nonce: 1, gas: 100000, gasPrice: 10000000000, value: 0 }) ✓ 增加⼀一个 type 字段来区分交易易类型 ✓ 除转账交易易之外其他 value 必须为 0
24. 存储 为了了快速的选举,需要在块头存储下⾯面⼏几个全局状态树的 root ✓ EpochTrie – 记录每个周期的验证⼈人列列表 ✓ VoteTrie – 记录投票⼈人对应投给的候选⼈人 ✓ CandidateTrie – 记录所有的候选⼈人 ✓ DelegateTrie – 记录候选⼈人对应所有投票⼈人列列表 ✓ MintCntTrie – 记录每个周期候选⼈人对应的出块数⽬目
25. 选举
26. 选举 prevEpoch := parent.Time.Int64() / epochInterval currentEpoch := ec.TimeStamp / epochInterval for i := prevEpoch; i < currentEpoch; i++ { votes, err := ec.countVotes() if err != nil { return err } } sort.Sort(candidates) seed := int64(parent.Hash().Bytes()) + i r := rand.New(rand.NewSource(seed)) for i := len(candidates) - 1; i > 0; i-- { j := int(r.Int31n(int32(i + 1))) candidates[i], candidates[j] = candidates[j], candidates[i] } } ✓ 根据时间确定是到达选举块 ✓ 使⽤用⽗父块的哈希值打散候选⼈人 ✓ 统计候选⼈人的票数并选出 top N
27. 调度 公式: current= block number % epoch interval % validators ⽐比如 13 % 10 % 5 = 3, 那么就是轮到图中的 validator-2 出块
28. 调度 func (ec *EpochContext) lookupValidator(now int64) (validator common.Address, err error) { offset := now % epochInterval offset /= blockInterval validators, err := ec.DposContext.GetValidators() if err != nil { return common.Address{}, err } validatorSize := len(validators) offset %= int64(validatorSize) return validators[offset], nil } ✓ 根据当前时间以及当前验证⼈人来列列表来确定是否轮到当前节点出块
29. 出块 func (self *worker) mintBlock(now int64) error { err := engine.CheckValidator(self.chain.CurrentBlock(), now) if err != nil { return err } work, err := self.createNewWork() if err != nil { return err } result, err := self.engine.Seal(self.chain, work.Block, self.quitCh) if err != nil { return err } } ✓ 查询出块⼈人以及时间 ✓ 创建块头,打包交易易 ✓ 验证⼈人签名 ✓ 块⼴广播
30. 测试 # 编译 $ cd go-etherem && make geth # 通过配置文件创建第一个创世块, 第一批验证人通过配置文件指定 $ ./build/bin/geth init --datadir /path/to/datadir dpos_test_genesis.json # 启动 $ ./build/bin/geth --datadir /path/to/datadir --keystore /path/to/keystore console # 解锁验证人的账号 $ personal.unlock($validator, $passwd, 0) # 设置验证人 $ miner.setValidator($validator) # 开启挖矿 $ miner.start()
31. 遇到的一些问题 ✓ 节点默认 fast sync 模式启动, 这种模式下⽆无法接受新块导致同步⼀一直失败 ✓ 共识算法的 单元测试 和其他模块关系紧密, 修改共识算法需要调整⼤大量量单元测试 ✓ 代码量量⼤大,调试 是个体⼒力力活
32. References [1] h*ps://github.com/ethereum/go-ethereum [2] h*ps://ethereum.github.io/yellowpaper/paper.pdf [3] h*ps://github.com/ethereum/wiki/wiki/White-Paper [4] h*ps://github.com/ethereum/wiki/wiki/Design-RaYonale [5] h*ps://bitcoin.org/en/developer-guide [6] h*ps://eprint.iacr.org/2013/881.pdf [7] h*p://bitcoin.org/bitcoin.pdf [8] h*p://en.wikipedia.org/wiki/Merkle_tree [9] h*p://en.wikipedia.org/wiki/Patricia_tree [10]h*ps://blog.golemproject.net/how-to-find-10m-by-just-reading-blockchain-6ae9d39fcd95 [11] h*ps://ethfans.org/toya/arYcles/588