Write a Solidity function for the efficient on-chain verification of a Ring Signature.
Description
To mint a token which contains the solvency proof, the contract has to verify the Ring Signature.
The description of what is expected is available here in the 'How to verify a ring signature' section
Skills needed
Solidity advanced skills
TypeScript understanding
Hours needed
Expected working time: 4 or 6 hours
What is expected
Complete the contract in the contracts/VerifyRingSignature.sol file (if it does not exist, create it)
The contract should use Solidity ^8.20
All the .sol file you create should be under the MIT license
The verifyRingSignature function should allow anyone to verify a ring signature like it is done in our TypeScript implementation
We really emphasize that the main objective is to optimize gas consumption for this Solidity function
struct PubKey {
uint256 x;
uint256 y;
}
struct Signature {
pubKey[] ring;
uint256 c;
string message;
uint256[] responses;
}
function verifyRingSignature( Signature memory _signature ) public pure returns (bool)
In-depth technical explanation
A ring signature is: (c, r1, ..., rn)
Ring: all the public keys involved in the signing process
n: ringSize - 1
Ki (0<i<n) (secp256k1 point) -> Ki = ring[i] = public key of signer i
c (uint) -> the initial cee to start the verification from
r0, ..., rn (uint) -> all the responses generated during the signing process (1 for each member of the ring)
m (uint) -> the clear message
N: SECP256K1 order
G: SECP256K1 generator point
H: hashing function
Be careful, these are points. They do not have the same properties as integersThose functions are implemented here
The process to verify a ring signature
compute c1' = H(Ring, m, [r0*G + c*Ki]
For i in [1, n], compute: ci+1' = H(Ring, m, [ri*G + ci*Ki]
If c == H(Ring, m, [rn*G + cn*Kn], the signature is considered valid.
The TypeScript implementation
/*
G is a global constant: the generator point of SECP256K1
N is a global constant: the order of SECP256K1
.mult() is the multiplication of a point by a scalar (ex: G.mult(2n) = 2G)
.add() is the addition of two points (ex: G.add(G) = 2G)
*/
/**
* Verify a RingSignature
*
* @param c - The message digest (= keccack256(clear message))
* @param responses - The responses of the signers
* @param ring - the ring of public keys
* @param messageDigest - the hashed message
*
* @returns True if the signature is valid, false otherwise
*/
function verify(c: bigint, responses: bigint[], ring: Secp256k1Point[], messageDigest: string): boolean {
// we compute c1' = Hash(Ring, m, [r0G, c0K0])
// then, for each ci (1 < i < n), compute ci' = Hash(Ring, message, [riG + ciKi])
// (G = generator, K = ring public key)
// finally, if we substitute lastC for lastC' and c0' == c0, the signature is valid
if (ring.length === 0)
throw new Error("Ring length must be greater than 0");
if (ring.length !== responses.length) {
throw new Error("ring and responses length mismatch");
}
if (ring.length === 1) throw new Error("Ring length must be greater than 1");
// computes the cees
let lastComputedCp = computeC(
// c1'
ring,
messageDigest,
G,
N,
responses[0],
c,
ring[0],
);
for (let i = 2; i < ring.length; i++) {
// c2' -> cn'
lastComputedCp = computeC(
ring,
messageDigest,
G,
N,
responses[i - 1],
lastComputedCp,
ring[i - 1],
);
}
// return true if c0 === c0'
return (
c ===
computeC(
ring,
messageDigest,
G,
N,
responses[responses.length - 1],
lastComputedCp,
ring[ring.length - 1],
)
);
}
function computeC(
ring: Secp256k1Point[],
message: string,
G: Secp256k1Point,
N: bigint,
r: bigint,
previousC: bigint,
previousPubKey: Secp256k1Point,
): bigint {
return modulo(
BigInt(
"0x" +
keccak256(
ring +
message +
G.mult(r).add(previousPubKey.mult(previousC)).toString(),
),
),
N,
);
}
export function modulo(n: bigint, p: bigint): bigint {
const result = n % p;
return result >= 0n ? result : result + p;
}
Here are two valid signatures to test the correctness of your implementation:
LeJamon
commented
11 months ago
Write a Solidity function for the efficient on-chain verification of a Ring Signature.
Description
To mint a token which contains the solvency proof, the contract has to verify the Ring Signature. The description of what is expected is available here in the 'How to verify a ring signature' section
Skills needed
Hours needed
Expected working time: 4 or 6 hours
What is expected
contracts/VerifyRingSignature.solfile (if it does not exist, create it)verifyRingSignaturefunction should allow anyone to verify a ring signature like it is done in our TypeScript implementationThe function's signature should be :
In-depth technical explanation
A ring signature is:
(c, r1, ..., rn)Ring: all the public keys involved in the signing process n: ringSize - 1 Ki (0<i<n) (secp256k1 point) -> Ki = ring[i] = public key of signer i c (uint) -> the initial cee to start the verification from r0, ..., rn (uint) -> all the responses generated during the signing process (1 for each member of the ring) m (uint) -> the clear message
N: SECP256K1 order G: SECP256K1 generator point H: hashing function
Be careful, these are points. They do not have the same properties as integers Those functions are implemented here
The process to verify a ring signature
compute
c1' = H(Ring, m, [r0*G + c*Ki]For i in [1, n], compute:
ci+1' = H(Ring, m, [ri*G + ci*Ki]If
c == H(Ring, m, [rn*G + cn*Kn], the signature is considered valid.The TypeScript implementation
Here are two valid signatures to test the correctness of your implementation:
The second one has a size of 10