mirror of
https://github.com/lux-apps/papers.git
synced 2026-10-30 18:15:21 +00:00
zeekay
abf99d05fc
Restructured from flat .tex/.pdf files into per-paper subdirectories. Added Antje Worring as co-author on all papers. Synced PDFs to pdfs/ for download site.
28 lines
1.2 KiB
TeX
28 lines
1.2 KiB
TeX
\section{Message Batching}
|
|
\label{sec:batching}
|
|
|
|
\subsection{Merkle Batch Proofs}
|
|
|
|
For high-throughput applications, multiple messages can be batched:
|
|
|
|
\begin{algorithm}[H]
|
|
\caption{Batched Warp Delivery}
|
|
\label{alg:batch}
|
|
\begin{algorithmic}[1]
|
|
\Require Messages $\mathcal{M}_1, \ldots, \mathcal{M}_k$ for same destination
|
|
\State $\mathsf{root} \gets \mathsf{MerkleRoot}(d(\mathcal{M}_1), \ldots, d(\mathcal{M}_k))$
|
|
\State Validators sign $\mathsf{root}$ instead of individual digests
|
|
\State $\Pi_{\text{batch}} \gets (\sigma_{\text{agg}}, \mathsf{bm})$ over $\mathsf{root}$
|
|
\State Relayer submits $(\mathcal{M}_1, \ldots, \mathcal{M}_k, \Pi_{\text{batch}}, \text{Merkle proofs})$
|
|
\State Destination verifies aggregate signature on $\mathsf{root}$
|
|
\State For each $\mathcal{M}_j$: verify Merkle proof, execute payload
|
|
\end{algorithmic}
|
|
\end{algorithm}
|
|
|
|
\begin{proposition}[Batch Efficiency]
|
|
Batching $k$ messages reduces total verification cost from $k \cdot C_{\text{verify}}$ to $C_{\text{verify}} + k \cdot C_{\text{merkle}}$, where $C_{\text{merkle}} \ll C_{\text{verify}}$.
|
|
\end{proposition}
|
|
|
|
For $k = 100$ messages: individual verification costs $100 \times 50{,}000 = 5{,}000{,}000$ gas; batched costs $50{,}000 + 100 \times 2{,}000 = 250{,}000$ gas---a 20x reduction.
|
|
|