Skip to content

Commit 676ea45

Browse files
furszyfurszy
committed
Merge #8: [Test] Complete test for Aggregated Shamir's Secret Sharing Scheme and DKG protocol.
d074717 [Test] Aggregated SSSS: add failed verification against the aggregated threshold signature when one of the signature shares is corrupted/invalid. (random-zebra) 78bc1c4 Add complete test for Aggregated Shamir's Secret Sharing Scheme. (furszy) 56996d3 Clean duplicate HexStr function. (furszy) 905fc4b Fix PublicKeyRecover and SignatureShare args names. (furszy) Pull request description: Going one step further over the Threshold Signatures tests, validating that the correlation and aggregation BLS properties are working properly on top of the Shamir's Secret Sharing Scheme, verifying the DKG protocol and each participant share/sig validation step described in DIP6 [BLS M-of-N Threshold Scheme and Distributed Key Generation](https://github.com/dashpay/dips/blob/master/dip-0006/bls_m-of-n_threshold_scheme_and_dkg.md) Plus corrected a duplicated `HexStr` function and few invalid function's args names. ACKs for top commit: random-zebra: ACK d074717 Tree-SHA512: 9a0acca2fecc44919292e46beea01e4c459aa15e90a65307a69d498f680907762d42f07ef823d85ef0d3d9971a12f2c9a0780984824b4951374b744b3b389eca
2 parents 4b9e9c0 + d074717 commit 676ea45

File tree

6 files changed

+230
-13
lines changed

6 files changed

+230
-13
lines changed

‎src/privatekey.cpp‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -40,7 +40,7 @@ PrivateKey PrivateKey::FromBytes(const Bytes& bytes, bool modOrder)
4040
}
4141

4242
// Construct a private key from a bytearray.
43-
PrivateKey PrivateKey::FromByteVector(const std::vector<uint8_t> bytes, bool modOrder)
43+
PrivateKey PrivateKey::FromByteVector(const std::vector<uint8_t>& bytes, bool modOrder)
4444
{
4545
return PrivateKey::FromBytes(Bytes(bytes), modOrder);
4646
}

‎src/privatekey.hpp‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -37,7 +37,7 @@ class PrivateKey {
3737
static PrivateKey FromBytes(const Bytes& bytes, bool modOrder = false);
3838

3939
// Construct a private key from a bytearray.
40-
static PrivateKey FromByteVector(const std::vector<uint8_t> bytes, bool modOrder = false);
40+
static PrivateKey FromByteVector(const std::vector<uint8_t>& bytes, bool modOrder = false);
4141

4242
// Aggregate many private keys into one (sum of keys mod order)
4343
static PrivateKey Aggregate(std::vector<PrivateKey> const &privateKeys);

‎src/test.cpp‎

Lines changed: 221 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1245,6 +1245,227 @@ TEST_CASE("Threshold Signatures") {
12451245
REQUIRE(recPk == pks[0]);
12461246
REQUIRE(recSig == sig);
12471247
}
1248+
1249+
1250+
typedef std::vector<uint8_t> RawData;
1251+
1252+
struct RecvShare {
1253+
PrivateKey skShare;
1254+
G1Element pkShare;
1255+
std::vector<G1Element> verifVec;
1256+
};
1257+
1258+
class Participant {
1259+
public:
1260+
// Unique identifier
1261+
RawData id;
1262+
// Free coefficient of S(x)
1263+
PrivateKey sk;
1264+
// Free coefficient of P(x)
1265+
G1Element pk;
1266+
// Free coefficient of SIG(x)
1267+
G2Element sig;
1268+
// Coefficients vectors
1269+
std::vector<PrivateKey> sks;
1270+
std::vector<G1Element> pks;
1271+
// Internal shares (contributions)
1272+
std::map<RawData, PrivateKey> sksShares;
1273+
std::map<RawData, G1Element> pksShares;
1274+
1275+
// Map of received shares from each participant id.
1276+
std::map<RawData, RecvShare> recvShares;
1277+
1278+
// The sk generated from the aggregation of all of the received sks shares (contributions).
1279+
PrivateKey skShare;
1280+
1281+
// Map of received aggrSig from each participant id.
1282+
std::map<RawData, G2Element> recvAggrSigs;
1283+
1284+
bool recvShareAndVerificationVector(RawData fromId, const PrivateKey& share, const std::vector<G1Element>& verifVec) {
1285+
G1Element evalPubShare = bls::Threshold::PublicKeyShare(verifVec, Bytes(id));
1286+
REQUIRE(share.GetG1Element() == evalPubShare);
1287+
recvShares.emplace(std::move(fromId), RecvShare{share, evalPubShare, verifVec});
1288+
return true;
1289+
}
1290+
void recvAggrSigsFrom(RawData& fromId, const G2Element& sigShare) {
1291+
recvAggrSigs.emplace(fromId, sigShare);
1292+
}
1293+
};
1294+
1295+
auto randPrivKey = [&]() {
1296+
RawData buf = getRandomSeed();
1297+
return PrivateKey::FromByteVector(buf, true);
1298+
};
1299+
1300+
auto randValue = [&](int mod, std::vector<int>& blockValues) {
1301+
uint8_t val = 0;
1302+
do { val = getRandomSeed()[0] % mod; } while (std::find(blockValues.begin(), blockValues.end(), val) != blockValues.end());
1303+
return val;
1304+
};
1305+
1306+
SECTION("Aggregated SSSS") {
1307+
size_t m = 3;
1308+
size_t n = 5;
1309+
1310+
// First create the participants and their secrets
1311+
std::vector<Participant> participants;
1312+
for (int i=0; i < n ; i++) {
1313+
Participant participant;
1314+
participant.id = getRandomSeed();
1315+
participant.sk = randPrivKey();
1316+
participant.pk = participant.sk.GetG1Element();
1317+
1318+
// Create the vectors' coefficients
1319+
participant.sks.emplace_back(participant.sk);
1320+
participant.pks.emplace_back(participant.pk);
1321+
for (int j = 0; j < (m-1); j++) {
1322+
auto sk = randPrivKey();
1323+
participant.sks.emplace_back(sk);
1324+
participant.pks.emplace_back(sk.GetG1Element());
1325+
}
1326+
participants.emplace_back(participant);
1327+
}
1328+
1329+
// Second, create shares for every other participant
1330+
for (Participant& participant : participants) {
1331+
for (int j=0; j < n; j++) {
1332+
RawData id = participants[j].id;
1333+
participant.sksShares.emplace(id, bls::Threshold::PrivateKeyShare(participant.sks, Bytes(id)));
1334+
participant.pksShares.emplace(id, bls::Threshold::PublicKeyShare(participant.pks, Bytes(id)));
1335+
REQUIRE(participant.sksShares[id].GetG1Element() == participant.pksShares[id]);
1336+
}
1337+
}
1338+
1339+
// Third, send shares and verification vectors
1340+
for (Participant& participant : participants) {
1341+
for (int j=0; j < n; j++) {
1342+
auto& recipient = participants[j];
1343+
RawData destId = recipient.id;
1344+
// S(x) evaluated in participant1.id.
1345+
PrivateKey skShare = participant.sksShares.at(destId);
1346+
// Participant P(x) coefficients.
1347+
std::vector<G1Element> verificationVector = participant.pks;
1348+
// Now let's verify skShare with the verification vector.
1349+
// evaluating the verification vector with the participant id.
1350+
recipient.recvShareAndVerificationVector(participant.id, skShare, verificationVector);
1351+
}
1352+
}
1353+
1354+
// Fourth, now that everyone has everyone's shares and verification vectors, let's aggregate all of them to create each aggregated sk
1355+
// This is done aggregating every received sk share + the participant S(id) own share.
1356+
// Then verify it against the evaluated Pa(id)
1357+
for (Participant& participant : participants) {
1358+
std::vector<PrivateKey> skSharedPrivKeys;
1359+
std::vector<G1Element> pkShares;
1360+
for (const auto& sharesById : participant.recvShares) {
1361+
skSharedPrivKeys.emplace_back(sharesById.second.skShare);
1362+
pkShares.emplace_back(sharesById.second.pkShare);
1363+
}
1364+
PrivateKey aggregatedSharedKey = PrivateKey::Aggregate(skSharedPrivKeys);
1365+
// Now let's verify that the public key of Sa(participant2_id) is equal to Pa(participant2_id)
1366+
// For that.. let's aggregate all of the verification vectors evaluated at participant2_id.
1367+
G1Element aggregatedPk;
1368+
for (const auto& pkShare : pkShares) {
1369+
aggregatedPk = !aggregatedPk.IsValid() ? pkShare : aggregatedPk + pkShare;
1370+
}
1371+
REQUIRE(aggregatedSharedKey.GetG1Element() == aggregatedPk);
1372+
participant.skShare = aggregatedSharedKey;
1373+
}
1374+
1375+
// Fifth, now that everyone has its own aggrKey, let's sign a common message with it and check if can everyone can recover the SIGa() free coefficient.
1376+
// Then verify that the recovered G2Element validates with the recovered G1Element (lagrange interpolation results for SIGa() and Pa() respectively)
1377+
1378+
// Let's aggregate all the verification vectors to obtain Pa():
1379+
std::vector<G1Element> finalVerifVector(participants[0].pks);
1380+
for (int j = 1; j < participants.size(); j++) {
1381+
for (int i = 0; i < finalVerifVector.size(); i++) {
1382+
finalVerifVector[i] += participants[j].pks.at(i);
1383+
}
1384+
}
1385+
1386+
// Data to be signed.
1387+
std::vector<uint8_t> msgHash = getRandomSeed();
1388+
for (auto& participant : participants) {
1389+
// Load SiG(0) value for each participant
1390+
participant.sig = bls::Threshold::Sign(participant.sk, Bytes(msgHash));
1391+
REQUIRE(bls::Threshold::Verify(participant.pk, Bytes(msgHash), {participant.sig}));
1392+
// Craft the participant.skShare sig
1393+
G2Element aggrSig = bls::Threshold::Sign(participant.skShare, Bytes(msgHash));
1394+
// Send it to every other participant which will receive the
1395+
// aggrSig and validate that corresponds to Pa() --> checking Pa(id) == participant.aggrPk
1396+
G1Element aggrPk = bls::Threshold::PublicKeyShare(finalVerifVector, Bytes(participant.id));
1397+
REQUIRE(aggrPk == participant.skShare.GetG1Element());
1398+
REQUIRE(bls::Threshold::Verify(aggrPk, Bytes(msgHash), {aggrSig}));
1399+
for (auto& recipient : participants) {
1400+
recipient.recvAggrSigsFrom(participant.id, aggrSig);
1401+
}
1402+
}
1403+
1404+
// Let's aggregate all the SIG(0) values to obtain SIGa(0)
1405+
// This will be checked for equality against the recovered threshold signature
1406+
G2Element finalSIG = participants[0].sig;
1407+
for (int j = 1; j < participants.size(); j++) {
1408+
finalSIG += participants[j].sig;
1409+
}
1410+
1411+
// Now that everyone has everyone's sigs, let's take a participant at random and remove some sigs, then try to recover and validate SIGa(0)
1412+
for (int i=0; i < 10; i++) {
1413+
std::vector<int> blockedParticipants;
1414+
Participant p = participants[randValue((int)participants.size(), blockedParticipants)];
1415+
// Block two participants at random
1416+
blockedParticipants.emplace_back(randValue((int)participants.size(), blockedParticipants));
1417+
blockedParticipants.emplace_back(randValue((int)participants.size(), blockedParticipants));
1418+
std::vector<RawData> blockedIds;
1419+
for (const auto& pos : blockedParticipants) {
1420+
blockedIds.emplace_back(participants[pos].id);
1421+
}
1422+
1423+
// Gather sigs and ids.
1424+
std::vector<G2Element> aggrSigs;
1425+
std::vector<Bytes> ids;
1426+
for (const auto& recvSigShare : p.recvAggrSigs) {
1427+
if (std::find(blockedIds.begin(), blockedIds.end(), recvSigShare.first) != blockedIds.end()) continue;
1428+
ids.emplace_back(recvSigShare.first);
1429+
aggrSigs.emplace_back(recvSigShare.second);
1430+
}
1431+
1432+
REQUIRE(aggrSigs.size() == m);
1433+
1434+
G2Element freeCoefficientSigs = bls::Threshold::SignatureRecover(aggrSigs, ids);
1435+
REQUIRE(freeCoefficientSigs == finalSIG);
1436+
// This will validate against Pa(0)!
1437+
G1Element freeCoefficientPks = finalVerifVector[0];
1438+
REQUIRE(bls::Threshold::Verify(freeCoefficientPks, Bytes(msgHash), freeCoefficientSigs));
1439+
1440+
// And.. as a final check, let's craft Sa(0)
1441+
std::vector<PrivateKey> aggrKeys;
1442+
std::vector<Bytes> ids3;
1443+
for (const auto& participant : participants) {
1444+
if (std::find(blockedIds.begin(), blockedIds.end(), participant.id) != blockedIds.end()) continue;
1445+
aggrKeys.emplace_back(participant.skShare);
1446+
ids3.emplace_back(participant.id);
1447+
}
1448+
// Now recover the free coefficient of Sa()
1449+
PrivateKey finalKey = bls::Threshold::PrivateKeyRecover(aggrKeys, ids3);
1450+
REQUIRE(finalKey.GetG1Element() == freeCoefficientPks);
1451+
REQUIRE(bls::Threshold::Sign(finalKey, Bytes(msgHash)) == freeCoefficientSigs);
1452+
1453+
// Now let's add one valid sig share and check that can recover the free coefficient correctly.
1454+
Participant extraParticipant = participants[blockedParticipants.back()];
1455+
auto extraRecvAggrSigs = p.recvAggrSigs[extraParticipant.id];
1456+
ids.emplace_back(extraParticipant.id);
1457+
aggrSigs.emplace_back(extraRecvAggrSigs);
1458+
G2Element freeCoefficientSigs2 = bls::Threshold::SignatureRecover(aggrSigs, ids);
1459+
REQUIRE(freeCoefficientSigs2.IsValid());
1460+
REQUIRE(bls::Threshold::Verify(freeCoefficientPks, Bytes(msgHash), freeCoefficientSigs2));
1461+
1462+
// Now let's modify one sig share, aggregate again, and check that verification fails
1463+
aggrSigs[0] += G2Element::Generator();
1464+
G2Element freeCoefficientSigs3 = bls::Threshold::SignatureRecover(aggrSigs, ids);
1465+
REQUIRE(freeCoefficientSigs3.IsValid());
1466+
REQUIRE(!bls::Threshold::Verify(freeCoefficientPks, Bytes(msgHash), freeCoefficientSigs3));
1467+
}
1468+
}
12481469
}
12491470

12501471
int main(int argc, char* argv[])

‎src/threshold.cpp‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -277,8 +277,8 @@ namespace bls {
277277
return Poly::Evaluate(pks, id);
278278
}
279279

280-
G1Element Threshold::PublicKeyRecover(const std::vector<G1Element>& sks, const std::vector<Bytes>& ids) {
281-
return Poly::LagrangeInterpolate(sks, ids);
280+
G1Element Threshold::PublicKeyRecover(const std::vector<G1Element>& pks, const std::vector<Bytes>& ids) {
281+
return Poly::LagrangeInterpolate(pks, ids);
282282
}
283283

284284
G2Element Threshold::SignatureShare(const std::vector<G2Element>& sigs, const Bytes& id) {

‎src/threshold.hpp‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -16,9 +16,9 @@ namespace bls {
1616
PrivateKey PrivateKeyRecover(const std::vector<PrivateKey>& sks, const std::vector<Bytes>& ids);
1717

1818
G1Element PublicKeyShare(const std::vector<G1Element>& pks, const Bytes& id);
19-
G1Element PublicKeyRecover(const std::vector<G1Element>& sks, const std::vector<Bytes>& ids);
19+
G1Element PublicKeyRecover(const std::vector<G1Element>& pks, const std::vector<Bytes>& ids);
2020

21-
G2Element SignatureShare(const std::vector<G2Element>& sks, const Bytes& id);
21+
G2Element SignatureShare(const std::vector<G2Element>& sigs, const Bytes& id);
2222
G2Element SignatureRecover(const std::vector<G2Element>& sigs, const std::vector<Bytes>& ids);
2323

2424
G2Element Sign(const PrivateKey& privateKey, const Bytes& vecMessage);

‎src/util.hpp‎

Lines changed: 3 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -53,7 +53,7 @@ class Util {
5353
public:
5454
static void Hash256(uint8_t* output, const uint8_t* message,
5555
size_t messageLen) {
56-
md_map_sh256(output, message, messageLen);
56+
md_map_sh256(output, message, (int) messageLen);
5757
}
5858

5959
static std::string HexStr(const uint8_t* data, size_t len) {
@@ -65,11 +65,7 @@ class Util {
6565
}
6666

6767
static std::string HexStr(const std::vector<uint8_t> &data) {
68-
std::stringstream s;
69-
s << std::hex;
70-
for (size_t i=0; i < data.size(); ++i)
71-
s << std::setw(2) << std::setfill('0') << static_cast<int>(data[i]);
72-
return s.str();
68+
return HexStr(data.data(), data.size());
7369
}
7470

7571
/*
@@ -104,7 +100,7 @@ class Util {
104100
/*
105101
* Converts a hex string into a vector of bytes.
106102
*/
107-
static std::vector<uint8_t> HexToBytes(const std::string hex) {
103+
static std::vector<uint8_t> HexToBytes(const std::string& hex) {
108104
if (hex.size() % 2 != 0) {
109105
throw std::invalid_argument("Invalid input string, length must be multple of 2");
110106
}

0 commit comments

Comments
 (0)