#include <transcript_builder.hpp>

Classes
struct	TranscriptRow

struct	VMState

Public Types
using	CycleGroup = bb::g1

using	FF = grumpkin::fr

using	Element = typename CycleGroup::element

using	AffineElement = typename CycleGroup::affine_element

using	Accumulator = typename std::vector< Element >

Static Public Member Functions
static AffineElement	offset_generator ()
	Computes offset_generator group element.

static AffineElement	remove_offset_generator (const AffineElement &other)

static std::vector< TranscriptRow >	compute_rows (const std::vector< ECCVMOperation > &vm_operations, const uint32_t total_number_of_muls)
	Computes the ECCVM transcript rows.

Static Private Member Functions
static void	populate_transcript_row (TranscriptRow &row, const ECCVMOperation &entry, const VMState &state, const uint32_t num_muls, const bool msm_transition, const bool next_not_msm)
	Populate the transcript rows with the information parsed after the first iteration over the ECCOpQueue.

static void	process_mul (const ECCVMOperation &entry, VMState &updated_state, const VMState &state)
	Process scalar multiplication from the ECCOpQueue.

static void	process_add (const ECCVMOperation &entry, VMState &updated_state, const VMState &state)
	Process addition from the ECCOpQueue.

static void	process_msm_transition (TranscriptRow &row, VMState &updated_state, const VMState &state)

static void	normalize_accumulators (Accumulator &accumulator_trace, Accumulator &msm_accumulator_trace, std::vector< Element > &intermediate_accumulator_trace)
	Batched conversion of points in accumulators from Jacobian coordinates \( (X, Y, Z) \) to affine coordinates \( (x = X/Z^2, y = Y/Z^3 ) \).

static void	add_affine_coordinates_to_transcript (std::vector< TranscriptRow > &transcript_state, const Accumulator &accumulator_trace, const Accumulator &msm_accumulator_trace, const Accumulator &intermediate_accumulator_trace)
	Once the point coordinates are converted from Jacobian to affine coordinates, we populate \((x,y)\)-coordinates of the corresponding accumulators.

static void	compute_inverse_trace_coordinates (const bool msm_transition, const TranscriptRow &row, const Element &msm_output, FF &transcript_msm_x_inverse_trace, Element &msm_accumulator_trace, Element &accumulator_trace, FF &inverse_trace_x, FF &inverse_trace_y)
	Compute the difference between the x and y coordinates of two points.

static void	compute_lambda_numerator_and_denominator (TranscriptRow &row, const ECCVMOperation &entry, const Element &intermediate_accumulator, const Element &accumulator, FF &add_lambda_numerator, FF &add_lambda_denominator)
	If entry is not a point at infinity, compute the slope between the VM entry point and current accumulator, else compute the slope between the accumulators.

static void	finalize_transcript (std::vector< TranscriptRow > &transcript_state, const VMState &updated_state)
	Place the number of the MSMs and the coordinates of the accumualted result in the last row of the transcript.

Detailed Description

Definition at line 15 of file transcript_builder.hpp.

Member Typedef Documentation

◆ Accumulator

using bb::ECCVMTranscriptBuilder::Accumulator = typename std::vector<Element>

Definition at line 21 of file transcript_builder.hpp.

◆ AffineElement

using bb::ECCVMTranscriptBuilder::AffineElement = typename CycleGroup::affine_element

Definition at line 20 of file transcript_builder.hpp.

◆ CycleGroup

using bb::ECCVMTranscriptBuilder::CycleGroup = bb::g1

Definition at line 17 of file transcript_builder.hpp.

◆ Element

using bb::ECCVMTranscriptBuilder::Element = typename CycleGroup::element

Definition at line 19 of file transcript_builder.hpp.

◆ FF

using bb::ECCVMTranscriptBuilder::FF = grumpkin::fr

Definition at line 18 of file transcript_builder.hpp.

Member Function Documentation

◆ add_affine_coordinates_to_transcript()

static void bb::ECCVMTranscriptBuilder::add_affine_coordinates_to_transcript	(	std::vector< TranscriptRow > &	transcript_state,
		const Accumulator &	accumulator_trace,
		const Accumulator &	msm_accumulator_trace,
		const Accumulator &	intermediate_accumulator_trace
	)

inlinestaticprivate

Once the point coordinates are converted from Jacobian to affine coordinates, we populate \((x,y)\)-coordinates of the corresponding accumulators.

Parameters

transcript_state	ECCVM Transcript
accumulator_trace	Accumulator for all group ops
msm_accumulator_trace	Accumulator for all MSMs
intermediate_accumulator_trace	Accumulator for the ongoing MSM

Definition at line 468 of file transcript_builder.hpp.

◆ compute_inverse_trace_coordinates()

static void bb::ECCVMTranscriptBuilder::compute_inverse_trace_coordinates	(	const bool	msm_transition,
		const TranscriptRow &	row,
		const Element &	msm_output,
		FF &	transcript_msm_x_inverse_trace,
		Element &	msm_accumulator_trace,
		Element &	accumulator_trace,
		FF &	inverse_trace_x,
		FF &	inverse_trace_y
	)

inlinestaticprivate

Compute the difference between the x and y coordinates of two points.

inverse_trace_x and inverse_trace_y are used to store the inverse of the difference between the x and y coordinates of two elliptic curve points, which is used in the calculation of the slope ( \( \lambda \)) during point addition and doubling.

Computing the inverse is expensive, therefore to optimize the overall calculation, all the required inversions are deferred and computed at once, rather than performing individual inversions for each operation.

In the case of MSM transition, we compute the difference between the coordinates of the MSM output accumulated in the intermediate accumulator and the point in the current accumulator.

In the case of point addition, we compute the difference between the coordinates of the current row in ECCVMOperations and the point in the current accumulator.

Definition at line 507 of file transcript_builder.hpp.

◆ compute_lambda_numerator_and_denominator()

static void bb::ECCVMTranscriptBuilder::compute_lambda_numerator_and_denominator	(	TranscriptRow &	row,
		const ECCVMOperation &	entry,
		const Element &	intermediate_accumulator,
		const Element &	accumulator,
		FF &	add_lambda_numerator,
		FF &	add_lambda_denominator
	)

inlinestaticprivate

If entry is not a point at infinity, compute the slope between the VM entry point and current accumulator, else compute the slope between the accumulators.

transcript_add_lambda represents the slope ( \( \lambda \)) of the line connecting two points on the elliptic curve during the point addition process or the tangent line at a point during point doubling.

Used for computing new x and y coordinates when adding or doubling points.

**Point Addition (when \( x_1 \neq x_2\) )**: If two points \( P(x_1, y_1) \) and \( Q(x_2, y_2) \) are distinct, the slope \( \lambda \) of the line passing through them is calculated as:
\[ \lambda = \frac{y_2 - y_1}{x_2 - x_1} \]
This \( \lambda \) is used to compute the coordinates of the resulting point \( R(x_r, y_r) \):
\[ x_r = \lambda^2 - x_1 - x_2 \]

\[ y_r = \lambda(x_1 - x_r) - y_1 \]
Point Doubling (when x1 = x2): If the points are the same (i.e., point doubling), the slope \( \lambda \) is computed as the tangent line at the point:
\[ \lambda = \frac{3x_1^2 + a}{2y_1} \]
where \( a \) is the curve parameter. In our case, \( a = 0 \).

Parameters

row
entry
intermediate_accumulator
accumulator
add_lambda_numerator
add_lambda_denominator

Definition at line 570 of file transcript_builder.hpp.

◆ compute_rows()

static std::vector< TranscriptRow > bb::ECCVMTranscriptBuilder::compute_rows	(	const std::vector< ECCVMOperation > &	vm_operations,
		const uint32_t	total_number_of_muls
	)

inlinestatic

Computes the ECCVM transcript rows.

This method processes the series of group operations extracted from ECCOpQueue, computing multi-scalar multiplications and point additions, while creating the transcript of the operations. In the first loop over the rows of ECCOpQueue, it mostly populates the TranscriptRow with boolean flags indicating the structure of the ops being performed, while performing elliptic curve operations in Jacobian (a.k.a projective) coordinates, and then normalizes these points to affine coordinates. Batch inversion is used to optimize expensive finite field inversions.

Parameters

vm_operations	ECCOpQueue
total_number_of_muls	The total number of multiplications in the series of operations.

Returns: A vector of TranscriptRows

Definition at line 137 of file transcript_builder.hpp.

◆ finalize_transcript()

static void bb::ECCVMTranscriptBuilder::finalize_transcript	(	std::vector< TranscriptRow > &	transcript_state,
		const VMState &	updated_state
	)

inlinestaticprivate

Place the number of the MSMs and the coordinates of the accumualted result in the last row of the transcript.

Parameters

transcript_state
updated_state

Definition at line 611 of file transcript_builder.hpp.

◆ normalize_accumulators()

static void bb::ECCVMTranscriptBuilder::normalize_accumulators	(	Accumulator &	accumulator_trace,
		Accumulator &	msm_accumulator_trace,
		std::vector< Element > &	intermediate_accumulator_trace
	)

inlinestaticprivate

Batched conversion of points in accumulators from Jacobian coordinates \( (X, Y, Z) \) to affine coordinates \( (x = X/Z^2, y = Y/Z^3 ) \).

Parameters

accumulator_trace	Accumulator for all group ops
msm_accumulator_trace	Accumulator for all MSMs
intermediate_accumulator_trace	Accumulator for the ongoing MSM

Definition at line 451 of file transcript_builder.hpp.

◆ offset_generator()

static AffineElement bb::ECCVMTranscriptBuilder::offset_generator ( )

inlinestatic

Computes offset_generator group element.

"offset generator" is used when performing multi-scalar-multiplications to ensure an HONEST prover never triggers incomplete point addition formulae. i.e. we don't need to constrain point doubling or points at infinity when computing an MSM The MSM accumulator is initialized to offset_generator. When adding the MSM result into the transcript accumulator, the contribution of the offset generator to the MSM result is removed (offset_generator * 2^{124})

Returns: AffineElement

Definition at line 97 of file transcript_builder.hpp.

◆ populate_transcript_row()

static void bb::ECCVMTranscriptBuilder::populate_transcript_row	(	TranscriptRow &	row,
		const ECCVMOperation &	entry,
		const VMState &	state,
		const uint32_t	num_muls,
		const bool	msm_transition,
		const bool	next_not_msm
	)

inlinestaticprivate

Populate the transcript rows with the information parsed after the first iteration over the ECCOpQueue.

Processes the state of the accumulator, base point, and the operation flags (addition, multiplication, equality check, and reset), as well as information about MSM transitions.

Processes the following values:

The 'accumulator_is_empty' flag.
Base point's coordinates when applicable.
MSM transitions and the number of MSMs.
Setting flags for add, mul, eq, or reset operations.
The opcode field.

Parameters

row	The transcript row to populate.
entry	The current VM operation being processed.
state	The current VM state before the operation is applied.
num_muls	The number of multiplications involved in the current operation.
msm_transition	A boolean indicating whether the operation represents an MSM transition.
next_not_msm	A boolean indicating if the next operation is not part of an ongoing MSM.

Definition at line 346 of file transcript_builder.hpp.

◆ process_add()

static void bb::ECCVMTranscriptBuilder::process_add	(	const ECCVMOperation &	entry,
		VMState &	updated_state,
		const VMState &	state
	)

inlinestaticprivate

Process addition from the ECCOpQueue.

If the entry indicates an addition operation, the base point from the ECCOpQueue is added to the main accumulator.

Parameters

entry	Current ECCOpQueue entry
updated_state	The state of the ECCVM to be updated with the result of the addition
state	The current state of the ECCVM

Definition at line 407 of file transcript_builder.hpp.

◆ process_msm_transition()

static void bb::ECCVMTranscriptBuilder::process_msm_transition	(	TranscriptRow &	row,
		VMState &	updated_state,
		const VMState &	state
	)

inlinestaticprivate

Handles the transition that occurs after the completion of an MSM operation. It updates the accumulator with the result of the MSM, removing the contribution of the offset generator. It checks if the MSM output is a point at infinity and sets the corresponding flag in the transcript, and also sets the is_accumulator_empty flag.

Parameters

row	Current transcript row
updated_state	The state of the ECCVM to be updated with the result of the addition
state	The current state of the ECCVM

Definition at line 430 of file transcript_builder.hpp.

◆ process_mul()

static void bb::ECCVMTranscriptBuilder::process_mul	(	const ECCVMOperation &	entry,
		VMState &	updated_state,
		const VMState &	state
	)

inlinestaticprivate

Process scalar multiplication from the ECCOpQueue.

If the entry indicates a multiplication operation, the base point from the ECCOpQueue is multiplied by the corresponding full scalar. The result is added to the 'msm_accumulator' field of the updated state.

Parameters

entry	Current ECCOpQueue entry
updated_state	The state of the ECCVM to be updated with the result of the multiplication
state	The current state of the ECCVM

Definition at line 390 of file transcript_builder.hpp.

◆ remove_offset_generator()

static AffineElement bb::ECCVMTranscriptBuilder::remove_offset_generator ( const AffineElement & other )

inlinestatic

Definition at line 105 of file transcript_builder.hpp.

The documentation for this class was generated from the following file:

src/barretenberg/eccvm/transcript_builder.hpp

Classes

Public Types

Static Public Member Functions

Static Private Member Functions

Detailed Description

Member Typedef Documentation

◆ Accumulator

◆ AffineElement

◆ CycleGroup

◆ Element

◆ FF

Member Function Documentation

◆ add_affine_coordinates_to_transcript()

◆ compute_inverse_trace_coordinates()

◆ compute_lambda_numerator_and_denominator()

◆ compute_rows()

◆ finalize_transcript()

◆ normalize_accumulators()

◆ offset_generator()

◆ populate_transcript_row()

◆ process_add()

◆ process_msm_transition()

◆ process_mul()

◆ remove_offset_generator()