UC SE Sonic

This crate is a UC-secure and simulation extractable (SE) version of Sonic¹, an updatable zk-SNARK protocol. We do this by using a generic transformation (BB-Lamassu [3]) that turns any sound NIZK into a simulation extractable NIZK — in a UC-secure way and compatible with the updatable setting.

THIS IMPLEMENTATION IS A PROTOTYPE AND IS FULL OF BUGS, DO NOT USE IT IN PRODUCTION

Background

Lamassu

Previous work² gave a generic transformation called Lamassu which lifts any sound NIZK into a simulation extractable NIZK, again in the updatable setting but in a non-black-box and therefore non-UC way. Lamassu changes the base NIZK's language from

{ (x,w) | x = H(w) }

to

{ ((x,h), (w,r)) | x = H(w) ∨ h = g^r }

with the proof being a tuple (σ, π, σ_OT, pk_ℓ, pk_OT), where

• σ ← Σ.Sign(sk_ℓ, pk_OT): an updatable signature (Schnorr over Jubjub) on a one-time signature public key,
• π ← Π.P(crs_up, (x':=(x,⊥), w':=(w,⊥)): a NIZK for the new language using the base protocol (Sonic) and the base statement/witness pair (i.e., using the left branch of the OR),
• σ_OT ← Σ_OT.Sign(sk_OT, π || x || c || pk_ℓ || σ): a strongly-unforgeable one-time signature (sOTS) (schnorrkel) on the above NIZK, the base statement x, and the above updatable ciphertext, updatable encryption public key, and updatable signature, using the secret key corresponding to the above one-time public key, and
• pk_ℓ, pk_OT: the public keys of the updatable and one-time signature schemes.

The intuition is that the sOTS is used to sign the parts of the proof that must be non-malleable, and the updatable signature is used to certify the one-time public key. The OR trick adds simulation extractability.

BB-Lamassu

The BB-Lamassu transformation³ is a version of Lamassu which is fully black-box. We introduce an updatable encryption of the underlying witness to enable BB SE (while remaining compatible with updatable CRS) and require the updatable signature to also be BB-extractable. With the new elements compared to Lamassu indicated in bold, the NIZK's language changes from

{ (x,w) | x = H(w) }

to

{ ((x,c,h), (w,ω,r)) | c = Enc(pk, w; ω) ∧ (x = H(w) ∨ h = g^r) }

and the proof is a tuple (σ, c, π, σ_OT, pk_ℓ, pk_OT) consisting of the elements from before plus:

• c ← UP.Enc(pk_up, w; ω): an updatable encryption (ElGamal over Jubjub) of the base scheme's witness, and
• π ← Π.P(crs_up, (x':=(x,c,⊥), w':=(w,ω,⊥)): the NIZK is now for the BB-Lamassu language, still using the base protocol (Sonic) and the base statement/witness pair with the left branch of the OR.

Usage

Compile and run the examples with with cargo run -r --example [example name] [pedersen|sha256] [witness bitsize] [sample size]. The witness bitsize options depend on the statement to prove: 48 or 384 for Pedersen and 512, 1024, or 2048 for SHA256. The default arguments are pedersen with witness bitsize 48 and sample size 5.

Example:

# BB-Lamassu to prove knowledge of a 48-bit Pedersen hash preimage (avg of 10)
cargo run -r --example bb-lamassu pedersen 48 10

# compare to previous work
cargo run -r --example sonic pedersen 48 10
cargo run -r --example lamassu pedersen 48 10

There are also tests:

# test the new building blocks
cargo test --test uc-se

# all tests
cargo test

One can also compile the code (without running anything) with cargo build.

Because of some of the dependencies, we need to use the nightly toolchain. This should be taken care of by the rust-toolchain.toml file but can also be done manually by replacing calls to cargo with cargo +nightly above.

Documentation

cargo doc --open

License

Licensed under either of

• Apache License, Version 2.0, (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Footnotes

1. Mary Maller, Sean Bowe, Markulf Kohlweiss, and Sarah Meiklejohn. Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updateable Structured Reference Strings. Cryptology ePrint Archive paper 2019/099. ↩

2. Behzad Abdolmaleki, Sebastian Ramacher, and Daniel Slamanig. Lift-and-Shift: Obtaining Simulation Extractable Subversion and Updatable SNARKs Generically. Cryptology ePrint Archive paper 2020/062. ↩

3. Universally Composable NIZKs: Circuit Succinct, Non-Malleable and CRS-Updatable. Cryptology ePrint Archive paper 2023/097. ↩