Documentation
Testing via devcontainer
You can quickly test our library by using the associated devcontainer to create its environment. Simply click on Code–>Codespaces–>Create codespace on master above to get started. This creates a docker container on a Github server that includes all of the dependencies and provides a web-based VScode interface to our current codebase. You can compile and run our benchmarks in this environment, but some of them may be slower than our reported values due to the VM.
Instructions to build
This package depends on cmake, openssl, zstd, clang, googletest and
googlebenchmark.
Ubuntu, debian
$ sudo apt install libssl-dev libzstd-dev libgtest-dev libbenchmark-dev zlib1g-dev
Fedora, redhat
$ yum install -y clang libzstd-devel openssl-devel git cmake google-benchmark-devel gtest-devel
MacOS
Ensure that Xcode command line tools such as clang and cmake are installed.
$ brew install googletest google-benchmark zstd
Building manually
First run the cmake initialization step
$ CXX=clang++ cmake -D CMAKE_BUILD_TYPE=Release -S lib -B clang-build-release --install-prefix ${PWD}/install
Next:
$ cd clang-build-release && make -j 16 && ctest -j 16
Running benchmarks
We have defined several unit, sumcheck, and zk benchmarks. Here are some of
them:
$ ./algebra/fft_test --benchmark_filter='BM_*'
$ ./circuits/sha/flatsha256_circuit_test --benchmark_filter=BM_ShaZK_fp2_128
1 - Using ZK in Identity Protocols
How to request a ZK proof via openid
Here is a proposed method to use the openid4vp framework to request a ZK proof. Openid4vp is an under-specified framework designed to encapsulate any specific identity format. One idea is for the dcql_query element to contain enough information to identity a ZK system, a ZK circuit, and a ZK theorem which defines the set of acceptable respose messages.
In the example below, the only differences with a standard mdoc request occur in the format and meta components: the special mso_mdoc_zk format value, and
the inclusion of zk_system_type and verifier_message, which are defined in the ISO 18013-5 second edition, section 10.3.4.
{
"response_type": "vp_token",
"response_mode": "dc_api",
"nonce": "nonce",
"dcql_query": {
"credentials": [{
"id": "cred1",
"format": "mso_mdoc_zk",
"meta": {
"doctype_value": "org.iso.18013.5.1.mDL"
"zk_system_type": [
{
"system": "longfellow-libzk-v1",
"circuit_hash": "f88a39e561ec0be02bb3dfe38fb609ad154e98decbbe632887d850fc612fea6f",
"num_attributes": 1,
"version": 1
}
],
"verifier_message": "challenge"
},
"claims": [{
"path": ["org.iso.18013.5.1", "family_name"]
}]
}]
},
"client_metadata": {
"jwks": {
"keys": [
{
"kid": "verifier",
"use": "enc",
"alg": "ECDH-ES",
"kty": "EC",
"crv": "P-256",
"x": "1234567890",
"y": "1234567890"
}
]
},
"authorization_encrypted_response_alg": "ECDH-ES",
"authorization_encrypted_response_enc": "A128GCM"
}
}
2 - Reviews
This page documents the security reviews of Longfellow that have been completed by external organizations.
Trail of Bits
Trail of Bits has reviewed our system and produced a
report. All of the issues have been addressed in the latest release. To briefly comment on the issues marked “High” severity:
Issue #1: The report noted that our library does not read each circuit to verify its hash. Because our library is intended to be used in a high-performance server, our library provides these methods, but does not perform the check in each call to the verifier method. Instead, we expect a proper verifier implementation to perform this costly check once upon start and then cache the circuits in memory. Our reference verifier implementation illustrates how this can be done.
Issue #10: Indeed, this report identified one under-constrained check in a circuit. The check used a private (witness) variable to determine the length of a string, when instead, it should have used the public (available to the verifier) version of that length. This issue has been resolved in the mdoc circuit.
ISRG
- ISRG-01. David Cook of ISRG reported a security flaw in our MDOC circuit that was patched on October 17th. The error stems from under-constraining variables in the ZK circuit. Specifically, the hash circuit witness values representing indices into the CBOR data are missing checks that they are less than the length of the mdoc MSO, which is used in signature verification. Witness variables for bytes of the MSO past the “correct” SHA-256 block are effectively unconstrained, so if the CBOR index witness variables point into that region, then the prover can substitute its own values for mdoc fields.
- To resolve this issue, additional checks have been added to verify that all bytes past the “correct” SHA-256 block are zero. Furthermore, all indices into the MDOC bytes are checked to be less than the number of bytes that are hashed. The number of bytes that are hashed is derived from the SHA block itself.
- The change is available in version 0.8.4
3 - Benchmarks
This page documents the results of some of our benchmark suite on different hardware. All of our code runs single threaded for deployment purposes. It is important not to consume a user’s battery.
Mac M4
FFT
Because Longfellow uses the Ligero proof system as a component, the FFT may be a bottleneck (without other measures). This benchmark measures the FFT time over different fields. Note that we have another, more realistic interpolation benchmark that measures the Reed-Solomon encoding time. However, this benchmark provides a good method to compare against other implementations. The Fp2 field is the quadratic extension over the P256 prime. The Fp128 and Fp64 fields are prime fields of size 128- and 64- bits respectively, and the Fp64_2 field is the quadratic extension of the later.
---------------------------------------------------------------
Benchmark Time CPU Iterations
---------------------------------------------------------------
BM_FFT_Fp256_2/1024 170279 ns 170237 ns 4108
BM_FFT_Fp256_2/4096 847506 ns 847413 ns 825
BM_FFT_Fp256_2/16384 4026932 ns 4026901 ns 172
BM_FFT_Fp256_2/65536 18797363 ns 18797378 ns 37
BM_FFT_Fp256_2/262144 87642167 ns 87641875 ns 8
BM_FFT_Fp256_2/1048576 446753854 ns 446742500 ns 2
BM_FFT_Fp256_2/4194304 2407741792 ns 2404540000 ns 1
BM_FFT_Fp128/1024 21159 ns 21159 ns 32950
BM_FFT_Fp128/4096 100587 ns 100587 ns 6956
BM_FFT_Fp128/16384 491966 ns 491966 ns 1421
BM_FFT_Fp128/65536 2364386 ns 2364385 ns 296
BM_FFT_Fp128/262144 11986404 ns 11986414 ns 58
BM_FFT_Fp128/1048576 57057522 ns 57053692 ns 13
BM_FFT_Fp128/4194304 328675687 ns 325409000 ns 2
BM_FFT_F64_2/1024 21233 ns 21219 ns 32806
BM_FFT_F64_2/4096 100339 ns 99601 ns 7064
BM_FFT_F64_2/16384 483286 ns 483174 ns 1379
BM_FFT_F64_2/65536 2565717 ns 2474719 ns 302
BM_FFT_F64_2/262144 11513783 ns 11501557 ns 61
BM_FFT_F64_2/1048576 66653771 ns 63372917 ns 12
BM_FFT_F64_2/4194304 319619000 ns 317158000 ns 2
BM_FFT_F64/1024 8731 ns 8552 ns 85701
BM_FFT_F64/4096 36468 ns 36466 ns 19083
BM_FFT_F64/16384 169061 ns 168981 ns 4119
BM_FFT_F64/65536 964327 ns 945066 ns 775
BM_FFT_F64/262144 4254247 ns 4249928 ns 166
BM_FFT_F64/1048576 20092198 ns 20092200 ns 35
BM_FFT_F64/4194304 106302274 ns 106238286 ns 7
SHA
This benchmark measures the time to prove in zero-knowledge the knowledge of a pre-image of size at most N blocks for a given 256-bit string.
--------------------------------------------------------------
Benchmark Time CPU Iterations
--------------------------------------------------------------
BM_ShaZK_fp2_128/1 5300363 ns 5300367 ns 109
BM_ShaZK_fp2_128/2 9602156 ns 9600622 ns 74
BM_ShaZK_fp2_128/4 18730299 ns 18730225 ns 40
BM_ShaZK_fp2_128/8 35389356 ns 35289150 ns 20
BM_ShaZK_fp2_128/16 65615658 ns 65553800 ns 10
BM_ShaZK_fp2_128/32 125226342 ns 125226400 ns 5
BM_ShaZK_fp2_128/33 132710525 ns 132710400 ns 5
ECDSA
Proof of posession of a signature (r,s) on a message e under public key (x,y).
The combined improvements in our system since our eprint paper have reduced the
time to prove posession of 1 signature to <17ms.
-------------------------------------------------------------------
Benchmark Time CPU Iterations
-------------------------------------------------------------------
BM_ECDSAZKProver/1 16713685 ns 16713667 ns 42
BM_ECDSAZKProver/2 26511215 ns 26498815 ns 27
BM_ECDSAZKProver/3 38322847 ns 38322889 ns 18
BM_ECDSAZKVerifier/1 10365617 ns 10365627 ns 67
BM_ECDSAZKVerifier/2 16086716 ns 15973932 ns 44
BM_ECDSAZKVerifier/3 23454887 ns 23454323 ns 31
5 - Reference
Low level reference docs for your project.
Doxygen data structure and file documentation.
6 - Longfellow ZK System spec parameters
List of ZK System spec parameters expected by Longfellow ZK library
ISO 18013-5 and and OpenId4VP allow RPs to request ZKP responses and specify any ZKP system and some parameters required to make sure RP will be able to verify the proof correctly.
The list of the parameters and their values are not defined in the standard and are specific for each ZKP system.
This document describes which parameters should be used by users of Longfellow ZK System. Those parameters are currently used by Google Wallet and Multipaz Wallet/RP.
For the Longfellow ZK, the following parameters and values should be used:
- zkSystemId: <any value, we recommend using circuit_hash to avoid confusion>
- system: ’longfellow-libzk-v1'
The following parameters must be present:
- circuit_hash: The hash of the used circuit.
- num_attributes: The number of requested attributes.
- version: The circuit version.
- block_enc_hash: The
block_enc parameter for the ZK proof of the hash component. - block_enc_sig: The
block_enc parameter for the ZK proof of the signature component.
The paramters change relatively often. We are releasing new circuits regularly, so it’s strongly recommended not to build ZKSpecs manually nor hardcode them, but instead to use kZkSpecs as a source of truth for the parameters
and convert it to CBOR/JSON as needed for corresponding protocols.
ZK Spec Parameters in ISO 18013-5
ISO 18013-5 Second Edition section 10.2.7 defines ZkSystemSpec like this:
ZkSystemSpec = {
"zkSystemId": ZkSystemId
"system": ZkSystem,
"params": ZkParams,
* tstr => RFU
}
ZkSystem = tstr
ZkSystemId = tstr
ZkParams = { * tstr => Ext}
This is an example of a correctly filled ZKSystemSpec:
Spec1 = {
"zkSystemId": "137e5a75ce72735a37c8a72da1a8a0a5df8d13365c2ae3d2c2bd6a0e7197c7c6"
"system": "longfellow-libzk-v1",
"params": {
"circuit_hash":"137e5a75ce72735a37c8a72da1a8a0a5df8d13365c2ae3d2c2bd6a0e7197c7c6",
"num_attributes": 1,
"version": 6,
"block_enc_hash": 4025,
"block_enc_sig": 2945,
}
}
ZK Spec Parameters in OpenID4VP DCQL
Currently there is no standard DCQL for OpenID4VP. We recommend using mso_mdoc_zk format to request an ISO mDL via OpenId4VP. This is an example of a correctly filled zk_system_type for this type of request:
"zk_system_type": [
{
"id": "137e5a75ce72735a37c8a72da1a8a0a5df8d13365c2ae3d2c2bd6a0e7197c7c6"
"system": "longfellow-libzk-v1",
"circuit_hash":"137e5a75ce72735a37c8a72da1a8a0a5df8d13365c2ae3d2c2bd6a0e7197c7c6",
"num_attributes": 1,
"version": 6,
"block_enc_hash": 4025,
"block_enc_sig": 2945,
}
],