1 of 52

Distributed Randomness from Weighted VRFs

* paper: https://eprint.iacr.org/2024/198

Science of Blockchain Conference

Wednesday, August 7th, 2024

Alin Tomescu

Aptos Labs�@alinush407

Sourav Das

UIUC�@sourav1547

Benny Pinkas

Aptos Labs�@bennypinkas

Daniel Xiang

Aptos Labs�@XiangZhuolun

verifiable random functions

2 of 52

tl;dr

PoS randomness beacon, on Aptos

On-chain randomness APIs (a.k.a., "precompiles")

e.g., uint random(uint min, uint max) [Tom24]
instant & cheap!

unbiasable & unpredictable under PoS assumption
via weighted VRF, PVSS, & NI-DKG for 𝔾 SKs

2

3 of 52

(1) Why might you care?

3

Academics:

PVSS for 𝔾 SKs

11x faster than SCRAPE [CD17]

Weighted VRF with O(1) share size

Circumvents lower bounds [BTW05]

Extensible to weighted threshold decryption & more

Practitioners:

Shorter & ~faster weighted VRFs

Alternative to weighted BLS

Fastest NI-DKG for 𝔾 SKs

Simpler to implement & debug

(PV, agg. & no complaints phase)

Compatible with:

[GJM+21] threshold VRF
Threshold decryption [Elga85]

4 of 52

(2) Why might you care? Randomness is powerful 💪!

🔗 Dapps

Games
Raffles
NFT minting

🕸️ Consensus

Asynchrony [FLP85]
Fair leader election
MEV mitigation

🤐 Privacy

Interactively-verify ZKPs
Key (co)generation
Time-locked encryption [GMR23]
Keyless accounts [AIP61]

4

5 of 52

Outline

Background

Randomness from VRFs
Weighted DKGs
t-out-of-n (unweighted) PVSS ⇒ DKG

5

6 of 52

Outline

Background

Randomness from VRFs
Weighted DKGs
t-out-of-n (unweighted) PVSS ⇒ DKG

Our (un)weighted PVSS
Our weighted VRF
Deployment on Aptos

6

7 of 52

Randomness from VRFs

7

e.g., VRF(sk, m) = H(m)^sk

r₇ =

VRF(sk, 7)

block 7

block 1337

block 8

r₈ =

VRF(sk, 8)

r₁₃₃₇ =

VRF(sk, 1337)

Q: Who knows sk?

8 of 52

Weighted distributed key generation (DKG)

8

∀ subset S with >66% stake,

sk = Reconstruct((sk_i)_i_∈_S)

v₁ = VRF(sk₁, m)

v₂ = VRF(sk₂, m)

v₃ = VRF(sk₃, m)

v₃ = VRF(sk₄, m)

secret key share

DKG of sk

9 of 52

Weighted distributed key generation (DKG)

9

v₁ = VRF(sk₁, m)

v₂ = VRF(sk₂, m)

v₃ = VRF(sk₃, m)

v₃ = VRF(sk₄, m)

DKG of sk

10 of 52

Weighted verifiable random function (VRF)

10

v₁ = VRF(sk₁, m)

v₂ = VRF(sk₂, m)

v₃ = VRF(sk₃, m)

v₃ = VRF(sk₄, m)

r_m = VRF(sk, m)

11 of 52

Weighted verifiable random function (VRF)

11

∀ subset S with >66% stake,

r_m = Reconstruct((v_i)_i∈_S)

v₁ = VRF(sk₁, m)

v₂ = VRF(sk₂, m)

v₃ = VRF(sk₃, m)

v₄ = VRF(sk₄, m)

VRF share

r_m = VRF(sk, m)

12 of 52

The road so far

Background

Randomness from VRFs
Weighted DKGs
t-out-of-n "unweighted" PVSS ⇒ DKG

Our (un)weighted PVSS
Our weighted VRF
Deployment on Aptos

12

13 of 52

t-out-of-n "unweighted" PVSS of a secret s

PVSS.Deal(s, t, ek₁, …, ek_n) → trx ⋍ [ Enc(ek_i, s_i) ]_i_∈[_n_]

PVSS.Verify(trx, t, ek₁, …, ek_n) → {0, 1}

PVSS.Aggregate(trx₁, trx₂) → trx_1,2

Public key infrastructure (PKI):

decryption key dk_i

encryption key

13

∀ subset S of size > t,

s = Reconstruct((s_i)_i_∈_S)

trx_1,2 "deals" s₁ + s₂

trx "deals" s

14 of 52

t-out-of-n "unweighted" DKG from PVSS

1. Every validator i:

picks random z_i
trx_i ← PVSS.Deal(z_i, t, ek₁, …, ek_n)

2. Q = subset of >t validators who dealt correctly

identified via PVSS.Verify

3. trx = PVSS.Aggregate({ trx_i}_i_∈_Q)

⇒ trx deals sk = ∑_i_∈_Q z_i

14

1. No subset of ≤ t can reconstruct sk

2. Only subsets of > t can reconstruct sk

15 of 52

The road so far

Background

Randomness from VRFs
Weighted DKGs
t-out-of-n (unweighted) PVSS ⇒ DKG

Our (un)weighted PVSS
Our weighted VRF
Deployment on Aptos

15

16 of 52

Cryptographic preliminaries

Type-3 pairing:

Public parameters:

16

17 of 52

Our t-out-of-n "unweighted" PVSS

17

PVSS.Deal(a₀, t, ek₁, …, ek_n) → trx

define deg-t polynomial s.t. p(0) = a₀

commit to shares

encrypt shares

the shared secret is

* t = 548 out of n = 821, consistent with initial weighted deployment on Aptos

288 ms (↑1.65x)

154 KiB (↑1.34x) & aggregatable

18 of 52

Our t-out-of-n "unweighted" PVSS

18

4

2

3

PVSS.Verify(trx, t, ek₁, …, ek_n) → {0, 1}

1

[CD17]

[Grot21]

19 of 52

Our t-out-of-n "unweighted" PVSS

19

PVSS.Verify!(trx, t, ek₁, …, ek_n) → {0, 1}

1

3

* t = 548 out of n = 821, consistent with initial weighted deployment on Aptos

21.4 ms (↓11x)

2

20 of 52

Weighted PVSS via virtualization

20

Lagrange coefficients

∀ subset S of weight > t,

sk = Reconstruct((sk_i)_i∈_S)

threshold weight t,

total weight n = ∑_i w_i

(e.g., w = [ 3, 2, 1, 2 ], n = 8)

h^p(¹⁾	h^p(²⁾	h^p(³⁾	h^p(⁴⁾	h^p(⁵⁾	h^p(⁶⁾	h^p(⁷⁾	h^p(⁸⁾
sk₁_,0	sk₁_,1	sk₁_,2	sk₂_,0	sk₂_,1	sk₃_,0	sk₄_,0	sk₄_,1

21 of 52

The road so far

Background

Randomness from VRFs
Weighted DKGs
t-out-of-n (unweighted) PVSS ⇒ DKG

Our (un)weighted PVSS
Our weighted VRF
Deployment on Aptos

21

22 of 52

Our weighted VRF

22

the final VRF

23 of 52

Our weighted VRF

23

the final VRF

post-DKG local keygen

O(1)-sized VRF share

Verifies against

📢 broadcast

24 of 52

Performance of our weighted VRF

N = 112 validators

threshold weight t = 548

total weight n = 821*

24

	Weighted BLS [BLS01]	Ours

* initial weight distributions from Aptos mainnet

The average case

25 of 52

Performance of our weighted VRF

N = 112 validators

threshold weight t = 548

total weight n = 821*

25

	Weighted BLS [BLS01]	Ours
Share signign time	590 μs	290 μs (↓2x)

* initial weight distributions from Aptos mainnet

+ spreadsheet here

The average case

26 of 52

Performance of our weighted VRF

N = 112 validators

threshold weight t = 548

total weight n = 821*

26

	Weighted BLS [BLS01]	Ours
Share signign time	590 μs	290 μs (↓2x)
Share verification time	1,760 μs	870 μs (↓2x)

* initial weight distributions from Aptos mainnet

+ spreadsheet here

The average case

27 of 52

Performance of our weighted VRF

N = 112 validators

threshold weight t = 548

total weight n = 821*

27

	Weighted BLS [BLS01]	Ours
Share signign time	590 μs	290 μs (↓2x)
Share verification time	1,760 μs	870 μs (↓2x)
Share size	352 bytes	96 bytes(↓3.67x)

* initial weight distributions from Aptos mainnet

+ spreadsheet here

The average case

28 of 52

Performance of our weighted VRF

N = 112 validators

threshold weight t = 548

total weight n = 821*

28

	Weighted BLS [BLS01]	Ours
Share signign time	590 μs	290 μs (↓2x)
Share verification time	1,760 μs	870 μs (↓2x)
Share size	352 bytes	96 bytes(↓3.67x)
Aggregation time	4.6 ms	43.5 ms (↓9.4x)

* initial weight distributions from Aptos mainnet

+ spreadsheet here

The average case

29 of 52

Performance of our weighted VRF

N = 112 validators

threshold weight t = 548

total weight n = 821*

29

	Weighted BLS [BLS01]	Ours
Share signign time	590 μs	290 μs (↓2x)
Share verification time	1,760 μs	870 μs (↓2x)
Share size	352 bytes	96 bytes(↓3.67x)
Aggregation time	4.6 ms	43.5 ms (↓9.4x)
End-to-end time	137 ms	108 ms (↓1.26x)

The average case

* initial weight distributions from Aptos mainnet

+ spreadsheet here; screenshotted here

Dominates end-to-end time

30 of 52

The road so far

Background

Randomness from VRFs
Weighted DKGs
t-out-of-n (unweighted) PVSS ⇒ DKG

Our (un)weighted PVSS
Our weighted VRF
Deployment on Aptos

30

31 of 52

Randomness on Aptos mainnet 🚀

31

# of randomness TXNs	520,141

Deployed on June 2024
A first: PoS randomness that is (1) unbiasable, (2) unpredictable & (3) as fast as the network

32 of 52

Randomness on Aptos mainnet 🚀

32

# of randomness TXNs	520,141
DKG duration	20 sec

Deployed on June 2024
A first: PoS randomness that is (1) unbiasable, (2) unpredictable & (3) as fast as the network

33 of 52

Randomness on Aptos mainnet 🚀

33

# of randomness TXNs	520,141
DKG duration	20 sec
Randomness latency	160 ms

↓6.4x to 25 ms since [DPTX24]

Deployed on June 2024
A first: PoS randomness that is (1) unbiasable, (2) unpredictable & (3) as fast as the network

34 of 52

Conclusion: "What can switching to 𝔾 SKs do for you?"

34

🤲 PVSS for 𝔾 SKs

🚀 Aptos randomness

🎲 O(1) weighted VRFs

Open source

Deployed on mainnet

Fastest aggregatable PVSS to date

Theoretically-surprising & practically-useful

https://github.com/aptos-labs/aptos-core

35 of 52

Acknowledgements

Sasha Spiegelman, for randomness idea
Zhoujun Ma and Zekun Li, for engineering
Dan Boneh, for help with security analysis and general advice
Aptos Labs team, for production readiness and deployment

35

36 of 52

Did not get to discuss

36

Details

Efficiently rounding from large stakes to small weights
Limitation: Aggregated VRF is not publicly-verifiable against the DKG PK
Weighted VRFs through the lens of functional encryption
Future work: More efficiently reusing EKs in our unweighted PVSS
SCRAPE low degree test [CD17]
Undergasing attacks on instant randomness
Mitigating against collusion attacks

37 of 52

"More! More! is the cry of a mistaken soul.

Less than All cannot satisfy Man."

William Blake

37

38 of 52

References

[AIP41] Move APIs for public randomness generation, Alin Tomescu; 2023

[AIP61] Keyless accounts (AIP-61), Alin Tomescu; 2024

[AIP79] Implementation of instant on-chain randomness (AIP-79), Alin Tomescu, Zhuolun "Daniel" Xiang, Zhoujun Ma; 2024

[BLS01] Short Signatures from the Weil Pairing; by Boneh, Dan and Lynn, Ben and Shacham, Hovav; in ASIACRYPT'01

[BTW05] Characterizing Ideal Weighted Threshold Secret Sharing; by Beimel, Amos and Tassa, Tamir and Weinreb, Enav; in TCC'05

[CD17] SCRAPE: Scalable Randomness Attested by Public Entities; by Cascudo, Ignacio and David, Bernardo; in ACNS'17

[CD20] ALBATROSS: publicly AttestabLe BATched Randomness based On Secret Sharing; by Ignacio Cascudo and Bernardo David;

[DPTX24] Distributed Randomness using Weighted VRFs; by Sourav Das and Benny Pinkas and Alin Tomescu and Zhuolun Xiang;

[Elga85] A public key cryptosystem and a signature scheme based on discrete logarithms; by Elgamal, T.; in IEEE Transactions on Information Theory; 1985

[FLP85] Impossibility of distributed consensus with one faulty process; by Michael J. Fischer and Nancy A. Lynch and Michael S. Paterson; in JACM'85;

[FS01] One Round Threshold Discrete-Log Key Generation without Private Channels; by Fouque, Pierre-Alain and Stern, Jacques; in PKC'01

[Grot21] Non-interactive distributed key generation and key resharing; by Jens Groth

[GJM+21] Aggregatable Distributed Key Generation; by Gurkan, Kobi; Jovanovic, Philipp; Maller, Mary; Meiklejohn, Sarah; Stern, Gilad; Tomescu, Alin; EUROCRYPT'21

[GMR23] tlock: Practical Timelock Encryption from Threshold BLS; by Nicolas Gailly, Kelsey Melissaris & Yolan Romailler

[MRV99] Verifiable random functions; by S. Micali and M. Rabin and S. Vadhan; in FOCS'99�[Stad96] Publicly Verifiable Secret Sharing; by Stadler, Markus; in EUROCRYPT'96

[Tom24] How to use on-chain randomness on Aptos; by Alin Tomescu, 2024

[XDL+24] The Latency Price of Threshold Cryptosystem in Blockchains; by Zhuolun Xiang, Sourav Das, Zekun Li, Zhoujun Ma & Alexander Spiegelman;

38

39 of 52

Appendix

39

40 of 52

PVSS without V in G₁

40

PVSS.Deal(a₀, t, ek₁, …, ek_n) → trx

the shared secret is

validator i's

secret share of sk:

∀ set S of size > t,

sk = Reconstr((sk_j)_j∈_S)

41 of 52

PVSS without V in G₁

41

PVSS.Verify(trx, ek₁, …, ek_n) → {0, 1}

1

2

3

✅trx is aggregatable

42 of 52

PVSS without V in G₁

42

PVSS.Verify(trx, ek₁, …, ek_n) → {0, 1}

3

2

1

43 of 52

Extra PVSS benchmarks

43

44 of 52

Performance of PVSS w/o V in G₁

t = 548, n = 821

44

	Unweighted PVSS w/o V in G₁
PVSS.Deal time	228 ms (↑1.3x)
PVSS.Verify time	17.9 ms (↓14x)
trx size	same
PVSS.Aggregate time	same

45 of 52

Weighted PVSS with reusable EKs performance

w = 548, W = 821, n = 112*

45

	Weighted PVSS w/ reusable EKs
PVSS.Deal time	464 ms (↑2.65x)
PVSS.Verify time	149 ms (↓1.68x)
trx size	269 KiB (↑2.34x)
PVSS.Aggregate time	3.89 ms (↑2.74x)

* weight distributions are from Aptos mainnet

46 of 52

Performance of our "unweighted" PVSS

t = 548 out of n = 821* PVSS

46

	SCRAPE [CD17]	Ours
PVSS.Deal time	175 ms	288 ms (↑1.65x)
PVSS.Verify time	251 ms	21.4 ms (↓11x)
trx transcript size	115 KiB	154 KiB (↑1.34x)
PVSS.Aggregate time	1.71 ms	2.18 ms (↑1.27x)

* t and n consistent with initial weighted deployment on Aptos

+ spreadsheet with data

+ implementation: https://github.com/aptos-labs/aptos-core/tree/main/crates/aptos-dkg

Dominates DKG cost!

May be lowered to ↑1.3x via AGM proof

May be avoidable via AGM proof

47 of 52

47

4

2

3

PVSS.Verify(trx, t, ek₁, …, ek_n) → {0, 1}

1

48 of 52

Weighted PVSS (via virtualization)

48

weighted PVSS:

total weight n

threshold weight t,

validator i: weight w_i

t-out-of-n PVSS

s_i is the starting index of validator i

Lagrange coefficients

∀ subset S of weight > t,

sk = Reconstr((sk_i)_i∈_S)

h^p(¹⁾	h^p(²⁾	h^p(³⁾	h^p(⁴⁾	h^p(⁵⁾	h^p(⁶⁾	h^p(⁷⁾	h^p(⁸⁾
sk₁_,0	sk₁_,1	sk₁_,2	sk₂_,0	sk₂_,1	sk₃_,0	sk₄_,0	sk₄_,1

49 of 52

Weighted BLS versus our wVRF

49

50 of 52

Staking on Aptos (as of March 2024)

About 880M tokens are staked
Validators and stake distribution change every epoch (2 hours)
Currently, 129 validators

14 have stake in the range 15M - 20M
43 have stake in the range 1M - 1.3M

50

* slide borrowed from Benny Pinkas's presentation on Aptos randomness

51 of 52

The randomness Move module

module aptos_std::randomness {

use std::vector;

/// Generates `n` bytes uniformly at random.

public fun bytes(n: u64): vector<u8> { /* ... */ }

/// Generates a number uniformly at random.

public fun u64_integer(): u64 { /* ... */ }

public fun u256_integer(): u256 { /* ... */ }

/// Generates a number $n \in [min_incl, max_excl)$ uniformly at random.

public fun u64_range(min_incl: u64, max_excl: u64): u64 { /* ... */ }

public fun u256_range(min_incl: u256, max_excl: u256): u256 { /* ... */ }

/// Generate a permutation of `[0, 1, ..., n-1]` uniformly at random.

public fun permutation(n: u64): vector<u64> { /* ... */ }

#[test_only]

/// Test-only function to set the entropy in the RNG to a specific value.

public fun set_seed(seed: vector<u8>) { /* ... */ }

}

51

Repeated calls will resample a new random outcome

52 of 52

Our weighted VRF from the lens of functional encryptional*

52

*https://en.wikipedia.org/wiki/Functional_encryption