Crypto Challenge: A proof of work for bitcoin miners | Technology

Upon landing on the island, I woke up and saw that my brothers Diego and María were still asleep.

“That we have already arrived!” I blurted out. Diego didn’t even flinch. Maria opened one eye, and she locked eyes with me. We were still drowsy when, on leaving the airport, we were intercepted by two policemen.

“Come with me, please,” they told us.

My parents, more awake than us, did not seem worried. The policemen explained to us that there were no legal tender currencies on the island and we would have to adapt. We could only use cryptocurrencies.

“That bitcoin thing?” I asked.

They nodded. They gave us an explanatory brochure, which we read carefully. Bitcoin was described there as a digital currency, a type of completely virtual money. Each bitcoin is a computer file that is stored in a “digital wallet” application on a device, such as a mobile phone or computer.

So this won’t be too complicated, I told my brothers, People can send bitcoins to their digital wallet, so it’s easy to send bitcoins to other people or merchants. Every single transaction is recorded on a public list called a blockchain (blockchainin English).

I kept reading, surprised, that thanks to this you can track the history of Bitcoins to prevent people from spending coins they do not own, making copies or undoing transactions.

-The blockchain— my brother explained to me—it’s a data structure. A chain of blocks, where each block contains a set of transactions. A kind of distributed ledger that contains all transactions chronologically; a network made up of many, many computers share this book.

“And so many computers, how do they come to an agreement?” asked my sister.

-Good question. Let’s see what the brochure says – I answered, already a little impatient

As we read, when someone wants to make a transaction, let’s say buy something, they send the request to the computer network. There, special computers called miners are in charge of collecting the requests (and making certain checks, such as having enough money to make the purchase), and incorporate them into the block chain.

“But if there are so many computers, who is in charge of updating that chain of blocks?” I asked.

Well, a puzzle is proposed, which is actually doing a very simple calculation with certain values, so that the result is a value that seems chosen at random. A simplified version would be, for example, to ask them to calculate, for a prime p and given a value x, the cube of x, and keep the rest of calculating the integer division of the cube of x by p. That is, if x = 20 and p = 541, the result would be 426, or if x = 21, with the same p, we would get 64.

“So you only change one number and the result is completely different?” Maria asked in surprise.

“Absolutely,” Diego observed, “Different and unpredictable if you don’t do the math, that’s why it’s called work test. Come on, I’ll put you to the test, to see who is the first to find a value x that cubed and divided by 541, provides a remainder that ends in zero.

My sister and I unholstered the mobile. Within a few minutes, she announced the result with a big smile.

“The 36th!”

My brother and I verified that he was right. 36 cubed is 46656, and when divided by 541, the remainder is 130.

“And I’ve only asked you to end in a zero, a 0,” my brother continued. Imagine if the objective is that with the same procedure it ends in two zeros. Do you want to try it?

Our fingers slid across the screen with great speed. In less than a minute, I had it

“The 481!” I yelled from the rooftops. My strategy of starting at 540 and going down hadn’t gone too badly.

Again, checking it took a few seconds, calculating it took quite a bit more work. Now I saw why it was called proof of work, but we still had to understand how the blockchain kept everyone’s available money. In the brochure there was a figure.

Each rectangle, we decided, represented a block. In each, three transactions seemed to be reflected; for example, in the first block we interpret that D has given M 5 coins M and D paid R 3 and 4 coins respectively. The B tag could be some kind of block name and the number next to the BA tag seemed to refer to the previous block.

—Heyyy!! Have you noticed that they are our initials? – said my sister – Diego, Roger, María.

“Yes, perhaps a lot of coincidence,” I said.

Since 541 played the role of divisor p in the examples in the brochure, we tried dividing 82821 by 541, and to our delight saw 48 come out. We already knew the relationship how the label BA of the second block was built, but where did B come from?

“Have you noticed that it starts with 48 and then the 3 transaction values ​​are concatenated?” observed my sister.

—Mmmmmmm… well now that you mention it, it totally agrees— I replied. But how are the other values ​​calculated? We continue reading.

There was the proof of work. Playing with the numbers in the pamphlet, we found the puzzle: we had to calculate a number whose first digits were 48421 such that when it was cubed and the integer divided with 541, the last two digits of the rest were 00. And it came out just 4842176!

“Well, I’d already be,” Diego sentenced. The miner who gets that value announces it; the other miners (as Maria is doing) check that it is correct and, if they agree, the block is added to the chain.

We went to the policemen and explained that we had already understood. The policewoman smiled mysteriously, she gave us a piece of paper and asked, how much money do you each have?

We managed to pass the test, and with it a small reward that we spent on a pizza, which cost no more and no less than 10,000 bitcoins. It was the year 2010. And to think that in euros that pizza has come to be worth more than 500 million euros!

Could you also pass the test?

Crypto challenges will be published every 15 days. Readers can leave their solutions and discuss the problem in the comments on this page, so anyone who wants to solve it on their own is advised not to read it until they have cracked the puzzle. You can also email your responses [email protected]. In each new challenge we will publish the solution of the previous one, accompanied by a comment with some original or inspiring ideas that we have received.

Vanessa Daza Fernandez She is a professor and researcher at the Department of Information Technologies and Communications at the Universitat Pompeu Fabra in Barcelona.

SOLUTION TO THE PREVIOUS CHALLENGE

The cryptographic tool that appears in this challenge is secret sharing schemes: how to share a secret value s between different participants, giving each participant Pi a fragment fiand in such a way that only those subsets of authorized participants (which define what is known as access structure).

In the first two sharings of the secret (the padlock code), the authorized subsets were all those with two (or more) participants. This is known as a threshold access structure (in this case, the threshold value is 2). Israeli cryptographer Adi Shamir (the S for RSA) proposed a secure way to share secrets for a threshold access structure you: a secret polynomial is chosen, f(x)degree t-1 having secret as an independent term snamely

f(x) = s + a1 x + a2 x² + a3 x³ + … + at-1 x raised to t-1

And the point of the Cartesian plane (i,f(i)) is assigned as a fragment of a participant Pi.

The secret polynomial f(x) has t unknown coefficients, s, a1,…,at-1. Intuition (and mathematics) tells us that to find those t values ​​we need to know at least t data of that polynomial, for example its evaluation at t different points. If there are less than t points / evaluations / fragments, any polynomial of degree t-1 is possible, and therefore the secret value s=f(0) is completely undetermined.

In the case of threshold 2, the polynomial has degree 1 and corresponds to a straight line, f(x) = s + a1 x. In the second distribution of fragments made by the Wizard of the Forest, also corresponding to a line, we have that the line that passes through the points (1.15) and (2.17) is the line with the equation y = 2x + 13. That line intersects the OY axis at the point (0.13), so the secret in that case was 13.

In the case of threshold 3, the secret polynomial will have degree 2, its graph will be a parabola: f(x) = s + a1 x + a2 x².

To recover this secret polynomial (or parabola), three evaluations of the polynomial are needed, that is, three fragments of three different kingdoms, for example we will take Kingdoms 1, 2 and 3. With that information, we would propose a system of three equations with three unknowns ; the unknowns are s, a1 and a2:

fragment (1,22) -> 22 = f(1) = s + a1 1 + a2 1²= s + a1 + a2

fragment (2,29) -> 29 = f(2) = s + a1 2 + a2 2²= s + 2 a1 + 4 a2

fragment (3,32) -> 32 = f(3) = s + a1 3 + a2 3²= s + 3 a1 + 9 a2

The solution to this system of equations is s=11, a1=13, a2=-2, that is to say that the secret polynomial was f(x) = 11 + 13 x – 2 x², and therefore the secret that opened the padlock was s=11.

From that day on, since t=5 fragments (that is, all the fragments of the five kingdoms) would be necessary to recover the secret, one possibility would be to use a secret polynomial of degree 4. But there is another, simpler and more efficient possibility ( and which works as long as the threshold t is equal to the total number of participants): given a secret s to share, the Forest Wizard simply had to choose four fragments at random, say f1, f2, f3 and f4, and define the last one as f5 = s – f1 – f2 – f3 – f4. Thus, the sum of the five fragments will give the secret, but with 4 or less fragments, no information about the secret will be obtained.

When using those schemes to share secrets in real life, the secrets and shards don’t have free size, but for example the secret is chosen from the set of integers {0,1,2,3,…,q-1} for a prime number whatand we work with modular operations modulo q, that is, what equals 0, q+3 equals 3, etc. Thus it is achieved that the size of the fragments f(i) is also controlled, since they belong to the same set {0,1,2,3,…,q-1} that the secret shared.

Many of our readers (such as Javier, Ramiro or Joaquín) have quickly solved this challenge… so we ask you an additional question: another option that the Wizard of the Forest would have had to make the wish of Kingdoms 1, 3 and 4 come true that the subset {2,5} could not retrieve the secret, it would have been to partition the secret for the access structure that contains all subsets of cardinal 2 except {2,5}. Do you dare to find a way to share the secret in that case?

PS: We still have to solve the musical cryptographic challenge that Salva Fuster sent us in the comments to one of these challenges. We have already received a response in our mail [email protected]. We encourage you to solve it too. In the next challenge we will publish the solution that its author has sent us.

You can follow EL PAÍS TECNOLOGÍA at Facebook Y Twitter or sign up here to receive our weekly newsletter.