cryptimeleon/incentive-system

A cryptographic incentive system.

incentive-system's Issues

Show QR code and rewards to claim (e.g. Teddy) after payment

It would be a nice addition to show a scannable code after checkout that a cashier could scan to verify which rewards a user gets.

getSpendAmount and getTransactionID endpoints for basket server

We need the above endpoints on the basket server to receive a trusted spend amount and transaction ID in the runDeduct method of deduct.DeductService.

Currently both values are hard-coded in the said class.

Make number of digits in TokenUpdateZkp and TokenPointsZkp mutable

Some of the ranges are oversubscribed by a lot (currently 6 digits).
Think about number of digits of geq or leq proofs that cover semantic range (e.g. when proving a user has a streak larger than 10, supporting streaks up to 200 weeks in a row might be sufficiently large). Find the smallest number of digits that can represent 200-10.

CryptoRepository classes in issue, credit and deduct are identical

It might be a good idea to refactor them into a single class (e.g. one CryptoRepository class in the services package).
However, this should be done on a dedicated branch in order to not overload the currently existing feature branches.

Generator of second group in bilinear group needed?

The generator g2 of the group G2 of BG is not used anywhere except for the return statement of the method that generates it.
Afaik, G2 is only needed for the internal workings of the underlying SPS-EQ scheme of the cryptimeleon incentive system.

So we might consider removing g2 from the code (IncentivePublicParameters class in crypto package).

Add credit crypto protocol to credit service

Promotion service

To keep a nice and clean microservice architecture, we need an additional (Spring) web service that handles all promotion related data.

This means that it stores records for all existing promotions and provides an endpoint for providers to add new ones to the system.
Each promotion needs to be identified by a promotion ID that is passed to the runDeduct algorithm in deduct.DeductService and can be used to resolve the promotion that the user that caused the execution of runDeduct wants to take part in.

This resolution is required to let deduct.DeductService know which reward item to add to the user's basket or (in versions beyond Feb22) which other action to perform (e.g.. 30% off on the basket, ...).

Some potential performance improvements

So first of all, we usually shouldn't blindly optimize performance, but rather check for performance hotspots and try to fix those.

That said, here are some few things I noticed during the code review:

TokenPointsZkp with additional commitment

In the TokenPointsZkp, it may be worth it (especially for policies with many leafs) to have the user create an additional commitment C' to just the point vector (without usk etc.), instead of always proving knowledge of usk, esk, dsrnd, etc. that open the "full" signed commitment every time they want to prove anything about the point vector. This costs basically nothing (just one more multiexponentiation and one more Zp element to prove that C' can be opened to the same values as in the signed commitment) in the "main" proof, but makes every statement about the point vector quite a bit smaller.

Tracing performance

When decrypting the (user's share of) esk* during tracing, the all possible w^b should be precomputed, ready in memory. Furthermore, more crucially, the inner loop shouldn't recompute the right hand side of the equality check anew every time.
Ideally, the code is something like:

// During setup
for b in {0,1, ..., ESK_DEC_BASE}: compute and store w^b in a HashMap w^b -> b;
//During decryption
for each digit i: decryption[i] = decrypt_elgamal(i).compute(); //start running those computations in parallel.
for each digit i:
  result[i] = HashMap(decryption[i])

generateEarnRequestResponse: concurrency

In generateEarnRequestResponse, start computing the new SPSEQ first (in the background), then run the checks, instead of the other way around. Only return the SPSEQ if the check succeeds, of course.

Benchmark with n=1000 using MCL groups

When performing the benchmark with large n (e.g. 1000) and the MCL group, the following error occurs when testing Spend-Deduct: With the Debug group, even larger n (e.g. 10000) work fine.

    May 28, 2021 9:20:37 PM org.cryptimeleon.incentivesystem.cryptoprotocol.BenchmarkTest lambda$runBenchmark$0
    INFO: SPEND_DEDUCT, round 0
    May 28, 2021 9:20:54 PM org.cryptimeleon.incentivesystem.cryptoprotocol.BenchmarkTest lambda$runBenchmark$0
    INFO: SPEND_DEDUCT, round 100

Exception: java.lang.OutOfMemoryError thrown from the UncaughtExceptionHandler in thread "ForkJoinPool.commonPool-worker-5"
    Exception in thread "ForkJoinPool.commonPool-worker-13" java.lang.OutOfMemoryError: Java heap space
    Exception in thread "ForkJoinPool.commonPool-worker-3" java.lang.OutOfMemoryError: Java heap space
    Exception in thread "ForkJoinPool.commonPool-worker-7" java.lang.OutOfMemoryError: Java heap space
    Exception in thread "ForkJoinPool.commonPool-worker-15" java.lang.OutOfMemoryError: Java heap space
    Exception in thread "ForkJoinPool.commonPool-worker-9" java.lang.OutOfMemoryError: Java heap space

And of the Gradle task:

org.gradle.api.internal.tasks.testing.TestSuiteExecutionException: Could not complete execution for Gradle Test Executor 3.
	at org.gradle.api.internal.tasks.testing.SuiteTestClassProcessor.stop(SuiteTestClassProcessor.java:63)
	at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:78)
	at java.base/jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.base/java.lang.reflect.Method.invoke(Method.java:567)
	at org.gradle.internal.dispatch.ReflectionDispatch.dispatch(ReflectionDispatch.java:36)
	at org.gradle.internal.dispatch.ReflectionDispatch.dispatch(ReflectionDispatch.java:24)
	at org.gradle.internal.dispatch.ContextClassLoaderDispatch.dispatch(ContextClassLoaderDispatch.java:33)
	at org.gradle.internal.dispatch.ProxyDispatchAdapter$DispatchingInvocationHandler.invoke(ProxyDispatchAdapter.java:94)
	at jdk.proxy1/jdk.proxy1.$Proxy2.stop(Unknown Source)
	at org.gradle.api.internal.tasks.testing.worker.TestWorker.stop(TestWorker.java:135)
	at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:78)
	at java.base/jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.base/java.lang.reflect.Method.invoke(Method.java:567)
	at org.gradle.internal.dispatch.ReflectionDispatch.dispatch(ReflectionDispatch.java:36)
	at org.gradle.internal.dispatch.ReflectionDispatch.dispatch(ReflectionDispatch.java:24)
	at org.gradle.internal.remote.internal.hub.MessageHubBackedObjectConnection$DispatchWrapper.dispatch(MessageHubBackedObjectConnection.java:182)
	at org.gradle.internal.remote.internal.hub.MessageHubBackedObjectConnection$DispatchWrapper.dispatch(MessageHubBackedObjectConnection.java:164)
	at org.gradle.internal.remote.internal.hub.MessageHub$Handler.run(MessageHub.java:414)
	at org.gradle.internal.concurrent.ExecutorPolicy$CatchAndRecordFailures.onExecute(ExecutorPolicy.java:64)
	at org.gradle.internal.concurrent.ManagedExecutorImpl$1.run(ManagedExecutorImpl.java:48)
	at java.base/java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1130)
	at java.base/java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:630)
	at org.gradle.internal.concurrent.ThreadFactoryImpl$ManagedThreadRunnable.run(ThreadFactoryImpl.java:56)
	at java.base/java.lang.Thread.run(Thread.java:831)
Caused by: java.lang.OutOfMemoryError: Java heap space: failed reallocation of scalar replaced objects

Basket Server

We need to mimic the behavior of the basket server in order to prototype the incentive system. We ignore the rewards at this point to keep complexity low. Later, endpoints for creating, editing, querying, ... rewards could be incorporated.

We have the following use-cases for the basket server.

• Users initialize a basket
• Users add a product to their basket
• Users remove a product from their basket
• Users query their basket's content
• Users pay for the items in their basket
• Users use their paid basket to get a reward (credit-earn-protocol)

Furthermore, we have the following requirements for the basket server:

• Users should only be able to see and edit their own baskets
• A basket can be used only once for getting a reward
• Users should be able to retry getting their reward in case something went wrong
• The payment should be verified

Hence, we need the following API endpoints:

• A verified but anonymous endpoint for users to initialize, edit, and query the basket.
• An authenticated endpoint for cash registers and stores to validate the basket contents and perform the payment. (Ensure user does not add anything during the payment process)
• An authenticated endpoint for the incentive system to validate credit-earn requests and mark baskets as redeemed.

Ideas for this:

• Users get a token to authenticate to the basket server when they create a basket.
• Cash registers and incentive services use TLS certificates to authenticate.
• We use TLS to encrypt all traffic

Implement Credit<->Earn protocol

Make the basket server store baskets in an actual database instead of the in-memory data structures used so far.

Wrong token count after cascadingInvalidationsTest of double-spending protection service

The mentioned test attempts to construct the graph from Chapter 6 of the 2019 UACS paper.
Thus the expected token count would be 5, actual is 4.

Log output from the test shows that the program thinks that the remainder token dsid5 of transaction t2Prime is already in the database so it does not add it.
Since dsid5 never is computed before (since it is a remainder token which are only traced upon double-spending attempts being detected), it is most likely that this is the missing token.

BigInteger::intValueExact is only available for android 12+

We could replace it by BigInteger::intValue which does not throw and Error if too large for an int, or write our own implementation to ensure the app works on older devices.

App: Promotion-type dependent UIs

Enhance the appearance and functionality of promotion-specific UIs, e.g. by not showing VIP updates to lower degrees that no user would choose.

Implement Issue<->Join protocol

App: Colorscheme

Replace the color scheme by one with a secondary color that looks less like the error color

Promotion DB

Currently, the types of existing promotions are hard-coded in the promotion API.
A long-term solution would be to store in an actual database (re-use persistent variant of the double-spending protection database).

Test helper to generate valid tokens with fixed valu

Write a helper method, that allows generating valid tokens with n points given all key material for testing purposes.

The most naive version would be just running issue-join and credit-earn once.

Pipeline enhancement

• Add test coverage
• Ignore changes in .md files

Add lock to basket to protect spend-deduct, pay and credit-earn workflow (protect workflow=user cannot change basket contents while in progress).

Compatibility of double-spending protection service with multiple promotions

Implement Double Spending Crypto algorithms

• DBSync
• Trace
• Link
• VerifyDs

Add payAndRedeem workflow to app.

Users should be able to:

• Select for every promotion what update to do on the token based on what's possible given the current basket
• Run the token-updates and pay the basket to get the updated tokens

Integrate recent changes from Spend-Deduct API into double-spending protection service

The double-spending protection service still uses simple spend amounts. Should use an object representing the user choice of rewards (see Dev Meeting X notes).

Update glossary

Add all variables from double-spending protection to glossary (README of crypto package)

Zkp implementations for the crypto protocols need to be refactored

crypto/.../model/proofs and crypto/.../proof should be merged into one directory for a better project structure

Refactor token ZKP tree

The quick pitch

Currently, there are two "leaf" statements for the "Spend" ZKP: TokenPointsZkp and TokenUpdateZkp. Each of those can do ... basically anything: range proofs, equality, you name it.

This is done for performance reasons: every leaf proof needs to prove knowledge of the point vector and commitment opening (see #90), before being able to do any actual work; so aggregating everything into a single leaf makes sense performance-wise.

It comes with disadvantages though:

• The API for setting up one such leaf is quite cumbersome, having to operate on several arrays.
• The performance savings are stopping short slightly for some (somewhat specific) statements where I need to prove something about the old vector and the new one, forcing me to AND-compose both types of leafs, incurring some overhead.
• If we ever wanted to extend this, say, by proving set membership of some point vector value, or proving something about a weighted sum of vector entries, we'd have to make those two classes even bigger.

Proposal

Ideally for the API and class complexity (the first and last bullet point), every leaf just does a small specialized thing, i.e. we'd have small leaf nodes like "new LinearRelationLeafNode(new[i].equals(old[i].add(5))" or "new InqualityLeafNode(new[i], 20)".

To make this work with good performance, it would be up to the "tree compiler" (SpendDeductBooleanZkp) to greedily aggregate leaf nodes connected by ANDs into a single SchnorrProof (which would then correspond to a merge of TokenPointsZkp and TokenUpdateZkp).

For example, take ((A and B and C) or (D and E)) as a SpendDeduct tree, where each letter is any statement over the old and new point vectors.
Every such leaf statement has a method List<SchnorrFragment> getAsSchnorrFragments(Vector<ZnWitness> oldVector, Vector<ZnWitness> newVector) that outputs the SchnorrFragment corresponding to the statement (say, a range proof about some weighted sum of old and new entries, or whatever).

In that scenario, the tree conversion should set up two SigmaProtocols of type ZkpLeafProof. One to handle A and B and C and one to handle D and E.

The ZkpLeafProof would work as follows:

• The list of statements it should handle (e.g., A,B,C) is passed in the constructor.
• ZkpLeafProof asks each statement whether it intends to state something about the old vector and/or the new vector.
• ZkpLeafProof sets up a proof consisting of
  • the "I can open the old/new point commitment" statement (depending on which one is needed, or both)
  • the fragments returned by getAsSchnorrFragments of A,B,C.

If none of the statements say they want to prove something about newVector, then ZkpLeafProof would just pass null for newVector in the getAsSchnorrFragments call.

Better API for TokenUpdateLeaf

I'm not crazy about the "pass arrays of BigIntegers or null" interface design for TokenUpdateLeafs. The incentive system user should probably be spared this and be allowed to specify their constraints more naturally.
This would indeed be the case here because now users would just add one leaf node for every inequality/linear relation they want checked instead of having to aggregate them into arrays.

Related

Issue #90 asks to have subproofs do their statements over a small committed vector. This is orthogonal to this issue, but is easily done within the same rework.

One open API issue

Being able to write things like new LinearRelationLeafNode(new[i].equals(old[i].add(5)) would require there to be some variables new[i] and old[i] at the time of instantiating those.
I'd recommend doing this using the Cryptimeleon variable framework somehow. Let me know if you want to discuss ideas.

Time to implement

This might sound like a complex change now, but I'm pretty sure this is mostly copy/pasting existing code cleverly into new classes and simplifying it a bit; plus a little bit of tree logic and API improving.

Implement Spend<->Deduct protocol

Allow batch update requests instead of sending every request individually

Genesis Token

Change join process to use genesis tokens for which a user needs proof its identity.
Currently, user-generated keys are used.

Payment service

Add simple web service for simulating the payment step. When a user clicks pay, the backend sends an authenticated call to set the paid flag of the basket.

Support encoding a promotionId to tokens

Add double spending service with the double spending DB

We should consider combining this with the deducting service.

Error Handling / Control Flow

We need to decide upon a concept for error handling (e.g. when the request's signature is not valid).

Bug in notEnoughPointsTest of deduct service

notEnoughPointsTest fails with a NullPointerException in generateAnnouncementSecret of the craco.protocols AndProof class.
Could not find the actual problem after some hours of debugging

Promotion: Differentiate ZKPs with side-effect on basket and those without a side effect on the basket

Important difference in the app and handling of adding these to the basket after payment.

Refactor UpgradeVipZkpTokenUpdate

Make this Update have the same side effect as the reached VIP level.
https://github.com/cryptimeleon/incentive-system/blob/develop/promotion/src/main/java/org/cryptimeleon/incentive/promotion/vip/UpgradeVipZkpTokenUpdate.java

Cache SpendProviderOutput at incentive service, send it periodically to the DS protection service

At the moment, the deduct service sends every observed transaction to the deduct service immediately.
To provide actual offline double-spending protection, we need a cache for the observed transaction data which is periodically transferred to the double-spending protection database.

Issue-join protocol does not use final pp of incentivesystem

See

incentive-system/crypto/src/main/java/org/cryptimeleon/incentive/crypto/IncentiveSystem.java

Line 79 in 06d594b

public JoinRequest generateJoinRequest(IncentivePublicParameters pp, ProviderPublicKey pk, UserKeyPair ukp) {

incentive-system/crypto/src/main/java/org/cryptimeleon/incentive/crypto/IncentiveSystem.java

Line 119 in 06d594b

public JoinResponse generateJoinRequestResponse(IncentivePublicParameters pp, ProviderKeyPair pkp, GroupElement upk, JoinRequest jr) throws IllegalArgumentException {

incentive-system/crypto/src/main/java/org/cryptimeleon/incentive/crypto/IncentiveSystem.java

Line 159 in 06d594b

public Token handleJoinRequestResponse(IncentivePublicParameters pp, ProviderPublicKey pk, UserKeyPair ukp, JoinRequest jReq, JoinResponse jRes) {

Design and add dumb coupons for the spend-deduct process. These are added to the basket after successfully executing spend-deduct and enforce the promotion.

Make Bilinear Group parameter of setup

This allows switching between the Counting, MCL, Barreto-Naehrig Bilinear Group

Add issue crypto protocol to issue service

Load dummy tokens for every promotion at start of the app.

Add provider public key well-formedness proof

We omitted the ZKP of the well-formedness of the provider public key in the beginning of the Issue-Join protocol for now.
We should add it later (where to do so will be discusseed on May 21, 2021)

Benchmark

Add a benchmark that times the execution time of each major function (and prints them and the combined results nicely) as the app. I think we can reuse most of the code of the integration test for such a benchmark and maybe execute it several times for more accurate results.
We could add a Gradle function for this, such that this expensive test case is not executed every time we execute the pipeline

Create spend/deduct service

We can hardcode rewards for our proof of concepts. This can be replaced by some promotion instance, later.

Add bar scanner to app that allows scanning items and adding them to the basket.

We need a bar scanner view or activity (view would be better) that allows scanning products, shows product information and allows putting them into the basket.

Deactivating clearDatabase API in DsprotectionController class

problem: this is public API accessible via HTTP requests, i.e. not secure (attackers accessing this endpoint could delete the entire double-spending database).

Remove protocoldefinition

The package is obsolete, move the definitions to the individual services.