Note: you can read a slightly edited version at https://yannickseurin.github.io/crypto-book/zk-hack-puzzles/puzzle-13/puzzle-13.html
- puzzle page
- GitHub repository
- puzzle description:
Bob has been designing a new optimized signature scheme for his L1 based on BLS
signatures. Specifically, he wanted to be able to use the most efficient form
of BLS signature aggregation, where you just add the signatures together rather
than having to delinearize them. In order to do that, he designed a
proof-of-possession scheme based on the B-KEA assumption he found in the the
Sapling security analysis paper by Mary Maller [1]. Based the reasoning in the
Power of Proofs-of-Possession paper [2], he concluded that his scheme would be
secure. After he deployed the protocol, he found it was attacked and there was
a malicious block entered the system, fooling all the light nodes...
BLS aggregate signatures, proofs of possession, ... This should be interesting and quite relevant to Ethereum since the beacon chain uses BLS signature aggregation since the Merge. Let's take a look at the code.
The package directory is organized as follows:
puzzle-supervillain
├── Cargo.toml
├── public_keys.bin
└── src
└── main.rs
The code is pretty simpler than in most other puzzles.
Let's take a look at main.rs.
It first brings a number of items from arkworks crates into scope, in particular related to the BLS12-381 pairing-friendly curve.
Let us introduce straightaway some (standard) notation that will help us explain what's going on in this puzzle.
In all the following, we will let G1Affine
and G2Affine
respectively correspond to points in G1Affine::generator()
and
Function main
is also quite simple.
First, it creates a vector public_keys
of public key/proof pairs pok_verify
does in a moment, but the idea is that
let public_keys: Vec<(G1Affine, G2Affine)> = from_file("public_keys.bin");
public_keys
.iter()
.enumerate()
.for_each(|(i, (pk, proof))| pok_verify(*pk, i, *proof));
There are 9 public key/proofs pair in total. We can print these public keys and proofs if we want, although there's not much remarkable about them:
for (i, (pk, proof)) in public_keys.iter().enumerate() {
println!("public_keys[{}].pk: {}", i, pk);
println!("public_keys[{}].proof: {}\n", i, proof);
}
We get:
public_keys[0].pk: (3951285727116295734026345521365512737910419062953537242549018568832618561552329351430853683858605302756892560527243, 2015562491477402081445210194864883205939261701444702459066048593747231321865210770475706036490256666079149530034340)
public_keys[0].proof: (QuadExtField(3882041700531663080715209917545481876729765846180025125888908765171220948117125212571143276457991056473137284787111 + 1050510852775817852847416507597900558865419625189113347525854846152071282929138131519646186856851998395894795581147 * u), QuadExtField(2276155031300751614807654043081790005359418219874201281987179783127300973516686184393036674096389076445085471809656 + 1499576108176939010561117214629143885375859964478472578277936997691719552590218342980721074321136489528861749450818 * u))
[...]
public_keys[8].pk: (1590421703439460875501217084904151928024777767932960691388269493213756601481659194276214126863101251608754666663069, 2514873486426372291261215275870411521130979618244175339961890502447807774325646533262394833397969654866179194151855)
public_keys[8].proof: (QuadExtField(3425299122867009301502774777484371853886695233020764827572267590585668332652640989134711487565285919169053024365378 + 3944021846570525607818281571743626433255634014300232163668270031644045523012218166565184866119660182557753392994734 * u), QuadExtField(109895792935386285998226095339950304065932040948382827892877878577064124319340998704951294008715504779991886183613 + 2408179566338427416508441175406184228438312159836037637845488388439414219265617277506646523139939207977761770383651 * u))
Then, function main
defines the index of an extra key and a message for which we will have to forge a signature and expects us to define three things: a new public key, a new proof and an aggregate signature:
let new_key_index = public_keys.len();
let message = b"YOUR GITHUB USERNAME";
/* Enter solution here */
let new_key = G1Affine::zero();
let new_proof = G2Affine::zero();
let aggregate_signature = G2Affine::zero();
/* End of solution */
The solution should satisfy two conditions. First, the new proof should be valid for the new public key, and second, the aggregate signature should be a valid BLS signature with respect to some aggregate key:
pok_verify(new_key, new_key_index, new_proof);
let aggregate_key = public_keys
.iter()
.fold(G1Projective::from(new_key), |acc, (pk, _)| acc + pk)
.into_affine();
bls_verify(aggregate_key, aggregate_signature, message)
This aggregate key is defined by adding all public keys
That's a good start. In order to progress, let us recall how BLS signatures work.
There are many great online resources about BLS signatures such as here or the IETF draft. In order to make this write-up more self-contained, let us quickly recall how they work.
The signature and verification functions are defined by these few lines of code:
fn bls_sign(sk: Fr, msg: &[u8]) -> G2Affine {
hasher().hash(msg).unwrap().mul(sk).into_affine()
}
fn bls_verify(pk: G1Affine, sig: G2Affine, msg: &[u8]) {
assert!(Bls12_381::multi_pairing(
&[pk, G1Affine::generator()],
&[hasher().hash(msg).unwrap().neg(), sig]
)
.is_zero());
}
Here, public keys are elements from group
Given a secret key
In order to sign a message
The verification function, given a public key
which is equivalent to (but more efficient to compute)
This works since for a signature computed correctly one has
Note that
Hashing into elliptic curves is delicate: this should be done in a way that does not leak any algebraic relation (such as relative discrete logarithms) between resulting points (more formally,
Here, the hash function used for hashing into
fn hasher() -> MapToCurveBasedHasher<G2Projective, DefaultFieldHasher<Sha256, 128>, WBMap<Config>> {
let wb_to_curve_hasher =
MapToCurveBasedHasher::<G2Projective, DefaultFieldHasher<Sha256, 128>, WBMap<Config>>::new(
&[1, 3, 3, 7],
)
.unwrap();
wb_to_curve_hasher
}
It's pretty complicated and fortunately there's no need to understand how it works exactly to solve the puzzle.
BLS signatures have the nice property that they can be aggregated by simply adding them.
Namely, if we have
Then, to check that the
This cuts the cost of verification roughly by half (one only has to compute
This can be shown to be secure assuming all messages are distinct as otherwise a so-called rogue-key attack is possible.
To see why, let us take the simple case of two signers with respective public keys
Because messages are the same, this can be written
Then, assuming signer 0 announced its public key first, signer 1 could just choose its public key as
for some known secret
There are several solutions to thwart this attack:
- one can use "augmented messages", meaning signer
$i$ signs$(P_i,m)$ instead of just$m$ ; this was suggested in the original paper where aggregate BLS signatures were proposed and further formalized in [BNN07]; - one can use "delinearization", meaning each public key
$P_i$ is multiplied by a some random-looking scalar$H'(i,(P_0,\dots,P_{n-1}))$ , for some hash function$H'$ with values in$\mathbb{F}_r$ ; this was first suggested to solve the corresponding problem for Schnorr multisignatures and later studied for BLS in [BDN18]; - finally (and this is the solution the puzzle is about) one can use "proofs of possession", as suggested in [RY07] (reference [2] in the puzzle description); this means that each signer must prove that it has access to the secret key corresponding to its public key; this thwarts rogue-key attacks since signer 1 does not know the secret key corresponding to
$P_1 = xG_1 - P_0$ and hence cannot provide a proof of possession.
What is a proof of possession (PoP) exactly? There is actually no clear security definition. [RY07] defines it as follows:
A POP attests that a party has access to the secret key associated with his/her public key, which is typically accomplished using the functionality of the key pair’s intended scheme. For signature schemes, the simplest POP has a party sign its certificate request message and send both the message and signature to the CA.
Hence, this is somewhat reminiscent of a proof of knowledge, except there is no formal guarantee that there exists an extractor which is capable of extracting the secret key when granted arbitrary access to the party implementing the PoP. In particular, this makes PoPs more cumbersome to use in security proofs. In a protocol based on a proof of knowledge, the security proof is typically modular, meaning it only relies on the assumption that the PoK satisfies extractability. The protocol is then guaranteed to be secure when used with any PoK meeting the definition (which can be proved independently). On the contrary, since PoPs have no formal security definition, one must provide a new security proof for each PoP scheme one may want to use the protocol with.
It has been proved in [RY07] that BLS multi-signatures are secure when used with the PoP which consists in signing its own public key with the corresponding secret key.
Namely, if my key pair is
How does the proof used in the puzzle work exactly? It is defined as follows:
fn derive_point_for_pok(i: usize) -> G2Affine {
let rng = &mut ark_std::rand::rngs::StdRng::seed_from_u64(20399u64);
G2Affine::rand(rng).mul(Fr::from(i as u64 + 1)).into()
}
#[allow(dead_code)]
fn pok_prove(sk: Fr, i: usize) -> G2Affine {
derive_point_for_pok(i).mul(sk).into()
}
fn pok_verify(pk: G1Affine, i: usize, proof: G2Affine) {
assert!(Bls12_381::multi_pairing(
&[pk, G1Affine::generator()],
&[derive_point_for_pok(i).neg(), proof]
)
.is_zero());
}
First, a point in rand
function seeded with some fixed string 20399
.
Importantly, the same point
Hence, this kind of looks like a BLS signature, except that the point which is multiplied by the secret key
We are now ready to gather all the pieces and solve the puzzle.
The straightforward idea is to mount a rogue key attack by choosing some "rogue" secret key
This way, the aggregate key
This means that we know the secret key corresponding to
Are we done, then?
Well, not exactly, as we now have to come with a valid proof of possession of the secret key for
Let us write formally what the proof for
the secret key corresponding to
Recall that the proof for the
We can compute the first term since we know
Hence, we obtain that the proof we're looking for can be computed from the puzzle data as
Here is the code computing the new key, the new proof, and the aggregate signature (the rogue secret is generated pseudorandomly):
let rng = &mut ark_std::rand::rngs::StdRng::seed_from_u64(23898323u64);
let rogue_secret = Fr::rand(rng);
let new_key = public_keys
.iter()
.fold(G1Affine::generator().mul(rogue_secret), |acc, (pk, _)| {
acc - pk
})
.into_affine();
let new_proof = public_keys.iter().enumerate().fold(
pok_prove(rogue_secret, new_key_index),
|acc, (i, (_, proof))| {
let correct =
Fr::from(new_key_index as u64 + 1) * Fr::from(i as u64 + 1).inverse().unwrap();
(acc - proof.mul(correct).into_affine()).into_affine()
},
);
let aggregate_signature = bls_sign(rogue_secret, message);
The proof of possession used in the puzzle departed from what has been proven secure in the literature: instead of hashing the public key into the group, it used points of the form