Confidential assets in EVM
The Confidential assets paper presented by Andrew Poelstra, Adam Back, Mark Friedenbach, Gregory Maxwell and Pieter Wuille describes the confidential assets implementation in Bitcoin. Published in 2016, the paper introduces the concept of confidential amounts, which allows users to hide the transaction amounts while still preserving the integrity of the blockchain. It uses the Pedersen Commitment and Back-Maxwell range proofs to hide amounts and owner public key into one elliptic curve point. Using such an approach we can go away from storing public amounts in UTXO placing elliptic point into instead.
The goal of that article is to explain the implementation of described solution in terms of EVM compatible system — using Solidity smart contracts. Also there will be a Golang implementation provided.
Lets start from theory
Pedersen commitment is an elliptic point constructed as C = aH + rG where the a can be an amount and r will be an owner private key. There is no way to reveal a or r until someone provides it as it is.
Basically, the confidential assets works in the following way: imagine we have an Alice that wants to send 5 ETH to Bob. Alice owns a UTXO that stores commitment to 5 ETH C1. Then, Bob, as a receiver, creates the commitment C2 to the 5 ETH that he wants to receive. After, they are constructing a transaction that spends C1 into output C2. Onchain, we have to verify that the resulting input and output amounts are equal an no one tries to scam our system by minting tokens from air. As an elliptic curve point supports an addition operation we need to add the C1 and reverse point С2' (lets define that operation as “-”). So the C = C1 — C2 = 5*H + rAlice*G — 5*H — rBob*G = (rAlice — rBob) * G. Then, to verify the correctness of provided inputs and outputs we need to provide the signature for public key (rAlice — rBob) * G. If the amounts is not equal there will be no way to provide such signature. So, the correctness of signature means that Alice and Bob know their private keys of commitments and also that input minus output amounts equal to zero. The most suitable way to provide described signature is to use aggregated Schnoor signatures where Bob and Alice can construct signatures by itself and then aggregate them to get an aggregated signature for public key (rAlice — rBob) * G.
Briefly, lets explain how the Schnoor signature works:
PubKey = rG
----
Signing
k = rand()
R = kG
s = k - Hash(msg|P|R)*r
Sig = <s, R>
----
Verification
Check that sG = R - Hash(msg|P|R)*P
----
Aggregation
PubAggr = PubAlice + PubBob
SigAlice = <kAlice - Hash(msg|PubAggr|RArrg)*rAlice, RAlice>
SigBob = <kBob - Hash(msg|PubAggr|RArrg)*rBob, RBob>
SigAggr = SigAlice + SigBob = < kAlice+kBob - Hash(msg|PubAggr|RArrg)*(rAlice+rBob), RAlice+RBob >Note that the knowledge of aggregated public key and R by both sides is required.
The last thing need to be discussed before implementing is the range proofs. The blockchain systems (Ethereum for example) uses uint256 for storing amounts. So we are working in the 2^n (n = 256) field and additionally we are working in selected elliptic curve field (less then 2²⁵⁶) that can be overflowed by addition and subtraction operations.
As an example, lets use the field with order 10. If we have an input amount 6 and output amounts in two commitments 9 and 7 the result of subtraction will be zero [6-9-7=0 (mod 10)]. So we will have 10 tokens minted from air. In order to prevent it we have to reduce the field order for amounts — by providing the zero knowledge that stored amount lies in [0; 2^k) where k < n.
The confidential assets paper describes the Back-Maxwell range proof that provides a zero knowledge proof with O(k) size. Also there is more efficient proof exists — Bulletproof, that creates a proof with O(log k) size.
The described Back-Maxwell rangeproof from confidential assets paper works for any positional numeral system with any base and can be simply modified for usage with base 2.
Golang implementation
You can explore the Golang implementation of Back-Maxwell rangeproof there. Here is the example of usage (from pedersen_test.go):
func TestPedersenCommitment(t *testing.T) {
proof, commitment, prv, err := CreatePedersenCommitment(10, 5)
if err != nil {
panic(err)
}
reconstructedCommitment := PedersenCommitment(big.NewInt(10), prv)
fmt.Println("Constructed commitment with prv key: " + reconstructedCommitment.String())
fmt.Println("Response commitment: " + commitment.String())
fmt.Println("Private Key: " + hexutil.Encode(prv.Bytes()))
if err = VerifyPedersenCommitment(commitment, proof); err != nil {
panic(err)
}
}Note, that Back-Maxwell rangeproof creates the commitment for any give amount that lies in defined interval and as the result gives the commitment and private key for that commitment.
Elliptic Curve
Before implementing the desired system in Solidity we need to choose the elliptic curve to work with. The obvious solution is to use native Ethereum secp256k1 curve, but unfortunately, Solidity does not provides the fast way to perform elliptic computations on it. Implementing addition and multiplication by ourself leads to the gas-out-of-range problem — such operations costs a lot. So wee need to use already precompiled elliptic curve contracts from EIP-196 — alt_bn128.
Lets create a simple library for alt_bn128 usage:
// SPDX-License-Identifier: MIT
pragma solidity >=0.6.0;
/**
* Referenced from https://github.com/kendricktan/heiswap-dapp/blob/master/contracts/AltBn128.sol
*/
library EllipticCurve {
/// @notice ECPoint stores the elliptic curve point coordinates.
struct ECPoint {
uint256 _x;
uint256 _y;
}
/// @notice Pedersen commitment base point H
uint256 public constant Hx =
0x2cb8b246dbf3d5b5d3e9f75f997cd690d205ef2372292508c806d764ee58f4db;
uint256 public constant Hy =
0x1fd7b632da9c73178503346d9ebbb60cc31104b5b8ce33782eaaecaca35c96ba;
/// @notice Pedersen commitment base point G
uint256 public constant Gx =
0x2f21e4931451bb6bd8032d52b90a81859fd1abba929df94621a716ebbe3456fd;
uint256 public constant Gy =
0x171c62d5d61cc08d176f2ea3fe42314a89b0196ea6c68ed1d9a4c426d47c3232;
/// @notice Number of elements in the field (often called `q`)
/// n = n(u) = 36u^4 + 36u^3 + 18u^2 + 6u + 1
uint256 public constant N =
0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001;
/// @notice p = p(u) = 36u^4 + 36u^3 + 24u^2 + 6u + 1
/// Field Order
uint256 public constant P =
0x30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd47;
/// @notice (p+1) / 4
uint256 public constant A =
0xc19139cb84c680a6e14116da060561765e05aa45a1c72a34f082305b61f3f52;
function ecAdd(
ECPoint memory _p1,
ECPoint memory _p2
) public view returns (ECPoint memory) {
uint256[4] memory _i = [_p1._x, _p1._y, _p2._x, _p2._y];
uint256[2] memory _r;
assembly {
// call ecadd precompile
// inputs are: x1, y1, x2, y2
if iszero(staticcall(not(0), 0x06, _i, 0x80, _r, 0x40)) {
revert(0, 0)
}
}
return ECPoint(_r[0], _r[1]);
}
function ecMul(
ECPoint memory _p,
uint256 s
) public view returns (ECPoint memory) {
// With a public key (x, y), this computes p = scalar * (x, y).
uint256[3] memory _i = [_p._x, _p._y, s];
uint256[2] memory _r;
assembly {
// call ecmul precompile
// inputs are: x, y, scalar
if iszero(staticcall(sub(gas(), 2000), 0x07, _i, 0x60, _r, 0x40)) {
revert(0, 0)
}
}
return ECPoint(_r[0], _r[1]);
}
function ecBaseMul(uint256 s) public view returns (ECPoint memory) {
// With a public key (x, y), this computes p = scalar * (x, y).
uint256[3] memory _i = [Gx, Gy, s];
uint256[2] memory _r;
assembly {
// call ecmul precompile
// inputs are: x, y, scalar
if iszero(staticcall(sub(gas(), 2000), 0x07, _i, 0x60, _r, 0x40)) {
revert(0, 0)
}
}
return ECPoint(_r[0], _r[1]);
}
function ecSub(
ECPoint memory _p1,
ECPoint memory _p2
) internal view returns (ECPoint memory) {
_p2 = ecNeg(_p2);
return ecAdd(_p1, _p2);
}
function ecNeg(ECPoint memory _p) internal pure returns (ECPoint memory) {
if (_p._x == 0 && _p._y == 0) return _p;
return ECPoint(_p._x, P - (_p._y % P));
}
function onCurve(ECPoint memory _p) public pure returns (bool) {
uint256 beta = mulmod(_p._x, _p._x, P);
beta = mulmod(beta, _p._x, P);
beta = addmod(beta, 3, P);
return beta == mulmod(_p._y, _p._y, P);
}
}It uses the staticcalls to 0x06 and 0x07 for point addition and scalar multiplication. Also note, that H and G points recommended to be constructed by trusted setup — in such way that no one by itself should not be able to reveal the scalar part.
Implementation definitions
As confidential assets works over the UTXO model, we need an UTXO smart contract that will emulate UTXOs in terms of EVM system. Let’s define the following interface (as an example we will work with EVM native asset, but it can be extended to be used with any possible asset):
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
import "../EllipticCurve.sol";
/**
* @title UTXO-ETH interface
*/
interface IUTXO {
/// @notice UTXO is a base structure that stores the Pedersen commitment to the amount and _valuable flag.
struct UTXO {
EllipticCurve.ECPoint _c;
bool _valuable;
}
/// @notice Proof contains the data to verify Back-Maxwell range proof for Pedersen commitment.
struct Proof {
uint256 _e0;
EllipticCurve.ECPoint[] _c;
uint256[] _s;
}
/// @notice Witness contains the aggregated Schnorr signature for transfer operation.
struct Witness {
EllipticCurve.ECPoint _r;
uint256 _s;
}
/// @notice Initializing new UTXO (without deposit). Use to create the transfer output.
/// No information about amount is required. The Back-Maxwell range proof should be valid.
/// @param _commitment Pedersen commitment point.
/// @param _proof Back-Maxwell range proof.
function initialize(
EllipticCurve.ECPoint memory _commitment,
Proof memory _proof
) external returns (uint256);
/// @notice Deposit ETH and create corresponding UTXO.
/// @param _publicKey Public key: `prv * G`.
/// @param _witness Schnorr signature for provided public key.
function deposit(
EllipticCurve.ECPoint memory _publicKey,
Witness memory _witness
) external payable returns (uint256);
/// @notice Withdraw UTXO.
/// @param _id UTXO index.
/// @param _to Receiver address
/// @param _amount amount in wei to withdraw.
/// @param _witness Schnorr signature for UTXO public key.
function withdraw(
uint256 _id,
address payable _to,
uint256 _amount,
Witness memory _witness
) external;
/// @notice Transfer ETH (anonymous)
/// @param _inputs Input UTXO index.
/// @param _outputs Output UTXO index.
/// @param _witness Schnorr signature for aggregated (output - input) public key.
function transfer(
uint256[] memory _inputs,
uint256[] memory _outputs,
Witness memory _witness
) external;
}The UTXO structure represents a simple UTXO that stores an elliptic point and valuable field , that defines does our UTXO contain any value or it has been spent or has not been activated yet.
The Proof structure represents the Back-Maxwell rangeproof for the committed amount. It will be used only once, during commitment creation.
The Witness structure represents the Schnoor signature that will be used in transfer operation and deposit operations to verify that users know the private keys of commitments.
Also, let’s describe the Back-Maxwell rangeproof verification in Solidity:
function verifyRangeProof(
EllipticCurve.ECPoint memory _commitment,
Proof memory _proof
) public view {
require(_proof._c.length == N, "invalid _c length got: ");
require(_proof._s.length == N, "invalid _s length got: ");
EllipticCurve.ECPoint[] memory _r = new EllipticCurve.ECPoint[](N);
for (uint256 _i = 0; _i < N; _i++) {
EllipticCurve.ECPoint memory _sig = EllipticCurve.ecBaseMul(
_proof._s[_i]
);
EllipticCurve.ECPoint memory _p = H.ecMul(pow2(_i));
_p = _proof._c[_i].ecSub(_p);
_p = _p.ecMul(_proof._e0);
_p = _sig.ecSub(_p);
bytes32 _ei = hash(abi.encodePacked(_p._x, _p._y));
_r[_i] = _proof._c[_i].ecMul(uint256(_ei));
}
bytes32 _e0 = hashPoints(_r);
EllipticCurve.ECPoint memory _com = _proof._c[0];
for (uint _i = 1; _i < N; _i++) {
_com = _com.ecAdd(_proof._c[_i]);
}
require(uint256(_e0) == _proof._e0, "failed to verify proof: e0");
require(_com._x == _commitment._x, "failed to verify proof: x");
require(_com._y == _commitment._y, "failed to verify proof: y");
}It is the same implementation that you can explore in Golang repository. Before verification we of course perform checks for the size of provided proof by:
require(_proof._c.length == N, "invalid _c length got: ");
require(_proof._s.length == N, "invalid _s length got: ");The N is the global constant parameter that defines the field order of amounts (2^N).
Also, in proof verification we are using the calls to our elliptic curve library, so the following definition should be provided:
using EllipticCurve for EllipticCurve.ECPoint;Usage Example
To take an advantage of our confidential assets system firstly you need to deposit some tokens into.
The withdrawal flow looks like the same:
Of course, such transactions will be public and everyone can see how many tokens you have been deposited or withdrawn into/from our contract. But all transfers inside will be performed with hidden amounts so no one can answer the question how many tokens do you own or who did you send money to.
Unfortunately, the transfer flow have to be more complicated to achieve anonymity:
Note that during the transfer Alice or Bob should reveal their public key to the other side that is required for Schnoor signature generation. At first sight it leads the potential deanonymization of commitment amount but if you will use the several inputs and outputs you will have to reveal only aggregated public key and there will not be any chance to unhide the amounts. For example, in our case Bob can use two outputs C2_1 = 2*H+r2_1*G, C2_2 = 3*H+r2_2*G where the sum is equal to 5 ETH, but only sharing of (r2_1 + r2_2)*G is required.
The resulting implementation of confidential assets in Solidity you can explore there: github.com/olegfomenko/utxo.
If you have any questions or suggestions please mail me: oleg.fomenko@distributedlab.com