# AmberNet: A Compact End-to-End Model for Spoken Language Identification

###### Abstract

We present AmberNet, a compact end-to-end neural network for Spoken Language
Identification. AmberNet consists of 1D depth-wise separable convolutions and
Squeeze-and-Excitation layers with global context, followed by statistics
pooling and linear layers. AmberNet achieves performance similar to state-of-
the-art (SOTA) models on VoxLingua107 dataset, while being 10x smaller.
AmberNet can be adapted to unseen languages and new acoustic conditions with
simple finetuning. It attains SOTA accuracy of 75.8% on FLEURS benchmark. We
show the model is easily scalable to achieve a better trade-off between
accuracy and speed. We further inspect the model’s sensitivity to input length
and show that AmberNet performs well even on short utterances.

Index Terms—  Spoken Language Identification, LangId, VoxLingua107, FLEURS

##  1 Introduction

Spoken Language Identification (LangID) is an important pre-processing step in
many applications. This task requires robust performance while introducing
minimal latency in the pipeline.

Early LangID models mostly relied on acoustic, phonetic, prosodic,
morphologic, and semantic level representations [1]. Recently, approaches
based on deep neural networks have outperformed traditional systems [2]. [3]
explores using Long Short Term Memory (LSTM) for LangID task on NIST LRE 2009,
and demonstrates that it can exploit temporal dependencies effectively. [4]
conducts experiments using bottleneck features from Convolutional Neural
Network (CNN) on noisy RATS Radio traffic data [5] and shows it has consistent
improvement regardless of various audio conditions and durations. [6] proposes
to add time-frequency attention mechanism to Time Delay Neural Network
architecture (TDNN) and CNN-LSTM-TDNN models to capture longer temporal
dependencies, and shows that frequency attention is more effective than time
attention. More recently, ECAPA-TDNN [7] further enhances TDNN performance on
speaker task by introducing additional skip connections. [8] adopts the
architecture to LangID task, training on VoxLingua107 [9] and achieving 6.7%
error rate on the evaluation set.

Another approach for LangID is to first learn a good language representation
vector, which can then be used for language category classification. To learn
such a vector, one can use self-supervised learning (SSL). Large scale speech
understanding models like XLS-R (0.3B) [10] and w2v-bert-51 (0.6B) [11] are
able to achieve great results by pre-training with more than 400k unlabeled
data and then fine-tuning on LangID datasets. More recently, [12] feeds the
outputs of XLS-R (0.3B) model through an attentive pooling layer [13],
achieving state-of-the-art (SOTA) results of 4.7% on VoxLingua107. Though SSL-
pretrained models show great performance, the huge model size makes it hard to
be deployed to compute-constrained scenarios.

There are two important capabilities of LangID model that have been rarely
investigated. 1) LangID model is expected to be robust to unseen domains and
be easily adapted to unseen languages. 2) Though the performance of LangID
task is highly sensitive to the duration of speech and is bounded by the
amount of information contained [14], LangID model should be robust on short
speech.

Our contributions include the following:

  * •

We propose AmberNet, a compact end-to-end neural network (NN) for LangID,
which combines local features from 1D depth-wise separable convolutions and
global context from Squeeze and Excitation (SE) layers [15]

  * •

On VoxLingua107 dataset, we show that the model is able to achieve SOTA
performance among models that are trained from scratch. Its accuracy is
similar to XLS-R model which uses SSL pretraining. Note that AmberNet is 10X
smaller than XLS-R.

  * •

We examine AmberNet’s adaptation capability to unseen languages and new
acoustic conditions. On the FLEURS dataset, AmberNet outperforms the previous
SOTA model using 20 times less number of parameters.

  * •

We study how the accuracy depends on segment length, and demonstrate that
model performs well even on short $\leq 5s$ segments.

  * •

We show that the model can be easily scaled up or down for better accuracy or
lower latency respectively.

Fig. 1: AmberNet Encoder is based on ContextNet architecture [16]. The Encoder
starts with a prolog block $B_{0}$, then $B$ residual mega-blocks, and an
epilog module $B_{N}$. Each residual block consists of $R$ “basic” blocks and
a squeeze-excite module in the end. A basic block is combined from 1D time-
channel separable convolution with kernel K and the number of channel $C$,
batch-norm, ReLU, and dropout. The decoder contains a statistic pooling layer
and two linear layers.

##  2 MODEL ARCHITECTURE

AmberNet consists of an encoder which is a 1D depth-wise channel separable
convolutional model with a ContextNet-like [16, 17] architecture and a decoder
as shown in Fig. 1.

The AmberNet encoder starts with a prolog block $B_{0}$, and followed by mega
blocks $B_{1}...B_{N-1}$. Each mega block begins with time-channel separable
convolutional [18] (noted as 1D Conv in Figure 1) module with stride 1 and
dilation 1, followed by BatchNorm, ReLU, and Dropout. Each 1D Conv module
compromises two parts: a depth-wise convolutional layer and a 1x1 pointwise
convolutional layer. These layers are repeated $R$ times and they are
residually connected with SE [15] layers with global average pooling as in
[17, 19]. The encoder ends with an epilog block $B_{N}$ and outputs
intermediary audio features.

The encoded audio features are passed to the decoder to perform
classification. The decoder contains two parts: a statistics pooling layer
(mean and std) [20] to map variable length of input audio features to fixed-
length feature representation, and two linear layers, one of output size 512
and another for a linear transformation from 512 to the final number of
classes $N$.

##  3 Experiment Setup and Results

###  3.1 Train on VoxLingua107

####  3.1.1 Dataset

VoxLingua107 [9] is a large dataset designed for LangID task which contains
diverse YouTube data for 107 languages. The dataset is quite noisy with
samples containing synthetic speech, singing, yelling, etc. The size of the
official training set is 6628 hours, 62 hours per language on average, but
it’s highly imbalanced.

We split 10% of data of each language in training set into validation set. The
input utterances have been split into non-overlap 3-second segments resulting
in 5.9M and 656K segments in train and validation set respectively. The
dataset comes with an official evaluation set of 1609 verified utterances
covering 33 languages. The duration of evaluation samples varies from 1.7
seconds to 19.98 seconds. From 1609 samples, 253 are found to be less than 5
seconds.

####  3.1.2 Training setup

The audio segments are pre-processed into 80-dimensional log-melspectrogram
calculated using 25ms window with stride of 10ms. Due to the extreme imbalance
of the number of samples for each language in training data, the AmberNet
model is trained with weighted cross entropy loss. The weight of each class is
calculated from data using

$w_{i}=\frac{\sum_{n=0}^{N}{c_{n}}}{c_{i}},$

where $N$ is number of classes and $c_{i}$ is number of samples of the given
class $i$. The weights are then normalized to sum up to one. To value the
minority class, macro accuracy which computes the accuracy for each class and
then take the average are used during validation to select the best checkpoint
for each run.

All models were trained for 40 epochs on 4 nodes with 8 GPUs in each node with
a batch size of 128 per GPU. We utilized the Adam optimizer and Cosine
Annealing learning rate scheduler with a warm-up ratio of 10%. A maximum
learning rate of 0.001 and a minimum learning rate of 0.0001 were used. We
apply noise augmentation, speed perturbation with 0.95x and 1.05x, and RIR
impulse corpora [21] augmentation as well as SpecAugment [22].

####  3.1.3 Results

We compare AmberNet with two other models trained from scratch: Resnet34 [9]
and ECAPA-TDNN [8]. We also add a comparison with three pre-trained self-
supervised learning (SSL) models finetuned on LangID task: wav2vec2.0 [10],
XLS-R [10] and XLS-R-attentive [12]. XLS-R [10] is a cross-lingually wav2vec
2.0 model which has been pretrained on 436K hours of 128 languages data
including VoxLingua107, and it has 300M parameters. It achieves 5.7% error
rate on the official evaluation set. XLS-R-attentive [12] extends XLS-R with
an additional attentive pooling layer and reaches 4.7% error rate. We have
also experimented with attentive pooling layer in [17] instead of statistic
pooling layer but we don’t observe performance gain.

Model | params | error rate (%)
---|---|---
(M) | 0…5s | 5…20s | avg
trained from scratch |  |  |  |
Resnet34 [9] | 21 | 12.3 | 6.1 | 7.1
ECAPA-TDNN [8]111The number of parameters and error rate are obtained with checkpoint https://huggingface.co/speechbrain/lang-id-VoxLingua107-ecapa | 21 | 11.9 | 6.7 | 7.5
AmberNet-3x5x1024 | 29 | 7.5 | 5.2 | 5.6
finetuned from SSL |  |  |  |
wav2vec2.0 [10] | 300 | 11.5 | 6.3 | 7.2
XLS-R [10] | 300 | 9.1 | 5.0 | 5.7
XLS-R-attentive [12] | 300 | - | - | 4.7
Table 1: Error rate on VoxLingua107 evaluation set. We compare AmberNet with
(1) two other models trained from scratch: Resnet34 [9] and ECAPA-TDNN [8];
(2) three pre-trained self-supervised learning (SSL) models finetuned on
VoxLingua107: wav2vec2.0 [10], XLS-R [10] and XLS-R-attentive [12]. Accuracy
numbers are computed for different utterance length categories and on all
samples.

In Table 1, we show that AmberNet-3x5x1024 achieves 5.6% error rate on all
samples, and it achieves 7.5% and 5.2% error rate for the short and long
recordings respectively. AmberNet gets SOTA performance for models trained
from scratch and it has accuracy close to pretrained SSL models while being
ten times smaller. The lowest error rate on 0-5 seconds samples also suggests
that AmberNet is robust even on relatively short samples.

In Fig. 2, we demonstrate number of the wrongly identified samples in each
languages in evaluation set with bright blue ink. And we can notice that the
most wrongly predicted languages are Urdu, English and Norwegian. Among the
errors, most of them occur between closely related languages such as “Urdu
$\rightarrow$ Hindi”, “Norwegian $\rightarrow$ Norwegian Nynorsk” and “Spanish
$\rightarrow$ Galician”. The English samples that have been wrongly identified
as Welsh could possibly due to bad quality of the retrieved Welsh data as
stated in [9].

Fig. 2: Number of samples for each language in VoxLingua107 evaluation set.
Dark blue represents accurately identified samples of AmberNet-3x5x1024.

###  3.2 Finetune on FLEURS

Trained on VoxLingua107, AmberNet has seen 82 out of 102 languages from
FLEURS. It has 77.9% macro accuracy on these seen languages. To investigate
the ability of adapting AmberNet to unseen languages and acoustic conditions,
we fine-tune AmberNet-3x5x1024 on the union of FLEURS and VoxLingua107.

####  3.2.1 Dataset

FLEURS [23] was created by recording 2009 sentences from FLoRes-101 benchmark
by three different native speakers for each language. The sizes of training,
dev, and test are 987h, 120h, 283h respectively. It has official split for
LangID task where speakers of the train sets are different than speakers from
the dev/test sets. There are 678K and 83K segments in FLEURS train and
validation set respectively after splitting utterances into non-overlap 3
seconds segments. 222 Note that VoxLingua107 is much diverse and noisy than
FLEURS. For example, the VoxLingua107 is based on YouTube data, and FLEURS
contains recorded Wikipedia sentences.

####  3.2.2 Fine-tuning setup

We fine-tune AmberNet-3x5x1024 which has been pre-trained on VoxLingua107 on
the combination of VoxLingua107 and FLEURS training sets. We freeze AmberNet
encoder and change number of output classes in decoder to 127 (VoxLingua107
union FLEURS). During fine-tuning, the weight of loss is calculated by the sum
of occurrence of each class from the two datasets. Model is fine-tuned for 5
epochs on a node with 8 GPUs. We use the same hyper-parameters as for
VoxLingua107, except: initial learning rate of 1e-5, dropout of 0.1 and speed
perturbation for augmentation.

####  3.2.3 Results

model | params | # languages |  macro acc (%)
---|---|---|---
(M) | pretrain | finetune
w2v-bert-51 [11] | 600 | 51 | 102 | 71.4
AmberNet | 29 | 107 | 127 | 75.8
Table 2: AmberNet-3x5x1024 finetuned on the union of FLEURS and VoxLingua107,
vs pretrained w2v-bert-51 fine-tuned on FLEURS.

We compare with wav2vec-BERT model, w2v-bert-51 which has 600M parameters.
w2v-bert-51 [11] was first SSL-pretrained on 429k unlabeled data from 51
languages, and then fine-tuned on FLEURS. It achieves 71.4% macro accuracy on
FLEURS test set . As shown in Table 2, AmberNet-3x5x1024 outperforms 20x
larger SSL pre-trained model w2v-bert-51 (0.6B) on FLEURS test set.

##  4 Ablation study

Since LangID model is frequently used as a pre-processing step for ASR, it is
expected to introduce less latency and extra processing time as possible,
especially for online mode. Hence both the input segment length for inference
and the model size are crucial parameters.

###  4.1 Input length for inference

Typically, the longer the segments, the more language information presented
thus leading to higher accuracy of identification. In this section, we
investigate how the input length would impact performance of the model.
AmberNet is able to classify the input segments with different lengths by
mapping variable-length utterances to a fixed-length representation. In Figure
3, we split the evaluation samples into segments of different lengths with
stride 2, resulting less number of samples with large segment length. It can
be seen that even though the model was trained with 3-second segments, the
model can still perform well and even better with segments of larger length.

###  4.2 Model scalability

R | C | Params | val | eval
---|---|---|---|---
(M) | macro acc (%) | error rate (%)
3 | 256 | 7.3 | 89.8 | 9.6
5 | 256 | 7.7 | 90.7 | 8.4
7 | 256 | 8.1 | 92.1 | 9.2
5 | 512 | 12.3 | 93.5 | 7.0
5 | 1024 | 28.9 | 95.0 | 5.6
5 | 2048 | 92.1 | 95.9 | 6.8
Table 3: AmberNet: scalablity study. We use the same number of blocks $B=3$
for all experiments and change model depth using umber of sub-blocks $R$ and
model width with number of channels $C$ respectively.

Fig. 3: The error rate of AmberNet-3x5x1024 on VoxLingua107 evaluation set
with different segment length. Generally the larger the input length, the
better the model performs.

The depth and width of AmberNet could be increased or decreased by number of
repeated layers R and changing filter size C. In this section, we report both
validation macro accuracy and evaluation error rate because as shown in Figure
2, the evaluation set is quite small and the distribution of it is imbalanced.
As seen in Table 3, the validation macro accuracy would increase alongside the
model size. The inconsistent trend of error rate could possibly due to the
limitation of evaluation set. AmberNet-3x5x512 with 12.3M parameters
outperforms the baseline model ECAPA-TDNN with 21M parameters. The model could
be easily scaled down for faster inference speed for constrained deployment
conditions or scaled with for better performance.

##  5 Conclusion

In this paper, we present AmberNet, an end-to-end model for language
identification. It combines 1D depth-wise separable convolutions and Squeeze-
and-Excite mechanism with global context to extract intermediary dimensional
vector representations. The representations are then sent to a classifier to
identify the language of the input audio.

AmberNet achieves SOTA accuracy on the VoxLingua107 dataset among models
trained from scratch. It is close to SOTA for SSL-pretrained models while
being 10x fewer parameters. This makes AmberNet an attractive model for memory
or compute-constrained environments. We also show that AmberNet can be adapted
to unseen languages and new acoustic conditions with simple fine-tuning. It
achieves new SOTA result on FLEURS.

The model’s implementation and checkpoint
333https://catalog.ngc.nvidia.com/orgs/nvidia/teams/nemo/models/
langid_ambernet are made available through NeMo - a conversational AI toolkit
[24].

## References

  * [1] H. Li, B. Ma, and K. A. Lee,  “Spoken language recognition: From fundamentals to practice,”  Proceedings of the IEEE, vol. 101, pp. 1136–1159, 05 2013.
  * [2] I. Lopez-Moreno, J. Gonzalez-Dominguez, O. Plchot, D. Martinez, J. Gonzalez-Rodriguez, and P. Moreno,  “Automatic language identification using deep neural networks,”  in ICASSP, 2014.
  * [3] J. Gonzalez-Dominguez, I. Lopez-Moreno, H. Sak, J. González-Rodríguez, and P. J. Moreno,  “Automatic language identification using long short-term memory recurrent neural networks,”  in INTERSPEECH, 2014.
  * [4] S. Ganapathy, K. Han, S. Thomas, M. Omar, M. Van Segbroeck, and S. Narayanan,  “Robust language identification using convolutional neural network features,”  in INTERSPEECH, 2014.
  * [5] K. Walker and S. M. Strassel,  “The RATS radio traffic collection system,”  in Odyssey 2012: The Speaker and Language Recognition Workshop, Singapore, June 25-28, 2012, H. Li, B. Ma, and K. Lee, Eds. 2012, pp. 291–297, ISCA.
  * [6] X. Miao, I. McLoughlin, and Y. Yan,  “A New Time-Frequency Attention Mechanism for TDNN and CNN-LSTM-TDNN, with Application to Language Identification,”  in Proc. Interspeech, 2019.
  * [7] B. Desplanques, J. Thienpondt, and K. Demuynck,  “ECAPA-TDNN: Emphasized channel attention, propagation and aggregation in TDNN based speaker verification,”  arXiv:2005.07143, 2020.
  * [8] M. Ravanelli, T. Parcollet, P. Plantinga, A. Rouhe, S. Cornell, L. Lugosch, C. Subakan, N. Dawalatabad, A. Heba, J. Zhong, J.-C. Chou, S.-L. Yeh, S.-W. Fu, C.-F. Liao, E. Rastorgueva, F. Grondin, W. Aris, H. Na, Y. Gao, R. D. Mori, and Y. Bengio,  “SpeechBrain: A general-purpose speech toolkit,” 2021,  arXiv:2106.04624.
  * [9] J. Valk and T. Alumäe,  “Voxlingua107: a dataset for spoken language recognition,”  in IEEE SLT, 2021.
  * [10] A. Babu, C. Wang, A. Tjandra, K. Lakhotia, Q. Xu, N. Goyal, K. Singh, P. von Platen, Y. Saraf, J. Pino, et al.,  “Xls-r: Self-supervised cross-lingual speech representation learning at scale,”  arXiv:2111.09296, 2021.
  * [11] A. Conneau, A. Bapna, Y. Zhang, M. Ma, P. von Platen, A. Lozhkov, C. Cherry, Y. Jia, C. Rivera, M. Kale, et al.,  “Xtreme-s: Evaluating cross-lingual speech representations,”  arXiv:2203.10752, 2022.
  * [12] K. Kukk and T. Alumäe,  “Improving language identification of accented speech,”  arXiv:2203.16972, 2022.
  * [13] Y. Zhu, T. Ko, D. Snyder, B. Mak, and D. Povey,  “Self-Attentive Speaker Embeddings for Text-Independent Speaker Verification,”  in Proc. Interspeech, 2018.
  * [14] M. Van Segbroeck, R. Travadi, and S. S. Narayanan,  “Rapid language identification,”  IEEE/ACM Transactions on Audio, Speech, and Language Processing, vol. 23, no. 7, pp. 1118–1129, 2015.
  * [15] J. Hu, L. Shen, and G. Sun,  “Squeeze-and-excitation networks,”  in IEEE CVPR, 2018.
  * [16] W. Han, Z. Zhang, Y. Zhang, J. Yu, C.-C. Chiu, J. Qin, A. Gulati, R. Pang, and Y. Wu,  “Contextnet: Improving convolutional neural networks for automatic speech recognition with global context,”  arXiv:2005.03191, 2020.
  * [17] N. R. Koluguri, T. Park, and B. Ginsburg,  “Titanet: Neural model for speaker representation with 1d depth-wise separable convolutions and global context,”  in ICASSP, 2022.
  * [18] S. Kriman, S. Beliaev, B. Ginsburg, J. Huang, O. Kuchaiev, V. Lavrukhin, R. Leary, J. Li, and Y. Zhang,  “Quartznet: Deep automatic speech recognition with 1d time-channel separable convolutions,”  in ICASSP, 2020.
  * [19] S. Majumdar, J. Balam, O. Hrinchuk, V. Lavrukhin, V. Noroozi, and B. Ginsburg,  “Citrinet: Closing the gap between non-autoregressive and autoregressive end-to-end models for automatic speech recognition,”  arXiv:2104.01721, 2021.
  * [20] D. Snyder, D. Garcia-Romero, G. Sell, D. Povey, and S. Khudanpur,  “X-vectors: Robust dnn embeddings for speaker recognition,”  in ICASSP. IEEE, 2018.
  * [21] T. Ko, V. Peddinti, D. Povey, M. L. Seltzer, and S. Khudanpur,  “A study on data augmentation of reverberant speech for robust speech recognition,”  in ICASSP, 2017.
  * [22] D. S. Park, W. Chan, Y. Zhang, C.-C. Chiu, B. Zoph, E. D. Cubuk, and Q. V. Le,  “SpecAugment: A simple data augmentation method for automatic speech recognition,”  arXiv:1904.08779, 2019.
  * [23] A. Conneau, M. Ma, S. Khanuja, Y. Zhang, V. Axelrod, S. Dalmia, J. Riesa, C. Rivera, and A. Bapna,  “FLEURS: Few-shot learning evaluation of universal representations of speech,”  arXiv:2205.12446, 2022.
  * [24] O. Kuchaiev, J. Li, H. Nguyen, O. Hrinchuk, R. Leary, B. Ginsburg, S. Kriman, S. Beliaev, V. Lavrukhin, J. Cook, et al.,  “Nemo: a toolkit for building ai applications using neural modules,”  arXiv:1909.09577, 2019.


generally when $\rho^{\prime}\ll\rho$ along the evolution of the coupled VS
and HS. In particular, this is the case both after relativistic thermalization
or when the dark photons are non-relativistic but already decaying,
$t\gtrsim\tau^{\prime}$, so that their abundance is exponentially suppressed.
In all these cases, we may rewrite the equation (4) for the abundance of DP as

$\displaystyle\frac{dY^{\prime}}{dt}+\sigma^{\prime}xY^{\prime}$
$\displaystyle\approx$ $\displaystyle{g^{\prime}\over
8g_{\ast}}\sigma^{\prime}x^{3}K_{1}(x)$ (100)

where $x=m^{\prime}/T$, $Y^{\prime}=n^{\prime}/s$ and
$\sigma^{\prime}=\Gamma^{\prime}/H^{\prime}\lesssim 1$ with
$H^{\prime}=H(m^{\prime})$. The lhs takes into account dark photon decay while
the rhs is the source terms from FI production. As before in the present work,
we have used MB statistic to express $n^{\prime}_{\rm eq}$ and
$\langle\Gamma^{\prime}\rangle$ in terms of Bessel functions, cf appendix A.
This Boltzmann equation is readily integrated to give

$\displaystyle Y^{\prime}$ $\displaystyle=$ $\displaystyle
Y^{\prime}_{i}\,e^{-{\sigma^{\prime}\over 2}(x^{2}-x_{i}^{2})}$ (101)
$\displaystyle+$ $\displaystyle{g^{\prime}\over
8g_{\ast}}\sigma^{\prime}\int_{x_{i}}^{x}dx^{\prime}x^{\prime
3}K_{1}(x^{\prime})e^{-{\sigma^{\prime}\over 2}(x^{2}-x^{\prime 2})}$

The first term on rhs represents the decay of the initial dark photon
abundance, $e^{-\sigma^{\prime}x^{2}/2}\sim e^{-t/\tau^{\prime}}$; the second
one represents their production from the VS convoluted by dark photon decay.

The simple expression (101) captures several features that we observed in the
more complicated problem of reheating of the VS from a HS. For the sake of
brevity, we just sketch the key results, which can be readily verified by
inspection of the general solution. For this, we refer to figure 7 in which
some typical solutions are depicted.

Consider first the solid lines, say for $\xi_{i}=10^{-3}$. The abundance is
initially characterized by a plateau $Y^{\prime}\approx
Y_{i}^{\prime}\propto\xi_{i}^{3}$, analogous to the plateau in the case of a
hot HS. For such choice of parameters, the initial temperature ratio is stable
and we can discuss the freeze-out of DM along the line of section V, with
$\xi_{\rm fo}=\xi_{i}$. Eventually, freeze-in production of dark photons
becomes relevant. This occurs essentially when the heating parameter
$\kappa^{\prime}\sim(1/Y^{\prime})\langle\Gamma^{\prime}\rangle/H$ becomes
$\mathcal{O}(1)$, marking the onset of dark photon creation from the VS, after
which $Y^{\prime}\propto a^{3}$ (and so $\xi\propto a$). This combination of
parameters is akin to the heating parameter
$\kappa\sim(\rho^{\prime}/\rho)\langle\Gamma^{\prime}\rangle/H$ in the problem
of heating of the VS from the HS.888There is slight difference between the
criteria for the onset of particle creation
$\sim(1/Y^{\prime})\langle\Gamma^{\prime}\rangle/H\sim 1$ and that of energy
transfer
$\kappa^{\prime}\sim\rho/\rho^{\prime}\langle\Gamma^{\prime}\rangle/H\sim 1$
(heating parameter). For freeze-in, we deem more relevant to focus on the
number density of dark photons rather than on their mean energy. For the
problem of reheating of the VS, the key issue is of course that of energy
transfer. Different choices of $\xi_{i}$ depict the same behaviour and for all
they track the production of dark photons, a curve which in that respect
behaves as an attractor. Such behavior includes cases in which $\xi_{i}$ is
very low. For instance, for $\xi_{i}=10^{-6}$, the abundance of dark photons
produced by freeze-in increases rapidly (see solid purple line) toward this
attractor solution. This sharp initial increase of the number of dark photons
is analogous to the rapid increase of temperature to $T_{\rm max}$ in the
problem of reheating of the VS. This occurs when
$\kappa^{\prime}\sim(1/Y_{i})\langle\Gamma^{\prime}\rangle_{i}/H_{i}^{\prime}\gtrsim
1$ at the initial moment. In that case, the initial choice of $\xi_{i}$ is
unstable. In the body of the text and in figure 6 we require that

$\kappa^{\prime}_{i}\approx\frac{\rho_{i}}{3\rho^{\prime}_{i}}\frac{\langle\Gamma^{\prime}\rangle_{i}}{H_{i}}\lesssim
1$ (102)

for the stability of the initial temperature ratio when $\xi_{i}\lesssim 1$,
see section V.2.

After freeze-in production, the dark photons are non-relativistic and
$Y^{\prime}\sim$ constant until decay becomes relevant. As the solid and
dotted curves show, the largest the freeze-in production, the earlier the
decay of the dark photons. That trivially results from the fact that their
creation and disappearance are controlled by related processes (inverse and
direct decay), in other words by the kinetic mixing parameter. In particular,
a dark photon that would reach $Y^{\prime}\sim Y^{\prime}_{\rm eq}$ at $T\sim
m$ would, by definition, be in thermal equilibrium and would subsequently
track their equilibrium abundance, $n^{\prime}\propto e^{-m^{\prime}/T}$, see
the dot-dashed curve in fig.7. For a smaller kinetic mixing, their abundance
will overshoot the equilibrium abundance until they start to decay,
$n^{\prime}\propto e^{-\Gamma^{\prime}t}$, see solid and dotted curves. As is
known since some time, see Harvey et al. (1982), such dark photons may
eventually thermalize with the VS if $n^{\prime}\propto
e^{-\Gamma^{\prime}t}\sim n^{\prime}_{\rm eq}(T)$, see solid curves and their
merging with the equilibrium abundance. Such outcome is of course only
relevant if the number density $n^{\prime}$ is not a ridiculously small number
when that condition is met, see short dashed curve.

Figure 7: Examples of evolution of dark photons abundance for $\xi_{i}\ll 1$.
The mass $m^{\prime}$ is fixed at 5 MeV. The solid curves correspond to a
value for $\varepsilon$ of $10^{-9.4}$, only differing by the value of
$\xi_{i}$, and the long-dashed one to an $\varepsilon=10^{-8.5}$. The dotted
curves are obtained by setting $\varepsilon$ to $10^{-11}$. One can observe
the attractor behavior for the curves that share the same $\varepsilon$ and,
afterwards, the contact point between $Y^{\prime}$ and its equilibrium value
$Y^{\prime}_{\rm eq}$ for this choice of parameters.

## References

  * Patt and Wilczek (2006) B. Patt and F. Wilczek (2006), eprint hep-ph/0605188.
  * Foot et al. (1991) R. Foot, H. Lew, and R. R. Volkas, Phys. Lett. B 272, 67 (1991).
  * Strassler and Zurek (2007) M. J. Strassler and K. M. Zurek, Phys. Lett. B 651, 374 (2007), eprint hep-ph/0604261.
  * Curtin and Sundrum (2017) D. Curtin and R. Sundrum (2017), eprint 1702.02524.
  * Spergel and Steinhardt (2000) D. N. Spergel and P. J. Steinhardt, Phys. Rev. Lett. 84, 3760 (2000), eprint astro-ph/9909386.
  * Tulin and Yu (2018) S. Tulin and H.-B. Yu, Phys. Rept. 730, 1 (2018), eprint 1705.02358.
  * Schwaller (2015) P. Schwaller, Phys. Rev. Lett. 115, 181101 (2015), eprint 1504.07263.
  * Dodelson and Widrow (1994) S. Dodelson and L. M. Widrow, Phys. Rev. Lett. 72, 17 (1994), eprint hep-ph/9303287.
  * McDonald (2002) J. McDonald, Phys. Rev. Lett. 88, 091304 (2002), eprint hep-ph/0106249.
  * Hall et al. (2010) L. J. Hall, K. Jedamzik, J. March-Russell, and S. M. West, JHEP 03, 080 (2010), eprint 0911.1120.
  * Chu et al. (2012) X. Chu, T. Hambye, and M. H. G. Tytgat, JCAP 05, 034 (2012), eprint 1112.0493.
  * Bernal et al. (2017) N. Bernal, M. Heikinheimo, T. Tenkanen, K. Tuominen, and V. Vaskonen, Int. J. Mod. Phys. A 32, 1730023 (2017), eprint 1706.07442.
  * Kolb and Turner (1990) E. W. Kolb and M. S. Turner, _The Early Universe_ , vol. 69 (1990), ISBN 978-0-201-62674-2.
  * Berlin et al. (2016a) A. Berlin, D. Hooper, and G. Krnjaic, Phys. Lett. B 760, 106 (2016a), eprint 1602.08490.
  * Heurtier and Huang (2019) L. Heurtier and F. Huang, Phys. Rev. D 100, 043507 (2019), eprint 1905.05191.
  * Ertas et al. (2022) F. Ertas, F. Kahlhoefer, and C. Tasillo, JCAP 02, 014 (2022), eprint 2109.06208.
  * Garani et al. (2021) R. Garani, M. Redi, and A. Tesi, JHEP 12, 139 (2021), eprint 2105.03429.
  * Berezhiani et al. (1996) Z. G. Berezhiani, A. D. Dolgov, and R. N. Mohapatra, Phys. Lett. B 375, 26 (1996), eprint hep-ph/9511221.
  * Adshead et al. (2016) P. Adshead, Y. Cui, and J. Shelton, JHEP 06, 016 (2016), eprint 1604.02458.
  * Hardy and Unwin (2017) E. Hardy and J. Unwin, JHEP 09, 113 (2017), eprint 1703.07642.
  * Tenkanen and Vaskonen (2016) T. Tenkanen and V. Vaskonen, Phys. Rev. D 94, 083516 (2016), eprint 1606.00192.
  * Sandick et al. (2021) P. Sandick, B. S. Es Haghi, and K. Sinha, Phys. Rev. D 104, 083523 (2021), eprint 2108.08329.
  * Ireland and Koren (2022) A. Ireland and S. Koren (2022), eprint 2211.13212.
  * Pospelov et al. (2008) M. Pospelov, A. Ritz, and M. B. Voloshin, Phys. Lett. B 662, 53 (2008), eprint 0711.4866.
  * Hannestad and Madsen (1995) S. Hannestad and J. Madsen, Phys. Rev. D 52, 1764 (1995), eprint astro-ph/9506015.
  * Kawasaki et al. (2000) M. Kawasaki, K. Kohri, and N. Sugiyama, Phys. Rev. D 62, 023506 (2000), eprint astro-ph/0002127.
  * Ackerman et al. (2009) L. Ackerman, M. R. Buckley, S. M. Carroll, and M. Kamionkowski, Phys. Rev. D 79, 023519 (2009), eprint 0810.5126.
  * Feng et al. (2009) J. L. Feng, M. Kaplinghat, H. Tu, and H.-B. Yu, JCAP 07, 004 (2009), eprint 0905.3039.
  * Holdom (1986) B. Holdom, Phys. Lett. B 166, 196 (1986).
  * Scherrer and Turner (1985) R. J. Scherrer and M. S. Turner, Phys. Rev. D 31, 681 (1985).
  * Coy et al. (2021) R. Coy, T. Hambye, M. H. G. Tytgat, and L. Vanderheyden, Phys. Rev. D 104, 055021 (2021), eprint 2105.01263.
  * Griest and Kamionkowski (1990) K. Griest and M. Kamionkowski, Phys. Rev. Lett. 64, 615 (1990).
  * Bernal et al. (2023) N. Bernal, P. Konar, and S. Show (2023), eprint 2311.01587.
  * An et al. (2013) H. An, M. Pospelov, and J. Pradler, Phys. Lett. B 725, 190 (2013), eprint 1302.3884.
  * Hambye et al. (2019) T. Hambye, M. H. G. Tytgat, J. Vandecasteele, and L. Vanderheyden, Phys. Rev. D 100, 095018 (2019), eprint 1908.09864.
  * Arvanitaki et al. (2021) A. Arvanitaki, S. Dimopoulos, M. Galanis, D. Racco, O. Simon, and J. O. Thompson, JHEP 11, 106 (2021), eprint 2108.04823.
  * Fairbairn et al. (2019) M. Fairbairn, E. Hardy, and A. Wickens, JHEP 07, 044 (2019), eprint 1901.11038.
  * Harvey et al. (1982) J. A. Harvey, E. W. Kolb, D. B. Reiss, and S. Wolfram, Nucl. Phys. B 201, 16 (1982).
  * Hannestad (2004) S. Hannestad, Phys. Rev. D 70, 043506 (2004), eprint astro-ph/0403291.
  * Dodelson and Turner (1992) S. Dodelson and M. S. Turner, Phys. Rev. D 46, 3372 (1992).
  * Mangano et al. (2005) G. Mangano, G. Miele, S. Pastor, T. Pinto, O. Pisanti, and P. D. Serpico, Nucl. Phys. B 729, 221 (2005), eprint hep-ph/0506164.
  * Berlin et al. (2016b) A. Berlin, D. Hooper, and G. Krnjaic, Phys. Rev. D 94, 095019 (2016b), eprint 1609.02555.
  * Gondolo and Gelmini (1991) P. Gondolo and G. Gelmini, Nucl. Phys. B 360, 145 (1991).
  * Berger et al. (2016) J. Berger, K. Jedamzik, and D. G. E. Walker, JCAP 11, 032 (2016), eprint 1605.07195.
  * Giudice et al. (1999) G. F. Giudice, A. Riotto, and I. Tkachev, JHEP 11, 036 (1999), eprint hep-ph/9911302.
  * Mondino et al. (2021) C. Mondino, M. Pospelov, J. T. Ruderman, and O. Slone, Phys. Rev. D 103, 035027 (2021), eprint 2005.02397.
  * Bringmann et al. (2021) T. Bringmann, P. F. Depta, M. Hufnagel, and K. Schmidt-Hoberg, Phys. Lett. B 817, 136341 (2021), eprint 2007.03696.
  * Bauer et al. (2018) M. Bauer, P. Foldenauer, and J. Jaeckel, JHEP 07, 094 (2018), eprint 1803.05466.
  * Hardy and Lasenby (2017) E. Hardy and R. Lasenby, JHEP 02, 033 (2017), eprint 1611.05852.
  * Arcadi et al. (2019) G. Arcadi, O. Lebedev, S. Pokorski, and T. Toma, JHEP 08, 050 (2019), eprint 1906.07659.
  * Hufnagel et al. (2018) M. Hufnagel, K. Schmidt-Hoberg, and S. Wild, JCAP 02, 044 (2018), eprint 1712.03972.
  * Hufnagel (2020) M. Hufnagel, Ph.D. thesis, Hamburg U., Hamburg (2020).
  * Bjorken et al. (1988) J. D. Bjorken, S. Ecklund, W. R. Nelson, A. Abashian, C. Church, B. Lu, L. W. Mo, T. A. Nunamaker, and P. Rassmann, Phys. Rev. D 38, 3375 (1988).
  * Athanassopoulos et al. (1998) C. Athanassopoulos et al. (LSND), Phys. Rev. C 58, 2489 (1998), eprint nucl-ex/9706006.
  * Bergsma et al. (1986) F. Bergsma et al. (CHARM), Phys. Lett. B 166, 473 (1986).
  * Blumlein et al. (1991) J. Blumlein et al., Z. Phys. C 51, 341 (1991).
  * Blümlein and Brunner (2014) J. Blümlein and J. Brunner, Phys. Lett. B 731, 320 (2014), eprint 1311.3870.
  * Alekhin et al. (2016) S. Alekhin et al., Rept. Prog. Phys. 79, 124201 (2016), eprint 1504.04855.
  * Baldes and Petraki (2017) I. Baldes and K. Petraki, JCAP 09, 028 (2017), eprint 1703.00478.
  * Flores and Petraki (2024) M. M. Flores and K. Petraki (2024), eprint 2405.02222.
  * Hambye et al. (2020) T. Hambye, M. Lucca, and L. Vanderheyden, Phys. Lett. B 807, 135553 (2020), eprint 2003.04936.
  * Hufnagel and Tytgat (2022) M. Hufnagel and M. H. G. Tytgat (2022), eprint 2212.09759.
  * Zyla et al. (2020) P. A. Zyla et al. (Particle Data Group), PTEP 2020, 083C01 (2020).
  * Davidson et al. (2008) S. Davidson, E. Nardi, and Y. Nir, Phys. Rept. 466, 105 (2008), eprint 0802.2962.
  * Morrissey and Ramsey-Musolf (2012) D. E. Morrissey and M. J. Ramsey-Musolf, New J. Phys. 14, 125003 (2012), eprint 1206.2942.
  * Dine and Kusenko (2003) M. Dine and A. Kusenko, Rev. Mod. Phys. 76, 1 (2003), eprint hep-ph/0303065.
  * Elor et al. (2019) G. Elor, M. Escudero, and A. Nelson, Phys. Rev. D 99, 035031 (2019), eprint 1810.00880.
  * Lozanov (2019) K. D. Lozanov (2019), eprint 1907.04402.
  * Davidson et al. (2000) S. Davidson, M. Losada, and A. Riotto, Phys. Rev. Lett. 84, 4284 (2000), eprint hep-ph/0001301.
  * Kajantie et al. (1996) K. Kajantie, M. Laine, K. Rummukainen, and M. E. Shaposhnikov, Phys. Rev. Lett. 77, 2887 (1996), eprint hep-ph/9605288.
  * Arnold et al. (1997) P. B. Arnold, D. Son, and L. G. Yaffe, Phys. Rev. D 55, 6264 (1997), eprint hep-ph/9609481.
  * Clery and Kimus (2024) S. Clery and J. Kimus (2024), eprint 24XX.YYYY.
  * Hufnagel et al. (in progress) M. Hufnagel, J. Kimus, and M. H. G. Tytgat (in progress).
  * Dvorkin et al. (2019) C. Dvorkin, T. Lin, and K. Schutz, Phys. Rev. D 99, 115009 (2019), [Erratum: Phys.Rev.D 105, 119901 (2022)], eprint 1902.08623.


# Blockchain Based Zero-Knowledge Proof of Location in IoT

Wei Wu, Erwu Liu, Xinglin Gong and Rui Wang  This work is supported in part by
the grants from the National Science Foundation of China (No. 61571330),
Shanghai Integrated Military and Cilivian Development Fund (No.
JMRH-2018-1075), and Science and Technology Commission of Shanghai
Municipality (No. 19511102002). Corresponding author: Erwu Liu. College of
Electronics and Information Engineering, Tongji University, Shanghai, China
Emails: {1832912, erwuliu, xinglingong<EMAIL_ADDRESS>
###### Abstract

With the development of precise positioning technology, a growing number of
location-based services (LBSs) facilitate people’s life. Most LBSs require
proof of location (PoL) to prove that the user satisfies the service
requirement, which exposes the user’s privacy. In this paper, we propose a
zero-knowledge proof of location (zk-PoL) protocol to better protect the
user’s privacy. With the zk-PoL protocol, the user can choose necessary
information to expose to the server, so that hierarchical privacy protection
can be achieved. The evaluation shows that the zk-PoL has excellent security
to resist main attacks, moreover the computational efficiency is independent
of input parameters and the zk-PoL is appropriate to delay-tolerant LBSs.

###### Index Terms:

Blockchain, zero-knowledge proof, location-based service, zk-PoL, IoT

##  I Introduction

In recent years, the popularity of smart terminal devices and the development
of sophisticated high-precision position sensors have led to many location
based-services (LBSs) [1], such as location-based rewards and digging
services, location-based recommendations and location-based social network
(LBSN) [2]. Most LBSs require the user’s proof of location (PoL) to prove that
the user satisfies service requirements. For example, a user needs to prove
that he is in the mart to obtain a discount coupon. While enjoying the
convenience of these services, the user’s location privacy is always revealed
through the PoL to the server or malicious adversaries. Hence, when the user
provides PoL to the server, the user’s privacy must be protected.

A large number of related works on PoL emerge to protect the user’s privacy.
The previously proposed PoL system architectures can be roughly divided into
two types: centralized and distributed. In the former, the user data is stored
in the central server, while the latter one applies distributed storage. Tyagi
et al. [3] propose a location privacy architecture based on the approach like
a mix zone model with other approaches to protect location privacy. Javali et
al. [4], based on channel state information (CSI) and fuzzy vault, a
cryptographic primitive, propose a location proof generation and verification
scheme in which provers can prove their presence in particular time with high
confidence. Li et al. [5], relying on the existing WiFi or cellular network
access points (APs), propose an infrastructure-based scheme to provide
privacy-preserving location proof, in which the database can verify the
location without knowing the user’s accurate location. All the above solutions
perform in a centralized way, which would lead to the following shortcomings.
First, a powerful dedicated central server is needed to serve a large number
of nodes, which results in an unbalanced load between the server and the node.
Once the server is overloaded, the entire system will be paralyzed. Second, a
malicious adversary is easier to capture the system because it has a single
opponent, the central server. Once the central server is captured, the entire
system is captured. Third, the user’s data is stored in the central server and
only the server can control them. This will lead to the user’s losing control
of his data.

In order to solve the problem of centralized architecture, Amoretti et al. [6]
propose a blockchain-based PoL system, in which users access a blockchain
network in a self-organized mode so that the users can communicate with
neighboring $witnesses$ and request them to issue location certificates.

Although this solution does not require a dedicated IoT device, the security
will be compromised because it does not restrict mobile nodes’ access to the
network and the permission of the nodes already accessed in the network is
also unrestricted. Therefore, combined with blockchain technology and zero-
knowledge proof, we propose a zero-knowledge proof of location (zk-PoL)
protocol. Our zk-PoL protocol consists of two parts: the generation scheme and
verification scheme. By generation scheme, an approved user could obtain a
location certificate from the smart AP. Here ’smart’ means that smart contact
can be embedded in the AP to regulate AP’s behavior and process data. By
verification scheme, the user could use the location certificate to generate a
zero-knowledge proof of location for LBSs he needs. Moreover, this zk-PoL
protocol allows the user to achieve hierarchical privacy protection by
generating different proofs with different input parameters. We also analyze
the performance of the zk-PoL protocol in security and computational
efficiency. The security analysis shows that the zk-PoL is able to resist the
main attacks. The experiment demonstrates that the system performance is
independent of input parameters and the zk-PoL is applicable to delay-tolerant
LBSs.

The remainder is organized as follows. In Section II, we introduce the
essentials of blockchain and zero-knowledge proof. In Section III, we build
our system model and based on it, we give our zk-PoL protocol. In Section IV
we analyze the security and computational efficiency of our system. In Section
V, we conclude the work of this paper.

##  II Preliminary

This section briefly introduces the knowledge of blockchain technology and
zero-knowledge proof.

###  II-A Blockchain Technology

Blockchain technology is a fusion of multiple technologies, including
encryption, consensus mechanisms, incentives, distributed storage and smart
contracts [7, 8, 9]. In essence, a blockchain is a chained public ledger
guaranteed to be indestructible with cryptographic methods. It consists of a
series of blocks, and the latter block is connected to the previous one by
including the cryptographic hash of the previous block. In addition, the block
also contains timestamps, nonce, transaction data, etc. Its structure is shown
in Fig. 1.

Figure 1: Structure of A Simplified Block Chain

Then, by the consensus algorithm, such as Proof of Work (PoW) and Proof of
Stake (PoS), all peers in the network agree on the ownership of the
bookkeeping right. The peer that obtains the bookkeeping right adds the
packaged block to the chain afterward. The data recorded in the chain cannot
be modified. This whole process is defined as mining, and the peers
participating in the bookkeeping right competition are defined as miners. For
the public chain, the miner that finally obtains the bookkeeping right and
completes the bookkeeping will receive a token reward. This mechanism is
referred to as the incentive mechanism. Currently, there are at least four
types of blockchain networks: public blockchain, private blockchain,
consortium blockchain, and hybrid blockchain. The blockchain network
introduced in this paper is the hybrid chain, in which different peers have
different permission according to their diverse responsibilities.

###  II-B Zero-Knowledge Proof

The zero-knowledge proof is a kind of method by which a $prover$ can convince
a $verifier$ that some statement is true without revealing any other
information. Any zero-knowledge proof protocol should satisfy three properties
[10]:

  * •

Completeness: If the statement is true then a $prover$ can convince a
$verifier$.

  * •

Soundness: A cheating $prover$ can not convince a $verifier$ of a false
statement.

  * •

Zero-knowledge: The interaction only reveals whether a statement is true or
not and nothing else.

Zero-Knowledge Succinct Non-Interactive Argument of Knowledge (zk-SNARK) is a
novel form of zero-knowledge cryptography which is introduced in [11] and
built in [12]. Quadratic Arithmetic Program (QAP) [13] and the Pinocchio
protocol [14] make it more effective and universal. Its first widespread
application is Zcash [15]. The following is a brief introduction to the zk-
SNARK protocol [10].

Any complex computation or program can be regarded as one consisting of a
series of simple operations which are defined as

$left\ operand\ \textbf{operator}\ right\
operand=output,\vspace*{-0.5\baselineskip}$ (1)

where ${operator}\in\left\\{+,-,\cdot,\div\right\\}$. Naturally, if we would
like to verify the correctness of the entire computation result, we just need
to verify the correctness of the results of each operation separately, but
such verification is very inefficient. Therefore, we can interpolate these
operations into a polynomial to verify all operations at a time, that is, to
verify polynomial

$L(x)\ \textbf{operator}\ R(x)=O(x),\vspace*{-0.5\baselineskip}$ (2)

where $L(x)$, $R(x)$ and $O(x)$ represent left, right and output polynomials,
respectively. This is the basic idea of QAP. Here, the operator is rewritten
as a multiplication since the addition and subtraction are made in each
operand, and the division can be converted into multiplication. It assumes
that the computation can be decomposed into $d$ operations. If the computation
is correct, the equation is true for each $x=i,\
i\in\left\\{1,...,d\right\\}$. Therefore, polynomial $L(x)\cdot R(x)-O(x)=0$
should have roots $x=i$, $i\in\left\\{1,...,d\right\\}$, which is denoted as

$p(x)=L(x)\cdot R(x)-O(x)=t(x)\cdot h(x),\vspace*{-0.5\baselineskip}$ (3)

where $\ t(x)=\prod_{i=1}^{d}{(x-i)}$.

In this way, by checking whether the polynomial $p\left(x\right)$ has the
factor $t\left(x\right)$, the correctness of the computation can be checked.
If a $prover$ intends to prove the correctness of the computation, he only
needs to provide $L(x)$, $R(x)$, $O(x)$ and $h\left(x\right)$ which satisfy
(3). In order to remain the same variable assignments of the same operands (or
output) in different operations unchanged, $L(x)$, $R(x)$ and $O(x)$ are
rewritten as the sum of the variable polynomials

$\left\\{\begin{matrix}L(x)=\prod_{i=0}^{n}{{v_{i}}{l_{i}}(x)}\\\
R\left(x\right)=\prod_{i=0}^{n}{{v_{i}}{r}_{i}\left(x\right)}\\\
O(x)=\prod_{i=0}^{n}{{v_{i}}{o}_{i}(x)}\end{matrix}\right.,$ (4)

where $i\in\left\\{0,...,n\right\\}$. $l_{i}(x)$ is the $i$th variable
polynomial of the left operand; $n$ is the number of variables involved;
$l_{0}(x)$ is variable polynomial of pseudo-variable $one$. The variable
polynomials are determined by the specific computation. The $prover$ cannot
modify these variable polynomials but only assign them, that is, multiply them
with $v_{i}$. Knowledge-of-Exponent Assumption (KEA) is utilized to construct
variable consistency polynomial. Variable consistency polynomial ensures
variable assignments consistency across operands in the same operation, and it
is denoted as

$\displaystyle Z\left(x\right)=$
$\displaystyle{v}_{i}\sum_{i=1}^{n}{\beta_{l}l_{i}\left(x\right)+\beta_{r}{r_{i}}\left(x\right)+\beta_{o}{o_{i}}\left(x\right)}$
(5) $\displaystyle=$
$\displaystyle{\beta_{l}}L(x)+{\beta_{r}}R(x)+{\beta_{o}}O(x),$

where $\beta_{l}$, $\beta_{r}$ and $\beta_{o}$ are random numbers. Next, the
$prover$ has to convince the $verifier$ that he knows the variable assignments
that satisfy the restrictions, but the $prover$ cannot directly inform the
$verifier$ of the variable assignments that satisfy (3). One reason is that it
will expose all information to $verifier$, the other is that the
multiplication of polynomials is extremely complex. According to the
Fundamental Theorem of Algebra, for any polynomial, we can use its evaluation
at any point to represent its unique identity. Therefore, the $verifier$ can
verify whether the evaluation of (3) is satisfied at a random point $s$, that
is, verify

$L\left(s\right)\cdot R\left(s\right)-O\left(s\right)=t\left(s\right)\cdot
h\left(s\right).\vspace*{-0.5\baselineskip}$ (6)

In order to ensure that the $prover$ cannot forge the polynomial, the random
point $s$ should be encrypted. So, the $verifier$ needs to verify (6) in the
encryption, that is, to verify

$e(g^{L(s)},g^{R(s)})=e(g^{t(s)},g^{h(s)})\cdot
e(g^{O(s)},g).\vspace*{-0.5\baselineskip}$ (7)

In addition, the $verifier$ also has to validate the constructing of
polynomials by checking

$\left\\{\begin{matrix}\begin{matrix}e(g^{L(s)},g^{\alpha_{l}})=e(g^{{\alpha_{l}}L(s)},g)\\\
e(g^{R(s)},g^{\alpha_{r}})=e(g^{{\alpha_{r}}R(s)},g)\end{matrix}\\\
e(g^{O(s)},g^{\alpha_{o}})=e(g^{{\alpha_{o}}O(s)},g)\end{matrix}\right.,$ (8)
$e(g^{L(s)},g^{\beta_{l}})\cdot e(g^{R(s)},g^{\beta_{r}})\cdot
e(g^{O(s)},g^{\beta_{o}})=e(g^{Z(s)},g),$ (9)

where $g$ is the generation point of elliptic curves and $e(g^{*},g^{*})$ is
cryptography pairings (or bilinear map), which maps two encrypted inputs from
two encrypted space to their multiplied form in different encrypted space, as
shown in Fig. 2.

Figure 2: Schematic Diagram of Bilinear Map

If (7), (8) and (9) are satisfied, the $verifier$ can believe that the
$prover$ indeed knows true variable assignments with great confidence and do
not know any other information about these variable assignments.

##  III System Model

The location data depict someone’s digital trace which gives more contextual
information such as individuals’ habits, interests, activities and
relationships. This information exposes the user to an unwanted advertisement
and location-based spams/scams, causing social reputation or economic damage
and making them victims of blackmail or even physical violence [16]. Moreover,
location data are insecurely transmitted and stored, and uncontrollable by its
owner in traditional mode. In order to solve these drawbacks, we consider a
system model with smart IoT devices. Our system model contains three
components: the server, the user, and the ledger, as shown in Fig. 3, where
the ledger is a blockchain network consisting of smart access points (APs).
The general function of each component is described below.

Figure 3: System Model of zk-PoL

APs are responsible for issuing location certificate to the user, providing
the user with Common Reference String (CRS) for generating the proof and
saving the service record, i.e. which service has been responded.

The user requests the nearby AP to issue a location certificate with short-
range communication mode. When some LBS is needed, the user uses the location
certificate to generate a proof for this LBS.

The server receives the service request and the proof sent by the user. After
validating the proof, the server provides the user with the corresponding LBS.
Once the service is obtained by the user, the server will request the AP to
save the service record, updating the ledger.

This kind of system enables separation of the user’s data and the service. The
public ledger only holds the root of trust of data, and the actual data is
stored locally by the user. When the user requests for LBSs from the server,
he just needs to prove the truth and validity of location data that he holds.

Focusing on the interaction details among all system components, we propose
the zk-PoL protocol. Our protocol consists of two parts: the generation and
verification scheme, where generation scheme mainly describes the issuance of
the location certificate, and verification scheme mainly describes the
generation and verification of the proof. The general process of the protocol
is shown in Fig. 4 and the details are given as follows.

Figure 4: Process Diagram of zk-PoL

###  III-A Generation scheme

Assuming that ${user}_{i}$ needs to request for LBSs from the ${server}_{j}$.
The first thing he should do is to access to the blockchain network and
communicate with the nearby access point $ap_{j}$ with short-range
communication mode, such as WiFi, bluetooth and ZigBee. Then the ${user}_{i}$
should request for location certificate issuing from the $ap_{j}$, and the
request is denoted as

${req}_{i\rightarrow
j}:{\left\\{\begin{matrix}{inf}_{i}:\left\\{\begin{matrix}{pk}_{user}^{i}\\\
{\left<longitude,latitude\right>}_{user}^{i}\end{matrix}\right\\},\\\
{\left\\{Hash\left({inf}_{i}\right)\right\\}}_{{sk}_{user}^{i}}\end{matrix}\right\\}}_{{pk}_{ap}^{j}},$
(10)

where ${req}_{i\rightarrow j}$ denotes the request sent by peer $i$ to peer
$j$. The ${sk}_{user}^{i}$ denotes the private key of the ${user}_{i}$; the
${pk}_{user}^{i}$ and ${pk}_{ap}^{j}$ denote the public key (also the identity
in the blockchain network) of ${user}_{i}$ and $ap_{j}$, respectively. It is
worth noting that the user equipment has no correspondence with ID in the
blockchain network. The blockchain network ID only matches the private key.
The ${\left<longitude,latitude\right>}_{user}^{i}$ denotes the geographic
coordinates of ${user}_{i}$. The ${user}_{i}$ uses ${sk}_{user}^{i}$ to sign
the ${inf}_{i}$ to prevent the malicious adversary from tampering with it, and
uses ${pk}_{ap}^{j}$ to encrypt the ${req}_{i\rightarrow j}$ to ensure that
only the $ap_{j}$ can correctly decrypt it.

After receiving ${req}_{i\rightarrow j}$, the $ap_{j}$ processes it according
to the following rules:

  * •

If the ${req}_{i\rightarrow j}$ has been tampered with, it will bediscarded.

  * •

If the geographic coordinates in ${inf}_{i}$ is out of the range of short-
range communication, the ${req}_{i\rightarrow j}$ is discarded.

  * •

Otherwise, the $ap_{j}$ responds to the ${user}_{i}$.

The response is defined as

${{res}_{j\rightarrow
i}:\left\\{\begin{matrix}{inf}_{j}:\left\\{\begin{matrix}{rand}_{user}^{i}\\\
{time}_{user}^{i}\end{matrix}\right\\},\\\
{\left\\{Hash\left({inf}_{j}\right)\right\\}}_{{sk}_{ap}^{j}}\end{matrix}\right\\}}_{{pk}_{user}^{i}},\vspace*{-0.5\baselineskip}$
(11)

where ${rand}_{user}^{i}$ is a random number and can be regarded as a serial
number of certificate. The ${time}_{user}^{i}$ indicates the moment when the
certificate is generated. Similarly, the $ap_{j}$ uses its own private key to
sign the ${inf}_{j}$, and uses ${user}_{i}$’s public key to encrypt the
${res}_{j\rightarrow i}$. Meanwhile, with ${inf}_{i}$ and ${inf}_{j}$, the
${ap}_{j}$ generates a digest of location certificate ${dig}_{i}$

${dig}_{i}:\left\\{Hash\left(\begin{matrix}\begin{matrix}{pk}_{user}^{i}\\\
{\left<longitude,latitude\right>}_{user}^{i}\end{matrix}\\\
{rand}_{user}^{i},{time}_{user}^{i}\end{matrix}\right)\right\\}.\vspace*{-0.5\baselineskip}$
(12)

Then, the ${dig}_{i}$ is broadcast to miners (APs) in the blockchain network.

The ${user}_{i}$ checks whether the ${res}_{j\rightarrow i}$ has been tampered
with or not. If it is, the ${user}_{i}$ discards the ${res}_{j\rightarrow i}$.
If not, with ${inf}_{i}$ and ${inf}_{j}$, the ${user}_{i}$ generates
${cer}_{i}$

${cer}_{i}:\left\\{\begin{matrix}\begin{matrix}{pk}_{user}^{i}\\\
{\left<longitude,latitude\right>}_{user}^{i}\end{matrix}\\\
{rand}_{user}^{i},{time}_{user}^{i}\end{matrix}\right\\}.\vspace*{-0.5\baselineskip}$
(13)

After ${cer}_{i}$ is generated, the ${ap}_{j}$ will delete ${inf}_{i}$ and
${inf}_{j}$ according to the embedded smart contract. Meanwhile, the miners
package the received ${dig}_{i}$ into their own blocks. Then by mining, one AP
is selected to add its block to the blockchain, updating the ledger. Once
${dig}_{i}$ is recorded in the ledger, it cannot be tampered with. The
${user}_{i}$ can generate a proof proving that his ${cer}_{i}$ is in
accordance with the ${dig}_{i}$ in the ledger to obtain related LBSs from the
${server}_{j}$.

###  III-B Verification scheme

Due to the different service requirements of different LBSs, when the
${user}_{i}$ requests for LBSs from the ${server}_{j}$, he needs to choose
different input parameters, as shown in TABLE I, to generate the appropriate
proof proving that he satisfies the service requirement.

TABLE I: input parameters Level | Public Parameters | Private Parameters
---|---|---
1 | $null$ |  |  ${pk}_{user}^{i}$,
---
${\left<longitude,latitude\right>}_{user}^{i}$,
${rand}_{user}^{i}$,
${time}_{user}^{i}$
2 | ${\left<longitude,latitude\right>}_{user}^{i}$ |  |  ${pk}_{user}^{i}$,
---
${rand}_{user}^{i}$,
${time}_{user}^{i}$
3 |  |  ${\left<longitude,latitude\right>}_{user}^{i}$,
---
${time}_{user}^{i}$
|  ${pk}_{user}^{i}$,
---
${rand}_{user}^{i}$
4 |  |  ${pk}_{user}^{i}$,
---
${\left<longitude,latitude\right>}_{user}^{i}$,
${time}_{user}^{i}$
${rand}_{user}^{i}$

The four levels of input parameters expose different necessary information to
the server, achieving so-called hierarchical privacy protection, which can be
applied to different scenarios:

  * •

Level 1: The ${user}_{i}$ locally generates a proof with input parameters in
level 1. This can be used to prove that someone has appeared at certain time
in the range covered by APs and be applied to the scenarios such as
authorization of attractions review where the critic must prove that he has
been some tourist area in order to get commenting permission.

  * •

Level 2: The ${user}_{i}$ locally generates a proof with input parameters in
level 2, disclosing its own coordinate. This can be used to prove that someone
has appeared at a particular location and certain moment, and can be applied
to the scenarios such as fixed-point Punching for Coupon Service (PCS) where
the user needs to punch in the specific place in order to get the coupon.

  * •

Level 3: The ${user}_{i}$ locally generates a proof with input parameters in
level 3, disclosing its own coordinate and time. This can be used to prove
that someone has appeared at a particular location and particular moment, and
can be applied to scenarios such as real-time location based recommendations
where the user must prove that he is now at a specific location in order to
get precise recommendations.

  * •

Level 4: The ${user}_{i}$ locally generates a proof with input parameters in
level 4, disclosing its own coordinate, time, and identity, i.e.
${pk}_{user}^{i}$. This can be used to prove that a particular person has
appeared at a particular place and a particular moment. For example, a suspect
needs the alibi to prove that he is not at the crime scene at a particular
moment.

Without loss of generality, the following takes the PCS as an example to
illustrate the details of the verification scheme. In PCS, the ${user}_{i}$
needs to punch in the specific place to get the coupon. Note that the ID of
${user}_{i}$ when he requests LBSs from the ${server}_{j}$ is no longer
${pk}_{user}^{i}$, so the ${user}_{i}$’s identity is not exposed. The
${user}_{i}$ should use the location certificate ${cer}_{i}$ to generate a
relevant proof and then send it to the ${server}_{j}$ for PCS. The specific
process goes as following.

####  III-B1 Computation to QAP

As mentioned earlier, any complex computation can be converted into QAP. The
complex computations in the PCS case is

$\left\\{\begin{matrix}Hash({rand}_{user}^{i})={hr}_{i}\\\
Hash\left(pubpara,pripara\right)={dig}_{i}\end{matrix}\right.,$ (14)

where ${hr}$ is the hash of serial number and it is set for special single-use
service. Its specific role will be discussed below. The $pubpara$ and
$pripara$ are public parameters and private parameters in TABLE I,
respectively. The QAP obtained from computation is

$\left\\{\left\\{{l}_{i}\left(x\right),{r}_{i}\left(x\right),{o}_{i}\left(x\right)\right\\},t\left(x\right)\right\\}\quad
i\in\left\\{0,...m,...,n\right\\},\vspace*{-0.5\baselineskip}$ (15)

where ${l}_{i}\left(x\right)$, ${r}_{i}\left(x\right)$ and
${o}_{i}\left(x\right)$ are variable polynomials; $n$ is the number of
variables; ${l}_{0}\left(x\right)$, ${r}_{0}\left(x\right)$ and
${o}_{0}\left(x\right)$ are polynomials of pseudo-variable $one$ and
${l}_{1}\left(x\right)$ to ${l}_{m}\left(x\right)$, ${r}_{1}\left(x\right)$ to
${r}_{m}\left(x\right)$ and ${o}_{1}\left(x\right)$ to ${o}_{m}\left(x\right)$
are polynomials of public variables. In this case $m=1$, which represents the
public parameter ${\left<longitude,latitude\right>}_{user}^{i}$;
$t\left(x\right)$ is the target polynomial and its degree $d$ denotes the
number of operations.

####  III-B2 Setup

After the conversion to QAP is completed, some randoms
$\left<s,g,{\rho}_{l},{\rho}_{r},\alpha_{l},\alpha_{r},{\alpha}_{o},\beta,\gamma\right>$
are needed. With these randoms, the APs generate proving key

$proving\quad key:\left\\{\begin{matrix}\left\\{{g}^{{s}^{i}}\right\\}\\\
\begin{matrix}\left\\{{g}_{l}^{{l}_{j}\left(s\right)},{g}_{r}^{{r}_{j}\left(s\right)},{g}_{o}^{{o}_{j}\left(s\right)}\right\\}\\\
\begin{matrix}\left\\{{g}_{l}^{{{\alpha}_{l}l}_{j}\left(s\right)},{g}_{r}^{{{\alpha}_{r}r}_{j}\left(s\right)},{g}_{o}^{{{\alpha}_{o}o}_{j}\left(s\right)}\right\\}\\\
\left\\{{g}_{l}^{{{\beta}l}_{j}\left(s\right)}{g}_{r}^{{{\beta}r}_{j}\left(s\right)}{g}_{o}^{{{\beta}o}_{j}\left(s\right)}\right\\}\end{matrix}\end{matrix}\end{matrix}\right\\},\vspace*{-0.5\baselineskip}$
(16)

where ${g}_{l}={g}^{{\rho}_{l}}$, ${g}_{r}={g}^{{\rho}_{r}}$,
${g}_{o}={g}^{{\rho}_{l}\cdot{\rho}_{r}}$, $i\in\left\\{1,...,d\right\\}$ and
$j\in\left\\{m+1,...,n\right\\}$, and verification key

$verification\quad
key:\left\\{\begin{matrix}{g}^{1},{g}_{o}^{t\left(s\right)}\\\
\left\\{{{g}}_{l}^{{l}_{i}\left(s\right)},{{g}}_{r}^{{r}_{i}\left(s\right)},{{g}}_{o}^{{o}_{i}\left(s\right)}\right\\}\\\
{g}^{{\alpha}_{l}},{g}^{{\alpha}_{r}},{g}^{{\alpha}_{o}},{g}^{\gamma},{g}^{\gamma\beta}\end{matrix}\right\\},\vspace*{-0.5\baselineskip}$
(17)

where $i\in\left\\{0,...,m\right\\}$.

Once proving key and verification key are generated, these randoms are deleted
by APs. Any adversary with these randoms has the ability to falsify a false
proof to cheat the server. This is why these randoms are called ’toxic waste’.

The above two phases can be collectively referred to as Trusted Setup (TS) for
generating CRS, i.e., the pair of proving and verification keys. In our
protocol, TS is executed by trusted APs at the system initialization.

####  III-B3 Calculate witness

In order to generate the proof, the ${user}_{i}$ needs to calculate all the
intermediate variables $witness$

$witness:\left\\{{v}_{m+1},{...,v}_{n}\right\\}.\vspace*{-0.5\baselineskip}$
(18)

####  III-B4 Generate proof

The ${user}_{i}$ calculates polynomials $L\left(x\right)$, $R\left(x\right)$
and $O\left(x\right)$ through assigning ${v}_{i}$ to ${l}_{i}\left(x\right)$,
${r}_{i}\left(x\right)$ and $o_{i}\left(x\right)$, as shown in (4), and then
obtains $h\left(x\right)$

$h\left(x\right)=\frac{L\left(x\right)R\left(x\right)-O\left(x\right)}{t\left(x\right)}.\vspace*{-0.5\baselineskip}$
(19)

Then using the proving key, the ${user}_{i}$ calculates

${g}_{l}^{{L}_{p}\left(s\right)}={g}_{l}^{\sum_{i=m+1}^{n}{{v}_{i}{l}_{i}\left(s\right)}},\vspace*{-0.5\baselineskip}$
(20)
${g}_{l}^{{L}_{p}^{{}^{\prime}}\left(s\right)}={g}_{l}^{{\alpha}_{l}\sum_{i=m+1}^{n}{{v}_{i}{l}_{i}\left(s\right)}}.$
(21)

Similarly, ${g}_{r}^{R_{p}\left(s\right)}$,
${g}_{r}^{R_{p}^{{}^{\prime}}\left(s\right)}$, ${g}_{o}^{O_{p}\left(s\right)}$
and ${g}_{o}^{O_{p}^{{}^{\prime}}\left(s\right)}$ can be obtained, and the
variable consistency polynomial is calculated by

$\displaystyle{g}^{Z\left(s\right)}=$
$\displaystyle\prod_{i=m+1}^{n}{{{g}_{l}}^{{v}_{i}\beta{l}_{i}\left(s\right)}}{{g}_{r}}^{{v}_{i}\beta
r_{i}\left(s\right)}{{g}_{o}}^{{v}_{i}\beta{o}_{i}\left(s\right)}$ (22)
$\displaystyle=$
$\displaystyle{{g}_{l}}^{\beta{L}_{p}\left(s\right)}{{g}_{r}}^{\beta{R}_{p}\left(s\right)}{{g}_{o}}^{\beta{O}_{p}\left(s\right)}$

In this way, the ${user}_{i}$ obtains the proof ${pro}_{i}$

${pro}_{i}:\left\\{\begin{matrix}{{g}_{l}^{L_{p}\left(s\right)},{g}_{l}^{{L}_{p}^{{}^{\prime}}\left(s\right)},}{g}_{o}^{R_{p}\left(s\right)},{g}_{r}^{R_{p}^{{}^{\prime}}\left(s\right)},\\\
{{g}_{o}^{O_{p}\left(s\right)},{g}_{o}^{{O}_{p}^{{}^{\prime}}\left(s\right)}},{g}^{Z\left(s\right)},{g}^{h\left(s\right)}\end{matrix}\right\\}.\vspace*{-0.5\baselineskip}$
(23)

After that, the ${user}_{i}$ sends proof to the ${server}_{j}$ and requests
the PCS from the ${server}_{j}$, and the request is

${req}_{i\rightarrow
j}:\left\\{{pro}_{i},{ind}_{PCS},{hr}_{i}\right\\},\vspace*{-0.5\baselineskip}$
(24)

where ${ind}_{PCS}$ is the index of PCS which ${user}_{i}$ requested.

####  III-B5 Verify proof

The ${server}_{j}$ checks if the service record has already existed in the
ledger. If it is, the request for PCS is denied. If not, using the
verification key, the ${server}_{j}$ validate ${pro}_{i}$ by checking

$\left\\{\begin{matrix}\begin{matrix}e\left({g}_{l}^{L_{p}\left(s\right)},{g}^{{\alpha}_{l}}\right)=e\left({g}_{l}^{{L}_{p}^{{}^{\prime}}\left(s\right)},g\right)\\\
e\left({g}_{r}^{R_{p}\left(s\right)},{g}^{{\alpha}_{r}}\right)=e\left({g}_{r}^{{R}_{p}^{{}^{\prime}}\left(s\right)},g\right)\end{matrix}\\\
e\left({g}_{o}^{O_{p}\left(s\right)},{g}^{{\alpha}_{o}}\right)=e\left({g}_{o}^{{O}_{p}^{{}^{\prime}}\left(s\right)},g\right)\end{matrix}\right.,$
(25)
$e\left({g}_{l}^{L_{p}\left(s\right)}{g}_{r}^{R_{p}\left(s\right)}{g}_{o}^{O_{p}\left(s\right)},{g}^{\beta\gamma}\right)=e\left({g}^{Z\left(s\right)},{g}^{\gamma}\right),$
(26)
$\begin{matrix}e\left({g}_{l}^{L_{v}\left(s\right)+L_{p}\left(s\right)},{g}_{r}^{R_{v}\left(s\right)+R_{p}\left(s\right)}\right)\\\
=e\left({g}_{o}^{t\left(s\right)},{g}^{h\left(s\right)}\right)\cdot
e\left({g}_{o}^{O_{v}\left(s\right)+O_{p}\left(s\right)},g\right)\end{matrix},\vspace*{-0.5\baselineskip}$
(27)

where
${g}_{l}^{L_{v}\left(s\right)}={g}_{l}^{{l}_{0}\left(s\right)+...+{v}_{m}{l}_{m}\left(s\right)}$,
and similarly for ${g}_{r}^{R_{v}\left(s\right)}$ and
${g}_{o}^{O_{v}\left(s\right)}$. After that, the ${server}_{j}$ provides PCS
for the ${user}_{i}$ and sends a service record ${rec}_{ji}$ to the
${ap}_{j}$, which is defined as

$\begin{matrix}{rec}_{ji}:\left\\{{pk}_{sever}^{j},{ind}_{PCS},{hr}_{i}\right\\}.\end{matrix}\vspace*{-0.5\baselineskip}$
(28)

Then ${rec}_{ji}$ is broadcasted to other APs in the blockchain network and
saved in the ledger through mining, which indicates that the ${server}_{j}$
has provided PCS for the ${user}_{i}$. When the ${user}_{i}$ attempts to
request PCS again to obtain another coupon, the ${server}_{j}$ can reject the
request because the service record has already existed in the ledger.

At this point, we have introduced the complete zk-PoL with input parameters in
level 1. The zk-PoL with input parameters in other levels has some subtle
differences in generating CRS, calculating witness, generating proof and
verifying proof, but the general process is the same. Because of space
limitation, the details will not be discussed here.

##  IV Evaluation

In this section, we analyze the proposed system security to resist main
attacks, including cheating on certificate parameters, cheating on service and
privacy inference attack. Moreover, we will also discuss computational
efficiency according to the experiment.

###  IV-A Security

####  IV-A1 Cheating on Certificate Parameters

In generation scheme, the certificate parameters ${time}$ and ${rand}$ are
generated by the trusted APs, so these two parameters can not be falsified. A
malicious user can only cheat on ${\left<longitude,latitude\right>}_{user}$,
and ${pk_{user}}$. However, by detecting whether the coordinate sent by the
malicious peer is in the range of short-range communication, the location
cheating can be prevented. In addition, to prevent cheating on ${pk_{user}}$,
the AP checks

${D}_{{pk}_{user}^{{}^{\prime}}}\left({E}_{{sk}_{user}}\left(Hash\left(inf\right)\right)\right)=Hash\left(inf\right),\vspace*{-0.5\baselineskip}$
(29)

where $D$ and $E$ are encryption algorithms and decryption algorithms of
asymmetric cryptography, respectively. The ${pk}_{user}^{{}^{\prime}}$ is the
ID to be checked.

####  IV-A2 Cheating on Services

In the verification scheme, the server, by checking variable polynomials
restriction, variable values consistency and valid operations, checks the
validity of $pro$, as shown in (25), (26) and (27). In addition, by deleting
’toxic waste’, it can be ensured that any malicious user without certificate
parameters can not forge $pro$ for corresponding services. Hence cheating on
services can be avoided. Moreover, to prevent cheating on obtaining special
one-off services repeatedly, the server checks

$\left({pk}_{server},ind,hr\right)\in\left\\{rec\right\\},\vspace*{-0.5\baselineskip}$
(30)

where $\left\\{rec\right\\}$ denotes the set of service records stored in the
ledger.

####  IV-A3 Privacy Inference Attack

In the generation scheme, the private information of the user is only
available to the user himself and the APs. The APs are prevented by the
embedded smart contract from disclosing the user’s privacy. Also, the digest
of the location certificate stored in the public ledger does not reveal the
user’s privacy to any malicious peer.

In the verification scheme, according to the characteristics of the trapdoor
function, it is hard to get the
$witness:\left\\{{v}_{m+1}{,...,v}_{n}\right\\}$ from CRS and $pro$, so our
zk-PoL only provides the necessary private information for the server without
revealing any other privacy.

###  IV-B Computational Efficiency

Our experiment is on MateBook 13 with 1.8Ghz i7 CPU and 8G RAM. Moreover, the
experiment is based on Circom and Snarkjs[17, 18]. Circom is a circuit
generator to translate program executions to arithmetic circuits. Snarkjs is a
JavaScript based cryptographic proof system for verifying the satisfiability
of arithmetic circuits generated by Circom. We experiment with parameters in
four levels, and the percentage of average execution time for each phase is as
shown in Fig. 5.

Figure 5: Distribution of Average Execution Time

  * •

_Computation to QAP:_ The percentages of this phase in four levels are 2.1%,
2.1%, 2.0%, and 2.0%, respectively.

  * •

_Setup:_ The percentages of this phase in four levels are 88.3%, 88.3%, 89.0%,
and 88.8%, respectively.

  * •

_Calculate witness:_ The percentages of this phase in four levels all are
0.2%.

  * •

_Generate proof:_ The percentages of this phase in four levels are 9.2%, 9.2%,
8.6%, and 8.8%, respectively.

  * •

_Verify proof:_ The percentages of this phase in four levels all are 0.2%.

The result shows that the distributions of average execution time in different
levels of zk-PoL are basically the same. Moreover, due to the complexity of
the elliptic curve point addition and hash algorithm, the percentage of the
average execution time of TS is large, accounting for about 90% of the total
execution time. Fortunately, the TS only needs to be executed once during the
system initialization. Therefore, we only need to consider the execution time
of the three phases: _Calculate witness_ , _Generate proof_ and _Verify
proof_.

The relationships between the average execution time and the number of public
parameters in the three phases are shown in the Fig. 6. It can be seen that
the average execution time of each phase across different public parameters is
basically the same. In addition, the total execution time of the three phases
that need to be repeated during different services is about 2 minutes. This
execution time is acceptable in some delay-tolerant LBSs, such as the PCS
case.

Figure 6: Average Execution Time of Four Levels

##  V Conclusion

In this paper, we bring zero-knowledge proof to LBSs for the first time,
proposing zk-PoL protocol which consists of generation scheme and verification
scheme. This protocol allows a user to achieve hierarchical, user-controllable
privacy protection by choosing different input parameters. In addition, for
main attacks, we analyze the security of our system, and the result shows that
the system has excellent security against these attacks. Finally, we
experiment with our system, demonstrating that the performance is independent
of the privacy protection level. In diverse services, the average execution
time of the phases needed to be repeated (all phases except the TS phase) is
about 2 minutes, and the ratio of that to the total time cost is about 10%.
This performance is appropriate to delay-tolerant LBSs, but not to delay-
sensitive LBSs. In our future work, we will implement different circuit
generators and cryptographic proof systems [19] to improve the system
performance, making our zk-PoL appropriate to more kinds of LBSs.

## References

  * [1] I. A. Junglas and R. T. Watson, “Location-based services,” _Communications of the ACM_ , vol. 51, no. 3, pp. 65–69, 2008.
  * [2] D. Jiang, X. Guo, Y. Gao, J. Liu, H. Li, and J. Cheng, “Locations recommendation based on check-in data from location-based social network,” in _2014 22nd International Conference on Geoinformatics_. IEEE, 2014, pp. 1–4.
  * [3] A. K. Tyagi and N. Sreenath, “Location privacy preserving techniques for location based services over road networks,” in _2015 International Conference on Communications and Signal Processing (ICCSP)_. IEEE, 2015, pp. 1319–1326.
  * [4] C. Javali, G. Revadigar, K. B. Rasmussen, W. Hu, and S. Jha, “I am Alice, I was in wonderland: secure location proof generation and verification protocol,” in _2016 IEEE 41st conference on local computer networks (LCN)_. IEEE, 2016, pp. 477–485.
  * [5] Y. Li, L. Zhou, H. Zhu, and L. Sun, “Privacy-preserving location proof for securing large-scale database-driven cognitive radio networks,” _IEEE Internet of Things Journal_ , vol. 3, no. 4, pp. 563–571, 2015.
  * [6] M. Amoretti, G. Brambilla, F. Medioli, and F. Zanichelli, “Blockchain-Based Proof of Location,” in _2018 IEEE International Conference on Software Quality, Reliability and Security Companion (QRS-C)_. IEEE, 2018, pp. 146–153.
  * [7] F. Tschorsch and B. Scheuermann, “Bitcoin and beyond: A technical survey on decentralized digital currencies,” _IEEE Communications Surveys & Tutorials_, vol. 18, no. 3, pp. 2084–2123, 2016.
  * [8] S. Nakamoto _et al._ , “Bitcoin: A peer-to-peer electronic cash system,” 2008\.
  * [9] “Ethereum: A Next-Generation Smart Contract and Decentralized Application Platform,” https://github.com/ethereum/wiki/wiki/White-Paper.
  * [10] M. Petkus, “Why and How zk-SNARK Works,” _ArXiv_ , vol. abs/1906.07221, 2019\.
  * [11] N. Bitansky, R. Canetti, A. Chiesa, and E. Tromer, “From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again,” in _Proceedings of the 3rd Innovations in Theoretical Computer Science Conference_. ACM, 2012, pp. 326–349.
  * [12] J. Groth, “Short pairing-based non-interactive zero-knowledge arguments,” in _International Conference on the Theory and Application of Cryptology and Information Security_. Springer, 2010, pp. 321–340.
  * [13] R. Gennaro, C. Gentry, B. Parno, and M. Raykova, “Quadratic span programs and succinct NIZKs without PCPs,” in _Annual International Conference on the Theory and Applications of Cryptographic Techniques_. Springer, 2013, pp. 626–645.
  * [14] B. Parno, J. Howell, C. Gentry, and M. Raykova, “Pinocchio: Nearly practical verifiable computation,” in _2013 IEEE Symposium on Security and Privacy_. IEEE, 2013, pp. 238–252.
  * [15] E. B. Sasson, A. Chiesa, C. Garman, M. Green, I. Miers, E. Tromer, and M. Virza, “Zerocash: Decentralized anonymous payments from bitcoin,” in _2014 IEEE Symposium on Security and Privacy_. IEEE, 2014, pp. 459–474.
  * [16] R. Shokri, G. Theodorakopoulos, J.-Y. Le Boudec, and J.-P. Hubaux, “Quantifying location privacy,” in _2011 IEEE symposium on security and privacy_. IEEE, 2011, pp. 247–262.
  * [17] “Circom: Circuit compiler for zkSNARKs,” https://github.com/iden3/circom.
  * [18] “Snarkjs: zkSNARK implementation in JavaScript,” https://github.com/iden3/snarkjs.
  * [19] E. Ben-Sasson, A. Chiesa, E. Tromer, and M. Virza, “Succinct non-interactive zero knowledge for a von neumann architecture,” in _23rd USENIX Security Symposium (USENIX Security 14)_. USENIX Association, Aug. 2014, pp. 781–796.


Detection and Evaluation  of
Clusters within Sequential Data

Alexander Van Werde, Albert Senen–Cerda, Gianluca Kosmella, Jaron Sanders
The authors are with the Faculty of Mathematics and Computer Science, Eindhoven University of Technology, Groene Loper 5, 5612 AZ Eindhoven, The Netherlands.

E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
§ INTRODUCTION

Modern data

§ PROBLEM FORMULATION

§ MODELS

§.§ Main model: BMC

§ RELATED LITERATURE

§ CLUSTERING ALGORITHM

§ METHODS FOR EVALUATING CLUSTERS AND MODELS

§ DATA SETS AND PREPROCESSING

§ DETECTED CLUSTERS WITHIN THE DATA

§ DETECTED ORDERS WITHIN THE DATA

§ CONCLUSIONS

§ ACKNOWLEDGMENTS

[1]
A. Zhang and M. Wang, “Spectral state compression of Markov processes,”
IEEE Transactions on Information Theory, 2019.

[2]
J. Sanders, A. Proutière, and S.-Y. Yun, “Clustering in Block Markov
Chains,” The Annals of Statistics, 2020.

[3]
S. Singh, T. Jaakkola, and M. Jordan, “Reinforcement Learning with soft
state aggregation,” Advances in Neural Information Processing
Systems, 1994.

[4]
R. Ortner, “Adaptive Aggregation for Reinforcement Learning in Average
Reward Markov Decision Processes,” Annals of Operations
Research, 2013.

[5]
J. Sanders and A. Van Werde, “Singular value distribution of dense random
matrices with block Markovian dependence,” arXiv preprint
arXiv:2204.13534, 2022.

[6]
J. Sanders and A. Senen-Cerda, “Spectral norm bounds for Block Markov
Chain random matrices,” arXiv preprint arXiv:2111.06201, 2021.

[7]
Y. Duan, T. Ke, and M. Wang, “State aggregation learning from Markov
transition data,” Advances in Neural Information Processing Systems,

[8]
S. Bi, Z. Yin, and Y. Weng, “A low-rank spectral method for learning Markov
models,” Optimization Letters, 2022.

[9]
Z. Du, N. Ozay, and L. Balzano, “Mode clustering for Markov jump systems,”
in 2019 IEEE 8th International Workshop on Computational Advances in
Multi-Sensor Adaptive Processing (CAMSAP), 2019.

[10]
Z. Zhu, X. Li, M. Wang, and A. Zhang, “Learning Markov models via low-rank
optimization,” Operations Research, 2021.

[11]
C. Gao, Z. Ma, A. Y. Zhang, and H. H. Zhou, “Achieving optimal
misclassification proportion in Stochastic Block Models,” The
Journal of Machine Learning Research, 2017.

[12]
S. Fortunato, “Community detection in graphs,” Physics Reports, 2010.

[13]
S. Zolhavarieh, S. Aghabozorgi, and Y. W. Teh, “A Review of Subsequence
Time Series Clustering,” The Scientific World Journal, 2014.

[14]
S. Aghabozorgi, A. S. Shirkhorshidi, and T. Y. Wah, “Time-series clustering
– A decade review,” Information Systems, 2015.

[15]
T. W. Liao, “Clustering of time series data – A survey,” Pattern
Recognition, 2005.

[16]
J. Lin, E. Keogh, and W. Truppel, “Clustering of Streaming Time Series
is Meaningless,” in Proceedings of the 8th ACM SIGMOD workshop
on Research Issues in Data Mining and Knowledge Discovery, 2003.

[17]
T. Rakthanmanon, E. J. Keogh, S. Lonardi, and S. Evans, “Time series
epenthesis: Clustering time series streams requires ignoring some data,” in
2011 IEEE 11th International Conference on Data Mining, 2011.

[18]
S. Rodpongpun, V. Niennattrakul, and C. A. Ratanamahatana, “Selective
subsequence time series clustering,” Knowledge-Based Systems, 2012.

[19]
A. Gionis and H. Mannila, “Finding Recurrent Sources in Sequences,”
in Proceedings of the seventh annual international conference on
Research in computational Molecular Biology, 2003.

[20]
A. Ultsch and F. Mörchen, ESOM-Maps: Tools for clustering,
visualization, and classification with Emergent SOM.

[21]
F. Mörchen, A. Ultsch, and O. Hoos, “Extracting interpretable muscle
activation patterns with time series knowledge mining,” International
Journal of Knowledge-based and Intelligent Engineering Systems, 2005.

[22]
O.-A. Maillard and S. Mannor, “Latent bandits.,” in International
Conference on Machine Learning, 2014.

[23]
M. G. Azar, A. Lazaric, and E. Brunskill, “Sequential transfer in
Multi-Armed Bandit with finite set of models,” Advances in Neural
Information Processing Systems, 2013.

[24]
L. Li, T. J. Walsh, and M. L. Littman, “Towards a unified theory of state
abstraction for MDPs,” in AI&M, 2006.

[25]
H. Y. Ong, “Value function approximation via low-rank models,” arXiv
preprint arXiv:1509.00061, 2015.

[26]
K. Azizzadenesheli, A. Lazaric, and A. Anandkumar, “Reinforcement Learning
in rich-observation MDPs using spectral methods,” arXiv preprint
arXiv:1611.03907, 2016.

[27]
Y. Yang, G. Zhang, Z. Xu, and D. Katabi, “Harnessing structures for
value-based planning and Reinforcement Learning,” arXiv preprint
arXiv:1909.12255, 2019.

[28]
A. A. Markov, “Primer statisticheskogo issledovaniya nad tekstom “evgeniya
onegina”, illyustriruyuschij svyaz’ispytanij v cep’,” Izvestiya
Akademii Nauk, 1913.

[29]
C. Manning and H. Schutze, Foundations of Statistical Natural
Language Processing.

[30]
H. Almagor, “A Markov analysis of DNA sequences,” Journal of
Theoretical Biology, 1983.

[31]
R. Jorre and R. Curnow, “A model for the evolution of the proteins: Cytochrome
c: mammals, reptiles, insects,” Biochimie, 1976.

[32]
S. Robin, F. Rodolphe, and S. Schbath, DNA, words and models: statistics
of exceptional words.

[33]
I. Gialampoukidis, K. Gustafson, and I. Antoniou, “Time operator of Markov
chains and mixing times. Applications to financial data,” Physica A:
Statistical Mechanics and its Applications, 2014.

[34]
D. Zhang and X. Zhang, “Study on forecasting the stock market trend based on
stochastic analysis method,” International Journal of Business and
Management, 2009.

[35]
J. van der Hoek and R. J. Elliott, “Asset pricing using finite state Markov
chain stochastic discount functions,” Stochastic Analysis and
Applications, 2012.

[36]
R. S. Mamon and R. J. Elliott, Hidden Markov Models in Finance.

[37]
P. Billingsley, “Statistical methods in Markov chains,” The Annals of
Mathematical Statistics, 1961.

[38]
M. Menéndez, D. Morales, L. Pardo, and K. Zografos, “Statistical inference
for finite Markov chains based on divergences,” Statistics &
Probability Letters, 1999.

[39]
L. Pardo, Statistical inference based on divergence measures.

[40]
M. Menéndez, J. Pardo, and L. Pardo, “Csiszar's-divergences for testing
the order in a Markov chain,” Statistical Papers, 2001.

[41]
F. Barsotti, A. Philippe, and P. Rochet, “Hypothesis testing for Markovian
models with random time observations,” Journal of Statistical Planning
and Inference, 2016.

[42]
H. Akaike, “A new look at the statistical model identification,” IEEE
Transactions on Automatic Control, 1974.

[43]
H. Bozdogan, “Model selection and Akaike's Information Criterion
(AIC): The general theory and its analytical extensions,” Psychometrika, 1987.

[44]
D. Anderson and K. Burnham, “Model selection and multi-model inference,” Second. NY: Springer-Verlag, 2004.

[45]
S. Kullback and R. A. Leibler, “On information and sufficiency,” The
Annals of Mathematical Statistics, 1951.

[46]
J. Ding, V. Tarokh, and Y. Yang, “Model selection techniques: An overview,”
IEEE Signal Processing Magazine, 2018.

[47]
National Library of Medicine, “OCA2 melanosomal transmembrane protein homo
sapiens (human).” <https://www.ncbi.nlm.nih.gov/gene/4948>, 2021.
Accessed in October 2021, RefSeq Accession NC_000015.10.

[48]
B. Wilson, “The Unknown Perils of Mining Wikipedia.”
June 2015.

[49]
S. Bird, E. Klein, and E. Loper, Natural language processing with Python:
analyzing text with the natural language toolkit.

[50]
D. L. Stephen Blake, Randy Arndt, “Movebank.”
Accessed: 2022-08-16.

[51]
Alpha Vantage Co, “Stock data API,” 2021.

[52]
G. A. Gutman and G. W. Hatfield, “Nonrandom utilization of codon pairs in
Escherichia coli,” Proceedings of the National Academy of Sciences,

[53]
J. R. Coleman, D. Papamichail, S. Skiena, B. Futcher, E. Wimmer, and
S. Mueller, “Virus Attenuation by Genome-Scale Changes in Codon
Pair Bias,” Science, 2008.

[54]
D. Kunec and N. Osterrieder, “Codon Pair Bias Is a Direct
Consequence of Dinucleotide Bias,” Cell Reports, 2016.

[55]
B. Irwin, J. D. Heck, and G. W. Hatfield, “Codon Pair Utilization
Biases Influence Translational Elongation Step Times,” Journal of Biological Chemistry, 1995.

[56]
G. Moura, M. Pinheiro, R. Silva, I. Miranda, V. Afreixo, G. Dias, A. Freitas,
J. L. Oliveira, and M. A. Santos, “Comparative context analysis of codon
pairs on an ORFeome scale,” Genome Biology, 2005.

[57]
A. Alexaki, J. Kames, D. D. Holcomb, et al., “Codon and codon-pair
usage tables (CoCoPUTs): facilitating genetic variation analyses and
recombinant gene design,” Journal of Molecular Biology, 2019.