PROOFS OF WORK AND BREAD PUDDING PROTOCOLS (EXTENDED ABSTRACT)

简单介绍

这一篇是讲PoW基础的论文,没有具体说明PoW是什么,但给出了与PoW相关的一些定义和例子, 用于理解PoW还可. 整篇文章看完还是云里雾里的, 但大概理解了PoW其实相当于一个证明, 对于给定的一个hash函数, V知道这个函数的计算结果, 而P要做的是向V证明它知道这个计算结果所对应的原象. 因为hash算逆几乎不可能, 因此若原象是n位, P随便猜的几率为1/2^n.

定义:

POW即是交互性的,又是非交互性的证明协议. 在协议执行期间P和V要进行 一个私密硬币翻转的随机数, 最终由V决定是否接收. 使用C_V来标记V的私密硬币翻转, 要保证有效的证明,就要保证C_V的生成不会被P控制. 在非交互性的PoW中, 证明者模拟与验证者的通信, 并将结果发给验证者.

隐性PoW: 一种非交互性的协议, 证明者在证明时不需要验证者的主动参与.

假设没有通信延迟, 定义开始时间\(t_s\)为V初始化它的第一轮通信；完成时间\(t_c\)为协议的最后一轮通信完成, PoW的目标即为P证明它在时间\([t_s, t_c]\)中进行了确定数量的计算. 令l为安全参数, poly为任何给定的多项式变量, 本定义在假设P可以在\([-\infty, t_c]\)的时间内进行计算. 作者对PoW的hardness进行特征化, 定义1为hardness的下界, 定义2为其上界.

• 定义1: PoW为(w,p)-hard: P有内存m, 若p在[t_s, t_c]时间内最多进行了w步, 则V接受它的概率至多为: \(p + o(\frac{m}{poly(l)})\).
• 定义2: PoW为(w,p,m)-feasible: P有内存m, 若p在\([t_s, t_c]\)时间内最多进行了w步, 且P能使V接收的概率至少为p.
• 定义3: 完备的PoW: 对于某个w, PoW 是(w,1,w)-feasible的. 若V的计算量大大少于P,则PoW为高效的, 且这种证明有很大的advantage.
• 定义4: 对于完备的PoW, w为满足 (w, 1, w)-feasible的最小值, z为V要进行的最大验证数量, 则PoW的 advantage 等于 w/z.
• 定义5: 两个PoW独立性的定义,略
• 定义6: 假设PoW1为(w,p)-hard, P1, V1分别为它的证明者了验证者. 假设P1同时也是PoW2的验证者(P1=V2), 若以下为真则PoW2为PoW1的bread pudding protocol: P1(V2) 接收PoW2, P1 可在PoW1中进行w个计算步骤并使V1接收PoW1的概率至少为: \(p+1/poly(l)\)

PoW例子

PIPOW: h为单向函数, V 生成长为l的随机二进制字符串x, x’为x的l-k位. V计算出y=h(x). V发送(x’, y)给P, 若要使PoW成功, P正确要计算出y的前向x.

Bread Pudding For MicroMint

(这个是作者的一个例子, 将它提出的Bread Pudding应用在MicroMint中. Mint 在这里的意思为铸币的意思.)

MicroMint

MicroMint是一个微支付系统, 铸币操作需要的边际成本较小,即铸币需要大量的基础硬件投资.假设hash函数h 将n位前象映射到n位的象中, 则要找到冲突即为将一个球随机地扔到2^n 个箱子中, 即给了h(x)找到x的概率为1/2^n.

若n太大,则维护2^n个箱子就需要太大的存储成本. 一个变体方案: 没大明白它的方案.

Bread Pudding Minting

令h 为hash函数, || 为字符串连接操作, 将球定义为三元组: (i,x,y), y=h(r||i), r为secret value. 一个有效的ball为一个三元组,且当h(x||y) 中至少有t个重要位与s相等.

在该方案中, 验证者初始化PoW时发送(i,y)给证明者, 其中y=h(r||i), 并发送参数对(s,t)给证明者. 客户的任务为找到一个值x, 让它h(x||y) 的前t位与s相等, 即(i,x,y)是一个有效ball.