arithmetic calculation problem to quadratic arithmetic program

Question

I am reading the Pinocchio paper (verifiable computation): http://research.microsoft.com/pubs/180286/pinocchio.pdf

The paper is rather hard for me. I am considering this calculation problem: $(c_1*c_2+c_3*c_4)*c_5$ Similar to the Figure 2 in the paper. I denote $c_1*c_2=c_6$, $c_3*c_4=c_7$, and $(c_6+c_7)*c_5=c_8$. And denote $r_6, r_7, r_8$ for the gate to get $c_6, c_7, c_8$.

For the value of $v_i$ at $r_6$, $r_7$, $r_8$ is:

vv:[[1,0,1],[0,0,1],[0,1,1],[0,0,1],[0,0,0],[0,0,1],[0,0,1],[0,0,0]]; similarly the value for w and y are:

vw:[[0,0,0],[1,0,0],[0,0,0],[0,1,0],[0,0,1],[0,0,0],[0,0,0],[0,0,0]];

vy:[[0,0,0],[0,0,0],[0,0,0],[0,0,0],[0,0,0],[1,0,0],[0,1,0],[0,0,1]];

Then I use maxima to find $v_i$, $w_i$, and $y_i$. They are all at most of degree 2. And eventually $p(x)$. While $t(x)=(x-r_6)*(x-r_7)*(x-r_8)$

And I found that $p(x)$ is with denominator $(r_7-r_6)^2*(r_8-r_7)^2*(r_6-r_8)^2$, so I I just focus on its numerator, let's denote it as pn(x).

$t(x)$ is of degree 3, $pn(x)$ is of degree 4(=(3-1)*2), so $h(x)$ is of degree 1, i.e. $pn(x)=t(x)*(h_0+h_1*x)$

Clearly, $h_1=\text{coeff}(pn(x),x,4)$ and $h_0=\text{coeff}(pn(x)-t(x)*x*h_1,x,3)$;

For $pn(x)$ to be divisible by $t(x)$, the coefficients of $pn(x)-t(x)*x*h_1$ for $x^2, x^1, x^0$ should be 0. That's to say the following three items should be 0.

$\text{coeff}(pn(x)-t(x)*x*h_1,x,2)$ =$(c_8-c_5*(c_6+c_7+c_4+c_3+c_2+c_1))*(r_7-r_6)^2*(r_8-r_7)*(r_6-r_8)$ $+(c_7-c_3*c_4)*(r_7-r_6)*(r_8-r_7)*(r_6-r_8)^2$ $+(c_6-c_1*c_2)*(r_7-r_6)*(r_8-r_7)^2*(r_6-r_8)$

$\text{coeff}(pn(x)-t(x)*x*h_1,x,1)$ =$(c_8-c_5*(c_6+c_7+c_4+c_3+c_2+c_1))*(r_7-r_6)^2*(r_8-r_7)*(r_6-r_8)*(r_7+r_6)$ $+(c_7-c_3*c_4)*(r_7-r_6)*(r_8-r_7)*(r_6-r_8)^2*(r_6+r_8)$ $+(c_6-c_1*c_2)*(r_7-r_6)*(r_8-r_7)^2*(r_6-r_8)*(r_8+r_7)$

$\text{coeff}(pn(x)-t(x)*x*h_1,x,0)$ =$(c_8-c_5*(c_6+c_7+c_4+c_3+c_2+c_1))*(r_7-r_6)^2*(r_8-r_7)*(r_6-r_8)*r_7*r_6$ $+(c_7-c_3*c_4)*(r_7-r_6)*(r_8-r_7)*(r_6-r_8)^2*r_6*r_8$ $+(c_6-c_1*c_2)*(r_7-r_6)*(r_8-r_7)^2*(r_6-r_8)*r_8*r_7$

This result seems to suggest that the QAP(quadratic arithmetic program) is putting these constrains:

$c_6=c_1*c_2$, $c_7=c_3*c_4$, and $c_8=c_5*(c_6+c_7+c_4+c_3+c_2+c_1)$

The 3rd constraint is very weird. It should be $c_8=c_5*(c_6+c_7)$. Anyone can help me to find the reason here. Appreciated! The following is the maxima code:

globalsolve: true$ r6; r7; r8; vv:[[1,0,1],[0,0,1],[0,1,1],[0,0,1],[0,0,0],[0,0,1],[0,0,1],[0,0,0]]; vw:[[0,0,0],[1,0,0],[0,0,0],[0,1,0],[0,0,1],[0,0,0],[0,0,0],[0,0,0]]; vy:[[0,0,0],[0,0,0],[0,0,0],[0,0,0],[0,0,0],[1,0,0],[0,1,0],[0,0,1]]; vi:=sum(cv[i,j]*x^j,j,0,2); wi:=sum(cw[i,j]*x^j,j,0,2); yi:=sum(cy[i,j]*x^j,j,0,2); solvepoly(i,fn,cn,vn):= (solve([fni=vn[i][1], fni=vn[i][2], fni=vn[i][3]],[cn[i,0],cn[i,1],cn[i,2]]),display([cn[i,0],cn[i,1],cn[i,2]]));

for i:1 step 1 thru 8 do (solvepoly(i,v,cv,vv),solvepoly(i,w,cw,vw),solvepoly(i,y,cy,vy))$

p(x):= rat(sum(c[i]*vi,i,1,8)*sum(c[i]*wi,i,1,8)-sum(c[i]yi,i,1,8)); t(x):=(x-r6)(x-r7)(x-r8); pn(x):=denum(p(x)); / or just times (r7-r6)^2*(r8-r7)^2*(r6-r8)^2; */ pn3(x):=pn(x)-t(x)xcoeff(pn(x),x,4); /* is of degree 3 since p(x) is of 4, t(x) is of 3 */ pn2(x):=pn3(x)-t(x)coeff(pn3(x),x,3); / is of degree 2, should be 0 since both p3(x) and t(x) is of 3 */

pn2_2: coeff(pn2(x),x,2); pn2_1: coeff(pn2(x),x,1); pn2_0: coeff(pn2(x),x,0);

The above 3 items should all be 0 for divisibility. Very unfortunately, these 3 items specify a constraint for $c_8$ is not what we want. What can be wrong here? I think the only place I might have made mistake is the values for v,w,y at $r_6, r_7, r_8$, but I am pretty sure they are all correctly constructed. Because I forgot $v_0, w_0, y_0$? Thanks for looking at this.

By the way, to work on pn2_2, I use the following: A:rat(subst(c[8]=t8+c[5]*(c[6]+c[7]+c[4]+c[3]+c[2]+c[1]),pn2_2)); B:rat(subst(c[7]=t7+c[3]*c[4],A)); C:rat(subst(c[6]=t6+c[1]*c[2],B));

Then I can investigate the coefficients for t8, t7, t6.