RangeProof.sol 11.8 KB
Newer Older
John Doe's avatar
John Doe committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393
// SPDX-License-Identifier: MIT
pragma solidity =0.8.4;

import "./RP/RangeProofMath.sol";

contract RangeProof is RangeProofMath {
	PointEC internal ecB; //point ec B
	PointEC internal ecBB; // point ec B'
	uint8 internal constant n = 64; // bits amount of secret value
	uint8 internal constant k = 6; // number of iterations for compression inner products, the dependence n = 2^k

	constructor() {
		(ecB.x, ecB.y) = (gx, gy);
		ecBB = _genPointEC(abi.encodePacked(ecB.x, ecB.y));
	}

	/**
	 * @dev Verify polinom tx verification.
	 * @param rp range proof elements.
	 * @return result of verification.
	 */
	function verifyPolinom(SlotRangeProof memory rp) external view returns (bool) {
		PointEC memory _leftPart;
		PointEC memory _rightPart;
		PointEC memory _pEC;
		uint256 _product;

		SlotCount memory _count = _calc_counters(rp.arrVj, rp.arrLk, rp.arrRk);

		SlotChallenge memory _challenge;
		_challenge.y = _calcChallY(rp.ecA, rp.ecS);
		_challenge.z = _calcChallZ(rp.ecA, rp.ecS, _challenge.y);
		_challenge.x = _calcChallX(rp.ecT1, rp.ecT2);

		_challenge.delta = _calc_delta(_count, _challenge);

		_product = mulmod(_challenge.z, _challenge.z, nn); // z^2
		(_rightPart.x, _rightPart.y) = eMul(_product, rp.arrVj[0].x, rp.arrVj[0].y); //z^2 * V
		for (uint8 j = 1; j < _count.m; j++) {
			_product = mulmod(_product, _challenge.z, nn);
			(_pEC.x, _pEC.y) = eMul(_product, rp.arrVj[j].x, rp.arrVj[j].y); //z^(j+1)*V[j]
			(_rightPart.x, _rightPart.y) = eAdd(_rightPart.x, _rightPart.y, _pEC.x, _pEC.y);
		}
		(_pEC.x, _pEC.y) = eMul(_challenge.delta, ecB.x, ecB.y); // delta*B
		(_rightPart.x, _rightPart.y) = eAdd(_rightPart.x, _rightPart.y, _pEC.x, _pEC.y); //... + delta*B
		(_pEC.x, _pEC.y) = eMul(_challenge.x, rp.ecT1.x, rp.ecT1.y); //x*T1
		(_rightPart.x, _rightPart.y) = eAdd(_rightPart.x, _rightPart.y, _pEC.x, _pEC.y); // ... + x*T1
		(_pEC.x, _pEC.y) = eMul(mulmod(_challenge.x, _challenge.x, nn), rp.ecT2.x, rp.ecT2.y); //x^2*T2
		(_rightPart.x, _rightPart.y) = eAdd(_rightPart.x, _rightPart.y, _pEC.x, _pEC.y); //... + x^2*T2

		(_leftPart.x, _leftPart.y) = ePedersenCommitment(
			rp.utx,
			rp.uttx,
			ecB.x,
			ecB.y,
			ecBB.x,
			ecBB.y
		);

		return _equalPointEC(_leftPart, _rightPart);
	}

	/**
	 * @dev Generate matrix H of elliptic curve points.
	 * @param mj stringValue.
	 * @return ecMatrHj H(stringValue)
	 */
	function genMatrixH(uint8 mj) external view returns (PointEC[] memory ecMatrHj) {
		bytes memory _paramSHA = abi.encode(ecBB.x, ecBB.y);
		ecMatrHj = _genMatrixECPoints(abi.encodePacked(_paramSHA, mj), n);
	}

	/**
	 * @dev Generate matrix G og elliptic curve points.
	 * @param mj H(Lk, Rk).
	 * @return ecMatrGj  u[j]^b(i,j).
	 */
	function genMatrixG(uint8 mj) external view returns (PointEC[] memory ecMatrGj) {
		// matrix G j
		bytes memory _paramSHA = abi.encode(ecB.x, ecB.y);
		ecMatrGj = _genMatrixECPoints(abi.encodePacked(_paramSHA, mj), n);
	}

	/**
	 * @dev Returns left part of IPP.
	 * @param rp range proof elements.
	 * @param ecGk G piint.
	 * @param ecHHk H point
	 * @return ecRight EC point, calculated left part of IPP.
	 */
	function getVerifyInnerProductLeft(
		SlotRangeProof memory rp,
		PointEC memory ecGk,
		PointEC memory ecHHk
	) external view returns (PointEC memory ecRight) {
		// a*<s, G> + b*<1/s, H> + a*b*Q
		PointEC memory _pEC;

		(ecRight.x, ecRight.y) = eMul(rp.ua, ecGk.x, ecGk.y); // a*<s, G>

		(_pEC.x, _pEC.y) = eMul(rp.ub, ecHHk.x, ecHHk.y); // b*<1/s, H'>

		(ecRight.x, ecRight.y) = eAdd(ecRight.x, ecRight.y, _pEC.x, _pEC.y);

		//a*b*(tx*B)
		// (_pEC.x, _pEC.y) = eMul(_challenge.w, ecB.x, ecB.y);
		(_pEC.x, _pEC.y) = eMul(_calcChallW(rp.utx, rp.uttx, rp.uee), ecB.x, ecB.y);
		(_pEC.x, _pEC.y) = eMul(rp.ua, _pEC.x, _pEC.y);
		(_pEC.x, _pEC.y) = eMul(rp.ub, _pEC.x, _pEC.y);

		(ecRight.x, ecRight.y) = eAdd(ecRight.x, ecRight.y, _pEC.x, _pEC.y);
	}

	/**
	 * @dev Calculates IPPP0 - parameter for Inner Product Right.
	 * @param rp range proof elements.
	 * @param baseP P piint, calculated by getBaseP function.
	 */
	function getIPPP0(SlotRangeProof memory rp, PointEC memory baseP)
		external
		view
		returns (PointEC memory ippP0)
	{
		//P - e'*B' + tx*Q
		PointEC memory _pEC;

		// e'*B'
		(_pEC.x, _pEC.y) = eMul(rp.uee, ecBB.x, ecBB.y);
		//- e'*B'
		(_pEC.x, _pEC.y) = eInv(_pEC.x, _pEC.y);

		(ippP0.x, ippP0.y) = eAdd(baseP.x, baseP.y, _pEC.x, _pEC.y);

		(_pEC.x, _pEC.y) = eMul(_calcChallW(rp.utx, rp.uttx, rp.uee), ecB.x, ecB.y); // Q = w*B
		(_pEC.x, _pEC.y) = eMul(rp.utx, _pEC.x, _pEC.y); // tx*Q

		(ippP0.x, ippP0.y) = eAdd(ippP0.x, ippP0.y, _pEC.x, _pEC.y);
	}

	/**
	 * @dev Final Range Proof verification.
	 * @param verPolinom polinom verification result.
	 * @param verIPP inner product proof verification result.
	 * @return Result of verification.
	 */
	function verifyRP(bool verPolinom, bool verIPP) external pure returns (bool) {
		return verPolinom && verIPP;
	}

	/**
	 * @dev Inner Product Prove verification.
	 * @param leftVerIPP left part of IPP: a*<s, G> + b*<1/s, H> + a*b*Q.
	 * @param rightVerIPP right part of IPP: P0 + <uk^2, L> + <uk^(-2), R>
	 * @return Result of verification.
	 */
	function verifyIPP(PointEC memory leftVerIPP, PointEC memory rightVerIPP)
		external
		pure
		returns (bool)
	{
		return _equalPointEC(leftVerIPP, rightVerIPP);
	}

	/**
	 * @dev Calculate vector u, parameter for 'inner product prove' verification.
	 * @param rp range proof elements.
	 * @return arrUk H(Lk, Rk).
	 */
	function genMatrUk(SlotRangeProof memory rp) external pure returns (uint256[] memory arrUk) {
		//uk = H(Lk, Rk)
		arrUk = _calc_matrix_u(k, rp.arrLk, rp.arrRk);
	}

	/**
	 * @dev Calculate vector s, parameter for 'inner product prove' verification.
	 * @param arrUk H(Lk, Rk.
	 * @return s u[j]^b(i,j).
	 */
	function genMatrS(uint256[] memory arrUk) external pure returns (uint256[] memory s) {
		uint256 _multipl;
		uint256 _prodMultipl;
		s = new uint256[](n);
		for (uint8 i = 0; i < n; i++) {
			_prodMultipl = 1;
			for (uint8 j = 1; j <= k; j++) {
				//calculation matrix u[j]^b(i,j)
				if (mulmod(1, i, 2**j) < 2**(j - 1)) {
					//u[i]^-1
					_multipl = invMod(arrUk[k - j], nn);
				} else {
					_multipl = arrUk[k - j];
				}
				_prodMultipl = mulmod(_prodMultipl, _multipl, nn);
			}
			s[i] = _prodMultipl;
		}
	}

	/**
	 * @dev Calculate point G.
	 * @param s points of u[j]^b(i,j) calculation.
	 * @param arrG array of G points.
	 * @return ecGk <s, G>.
	 */
	function genGk(uint256[] memory s, PointEC[] memory arrG)
		external
		pure
		returns (PointEC memory ecGk)
	{
		PointEC memory _pEC;
		for (uint8 i = 0; i < n; i++) {
			(_pEC.x, _pEC.y) = eMul(s[i], arrG[i].x, arrG[i].y);
			(ecGk.x, ecGk.y) = eAdd(_pEC.x, _pEC.y, ecGk.x, ecGk.y);
		}
	}

	/**
	 * @dev Calculate point H.
	 * @param s points of u[j]^b(i,j) calculation.
	 * @param arrHH array of H points.
	 * @return ecHHk <1/s, H'>.
	 */
	function genHHk(uint256[] memory s, PointEC[] memory arrHH)
		external
		pure
		returns (PointEC memory ecHHk)
	{
		PointEC memory _pEC;
		for (uint8 i = 0; i < n; i++) {
			(_pEC.x, _pEC.y) = eMul(s[n - i - 1], arrHH[i].x, arrHH[i].y);
			(ecHHk.x, ecHHk.y) = eAdd(ecHHk.x, ecHHk.y, _pEC.x, _pEC.y);
		}
	}

	/**
	 * @dev Calculate vector of 2^n.
	 * @return arr2n [2^i], i={0, 1, ..., n-1}.
	 */
	function genMatr2n() external pure returns (uint256[] memory arr2n) {
		arr2n = _gen_matrix_product(n, 2, nn);
	}

	/**
	 * @dev Calculate vector of y^n.
	 * @param rp range proof elements.
	 * @return arr2n [y^i], i={0, 1, ..., n-1}.
	 */
	function genMatrYn(SlotRangeProof memory rp) external pure returns (uint256[] memory arr2n) {
		arr2n = _gen_matrix_product(n, _calcChallY(rp.ecA, rp.ecS), nn);
	}

	/**
	 * @dev Calculate inverse vector of y^n.
	 * @param arrYn array of elements y^n.
	 * @return arrInvYn [y]^(-1).
	 */
	function genInvMatrYn(uint256[] memory arrYn)
		external
		pure
		returns (uint256[] memory arrInvYn)
	{
		arrInvYn = _invMatrMod(arrYn, nn);
	}

	/**
	 * @dev Calculate inverse vector of y^n.
	 * @param arrUk array of elements u - H(Lk, Rk).
	 * @return arrUk2 inversed y^n vector.
	 */
	function genMatrUk2(uint256[] memory arrUk) external pure returns (uint256[] memory arrUk2) {
		arrUk2 = new uint256[](k);
		for (uint8 j = 0; j < k; j++) {
			arrUk2[j] = mulmod(arrUk[j], arrUk[j], nn);
		}
	}

	/**
	 * @dev Calculate inverse vector of arrU2k with mod nn .
	 * @param arrU2k array of elements u - H(Lk, Rk).
	 * @return arrInvU2k inversed arrU2k vector.
	 */
	function genInvMatrUk2(uint256[] memory arrU2k)
		external
		pure
		returns (uint256[] memory arrInvU2k)
	{
		arrInvU2k = _invMatrMod(arrU2k, nn);
	}

	/**
	 * @dev Calculate vector H', parameter for IPP verification.
	 * @param arrH array H points.
	 * @param arrInvYn inversed y^n.
	 * @return _arrHH [y^(-n)] * [H].
	 */
	function genMatrHprime(PointEC[] memory arrH, uint256[] memory arrInvYn)
		external
		pure
		returns (PointEC[] memory _arrHH)
	{
		_arrHH = new PointEC[](arrH.length);
		for (uint8 i = 0; i < arrH.length; i++) {
			(_arrHH[i].x, _arrHH[i].y) = eMul(arrInvYn[i], arrH[i].x, arrH[i].y); // y^(-n) * H
		}
	}

	/**
	 * @dev Calculates point P, parameter for IPP verification.
	 * @param rp range proof elements.
	 * @param ecMatrG array of G points.
	 * @param ecMatrHH array of H points.
	 * @param arr2n array of 2^n elements.
	 * @param arrYn array of y^n elements.
	 * @return baseP P = A + x*S - z*<1, G> + <z*y^n + z^2*2^n, H'>.
	 */
	function getBaseP(
		SlotRangeProof memory rp,
		PointEC[] memory ecMatrG,
		PointEC[] memory ecMatrHH,
		uint256[] memory arr2n,
		uint256[] memory arrYn
	) external pure returns (PointEC memory baseP) {
		// P = A + x*S - z*<1, G> + <z*y^n + z^2*2^n, H'>

		SlotChallenge memory _challenge;
		_challenge.y = _calcChallY(rp.ecA, rp.ecS);
		_challenge.z = _calcChallZ(rp.ecA, rp.ecS, _challenge.y);
		_challenge.x = _calcChallX(rp.ecT1, rp.ecT2);

		uint256 _mul;
		uint256 _z2 = mulmod(_challenge.z, _challenge.z, nn); //z^2
		PointEC memory _pEC;

		// P = A + x*S - z*<1, G> + <z*y^n + z^2*2^n, H'>

		// <z*y^n + z^2*2^n, H'>
		for (uint8 i = 0; i < ecMatrHH.length; i++) {
			_mul = addmod(mulmod(_challenge.z, arrYn[i], nn), mulmod(_z2, arr2n[i], nn), nn); // z*y^n + z^2*2^n
			(_pEC.x, _pEC.y) = eMul(_mul, ecMatrHH[i].x, ecMatrHH[i].y); // (z*y^n + z^2*2^n) * H'
			(baseP.x, baseP.y) = eAdd(baseP.x, baseP.y, _pEC.x, _pEC.y);
		}

		(_pEC.x, _pEC.y) = eMul(_challenge.x, rp.ecS.x, rp.ecS.y); //x*S

		(_pEC.x, _pEC.y) = eAdd(rp.ecA.x, rp.ecA.y, _pEC.x, _pEC.y); // A + x*S

		(baseP.x, baseP.y) = eAdd(_pEC.x, _pEC.y, baseP.x, baseP.y); //A + x*S + <z*y^n + z^2*2^n, H'>

		// - z*<1, G>
		_pEC = ecMatrG[0];
		for (uint8 i = 1; i < ecMatrG.length; i++) {
			(_pEC.x, _pEC.y) = eAdd(_pEC.x, _pEC.y, ecMatrG[i].x, ecMatrG[i].y);
		}
		(_pEC.x, _pEC.y) = eMul(_challenge.z, _pEC.x, _pEC.y);
		(_pEC.x, _pEC.y) = eInv(_pEC.x, _pEC.y);

		(baseP.x, baseP.y) = eAdd(baseP.x, baseP.y, _pEC.x, _pEC.y); //...+ -z*<1,G>
	}

	/**
	 * @dev Calculates point P, parameter for IPP verification.
	 * @param rp range proof elements.
	 * @param ecIPPP0 EC point IPPP0.
	 * @param arrUk2 array of arrU2k.
	 * @param arrInvUk2 array of inversed arrU2k elements.
	 * @return x y point coordinates.
	 */
	function getVerifyInnerProductRight(
		SlotRangeProof memory rp,
		PointEC memory ecIPPP0,
		uint256[] memory arrUk2,
		uint256[] memory arrInvUk2
	) external pure returns (uint256 x, uint256 y) {
		//P0 + <uk^2, L> + <uk^(-2), R>
		PointEC memory _ecUL;
		PointEC memory _ecUR;
		PointEC memory _pEC;
		uint8 j;
		//<uk^2, L>
		for (j = 0; j < rp.arrLk.length; j++) {
			(_pEC.x, _pEC.y) = eMul(arrUk2[j], rp.arrLk[j].x, rp.arrLk[j].y);
			(_ecUL.x, _ecUL.y) = eAdd(_ecUL.x, _ecUL.y, _pEC.x, _pEC.y);
		}
		//<uk^(-2), R>
		for (j = 0; j < rp.arrRk.length; j++) {
			(_pEC.x, _pEC.y) = eMul(arrInvUk2[j], rp.arrRk[j].x, rp.arrRk[j].y);
			(_ecUR.x, _ecUR.y) = eAdd(_ecUR.x, _ecUR.y, _pEC.x, _pEC.y);
		}
		(_pEC.x, _pEC.y) = eAdd(ecIPPP0.x, ecIPPP0.y, _ecUL.x, _ecUL.y);
		(_pEC.x, _pEC.y) = eAdd(_pEC.x, _pEC.y, _ecUR.x, _ecUR.y);
		return (_pEC.x, _pEC.y);
	}
}