Try   HackMD

ZK-Hack Puzzle #1 Writeup

Intro

A really cool event is ongoing now in the Zero-Knowledge community - the ZK-Hack (details: https://zkhack.dev). Every week a workshop about one of the ZK technologies being developed today is given (details). The first one, given on 26/10/2021 was an introductory workshop about the field of Zero Knowledge Proofs with a great historical introduction.
The event is ongoing for the following seven weeks, with each week a new puzzle is published after the workshop of that week is given.
In this post I'll share a write-up of the first puzzle (link) I was solving with Elichai and Shalev.

Let's Hash it Out

So before the puzzle we are given introductory material to two topics in cryptography:

  1. BLS Signatures
  2. Pedersen Hashes

We are also given a referral to the documentation of arkworks library.

The challenge is available on github, here.
First let's talk briefly on those two cryptographic topics.

BLS Signatures

BLS is a signature scheme, named after Boneh, Lynn and Shacham. It is based on pairings which is a unique algebraic construct based on bilinear maps. Before anyone panics I'll explain what that means.

Definition: Let

G,GT be two groups. A function
e:G×GGT
is a bilinear-map if:

  1. For any scalar
    λ
    and for any
    a,bG
    and for
    c=e(a,b)
    we have:
    e(λa,b)=e(a,λb)=λe(a,b)=λc
  2. For any
    a1,a2,bG
    we have:
    e(a1+a2,b)=e(a1,b)+e(a2,b)
  3. For any
    b1,b2,aG
    we have:
    e(a,b1+b2)=e(a,b1)+e(a,b2)

In a sense, it just means a scalar can be moved freely between the any of the arguments or even out of the function evaluation to the output. If you're really interested how the magic happens I'd recommend reading about Weil-Pairings.

So the BLS signatures are signature schemes that provide the following the functions of KeyGen, Sign and Verify. Let's see how those are performed, please notice that BLS Signatures have multiple variants, I'll be discussing a simplified one that is sufficient to understand the problem.

Setup - Let

g be a generator of group
G
of prime order
r
, and
e:G×GGT
a bilinear map.

  1. KeyGen - Take a random scalar
    sk
    between 0 and
    r1
    . The private key will be
    sk
    , the public key,
    pk=skg
    . Publish
    pk
    and keep
    sk
    secret.
  2. Sign - Given a message
    mG
    the signature of the message is
    skm
    .
  3. Verify, given a message
    m
    and public key
    pk
    and signature
    σ
    verify that
    e(m,pk)=e(σ,g)
    . Notice that if
    σ=skm
    and since
    pk=skg
    then, following the bilinearity of
    e
    we get:

e(m,pk)=e(m,skg)=e(skm,g)=e(σ,g)

This is all nice but in real life scenarios our message to sign is an arbitrary stream of bits and not a group element. Can we find a way to map arbitrary bit-streams into group elements? The answer is yes, and is composed typically of two steps.

  • First, employing a cryptographically secure hash function to the message, reducing it to a constant size (e.g. 256 bits). One example of such function is blake2b.
  • Second, mapping the hash to a group element (typically an element on an elliptic-curve) using a "hash-to-curve" technique.

It is important that along the way we create as little bias as possible to retain the security of the signature scheme.

One such hash-to-curve technique Pedersen Hashes, which is our next subject.

Pedersen Hashes

As mentioned, using Pedersen Hashes we can map the output of a hash function to a group element. Since those groups are typically elliptic curve points, we will use "group element" and "curve point" interchangeably in this section.

So, the Pedersen hash scheme setup is based on a set of

n group elements
g1,...,gn
, which we assume we don't know the discrete-log of each
gi
with respect to any other
gj
. In other words, for each pair
i,j
(
ij
) we can't efficiently find a value
k
such that
gik=gj
.

Given an

n-bit output of of a hash function
h=(b1,...,bn)
(each
bi
is a single bit), the value of the pedersen hash of
h
is
i=1nbigi
. By that we get an element in the group.

The Challenge

In the challenge we are given 256 messages (

m1,...,m256) and those messages' signatures
(s1,...,s256)
signed by some unknown private key (
sk
) which its corresponding public-key is given as well (
pk
).

Each message is signed using the BLS signature scheme where messages are mapped to group elements by first employing a blake2s hash and then using pedersen hash on its output.
It's important to mention that the output of blake2s is 256-bits wide.
The group elements

g1,...,g256 are picked arbitrarily.
Notice that the prime size of the group in our challenge is
r=0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001
.
Therefore the private key is a number in
Zr
(between
0
and
r1
).

We are told that these signatures were published and someone managed to sign some previously unsigned message, and we're asked how can this be done? The solution is in the form of signing ourselves our username as a proof to show we know how can this be done, this basically means that Existential-Unforgeability isn't a property of the signature scheme in this puzzle.

If you haven't tried yet tackling this challenge, I highly encourage you to do so, this is the best way to really understand what happens and to get a better grasp of the underlying concepts who take part in the challenge.

Either way, let's see how this can be solved. We begin with a few notations to make the solution simpler.

Notation

As for notation, we will denote the blake2s of a message

mj using
b(mj)
. We will also denote the
ith
bit of
b(mj)
using
bi(mj)
. Therefore, the pedersen-hash of each message
mj
is:
i=1256bi(mj)gi

Thus, we can view each blake2s output

b(m) as a column-vector of 1's and 0's:
b(m)=(b1(m)b2(m)b256(m))

So, we can also define basic arithmetic of blake2s hashes using vector arithmetics. For two message

mi,mj we have:
b(mi)+b(mj)=(b1(mi)+ b1(mj)b2(mi)+ b2(mj)b256(mi)+ b256(mj))

Where addition is over

Zr (
r
is the size of the group
G
).
For a scalar
cZr
and for some message
m
we define the scalar multiplication
cb(m)
as:
cb(m)=(cb1(m)cb2(m)cb256(m))

The solution

The solution is based on the fact that the signature itself is linear. In the end of the day, we are signing (i.e. multiplying our private key by) a group elemenet. We'll show that the signature of the sum of two group elememts is the sum of the signatures. Let's see what does it mean:
If we take two messages

m1,m2 and blake2s them
b(m1),b(m2)
their pedersen hashes are:
h1=i=1256bi(m1)gih2=i=1256bi(m2)gi

Thus, their signatures
s1,s2
are:
s1=skh1s2=skh2

It's very easy to tell that the signature of

h1+h2 is:
sk(h1+h2)=skh1+skh2=s1+s2

Not only that, but the pedersen hashing is also linear!

Given the vector arithmetics defined previously for the blake2s outputs we can tell that first summing the blake2s outputs and then performing the pedersen hash transformations or first doing the pedersen transformation for each blake2s output and then adding the results yields the same output. In algebtraic terms it means that:

i=1256bi(m1)gi+i=1256bi(m2)gi=i=1256(bi(m1)+bi(m2))gi

Ok, with these two linearity properties, we are ready to solve the puzzle!
We have message

m we want to sign, we compute its blake2s hash
b(m)
.
If we are able to find constants
c1,...,c256
in
Zr
such that:

()    b(m)=i=1256cib(mi)
Then we can generate signature
sm
for
m
by following both linearity properties.
()     sm=i=1256cisi

Remember that

() is a vector equation, holding for each entry in the vector
b(m)
. Which means that for all
j
:
bj(m)=i=1256cibj(mi)

Let's see why

() holds:
sm=skj=1256bj(m)gj=skj=1256(i=1256cibj(mi))gj=ski=1256(j=1256cibj(mi)gj)=i=1256cisk(j=1256bj(mi)gj)si=i=1256cisi

Great, so now the only question is - how can we find those constants

c1,...,c256?
Well, let's look at
()
again, as we already said this is a vector-equation, so it's actually a linear equation system with 256 linear equations (since the vectors are of size 256) and with 256 variables (
c1,...,c256
).
We can express this system of linear equations in matrix nontation:
Ac=b

Such that the variable of the equation is:
c=(c1c2c256)

The vector

b is the bits of the blake hash of our target message
m
:
b=b(m)=(b1(m)b2(m)b256(m))

And the matrix

A is the bits of the blake hash of all messages
m1,...,m256
. Each message has its own column:

A=(b1(m1)b1(m2)b1(m256)b2(m1)b2(m2)b2(m256)b256(m1)b256(m2)b256(m256))

The solution to the equation is:

c=A1b

Luckily enough, matrix

A is invertible so can easily sign the message
m
following our previous equation:
sm=i=1256cisi

Code

In this section we give the basic tools we used to solve the problem in code. While the input data and the whole rust program is written in rust, we have written our solution in the sage programming language.
Sage is a mathematical-oriented programming language with many built-in tools for computation in the fields of algebra, statistics, combinatorics, graph theory and more. It may look similar to python to some readers.
We have also used some rust code to preprocess the input to the sage program and postprocess its output.

Input preprocessing

First we took the messages blake2s hashes from the rust file using the following functions:

fn bytes_to_bits_string(bytes: &[u8]) -> String { let bits = bytes_to_bits(bytes); let mut s = String::with_capacity(bits.len()); for bit in bits { if bit { s.push('1'); } else { s.push('0'); } } return s; } fn write_msgs_to_file(msgs: Vec<Vec<u8>>) { let mut file = File::create(format!( "bits_vecs-{}", (SystemTime::now().duration_since(UNIX_EPOCH)) .unwrap() .as_millis() )) .unwrap(); for msg in msgs { let blake = hash_to_curve(&msg).0; let string = bytes_to_bits_string(&blake); file.write_all(string.as_ref()).unwrap(); file.write_all(b"\n").unwrap(); } }

The write_msgs_to_file function takes a vector of blake2b hashes of the input messages and writes each hash as a string of 0s and 1s representing the binary form of the hash.
Each hash is written in a separate line to the output file.
This file will be passed to our sage code.

Algebraic Processing in Sage

Our sage code is quite short and powerful.
First we read the input and parse it as a list of lists (therefore - a matrix) of 0s and 1s, each binary digit in its own cell of the matrix.

A = list() # bits_vecs-1635288647752 was computed by the rust program, it contains a list of all the messages in bits represantion (after the blake2s hash) with open("bits_vecs-1635288647752", 'r') as f: for line_index, line in enumerate(f): A.append(list()) for bit_index in range(0, 256): A[line_index].append(int(line[bit_index]))

Next, we define

P to be the order of the curve, so scalar that will later be multiplied by the generators in the Pedersen-has-to-curve scheme will be taken from the field
F=ZP
defined right after.

# Curve Order P = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001 F = FiniteField(P)

Next, we define the matrix GA to be simply the list-of-lists A we previously defined, where each entry (0/1) is considered as an element in field F. We transpose it because if you pay attention in the A matrix we defined in the previous section each column (and not row) should contain the bits of a hash of a specific message.
Finally, we compute GAinv which is the transpose of our matrix.

GA = Matrix(F, A)
GAT = GA.transpose()
GAinv = GAT.inverse()

Next, we computed the blake2s value of our message this is our vector

b from previous section where we will look at each bit as an element in
ZP
. Finally, we have to compute
A1b
.

```sage # blake2s of ou bitstring = '0111011010010000000111101110100010110110010100111011011011111111100110001010110001110000111111111100111001100110001001111101110110111011101000100110010110011111001111011010110111110011111111110100111011111011000110000011100101101000001110011101011100010000' bits = [int(el) for el in bitstring] gbits = vector(F, bits) gsolution = GAinv * gbits # Print the generator multipliers. ",".join(['Fq::from_str("'+str(el)+'").unwrap()' for el in gsolution])

The output we get is a vector

c of elements from
ZP
such that the signature for our message will be
i=1256cisi
where
si
is the signature of the
ith
message. This part will be done in rust.

Final Postprocessing and Signature Generation

Our signature generation is also done using rust and is available here as the full code:

https://gist.github.com/elichai/7401f5423c2693960677ba4f8a9fab14#file-computing_the_sig-rs-L55

Here we'll give some explanation on snippets out of it.

First we define the selectors array, a very long array such that selectors[i] is the field element

ci we have obtained using our sage program.

let selectors = [ Fr::from_str( "27645015623588109382996024038763530282647599513403648261518408122004451823795", ) .unwrap(), Fr::from_str( "23018579491472099737921523253639007115479688088731410213980168199642094036630", ) .... .... .... .unwrap(), Fr::from_str( "6769691326408305518047502379958157439957827386631887324632648911856770263560", ) .unwrap(), ];

Next, we multiply each selector[i] by

si the signature of
ith
message (sigs[i]).
This is done using arkworks library.

let mut sum = G1Projective::zero(); for (i, num) in selectors.iter().enumerate() { let additive = sigs[i].into_projective().mul(num); sum += additive; }

Next we make a curve element out of the sum

let affine = G1Affine::from(sum);

And we verify we actually got the correct signature.

verify(pk, msg, affine.clone());

Assuming we do, we output the signature so it is ready for submission and we're done!

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

let mut sig = Vec::new(); affine.serialize(&mut sig).unwrap(); let sig_hex = hex::encode(sig); println!("sig: {}", sig_hex);