Batch Interface PoC

This is a proof of concept for the batch object proposed in this comment. There are also some discussions here.
I made the following decisions to simplify the implementation of this PoC:

no randomizer generation.
no API for decompressing schnorr_sig.
no API for decompressing tweak_check.
support only strauss_batch for batch verification.
no callback func and callback data.

Note: This PoC demonstrates user interaction with the batch object. I made some terrible design decisions (like a bad refactor of strauss_batch) to cut implementation time. These won't persist in the final implementation.

Interface Details

Batch Object Structure

typedef struct batch_struct{
    secp256k1_scratch *data; /*(scalar, Point)*/
    secp256k1_gej *points; /* base ptr of Points */
    secp256k1_scalar *scalars; /* base ptr of scalars */
    secp256k1_scalar sc_g; /* scalar of G */
    secp256k1_gej res_gej; /* final result as gej */
    size_t len; /* current len */
    size_t capacity; /* max possible len */
    int result; /* final result as success or fail */
} batch;

API's available to the user

/* allocates the memory for the batch object */
batch* batch_context_create(size_t n);

/* this API will be replaced by `batch_add_schnorrsig` and `batch_add_xonly_tweak_check` in the final implmentation*/
int batch_add_one_term(batch *ctx, const secp256k1_scalar *sc, const secp256k1_ge *pt);

/* not implemented 
adds (-ai, Qi), (ai, Pi) to the batch object
Qi = tweaked pubkey key  - secp256k1_gej
Pi = internal pubkey - secp256k1_gej
ai = randomizer - secp256k1_scalar
*/
int batch_add_xonly_tweak_check(batch* ctx, const unsigned char *tweaked_pubkey32, int tweaked_pk_parity, const secp256k1_xonly_pubkey *internal_pubkey, const unsigned char *tweak32);

/* not implemented 
adds (ai, Ri), (ai.ei, Xi) to the batch object
Ri = nonce commitment - secp256k1_gej
Xi = pubkey - secp256k1_gej
ai = randomizer - secp256k1_scalar
*/
int batch_add_schnorrsig(batch* ctx, const unsigned char *sig64, const unsigned char *msg, size_t msglen, const secp256k1_xonly_pubkey *pubkey);

/* computes the multi-multiplication:
0 ?= -sc*G + A1 + a2.A2 + ... + au.Au
*/
int batch_verify(batch *ctx);

/* destorys the context object */
void batch_context_destroy (batch *ctx);

Build Instructions

To clone this repository:

git clone --recurse-submodules [URL Link]
cd batch-verify-poc

To build and run the code:

make
./main #batch object usage example
./scratch #secp256k1_scratch usage example

Checklist

Make sure the following are in the final implementation.

Batch object needs to be opaque in the final impl
Modify libsecp256k1 build to support a new API
Generate randomizers
In batch_context_create() if user gives n allocate 2n points space (different from this PoC)
In batch_add_one_term, transparently (print to terminal) run batch_verify if the scratch space is full

Design Decisions

Allocating scalar: secp256k1_scalar[n], points: secp256k1_gej[n] consecutively (on scratch space) during batch object creation.
- user wants to run verify on n1 terms (n1 < n). Now, 2*(n-n1) space on scratch will never be used
Refactor staruss_batch and pippenger_batch by adding two new arguments: secp256k1_scalar* scalars and secp256k1_gej* points.
- if points = scalars = NULL, then the scratch space does not have any points and scalars allocated inside it (same as old impl).
- if scalars != NULL or points != NULL, then the scratch contains a contiguous block of secp256k1_scalars (pointer by scalars variable) or secp256k1_gej (pointer by points variable). Hence, strauss_batch avoid allocating space for points or scalars.
- This seems like a bad refactor. Try to think of a design where we don't need to pass both scalars and points base pointers.
Randomizer generation - see proposal
Synthetic Randomness - see proposal

Scratch Space Notes

After allocating memory block in scratch (int* ptr = scratch_alloc(10)) don't use scratch->data to access the value, use only ptr
void pointers in C

Doubts

why is data present (in temp ptr) after destroying the scratch space?
why does allocating 3 points (secp256k1_ge) on scratch space require more memory than 3*sizeof(secp256k1_ge)?
- 3 * sizeof(secp256k1_ge) = 3 * 88 = 264
- but after scratch_alloc(264), the scratch->alloc_size = 272 not 264. why?
- read about alignment of C structs
scratch_destroy does not seem to free the scratch->data why? Also, its max_size and alloc_size are not set to 0 after destroying the object.
The final implementation will not have callback func or callback data, right?

siv2r/batch-verify-poc

ErrorLooks like something went wrong!

About

Topics

Resources

Uh oh!

Stars

Watchers

Forks

Releases

Packages 0

Languages

Error
Looks like something went wrong!

Packages