https://zkhack.dev/zkhackIV/puzzleF2.html
When I got this question, I didn't know where to start.
I tried running cargo run --release
, and as expected, an assert error occurred.
Then I browsed the source code and found that it mainly used things related to the ark_bls12_381
curve, and then looked at the relevant information provided, two English papers. I couldn't read it after just looking at the title
and abstract
. Unfortunately, cryptography papers are often too long for me and I can't grasp the key points. But I vaguely know that this is something related to BLS signature aggregation
and rogue key attacks
.
I'm starting to feel the pain. When I was learning ECC in the past, the difficulty of Pairing-related topics was too high for me, so I skipped it. As a result, my current understanding of BLS pairing is only a black box that that can provide method like
Well, I have to strengthen my understanding of BLS. I found some information, such as Ben's excellent article BLS12-381 For The Rest Of Us, which also quotes a lot of great information, such as Vitalik's article Exploring Elliptic Curve Pairings. I have read these two articles several times, but did not understand them. I am thinking that this time I must completely understand the principle of Pairing, for example, at least in the specific scenario of bls12-381.
A few hours went by and eventually I was exhausted by things like field expansion, embeddedness, and so on. I have found that when studying, if you are exposed to too many new concepts at once and cannot connect these concepts (such as deriving formulas), your brain will become increasingly resistant.
I decided to change direction. I want to still treat BLS Pairing as a black box and see if it can solve the problem. As for the principles and theories, I will study them later.
So I searched for Rogue-Key Attacks
and found this article Rogue Key Attack in BLS Signature and Harmony Security, and then it is recommended to read BLS signatures: better than Schnorr to understand the BLS signature, how it works. There was a familiarity to the article that suggested I had read it before, but reading it again allowed me to understand some of the details. In particular, I decided to manually derive it again based on Signature aggregation section:
There are
Verify signature:
Use aggregated signature, we can compute
Now I figured out that even if different secret keys sign different messages, they can be aggregated.
So what happens with rogue key attacks?
Continue reading the previous article and derive the formula.
Rogue key attacks generally occur when multiple parties sign and aggregate the same message, and the attacker can replace the signed message with the message he wants.
Imagine a scene like this, in consensus, different nodes sign the same block, so
The leader
Normal Process
The malicious leader want to change the block to
When the derivation reaches this point, I feel confident that I can solve this puzzle. This is the power of derivation formulas.
From above, the
We need to provide new_key
, new_proof
, aggregate_signature
, and make them meet the verification of pok and bls:
let new_key = G1Affine::zero();
let new_proof = G2Affine::zero();
let aggregate_signature = G2Affine::zero();
pok_verify(new_key, new_key_index, new_proof);s
bls_verify(aggregate_key, aggregate_signature, message)
Let’s take a look at the contents of bls_verify
first, because we have just derived the formula and are more familiar with it:
#[allow(dead_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());
}
The signature is indeed equivalent to:
But the formula for verifying the signature is a bit strange:
Well, I can only deal with it as a black box again.
Then we see that an aggregate signature is needed to verify a brand new message:
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 requires rogue key attacks to come into play:
let sk = Fr::from(1)
, sk
can be any Fr
non-zero element, but for simplicity, I let it be 1.let pubkey = G1Affine::generator().mul(sk).into_affine();
let sign = bls_sign(sk, message);
let new_key = (pubkey - sum_pubkeys).into_affine();
aggregate_key = new_key + sum_pubkeys = pubkey
, aggregate_signature = sign
, Of course pubkey
and sign
can pass the verification of bls_verify(aggregate_key, aggregate_signature, message)
.Then we need to look at pok related
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());
}
fn main() {
// ...
let new_key = (pubkey - sum_pubkeys).into_affine();
pok_verify(new_key, new_key_index, new_proof);
// ...
}
We can see that pok proof is a point on G2. The random number in derive_point_for_pok
is a fixed number, we can assume it is a. Therefore proof[i] = a * sk[i] * (i+1) * G2
According to the previous summary pok_verify
will success when
How to make new_key
pass the verification of pok_verify
? We don’t have the secret key corresponding to the public key new_key
, but we can make up the correct proof like a signature.
proof[i]/(i+1) = a * sk[i] * G_2
proof = proof[new_key_index] - (new_key_index + 1) * Σ proof[i]/(i+1)
So, the whole solution is:
/* Enter solution here */
let sk = Fr::from(1); // it can be any Fr element
let pubkey = G1Affine::generator().mul(sk).into_affine();
let sign = bls_sign(sk, message);
let proof = pok_prove(sk, new_key_index);
// sum_pubkeys = Σ pubkey
// sum_proofs = Σ (new_key_index + 1) / (i + 1) * proof
let (sum_pubkeys, sum_proofs) = public_keys.iter().enumerate().fold(
(G1Affine::zero(), G2Affine::zero()),
|(acc_pubkey, acc_proof), (index, (pubkey, proof))| {
(
(acc_pubkey + pubkey).into_affine(),
(acc_proof
+ proof.mul(Fr::from(new_key_index as u64 + 1) / (Fr::from(index as u64 + 1))))
.into_affine(),
)
},
);
let new_key = (pubkey - sum_pubkeys).into_affine();
let new_proof = (proof - sum_proofs).into_affine();
let aggregate_signature = sign;
/* End of solution */
The whole solution is here: https://github.com/flyq/puzzle-supervillain