-
Notifications
You must be signed in to change notification settings - Fork 220
Expand file tree
/
Copy pathphone-a-friend.html
More file actions
816 lines (806 loc) · 41 KB
/
phone-a-friend.html
File metadata and controls
816 lines (806 loc) · 41 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
<!DOCTYPE html>
<html lang="en">
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
<meta name="viewport" content="width=device-width, initial-scale=1, minimum-scale=1" />
<link rel="preload" href="/style.css" as="style">
<link rel="preload" href="/shared.js" as="script">
<link rel="icon" href="/favicon.ico" type="image/x-icon">
<title>commonware > Phone a Friend</title>
<meta name="description" content="Instead of every single validator
carrying out the work of decryption, a well-provisioned helper can do
the work once and broadcast hints to the network which will be used to
quickly verify the result.">
<meta name="author" content="Guru Vamsi Policharla">
<meta name="keywords" content="commonware, open source, common goods, software, internet, ownership, trust, blockchain, decentralization, crypto">
<meta property="og:url" content="https://commonware.xyz/blogs/phone-a-friend" />
<meta property="og:type" content="article" />
<meta property="og:site_name" content="commonware" />
<meta property="og:image" content="https://commonware.xyz/imgs/batch-mempool-decryption.png" />
<meta property="og:title" content="Phone a Friend" />
<meta property="og:description" content="Instead of every single
validator carrying out the work of decryption, a well-provisioned helper
can do the work once and broadcast hints to the network which will be
used to quickly verify the result." />
<meta property="article:author" content="Guru Vamsi Policharla" />
<meta property="article:published_time" content="2026-05-19T00:00:00Z" />
<meta property="article:modified_time" content="2026-05-19T00:00:00Z" />
<link rel="canonical" href="https://commonware.xyz/blogs/phone-a-friend" />
<meta name="twitter:card" content="summary_large_image" />
<meta property="twitter:domain" content="commonware.xyz" />
<meta property="twitter:url" content="https://commonware.xyz/blogs/phone-a-friend" />
<meta property="twitter:title" content="Phone a Friend" />
<meta property="twitter:description" content="Instead of every
single validator carrying out the work of decryption, a well-provisioned
helper can do the work once and broadcast hints to the network which
will be used to quickly verify the result." />
<meta property="twitter:image" content="https://commonware.xyz/imgs/batch-mempool-decryption.png" />
<meta property="twitter:site" content="@commonwarexyz" />
<meta property="twitter:creator" content="https://x.com/guruvamsip" />
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/katex@0.16.0/dist/katex.min.css">
<script defer src="https://cdn.jsdelivr.net/npm/katex@0.16.0/dist/katex.min.js"
onload="document.querySelectorAll('.math').forEach(function (el) {
katex.render(el.textContent, el, {
displayMode: el.classList.contains('display'),
throwOnError: false
});
});"></script>
<link rel="stylesheet" type="text/css" href="/style.css">
</head>
<body>
<div id="logo-placeholder">
<div class="logo-line">
<span class="edge-logo-symbol">+</span>
<span class="horizontal-logo-symbol">~</span>
<span class="horizontal-logo-symbol"> </span>
<span class="horizontal-logo-symbol">-</span>
<span class="horizontal-logo-symbol">+</span>
<span class="horizontal-logo-symbol">-</span>
<span class="horizontal-logo-symbol">+</span>
<span class="horizontal-logo-symbol"> </span>
<span class="horizontal-logo-symbol">-</span>
<span class="horizontal-logo-symbol">+</span>
<span class="horizontal-logo-symbol">-</span>
<span class="horizontal-logo-symbol">~</span>
<span class="horizontal-logo-symbol">~</span>
<span class="edge-logo-symbol">*</span>
</div>
<div class="logo-line">
<span class="vertical-logo-symbol">|</span>
<span class="logo-text"> commonware </span>
<span class="vertical-logo-symbol"> </span>
</div>
<div class="logo-line">
<span class="edge-logo-symbol">*</span>
<span class="horizontal-logo-symbol">~</span>
<span class="horizontal-logo-symbol">+</span>
<span class="horizontal-logo-symbol">+</span>
<span class="horizontal-logo-symbol">-</span>
<span class="horizontal-logo-symbol"> </span>
<span class="horizontal-logo-symbol">~</span>
<span class="horizontal-logo-symbol">-</span>
<span class="horizontal-logo-symbol">+</span>
<span class="horizontal-logo-symbol"> </span>
<span class="horizontal-logo-symbol">-</span>
<span class="horizontal-logo-symbol">*</span>
<span class="horizontal-logo-symbol">-</span>
<span class="edge-logo-symbol">+</span>
</div>
</div>
<div class="content">
<h1>Phone a Friend</h1>
<div class="meta">
<div class="author">By <a href="https://x.com/guruvamsip">Guru
Vamsi Policharla</a></div>
<div class="date">May 19th, 2026</div>
</div>
<p>Two <em>advanced</em> encryption schemes have gained traction
to protect the privacy of pending transactions:</p>
<p><strong>Identity-Based Encryption:</strong> Ciphertexts can
be encrypted to arbitrary “strings” such that a signature on the
string acts as the key to decrypt the ciphertext. If the signing
key is secret shared amongst the validator set, they can sign
the block height as a “timestamp” which enables encryption to a
specific time in the future. More generally, you can sign
arbitrary events, enabling conditional decryption of ciphertexts
on chain. Concretely, this can be instantiated with BLS
signatures as shown in <a
href="https://eprint.iacr.org/2001/090">BF01</a> or even with
Silent Setup as shown in <a
href="https://eprint.iacr.org/2024/263">GKPW24</a>.</p>
<p>Thus, each validator only broadcasts a constant amount of
information to sign a message – but the signature can then be
used to decrypt an arbitrary number of ciphertexts. But building
an application on-chain with this requires some care.</p>
<p>Consider a sealed-bid auction where users encrypt their bid
to some time <span class="math inline">T</span> in the future,
when the auction ends. It’s now entirely possible that a user’s
bid is not included on chain before <span
class="math inline">T</span> and therefore never included as
part of the auction, but after time <span
class="math inline">T</span> their bid can be decrypted. While
you can mitigate this by ensuring users have sufficient time to
have their bids included, this is not always reasonable in time
sensitive applications such as trading.</p>
<p><strong>Batched Threshold Encryption:</strong> This brings us
to batched threshold encryption which allows the validator set
to <em>specify</em> the exact set of ciphertexts that should be
decrypted. At the same time, ensuring the communication from
validators is independent of the number of ciphertexts in the
batch. Since the primitive was introduced in <a
href="https://eprint.iacr.org/2024/669">CGPP24</a>, there’s been
a long line of work pushing the primitive closer to
practicality.</p>
<p>Latest constructions of BTE [<a
href="https://eprint.iacr.org/2026/674">BNRT26</a>, <a
href="https://eprint.iacr.org/2026/760">Pol26</a>, <a
href="https://eprint.iacr.org/2026/754">ADG+26</a>] have reduced
the ciphertext size to <span class="math inline">|\mathbb{G}_1|
+ |\mathsf{msg}|</span> – just 16 bytes longer than threshold
ElGamal (over ed25519) when instantiated with BLS12-381.
Decryption is the fastest amongst all known schemes but
nevertheless still requires <span
class="math inline">O(B\log{B})</span> group operations and
<span class="math inline">O(B)</span> pairings.</p>
<p>Both IBE and BTE still require a few pairings to decrypt a
ciphertext which places a lower bound of <span
class="math inline">\approx 1</span> ms per transaction.
Processing 100K transactions would still require 100s in
single-core CPU time!</p>
<h2 id="how-do-we-scale">How do we scale?</h2>
<p>To avoid designing bespoke solutions for every primitive, we
will use the observation from <a
href="https://eprint.iacr.org/2025/1364">GHKKP25</a> that many
pairing-based <em>advanced</em> encryption schemes including
IBE/Timelock Encryption [<a
href="https://eprint.iacr.org/2001/090">BF01</a>, <a
href="https://eprint.iacr.org/2022/433">DHMW23</a>, <a
href="https://eprint.iacr.org/2023/189">GMR23</a>], Batch
Threshold Encryption/IBE [<a
href="https://eprint.iacr.org/2024/669">CGPP24</a>, <a
href="https://eprint.iacr.org/2024/1516">CGPW25</a>, <a
href="https://eprint.iacr.org/2024/1575">AFP25</a>], Silent
Threshold Encryption [<a
href="https://eprint.iacr.org/2024/263">GKPW24</a>], ABE [<a
href="https://eprint.iacr.org/2004/086">SW05</a>], Distributed
Broadcast Encryption [<a
href="https://eprint.iacr.org/2023/874">KMW23</a>] and more can
be viewed as witness encryptions for relations of the form:</p>
<p><span class="math display">
\underbrace{
\begin{bmatrix}
A_{1,1} & \cdots & A_{1,n} \\
A_{2,1} & \cdots & A_{2,n} \\
\vdots & \ddots & \vdots \\
A_{m,1} & \cdots & A_{m,n}
\end{bmatrix}
}_{\text{public statement}}
\circ
\underbrace{
\begin{bmatrix}
w_1 \\
w_2 \\
\vdots \\
w_n
\end{bmatrix}
}_{\text{secret witness}}
=
\underbrace{
\begin{bmatrix}
b_1 \\
b_2 \\
\vdots \\
b_m
\end{bmatrix}
}_{\text{public statement}}
</span></p>
<p>Here <span class="math inline">\circ</span> denotes a pairing
(and its natural extension to matrix multiplication), the
entries of <span class="math inline">A</span> and <span
class="math inline">w</span> are from compatible source groups,
and the entries of <span class="math inline">b</span> lie in
<span class="math inline">\mathbb{G}_T</span>. Given randomness
<span
class="math inline">\alpha=(\alpha_1,\ldots,\alpha_m)</span>,
encryption of a message <span class="math inline">M</span> has
the form <span class="math inline">\mathsf{Enc}(M,
(A,b)):</span></p>
<p><span class="math display">
\mathsf{ct}_0 := M + \sum_{i=1}^{m}\alpha_i b_i,
\qquad
\mathsf{ct}_j := \sum_{i=1}^{m}\alpha_i A_{i,j}
\quad\text{for }j\in[n].
</span></p>
<p>Given a valid witness <span class="math inline">w</span>,
decryption recovers the message as <span
class="math inline">\mathsf{Dec}(\mathsf{ct}, w):</span></p>
<p><span class="math display">
M \gets \mathsf{ct}_0 - \sum_{j=1}^{n}\mathsf{ct}_j \circ w_j.
</span></p>
<p><strong>Phone a Friend:</strong> Instead of every single
validator carrying out the work of decryption, a
well-provisioned helper can do the work once and broadcast
<em>hints</em> to the network which will be used to quickly
verify the result. More formally, there exists a method:</p>
<p><span
class="math display">\mathsf{HintDec}((\mathsf{ct}^1,\ldots,\mathsf{ct}^B),
\mathsf{hint}) \to (m^1,\dots,m^B)</span></p>
<p>which takes as input a batch of <span
class="math inline">B</span> ciphertexts <span
class="math inline">\mathsf{ct}^1, \ldots, \mathsf{ct}^B</span>
and a hint <span class="math inline">\mathsf{hint}</span>, and
outputs the messages <span class="math inline">m^1, \ldots,
m^B</span> or <span class="math inline">\bot</span>. Of course
<span class="math inline">\mathsf{HintDec}</span> is non-trivial
only if it offers a speedup over the naive decryption algorithm.
For security, we will require that it is computationally
infeasible to produce a <span
class="math inline">\mathsf{hint}</span> such that:</p>
<p><span class="math display">
\mathsf{HintDec}((\mathsf{ct}^1,\ldots,\mathsf{ct}^B),
\mathsf{hint}) \neq (\mathsf{Dec}(\mathsf{ct}^1, w^1), \ldots,
\mathsf{Dec}(\mathsf{ct}^B, w^B))
</span></p>
<p>even for adversarially chosen ciphertexts <span
class="math inline">(\mathsf{ct}^1,\ldots,\mathsf{ct}^B)</span>,
where the probability is taken over the randomness of the
adversary. Thus we only rely on the helper for liveness and a
malicious helper cannot violate safety by equivocating
hints.</p>
<h3 id="a-first-attempt">A First Attempt</h3>
<p>In some pairing based proof systems, it’s possible to reduce
the verification of <span class="math inline">N</span> pairing
product equations to MSMs of size <span
class="math inline">N</span> and a single pairing product
equation. In fact, we used this idea in our previous <a
href="/blogs/batch-pari">blog post</a> on batch verification of
Pari proofs.</p>
<p>A natural approach is to have the helper send the recovered
message together with the corresponding witness as the hint. The
verifier can then check the decryption equation is satisfied for
all of the ciphertexts by sampling random coefficients and
applying the test from <a
href="https://eprint.iacr.org/2008/015">FGHP09</a>. This reduces
many checks to a single pairing-product equation. However, the
number of pairings only reduces when there is a common input
across the different pairing terms: <span class="math display">
\prod_{i=1}^B e(g_i, h)^{r_i} = e\left(\sum_{i=1}^B r_i g_i,\;
h\right).
</span></p>
<p>So if all ciphertexts use the same witness, the verifier can
fold pairings across the <span class="math inline">B</span>
ciphertexts with an MSM. Fortunately, this is the case for
Timelock encryption as the witness is a signature on the block
height. But if each ciphertext has its own unrelated witness,
which is the case in most other applications of pairing based WE
schemes, the verifier will have to evaluate a large number of
pairings.</p>
<h2 id="our-approach">Our Approach</h2>
<p>We start from a simple observation:</p>
<div data-align="center">
<p><em>A perfectly correct encryption scheme is also a perfectly
binding commitment scheme</em></p>
</div>
<p>If a helper provides us the message <em>and</em> randomness
used to create the ciphertext, we can avoid the decryption
equation check entirely. Instead, we can check that the
ciphertext is a valid encryption of the claimed message under
the claimed randomness. In the linear WE notation above, this
means checking:</p>
<p><span class="math display">
\mathsf{ct}_j
\stackrel{?}{=}
\sum_{i=1}^{m}\alpha_i A_{i,j}
\quad\text{for every }j\in[n],
\qquad
\mathsf{ct}_0 - M
\stackrel{?}{=}
\sum_{i=1}^{m}\alpha_i b_i.
</span></p>
<p>These checks use MSMs in the source groups and target group,
but no pairings. They also batch naturally via <a
href="https://eprint.iacr.org/2008/015">FGHP09</a>: sample
random coefficients <span
class="math inline">r_1,\ldots,r_B\gets\mathbb{F}</span> and
check the random linear combination of the claimed openings:</p>
<p><span class="math display">
\sum_{k=1}^{B} r_k\mathsf{ct}^k_j
\stackrel{?}{=}
\sum_{k=1}^{B}\sum_{i=1}^{m} r_k\alpha^k_i A^k_{i,j}
\quad\text{for every }j\in[n],
</span></p>
<p>and</p>
<p><span class="math display">
\sum_{k=1}^{B} r_k(\mathsf{ct}^k_0-M^k)
\stackrel{?}{=}
\sum_{k=1}^{B}\sum_{i=1}^{m} r_k\alpha^k_i b^k_i.
</span></p>
<p>The missing piece is actually recovering the randomness from
the ciphertext. A simple approach is to just encrypt the
randomness in a separate ciphertext, but this comes at a <span
class="math inline">2\times</span> penalty in ciphertext size
and encryption/decryption time.</p>
<h3 id="randomness-recovery">Randomness Recovery</h3>
<p>Our approach uses the <a
href="https://link.springer.com/chapter/10.1007/3-540-48405-1_34">Fujisaki-Okamoto
transform</a> for randomness recovery. It’s important to note
that this does not provide CCA security in the threshold
decryption setting as the committee would need to securely carry
out certain checks during decryption that require interaction.
So constructions such as batched threshold encryption still
require additional mechanisms such as Simulation-Extractable
NIZKs for CCA security.</p>
<p>Let <span class="math inline">\mathcal{K}</span> be the
message space of the underlying WE scheme, and</p>
<p><span class="math display">
H_R:\mathcal{K}\times\{0,1\}^{\ell_m}\to\{0,1\}^{\ell_\rho},
\qquad
H_M:\mathcal{K}\to\{0,1\}^{\ell_m},
</span></p>
<p>be random oracles, and let <span
class="math inline">G:\{0,1\}^{\ell_\rho}\to\mathbb{F}^m</span>
be a PRG. To encrypt a message <span class="math inline">M \in
\{0,1\}^{\ell_m}</span>, sample <span
class="math inline">K\gets\mathcal{K}</span>, derive</p>
<p><span class="math display">
\rho := H_R(K,M),
\qquad
\alpha := G(\rho),
</span></p>
<p>and output:</p>
<p><span class="math display">
\mathsf{ct}' := \left(\mathsf{Enc}((A,b), K; \alpha),\;
H_M(K)\oplus M\right).
</span></p>
<p>This gives two possible choices for the hint:</p>
<ul>
<li><p><strong>Bandwidth-optimized:</strong> the helper sends
the short PRG seed <span class="math inline">\rho^k</span> (16
bytes) for each ciphertext. Parse the <span
class="math inline">k</span>-th transformed ciphertext as <span
class="math inline">\mathsf{ct}^{\prime
k}=((\mathsf{ct}^k_0,\mathsf{ct}^k_1,\ldots,\mathsf{ct}^k_n),
c^k)</span> where <span class="math inline">c^k=H_M(K^k)\oplus
M^k</span>. For each <span class="math inline">k\in[B]</span>,
the verifier computes</p>
<p><span class="math display">
\alpha^k := G(\rho^k),
\qquad
K^k := \mathsf{ct}^k_0-\sum_{i=1}^{m}\alpha^k_i b^k_i,
\qquad
M^k := c^k\oplus H_M(K^k),
</span></p>
<p>checks <span class="math inline">\rho^k=H_R(K^k,M^k)</span>,
and then batch-verifies <span
class="math inline">\mathsf{ct}^k_j=\sum_{i=1}^{m}\alpha^k_i
A^k_{i,j}</span> for every <span
class="math inline">j\in[n]</span>.</p></li>
<li><p><strong>Verification-optimized:</strong> the helper sends
<span class="math inline">K^k</span> directly (576 bytes) for
each ciphertext. For each <span
class="math inline">k\in[B]</span>, the verifier computes</p>
<p><span class="math display">
M^k := c^k\oplus H_M(K^k),
\qquad
\rho^k := H_R(K^k,M^k),
\qquad
\alpha^k := G(\rho^k).
</span></p>
<p>It then batch-verifies:</p>
<p><span class="math display">
\mathsf{ct}^k_j
=
\sum_{i=1}^{m}\alpha^k_i A^k_{i,j}
\quad\text{for every }j\in[n],
\qquad
\mathsf{ct}^k_0-K^k
=
\sum_{i=1}^{m}\alpha^k_i b^k_i.
</span></p>
<p>This uses larger hints, but avoids the per-ciphertext
target-group work needed to recover <span
class="math inline">K^k</span> from a seed.</p></li>
</ul>
<h2 id="scaling-batched-threshold-encryption">Scaling Batched
Threshold Encryption</h2>
<p>Coming to the specific case of batched threshold encryption
there are two remaining hurdles:</p>
<ul>
<li>While some constructions of BTE such as <a
href="https://eprint.iacr.org/2024/1516">CGPW25</a> and <a
href="https://eprint.iacr.org/2024/1575">AFP25</a> have been
presented as witness encryption schemes, it is not obvious how
we can view constructions such as <a href="/blogs/bte">Simple
BTE</a> as a witness encryption scheme.</li>
<li>We have completely ignored the issue of malformed
ciphertexts. Suppose a user submits a ciphertext that fails the
FO decryption check such that the helper cannot recover
randomness. Observe that the helper cannot just output <span
class="math inline">\bot</span>, because a malicious helper
could suppress honest ciphertexts by falsely claiming they are
malformed. Instead, the helper needs to <em>prove</em> the
ciphertext is malformed. One can of course attach a SNARK but
this is quite expensive and we would like to do better.</li>
</ul>
<h3 id="simple-bte-as-a-witness-encryption-scheme">Simple BTE as
a Witness Encryption Scheme</h3>
<p>We recall the simple BTE construction from our <a
href="/blogs/bte">previous blog post</a>.</p>
<ul>
<li><p><strong>Encrypt:</strong> An ElGamal-style
ciphertext:</p>
<p><span class="math display">
\mathsf{ct} := \left([k]_1,\; m + [k\tau^{B+1}]_T\right)
</span></p></li>
<li><p><strong>Partial Decrypt:</strong> To decrypt a batch
<span class="math inline">(\mathsf{ct}_i)_{i\in[B]}</span>, each
validator <span class="math inline">j</span> holding shares
<span class="math inline">(\sigma^i_j)_{i\in[B]}</span> of <span
class="math inline">(\tau^i)_{i\in[B]}</span> broadcasts:</p>
<p><span class="math display">
\mathsf{pd}_j := \sum_{i\in[B]} \sigma_j^i\cdot
\mathsf{ct}_{i,1}
</span></p>
<p>Any <span class="math inline">t</span> partial decryptions
are combined via Lagrange interpolation to reconstruct:</p>
<p><span class="math display">
\mathsf{pd} = \left[\sum_{i\in[B]} k_i\tau^i\right]_1
</span></p></li>
</ul>
<p>At first glance, one might view each ciphertext as a witness
encryption for the relation</p>
<p><span class="math display">
[1]_1\circ w=[\tau^{B+1}]_T.
</span></p>
<p>Clearly the only witness that can satisfy this relation is
<span class="math inline">w = [\tau^{B+1}]_2</span> but the
decryptor never learns it. In fact, they never should as it
allows them to decrypt all ciphertexts (even outside the batch).
Instead, consider the following relation <span
class="math inline">R_j</span>:</p>
<p><span class="math display">
\begin{bmatrix}
[1]_1 & 0 & \cdots & 0 & [\tau]_1 \\
0 & [1]_1 & \cdots & 0 & [\tau^2]_1 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & \cdots & [1]_1 & [\tau^B]_1
\end{bmatrix}
\circ
\begin{bmatrix}
w_1\\
w_2\\
\vdots\\
w_B\\
w_{B+1}
\end{bmatrix}
=
\begin{bmatrix}
0\\
\vdots\\
[\tau^{B+1}]_T\\
\vdots\\
0
\end{bmatrix},
</span></p>
<p>where the non-zero entry on the right-hand side is in the
<span class="math inline">j</span>-th row. If we run the WE
encryption algorithm for <span class="math inline">R_j</span>
with randomness <span
class="math inline">(k_1,\ldots,k_B)</span>, the resulting
ciphertext has the form:</p>
<p><span class="math display">
\left(
[k_1]_1,\ldots,[k_B]_1,\;
\left[\sum_{i=1}^{B}k_i\tau^i\right]_1,\;
[k_j\tau^{B+1}]_T+m
\right).
</span></p>
<p>As it turns out, if we want to encrypt different messages
<span class="math inline">\{m_j\}_{j \in [B]}</span> under
relations <span class="math inline">\{\mathcal{R}_j\}_{j \in
[B]}</span>, respectively, we can <em>securely</em> share the
randomness <span class="math inline">(k_1,\dots,k_B)</span>
between the ciphertexts. This can also be viewed as a <a
href="https://eprint.iacr.org/2014/301">witness PRF</a>, where
<span class="math inline">([k_1]_1,\ldots,[k_B]_1,
\left[\sum_{i=1}^{B}k_i\tau^i\right]_1)</span> is the secret key
and <span
class="math inline">(0,\ldots,[\tau^{B+1}]_T,\ldots,0)</span> is
the statement at which the PRF is evaluated.</p>
<p>This leads to a compression in the ciphertext size from <span
class="math inline">B(B + 1)\times\mathbb{G}_1 + B\times
\mathbb{G}_T</span> group elements to <span
class="math inline">(B + 1)\times\mathbb{G}_1 + B\times
\mathbb{G}_T</span> group elements.</p>
<p><span class="math display">
\mathsf{ct} =\left(
[k_1]_1,\ldots,[k_B]_1,\;
\left[\sum_{i=1}^{B}k_i\tau^i\right]_1,\;
[k_1\tau^{B+1}]_T+m_1,\ldots,[k_B\tau^{B+1}]_T+m_B
\right).
</span></p>
<div data-align="center">
<p>This is precisely the batch of ciphertexts together with the
partial decryption in the simple-BTE scheme! Thus the users and
the committee produce the ciphertext <span
class="math inline">\mathsf{ct}</span> in a <em>distributed</em>
manner.</p>
</div>
<p><strong>Decrypt:</strong> To decrypt the <span
class="math inline">i</span>-th ciphertext, we use <span
class="math inline">\{h_{\ell+B+1-i}\}_{\ell\in[0,B]\setminus\{i\}}</span>
as the witness which is readily available in the public
parameters. <span class="math display">
m_i = \mathsf{ct}_{i,2} - \mathsf{pd}\circ h_{B+1-i}
+ \sum_{\substack{\ell\in[B]\\\ell\ne i}}
\mathsf{ct}_{\ell,1}\circ h_{\ell+B+1-i}
</span></p>
<h3 id="malformed-ciphertexts">Malformed Ciphertexts</h3>
<p>The construction above assumes the helper can recover the
randomness for all ciphertexts. However, a malicious user can
always submit a malformed ciphertext that fails the decryption
checks. In this case, the helper cannot simply output <span
class="math inline">\bot</span>, because a malicious helper
could suppress a valid ciphertext by falsely claiming it is
malformed.</p>
<p>One strategy is to have the helper provide the witness for
the underlying relation as part of the hint. This allows the
verifier to run the decryption locally and confirm that the
ciphertext is malformed. Indeed, this would work for [<a
href="https://eprint.iacr.org/2024/1516">CGPW25</a>, <a
href="https://eprint.iacr.org/2024/1575">AFP25</a>] since the
witness is <span class="math inline">O(1)</span> group elements.
But as we saw above, the witness for the Simple BTE relation is
actually <span class="math inline">O(B)</span> group elements
and decryption requires <span class="math inline">O(B)</span>
pairings. Naively using the above strategy would quickly destroy
the benefit of helper-aided verification. In <a
href="https://eprint.iacr.org/2026/760">our paper</a>, we show
how to use <a href="https://eprint.iacr.org/2019/1177">Inner
Pairing Product Proofs</a> to certify the malformed ciphertexts
more efficiently.</p>
<h2 id="evaluation">Evaluation</h2>
<p>We benchmarked the batch verification of decryption for the
simple BTE scheme on an M5 MacBook Pro in single-threaded mode.
Our implementation using arkworks can be found <a
href="https://github.com/commonwarexyz/simple-bte/pull/2">here</a>.</p>
<table>
<colgroup>
<col style="width: 9%" />
<col style="width: 14%" />
<col style="width: 12%" />
<col style="width: 29%" />
<col style="width: 34%" />
</colgroup>
<thead>
<tr>
<th style="text-align: center;"><span
class="math inline">B</span></th>
<th style="text-align: center;">Helper</th>
<th style="text-align: center;">Naive</th>
<th style="text-align: center;">Bandwidth-opt.</th>
<th style="text-align: center;">Verification-opt.</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align: center;">32</td>
<td style="text-align: center;">121.61 ms</td>
<td style="text-align: center;">89.61 ms (1.4 <span
class="math inline">\times</span>)</td>
<td style="text-align: center;">11.53 ms (10.5 <span
class="math inline">\times</span>)</td>
<td style="text-align: center;">7.274 ms (16.7 <span
class="math inline">\times</span>)</td>
</tr>
<tr>
<td style="text-align: center;">128</td>
<td style="text-align: center;">596.13 ms</td>
<td style="text-align: center;">415.27 ms (1.4 <span
class="math inline">\times</span>)</td>
<td style="text-align: center;">45.48 ms (13.1 <span
class="math inline">\times</span>)</td>
<td style="text-align: center;">14.93 ms (39.9 <span
class="math inline">\times</span>)</td>
</tr>
<tr>
<td style="text-align: center;">512</td>
<td style="text-align: center;">2.84 s</td>
<td style="text-align: center;">1.927 s (1.5 <span
class="math inline">\times</span>)</td>
<td style="text-align: center;">179.46 ms (15.8 <span
class="math inline">\times</span>)</td>
<td style="text-align: center;">34.45 ms (82.4 <span
class="math inline">\times</span>)</td>
</tr>
<tr>
<td style="text-align: center;">2048</td>
<td style="text-align: center;">12.78 s</td>
<td style="text-align: center;">8.751 s (1.5 <span
class="math inline">\times</span>)</td>
<td style="text-align: center;">726.68 ms (17.6 <span
class="math inline">\times</span>)</td>
<td style="text-align: center;">112.01 ms (114.1 <span
class="math inline">\times</span>)</td>
</tr>
<tr>
<td style="text-align: center;">16384</td>
<td style="text-align: center;">120.76 s</td>
<td style="text-align: center;">82.584 s (1.5 <span
class="math inline">\times</span>)</td>
<td style="text-align: center;">5.867 s (20.6 <span
class="math inline">\times</span>)</td>
<td style="text-align: center;">611.20 ms (197.6 <span
class="math inline">\times</span>)</td>
</tr>
<tr>
<td style="text-align: center;">32768</td>
<td style="text-align: center;">262.54 s</td>
<td style="text-align: center;">174.005 s (1.5 <span
class="math inline">\times</span>)</td>
<td style="text-align: center;">12.006 s (21.9 <span
class="math inline">\times</span>)</td>
<td style="text-align: center;">1.136 s (231.1 <span
class="math inline">\times</span>)</td>
</tr>
<tr>
<td style="text-align: center;">65536</td>
<td style="text-align: center;">556.09 s</td>
<td style="text-align: center;">366.852 s (1.5 <span
class="math inline">\times</span>)</td>
<td style="text-align: center;">23.937 s (23.2 <span
class="math inline">\times</span>)</td>
<td style="text-align: center;">1.988 s (279.7 <span
class="math inline">\times</span>)</td>
</tr>
</tbody>
</table>
<p>Helper refers to the time it takes to carry out decryption.
Producing hints has negligible overhead. For the batch
verification, we benchmarked three different strategies:</p>
<ul>
<li><strong>Naive:</strong> This is the “first attempt”
described above where the helper sends the recovered message
together with the corresponding witness as the hint, and the
verifier checks the decryption equation for each
ciphertext.</li>
<li><strong>Bandwidth-optimized:</strong> This is the strategy
described above where the helper sends the short PRG seed <span
class="math inline">\rho^k</span> for each ciphertext but this
comes at the cost of <span
class="math inline">\mathbb{G}_T</span> exponentiations for each
ciphertext.</li>
<li><strong>Verification-optimized:</strong> This is the
strategy described above where the helper sends the recovered
<span class="math inline">K^k</span> values directly and only
uses MSMs/Hashes for verification.</li>
</ul>
<p>While these benchmarks were run in single-threaded mode on an
M5 MacBook Pro, we expect them to scale well with
parallelization.</p>
<h2 id="applications">Applications</h2>
<p>We now outline two applications of helper-aided
decryption.</p>
<h3 id="reducing-operating-costs-of-encrypted-mempools">Reducing
Operating Costs of Encrypted Mempools</h3>
<p>Consider a globally distributed network of validators running
a chain with encrypted mempools. Each transaction is assumed to
be ~400 bytes (typical trades fit in ~300 bytes and we add ~100
bytes for ciphertext overhead). At 65K TPS, the proposer needs
to push about 26 MB of data to every participant in the network,
every second. To aid in scaling, we can use sub-batching where
the committee decrypts multiple batches but of a smaller size in
each slot. Each batch can then be processed in parallel,
potentially across different machines. Concretely, let’s assume
we use four sub-batches each with a batch size of 16384 and the
partial decryption increases from 48 bytes to 192 bytes.</p>
<p><strong>Local Decryption:</strong> If all validators carried
out the decryption locally, they would need to speed up
decryption by over <span class="math inline">\approx 500
\times</span>. In theory, this can be achieved by running four
large instances that come with 128 vCPUs each (say) and cost
<span class="math inline">\approx 4 \times \$6.5</span> per
hour, but this is much more expensive than the <span
class="math inline">\$2</span>-<span
class="math inline">\$3</span> per hour it normally costs to
rent compute as a validator.</p>
<p>With helper aided decryption:</p>
<ul>
<li>In the <strong>Verification-optimized</strong> version, the
helper needs to distribute an additional 38 MB of data to every
participant in the network, every second. However, this comes
with the benefit of being able to batch verify the decryption of
ciphertexts in under 2s (single threaded) instead of spending
556s decrypting them. When bandwidth is abundant and we have
room to double the throughput, this is the preferred
option.</li>
<li>In the <strong>Bandwidth-optimized</strong> version, the
helper needs to distribute just 1 MB of data to every
participant in the network, every second. The validators spend
about 24 s (single threaded) verifying the decryption but this
can of course be parallelized. This allows us to retain the
benefits of batched verification (23 <span
class="math inline">\times</span> speedup) with a modest (~4%)
increase in bandwidth usage.</li>
</ul>
<p>In the figure below, we provide a visual representation of
the three different decryption strategies. Pricing is estimated
by assuming perfect parallelization of single threaded
performance and calculating the number of threads required to
attain 65K TPS. For local decryption we use 4 <span
class="math inline">\times</span> c8id.32x large instances (128
vCPUs each), for verification optimized hints we use r6id.large
(2 vCPUs), and for bandwidth optimized hints we use z1d.6xlarge
(24 vCPUs). Reducing costs through the use of specialized
hardware such as GPUs/FPGAs is an interesting avenue for future
work.</p>
<figure>
<img src="/imgs/batch-mempool-decryption.png"
alt="Helper-aided decryption reduces validator compute requirements compared to local decryption." />
<figcaption aria-hidden="true">Helper-aided decryption reduces
validator compute requirements compared to local
decryption.</figcaption>
</figure>
<p>In both helper aided architectures, even though the helper
spends a lot more resources to carry out decryption, the
marginal cost to support additional validators is sending ~1 MB
of hints. Thus, we are able to support the same level of
decentralization with minimal overhead.</p>
<p>A knee-jerk criticism is that validators must wait to receive
hints from the helper which increases latency. We dig deeper and
address these concerns.</p>
<p>We envision a system where there are dedicated fee paying
accounts which can only be used to pay the fees for encrypted
transactions. Additionally, we delay the state root update by a
small number of slots, say 10 blocks. Because the balances of
fee paying accounts are never encrypted, they can be updated
immediately by validators even without hints. Transactions that
can pay base fee can be sorted and proposed based on priority
fees.</p>
<figure>
<img src="/imgs/encrypted-transaction.png"
alt="Encrypted transactions can be sequenced before helpers provide decryption hints." />
<figcaption aria-hidden="true">Encrypted transactions can be
sequenced before helpers provide decryption hints.</figcaption>
</figure>
<p>While it’s true that validators will incur additional latency
before they see the latest state of the chain, note that it does
not materially affect their ability to propose and vote on
blocks. Thus, they have no motivation to decrypt faster (as the
data being sequenced is encrypted). Specialized parties such as
RPC providers / Searchers / Market Makers are incentivized to
decrypt transactions quickly in order to gain an edge and can
then act as helper parties assisting the network. The buffer for
state root updates also makes helper failures easier to absorb:
the network can fall back to another helper or to local
decryption, spreading the recovery process across several slots
rather than forcing all validators to catch up in a single
block.</p>
<h3 id="blinded-sequencer">Blinded Sequencer</h3>
<p>Most rollups today use a single sequencer who is responsible
for building and proposing blocks but they have a lot of
influence over the chain as they can censor/reorder
transactions. Currently, users (at best) get a promise that
their transactions will not be censored/frontrun but there are
no formal guarantees.</p>
<p>Instead, consider a dedicated sequencer where transactions
are encrypted to some committee who will release partial
decryption shares only after the sequencer commits. This
provides the performance benefits of a single sequencer but with
a <em>cryptographic</em> guarantee of transaction privacy until
inclusion. Concerns around censorship through metadata such as
fee payer accounts/IP address leakage can be mitigated via <a
href="https://datatracker.ietf.org/wg/privacypass/about/">anonymous
tokens</a> or routing transactions through an RPC provider that
acts as the fee payer.</p>
<p>Furthermore, the sequencer itself can act as the helper party
and broadcast hints to the network. This colocation allows the
sequencer to begin a large chunk (~90%) of the decryption work
that we refer to as <a href="/blogs/bte">“pre-decryption”</a>
immediately after it has built the block. It does not have to
wait for decryption shares to be released and allows decryption
work to be pipelined with block dissemination.</p>
<div id="footer-placeholder"></div>
<script src="/shared.js"></script>
</body>
</html>