代做CSCI-GA. 3033-107: Cryptography of Blockchains Spring 2024 Homework #2代做迭代

日期：2025-03-15 05:36

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