In part 1 we revisited the Math in Pietrzak’s algorithm. In this post, we’ll try to narrow down a way to do what we’ll need to allow the buying and selling of puzzles. In part 1 this is what we said:
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.
Wouldn’t it be nice if we could simply transform all the values, publish them and preserve the validity of the proof ? The prospective buyer could pick a random factor f and if we multiplied all the values by that factor, would the proof still work ?
$$ y =x^{2^t} \Longrightarrow \;\; y \rho \neq (x \rho)^{2^t} $$
$$ y =x^{2^t} \Longrightarrow \;\; y \rho^{2^t} = (x \rho)^{2^t} $$
This is interesting, isn’t it ?
The solution to a previous partial puzzle of the same complexity, can be used to transform the starting point and solution of a partial puzzle.
Can the proof to a previous partial puzzle be combined with that of another and remain valid ?
Unfortunately, hash values cannot be transformed to preserve the truth of each statement in the proofs, in a way that can allow the next statement to be verified. There is no way to combine ri values. However, because successive values of x and y are directly derived from u and r, we can imagine it might be possible to re-define the values r as:
$$ r_i = g^{x_i.y_i.u_i} \pmod Q , \ \ \ \rho_i = g^{\chi_i \gamma_i \mu_i} \pmod Q , $$ for some group generator g.
With ri defined this way, it’s just as hard for the malicious prover to predict values of r, but now they can be transformed. The proof’s basic equation becomes:
$$ u_{i+1}^{r_i}y_{i+1} \; mod N = (x_{i+1}^{r_i}u_{i+1})^{2^{t/2}} \; mod N$$
What’s interesting now is if we combine two proofs, what does the math look like ? For this I’m going to use greek letters for the other equation and only worry about the r values later:
$$ \mu_{i+1}^{\rho_i}\gamma_{i+1} \; mod N = (\chi_{i+1}^{\rho_i}\mu_{i+1})^{2^{t/2}} \; mod N$$
Multiplying the two sides:
$$ u_{i+1}^{r_i}y_{i+1} \; \mu_{i+1}^{\rho_i}\gamma_{i+1} \; mod N = (x_{i+1}^{r_i}u_{i+1})^{2^{t/2}} \; (\chi_{i+1}^{\rho_i}\mu_{i+1})^{2^{t/2}} \; mod N $$
which simplifies to:
$$ u_{i+1}^{r_i}y_{i+1} \; \mu_{i+1}^{\rho_i}\gamma_{i+1} \; mod N = (x_{i+1}^{r_i}u_{i+1} \; \chi_{i+1}^{\rho_i}\mu_{i+1})^{2^{t/2}} \; mod N $$
rearranging:
$$ u_{i+1}^{r_i} \; \mu_{i+1}^{\rho_i} y_{i+1} \ \gamma_{i+1} \; mod N = (x_{i+1}^{r_i} \; \chi_{i+1}^{\rho_i} u_{i+1} \; \mu_{i+1})^{2^{t/2}} \; mod N $$
Since the (i+1) terms are defined recursively:
$$ x_{i+1} = x_i^{r_i} u_i \ \ , \ \ \ \ \ y_{i+1} = u_i^{r_i} y_i $$
we can see that in order for each side of the equation to have the original form
$$ \beta_i^{\delta_i}\omega_i = (\alpha_i^{\delta_i}\beta_i)^{2^t} $$
we need the left side term to have the form:
$$ u_{i+1}^{r_i} \; \mu_{i+1}^{\rho_i} y_{i+1} \gamma_{i+1} = \beta_i^{\delta_i}\ \omega_i $$
and the right side term, to have the same form:
$$ (x_{i+1}^{r_i} \; \chi_{i+1}^{\rho_i} u_{i+1} \; \mu_{i+1})^{2^{t/2}} = (\alpha_i^{\delta_i}\beta_i)^{2^t}$$ or simply:
$$ x_{i+1}^{r_i} \; \chi_{i+1}^{\rho_i} u_{i+1} \; \mu_{i+1} = \alpha_i^{\delta_i}\beta_i $$
It should be obvious that if we set $$ \forall i, \ \ \delta_i = r_i = \rho_i $$
then setting $$ \forall i, \ \ \beta_i = u_i \mu_i , \ \ \alpha_i = x_i \chi_i, \ \ \omega_i = y_i \gamma_i $$ could make the equations work.
But perhaps we need to check on the way the midpoints are computed:
$$ \beta_i = u_i \mu_i $$ and from above for i=3: $$ u_3 = ({x_0^{t/8}})^{r_2 r_1} ({x_0^{3t/8}})^{r_1} ({x_0^{5t/8}})^{r_2} ({x_0^{7t/8}}) $$ so naturally: $$ \mu_3 = ({\chi_0^{t/8}})^{\rho_2 \rho1_1} ({\chi_0^{3t/8}})^{\rho_1} ({\chi_0^{5t/8}})^{\rho_2} ({x_0^{7t/8}}) $$
we get: $$ \beta_3 = u_3 \mu_3 = ({x_0^{t/8}})^{r_2 r_1} ({x_0^{3t/8}})^{r_1} ({x_0^{5t/8}})^{r_2} ({x_0^{7t/8}}) . ({\chi_0^{t/8}})^{\rho_2 \rho1_1} ({\chi_0^{3t/8}})^{\rho_1} ({\chi_0^{5t/8}})^{\rho_2} ({x_0^{7t/8}}) $$
grouping similar t exponents:
$$ \beta_3 = ({x_0^{t/8}})^{r_2 r_1} ({\chi_0^{t/8}})^{\rho_2 \rho1_1} ({x_0^{3t/8}})^{r_1} ({\chi_0^{3t/8}})^{\rho_1} ({x_0^{5t/8}})^{r_2} ({\chi_0^{5t/8}})^{\rho_2} ({x_0^{7t/8}}) ({x_0^{7t/8}}) $$
and since $$ r_1 = \rho_1, \ \ r_2 = \rho_2 $$
we have:
$$ \beta_3 = ({(x_0\chi0)^{t/8}})^{r_2 r_1} ({(x_0\chi_0)^{3t/8}})^{r_1} ({(x_0\chi_0)^{5t/8}})^{r_2} ({(x_0\chi_0)^{7t/8}}) $$
which is of course:
$$ \beta_3 = ({\alpha_0^{t/8}})^{r_2 r_1} ({\alpha_0^{3t/8}})^{r_1} ({\alpha_0^{5t/8}})^{r_2} ({\alpha_0^{7t/8}}) $$
So now we know we can combine two proofs as long as the two ‘challenge’ exponents are equal:
$$ r_i = g^{x_i.y_i.u_i} = \rho_i = g^{\chi_i \gamma_i \mu_i} \pmod Q $$
In the next post we’ll try to handle this last problem.
One Reply to “Buying and Selling Puzzles Part 2”
Comments are closed.