0xArsi

ZKHack IV - Supervillian Puzzle Writeup

Objective

Suppose we have $n$ honest validators in a network, and each has their own public key and proof-of-key. This data is given in the file the puzzle reads from. For simplicity, we denote the $i$-th public key by $k_i$ and the $i$-th proof by $p_i$. We would like to create a new_key and new_proof such that:

pok_verify(new_key, new_key_index, new_proof) passes

bls_verify(aggregate_key, aggregate_signature, message) passes

where new_key, new_proof and message are the only variables in our control, and aggregate_key and aggregate_signature are the respective "sums" of all the keys / signatures involved, including our own. One can interpret new_key as a rogue key (denoted by $k_{n+1}$) which has the following traits: