[SOLVED] CSCI-GA 3033-107 Cryptography of Blockchains Spring 2024 Homework 2

CSCI-GA.3033-107: Cryptography of Blockchains

Spring 2024

Homework #2

Due: 11:59pm on Sunday, 3/10, 2024

Submit via Brightspace

Problem 1. Distributed Randomness Beacons using VDFs. A distributed randomness beacon

(DRB) allows mutually untrusted parties to engage in a protocol and derive a random value ω that

cannot be biased by any party. Consider the verifiable delay function VDF(x) : G → G = x2t

where (G, ·) is a multiplicative group of unknown order. Let g be a generator of G and let

h = VDF(g). Consider the following one-round protocol DRB1:

Round 1: Each party reveals a random value ri.

Suppose n parties participate in Round 1. The DRB output is obtained as ω = (
!

n

i=1

ri)2t
∈ G.

a. Show that this protocol is not secure and can be biased. That is, describe an attack an

adversary acting as of the parties can perform. that lets them set the DRB output to any

value they want. (Note the adversary can get preparation time before the protocol starts.)

b. Suggest a solution to this attack based on the solution used to prevent the rogue-key attack

when aggregating BLS signatures. (You need not prove your answer. A brief justification is

enough.)

An issue with the VDF-based DRBs is that they always require a costly VDF computation

to be done. Consider the following protocol DRB2:

Round 1: Commit Round: Each party i samples a random nonce αi and shares ci = gαi .

Round 2: Reveal Round: After all parties share their commitments, each party reveals αi. (If

ci = gαi then this αi is ignored by the other parties).

Suppose n parties participate in Round 1. There are two scenarios here, based on the behavior.

of the n parties in Round 2. The optimistic scenario allows all the parties to compute the

output quickly while the pessimistic one resorts to the costly VDF computation.

• Optimistic case: If all n parties reveal a valid nonce in Round 2, then the DRB output

ω is quickly obtained as ω = !

n

i=1

hαi .

• Pessimistic case: If any party skips Round 2, then the DRB output is obtained by the

others as ω = VDF(
!

n

i=1

ci).

(You may verify that the randomness obtained in the two cases is the same.)

c. This scheme also suffers from a biasing attack similar to the one in part (a). Show how.

d. As in part (b), write out a solution that prevents the above attack. (Again, it’s based on the

technique used in BLS signature aggregation. And you need not formally prove security.)

e. Even after this fix, there is an inherent weakness associated with any DRB that has an

“optimistic” fast case and a “pessimistic” slow case. Show how one party participating in the

protocol can learn ω much faster than all the other parties. (Note that they don’t bias the

value. They only learn it much faster than the others.)

1Problem 2. More VDFs

a. Is Proof-of-Work a VDF? Why or why not? If it is, describe the VDF input, output, and

prove and verify functions. If not, describe what property of a VDF is not satisfied.

b. Can a VDF be used as a Proof-of-Work function? For a given challenge ch, the goal of the

miner to now produce a valid output and proof for a given VDF function on input ch.

c. A commonly used randomness beacon is the Bitcoin blockchain. Suppose random value r

is obtained by hashing the latest block header b as r = H(b). What is one issue with this

method? (Hint: think about which parties can bias the randomness.)

d. What if the randomness is obtained by hashing the VDF output on the header, instead? That

is, r = H(VDF(b)). Briefly explain (doesn’t have to be formal) how this is secure or insecure.

Problem 3. Certificates of Correctness

In class, we so far have seen ways to obtain quorum certificates where each signature has equal

weight. What if we want to extend this to a scenario where different nodes have different weights?

This may be the scenario in a Proof-of-Stake blockchain where the more stake you have, the more

your vote counts. Instead of needing 2/3rd of all miners for a quorum, you need 2/3rd of all the

weight (that is, stake).

a. Let node i have weight wi for i = 1, . . . , n. Modify the Merkle tree construction for QC to

show that some fraction x of all stake is in the quorum. Hint: Assume the total stake is

T = ”

n

i=1

wi. The Merkle tree should enable the verifier to query a value q between 0 and T

and the prover returns the leaf wi
′
, such that ”

i

′

−1

i

=1

wi < q and ”

i

′

i

=1

wi >= q. The Merkle

tree needs to track more information than just the hashes in order to do this.

Problem 4. Security of Wesolowski VDF

This question will analyze the role of the prime challenge ℓ in Wesolowski VDFs. To establish

notation, the input is (G, g, h,t), w here g, h ∈ G and the prover claim is that h = g2t
. The

verifier sends a challenge ℓ, which is a prime. The prover responds π where π = gq and 2t = qℓ+r

and r < ℓ. The

a. Show that the scheme isn’t secure when ℓ ≈ 2λ is the product of small primes each less than

k (for some constant k), by describing an attack that runs in time O(k · λ) group operations.

Problem 5. Batching Polynomial Commitments

In this question, we’ll build and efficient batch evaluation proofs from a linearly homomor

phic polynomial commitment scheme. Here, a prover P and verifier V have input polynomials

f0, . . . , fℓ−1 ∈ F<d[X]. The prover claims that fi(ωi) = 0 for all i = 0, . . . , ℓ − 1 and elements

ω0, . . . , ωℓ−1. The interactive protocol with a non-succinct verifier to prove the following is:

1. V sends P a challenge ρ ∈ F.

2. P sends V the polynomial q(X) = ”

ℓ

i=
−
0
1

ρi
fi(X)/(X − ωi).

3. V sends P a challenge r ∈ F.

24. Let z(X) = !

ℓ

i=
−
0
1

(X − ωi) and zi(X) = z(X)/(X − ωi). V computes the polynomials

g(X) = #”

ℓ

i=
−
0
1

ρi
zi(r) · fi(X)
$
− z(r) · q(X)

5. V accepts if g(r) = 0.

The verifier can be made succinct using polynomial commitments. In this setting, the input

additionally contains commitments C0, . . . , Cℓ−1 to the polynomials f0, . . . , fℓ−1. In the questions

below, you will work out how the steps change when using polynomial commitment schemes.

a. In step 2 above, the prover will send a commitment Cq to polynomial q(X). Using Cq and

all other inputs and challenges, show how the verifier can compute a commitment Cg to

polynomial g(X) in Step 4 efficiently.

b. How does step 5 change when using polynomial commitments? (Note the succinct verifier

only has commitment to q(X) and g(X).)

We’ll generalize the protocol to prove the claim fi(ω) = vi for i = 0, . . . , ℓ − 1.

c. What is the new q in this scenario? And how does V compute Cg(X)? Short one-line answers

are sufficient. (Hint: reduce this to the original case by modifying the polynomials sent as

input.)

3