BLS12-377 curve operations by shamatar · Pull Request #2539 · ethereum/EIPs

shamatar · 2020-02-26T18:56:41Z

This EIP adds a set of precompiles to efficiently implement operations over BLS12-377 curve

Make even with master

iAmMichaelConnor · 2020-06-29T08:35:45Z

EIPS/eip-2539.md

+
+To encode points involved in the operation one has to encode elements of the base field and the extension field.
+
+Base field element (Fp) is encoded as `48` bytes by performing BigEndian encoding of the corresponding (unsigned) integer. Corresponding integer **must** be less than field modulus.


@shamatar to be compatible with 32-byte 'words' of the EVM/Solidity (and to allow easy mload and mstore operations of 32-byte values in assembly), perhaps elements of Fp should be encoded as 64 bytes instead?

The first 16-bytes could be enforced to be all zeros, or ignored by the builtin contracts.

It'd be great to get your thoughts.

iAmMichaelConnor · 2020-06-29T08:39:53Z

EIPS/eip-2539.md

+
+Base field element (Fp) is encoded as `48` bytes by performing BigEndian encoding of the corresponding (unsigned) integer. Corresponding integer **must** be less than field modulus.
+
+For elements of the quadratic extension field (Fp2) encoding is byte concatenation of individual encoding of the coefficients totaling in `96` bytes for a total encoding. For an Fp2 element in a form `el = c0 + c1 * v` where `v` is formal quadratic non-residue and `c0` and `c1` are Fp elements the corresponding byte encoding will be `encode(c0) || encode(c1)` where `||` means byte concatenation.


@shamatar perhaps elements of Fp2 could be 128 bytes, to enable easier field arithmetic in solidity (since real and 'imaginary' coefficients could each be stored in a uint[2] or bytes32[2]).

I’ll make similar adjustments to 2537 and will largely copy-paste and updated spec here

github-actions · 2020-09-08T16:20:23Z

There has been no activity on this pull request for two months. It will be closed in a week if no further activity occurs. If you would like to move this EIP forward, please respond to any outstanding feedback or add a comment indicating that you have addressed all required feedback and are ready for a review.

prestwich · 2020-09-14T17:48:39Z

@shamatar We are considering this EIP for inclusion in Celo Blockchain. Has thought been given to updating the precompile list with map to group operations in order to match the #2537 API?

shamatar · 2020-09-16T15:40:57Z

Sure, but I'm not aware of mapping parameters for BLS12-377. The easiest way is to copy-paste #2537 text in here while keeping the curve parameters

prestwich · 2020-09-16T18:08:04Z

I don't know that it's strictly necessary for anyone's use case. But it would be nice to have direct feature parity with the other precompile

MicahZoltu

Looks good! I left some feedback that I encourage checking out but nothing that blocks merging as a draft.

MicahZoltu · 2020-09-22T16:44:31Z

EIPS/eip-2539.md

+---
+
+## Simple Summary
+This precompile adds operation on BLS12-377 curve (from Zexe paper) as a precompile in a set necessary to *efficiently* perform operations such as BLS signature verification and perform SNARKs verifications. Unique properties of BLS12-377 also later allow to have SNARKs that check BLS12-377 pairing in an efficient way and allow e.g. constant-size BLS signature aggregation.


Remove "from Zexe paper". This is a technical document, not a place to give props/kudos/attribution. If you think that the paper is particularly relevant, I recommend adding it to ../assets/eip-2539/zexe-paper.pdf and linking to it in a place where it makes sense that a future reader of this specification would care.

Suggested change

This precompile adds operation on BLS12-377 curve (from Zexe paper) as a precompile in a set necessary to *efficiently* perform operations such as BLS signature verification and perform SNARKs verifications. Unique properties of BLS12-377 also later allow to have SNARKs that check BLS12-377 pairing in an efficient way and allow e.g. constant-size BLS signature aggregation.

Adds BLS12-377 curve operations as precompiles.

Simple summary should be a very terse one-line description. Longer than the title, but not meant to convey much information and instead let the reader quickly identify "am I in the right place?". This may show up in a sub-heading somewhere for example. The rest of this should probably go in the motivation, as it is is discussing why this is useful/interesting.

MicahZoltu · 2020-09-22T16:48:10Z

EIPS/eip-2539.md

+
+Multiexponentiation operation is included to efficiently aggregate public keys or individual signer's signatures during BLS signature verification.
+
+### Proposed addresses table


Suggested change

### Proposed addresses table

### Addresses Table

EIPs don't propose, they assert.

MicahZoltu · 2020-09-22T16:48:38Z

EIPS/eip-2539.md

+|BLS12_377_PAIRING        | 0x19  |
+
+## Motivation
+Motivation of this precompile is to add a cryptographic primitive that allows to get 120+ bits of security for operations over pairing friendly curve compared to the existing BN254 precompile that only provides 80 bits of security. In addition it allows efficient one-time recursive proof aggregations, e.g. proofs about existence of BLS12-377 based signature.


Consider adding some of the stuff from Simple Summary to here. This is a great place to tell users why this EIP is a useful standard.

MicahZoltu · 2020-09-22T16:49:29Z

EIPS/eip-2539.md

+x is negative = false
+```
+
+#### Fine points and encoding of base elements


Suggested change

#### Fine points and encoding of base elements

### Fine points and encoding of base elements

You skipped ### here, this can sometimes break some rendering systems particularly when they try to render table of contents.

Same thing with all of the following sections, they are all 1 too deep.

MicahZoltu · 2020-09-22T16:51:08Z

EIPS/eip-2539.md

+
+Curve parameters:
+
+BLS12-377 curve is fully defined by the following set of parameters (coefficient `A=0` for all BLS12 curves):


Suggested change

BLS12-377 curve is fully defined by the following set of parameters (coefficient `A=0` for all BLS12 curves):

[BLS12-377](../assets/eip-2539/bls12-377.pdf) curve is fully defined by the following set of parameters (coefficient `A=0` for all BLS12 curves):

This would be a good spot to have a relative link out to an attachment of the BLS12-377 paper. (note: if you accept this comment, make sure to actually add the paper as an asset!)

MicahZoltu · 2020-09-22T16:53:59Z

EIPS/eip-2539.md

+## Backwards Compatibility
+There are no backward compatibility questions.
+
+## Important notes


This is a non-standard section, and while non-standard sections aren't technically disallowed we prefer they not be included so the repository remains consistent. Can we move this into a subsection of the specification? It feels pretty specification like to me, though I suppose it is really just a "pro-tip".

MicahZoltu · 2020-09-22T16:59:43Z

EIPS/eip-2539.md

+type: Standards Track
+category: Core
+created: 2020-02-26
+requires: 1109, 2046


Suggested change

requires: 1109, 2046

Why are these required? It feels like a chain who doesn't have these implemented would still be able to include this EIP.

Adds BLS12-377 curve operations as precompiles.

rdubois-crypto · 2022-11-07T16:16:50Z

Sidenote: the divisibility of (p-1) by 2^44 in BLS12-377 Fp field could also benefit to Starks (PQ-snarks), as the FRI requires NTT operations to interpolate the trace polynomial. https://vitalik.ca/general/2017/11/22/starks_part_2.html.

burdges · 2023-09-19T00:59:26Z

It's not discussed here, but..

IRTF hash-to-curve spec says Edwards curves should use Elligator for their hash-to-curve, not WB or SWU. BLS12-377 should fall under this, given it has an Edwards form (and an extremely prominent one).

shamatar added 3 commits February 21, 2020 09:43

Merge pull request #1 from ethereum/master

9c4e52b

Make even with master

BLS12-377 initial spec

5759ace

set eip number

41dea96

Souptacular mentioned this pull request Mar 6, 2020

Ethereum Core Devs Meeting 82 Agenda ethereum/pm#155

Closed

axic added the type: Core label Apr 21, 2020

iAmMichaelConnor reviewed Jun 29, 2020

View reviewed changes

github-actions bot added the stale label Sep 8, 2020

github-actions bot removed the stale label Sep 14, 2020

prestwich mentioned this pull request Sep 17, 2020

Ethereum Core Devs Meeting 96 Agenda ethereum/pm#206

Closed

shamatar added 3 commits September 22, 2020 12:21

update to follow 2537

c5ca07e

cleanup and spellcheck

4388b02

extra whitespace?

47e4503

MicahZoltu approved these changes Sep 22, 2020

View reviewed changes

MicahZoltu merged commit ac73014 into ethereum:master Sep 22, 2020

tkstanczak pushed a commit to tkstanczak/EIPs that referenced this pull request Nov 7, 2020

BLS12-377 curve operations (ethereum#2539)

a362f60

Adds BLS12-377 curve operations as precompiles.

Arachnid pushed a commit to Arachnid/EIPs that referenced this pull request Mar 6, 2021

BLS12-377 curve operations (ethereum#2539)

97ded8a

Adds BLS12-377 curve operations as precompiles.


		To encode points involved in the operation one has to encode elements of the base field and the extension field.

		Base field element (Fp) is encoded as `48` bytes by performing BigEndian encoding of the corresponding (unsigned) integer. Corresponding integer must be less than field modulus.


		Base field element (Fp) is encoded as `48` bytes by performing BigEndian encoding of the corresponding (unsigned) integer. Corresponding integer must be less than field modulus.

		For elements of the quadratic extension field (Fp2) encoding is byte concatenation of individual encoding of the coefficients totaling in `96` bytes for a total encoding. For an Fp2 element in a form `el = c0 + c1 * v` where `v` is formal quadratic non-residue and `c0` and `c1` are Fp elements the corresponding byte encoding will be `encode(c0) \|\| encode(c1)` where `\|\|` means byte concatenation.

	This precompile adds operation on BLS12-377 curve (from Zexe paper) as a precompile in a set necessary to efficiently perform operations such as BLS signature verification and perform SNARKs verifications. Unique properties of BLS12-377 also later allow to have SNARKs that check BLS12-377 pairing in an efficient way and allow e.g. constant-size BLS signature aggregation.
	Adds BLS12-377 curve operations as precompiles.


		Multiexponentiation operation is included to efficiently aggregate public keys or individual signer's signatures during BLS signature verification.

		### Proposed addresses table

	#### Fine points and encoding of base elements
	### Fine points and encoding of base elements


		Curve parameters:

		BLS12-377 curve is fully defined by the following set of parameters (coefficient `A=0` for all BLS12 curves):

	BLS12-377 curve is fully defined by the following set of parameters (coefficient `A=0` for all BLS12 curves):
	[BLS12-377](../assets/eip-2539/bls12-377.pdf) curve is fully defined by the following set of parameters (coefficient `A=0` for all BLS12 curves):

Conversation

shamatar commented Feb 26, 2020

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

github-actions bot commented Sep 8, 2020

Uh oh!

prestwich commented Sep 14, 2020

Uh oh!

shamatar commented Sep 16, 2020

Uh oh!

prestwich commented Sep 16, 2020

Uh oh!

MicahZoltu left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

rdubois-crypto commented Nov 7, 2022

Uh oh!

burdges commented Sep 19, 2023

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

7 participants