Move from secp256k1 to bn256.G1

[HarryR]

The following changes are necessary:

1. remove eclib code
2. add test data generated by orbital for bn256.g1 curve (keep secp256k1 data for reference)
3. update deposit() to validate points for bn256.g1 [1]
4. update 'ring full' branch in deposit() to calculate hashx for bn256.g1 [2]
5. in withdraw() update ring signature calculation [3]
6. update tests
7. check if coverage runs without timing out

[1] https://github.com/clearmatics/mobius/blob/master/contracts/Ring.sol#L81
[2] https://github.com/clearmatics/mobius/blob/master/contracts/Ring.sol#L118
[3] https://github.com/clearmatics/mobius/blob/master/contracts/Ring.sol#L162

[HarryR]

the first step for Ring.sol is to change the curve point validation

bn256 IsOnCurve (where curveB is 3)

func (c *curvePoint) IsOnCurve() bool {
	yy := new(big.Int).Mul(c.y, c.y)
	xxx := new(big.Int).Mul(c.x, c.x)
	xxx.Mul(xxx, c.x)
	yy.Sub(yy, xxx)
	yy.Sub(yy, curveB)
	if yy.Sign() < 0 || yy.Cmp(p) >= 0 {
		yy.Mod(yy, p)
	}
	return yy.Sign() == 0
}

translating this to Solidity is a problem because it relies on signed integers and subtraction, whereas in solidity we have mulmod and addmod but no submod and only have unsigned ints... 😨

so in solidity it should be something like this:

yy = mulmod(y, y, P)
xxx = mulmod(x, x, P)
xxx = mulmod(xxx, x, P)
yy = yy - xxx
yy = yy - 3  // curveB
if( yy >= P ) {
   yy = yy % P
}
return yy.Sign() == 0

but... translating yy.Sign() to work on unsigned ints? 🤕

another method is something like:

yy = mulmod(y, y, P)
xx = mulmod(x, x, P)
z1 = mulmod(xx, x, P)
z2 = addmod(z1, 3, P)
y = modexp(z2, A, P)
return mulmod(y, y, P) == z2

where A is a constant for (P/4)+1

this flips the the point round the doughnut to find its opposing point and verify symmetry.... kinda

the problem here is that modexp is a precompiled contract, so we need to write a wrapper around it possibly using inline assembly. a nice solidity wrapper for the builtin modexp is: https://gist.github.com/lionello/ee285ea220dc64517499c971ff92a2a5 however I think this can be done with less code and cost less gas.

---

secp256k1 IsOnCurve:

// IsOnCurve returns boolean if the point (x,y) is on the curve.
// Part of the elliptic.Curve interface. This function differs from the
// crypto/elliptic algorithm since a = 0 not -3.
func (curve *KoblitzCurve) IsOnCurve(x, y *big.Int) bool {
	// Convert big ints to field values for faster arithmetic.
	fx, fy := curve.bigAffineToField(x, y)

	// Elliptic curve equation for secp256k1 is: y^2 = x^3 + 7
	y2 := new(fieldVal).SquareVal(fy).Normalize()
	result := new(fieldVal).SquareVal(fx).Mul(fx).AddInt(7).Normalize()
	return y2.Equals(result)
}

Ring.sol IsOnCurve (secp256k1, where FIELD_ORDER is P)

        // Throw if submitted pubkey not a valid point on curve
        // Accepting would lock money in the contract forever -- there would
        // be no private key with which to generate the signature to release it
        uint xcubed = mulmod(mulmod(pubx, pubx, FIELD_ORDER), pubx, FIELD_ORDER);

        // Checking y^2 = x^3 + 7 is sufficient as only integers exist in solidity
        if (addmod(xcubed, 7, FIELD_ORDER) != mulmod(puby, puby, FIELD_ORDER)) {
            revert();
        }  

[HarryR]

The second step is to convert HashToPoint, the technique used in Orbital is:

// NewCurvePointFromHash implements the 'try-and-increment' method of
// hashing into a curve which preserves random oracle proofs of security
//
// See: https://www.normalesup.org/~tibouchi/papers/bnhash-scis.pdf
//
func NewCurvePointFromHash(s []byte) *CurvePoint {
	P := CurvePoint{}.Prime()
	N := CurvePoint{}.Order()

        // x = H(s) % N
	h := sha256.Sum256(s)
	x := new(big.Int).SetBytes(h[:])
	x.Mod(x, N)

	for {
		xxx := new(big.Int).Mul(x, x)
		xxx.Mul(xxx, x)
		t := new(big.Int).Add(xxx, 3)

		y := new(big.Int).ModSqrt(t, P)
		if y != nil {
			curveout := CurvePoint{}.SetFromXY(x, y)
			if curveout != nil {
				return curveout
			}
		}
		x.Add(x, bigOne)
	}
}

The biggest problem is Solidity doesn't have a modsqrt function, but with the IsOnCurve method described above it's trivial to perform a similar try-and-increment search, however the IsOnCurve function needs to also return the valid Y point so we can turn the H() output into a point.

e.g.

        x = uint256(sha256(s))
        while(!z) {
            (y, z) = IsOnCurve(x);
            x++;
        }
        x--;

The big problem with try-and-increment is it's complexity is potentially O(n/?) (.... maybe?), but a more complex algorithm which is Ω(1) for a random sample is likely to cost more on average than the naive approach. But that's a story for another day.

[HarryR]

It's possible to compress and decompress points to reduce the on-block storage requirements, however this may increase the gas cost by up to 20%. There are two angles for this:

• current per-byte data costs for uncompressed points (e.g. x,y) are less than the gas cost of decompressing an x' point into x,y
• future costs for uncompressing a point x' point may be lower than storing an x,y point.

I don't think it's worth using compressed points now, but we should re-evaluate this in future.

[HarryR]

Implementation of ecAdd, ecMul and ModExp builtin contracts for Solidity:

    function ModExp(uint256 _base, uint256 _exponent, uint256 _modulus)
        public constant returns (uint256 retval)
    {
        bool success;
        uint[3] memory input;
        input[0] = _base;
        input[1] = _exponent;
        input[2] = _modulus;
        assembly {
            success := call(sub(gas, 2000), 5, 0, input, 0x60, retval, 0x20)
            // Use "invalid" to make gas estimation work
            switch success case 0 { invalid }
        }
        require(success)
    }

The following are taken from Christian Reitwiessner Pairing library: https://gist.github.com/chriseth/f9be9d9391efc5beb9704255a8e2989d (MIT license)

However I noted the inputSize variable is larger than necessary, e.g. 0x80 for 3 arguments, and 0xc0 for 4 arguments, where it should be 0x60 and 0x80 respectively. The return sizes are off too... 0x60 instead of 0x40 for a G1Point...

	/// @return the product of a point on G1 and a scalar, i.e.
	/// p == p.mul(1) and p.add(p) == p.mul(2) for all points p.
	function mul(G1Point p, uint s) internal returns (G1Point r) {
		uint[3] memory input;
		input[0] = p.X;
		input[1] = p.Y;
		input[2] = s;
		bool success;
		assembly {
			success := call(sub(gas, 2000), 7, 0, input, 0x80, r, 0x60)
			// Use "invalid" to make gas estimation work
			switch success case 0 { invalid }
		}
		require (success);
	}

	/// @return the sum of two points of G1
	function add(G1Point p1, G1Point p2) internal returns (G1Point r) {
		uint[4] memory input;
		input[0] = p1.X;
		input[1] = p1.Y;
		input[2] = p2.X;
		input[3] = p2.Y;
		bool success;
		assembly {
			success := call(sub(gas, 2000), 6, 0, input, 0xc0, r, 0x60)
			// Use "invalid" to make gas estimation work
			switch success case 0 { invalid }
		}
		require(success);
	}

	struct G1Point {
		uint X;
		uint Y;
	}

I think we can remove the copying of p1/p2 X and Y and just use the p1 address assuming memory layout is as expected and won't change.

To implement the IsOnCurve function and calculate the y point the following function should work:

    function IsOnCurve(uint256 x)
        public constant returns (uint256 y, bool r)
    {
        uint256 z = mulmod(x,x, P);
        z = mulmod(z, x, P);
        z = addmod(z, 3, P);
        y = modexp(z, A, P);
        r = (z == mulmod(y, y, P));
    }

This should be added to the Pairing library, or at least split the Pairing library into G1 and add it there.

Where A should be (P/4)+1 ? Or (N+1)/4...

G1 is a curve where y² = x³ + b where b=3

Wheres P256k1 is y² = x³ + 7.

---

I noticed the HashToPoint in Deposit() looks like:

            // Security parameter. P(fail) = 1/(2^k)
            uint k = 999;
            uint256 z = bn256g1.Order() + 1;
            z = z / 4;
            for (i = 0; i < k; i++) {
                uint256 beta = addmod(mulmod(mulmod(hashx, hashx, bn256g1.Order()), hashx, bn256g1.Order()), 3, bn256g1.Order());
                hashy = expMod(beta, z, bn256g1.Order());
                if (beta == mulmod(hashy, hashy, bn256g1.Order())) {
                    return;
                }
                
                hashx = (hashx + 1) % bn256g1.Order();
            }         

[HarryR]

After implementing the curve functionality in a library it's now possible to write code like:

            // y^c = G^(xc)
            bn256g1.Point memory yc = ring.pubkeys[i].ScalarMult(cj);

            // G^t + y^c
            bn256g1.Point memory Gt = bn256g1.ScalarBaseMult(tj).PointAdd(yc);

            //H(m||R)^t
            bn256g1.Point memory H = ring.hash.ScalarMult(tj).PointAdd(tag.ScalarMult(cj));

            hashout ^= uint256(sha256(Gt.X, Gt.Y, H.X, H.Y));
            
            csum = addmod(csum, cj, bn256g1.Prime());

Compare this to the half-ported one (using bn256g1):

        // Form H(R||m)
        uint csum = 0;

        for (i = 0; i < Participants; i++) {          
            uint256 cj = ctlist[2*i];
            uint256 tj = ctlist[2*i+1];      

            bn256g1.Point memory y = bn256g1.Point(pubKeyx[i], pubKeyy[i]);
            bn256g1.Point memory yc = bn256g1.ScalarMult(y, cj); // y^c = G^(xc)
            bn256g1.Point memory Gt = bn256g1.ScalarBaseMult(tj); // G^t
            Gt = bn256g1.PointAdd(Gt, yc); // == G^t + y^c
            hashList.push(Gt.X);
            hashList.push(Gt.Y);

            bn256g1.Point memory tauc = bn256g1.ScalarMult(bn256g1.Point(tagx, tagy), cj);
            bn256g1.Point memory H = bn256g1.ScalarMult(bn256g1.Point(hashx, hashy), tj); //H(m||R)^t
            H = bn256g1.PointAdd(H, tauc);            
            hashList.push(H.X);
            hashList.push(H.Y);
           
            csum = addmod(csum, cj, bn256g1.Prime());
        }

        var hashout = uint256(sha256(commonHashList, hashList)) % bn256g1.Prime();

And the original using P256k1:

        for (i = 0; i < Participants; i++) {          
            /* fieldJacobianToBigAffine `normalizes' values before returning -
            normalize uses fast reduction on special form of secp256k1's prime! */ 

            uint cj = ctlist[2*i];
            uint tj = ctlist[2*i+1];      

            (lhsx, lhsy) = ecMul(GX, GY, tj);
            (rhsx, rhsy) = ecMul(pubKeyx[i], pubKeyy[i], cj);
            (lhsx, lhsy) = ecAdd(lhsx, lhsy, rhsx, rhsy);                        
            
            hashList.push(lhsx);
            hashList.push(lhsy);            

            (lhsx, lhsy) = ecMul(hashx, hashy, tj);
            (rhsx, rhsy) = ecMul(tagx, tagy, cj);
            (lhsx, lhsy) = ecAdd(lhsx, lhsy, rhsx, rhsy);               
            
            hashList.push(lhsx);
            hashList.push(lhsy);  
           
            csum = addmod(csum, cj, GEN_ORDER);
        }

        var hashout = uint256(sha256(commonHashList, hashList)) % GEN_ORDER;

Then a slight revision:

	function _ringLink( uint256 cj, uint256 tj, bn256g1.Point tag, bn256g1.Point hash, bn256g1.Point pub )
		internal constant returns (uint256 ho)
	{		
        // y^c = G^(xc)
        bn256g1.Point memory yc = pub.ScalarMult(cj);

        // G^t + y^c
        bn256g1.Point memory Gt = bn256g1.ScalarBaseMult(tj).PointAdd(yc);

        //H(m||R)^t
        bn256g1.Point memory H = hash.ScalarMult(tj).PointAdd(tag.ScalarMult(cj));

        return uint256(sha256(Gt.X, Gt.Y, H.X, H.Y));
	}


	function Withdraw (bytes32 ring_id, uint256 _tag_x, uint256 _tag_y, uint[] ctlist)
		public returns (bool)
	{
		bn256g1.Point memory tag = bn256g1.Point(_tag_x, _tag_y);
		Ring storage ring = m_rings[ring_id];
		if( ring.pubkeys.length != RING_SIZE ) {
			revert();
		}

		// tags are unique, a duplicate tag = double spend
		for( uint i = 0; i < ring.tags.length; i++ ) {
			if( ring.tags[i] == tag.X )  {
				revert();
			}
		}

		uint256 hashout = 0; // begin with commonHashList
        uint csum = 0;
		uint256 cj;
		uint256 tj;

        for (i = 0; i < ring.pubkeys.length; i++) {        	
            cj = ctlist[2*i];
            tj = ctlist[2*i+1];
            hashout ^= _ringLink(cj, tj, tag, ring.hash, ring.pubkeys[i]);
            csum = addmod(csum, cj, bn256g1.Prime());
        }

        hashout %= bn256g1.Prime();

        return hashout == csum;
	}

Need to verify equivalency

[HarryR]

Original:

lhs = G^t
rhs = pub^c
lhs = lhs + rhs

so this reduces to G^t + pub^c

Then

lhs = hash^t
rhs = tag^c
lhs = lhs + rhs

Which reduces to hash^t + tag^c

So...

Gt = G^t    // (lhsx, lhsy) = ecMul(GX, GY, tj);
pc = p^c    // ecMul(pubKeyx[i], pubKeyy[i], cj);
Gt_pc = Gt + p^c  // ecAdd(lhsx, lhsy, rhsx, rhsy);  
z = hash^t + tag^c

So, then the two sides of the hash are constructed:

h []= (Gt_pc, z)
csum += c

Then to verify the hash of all elements of h and the public keys x points involved in the ring are hashed mod G, this should equal the sum of all c.

I would like to adjust the way the hash is constructed to reduce the EVM storage, stack and memory limitations, the way I intend to do this is to instead of constructing a list of all public keys in the ring along with the Gt_pc and z values from the algorithm above, to instead use the commutable property to combine the hashes in a way which doesn't break the random oracle model.

I am concerned about ensuring ordering is preserved when necessary to prevent weird edge cases, for example I don't want to make the assumption that H(Gt_pc) ⊕ H(hash^t + tag^c) are equivalent because this could introduce a signature malleability problem, so it must be H(Gt_pc, hash^t + tag^c).

However, as long as it's done this way I don't see any reason why we cannot use xor to construct the hash.

[HarryR]

Next we need to verify whether or not the adjustments made in the signature verification in Withdraw() can be easily applied to the Signature() algorithm in Orbital.

// Signature generates a signature
func (r *Ring) Signature(pk *big.Int, message []byte, signer int) (*RingSignature, error) {
	N := CurvePoint{}.Order()

	mR := r.Bytes()
	byteslist := append(mR, message...)
	hashp := NewCurvePointFromHash(byteslist)
	// TODO: checkk hashp

	pk.Mod(pk, N)
	hashSP := hashp.ScalarMult(pk)

	n := len(r.PubKeys)
	var ctlist []*big.Int   //This has to be 2n so here we have n = 4 so 2n = 8 :)
	var a, b CurvePoint
	var ri *big.Int
	csum := big.NewInt(0)

	for j := 0; j < n; j++ {

		if j != signer {
			cj := CurvePoint{}.RandomN()
			tj := CurvePoint{}.RandomN()

			a = r.PubKeys[j].ParameterPointAdd(tj, cj)

			b = hashp.HashPointAdd(hashSP, tj, cj)
			ctlist = append(ctlist, cj)
			ctlist = append(ctlist, tj)
			csum.Add(csum, cj)
		}

		if j == signer {
			dummy := big.NewInt(0)
			ctlist = append(ctlist, dummy)
			ctlist = append(ctlist, dummy)
			ri = CurvePoint{}.RandomN()
			a = CurvePoint{}.ScalarBaseMult(ri)
			b = hashp.ScalarMult(ri)
		}
		byteslist = append(byteslist, a.Marshal()...)
		byteslist = append(byteslist, b.Marshal()...)
	}

	hasha := sha256.Sum256(byteslist)
	hashb := new(big.Int).SetBytes(hasha[:])
	hashb.Mod(hashb, N)
	csum.Mod(csum, N)
	c := new(big.Int).Sub(hashb, csum)
	c.Mod(c, N)

	cx := new(big.Int).Mul(c, pk)
	cx.Mod(cx, N)
	ti := new(big.Int).Sub(ri, cx)
	ti.Mod(ti, N)
	ctlist[2*signer] = c
	ctlist[2*signer+1] = ti

	return &RingSignature{hashSP, ctlist}, nil
}

So, where the public key from the ring isn't ours:

c = r%N
t = r%N
a = G^t + pub^c
b = hash^t + hash^pk
ctlist.append([c, t])
csum += c

Where the public key is ours, and we hold the private key:

ctlist.append([0, 0])
ri = r%N
a = G^ri
b = hash^ri

Where:

• each r is a random integer
• pub is a public key from the ring
• pk is the signers/our private key

So, H(a,b) matches H(Gt_pc, z) from above.

The really interesting stuff is at the end though, but it looks like we can use the xor commutative property here 👍

So if byteslist is a list of H(a,b), and hash is the xor of every H(a,b)

Then c = (hash - csum) % N

cx = (c*pk)%N

ti = (ri - cx) % N

Then replace entries in ctlist (which were populated with 0) with c and ti.

Assuming there are no flaws in the mathematics underpinning paper, and I have to trust it, then we should be good.

[HarryR]

While I'm at it I'm re-working the Mixer.sol to get it into a state where I can start to run tests and verify the code. This should be a relatively quick change which allows the one Mixer contract to handle multiple Rings, calling Deposit() will automatically select a Ring for you and return the Ring GUID - this must be passed to the Withdraw() function.

[HarryR]

So Matt pointed out that with the optimisation I implemented there is one flaw.

If any x is found where sha256(x) == 0 then all rings are broken. Whereas with ordering enforced the same amount of effort would be required to break each ring.

This change has been modified to preserve the initial storage optimisations while maintaining the probabilistic unlikelyhood of an attack against sha256 affecting all chains indiscriminately.