aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Makefile.am1
-rw-r--r--brandt.c20
-rw-r--r--crypto.h30
-rw-r--r--gp-scripts/mp_pub104
-rw-r--r--mp_pub.c526
-rw-r--r--test_brandt.c28
6 files changed, 699 insertions, 10 deletions
diff --git a/Makefile.am b/Makefile.am
index e0b6356..9b80791 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -10,6 +10,7 @@ libbrandt_la_SOURCES = \
10 fp_priv.c \ 10 fp_priv.c \
11 fp_pub.c \ 11 fp_pub.c \
12 mp_priv.c \ 12 mp_priv.c \
13 mp_pub.c \
13 util.c 14 util.c
14 15
15libbrandt_la_LIBADD = \ 16libbrandt_la_LIBADD = \
diff --git a/brandt.c b/brandt.c
index a05731d..ce41541 100644
--- a/brandt.c
+++ b/brandt.c
@@ -68,7 +68,7 @@ BRANDT_bidder_start (struct BRANDT_Auction *auction,
68 outcome = auction->outcome_public ? outcome_public : outcome_private; 68 outcome = auction->outcome_public ? outcome_public : outcome_private;
69 69
70 if (auction_mPlusFirstPrice == atype && n <= auction->m) 70 if (auction_mPlusFirstPrice == atype && n <= auction->m)
71 { /* fewer bidders than items to sell. every bidder won with lowest price */ 71 { /* fewer bidders than items to sell. every bidder won with lowest price */
72 struct BRANDT_Result *res; 72 struct BRANDT_Result *res;
73 if (auction->outcome_public) 73 if (auction->outcome_public)
74 { 74 {
@@ -138,7 +138,8 @@ seller_start (void *arg)
138 } 138 }
139 else if (ad->n <= ad->m) 139 else if (ad->n <= ad->m)
140 { 140 {
141 struct BRANDT_Result *res = GNUNET_new_array (ad->n, struct BRANDT_Result); 141 struct BRANDT_Result *res = GNUNET_new_array (ad->n,
142 struct BRANDT_Result);
142 143
143 weprintf ("less bidders than needed, selling for lowest price"); 144 weprintf ("less bidders than needed, selling for lowest price");
144 for (uint16_t i = 0; i < ad->n; i++) 145 for (uint16_t i = 0; i < ad->n; i++)
@@ -346,14 +347,23 @@ BRANDT_destroy (struct BRANDT_Auction *auction)
346 smc_free2 (auction->alpha, auction->n, auction->k); 347 smc_free2 (auction->alpha, auction->n, auction->k);
347 smc_free2 (auction->beta, auction->n, auction->k); 348 smc_free2 (auction->beta, auction->n, auction->k);
348 smc_free2 (auction->gamma2, auction->n, auction->k); 349 smc_free2 (auction->gamma2, auction->n, auction->k);
349 smc_free3 (auction->gamma3, auction->n, auction->n, auction->k);
350 smc_free2 (auction->delta2, auction->n, auction->k); 350 smc_free2 (auction->delta2, auction->n, auction->k);
351 smc_free3 (auction->delta3, auction->n, auction->n, auction->k);
352 smc_free2 (auction->phi2, auction->n, auction->k); 351 smc_free2 (auction->phi2, auction->n, auction->k);
353 smc_free3 (auction->phi3, auction->n, auction->n, auction->k);
354 free (auction->phiproofs3); 352 free (auction->phiproofs3);
355 smc_free1 (auction->tmpa1, auction->k); 353 smc_free1 (auction->tmpa1, auction->k);
356 smc_free1 (auction->tmpb1, auction->k); 354 smc_free1 (auction->tmpb1, auction->k);
355 if (auction->m > 0 && auction->outcome_public)
356 {
357 smc_free3 (auction->gamma3, auction->n, 2, auction->k);
358 smc_free3 (auction->delta3, auction->n, 2, auction->k);
359 smc_free3 (auction->phi3, auction->n, 2, auction->k);
360 }
361 else
362 {
363 smc_free3 (auction->gamma3, auction->n, auction->n, auction->k);
364 smc_free3 (auction->delta3, auction->n, auction->n, auction->k);
365 smc_free3 (auction->phi3, auction->n, auction->n, auction->k);
366 }
357} 367}
358 368
359 369
diff --git a/crypto.h b/crypto.h
index 4c06b4a..8291bc2 100644
--- a/crypto.h
+++ b/crypto.h
@@ -188,6 +188,26 @@ struct BRANDT_Result *mp_priv_determine_outcome (struct BRANDT_Auction *ad,
188 uint16_t *len); 188 uint16_t *len);
189 189
190 190
191void mp_pub_prep_outcome (struct BRANDT_Auction *ad);
192unsigned char *mp_pub_compute_outcome (struct BRANDT_Auction *ad,
193 size_t *buflen);
194int mp_pub_recv_outcome (struct BRANDT_Auction *ad,
195 const unsigned char *buf,
196 size_t buflen,
197 uint16_t sender);
198
199void mp_pub_prep_decryption (struct BRANDT_Auction *ad);
200unsigned char *mp_pub_decrypt_outcome (struct BRANDT_Auction *ad,
201 size_t *buflen);
202int mp_pub_recv_decryption (struct BRANDT_Auction *ad,
203 const unsigned char *buf,
204 size_t buflen,
205 uint16_t sender);
206
207struct BRANDT_Result *mp_pub_determine_outcome (struct BRANDT_Auction *ad,
208 uint16_t *len);
209
210
191/* --- Round dictionaries --- */ 211/* --- Round dictionaries --- */
192 212
193typedef void 213typedef void
@@ -245,6 +265,8 @@ static const RoundPrep handler_prep[auction_last][outcome_last][msg_last] = {
245 [outcome_public] = { 265 [outcome_public] = {
246 [msg_init] = &smc_prep_keyshare, 266 [msg_init] = &smc_prep_keyshare,
247 [msg_bid] = &smc_prep_bid, 267 [msg_bid] = &smc_prep_bid,
268 [msg_outcome] = &mp_pub_prep_outcome,
269 [msg_decrypt] = &mp_pub_prep_decryption,
248 }, 270 },
249 }, 271 },
250}; 272};
@@ -285,6 +307,8 @@ static const MsgIn handler_in[auction_last][outcome_last][msg_last] = {
285 [outcome_public] = { 307 [outcome_public] = {
286 [msg_init] = &smc_recv_keyshare, 308 [msg_init] = &smc_recv_keyshare,
287 [msg_bid] = &smc_recv_encrypted_bid, 309 [msg_bid] = &smc_recv_encrypted_bid,
310 [msg_outcome] = &mp_pub_recv_outcome,
311 [msg_decrypt] = &mp_pub_recv_decryption,
288 }, 312 },
289 }, 313 },
290}; 314};
@@ -326,6 +350,8 @@ static const MsgOut handler_out[auction_last][outcome_last][msg_last] = {
326 [outcome_public] = { 350 [outcome_public] = {
327 [msg_init] = &smc_gen_keyshare, 351 [msg_init] = &smc_gen_keyshare,
328 [msg_bid] = &smc_encrypt_bid, 352 [msg_bid] = &smc_encrypt_bid,
353 [msg_outcome] = &mp_pub_compute_outcome,
354 [msg_decrypt] = &mp_pub_decrypt_outcome,
329 }, 355 },
330 }, 356 },
331}; 357};
@@ -342,13 +368,13 @@ static const MsgOut handler_out[auction_last][outcome_last][msg_last] = {
342 * of 0 means a private outcome, while a value of 1 means public outcome. 368 * of 0 means a private outcome, while a value of 1 means public outcome.
343 */ 369 */
344static const Result handler_res[auction_last][outcome_last] = { 370static const Result handler_res[auction_last][outcome_last] = {
345 [auction_firstPrice] = { 371 [auction_firstPrice] = {
346 [outcome_private] = &fp_priv_determine_outcome, 372 [outcome_private] = &fp_priv_determine_outcome,
347 [outcome_public] = &fp_pub_determine_outcome, 373 [outcome_public] = &fp_pub_determine_outcome,
348 }, 374 },
349 [auction_mPlusFirstPrice] = { 375 [auction_mPlusFirstPrice] = {
350 [outcome_private] = &mp_priv_determine_outcome, 376 [outcome_private] = &mp_priv_determine_outcome,
351// [outcome_public] = , 377 [outcome_public] = &mp_pub_determine_outcome,
352 }, 378 },
353}; 379};
354 380
diff --git a/gp-scripts/mp_pub b/gp-scripts/mp_pub
new file mode 100644
index 0000000..9b49c13
--- /dev/null
+++ b/gp-scripts/mp_pub
@@ -0,0 +1,104 @@
1\\ From: "Fully private auctions in a constant number of rounds" (2003) by Felix Brandt pages 9-10
2
3
4\\\\\\\\\\\\
5\\ Adapt the following values to your needs
6\\\\\\\\\\\\
7
8\\ auction parameter
9M = 1
10\\ amount of bidders
11n = 2^2
12\\ amount of possible prices
13k = 2^4
14\\ randomize bids (change to something static, if you like)
15bid = vector(n,i,random(k)+1)
16\\bid = vector(n,i,n-i+1) \\ first bidder wins
17\\bid = vector(n,i,i) \\ last bidder wins
18\\bid = vector(n,i,(i+1)%2) \\ second bidder wins (with ties)
19
20\\ prime finite field setup (result may be ambiguous if your prime is too small, 4*n*k seems to work fine)
21\\q = prime(2^12)
22\\ 512bit prime:
23q = 12513167897862218633350152063959653109080007724899931588313481862015596111526299656550478091592311160908219544364381660940520774223634480285451547911456579
24\\ 2048bit prime:
25\\q = 31905233907400964621684499856844075173802000556075101303613351426740101897961025481077892281365444367883091980681462491724119317344478120131982416132058173572772607966572720945691237876256074322291459510766147107539260048324345382562673904236506104922357079761457605045674628331006193183908801308817507027556440703972646885207099302085383887085776295396030033300833460743425162726394704256227108175491673135830378272029374848904772902525385997099641162537271298634032011458617811670193865244028195169383991286227040469186123958053863978710424421008752927011390777187889943940479064193231486057910586526439884046593027
26\\ 3072bit prime:
27\\q = 5175054779340588353586849786144680366505563673837334790820581054294754700842534366479020240016540005621125885927641963390708863183739793208880756653713659686139600715884857385144475261507869935694699816011948585170171332029002674283854825650901258017026965486602158722052719421343475066067509485302858041368266332080773331946039572497794442067057597327877030322029413318847025776818839927761556478107499002213648377029201340152459685610920194363099878398871001275336711869213616313858200583491913270052111910410231060407633125816386053759634073500319223989240814564691163285769745840521560940666058800931070258886096469889796899266014106833050284032035948051974659796051419431527095503586817863043771919051402039741075037010264761045992285666560487072740505566408086913711094879155498223636912657852688296081316652278801546924079650897913388978423388839346058027184069633227966507908979049369500450630036982661231208087459099
28g = Mod(2, q)
29
30\\ get generator / primitive element for G_q
31\\var = 'x \\ copy pasta from internet
32\\pe=ffgen(minpoly(ffprimroot(ffgen(ffinit(p,1))),var),var) \\ get primitive element
33\\1/(fforder(pe) == p-1) \\ error out, if ord(pe) is wrong
34\\g = Mod(eval(Str(pe))^2, p) \\ dirty hack to convert t_FFELEM to t_INT
35
36\\\\\\\\\\\\
37\\ PROLOG
38\\\\\\\\\\\\
39
40\\ private keys of agents
41x = vector(n,i,random(q))
42\\ public keyshares of agents
43yshares = vector(n,i,g^x[i])
44\\ shared public key
45y = prod(X=1,n,yshares[X])
46
47\\ first index level = owning agent id (additive share)
48\\ second index level = agent id, price id
49m = matrix(n,k,a,b,random(q))
50
51\\ index = owning agent id, price id
52r = matrix(n,k,i,j,random(q))
53\\ bid matrix
54b = matrix(n,k,i,j,g^(bid[i]==j))
55
56\\\\\\\\\\\\
57\\ ROUND1
58\\\\\\\\\\\\
59
60\\ encrypted bids
61alpha = matrix(n,k,i,j, b[i,j]*y^r[i,j])
62beta = matrix(n,k,i,j, g^r[i,j])
63
64\\\\\\\\\\\\
65\\ ROUND2
66\\\\\\\\\\\\
67
68\\ multiplicative shares
69\\ first index level = owning agent id (multiplicative share)
70\\ second index level = agent id, price id
71GammaPrice = matrix(n,k,a,j, ( prod(h=1,n,prod(d=j,k,alpha[h,d]) * prod(d=j+1,k,alpha[h,d])) / g^(2*M+1) )^(m[a,j]) )
72DeltaPrice = matrix(n,k,a,j, ( prod(h=1,n,prod(d=j,k, beta[h,d]) * prod(d=j+1,k, beta[h,d])) )^(m[a,j]) )
73GammaWinner = matrix(n,k,a,j, ( GammaPrice[a,j] * prod(h=1,n,prod(d=j+1,k,alpha[h,d]^(2^(h-1)))) ))
74DeltaWinner = matrix(n,k,a,j, ( DeltaPrice[a,j] * prod(h=1,n,prod(d=j+1,k, beta[h,d]^(2^(h-1)))) ))
75
76\\\\\\\\\\\\
77\\ ROUND3
78\\\\\\\\\\\\
79
80\\ multiplicative shares (decryption)
81\\ first index level = owning agent id (multiplicative share)
82\\ second index level = agent id, price id
83PhiPrice = matrix(n,k,a,j, prod(h=1,n,DeltaPrice[h,j])^x[a] )
84PhiWinner = matrix(n,k,a,j, prod(h=1,n,DeltaWinner[h,j])^x[a] )
85
86\\\\\\\\\\\\
87\\ EPILOG
88\\\\\\\\\\\\
89
90\\ winner matrix
91vPrice = lift(vector(k,j, prod(i=1,n,GammaPrice[i,j]) / prod(i=1,n,PhiPrice[i,j]) ))
92vWinner = vector(k,j, prod(i=1,n,GammaWinner[i,j]) / prod(i=1,n,PhiWinner[i,j]) )
93
94print("bids are: ", bid)
95
96price = -1
97for(j=1,k, if(vPrice[j]==1, price=j))
98
99winners = vector(i=1,M,-1)
100winp = binary(znlog(vWinner[price],g)/n)
101cur = 1;
102for(i=1,length(winp), if(winp[length(winp)-i+1]==1,winners[cur]=i;cur=cur+1))
103print("Winners are ", winners)
104print("And the price is ", price)
diff --git a/mp_pub.c b/mp_pub.c
new file mode 100644
index 0000000..7c2a373
--- /dev/null
+++ b/mp_pub.c
@@ -0,0 +1,526 @@
1/* This file is part of libbrandt.
2 * Copyright (C) 2016 GNUnet e.V.
3 *
4 * libbrandt is free software: you can redistribute it and/or modify it under
5 * the terms of the GNU General Public License as published by the Free Software
6 * Foundation, either version 3 of the License, or (at your option) any later
7 * version.
8 *
9 * libbrandt is distributed in the hope that it will be useful, but WITHOUT ANY
10 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
11 * A PARTICULAR PURPOSE. See the GNU General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public License along with
14 * libbrandt. If not, see <http://www.gnu.org/licenses/>.
15 */
16
17/**
18 * @file mp_pub.c
19 * @brief Implementation of the m+1st price public outcome algorithm.
20 * @author Markus Teich
21 */
22
23#include "platform.h"
24
25#include <gcrypt.h>
26
27#include "crypto.h"
28#include "internals.h"
29#include "util.h"
30
31
32void
33mp_pub_prep_outcome (struct BRANDT_Auction *ad)
34{
35 gcry_mpi_t factor = gcry_mpi_new (256);
36 gcry_mpi_point_t subtr = gcry_mpi_point_new (0);
37 gcry_mpi_point_t tmpa = gcry_mpi_point_new (0);
38 gcry_mpi_point_t tmpb = gcry_mpi_point_new (0);
39 gcry_mpi_point_t *tlta1;
40 gcry_mpi_point_t *tltb1;
41 gcry_mpi_point_t **tlta2;
42 gcry_mpi_point_t **tltb2;
43 gcry_mpi_point_t **tlta3;
44 gcry_mpi_point_t **tltb3;
45
46 ad->gamma3 = smc_init3 (ad->n, 2, ad->k);
47 brandt_assert (ad->gamma3);
48
49 ad->delta3 = smc_init3 (ad->n, 2, ad->k);
50 brandt_assert (ad->delta3);
51
52 /* create temporary lookup tables with partial sums */
53 tlta1 = smc_init1 (ad->k);
54 tltb1 = smc_init1 (ad->k);
55 tlta2 = smc_init2 (ad->n, ad->k);
56 tltb2 = smc_init2 (ad->n, ad->k);
57 tlta3 = smc_init2 (ad->n, ad->k);
58 tltb3 = smc_init2 (ad->n, ad->k);
59
60 /* temporary lookup table for first summand (building ladder of bids) */
61 for (uint16_t i = 0; i < ad->n; i++)
62 {
63 smc_sums_partial (tlta3[i], ad->alpha[i], ad->k, 1, 1);
64 smc_sums_partial (tltb3[i], ad->beta[i], ad->k, 1, 1);
65 for (uint16_t j = 0; j < ad->k; j++)
66 {
67 gcry_mpi_ec_sub (tlta2[i][j],
68 tlta3[i][ad->k - 1],
69 tlta3[i][j],
70 ec_ctx);
71 gcry_mpi_ec_sub (tltb2[i][j],
72 tltb3[i][ad->k - 1],
73 tltb3[i][j],
74 ec_ctx);
75 }
76 brandt_assert (!ec_point_cmp (ec_zero, tlta2[i][ad->k - 1]));
77 brandt_assert (!ec_point_cmp (ec_zero, tltb2[i][ad->k - 1]));
78 }
79 for (uint16_t j = 0; j < ad->k; j++)
80 {
81 /* 2L - 2I */
82 smc_sum (tmpa, &tlta2[0][j], ad->n, ad->k);
83 smc_sum (tmpb, &tltb2[0][j], ad->n, ad->k);
84 gcry_mpi_ec_mul (tlta1[j], GCRYMPI_CONST_TWO, tmpa, ec_ctx);
85 gcry_mpi_ec_mul (tltb1[j], GCRYMPI_CONST_TWO, tmpb, ec_ctx);
86
87 /* I */
88 smc_sum (tmpa, &ad->alpha[0][j], ad->n, ad->k);
89 smc_sum (tmpb, &ad->beta[0][j], ad->n, ad->k);
90
91 /* 2L - 2I + I = 2L - I */
92 gcry_mpi_ec_add (tlta1[j], tlta1[j], tmpa, ec_ctx);
93 gcry_mpi_ec_add (tltb1[j], tltb1[j], tmpb, ec_ctx);
94 }
95 brandt_assert (!ec_point_cmp (tmpa, tlta1[ad->k - 1]));
96 brandt_assert (!ec_point_cmp (tmpb, tltb1[ad->k - 1]));
97
98 /* compute subtrahend: (2M+1)G */
99 gcry_mpi_set_ui (factor, ad->m);
100 gcry_mpi_lshift (factor, factor, 1);
101 gcry_mpi_add_ui (factor, factor, 1);
102 gcry_mpi_ec_mul (subtr, factor, ec_gen, ec_ctx);
103
104 /* compute gamma and delta for price determination */
105 for (uint16_t j = 0; j < ad->k; j++)
106 {
107 /* compute inner gamma */
108 gcry_mpi_ec_sub (tmpa, tlta1[j], subtr, ec_ctx);
109
110 /* inner delta */
111 ec_point_copy (tmpb, tltb1[j]);
112
113 /* copy unmasked outcome to all other bidder layers so they don't
114 * have to be recomputed to check the ZK proof_2dle's from other
115 * bidders when receiving their outcome messages */
116 for (uint16_t a = 0; a < ad->n; a++)
117 {
118 ec_point_copy (ad->gamma3[a][0][j], tmpa);
119 ec_point_copy (ad->delta3[a][0][j], tmpb);
120 }
121 }
122
123 /* gamma and delta for winner determination: compute
124 * @f$\sum_{h=1}^n\sum_{d=j+1}^k2^{h-1}b_h@f and store it in every bidders gamma and
125 * delta, since it is needed each time a gamma,delta pair is received from
126 * another bidder. */
127 for (uint16_t i = 0; i < ad->n; i++)
128 {
129 for (uint16_t j = 0; j < ad->k; j++)
130 {
131 /* initialize with zeroes, since we are calculating a sum */
132 ec_point_copy (ad->gamma3[i][1][j], ec_zero);
133 ec_point_copy (ad->delta3[i][1][j], ec_zero);
134 }
135 }
136 gcry_mpi_set_ui (factor, 1);
137 for (uint16_t h = 0; h < ad->n; h++)
138 {
139 for (uint16_t j = 0; j < ad->k; j++)
140 {
141 for (uint16_t d = j + 1; d < ad->k; d++)
142 {
143 gcry_mpi_ec_mul (tmpa, factor, ad->alpha[h][d], ec_ctx);
144 gcry_mpi_ec_add (ad->gamma3[0][1][j],
145 ad->gamma3[0][1][j],
146 tmpa,
147 ec_ctx);
148 gcry_mpi_ec_mul (tmpb, factor, ad->beta[h][d], ec_ctx);
149 gcry_mpi_ec_add (ad->delta3[0][1][j],
150 ad->delta3[0][1][j],
151 tmpb,
152 ec_ctx);
153 }
154 }
155 gcry_mpi_lshift (factor, factor, 1);
156 }
157 /* copy component to all bidders so they don't have to be recomputed */
158 for (uint16_t a = 1; a < ad->n; a++)
159 {
160 for (uint16_t j = 0; j < ad->k; j++)
161 {
162 ec_point_copy (ad->gamma3[a][1][j], ad->gamma3[0][1][j]);
163 ec_point_copy (ad->delta3[a][1][j], ad->delta3[0][1][j]);
164 }
165 }
166
167 gcry_mpi_release (factor);
168 gcry_mpi_point_release (subtr);
169 gcry_mpi_point_release (tmpa);
170 gcry_mpi_point_release (tmpb);
171 smc_free1 (tlta1, ad->k);
172 smc_free1 (tltb1, ad->k);
173 smc_free2 (tlta2, ad->n, ad->k);
174 smc_free2 (tltb2, ad->n, ad->k);
175 smc_free2 (tlta3, ad->n, ad->k);
176 smc_free2 (tltb3, ad->n, ad->k);
177}
178
179
180/**
181 * mp_pub_compute_outcome computes encrypted outcome shares and packs them into
182 * a message buffer together with proofs of correctnes.
183 *
184 * @param[in] ad Pointer to the BRANDT_Auction struct to operate on
185 * @param[out] buflen Size of the returned message buffer in bytes
186 * @return A buffer containing the encrypted outcome vectors
187 * which needs to be broadcast
188 */
189unsigned char *
190mp_pub_compute_outcome (struct BRANDT_Auction *ad, size_t *buflen)
191{
192 unsigned char *ret;
193 unsigned char *cur;
194 struct msg_head *head;
195 gcry_mpi_point_t tmpa = gcry_mpi_point_new (0);
196 gcry_mpi_point_t tmpb = gcry_mpi_point_new (0);
197 struct ec_mpi *gamma;
198 struct ec_mpi *delta;
199 struct proof_2dle *proof2;
200
201 brandt_assert (ad && buflen);
202
203 *buflen = (sizeof (*head) + /* msg header */
204 ad->k * /* k * (gamma, delta, proof2) */
205 (sizeof (*gamma) + sizeof (*delta) + sizeof (*proof2)));
206 ret = GNUNET_new_array (*buflen, unsigned char);
207
208 head = (struct msg_head *)ret;
209 head->prot_version = htonl (0);
210 head->msg_type = htonl (msg_outcome);
211 cur = ret + sizeof (*head);
212
213 for (uint16_t j = 0; j < ad->k; j++)
214 {
215 gamma = (struct ec_mpi *)cur;
216 delta = &((struct ec_mpi *)cur)[1];
217 proof2 = (struct proof_2dle *)(cur + 2 * sizeof (struct ec_mpi));
218
219 /* only send the price determination gamma,delta pair, since the winner
220 * determination pair can and will be computed by the receiver */
221 ec_point_copy (tmpa, ad->gamma3[ad->i][0][j]);
222 ec_point_copy (tmpb, ad->delta3[ad->i][0][j]);
223
224 /* apply random masking for losing bidders */
225 smc_zkp_2dle (ad->gamma3[ad->i][0][j],
226 ad->delta3[ad->i][0][j],
227 tmpa,
228 tmpb,
229 NULL,
230 proof2);
231
232 ec_point_serialize (gamma, ad->gamma3[ad->i][0][j]);
233 ec_point_serialize (delta, ad->delta3[ad->i][0][j]);
234
235 /* compute own winner determination gamma,delta pair */
236 gcry_mpi_ec_add (ad->gamma3[ad->i][1][j],
237 ad->gamma3[ad->i][0][j],
238 ad->gamma3[ad->i][1][j],
239 ec_ctx);
240 gcry_mpi_ec_add (ad->delta3[ad->i][1][j],
241 ad->delta3[ad->i][0][j],
242 ad->delta3[ad->i][1][j],
243 ec_ctx);
244
245 cur += sizeof (*gamma) + sizeof (*delta) + sizeof (*proof2);
246 }
247
248 gcry_mpi_point_release (tmpa);
249 gcry_mpi_point_release (tmpb);
250 return ret;
251}
252
253
254int
255mp_pub_recv_outcome (struct BRANDT_Auction *ad,
256 const unsigned char *buf,
257 size_t buflen,
258 uint16_t sender)
259{
260 int ret = 0;
261 const unsigned char *cur = buf;
262 struct proof_2dle *proof2;
263 gcry_mpi_point_t gamma = gcry_mpi_point_new (0);
264 gcry_mpi_point_t delta = gcry_mpi_point_new (0);
265
266 brandt_assert (ad && buf);
267
268 if (buflen != (ad->k * (2 * sizeof (struct ec_mpi) + sizeof (*proof2))))
269 {
270 weprintf ("wrong size of received outcome");
271 goto quit;
272 }
273
274 for (uint16_t j = 0; j < ad->k; j++)
275 {
276 ec_point_parse (gamma, (struct ec_mpi *)cur);
277 ec_point_parse (delta, &((struct ec_mpi *)cur)[1]);
278 proof2 = (struct proof_2dle *)(cur + 2 * sizeof (struct ec_mpi));
279 if (smc_zkp_2dle_check (gamma,
280 delta,
281 ad->gamma3[sender][0][j],
282 ad->delta3[sender][0][j],
283 proof2))
284 {
285 weprintf ("wrong zkp2 for gamma, delta received");
286 goto quit;
287 }
288 ec_point_copy (ad->gamma3[sender][0][j], gamma);
289 ec_point_copy (ad->delta3[sender][0][j], delta);
290
291 /* compute winner determination gamma,delta pair */
292 gcry_mpi_ec_add (ad->gamma3[sender][1][j],
293 ad->gamma3[sender][0][j],
294 ad->gamma3[sender][1][j],
295 ec_ctx);
296 gcry_mpi_ec_add (ad->delta3[sender][1][j],
297 ad->delta3[sender][0][j],
298 ad->delta3[sender][1][j],
299 ec_ctx);
300
301 cur += 2 * sizeof (struct ec_mpi) + sizeof (*proof2);
302 }
303
304 ret = 1;
305quit:
306 gcry_mpi_point_release (gamma);
307 gcry_mpi_point_release (delta);
308 return ret;
309}
310
311
312void
313mp_pub_prep_decryption (struct BRANDT_Auction *ad)
314{
315 gcry_mpi_point_t tmp_price = gcry_mpi_point_new (0);
316 gcry_mpi_point_t tmp_winner = gcry_mpi_point_new (0);
317
318 ad->phi3 = smc_init3 (ad->n, 2, ad->k);
319 brandt_assert (ad->phi3);
320
321 for (uint16_t j = 0; j < ad->k; j++)
322 {
323 smc_sum (tmp_price, &ad->delta3[0][0][j], ad->n, 2 * ad->k);
324 smc_sum (tmp_winner, &ad->delta3[0][1][j], ad->n, 2 * ad->k);
325
326 /* copy still encrypted outcome to all other bidder layers so they
327 * don't have to be recomputed to check the ZK proof_2dle's from
328 * other bidders when receiving their outcome decryption messages */
329 for (uint16_t a = 0; a < ad->n; a++)
330 {
331 ec_point_copy (ad->phi3[a][0][j], tmp_price);
332 ec_point_copy (ad->phi3[a][1][j], tmp_winner);
333 }
334 }
335
336 gcry_mpi_point_release (tmp_price);
337 gcry_mpi_point_release (tmp_winner);
338}
339
340
341/**
342 * mp_pub_decrypt_outcome decrypts part of the outcome and packs it into a
343 * message buffer together with proofs of correctnes.
344 *
345 * @param[in] ad Pointer to the BRANDT_Auction struct to operate on
346 * @param[out] buflen Size of the returned message buffer in bytes
347 * @return A buffer containing the own share of the decrypted outcome
348 * which needs to be broadcast
349 */
350unsigned char *
351mp_pub_decrypt_outcome (struct BRANDT_Auction *ad, size_t *buflen)
352{
353 unsigned char *ret;
354 unsigned char *cur;
355 gcry_mpi_point_t tmp = gcry_mpi_point_new (0);
356 struct msg_head *head;
357 struct ec_mpi *phi;
358 struct proof_2dle *proof2;
359
360 brandt_assert (ad && buflen);
361
362 *buflen = (sizeof (*head) + 2 * ad->k * (sizeof (*phi) + sizeof (*proof2)));
363 ret = GNUNET_new_array (*buflen, unsigned char);
364
365 head = (struct msg_head *)ret;
366 head->prot_version = htonl (0);
367 head->msg_type = htonl (msg_decrypt);
368 cur = ret + sizeof (*head);
369
370 /* decrypt price and winner components */
371 for (uint16_t comp = 0; comp < 2; comp++)
372 {
373 for (uint16_t j = 0; j < ad->k; j++)
374 {
375 phi = (struct ec_mpi *)cur;
376 proof2 = (struct proof_2dle *)(cur + sizeof (*phi));
377
378 ec_point_copy (tmp, ad->phi3[ad->i][comp][j]);
379
380 /* decrypt outcome component and prove the correct key was used */
381 smc_zkp_2dle (ad->phi3[ad->i][comp][j],
382 NULL,
383 tmp,
384 ec_gen,
385 ad->x,
386 proof2);
387
388 ec_point_serialize (phi, ad->phi3[ad->i][comp][j]);
389
390 cur += sizeof (*phi) + sizeof (*proof2);
391 }
392 }
393
394 gcry_mpi_point_release (tmp);
395 return ret;
396}
397
398
399int
400mp_pub_recv_decryption (struct BRANDT_Auction *ad,
401 const unsigned char *buf,
402 size_t buflen,
403 uint16_t sender)
404{
405 int ret = 0;
406 const unsigned char *cur = buf;
407 struct proof_2dle *proof2;
408 gcry_mpi_point_t phi = gcry_mpi_point_new (0);
409
410 brandt_assert (ad && buf);
411
412 if (buflen != (2 * ad->k * (sizeof (struct ec_mpi) + sizeof (*proof2))))
413 {
414 weprintf ("wrong size of received outcome decryption");
415 goto quit;
416 }
417
418 /* handle received price and winner components */
419 for (uint16_t comp = 0; comp < 2; comp++)
420 {
421 for (uint16_t j = 0; j < ad->k; j++)
422 {
423 ec_point_parse (phi, (struct ec_mpi *)cur);
424 proof2 = (struct proof_2dle *)(cur + sizeof (struct ec_mpi));
425
426 if (smc_zkp_2dle_check (phi,
427 ad->y[sender],
428 ad->phi3[sender][comp][j],
429 ec_gen,
430 proof2))
431 {
432 weprintf ("wrong zkp2 for phi, y received");
433 goto quit;
434 }
435 ec_point_copy (ad->phi3[sender][comp][j], phi);
436 cur += sizeof (struct ec_mpi) + sizeof (*proof2);
437 }
438 }
439
440 ret = 1;
441quit:
442 gcry_mpi_point_release (phi);
443 return ret;
444}
445
446
447struct BRANDT_Result *
448mp_pub_determine_outcome (struct BRANDT_Auction *ad,
449 uint16_t *len)
450{
451 struct BRANDT_Result *ret;
452 int32_t price = -1;
453 uint16_t cur_winner = 0;
454 int dlogi = -1;
455 gcry_mpi_point_t sum_gamma = gcry_mpi_point_new (0);
456 gcry_mpi_point_t sum_phi = gcry_mpi_point_new (0);
457
458 brandt_assert (ad);
459
460 for (uint16_t j = ad->k - 1; j >= 0; j--)
461 {
462 smc_sum (sum_gamma, &ad->gamma3[0][0][j], ad->n, 2 * ad->k);
463 smc_sum (sum_phi, &ad->phi3[0][0][j], ad->n, 2 * ad->k);
464 gcry_mpi_ec_sub (sum_gamma, sum_gamma, sum_phi, ec_ctx);
465 /* first zero component determines the price */
466 if (!ec_point_cmp (sum_gamma, ec_zero))
467 {
468 price = j;
469 break;
470 }
471 }
472
473 if (-1 == price)
474 return NULL;
475
476 /* extract winners point for the winning price */
477 smc_sum (sum_gamma, &ad->gamma3[0][1][price], ad->n, 2 * ad->k);
478 smc_sum (sum_phi, &ad->phi3[0][1][price], ad->n, 2 * ad->k);
479 gcry_mpi_ec_sub (sum_gamma, sum_gamma, sum_phi, ec_ctx);
480
481 dlogi = GNUNET_CRYPTO_ecc_dlog (ec_dlogctx, sum_gamma);
482 brandt_assert (dlogi > 0);
483
484 /* all bidders participated with a multiplicative share */
485 dlogi /= ad->n;
486
487 price = price / ad->n;
488 ret = GNUNET_new_array (ad->m, struct BRANDT_Result);
489
490 /* can only support up to bits(dlogi) bidders */
491 brandt_assert (sizeof (int) * 8 > ad->n);
492 for (uint16_t i = 0; i < ad->n; i++)
493 {
494 /* a set bit determines a winner */
495 if (dlogi & (1 << i))
496 {
497 if (cur_winner >= ad->m)
498 {
499 weprintf ("too many winners detected");
500 GNUNET_free (ret);
501 ret = NULL;
502 goto quit;
503 }
504
505 ret[cur_winner].bidder = i;
506 ret[cur_winner].price = price;
507 ret[cur_winner].status = BRANDT_bidder_won;
508 cur_winner++;
509 }
510 }
511
512 if (cur_winner != ad->m)
513 {
514 weprintf ("too few winners detected");
515 GNUNET_free (ret);
516 ret = NULL;
517 goto quit;
518 }
519
520 if (len)
521 *len = ad->m;
522quit:
523 gcry_mpi_point_release (sum_gamma);
524 gcry_mpi_point_release (sum_phi);
525 return ret;
526}
diff --git a/test_brandt.c b/test_brandt.c
index 46ec90d..d18b17a 100644
--- a/test_brandt.c
+++ b/test_brandt.c
@@ -54,7 +54,7 @@ static struct testcase tcase;
54 54
55 55
56static struct BRANDT_Result * 56static struct BRANDT_Result *
57expected_outcome (uint16_t i) 57expected_outcome (uint16_t i, uint16_t *rlen)
58{ 58{
59 struct BRANDT_Result *ret = NULL; 59 struct BRANDT_Result *ret = NULL;
60 int32_t highest_bidder = -1; 60 int32_t highest_bidder = -1;
@@ -65,6 +65,8 @@ expected_outcome (uint16_t i)
65 uint16_t winners = MIN (tcase.m, tcase.n); 65 uint16_t winners = MIN (tcase.m, tcase.n);
66 uint16_t cur_winner = 0; 66 uint16_t cur_winner = 0;
67 67
68 *rlen = 0;
69
68 if (0 == tcase.n) 70 if (0 == tcase.n)
69 return NULL; 71 return NULL;
70 72
@@ -81,6 +83,7 @@ expected_outcome (uint16_t i)
81 ret->bidder = highest_bidder; 83 ret->bidder = highest_bidder;
82 ret->price = highest_bid; 84 ret->price = highest_bid;
83 ret->status = BRANDT_bidder_won; 85 ret->status = BRANDT_bidder_won;
86 *rlen = 1;
84 return ret; 87 return ret;
85 } 88 }
86 89
@@ -89,7 +92,7 @@ expected_outcome (uint16_t i)
89 { 92 {
90 if (tcase.outcome_public || i == tcase.n) 93 if (tcase.outcome_public || i == tcase.n)
91 { 94 {
92 ret = GNUNET_new_array (tcase.n, struct BRANDT_Result); 95 ret = GNUNET_new_array ((*rlen = tcase.n), struct BRANDT_Result);
93 for (uint16_t h = 0; h < tcase.n; h++) 96 for (uint16_t h = 0; h < tcase.n; h++)
94 { 97 {
95 ret[h].bidder = h; 98 ret[h].bidder = h;
@@ -103,6 +106,7 @@ expected_outcome (uint16_t i)
103 ret->bidder = i; 106 ret->bidder = i;
104 ret->price = 0; 107 ret->price = 0;
105 ret->status = BRANDT_bidder_won; 108 ret->status = BRANDT_bidder_won;
109 *rlen = 1;
106 } 110 }
107 return ret; 111 return ret;
108 } 112 }
@@ -154,6 +158,7 @@ expected_outcome (uint16_t i)
154 cur_winner++; 158 cur_winner++;
155 } 159 }
156 } 160 }
161 *rlen = cur_winner;
157 return ret; 162 return ret;
158} 163}
159 164
@@ -250,7 +255,16 @@ cb_result (void *auction_closure,
250 uint16_t results_len) 255 uint16_t results_len)
251{ 256{
252 uint16_t *s = (uint16_t *)auction_closure; 257 uint16_t *s = (uint16_t *)auction_closure;
253 struct BRANDT_Result *must = expected_outcome (*s); 258 uint16_t mustlen = -1;
259 struct BRANDT_Result *must = expected_outcome (*s, &mustlen);
260
261 if (mustlen != results_len)
262 {
263 weprintf ("expected result len is: %d", mustlen);
264 weprintf ("computed result len is: %d (by agent %d)", results_len, *s);
265 tcase.ret = 1;
266 goto quit;
267 }
254 268
255 if (0 == results_len) 269 if (0 == results_len)
256 { 270 {
@@ -281,6 +295,7 @@ cb_result (void *auction_closure,
281 tcase.ret = 1; 295 tcase.ret = 1;
282 } 296 }
283 297
298quit:
284 tcase.result_called[*s] = 1; 299 tcase.result_called[*s] = 1;
285 if (must) 300 if (must)
286 GNUNET_free (must); 301 GNUNET_free (must);
@@ -406,17 +421,24 @@ main (int argc, char *argv[])
406 BRANDT_init (edc); 421 BRANDT_init (edc);
407 422
408 ret |= 0 || 423 ret |= 0 ||
424 // zero bidders
409 test_auction (0, 2, NULL, 0, 0) || 425 test_auction (0, 2, NULL, 0, 0) ||
410 test_auction (0, 2, NULL, 0, 1) || 426 test_auction (0, 2, NULL, 0, 1) ||
411 test_auction (0, 2, NULL, 1, 0) || 427 test_auction (0, 2, NULL, 1, 0) ||
412 test_auction (0, 2, NULL, 2, 0) || 428 test_auction (0, 2, NULL, 2, 0) ||
429
430 // too few bidders => outcome is lowest possible price
413 test_auction (1, 2, (uint16_t[]) { 1 }, 1, 0) || 431 test_auction (1, 2, (uint16_t[]) { 1 }, 1, 0) ||
414 test_auction (1, 2, (uint16_t[]) { 0 }, 2, 0) || 432 test_auction (1, 2, (uint16_t[]) { 0 }, 2, 0) ||
415 test_auction (2, 2, (uint16_t[]) { 1, 0 }, 2, 0) || 433 test_auction (2, 2, (uint16_t[]) { 1, 0 }, 2, 0) ||
416 test_auction (2, 2, (uint16_t[]) { 1, 0 }, 1, 0) || 434 test_auction (2, 2, (uint16_t[]) { 1, 0 }, 1, 0) ||
417 test_auction (3, 2, (uint16_t[]) { 0, 0, 1 }, 2, 0) || 435 test_auction (3, 2, (uint16_t[]) { 0, 0, 1 }, 2, 0) ||
436
437 // general checks of all four algorithms
418 test_auction (3, 2, (uint16_t[]) { 0, 1, 1 }, 0, 0) || 438 test_auction (3, 2, (uint16_t[]) { 0, 1, 1 }, 0, 0) ||
419 test_auction (3, 2, (uint16_t[]) { 0, 1, 1 }, 0, 1) || 439 test_auction (3, 2, (uint16_t[]) { 0, 1, 1 }, 0, 1) ||
440 test_auction (3, 2, (uint16_t[]) { 0, 1, 1 }, 2, 0) ||
441 test_auction (3, 2, (uint16_t[]) { 0, 1, 1 }, 2, 1) ||
420 0; 442 0;
421 443
422 GNUNET_CRYPTO_ecc_dlog_release (edc); 444 GNUNET_CRYPTO_ecc_dlog_release (edc);
generated by cgit v1.2.3 (git 2.39.1) at 2024-04-20 01:36:26 +0000