RangeProofMath.sol

pragma solidity =0.8.4;

import "../EC/EllipticCurve.sol";

contract RangeProofMath is EllipticCurve {
	// elliptic curve point structure
	struct PointEC {
		uint256 x;
		uint256 y;
	}

	// set of data to verify the range proof, where
	// n is the number of bits in the secret
	// m - the number of participants to generate an aggregate range proof
	// k is the number of iterations for the compression operation
	struct SlotCount {
		uint256 n;
		uint256 m; //count Vj
		uint256 k; //count L and R
	}

	// chellenges for range proof verification
	struct SlotChallenge {
		uint256 y;
		uint256 z;
		uint256 x;
		uint256 w;
		uint256 delta;
	}

	// Range Proof structure
	struct SlotRangeProof {
		PointEC[] arrVj;
		PointEC ecA;
		PointEC ecS;
		PointEC ecT1;
		PointEC ecT2;
		uint256 utx;
		uint256 uttx;
		uint256 uee;
		PointEC[] arrLk;
		PointEC[] arrRk;
		uint256 ua;
		uint256 ub;
	}

	// Point to hash function
	function _hashPPToChallange(PointEC memory _pEC_1, PointEC memory _pEC_2)
		internal
		pure
		returns (uint256)
	{
		return uint256(sha256(abi.encode(_pEC_1.x, _pEC_1.y, _pEC_2.x, _pEC_2.y)));
	}

	// function for calculating '_negM' opposite to '_v' modulo 'nn', where
	// _negM + _v = 0 (mod nn)
	function _negMod(uint256 _v) internal pure returns (uint256 _negM) {
		_negM = mulmod(1, _v, nn);
		_negM = nn - _negM;
	}

	// function for calculating vector arrInvYn inverse to _arrMatr modulo _mod, where
	// [_arrMatr] = [arrInvYn] ^ (- 1) (mod _mod)
	function _invMatrMod(uint256[] memory _arrMatr, uint256 _mod)
		internal
		pure
		returns (uint256[] memory _arrInvMatr)
	{
		_arrInvMatr = new uint256[](_arrMatr.length);
		for (uint8 i = 0; i < _arrMatr.length; i++) {
			_arrInvMatr[i] = invMod(_arrMatr[i], _mod);
		}
	}

	// '_paramSHA' - input to start generation
	// function for generating a point on an elliptic curve
	function _genPointEC(bytes memory _paramSHA) internal pure returns (PointEC memory _pEC) {
		uint256 _x;
		uint256 _y;
		uint8 _i;
		while (_i < 256) {
			_x = addmod(uint256(0), uint256(sha256(abi.encodePacked(_i, _paramSHA))), pp);
			_y = eDeriveY(2, _x);
			if (eIsOnCurve(_x, _y) == true) {
				_pEC.x = _x;
				_pEC.y = _y;
				return _pEC;
			}
			_i++;
		}
	}

	// '_paramSHA' - input to start generation
	// '_n' - vector size
	// function for generating a vector of elliptic curve points
	function _genMatrixECPoints(bytes memory _paramSHA, uint256 _n)
		internal
		pure
		returns (PointEC[] memory _matrixECPoints)
	{
		_matrixECPoints = new PointEC[](_n);
		for (uint8 i = 0; i < _n; i++) {
			_matrixECPoints[i] = _genPointEC(abi.encodePacked(_paramSHA, i));
			if (_matrixECPoints[i].y < uint256(pp / 2)) {
				_matrixECPoints[i].y = pp - _matrixECPoints[i].y;
			}
		}
	}

	// function for checking the equality of two points of an elliptic curve
	function _equalPointEC(PointEC memory _pEC1, PointEC memory _pEC2)
		internal
		pure
		returns (bool _isEq)
	{
		_isEq = (_pEC1.x == _pEC2.x) && (_pEC1.y == _pEC2.y);
	}

	// function for calculation vector u, parameter for 'inner product' verification
	function _calc_matrix_u(
		uint256 _k,
		PointEC[] memory _arrLk,
		PointEC[] memory _arrRk
	) internal pure returns (uint256[] memory _arrUk) {
		_arrUk = new uint256[](_k);
		for (uint8 i = 0; i < _k; i++) {
			_arrUk[i] = mulmod(1, _hashPPToChallange(_arrLk[i], _arrRk[i]), nn);
		}
	}

	// function for calculation delta, parameter for 'polinom tx' verification
	function _calc_delta(SlotCount memory _count, SlotChallenge memory _challenge)
		internal
		pure
		returns (uint256 _delta)
	{
		uint256 _n = _count.n;
		uint256 _m = _count.m;

		uint256 _y = _challenge.y;
		uint256 _z = _challenge.z;

		uint256 _v1 = 1; //y^n
		uint256 _v2 = 1; //2^n

		uint256 _spm1 = 1; // <1, y^n>
		uint256 _spm2 = 1; // <1, 2^n>

		uint256 _zz = mulmod(_z, _z, nn); //z^2 mod k

		// _zz = addmod(_negMod(_zz), _z, nn); // z-z^2

		// (z-z^2) * <1, y ^ n*m> === (z-z^2)* m * <1, y^n>
		for (uint8 i = 1; i < _n; i++) {
			_v1 = mulmod(_v1, _y, nn);
			_spm1 = addmod(_spm1, _v1, nn); // <1, y^n>

			_v2 = mulmod(_v2, 2, nn);
			_spm2 = addmod(_spm2, _v2, nn); // <1, 2^n>
		}
		_delta = mulmod(mulmod(_spm1, _m, nn), addmod(_negMod(_zz), _z, nn), nn); // (z-z^2)* m * <1, y^n>

		// -z^3*summ(z^j)*<1, 2^nm> == -summ(z^j) * z^3 * m * <1, 2^n>

		_spm1 = 1;
		for (uint256 j = 1; j < _m; j++) {
			_v1 = mulmod(_v1, _z, nn); //z^j
			_spm1 = addmod(_spm1, _v1, nn); // summ(z^j)
		}
		_spm1 = mulmod(mulmod(_zz, _z, nn), _spm1, nn);
		_spm1 = mulmod(_spm1, mulmod(_spm2, _m, nn), nn);

		_delta = addmod(_delta, _negMod(_spm1), nn);
	}

	// function for calculation challange y
	function _calcChallY(PointEC memory _ecA, PointEC memory _ecS)
		internal
		pure
		returns (uint256 _chall)
	{
		require(eIsOnCurve(_ecA.x, _ecA.y), "Argument '_ecA' is not ec point");
		require(eIsOnCurve(_ecS.x, _ecS.y), "Argument '_ecS' is not ec point");
		_chall = addmod(0, _hashPPToChallange(_ecA, _ecS), nn);
	}

	// function for calculation challange z
	function _calcChallZ(
		PointEC memory _ecA,
		PointEC memory _ecS,
		uint256 _y
	) internal pure returns (uint256 _chall) {
		_chall = addmod(0, uint256(sha256(abi.encode(_ecA.x, _ecA.y, _ecS.x, _ecS.y, _y))), nn);
	}

	// function for calculation challange x
	function _calcChallX(PointEC memory _ecT1, PointEC memory _ecT2)
		internal
		pure
		returns (uint256 _chall)
	{
		require(eIsOnCurve(_ecT1.x, _ecT1.y), "Argument '_ecT1' is not ec point");
		require(eIsOnCurve(_ecT2.x, _ecT2.y), "Argument '_ecT2' is not ec point");
		_chall = addmod(0, _hashPPToChallange(_ecT1, _ecT2), nn);
	}

	// function for calculation challange w
	function _calcChallW(
		uint256 _tx,
		uint256 _ttx,
		uint256 _ee
	) internal pure returns (uint256 _chall) {
		_chall = addmod(0, uint256(sha256(abi.encode(_tx, _ttx, _ee))), nn);
	}

	// function for calculation number of parameters for the SlotCount structure
	function _calc_counters(
		PointEC[] memory _Vj,
		PointEC[] memory _Lk,
		PointEC[] memory _Rk
	) internal pure returns (SlotCount memory _count) {
		//m- number of participants
		_count.m = _Vj.length;
		require(_count.m > 0, "Array Vj is empty");

		_count.k = _Lk.length;
		require(_count.k > 0, "Arrays Lk and Rk with an error");
		require(_count.k == _Rk.length, "Rk and Lk have different sizes");

		//n- length 'v' in bits or k = log2(n) => n = 2^k
		_count.n = 2**_count.k;
	}

	// function for calculation vector with size _n from the powers of _v modulo _mod,
	// where _v ^ i (mod _mod), i = {0, 1, _n-1}
	function _gen_matrix_product(
		uint8 _n,
		uint256 _v,
		uint256 _mod
	) internal pure returns (uint256[] memory arrProd) {
		arrProd = new uint256[](_n);
		arrProd[0] = 1;
		for (uint8 i = 1; i < _n; i++) {
			arrProd[i] = mulmod(arrProd[i - 1], _v, _mod);
		}
	}
}