代码编织梦想

1. 引言

Aleo系列,前序博客有:

Aleo采用Proof of Succinct Work共识。

Proof of Succinct Work为SNARK-based Proof of Work算法,旨在激励对SNARKs的硬件加速。

具体为:
Miner将pending交易打包,并计算a valid nonce来解决a Proof of Succinct Work puzzle。

puzzle的difficulty rate会动态调整,以反映Aleo上的miners在每秒贡献的proof数量。

  • block time:是指网络生成有效区块所用的时间。基于网络的hashrate会变化。但是由blcok difficulty控制。
  • block difficulty:根据最近的block times来调整,以维护整个网络的平均block time的稳定性。

解决该puzzle的miner address将的激励为:base block reward + 该区块所包含的交易的手续费。

2. Aleo中所用的曲线

Aleo中使用pairing-friendly 曲线来生成和验证proof:

*Edwards BLS12BLS12-377Edwards BW6BW6-761
Curve TypeTwisted EdwardsBarreto-Lynn-ScottTwisted EdwardsBrezing–Weng
Scalar Field Size251 bits253 bits374 bits377 bits
Base Field Size253 bits377 bits377 bits761 bits
G1 Compressed Size*32 bytes48 bytes48 bytes96 bytes
G2 Compressed Size*N/A96 bytesN/A96 bytes

相关参数为:

  • Edwards BLS12:

    • scalar field: 0 x 04 a a d 957 a 68 b 2955982 d 1347970 d e c 005293 a 3 a f c 43 c 8 a f e b 95 a e e 9 a c 33 f d 9 f f 0x04aad957a68b2955982d1347970dec005293a3afc43c8afeb95aee9ac33fd9ff 0x04aad957a68b2955982d1347970dec005293a3afc43c8afeb95aee9ac33fd9ff
    • scalar field root of unity: 0 x 00 b 4 b 1 d 4 c 7 e 5 e 163 b 1 a f 246173 f d b 411 b d b 82 a c 32901 d c b 9 d 289433 f f 2 b 7 d 5 c 9 0x00b4b1d4c7e5e163b1af246173fdb411bdb82ac32901dcb9d289433ff2b7d5c9 0x00b4b1d4c7e5e163b1af246173fdb411bdb82ac32901dcb9d289433ff2b7d5c9
    • base field: 0 x 12 a b 655 e 9 a 2 c a 55660 b 44 d 1 e 5 c 37 b 00159 a a 76 f e d 00000010 a 11800000000001 0x12ab655e9a2ca55660b44d1e5c37b00159aa76fed00000010a11800000000001 0x12ab655e9a2ca55660b44d1e5c37b00159aa76fed00000010a11800000000001
    • base field root of unity: 0 x 0 d 1 b a 211 c 5 c c 349 c d 7 a a c c 7 c 597248269 a 14 c d a 3 e c 99772 b 3 c 3 d 3 c a 739381 f b 2 0x0d1ba211c5cc349cd7aacc7c597248269a14cda3ec99772b3c3d3ca739381fb2 0x0d1ba211c5cc349cd7aacc7c597248269a14cda3ec99772b3c3d3ca739381fb2
  • BLS12-377:

    • scalar field: 0 x 12 a b 655 e 9 a 2 c a 55660 b 44 d 1 e 5 c 37 b 00159 a a 76 f e d 00000010 a 11800000000001 0x12ab655e9a2ca55660b44d1e5c37b00159aa76fed00000010a11800000000001 0x12ab655e9a2ca55660b44d1e5c37b00159aa76fed00000010a11800000000001
    • scalar field root of unity: 0 x 0 d 1 b a 211 c 5 c c 349 c d 7 a a c c 7 c 597248269 a 14 c d a 3 e c 99772 b 3 c 3 d 3 c a 739381 f b 2 0x0d1ba211c5cc349cd7aacc7c597248269a14cda3ec99772b3c3d3ca739381fb2 0x0d1ba211c5cc349cd7aacc7c597248269a14cda3ec99772b3c3d3ca739381fb2
    • base field: 0 x 01 a e 3 a 4617 c 510 e a c 63 b 05 c 06 c a 1493 b 1 a 22 d 9 f 300 f 5138 f 1 e f 3622 f b a 094800170 b 5 d 44300000008508 c 00000000001 0x01ae3a4617c510eac63b05c06ca1493b1a22d9f300f5138f1ef3622fba094800170b5d44300000008508c00000000001 0x01ae3a4617c510eac63b05c06ca1493b1a22d9f300f5138f1ef3622fba094800170b5d44300000008508c00000000001
    • base field root of unity: 0 x 00 f 3 c 1414 e f 58 c 54 f 95564 f 4 c b c 1 b 61 f e e 086 c 1 f e 367 c 33776 d a 78169 a 7 f 3950 f 1 b d 15 c 3898 d d 1 a f 1 c 104955744 e 6 e 0 f 0x00f3c1414ef58c54f95564f4cbc1b61fee086c1fe367c33776da78169a7f3950f1bd15c3898dd1af1c104955744e6e0f 0x00f3c1414ef58c54f95564f4cbc1b61fee086c1fe367c33776da78169a7f3950f1bd15c3898dd1af1c104955744e6e0f
  • Edwards BW6:

    • scalar field: 0 x 0035 c 748 c 2 f 8 a 21 d 58 c 760 b 80 d 94292763445 b 3 e 601 e a 271 e 1 d 75 f e 7 d 6 e e b 84234066 d 10 f 5 d 893814103486497 d 95295 0x0035c748c2f8a21d58c760b80d94292763445b3e601ea271e1d75fe7d6eeb84234066d10f5d893814103486497d95295 0x0035c748c2f8a21d58c760b80d94292763445b3e601ea271e1d75fe7d6eeb84234066d10f5d893814103486497d95295
    • scalar field root of unity: 0 x 0006 b a 8 c 867 e a c c f 5 f 7 e 46 b c d b 07 d 0 f 4 b 2595092 e e d f f 5 c 5603102866827125373710874 d 7416 d 75 a 832273177 b 0 e 245 0x0006ba8c867eaccf5f7e46bcdb07d0f4b2595092eedff5c5603102866827125373710874d7416d75a832273177b0e245 0x0006ba8c867eaccf5f7e46bcdb07d0f4b2595092eedff5c5603102866827125373710874d7416d75a832273177b0e245
    • base field: 0 x 01 a e 3 a 4617 c 510 e a c 63 b 05 c 06 c a 1493 b 1 a 22 d 9 f 300 f 5138 f 1 e f 3622 f b a 094800170 b 5 d 44300000008508 c 00000000001 0x01ae3a4617c510eac63b05c06ca1493b1a22d9f300f5138f1ef3622fba094800170b5d44300000008508c00000000001 0x01ae3a4617c510eac63b05c06ca1493b1a22d9f300f5138f1ef3622fba094800170b5d44300000008508c00000000001
    • base field root of unity: 0 x 00 f 3 c 1414 e f 58 c 54 f 95564 f 4 c b c 1 b 61 f e e 086 c 1 f e 367 c 33776 d a 78169 a 7 f 3950 f 1 b d 15 c 3898 d d 1 a f 1 c 104955744 e 6 e 0 f 0x00f3c1414ef58c54f95564f4cbc1b61fee086c1fe367c33776da78169a7f3950f1bd15c3898dd1af1c104955744e6e0f 0x00f3c1414ef58c54f95564f4cbc1b61fee086c1fe367c33776da78169a7f3950f1bd15c3898dd1af1c104955744e6e0f
  • BW6-761:

    • scalar field: 0 x 01 a e 3 a 4617 c 510 e a c 63 b 05 c 06 c a 1493 b 1 a 22 d 9 f 300 f 5138 f 1 e f 3622 f b a 094800170 b 5 d 44300000008508 c 00000000001 0x01ae3a4617c510eac63b05c06ca1493b1a22d9f300f5138f1ef3622fba094800170b5d44300000008508c00000000001 0x01ae3a4617c510eac63b05c06ca1493b1a22d9f300f5138f1ef3622fba094800170b5d44300000008508c00000000001
    • scalar field root of unity: 0 x 00 f 3 c 1414 e f 58 c 54 f 95564 f 4 c b c 1 b 61 f e e 086 c 1 f e 367 c 33776 d a 78169 a 7 f 3950 f 1 b d 15 c 3898 d d 1 a f 1 c 104955744 e 6 e 0 f 0x00f3c1414ef58c54f95564f4cbc1b61fee086c1fe367c33776da78169a7f3950f1bd15c3898dd1af1c104955744e6e0f 0x00f3c1414ef58c54f95564f4cbc1b61fee086c1fe367c33776da78169a7f3950f1bd15c3898dd1af1c104955744e6e0f
    • base field: 0 x 0122 e 824 f b 83 c e 0 a d 187 c 94004 f a f f 3 e b 926186 a 81 d 14688528275 e f 8087 b e 41707 b a 638 e 584 e 91903 c e b a f f 25 b 423048689 c 8 e d 12 f 9 f d 9071 d c d 3 d c 73 e b f f 2 e 98 a 116 c 25667 a 8 f 8160 c f 8 a e e a f 0 a 437 e 6913 e 6870000082 f 49 d 00000000008 b 0x0122e824fb83ce0ad187c94004faff3eb926186a81d14688528275ef8087be41707ba638e584e91903cebaff25b423048689c8ed12f9fd9071dcd3dc73ebff2e98a116c25667a8f8160cf8aeeaf0a437e6913e6870000082f49d00000000008b 0x0122e824fb83ce0ad187c94004faff3eb926186a81d14688528275ef8087be41707ba638e584e91903cebaff25b423048689c8ed12f9fd9071dcd3dc73ebff2e98a116c25667a8f8160cf8aeeaf0a437e6913e6870000082f49d00000000008b
    • base field root of unity: 0 x 00 d 0 f 0 a 60 a 5 b e 58 c f 9 d f a a 846595555 f 73 a 18 e 069 a c 04458 d 72 c 1 d 6 f 77 d 5 f 5 c 54 d 28 b e 3 a 9 f 55 c 8155 c 81153 f 4906 e 9 f e c 5 a 3614 a c 0 b 1 d 98484 f 3089 e 56574722 b e 36179047832 b 0377738 a 6 b 6870 f 9598 c 391832 e 000739 b f 29 a 000000007 a b 6 0x00d0f0a60a5be58cf9dfaa846595555f73a18e069ac04458d72c1d6f77d5f5c54d28be3a9f55c8155c81153f4906e9fec5a3614ac0b1d98484f3089e56574722be36179047832b0377738a6b6870f9598c391832e000739bf29a000000007ab6 0x00d0f0a60a5be58cf9dfaa846595555f73a18e069ac04458d72c1d6f77d5f5c54d28be3a9f55c8155c81153f4906e9fec5a3614ac0b1d98484f3089e56574722be36179047832b0377738a6b6870f9598c391832e000739bf29a000000007ab6

3. Proof of Succinct Work (PoSW)

PoSW为比特币SHA-based difficulty adjusting算法的变种,最关键的不同之处在于:

  • 底层计算不是hash运算,而是proof of knowledge计算。

使得PoSW:

  • 作为PoW来保证系统共识
  • 提供verification of transaction inclusion in a given block

PoSW采用异步模式,假设大多数miners(Provers)是诚实的。

PoSW中对于relation R \mathcal{R} R 的SNARK ( G , P , V ) (G,P,V) (G,P,V) 流程为:

  • 1)已知a set of (valid) transactions T i = t 1 , . . . , t n T_i = { t_1, ..., t_n } Ti=t1,...,tn 和 当前state state i \text{state}_i statei
    NewState ( state i , T i ) ← ( state i + 1 , w i + 1 ) \text{NewState}(\text{state}_i, T_i) \leftarrow (\text{state}_{i+1}, w_{i+1}) NewState(statei,Ti)(statei+1,wi+1)
    其中:

    • state i \text{state}_i statei:为第 i i i个block的state
    • w i + 1 w_{i+1} wi+1:为auxiliary information attesting to the validity of state i + 1 \text{state}_{i+1} statei+1
  • 2)Sample a random nonce n n n 并计算:【 C R S CRS CRS G G G的public output】
    P ( C R S , [ n , state i + 1 ] , w i + 1 ) ← π n P(CRS, [n, \text{state}_{i+1}], w_{i+1}) \leftarrow \pi_n P(CRS,[n,statei+1],wi+1)πn

  • 3)若 P R F ( π n ) < = d PRF(\pi_n)<= d PRF(πn)<=d,则设置 n i + 1 = n n_{i+1}=n ni+1=n π i + 1 = π n \pi_{i+1}=\pi_n πi+1=πn。否则返回步骤2)。【 P R F PRF PRF为a pseudorandom function used to evaluate the difficulty condition。】
    d d d为难度系数,借鉴了Bitocoin和其他PoW链,会根据网络hashrate进行动态更新。It is iteratively updated based on the maximal and current targets every fixed number of blocks and guarantees constant block time.

4. PoSW共识security

PoSW设计为满足传统PoW guarantees,要求其具有a time-lock puzzle安全属性。

为了实现time-lock,要求PoSW满足:

  • Amortization Resistance:即 不可摊销,不可batch操作。

4.1 Amortization Resistance(PoSW的不可batch性)

任何PoW系统的最重要特性是non-batchability,是指:

  • computation of many instances of the problem should not provide substantial speed-ups to miners through the reuse of information。

Aleo采用的是Generic Group Model (GGM),其中miners have access to an oracle O O O performing a given hard computation in the random encoding of some group G G G。计算难度取决于miner访问oracle O O O的次数。

在setup时,定义了 ϵ \epsilon ϵ-amortization resistance 作为 the ratio of oracle queries performed by the optimal algorithm A O ( P , n ) A^O(P,n) AO(P,n) computing n = p o l y ( n ) n=poly(n) n=poly(n) proofs simultaneously versus the algorithm A O ( P , 1 ) A^O(P,1) AO(P,1) computing each n n n proof individually。其中 n n n为proof size, Q u e r i e s ( A O ) Queries(A^O) Queries(AO)为the number of queries A O A^O AO makes to O O O x i x_i xi为the (randomly sampled) i i i-th problem instance:
ϵ ≤ 1 − Q u e r i e s ( A P , ℓ ( n ) O ( { x i } i = 1 ℓ ( n ) ) ) ∑ i = 1 ℓ ( n ) Q u e r i e s ( A P , 1 O ( x i ) ) . \epsilon \leq 1 - \frac{\mathsf{Queries}(\mathcal{A}^{\mathcal{O}}_{\mathcal{P}, \ell(n)}(\{\mathbf{x_i}\}_{i = 1}^{\ell(n)}))}{\sum_{i = 1}^{\ell(n)} \mathsf{Queries}(\mathcal{A}^{\mathcal{O}}_{\mathcal{P}, 1}(\mathbf{x_i}))}. ϵ1i=1(n)Queries(AP,1O(xi))Queries(AP,(n)O({xi}i=1(n))).

ϵ \epsilon ϵ为the advantage that a large miner receives due to the amortizability of the underlying puzzle。若 ϵ = 0 \epsilon=0 ϵ=0,则没有算法可attain speedup from batching and the puzzle is perfectly amortizable。

4.2 Quantization Error & Forking Probability

与其它PoW scheme不同,PoSW底层计算可能solution (a single proof)所需时间要长于其它puzzles。因为NIZK生成proof是计算密集型的,若其与产块时间相当,会影响底层链的安全性。

4.2.1 Quantization Error

设置proof生成时间 为 a significant fraction of 产块时间,slow miner可在其finish current attempt之前 hear of a new solution,然后放弃当前其所计算的部分proof,直接开始mine新的区块。这种放弃的部分算力浪费对应为quantization error ϵ Q \epsilon_Q ϵQ
ϵ Q = 1 − τ / ( e τ − 1 ) \epsilon_Q = 1 - \tau / (e^{\tau} - 1) ϵQ=1τ/(eτ1)
其中产块时间normalize为 1 1 1,平均生成proof的时间设置为 τ \tau τ

注意 τ ← 0 \tau\leftarrow 0 τ0意味着 ϵ Q ← 0 \epsilon_Q\leftarrow 0 ϵQ0。即意味着miner放弃的work趋近为0。生成proof的时间 τ p \tau_p τp与产块时间 τ b \tau_b τb之间的ratio r = τ p / τ b r=\tau_p/\tau_b r=τp/τb应最小化。

4.2.2 Forking Probability

以上quantum effects将增加the number of observed collisions。若miner未同步,当收到一个区块时,会选择继续完成其当前effort。若所有miner都这么做,将影响整个网络同步。

一个mining round所期待的solution数量为一个随机变量 X ∼ P o ( τ ) X\sim Po(\tau) XPo(τ)

将分叉的概率上线表示为 ϵ F \epsilon_F ϵF
ϵ F < = ( 1 − P o i s s o n ( 1 , τ ) ) / ( 1 − P o i s s o n ( 0 , τ ) ) < = τ / 2 \epsilon_F <= (1 - Poisson(1, \tau)) / (1 - Poisson(0, \tau)) <= \tau / 2 ϵF<=(1Poisson(1,τ))/(1Poisson(0,τ))<=τ/2
其中, f ( q ) = P o s s i o n ( q , τ ) f(q)=Possion(q,\tau) f(q)=Possion(q,τ)为the PDF of X X X

对于固定的block time,任何对proving time的改进(如硬件加速,或circuit size调整),都将降低分叉概率。

5. PoSW Predicate

PoSW circuit中的predicate用于验证the inclusion of transactions in a given block。

5.1 System State

Aleo中的system state定义为:

  • a Merkle tree Tree G ( h ) \text{Tree}_G(h) TreeG(h) of depth h h h over a CRT function G : { 0 , 1 } 512 → { 0 , 1 } k / 2 G:\{0,1\}^{512}\rightarrow \{0,1\}^{k/2} G:{0,1}512{0,1}k/2

其中 G G G为SHA-256, k = 512 k=512 k=512

Aleo中的system state也可称为“state tree”,其每个leaf为the unique ID of a transaction to be processed,变量state为tree root。

在这里插入图片描述

PoSW circuit取 state tree中的 q < = d q<=d q<=d subtree,然后计算a Merkle tree of depth q q q。 The leaves of the tree are the depth q q q elements of the state tree Tree H ( h ) \text{Tree}_H(h) TreeH(h), instantiated over k k k-bit leaves with a different CRT function H : { 0 , 1 } k → { 0 , 1 } ( k / 2 ) H: \{0, 1\}^k \rightarrow \{0, 1\}^{(k/2)} H:{0,1}k{0,1}(k/2) as a new PoSW tree Tree H ( q ) \text{Tree}_H(q) TreeH(q). This layout is illustrated in the diagram on the left. For example, for KaTeX parse error: Expected '}', got '_' at position 16: G = \text{BLS12_̲377} we set H H H as the 512-bit Pedersen CRH with output truncated to 256 bits.

H H H的circuit implementation将mask the witness variables based on a pseudorandom seed,这将作为predicate statement的一部分。这需要满足non-amortization要求。Aleo中设置 q = 3 q=3 q=3

5.2 Pedersen Primitives

k k k-bit Pedersen hash function over G G G CRT hash函数定义为:
H ( G , x ) = ∏ i = 1 k G i x i H(G,x)=\prod_{i=1}^k G_i^{x_i} H(G,x)=i=1kGixi

其中 G i G_i Gi G G G中的randomly sampled generator, x i x_i xi为input x x x的第 i i i个bit。

该函数的CRT security可reduce为 the hardness of the DLP over group G G G

5.2.1 Symmetric Pedersen Gadget

k k k-bit symmetric Pedersen hash定义为:
H sym ( H , ρ ) = ∏ i = 1 k H i ( 1 − 2 ⋅ ρ i ) H_{\text{sym}}(H,\rho)=\prod_{i=1}^{k}H_i^{(1-2\cdot \rho_i)} Hsym(H,ρ)=i=1kHi(12ρi)

定义 ( F p 2 ) k (F_{p^2})^k (Fp2)k内的group variable Q = ( Q x , Q y ) , h i = ( h x i , h y i ) Q=(Q_x,Q_y), h_i=(h^i_x,h^i_y) Q=(Qx,Qy),hi=(hxi,hyi),check如下evaluations:

  • ρ i = 0 \rho_i=0 ρi=0,设 h i = H i h_i=H_i hi=Hi;否则若 ρ i = 1 \rho_i=1 ρi=1,则设 h i = H i − 1 h_i=H_i^{-1} hi=Hi1
  • Q 0 Q_0 Q0为identity 且 Q i = Q i − 1 ∗ h i Q_i=Q_{i-1}*h_i Qi=Qi1hi

这需要 k k k Edwards multiplications (6 constraints each),且需要a bit lookup for each of the h i h_i hi in addition to k k k booleanity checks。

具体见PedersenCRHGadget中的precomputed_base_symmetric_multiscalar_mul

5.2.2 Masked Pedersen Gadget

k k k-length masked Pedersen hash function over G G G 为 CRT hash function H mask : { 0 , 1 } k × { 0 , 1 } k × G → G H_\text{mask}:\{0,1\}^k\times\{0,1\}^k\times G\rightarrow G Hmask:{0,1}k×{0,1}k×GG
H mask G , H ( ρ , x , P ) = P ∗ ∏ i = 1 k ( 1 [ x i ( + ) ρ i = 1 ] G i 2 ∗ x i − 1 H i 2 ∗ ρ i − 1 + 1 [ x i ( + ) ρ i = 0 ] H i 2 ∗ ρ i − 1 ) H_\text{mask}^{G, H}(\rho, x, P) = P * \prod_{i=1}^{k}(1[x_i (+) \rho_i = 1] G_i^{2 * x_i - 1} H_i^{2 * \rho_i - 1} + 1[x_i (+) \rho_i = 0] H_i^{2 * \rho_i - 1}) HmaskG,H(ρ,x,P)=Pi=1k(1[xi(+)ρi=1]Gi2xi1Hi2ρi1+1[xi(+)ρi=0]Hi2ρi1)

其中 x i x_i xi ρ i \rho_i ρi分别为 x x x ρ \rho ρ的第 i i i个bit,而 G i G_i Gi为randomly sampled generators of G G G ( + ) (+) (+)为bitwise XOR operation。附加 P P P变量来实现demasking操作。

定义 ( F p 2 ) k (F_{p^2})^k (Fp2)k内的group variable Q = ( Q x , Q y ) , g i = ( g x i , g y i ) Q=(Q_x,Q_y), g_i=(g^i_x,g^i_y) Q=(Qx,Qy),gi=(gxi,gyi) 以及 F p k F_{p}^k Fpk内布尔变量 z z z,执行如下evaluations:

  • 对于 2 2 2-bit lookup,for i ∈ [ k ] i\in [k] i[k],设置 g i = g_i= gi=
    • H i − 1 H_i^{-1} Hi1 if ρ i = 0 \rho_i=0 ρi=0 and x i = 0 x_i=0 xi=0
    • H i H_i Hi if ρ i = 1 \rho_i=1 ρi=1 and x i = 1 x_i=1 xi=1
    • G i ∗ H i − 1 G_i * H_i^{-1} GiHi1 if ρ i = 1 \rho_i=1 ρi=1 and x i = 0 x_i=0 xi=0
    • G i − 1 ∗ H i G_i^{-1} * H_i Gi1Hi if ρ i = 0 \rho_i=0 ρi=0 and x i = 1 x_i=1 xi=1
  • Q 0 = P Q_0=P Q0=P and Q i = Q i − 1 ∗ g i Q_i=Q_{i-1} * g_i Qi=Qi1gi

这需要 k k k Edwards multiplications (6 constraints each),且需要a 2 2 2-bit lookup for each of the g i g_i gi (2 constraints each) in addition to k k k booleanity checks。

具体见PedersenCRHGadget中的precomputed_base_scalar_mul_masked

5.2.3 Pedersen Hash Gadget

Aleo instantiate a circuit verifying M M M evaluations of H G H^G HG using circuit for H mask G , H H_{\text{mask}}^{G,H} HmaskG,H and H sym H H_{\text{sym}^H} HsymH over G G G。注意,这些变量在 F p F_p Fp内,而 ( z x , z y ) (z_x,z_y) (zx,zy)变量在 F p 2 F_{p^2} Fp2域,可解析为elliptic curve point in G G G
假设 G G G中的 G i , H i G_i,H_i Gi,Hi已预计算,可作为constant被访问。

  • 1)Inputs:
    k k k-length masked evaluation of M M M Pedersen hashes的输入为:

    • for i ∈ [ M ] i\in[M] i[M],布尔变量 x i = { x 1 i , ⋯   , x k i } x^i=\{x^i_1,\cdots,x^i_k\} xi={x1i,,xki}
    • boolean seed ρ ∈ { 0 , 1 } k \rho\in \{0,1\}^k ρ{0,1}k为a subset of F p k F^k_p Fpk
  • 2)Evaluation:

    • 设置 z ← H sym H ( ρ ) z\leftarrow H_{\text{sym}}^{H}(\rho) zHsymH(ρ)
    • for i ∈ [ M ] i\in [M] i[M],设置 ( o x i , o y i ) = H mask G , H ( ρ , x i , z ) (o^i_x,o^i_y)=H_{\text{mask}}^{G,H}(\rho,x^i,z) (oxi,oyi)=HmaskG,H(ρ,xi,z)
  • 3)Output:
    The k / 2 k/2 k/2 length set of variables { o x 1 , ⋯   , o x k } \{o^1_x,\cdots,o^k_x\} {ox1,,oxk} in ( F p ) k (F_p)^k (Fp)k as the truncated outputs。

5.2.4 实例化

Aleo中的Pedersen Primitives采用BLS12-377作为底层group,相应的output length(point压缩格式)为 256 + 1 = 257 256+1=257 256+1=257,Aleo 将其truncate为 256 256 256 bits。基于的安全假设为ECDLP,相应的security level 为 λ ∼ = 128 \lambda\sim=128 λ=128 bits。
input length k = 512 k=512 k=512 bits。

5.3 PoSW Circuit

PoSW tree Tree H ( q ) \text{Tree}_H(q) TreeH(q)的叶子为:subroots of the state tree’s q q q-depth nodes。
PoSW tree Tree H ( q ) \text{Tree}_H(q) TreeH(q)使用 k k k-bit Pedersen hash gadget 和 seed ρ \rho ρ 来计算root state i \text{state}_i statei
seed 参数 ρ = P R F ( s t a t e i ∣ ∣ n ) \rho=PRF(state_i||n) ρ=PRF(statein)为伪随机函数 P R F PRF PRF的输出,输入为nonce n n n 和 tree root。

5.3.1 Seed Generation

在每个Predicate 生成seed的流程为:
1)已知输入:nonce n ∈ { 0 , 1 } 256 n\in \{0,1\}^{256} n{0,1}256 stae i ∈ { 0 , 1 } 256 \text{stae}_i\in \{0,1\}^{256} staei{0,1}256,输出 ρ 0 ∈ { 0 , 1 } 256 \rho_0\in \{0,1\}^{256} ρ0{0,1}256 as ρ 0 = B L A K E ( n ∣ ∣ state i ) \rho_0=BLAKE(n||\text{state}_i) ρ0=BLAKE(nstatei),其中 ∣ ∣ || 表示string拼接。
2)若 ρ 0 \rho_0 ρ0的第 i i i个bit ρ 0 , i \rho_{0,i} ρ0,i 0 0 0 1 1 1,设置 ρ \rho ρ的第 ( 2 i − 1 ) (2i-1) (2i1)或第 2 i 2i 2i个bit分别为 10 10 10 01 01 01。使得 ρ ∈ { 0 , 1 } 512 \rho\in\{0,1\}^{512} ρ{0,1}512具有constant Hamming distance 256 256 256

这些都是在circuit之外完成的。且需要input format for every valid instance。

5.3.2 Circuit Size

5.3.2.1 Statement-Witness Definition

a valid statement ϕ = < state i , n > ∈ { 0 , 1 } 512 \phi=<\text{state}_i,n>\in\{0,1\}^{512} ϕ=<statei,n>{0,1}512 为 a subset of F p 512 F_p^{512} Fp512,其中:
1) state i ∈ { 0 , 1 } 256 \text{state}_i\in\{0,1\}^{256} statei{0,1}256 为bitwise representation of the PoSW root node of the updated state variable。
2) n ∈ { 0 , 1 } 256 n\in\{0,1\}^{256} n{0,1}256 为the bitwise representation of the nonce。

以上statement的witness w w w包含:

  • 1)A boolean representation of ρ ∈ { 0 , 1 } 512 \rho\in \{0,1\}^{512} ρ{0,1}512
  • 2)The subroot leaves { x i } i = 1 2 q ∈ { 0 , 1 } 512 \{x_i\}_{i=1}^{2^q}\in\{0,1\}^{512} {xi}i=12q{0,1}512 corresponding to state i \text{state}_i statei
  • 3)Boolean representations of the intermediate node values of Tree H ( q ) \text{Tree}_H(q) TreeH(q)

5.3.2.2 Evaluations

对于root state i \text{state}_i statei Tree H ( q ) \text{Tree}_H(q) TreeH(q)的所有内部nodes,运行a computation of the H H H gadget with the node value as output and its children as inputs。

PoSW circuit会验证 Tree H ( q ) \text{Tree}_H(q) TreeH(q) 正确生成的。需要的计算量为 2 q − 1 + 1 2^{q-1}+1 2q1+1 instances of H H H

6. Aleo的mining流程

PoSW共识中的mining算法为:modular exponentiation over some group G G G
R R R来表示代表PoSW circuit的relation,NIZK ( G , P , V ) (G,P,V) (G,P,V),生成common reference string C R S = G ( R ) CRS=G(R) CRS=G(R)
兴趣点在于为 P P P定义一种算法,该算法具有a size S S S precomputation string that minimizes the number of multiplications performed in G G G

6.1 Modular Multiexponentiation

PoSW将PoW process reduce为 the hardness of exponentiation,需要计算 q q q instances of exponentiating k k k random indices x i , j x_{i,j} xi,j in Z p Z_p Zp ( i , j ) ∈ [ q ] × [ k ] (i,j)\in[q]\times [k] (i,j)[q]×[k] for prime p p p of size n = l o g ( p ) n=log(p) n=log(p) by some random bases G i G_i Gi in G G G
MultiExp ( G 1 , . . . , G k , x 1 , . . . , x q ) = ( ∏ i = 1.. k G i x 1 , i , . . . , ∏ i = 1.. k G i x q , i ) \text{MultiExp}({G_1, ..., G_k}, {x_1, ..., x_q}) = (∏_{i = 1..k} G_i^{x_{1,i}}, ..., ∏_{i = 1..k} G_i^{x_{q,i}}) MultiExp(G1,...,Gk,x1,...,xq)=(i=1..kGix1,i,...,i=1..kGixq,i)

算法 A = ( A 1 , A 2 ) A=(A_1,A_2) A=(A1,A2)分为2个阶段:

  • 1) A 1 A_1 A1:precompute a string of S S S group elements in G G G from the common reference string S R S = { G 1 , ⋯   , G k } SRS=\{G_1,\cdots,G_k\} SRS={G1,,Gk}
  • 2) A 2 A_2 A2:输入有 q q q sets of k k k elements in Z p Z_p Zp,输出为 q q q outputs { π 1 , ⋯   , π q } \{\pi_1,\cdots,\pi_q\} {π1,,πq}

对于每个bases G i G_i Gi,计算 S / k S/k S/k exponents,并将其存入precomputation string中。这些exponents为the radix decomposition bases for Z p Z_p Zp at the maximal permissible depth c c c
平均来说,每个index最多需要 n / ( 3 + l o g ( S ) − l o g ( k ) − l o g ( n ) ) n/(3+log(S)-log(k)-log(n)) n/(3+log(S)log(k)log(n))次multiplications for a total of q ∗ k ∗ n / ( l o g ( S ) − l o g ( k ) − l o g ( n ) ) q*k*n/(log(S)-log(k)-log(n)) qkn/(log(S)log(k)log(n))。这意味着the size of the precomputation string s s s grows exponentially with a linear improvement in proving time。

6.2 Security & Miner Size

对于具有 S = k ∗ ( n / c ) ∗ ( 2 c − 1 ) S=k*(n/c)*(2^c-1) S=k(n/c)(2c1)个group elements的precomputation table,每个exponentiation平均计算量为 n / c n/c n/c次multiplication。但是,某些point a maximal c ∗ c^* c is obtained that balances the communication cost of sending more precomputed elements with the cost of performing additional multiplications。因此,可假设miners work at around the level, and look at the security it implies。

Aleo评估了不同values of c ∈ N + c\in {N_+} cN+的proof生成时间。在constant block frequency场景下,可用于project what the minimal table size S S S is for a predicate involving k k k exponentiations to achieve sufficiently low quantization error and collision probability。

We fix S S S and k k k and investigate proof generation times for fixed table size. Proving times in the GM17 and Marlin provers alongside the corresponding quantization error and collision probabilities are provided below for a single-threaded desktop machine. Security is with respect to 1 minute blocks and a circuit with k ≈ 2 13 k\approx 2^{13} k213 exponentiations per proof.

Proof SystemProof Generation Time (s)Quantization Error (%)Collision Probability (%)
Marlin4.653.823.87
GM170.910.7580.76

6.2.1 Security Implications of Hardware Acceleartion

采用硬件加速的miner的proof生成时间将大幅缩短,因此,更多更快的miner将有助于降低quantization error和collision probabilities。也有助于网络更安全的运行。

7. PoSW 实例化

Aleo的PoSW中的proof system采用的Marlin架构。Marlin架构与non-interactive Random Oracle setting下的属性一致。

7.1 Simulation Extractability

simulation-extractable (SE) proof system 具有 a unique encoding for every valid instance-witness pair ⟨ ϕ , w ⟩ \langle \phi, w\rangle ϕ,w。即意味着valid proofs cannot be rerandomized without explicit knowledge of a different witness for ϕ \phi ϕ。否则an adversarial prover would be able to change the encoding of a proof after computation until it satisfies difficulty, which would violate the non-amortization requirement。

7.2 Reduction to an Average-Case Hard Problem

A non-amortizable prover should reduce in difficulty to a problem known (or postulated) to be non-batchable (or ‘hard’) on average。

由于当前大多数proof system采用的都是Kate commitment。因此Aleo中致力于 reduce proof computation to the problem of multi-exponentiation of a set of given (random) bases G i i = 1 m ∈ G m {G_i}_{i = 1}^m \in \mathbb{G}^m Gii=1mGm by a set of random indices x i i = 1 m ∈ Z p m {x_i}_{i =1}^m \in \mathbb{Z}_p^m xii=1mZpm。此时,hardness is measured in the number of queries to a multiplication oracle O m \mathcal{O}_m Om in the given group’s encoding。
尽管该问题在unbounded space下并 non-amortizable的,但是,miners具有fixed size precomputation string,可认为其是non-amortizable的。

7.3 Predicate Design

predicate的选择对于确保以上security也至关重要。
R \mathcal{R} R relation应满足如下属性:

  • 1)Usefulness:The proof is a proof of knowledge for a statement providing inherent value to the protocol. We opt for a relation that verifies the inclusion of a set of transactions in the given block.
  • 2)Computational Uniqueness:An adversary cannot find a new witness w 2 w_2 w2 for ϕ \phi ϕ given knowledge of a valid instance-witness pair ⟨ ϕ , w ⟩ \langle \phi, w\rangle ϕ,w. This ensures that the miner cannot resample witnesses for ϕ \phi ϕ to reduce computational burden.
  • 3)Non-Amortization:Valid witnesses for R \mathcal{R} R need to “look” sufficiently random to reduce to the average-case hardness of multiexponentiation. The chosen predicate achieves ϵ = 0 \epsilon = 0 ϵ=0 (or perfect) non-amortization in this context.

7.4 Error Bounds

We set the desirable error bounds for quantization and forking error to 3 % 3\% 3% and 1.5 % 1.5\% 1.5% respectively. For a protocol with 1 1 1-minute block times, this implies that average proof generation times need to be upper bounded by τ = 1.8 ≈ 2 \tau = 1.8 \approx 2 τ=1.82 seconds.

8. PoSW并行化

PoSW circuit支持并行化 in each of the bases that need to be exponentiated。即意味着使用并行硬件可降低proving time,也意味着更高的chain security。但是带来的问题是需要能支持large parallel computing instances的larger miners。
若底层circuit computation为inherently sequential的,则可实现Verifiable Delay Function(VDF)。

8.1 Recursion

Recursion computation可将PoSW circuit转换为sequential computation。将circuit切分为sequential proofs that ‘pass’ an intermediate set of witnesses through many sub-circuit:
每个仅需运行一小部分计算。

通过recursion,每个proof都是下一proof的输入,让subcircuit足够小,将保证最终生成的proof为几乎sequential。

8.2 Towards a VDF Construction

尽管当前的设计倾向于non-parallelizabilit,这将带来high efficiency costs due to the requirement for recursive computation。

但是,需要设计a parallelizable instance,使得可开发相应的硬件,来提供有意义的security guarantee(low collision probability due to lower proof generation times)。
随着硬件和密码学优化,recursive composition就足够了,整个协议可简单过渡为a state where the underlying proof generation is inherently sequential。

参考资料

[1] Aloe Proof of Succinct Work
[2] Incentivized Testnet Announcement
[3] Aleo 共识
[4] Aleo Mining Process
[5] Aleo PoSW并行化

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/mutourend/article/details/121819105

使用Zexe构建Aleo隐私应用——How Zero Knowledge is Rebalancing the Scales of the Internet-爱代码爱编程

1. 数据所有权的革命 十年前,人们难以想象互联网将延伸至人类生活的哪些方面;而当今,人类的大多数经济和社交活动均发生在网络上。 网络带来的好处在COVID-19大流行期间尤其明显: 以前不依赖于网络的生意,为了生存,也开始通过网络来获客;地理上隔离的人们也可以通过网络来保持联系。人类生活高度依赖网络将产生指数量级增长的大量数据。基于这些大数据进行分析

欢迎关注Aleo-爱代码爱编程

1. 引言 Aleo的诞生源于实现一种不可能的愿望——在网络上建立一种真正个人(truly personal)和真正私人(truly private)的用户体验。 Aleo是第一个提供完全私有应用程序的平台: 借助分布式系统和零知识密码学来保护web上的用户数据。在Aleo的核心层,为用户和应用开发者提供了无限计算和绝对隐私。Aleo的底层架构为默认

Aleo系列博客——透明的代价-爱代码爱编程

1. 引言 这是Aleo的一组系列博客,旨在探索当今数字世界隐私的演变和价值,以及零知识技术为每个人提供公平竞争环境的机会。 前序博客参见:使用Zexe构建Aleo隐私应用——How Zero Knowledge is Rebalancing the Scales of the Internet 区块链技术设计之初,就默认为透明的。这种架构与当今的w

Aleo系列博客——零知识密码学技术的未来-爱代码爱编程

1. 引言 Aleo系列,前序博客有: 欢迎关注Aleo使用Zexe构建Aleo隐私应用——How Zero Knowledge is Rebalancing the Scales of the InternetAleo系列博客——透明的代价这系列文章探讨了当今数字世界隐私的演变和价值,以及零知识技术为公平竞争提供的机会。 2. 隐私 是 Web3中

Aleo 提供的zero knowledge primitives-爱代码爱编程

1. 引言 Aleo系列,前序博客有: 欢迎关注Aleo使用Zexe构建Aleo隐私应用——How Zero Knowledge is Rebalancing the Scales of the InternetAleo系列博客——透明的代价Aleo系列博客——零知识密码学技术的未来Aleo为Web3生态系统中的任意隐私、可编程应用提供了核心组件。

Aleo提供的zkCloud:去中心化隐私计算-爱代码爱编程

1. 引言 Aleo系列,前序博客有: 欢迎关注Aleo使用Zexe构建Aleo隐私应用——How Zero Knowledge is Rebalancing the Scales of the InternetAleo系列博客——透明的代价Aleo系列博客——零知识密码学技术的未来Aleo 提供的zero knowledge primitives在

ETH 增发量将减少 8 倍?合并之后能否迎来通缩?| Eth2 AMA 第六期-爱代码爱编程

来源:Reddit 编辑:南风   6 月 23 日,以太坊开发者们在 Reddit 的 r/Ethereum 板块举行了第六期 Eth2 AMA 线上问答活动,以太坊联合创始人 Vitalik Buterin 以及以太坊基金会的 Justin Drake、Danny Ryan、Dankrad Feist 等人回答了以太坊社区的提问。本

Aleo Wagyu钱包-爱代码爱编程

1. 引言 Aleo系列,前序博客有: 欢迎关注Aleo使用Zexe构建Aleo隐私应用——How Zero Knowledge is Rebalancing the Scales of the InternetAleo系列博客——透明的代价Aleo系列博客——零知识密码学技术的未来Aleo 提供的zero knowledge primitivesAl

介绍 新项目Aleo 的功能赏金-爱代码爱编程

 编辑 搜图 赠款计划更新 今年六月,他们的核心团队宣布了 Aleo 社区资助计划的第一次迭代。他们的目的是为社区成员提供为 Aleo 开源生态系统做出贡献的机会,并实现他们为网络上的每个人创造私人和个人体验的愿景。 自该计划启动以来,他们收到了许多申请,并批准了一些申请。在接下来的几个月里,他们将与他们的受资助者密切合作,构建项目并创建展示 A