Buying and Selling Time-Lock Puzzles

As the BqETH system grows, more puzzle farmers will be attracted by the prospect of rewards. Yet, once a puzzle farmer has embarked on solving a puzzle, there is no clear way in which they will be able to privately sell a partially completed puzzle within a puzzle chain. This is because the BqETH contract implementing the Commit/Reveal method of claiming puzzle rewards, forces the puzzle farmer to reveal the puzzle solution eventually.

First, it should be obvious that rather than sell a completed puzzle, it will be simpler to just claim its reward. If a puzzle farmer needs to abandon puzzle farming for whatever reason, a partially completed puzzle is only viable if:

• The buyer can be sure it is a true solution y=x₀ⁿ with n less than the puzzle challenge t
• The buyer has enough information to claim the final reward
• No-one else can use the information to claim the reward.

With these constraints, it should be clear that a valid proof of completion up-to the step n could be sufficient to convince a buyer the solution is valid. Yet, because the final proof requires computing values u_i which depend on intermediate ‘checkpoints’ at fractions of the value t , e.g. 5t/8 .

it is clear that the checkpoints at powers of x₀ will need to be communicated to the buyer, who will then be able to re-construct values of r_i, then u_i.

The inset below shows the values used for each level, as a sort of convolution.

u1 -> 1                                  t/2
u2 -> r1, 1                              t/4, 3t/4
u3 -> r2 r1, r1, r2, 1                   t/8, 3t/8, 5t/8, 7t/8
u4 -> r3 r2 r1, r2 r1, r3 r1, r1, r3 r2, r2, r3, 1     t/16, 3t/16, 5t/16, 7t/16, 9t/16, 11t/16, 13t/16, 15t/16
...

Also, because we assumed the puzzle is not yet finished, perhaps it is only half complete, clearly some of these values will be missing, e.g. 3t/4, 5t/8 etc…

Finally, because it is only possible to construct a Pietrzak proof for a puzzle in which t is a power of two. On the surface, this might appear to mean puzzle farmers cannot stop in the second half of the puzzle – since there is no power of two between t/2 and t – but luckily, we have no such restriction on the starting point of a puzzle. In other words, a puzzle of length t=1024 which has been computed up to 2⁷⁶⁸ because it can be decomposed into two smaller puzzles, with complete proofs for 2⁵¹² and 2²⁵⁶ with the same checkpoints. The proof for the second puzzle just needs to start with the solution of the first.

For the rest of the discussion, we’ll just focus on what needs to be done when the partial puzzle falls on a power of two.

Finally, to address the third bullet, we need to consider that with a multitude of active puzzles in the BqETH ecosystem, it is likely that a market will develop for incomplete puzzles, which means that some efficiency will emerge only if puzzle farmers can not only offer their solutions but also prove their legitimacy independently of the number of potential buyers. It would be unreasonable to imagine the seller encrypting their payload for every potential buyer.

Therefore, a method of presenting a transformed solution and proof will be needed, such that the transformed version’s proof can verify the solution without revealing it.
I don’t know if we can solve this problem, yet, and these are my thoughts.

Revisiting the Math

In the diagram below, the arrows depict the relationships between values that are required to calculate them. For example, y₂ is calculated from u₁, r₁ and y₁. Here, x₁ is the start value and y₁ is the solution.

The red arrows depict that some substantial work must occur to compute the result. Indeed the longest arrow from x₁ to y₁ is the full puzzle. The other arrows are work that is already done, while solving the puzzle, to arrive at the checkpoints used in the calculations of the u_i expressions, as explained in the section above, yet it takes time.
This is why these values are given to the verifier. The easiest one to see is of course u₁, the midpoint between x₁ and y₁. It would clearly be unreasonable to expect the verifier to compute that value, spending half the original puzzle time, to compute it from x₁.

In the original algorithm of Pietrzak, the prover and the verifier can both derive the values r , following the Fiat-Shamir transformation, from the transcript of the proof protocol so far.

This is to emulate a dialogue with a verifier who would pick a random challenge r_i such that a legitimate prover, in possession of x_i, u_i and y_i can simply compute

but a malicious prover who doesn’t know u_i and cannot predict the value of r, is faced with searching for a value u_i that will make the equation work with their fake solution y. As it turns out, this is harder than doing the honest work of solving the puzzle.

In practice, the value r is typically derived from the hash of the last known values of x, y, u. The important criteria here is that it should be near impossible for a Prover to predict the value of r, ahead of time, without having first done the work of repeated modular exponentiation between x₁ and y₁. The verifier, can also derive the same values of r later, allowing the proof and verification to occur without the need for the dialogue.

With a single level, the verifier would have to perform work equivalent to a half puzzle’s time to verify the statement, since it has half the complexity, but luckily, that statement too can have its own proof in the form of a new midpoint u , a new challenge r and half the complexity to verify. This halving of complexity continues until the last statement to verify is a simple squaring.

To fool a Pietrzak verifier, a malicious Prover would therefore have to search for values of u_i that validate the fake solution, starting at the easiest level first, then moving up. If the r values are predictable, or weak, the search may find values of (x_i, y_i , u_i) whose relationship in the equation above holds true, for the last exponent, such as 2, i.e. t=1.

Let’s work through an example and see how this would work out. We could assume our hash function is too easy to reverse, in other words, assume that figuring out a value u_i that yields a specific r_i=H(x_i, y_i, u_i) is simple to do.

Also, we’re only going to expose the algorithm with just three levels: the last level of the proof the verifier checks is of the form

Then, proceeding backward from the last statement in the proof with:

At this point, the malicious Prover must use the x₁ from the puzzle, since this value is public, but the value of y₁ is still unknown. They can simply pick a random u₁, then derive x₂ using equation (3) , then pick u₂ and derive y₂ from equation (2), then from y₂ and u₁ derive y₁ using equation (4).

In other words, they can descend through the left side of the diagram, deriving u₁, x₂, u₂, x₃, u₃, x₄, u₄, …. then solve a single modular squaring to derive the deepest value of y, then using the same values of u, they can climb back through the right side of the diagram, deriving y₄, y₃, y₂, y₁ .

Cheating is only possible if the way r_i values are created is predictable.

In Part 2, we’ll investigate how we might approach a solution.