区块链原理与应用 习题及答案 范磊

第一章1.如果将数据库存储的数据格式改造为哈希链的形式能不能将其称为区块链系统，为什么？仅把数据块依次串联，后一块保存前一块哈希，实现数据防篡改完整性校验，只是一种数据存储结构。区块链不只是哈希链数据结构，是一套完整分布式系统。单机数据库改成哈希链，缺少分布式网络与共识，仅仅实现防篡改存储，不属于区块链系统。2.在区块链的结构中，每个区块包含前面一个区块的哈希值，这种结构是否可以扩展为每个区块可以包含多于一个区块的哈希值？如果不能这样扩展请给出理由，如果可以这样扩展请给出必要的条件。可以扩展，一个区块可以存放多个历史区块哈希。共识算法必须识别多父哈希结构，定义分叉选择规则。传统最长链规则不再直接适用，需要设计新的权重选择规则，解决多个父区块带来的分叉问题。3.假设区块链系统有10000个节点，每个节点采用随机选择的方式请求连接10个邻居节点建立P2P网络，请估算在该网络中从一个节点到任意节点的最大跳数，并利用Python等语言写一个仿真程序验证结论。 代码略。4.如果要在区块链的计算层实现数据加密功能面临什么困难，是否可以直接将加密数据？可以存储加密后的密文数据上链，但是区块链计算层不能直接对密文做业务计算。EVM等虚拟机只能执行明文逻辑，普通加密算法不支持密文态运算。如果采用隐私计算方案（同态加密、零知识证明）实现密文计算，计算开销极大，难以用于高频业务。5.设想一个未来需要区块链的应用场景，并分析在该场景中为何区块链比中心化系统更有优势。略。第二章1.利用SHA256的算法库，设计并实现一个对于数据验证的默克尔树的结构。代码略2.默克尔树采用的是二叉树的结构实现对于交易的快速验证，是否可以采用多叉树对默克尔树进行扩展，分析采用多叉树后验证一笔交易所需的计算量。 如果采用k叉树，验证一笔交易，需要沿着证明路径从叶子向上重新计算哈希直到根节点，需要执行H=logkN次哈希运算。k增大，树高度降低，验证单笔交易需要的哈希计算次数减少；默克尔证明路径的哈希元素个数变少。但是生成证明的时候，每个父节点需要携带k1个兄弟哈希值，单条默克尔证明的数据体积增大。3.改造ECDSA签名算法库在消息签名中使用固定的随机数，利用两个签名对恢复签名所使用的私钥。思路：如果两次签名使用同一个固定随机数k对两条不同消息(m_1,m_2)签名。得到两组签名(r,s_1)、(r,s_2)；r相同，因为完全由k决定。联立签名方程即可解出随机数及私钥。4.如果椭圆曲线上的计算性DH问题得到解决，构造针对Schnorr签名算法的攻击方法。 Schnorr算法的安全性依赖于离散对数问题，CDH问题可解不等于离散对数问题可解，因此并不存在基于CDH可解二设计的针对Schnorr签名算法的直接攻击方法。实际上离散对数问题可解可以得到CDH问题可解，反之并不成立。5.利用BLS签名算法库，实现BLS的聚合签名算法。 代码略。

第三章1.在比特币系统中，第i个区块的定义为Bi={H(Bi-1),Ri,ri}，并且满足H(Bi)<T。如果对于H(Bi)的计算定义为H((Bi-1)⊕Ri⊕ri)，其中⊕为按位异或，这种构造方式是否安全？为什么？ 不安全，存在严重安全漏洞。利用异或运算性质A⊕A=0。攻击者令R_i=B_{i1}，则B_{i1}⊕R_i⊕r_i=0⊕r_i=r_i区块哈希变为H(B_i)=H(r_i)。此时PoW哈希计算不再依赖父区块内容。攻击者可以离线预先暴力搜索满足H(r_i)<T的r_i；之后任意选定父块B_{i1}，设置R_i=B_{i1}，直接组装出满足PoW条件的合法区块。2.在比特币系统中，中本聪设定的出块速度目标为10分钟生成一个区块。假设在某个时刻系统中所有节点计算哈希的速度为10^9次/秒，有效区块的哈希值目标T应设定为多少？ 2^256/(6*10^11)3.思考构造工作量证明算法的函数需要满足哪些要求，设想是否可以利用其他函数替代哈希函数构造工作量证明算法。 PoW函数需要满足的要求：求解困难，验证高效。解不可复用，抵御预计算攻击。可以调整参数改变求解期望开销，适配算力变化。相同输入输出唯一，保证分布式各节点验证结果一致。 可能存在其他的替代函数。例如可能涉及基于大数分解、RSA求根等数论难题等。但替代方案存在局限,目前还没有满足上述要求的替代方案。4.重新定义一种数字货币系统，假设其区块产生速度与比特币相同。初始状态每个区块奖励100个数字货币，并且每个区块奖励数量每年衰减为上一年的90%，计算这个系统中数字货币的总量。 区块出块间隔10分钟，一年区块数量：C=365*24*6=52560第k年单块奖励：100*0.9^{k-1}每年发行总量构成无穷等比数列，公比q=0.9 发行总量为Total=52560*100*10=525600005.假设Alice拥有比特币系统中某个UTXO锁定账户所对应的私钥，该UTXO中锁定了10个比特币。Alice签署一个支付交易，该交易具有一个输出转账7个比特币给Bob，原始UTXO中剩余的3个比特币是否仍归Alice所有？ 如果Alice没有处理剩余的3个比特币，则由于锁定的交易从UTXO中移除，Alice将不再拥有这3个比特币。6.假设Alice与Bob共享了一个秘密的口令P，Alice计算P的哈希值得到PHASH=SHA256(P)。Alice构造锁定脚本将比特币转给Bob，脚本内容为：SHA256<PHASH>EQVERIFY。1）Bob应该构造怎么的解锁脚本才能使用Alice转给他的比特币。解锁脚本为<P>。压入P；执行SHA256得到SHA256(P)=PHASH；压入常量PHASH；EQVERIFY比较两者相等，脚本验证通过，Bob可以花费该笔输出。2）这种基于口令的转账机制是否安全？如果不安全存在什么样的攻击？ 该机制不安全。首先可以采用离线字典暴力破解攻击。锁定脚本存储在公开区块链，PHASH对全网可见。攻击者获取PHASH后，可以离线遍历口令字典，计算候选口令的SHA256哈希，比对PHASH。由于人类口令熵通常很低，攻击者可以快速破解出口令P，得到P之后攻击者构造解锁脚本直接盗走比特币。SHA256计算速度快，进一步放大攻击效果。其次解锁脚本无签名身份校验，不需要Bob的私钥，任何知晓口令P的人均可花费输出。当Bob签署转账脚本时，攻击者截获交易修改转账地址仍然可以通过验证。

第四章1.在共识协议中为什么有效性也是必须的，如果协议不具有有效性会如何影响区块链的执行？ 如果共识协议不具有有效性，则共识结果可能都是无意义的内容，协议失去实际意义。2.请描述在同步网络环境中，为什么共识协议不受FLP不可能定理的约束。 FLP不可能定理约束的是异步环境中的情况。在同步网络环境中，节点间可通过超时机制确认对方的状态，不会出现状态不确定的状况，因此可以同时保证协议的安全性和活性。3.在实际的网络环境中，网络延迟通常是变化的，请思考如果要设计基于同步网络假设的共识协议可以通过什么方式获得网络最大延迟？ 强同步共识协议需要网络最大延迟Δ，现实网络延迟动态变化，无法获得绝对真实的物理上界，只能通过测量与保守估计得到Δ。节点之间周期性发送心跳探测包，测量往返时延RTT，取单向时延高百分位统计值，叠加安全余量作为Δ。4.假设在OM(f)协议中f=1，n=4，如果主节点是恶意节点，描述协议执行过程并说明协议执行的结果。 略5.如果Dolev-Strong协议仅执行f轮是否安全，为什么？ 不安全，因为包含主节点的f个恶意节点可以完全控制f轮的运行，在f结束时使得不同诚实节点可能收到不同的提案，从而破坏系统的安全性。

第五章1.在比特币系统中，假设所有节点每秒钟完成工作量证明计算的次数为10^8，为了保证平均10分钟完成一次出块，工作量证明的目标T应设为何值？ T=2^256/{6*10^10}2.在工作量证明系统中，假设诚实节点的算力占比为60%，恶意节点的算力占比为40%。不考虑网络延迟因素，如果一个交易被6个区块确认后就被接受，则其被最终擦除掉的概率为多少？ 诚实算力：q=0.6,恶意算力：p=0.4,z=6个区块确认。攻击者追上的概率近似为(p/q)^z。带入后可得概率约为8.78%。3.在工作量证明系统中，假设诚实节点的算力占比为60%，恶意节点的算力占比为40%。假设区块在网络中传播的延迟为1分钟，估算一下区块的出块间隔需要设置为多少才能保证系统的安全性。 粗略估算如下：假设出块间隔为T分钟，当产生一个新区块后，诚实节点平均1分钟后才能收到，因此在这1分钟内诚实节点的算力是浪费的。也就是每T分钟，诚实节点浪费1分钟,因此诚实节点的算力利用率为T/(T+1)。如果要保证系统的安全性，诚实节点的有效算力应该大于恶意节点。也就是0.6T/(T+1)>0.4。可得T>2。这是一个最基本的估计，仅仅要求诚实节点算力占优。如果要求以较短的确认时间保证安全性，需要诚实节点有效算力显著占优。例如要求0.6T/(T+1)>0.4*1.2,则T>4。4.在工作量证明系统中，假设恶意节点占有算力的比例为20%，如果恶意节点采取自私挖矿策略，则其获得奖励占系统总奖励的比例是多少？如果恶意节点占有算力的比例为40%，则采用自私挖矿获得奖励的比例呢？ 近似估计，如果算力占20%：0.2*(2*0.2+1*(1-0.2)/2)=16% 如果算力占40%: 0.4(2*0.4+1*(1-0.4)/2)=44%5.利用Python或者Go语音，实现一个工作量证明的仿真系统，设置合理的参数模拟区块链的生成过程。假设恶意节点算力占比为40%，一笔交易的接受需要6个区块确认，在这些条件下通过仿真统计恶意节点攻击一笔交易（擦除该交易）成功的概率。 略

第六章1.在共识协议中，假设存在f个拜占庭节点，节点的总数n=5f+1，则法定多数证明QC应至少包括多少有效的投票。 5f+1个节点最多能投出6f+1个投票，为了保证安全性需要#{QC}>(6f+1)/2，也就是要求#{QC}>=3f+1。2.在Paxos协议中，如果更新的主节点在没有收到超过半数节点发送的gather消息时就开始新的共识过程可能存在什么问题？ 新主节点可能无法获取已经完成投票的旧提案，会直接提交冲突的新提案值，有可能覆盖已经确定的决议，造成系统同时存在两个不同已选定值，破坏共识的安全性。3.在分布式系统中假设存在f个拜占庭节点，节点的总数n=2f+1，如何修改PBFT协议才能够实现同时保证活性和安全性的共识协议。 要在n=2f+1，容忍f个拜占庭节点，同时保证安全+活性，必须引入额外系统假设，不能只修改PBFT消息阶段或者quorum大小。例如放弃PBFT的部分同步假设，改为强同步网络，消息存在已知的最大传输时延。每个共识阶段设置严格超时，超时没有收到消息直接认为该节点是拜占庭节点，视图切换也使用固定超时。强同步下可以区分“消息延迟”和“节点作恶”。拜占庭节点沉默不响应，直接判定为故障,诚实节点消息一定在最大延迟内到达。此时n=2f+1可以容忍f个拜占庭节点。4.利用Python或者Go语音，实现基本的Paxos共识协议。 略。

第七章1.假设共识节点总数为1000，每次从中随机抽取100个节点作为参与共识。共识协议要求参与共识的节点中诚实节点数量超过2/3，如果要保证这个安全假设满足的概率为99.99%，则1000个共识节点中诚实节点的数量至少为多少？抽样到属于无放回抽样，设全网诚实节点数量为H，抽样诚实节点数量X符合超几何分布：X∼H(N=1000,H,n=100)。要求Pr[X≥67]≥0.9999。由于N较大、抽样比例100/1000=0.11，可用二项式分布近似超几何分布。通过近似计算可得，诚实节点数量至少为850.2.在DFINITY的共识协议中，如果对于第r-2轮区块的确认不要求r-1的所有区块都连接在同一个r-2轮的区块中是否会影响协议的安全性？ DFINITY确认规则要求第r1轮所有区块都必须以该r2区块作为父块。该条件用于保证不存在其他分叉分支可以在r2高度产生竞争区块，确保全网只能有唯一区块被最终确认。如果取消该约束，攻击者可以使得两个不同r2区块均满足其余确认条件，破坏安全性保证。3.在Algorand算法中，为什么协议的安全性也需要同步网络假设？如果网络失去同步请构造一种破坏安全性的场景。 Algorand的核心目标是：在每个共识轮次里，系统以很高概率选出足够多的诚实提议者/证明者，从而得到唯一的、不可伪造的“可用块”，并保证不会出现两边都能在链上形成对抗分叉。若延迟不受约束，对手就可以持续让某些诚实节点在关键时刻“收不到/没来得及知道”对方已经看到的提议，从而实现分叉。 攻击者将网络节点分成两组A和B，其中各约一半，且尽量包含足够多诚实节点。让组A收到提案P1并完成投票，让组B看不到P1的信息。同时让组B收到P2也完成投票。这个过程能成功是因为Algorand是一个软投票QC的机制，对于达到QC的数量是不固定的，因此对于投票结果的确认可能出现误判。​4.在OuroborosPraos协议中，如果一个纪元的跨度设置为很短是否会影响协议的安全性？例如在极端情况下，一个纪元仅包含一个时间片也就是仅生成一个区块，恶意用户是否可以通过控制随机数种子η控制区块的输出？ 可能会影响协议的安全性。恶意用户通过有机会通过控制随机数种子使得后续纪元的出块节点均为恶意节点。5.在Casper协议中，对于区块的确认要求出现两个连续高度的区块间的边完成投票才能完成对第一个区块的确认，如果对于区块的确认不要求是连续的高度是否会影响协议的安全性？ 会破坏协议的安全性。可以通过构造冲突的投票结果证明。

第八章1.智能合约中的燃料费是什么？燃料费的作用是什么？为什么需要支付燃料费用？ 燃料费是EVM中衡量执行操作资源消耗的计量单位，每一种虚拟机指令对应固定Gas消耗,燃料费等于消耗Gas数量乘以Gas价格，用户以ETH支付。其作用是计量合约执行的资源开销，奖励打包交易的验证节点，限制执行步骤，终止无限循环代码。区块链节点需要执行全部交易，公共资源如果免费，攻击者可发送大量恶意交易实施DoS攻击。付费形成经济门槛抵御垃圾交易，保障区块链网络稳定运行。2.为什么智能合约中不能使用随机化算法，如果使用随机化算法会带来什么问题？ 区块链EVM执行要求完全确定性，全网节点执行同一交易必须输出一致结果；传统随机算法依赖本地熵源，无法保证各节点输出相同随机数，链上没有原生安全随机源。3.为什么智能合约中不直接使用浮点数，要表示比较小的量应该如何处理？ 浮点数存在精度丢失，金融合约中微小误差会累积造成错误。浮点数不同平台舍入行为不一致，会破坏区块链执行的确定性，导致各节点结果不一致，破坏共识。表示小数值采用定点整数缩放方案：将小数乘以放大倍数（一般为10的N次幂）转化为整数，全部运算使用整数。计算遵循先乘法后除法，降低截断误差。4.阻塞区块链的交易也是对于区块链的一种攻击方法，查阅当前以太坊的手续费水平以及吞吐率，计算阻塞以太坊3分钟的交易所需要的手续费成本。 以太坊出块间隔12秒，3分钟共15个区块；区块gas上限60 000 000gas。阻塞攻击需要填满全部区块。总Gas=15×60 000 000=900 000 000gas。取gas单价12gwei/gas，总手续费=900000000*12=10.8ETH。5.如何修改本章最后一节中的代码才能避免重入攻击？ 修改为先减去余额再转账。

第九章1.学习使用Remix智能合约开发环境，基于样例代码完成合约代码的编写、编译与部署测试。 略。2.智能合约中的状态变量是如何存储和访问的？为什么状态变量需要持久化存储？ 以太坊中合约的状态变量存储在合约账户的存储Storage中，Storage是持久化的键值数据库，键和值均为32字节。EVM的memory仅在单次交易生效，交易结束就销毁，合约需要在不同交易、不同区块之间保存余额、权属、配置等业务数据。持久化存储的数据在节点重启后数据不丢失，后续交易可以访问历史状态。3.请编写一个简单的智能合约，实现对于映射表的存储，可以在映射表中插入数据、修改数据、删除数据以及查询数据。略4.智能合约一旦部署通常是不可更改的，是否可能设计一种可以升级的智能合约架构。 可以实现可升级智能合约。合约部署后字节码不可直接修改，采用代理模式将存储状态与业务逻辑分离。代理合约对外暴露固定地址，保存全部状态数据，逻辑合约执行业务代码，读写代理合约的存储。升级时部署新版逻辑合约，修改代理指向新逻辑合约，实现功能迭代。5.编写一个简单的以太坊智能合约，实现一个简单的投票系统。合约的建立者设置若干候选人以及投票截至时间，允许用户投票给不同的候选人且每个用户只能投一票，在投票结束后输出得票最高的候选人。 略。

第十章1.同质化代币和非同质化代币的区别是什么？为什么非同质化代币可以更好的用于传统资产的数字化？同质化代币之间完全等价、可互换。每一枚代币没有唯一标识，任意两个代币可以等价替换，可以无限拆分。账户记录余额，只记录持有数量，不区分单个代币个体。非同质化代币中每一个代币拥有全局唯一ID，代币之间不可互换，每个代币代表独立唯一资产。现实世界传统资产（房产凭证、艺术品、版权凭证、奢侈品、票据）大多具备唯一性，资产个体之间不可等价互换。NFT自带唯一标识，可以对应现实中唯一实体资产；同质化代币只能代表“数量”，无法区分个体。NFT的转移即代表链上权属变更，交易流转记录完整可追溯。每一份资产独立，不会发生多份实体资产混淆，契合实物资产“一物一权”的现实法律逻辑。2.在UniSwap去中心化交易系统中，假设建立的一个交易对包含A、B两种数字货币。其中A的数量为1000000，B的数量为500000，则注入1000个A可以获得多少B？完成这个交易后B相对于A的价格变化多少？ 初始：A0=1000000，B0=500000，得到A0*B0=5*1011注入AD=1000，则A1=A0+AD=1001000，可得B1=499500.4995获得B的数量BD=500000-499500.4995=499.5 交易前价格：P_0=1000000/500000=2交易后价格：P_1=1001000/499500.4995=2.004价格变化：P=P_1-P_0=0.0043.在UniSwap去中心化交易系统中，假设建立的一个交易对包含A、B两种数字货币。其中A的数量为2000000，B的数量为5000000，如果侦测到有一笔注入10000个A的交易，如何通过三明治攻击无风险获利？攻击者设置更高Gas，优先执行一笔交易：投入B，从池中买入A。池子里A的储备变少，A的价格被推高。矿工接着打包受害者交易：受害者向池子注入10000个A，池内A数量增加，A价格下跌。受害者在已经抬高的价格下完成兑换B，承受滑点损失。紧随受害者交易之后，攻击者再执行一笔交易：把第一步抢跑获得的A全部卖回池子，换回B。此时A价格因受害者交易已经回落，攻击者卖出A得到的B多于最初投入的B，实现套利。4.流动性提供者向Uniswap的一个交易对ETH/USDT池中投入了10000ETH和30000000USDT，因此初始时1ETH等于3000USDT。随后市场价格变动，1ETH的价格上升到6000USDT。以USDT为基准计算流动性提供者的无常损失。 初始状态：10000*30000000=3*10^11 价格变动后，交易池中的价格将于市场价格接近，设此时有ETH数量为x，USDT的数量为y，则y/x=6000，同时x*y=3*10^11因此可以得到：y=42,426,407，x=7071此时总价值以USDT计算为：y+6000*x=84,852,407初始状态总价值以当前的USDT计算为30000000+10000*6000=90000000因此无常损失为：90000000-84,852,407=5,147,593USDT5.设计一个在未来互联网中的去中心化身份认证的应用场景，相对于中心化身份认证有何优势？ 略

第十一章1.列举常用的区块链性能扩展方式，并比较几种方式的优劣。可以通过修改区块链的基本参数扩容，例如增大区块大小、缩短出块间隔。这种方法实现简单，无需修改上层应用。但是增大区块会加重节点存储、带宽压力，降低全节点参与度，趋向中心化。缩短出块间隔会提升分叉率，降低网络稳定性。因此性能扩展主要使用下面的技术。第一种是分片技术，将全网状态与交易拆分到多个分片并行处理。性能随分片数量线性提升，吞吐量上限高。缺点是存在跨分片交易开销，协议设计复杂。第二种是侧链技术，通过双向锚定和主链资产互通。侧链可以自定义参数，吞吐量高，主链负责资产锁定，不处理业务交易。但是安全性继承主链，资产赎回存在时间延迟。第三中是汇总Rollup技术。这种扩容技术将交易数据放在链下，性能扩展性好。但是需要额外保证链下处理交易数据过程的正确性，证明生成计算开销大。第四种是闪电网络类技术。交易链下执行，仅将最终状态上链。交易即时确认，手续费极低。但是需要预先建立通道、抵押资金。2.在区块链的分片技术中如何提高分片间数据同步的效率？分片系统将交易拆分到不同分片执行，跨分片交易、分片状态同步是主要瓶颈，可