Non-interactive zero-knowledge proof or argument (NIZK) systems are widely used in many
security sensitive applications to enhance computation integrity, privacy and scalability.
In such systems, a prover wants to convince one or more verifiers that the result of a
public function is correctly computed without revealing the (potential) private input,
such as the witness. In this work, we introduce a new notion, called scriptable SNARK,
where the prover and verifier(s) can specify the function (or language instance) to be
proven via a script. We formalize this notion in UC framework and provide a generic
trusted hardware based solution. We then instantiate our solution in both SGX and
Trustzone with Lua script engine. The system can be easily used by typical programmers
without any cryptographic background. The benchmark result shows that our solution is
better than all the known SNARK proof systems w.r.t. prover’s running time (1000 times
faster), verifier’s running time, and the proof size. In addition, we also give a
lightweight scriptable SNARK protocol for hardware with limited state, e.g.,
bits. Finally,
we show how the proposed scriptable SNARK can be readily deployed to solve many well-known
problems in the blockchain context, e.g. verifier’s dilemma, fast joining for new players,
etc.
S.Ames, C.Hazay, Y.Ishai and M.Venkitasubramaniam,
Ligero: Lightweight sublinear arguments without a trusted
setup, in: ACM CCS 2017, B.M.Thuraisingham,
D.Evans, T.Malkin and D.Xu,
eds, ACM Press, 2017,
pp. 2087–2104.
2.
C.Baum, J.Bootle, A.Cerulli, R.Del
Pino, J.Groth and V.Lyubashevsky,
Sub-linear lattice-based zero-knowledge arguments for arithmetic
circuits, in: Annual International Cryptology
Conference, Springer, 2018,
pp. 669–699.
3.
A.Baumann, M.Peinado and G.Hunt,
Shielding applications from an untrusted cloud with
haven, ACM Transactions on Computer Systems (TOCS)33(3) (2015), 8. doi:10.1145/2799647.
4.
E.Ben-Sasson,
I.Bentov, Y.Horesh and M.Riabzev, Scalable,
transparent, and post-quantum secure computational integrity, Cryptology ePrint Archive,
Report 2018/046, 2018.
5.
E.Ben-Sasson,
A.Chiesa, D.Genkin, E.Tromer and M.Virza,
SNARKs for C: Verifying program executions succinctly and in zero
knowledge, in: CRYPTO 2013, Part II, R.Canetti and J.A.Garay, eds,
LNCS, Vol. 8043,
Springer, Heidelberg,
2013, pp. 90–108. doi:10.1007/978-3-642-40084-1_6.
6.
E.Ben-Sasson,
A.Chiesa, M.Riabzev, N.Spooner, M.Virza and N.P.W.Aurora,
Transparent succinct arguments for r1cs, in:
Annual International Conference on the Theory and Applications of Cryptographic
Techniques, Springer, 2019,
pp. 103–128.
7.
E.Ben-Sasson,
A.Chiesa, E.Tromer and M.Virza,
Succinct non-interactive zero knowledge for a von Neumann
architecture, in: USENIX Security 2014, K.Fu
and J.Jung, eds,
USENIX Association, 2014,
pp. 781–796.
8.
M.Blum, P.Feldman and S.Micali,
Non-interactive zero-knowledge and its applications (extended
abstract), in: 20th ACM STOC, ACM
Press, 1988,
pp. 103–112.
9.
J.Bootle, A.Cerulli, P.Chaidos, J.Groth and C.Petit,
Efficient zero-knowledge arguments for arithmetic circuits in the
discrete log setting, in: EUROCRYPT 2016, Part II,
M.Fischlin and
J.-S.Coron, eds,
LNCS, Vol. 9666,
Springer, Heidelberg,
2016, pp. 327–357. doi:10.1007/978-3-662-49896-5_12.
10.
J.Bootle, A.Cerulli, E.Ghadafi, J.Groth, M.Hajiabadi and
S.K.Jakobsen,
Linear-time zero-knowledge proofs for arithmetic circuit
satisfiability, in: International Conference on the Theory and
Application of Cryptology and Information Security,
Springer, 2017,
pp. 336–365.
11.
E.Brickell and
J.Li,
Enhanced privacy id from bilinear pairing for hardware authentication and
attestation, in: 2010 IEEE Second International Conference on
Social Computing, 2010, pp. 768–775.
doi:10.1109/SocialCom.2010.118.
12.
B.Bünz, J.Bootle, D.Boneh, A.Poelstra, P.Wuille and G.Maxwell,
Bulletproofs: Short proofs for confidential transactions and
more, in: 2018 IEEE Symposium on Security and Privacy,
IEEE Computer Society Press, 2018,
pp. 315–334. doi:10.1109/SP.2018.00020.
13.
R.Canetti, Universally
composable security: A new paradigm for cryptographic protocols, Cryptology ePrint
Archive, Report 2000/067, 2000.
14.
R.Canetti,
Universally composable security: A new paradigm for cryptographic
protocols, in: 42nd FOCS, IEEE Computer
Society Press, 2001,
pp. 136–145.
G.Chen, S.Chen, Y.Xiao, Y.Zhang, Z.Lin
and H.Ten
Lai, Sgxpectre attacks: Stealing intel secrets from sgx
enclaves via speculative execution, 2018.
17.
R.Cheng, F.Zhang, J.Kos,
W.He, N.Hynes, N.Johnson, A.Juels, A.Miller and D.Song, Ekiden: A platform
for confidentiality-preserving, trustworthy, and performant smart
contracts.
G.Danezis, C.Fournet, J.Groth and M.Kohlweiss,
Square span programs with applications to succinct NIZK
arguments, in: ASIACRYPT 2014, Part I, P.Sarkar and T.Iwata, eds,
LNCS, Vol. 8873,
Springer, Heidelberg,
2014, pp. 532–550.
20.
ECRYPT. ebacs: Ecrypt benchmarking of cryptographic
systems. https://bench.cr.yp.to/results-hash.html, 2018. Last accessed:
2019-05-11.
21.
G.Edward Suh,
D.Clarke, B.Gassend, M.Van
Dijk and S.Devadas,
Aegis: Architecture for tamper-evident and tamper-resistant
processing, in: ACM International Conference on Supercomputing
25th Anniversary Volume, ACM,
2014, pp. 357–368.
22.
B.Fisch, D.Vinayagamurthy,
D.Boneh and S.Gorbunov,
IRON: Functional encryption using intel SGX, in:
ACM CCS 2017, B.M.Thuraisingham,
D.Evans, T.Malkin and D.Xu,
eds, ACM Press, 2017,
pp. 765–782.
23.
R.Gennaro, C.Gentry, B.Parno and M.Raykova,
Quadratic span programs and succinct NIZKs without PCPs,
in: EUROCRYPT 2013, T.Johansson and
P.Q.Nguyen, eds,
LNCS, Vol. 7881,
Springer, Heidelberg,
2013, pp. 626–645. doi:10.1007/978-3-642-38348-9_37.
24.
C.Gentry and
D.Wichs,
Separating succinct non-interactive arguments from all falsifiable
assumptions, in: 43rd ACM STOC, L.FortnowS.P.Vadhan, ed.,
ACM Press, 2011,
pp. 99–108.
25.
I.Giacomelli,
J.Madsen and
C.Orlandi, ZKBoo: Faster
zero-knowledge for boolean circuits, Cryptology ePrint Archive, Report 2016/163,
2016.
26.
O.Goldreich and
Y.Oren,
Definitions and properties of zero-knowledge proof
systems, Journal of Cryptology7(1) (1994),
1–32. doi:10.1007/BF00195207.
27.
S.Goldwasser,
Y.Tauman
Kalai and G.N.Rothblum,
Delegating computation: Interactive proofs for muggles,
in: 40th ACM STOC, R.E.Ladner and
C.Dwork, eds,
ACM Press, 2008,
pp. 113–122.
28.
J.Groth,
Fully anonymous group signatures without random oracles,
in: ASIACRYPT 2007, K.Kurosawa, ed.,
LNCS, Vol. 4833,
Springer, Heidelberg,
2007, pp. 164–180. doi:10.1007/978-3-540-76900-2_10.
29.
J.Groth,
Efficient zero-knowledge arguments from two-tiered homomorphic
commitments, in: ASIACRYPT 2011, D.Hoon
Lee and X.Wang, eds,
LNCS, Vol. 7073,
Springer, Heidelberg,
2011, pp. 431–448. doi:10.1007/978-3-642-25385-0_23.
30.
J.Groth, M.Kohlweiss, M.Maller, S.Meiklejohn and
I.Miers,
Updatable and universal common reference strings with applications to
zk-SNARKs, in: CRYPTO 2018, Part III, H.Shacham and A.Boldyreva, eds,
LNCS, Vol. 10993,
Springer, Heidelberg,
2018, pp. 698–728. doi:10.1007/978-3-319-96878-0_24.
31.
J.Groth, R.Ostrovsky and
A.Sahai,
Perfect non-interactive zero knowledge for np, in:
Annual International Conference on the Theory and Applications of Cryptographic
Techniques, Springer, 2006,
pp. 339–358.
32.
Y.Ishai, E.Kushilevitz and
R.Ostrovsky,
Efficient arguments without short pcps, in:
Twenty-Second Annual IEEE Conference on Computational Complexity
(CCC’07), 2007, pp. 278–291.
doi:10.1109/CCC.2007.10.
33.
Y.Ishai, E.Kushilevitz,
R.Ostrovsky and
A.Sahai,
Zero-knowledge from secure multiparty computation, in:
39th ACM STOC, D.S.Johnson and
U.Feige, eds,
ACM Press, 2007,
pp. 21–30.
34.
S.P.Johnson,
V.R.Scarlata,
C.V.Rozas, E.Brickell and
F.McKeen, Intel sgx:
Epid provisioning and attestation services, Intel
(2016).
35.
A.Juels, A.E.Kosba and E.Shi,
The ring of Gyges: Investigating the future of criminal smart
contracts, in: ACM CCS 2016, E.R.Weippl, S.Katzenbeisser,
C.Kruegel, A.C.Myers and S.Halevi, eds,
ACM Press, 2016,
pp. 283–295.
36.
A.Kiayias, A.Miller and D.Zindros, Non-interactive
proofs of proof-of-work, Cryptology ePrint Archive, Report 2017/963,
2017.
37.
A.Kosba, Z.Zhao, A.Miller, Y.Qian, H.Chan, C.Papamanthou,
R.Pass, A.Shelat and E.Shi,
C∅c∅: A framework for building composable
zero-knowledge proofs, Cryptology ePrint Archive, Report 2015/1093, 2015.
38.
A.E.Kosba, A.Miller, E.Shi,
Z.Wen and C.P.Hawk,
The blockchain model of cryptography and privacy-preserving smart
contracts, in: 2016 IEEE Symposium on Security and
Privacy, IEEE Computer Society Press,
2016, pp. 839–858. doi:10.1109/SP.2016.55.
39.
S.Lee, M.-W.Shih, P.Gera, T.Kim,
H.Kim and M.Peinado,
Inferring fine-grained control flow inside sgx enclaves with branch
shadowing, in: USENIX Security, USENIX
Association, 2017.
40.
G.V.Leslie,
Universal circuits (preliminary report), in:
Proceedings of the Eighth Annual ACM Symposium on Theory of Computing, STOC
’76, ACM, New York, NY,
USA, 1976,
pp. 196–203.
41.
H.Lipmaa, P.Mohassel and
S.Sadeghian, Valiant’s
universal circuit: Improvements, implementation, and applications, Cryptology ePrint
Archive, Report 2016/017, 2016.
42.
M.Lipp, D.Gruss, R.Spreitzer, C.Maurice and S.Mangard,
ARMageddon: Cache attacks on mobile devices, in:
USENIX Security 2016, T.Holz and S.Savage, eds,
USENIX Association, 2016,
pp. 549–564.
43.
L.Luu, J.Teutsch, R.Kulkarni and
P.Saxena,
Demystifying incentives in the consensus computer, in:
ACM CCS 2015, I.Ray, N.Li
and C.Kruegel, eds,
ACM Press, 2015,
pp. 706–719.
44.
M.Maller, S.Bowe, M.Kohlweiss and
S.Meiklejohn,
Sonic: Zero-knowledge snarks from linear-size universal and updateable
structured reference strings, IACR Cryptology ePrint
Archive2019 (2019), 99.
45.
J.M.McCune, B.J.Parno, A.Perrig, M.K.Reiter and
H.Isozaki,
Flicker: An execution infrastructure for tcb
minimization, in: ACM SIGOPS Operating Systems Review,
Vol. 42, ACM, 2008,
pp. 315–328.
46.
O.Ohrimenko,
M.Costa, C.Fournet, C.Gkantsidis, M.Kohlweiss and
D.Sharma,
Observing and preventing leakage in MapReduce, in:
ACM CCS 2015, I.Ray, N.Li
and C.Kruegel, eds,
ACM Press, 2015,
pp. 1570–1581.
47.
O.Ohrimenko,
F.Schuster, C.Fournet, A.Mehta, S.Nowozin, K.Vaswani and M.Costa,
Oblivious multi-party machine learning on trusted
processors, in: USENIX Security 2016, T.Holz
and S.Savage, eds,
USENIX Association, 2016,
pp. 619–636.
48.
B.Parno, J.Howell, C.Gentry and M.Raykova,
Pinocchio: Nearly practical verifiable computation, in:
2013 IEEE Symposium on Security and Privacy, IEEE
Computer Society Press, 2013,
pp. 238–252. doi:10.1109/SP.2013.47.
49.
R.Pires, D.Gavril, P.Felber, E.Onica and M.Pasin, A
lightweight mapreduce framework for secure processing with sgx, in:
Proceedings of the 17th IEEE/ACM International Symposium on Cluster, Cloud and
Grid Computing, CCGrid ’17, IEEE Press,
Piscataway, NJ, USA, 2017,
pp. 1100–1107.
50.
O.Reingold, G.N.Rothblum and
R.D.Rothblum,
Constant-round interactive proofs for delegating
computation, in: 48th ACM STOC, D.Wichs and Y.Mansour, eds,
ACM Press, 2016,
pp. 49–62.
51.
F.Schuster, M.Costa, C.Fournet, C.Gkantsidis, M.Peinado, G.Mainar-Ruiz and
M.Russinovich,
VC3: Trustworthy data analytics in the cloud using SGX,
in: 2015 IEEE Symposium on Security and Privacy, IEEE
Computer Society Press, 2015,
pp. 38–54. doi:10.1109/SP.2015.10.
52.
SCIPR Lab, 2019, libsnark: A c++
library for zksnark proofs.
53.
F.Tramer, F.Zhang, H.Lin,
J.Hubaux, A.Juels and E.Shi,
Sealed-glass proofs: Using transparent enclaves to prove and sell
knowledge, in: Euro S&P 2017, 2017,
pp. 19–34.
54.
T.Tuan, A.Dinh, P.Saxena, E.-C.Chang, B.Chin
Ooi and C.Zhang,
M2R: Enabling stronger privacy in MapReduce computation,
in: USENIX Security 2015, J.Jung and T.Holz, eds,
USENIX Association, 2015,
pp. 447–462.
55.
P.Valiant,
Incrementally verifiable computation or proofs of knowledge imply
time/space efficiency, in: TCC 2008, R.Canetti, ed.,
LNCS, Vol. 4948,
Springer, Heidelberg,
2008, pp. 1–18.
56.
J.Van Bulck,
M.Minkin, O.Weisse, D.Genkin, B.Kasikci, F.Piessens, M.Silberstein,
T.F.Wenisch,
Y.Yarom and R.Strackx,
Foreshadow: Extracting the keys to the intel sgx kingdom with transient
out-of-order execution, in: USENIX Security Symposium,
2018.
57.
R.S.Wahby, I.Tzialla, A.Shelat, J.Thaler and M.Walfish,
Doubly-efficient zkSNARKs without trusted setup, in:
2018 IEEE Symposium on Security and Privacy, IEEE
Computer Society Press, 2018,
pp. 926–943. doi:10.1109/SP.2018.00060.
58.
N.Weichbrodt,
A.Kurmus, P.R.Pietzuch and
R.Kapitza,
Asyncshock: Exploiting synchronisation bugs in intel SGX
enclaves, in: ESORICS 2016, 2016,
pp. 440–457.
59.
Y.Xu, W.Cui
and M.Peinado,
Controlled-channel attacks: Deterministic side channels for untrusted
operating systems, in: Proceedings of the 2015 IEEE Symposium on
Security and Privacy, SP ’15, IEEE Computer
Society, 2015, pp. 640–656.
doi:10.1109/SP.2015.45.
60.
B.Zhang, Y.Chen, J.Li,
Y.Zhou, P.Thai, H.-S.Zhou and K.Ren,
Succinct scriptable nizk via trusted hardware, in:
European Symposium on Research in Computer Security,
Springer, 2021,
pp. 430–451.
61.
F.Zhang, E.Cecchetti, K.Croman, A.Juels and E.Shi,
Town crier: An authenticated data feed for smart
contracts, in: ACM CCS 2016, E.R.Weippl, S.Katzenbeisser,
C.Kruegel, A.C.Myers and S.Halevi, eds,
ACM Press, 2016,
pp. 270–282.
62.
Y.Zhang, D.Genkin and J.Katz, D.Papadopoulos,
C.Papamanthou,
vSQL: Verifying arbitrary SQL queries over dynamic outsourced
databases, in: 2017 IEEE Symposium on Security and
Privacy, IEEE Computer Society Press,
2017, pp. 863–880. doi:10.1109/SP.2017.43.
