// 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* + b*<1/s, H> + a*b*Q PointEC memory _pEC; (ecRight.x, ecRight.y) = eMul(rp.ua, ecGk.x, ecGk.y); // a* (_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* + b*<1/s, H> + a*b*Q. * @param rightVerIPP right part of IPP: P0 + + * @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 . */ 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> + . */ 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> + 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> + // 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*<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 + + PointEC memory _ecUL; PointEC memory _ecUR; PointEC memory _pEC; uint8 j; // 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); } // 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); } }