> ## Documentation Index > Fetch the complete documentation index at: https://voltaire.tevm.sh/llms.txt > Use this file to discover all available pages before exploring further. # 0x0D BLS12-381 G1 MSM > BLS12-381 G1 multi-scalar multiplication **This page is a placeholder.** All examples on this page are currently AI-generated and are not correct. This documentation will be completed in the future with accurate, tested examples. ## Overview **Address:** `0x000000000000000000000000000000000000000d` **Introduced:** Prague (EIP-2537) **EIP:** [EIP-2537](https://eips.ethereum.org/EIPS/eip-2537) The BLS12-381 G1 MSM (Multi-Scalar Multiplication) precompile performs efficient batch scalar multiplication on the BLS12-381 curve's G1 group. It computes the sum of multiple points each multiplied by their respective scalars: `k1*P1 + k2*P2 + ... + kn*Pn`. This operation is fundamental for BLS signature aggregation, zkSNARK verification, and efficient batch cryptographic operations. MSM is significantly more efficient than performing individual multiplications and additions separately. The precompile uses optimized algorithms (like Pippenger's algorithm) to compute batch operations with sublinear scaling. EIP-2537 introduces BLS12-381 operations to enable efficient aggregate signatures used in Ethereum 2.0 consensus, where thousands of validator signatures must be verified together. ## Gas Cost **Dynamic with discount:** `(BASE_GAS * k * discount) / 1000` * **BASE\_GAS:** 12000 * **k:** Number of point-scalar pairs * **discount:** Discount factor based on batch size (EIP-2537 table) ### Discount Table | Pairs (k) | Discount | Gas per pair | | --------- | -------- | ------------ | | 1 | 1000 | 12000 | | 2-3 | 820 | 9840 | | 4-7 | 580 | 6960 | | 8-15 | 430 | 5160 | | 16-31 | 320 | 3840 | | 32-63 | 250 | 3000 | | 64-127 | 200 | 2400 | | 128+ | 174 | 2088 | **Example:** For 32 pairs: `(12000 * 32 * 250) / 1000 = 96000 gas` The discount reflects the efficiency gains from batch processing, making aggregate operations economical. ## Input Format ``` Offset | Length | Description ----------|--------|------------- 0 | 64 | x1 (first point x-coordinate, big-endian, left-padded) 64 | 64 | y1 (first point y-coordinate, big-endian, left-padded) 128 | 32 | k1 (first scalar, big-endian) 160 | 64 | x2 (second point x-coordinate) 224 | 64 | y2 (second point y-coordinate) 288 | 32 | k2 (second scalar) ... | ... | (repeat for each pair) n*160 | 64 | xn (nth point x-coordinate) n*160+64 | 64 | yn (nth point y-coordinate) n*160+128 | 32 | kn (nth scalar) ``` Total input length: `160 * k` bytes (must be exact multiple of 160) Each point must satisfy the curve equation: `y^2 = x^3 + 4` over BLS12-381 base field. Point at infinity represented as all zeros (128 bytes). ## Output Format ``` Offset | Length | Description -------|--------|------------- 0 | 64 | x (result point x-coordinate, big-endian, left-padded) 64 | 64 | y (result point y-coordinate, big-endian, left-padded) ``` Total output length: 128 bytes (single aggregated point) ## TypeScript Example ```typescript theme={null} import { execute, PrecompileAddress } from '@tevm/voltaire/precompiles'; import { Hardfork } from '@tevm/voltaire/primitives/Hardfork'; // BLS12-381 G1 generator (48 bytes, left-padded to 64) const g1_x = Bytes64('0x000000000000000000000000000000000017f1d3a73197d7942695638c4fa9ac0fc3688c4f9774b905a14e3a3f171bac586c55e83ff97a1aeffb3af00adb22c6bb'); const g1_y = Bytes64('0x0000000000000000000000000000000008b3f481e3aaa0f1a09e30ed741d8ae4fcf5e095d5d00af600db18cb2c04b3edd03cc744a2888ae40caa232946c5e7e1'); // Compute: 3*G + 5*G + 7*G = 15*G (3 pairs) const input = new Uint8Array(160 * 3); // First pair: (G, 3) input.set(g1_x, 0); input.set(g1_y, 64); const scalar1 = Bytes32('0x0000000000000000000000000000000000000000000000000000000000000003'); input.set(scalar1, 128); // Second pair: (G, 5) input.set(g1_x, 160); input.set(g1_y, 224); const scalar2 = Bytes32('0x0000000000000000000000000000000000000000000000000000000000000005'); input.set(scalar2, 288); // Third pair: (G, 7) input.set(g1_x, 320); input.set(g1_y, 384); const scalar3 = Bytes32('0x0000000000000000000000000000000000000000000000000000000000000007'); input.set(scalar3, 448); // Gas calculation: k=3, discount=820 // gas = (12000 * 3 * 820) / 1000 = 29520 const result = execute( PrecompileAddress.BLS12_G1_MSM, input, 50000n, Hardfork.PRAGUE ); if (result.success) { console.log('Result: 15*G (sum of 3*G + 5*G + 7*G)'); console.log('Gas used:', result.gasUsed); // 29520 } else { console.error('Error:', result.error); } ``` ## Zig Example ```zig theme={null} const std = @import("std"); const precompiles = @import("precompiles"); pub fn main() !void { var gpa = std.heap.GeneralPurposeAllocator(.{}){}; defer _ = gpa.deinit(); const allocator = gpa.allocator(); // BLS12-381 G1 generator (padded to 64 bytes) const g1_x = [_]u8{ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x17, 0xf1, 0xd3, 0xa7, 0x31, 0x97, 0xd7, 0x94, 0x26, 0x95, 0x63, 0x8c, 0x4f, 0xa9, 0xac, 0x0f, 0xc3, 0x68, 0x8c, 0x4f, 0x97, 0x74, 0xb9, 0x05, 0xa1, 0x4e, 0x3a, 0x3f, 0x17, 0x1b, 0xac, 0x58, 0x6c, 0x55, 0xe8, 0x3f, 0xf9, 0x7a, 0x1a, 0xef, 0xfb, 0x3a, 0xf0, 0x0a, 0xdb, 0x22, 0xc6, 0xbb, }; const g1_y = [_]u8{ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x08, 0xb3, 0xf4, 0x81, 0xe3, 0xaa, 0xa0, 0xf1, 0xa0, 0x9e, 0x30, 0xed, 0x74, 0x1d, 0x8a, 0xe4, 0xfc, 0xf5, 0xe0, 0x95, 0xd5, 0xd0, 0x0a, 0xf6, 0x00, 0xdb, 0x18, 0xcb, 0x2c, 0x04, 0xb3, 0xed, 0xd0, 0x3c, 0xc7, 0x44, 0xa2, 0x88, 0x8a, 0xe4, 0x0c, 0xaa, 0x23, 0x29, 0x46, 0xc5, 0xe7, 0xe1, }; // Compute MSM with 4 pairs: 1*G + 2*G + 3*G + 4*G = 10*G var input: [640]u8 = [_]u8{0} ** 640; var i: usize = 0; while (i < 4) : (i += 1) { const offset = i * 160; @memcpy(input[offset..offset+64], &g1_x); @memcpy(input[offset+64..offset+128], &g1_y); input[offset + 159] = @intCast(i + 1); // scalars: 1, 2, 3, 4 } const result = try precompiles.bls12_g1_msm.execute(allocator, &input, 100000); defer result.deinit(allocator); std.debug.print("Result: 10*G (1*G + 2*G + 3*G + 4*G)\n", .{}); std.debug.print("Gas used: {}\n", .{result.gas_used}); } ``` ## Error Conditions * **Out of gas:** gasLimit \< calculated gas cost * **Invalid input length:** input.len % 160 != 0 or input.len == 0 * **Invalid point:** Any point doesn't satisfy curve equation y² = x³ + 4 * **Point not in subgroup:** Any point not in correct subgroup * **Coordinate out of range:** Any x or y >= field modulus Invalid inputs cause precompile to return `error.InvalidPoint`. ## MSM Properties * **Linearity:** MSM(P, k) = k1*P1 + k2*P2 + ... + kn\*Pn * **Zero scalars:** Points with k=0 contribute nothing to sum * **Point at infinity:** Infinity points with any scalar contribute nothing * **Empty input:** Returns error (must have at least one pair) * **Order independence:** Result same regardless of pair order ## Use Cases * **BLS signature aggregation:** Aggregate thousands of validator signatures * **Batch verification:** Verify multiple signatures simultaneously * **zkSNARK verification:** Multi-scalar multiplications in proof verification * **Threshold signatures:** Combine signature shares efficiently * **Polynomial commitments:** KZG-style commitments on BLS12-381 * **Consensus protocols:** Ethereum 2.0 beacon chain signature aggregation * **Privacy protocols:** Efficient batch operations in zk-Rollups ## Implementation Details * **Zig:** Uses blst library's optimized MSM implementation * **TypeScript:** Manual loop (naive implementation, less efficient) * **Algorithm:** Pippenger's algorithm for efficient batch processing * **Optimization:** Exploits parallelism and precomputation * **Memory:** Temporary storage proportional to number of pairs ## Performance Characteristics * **Time complexity:** O(k \* log(k)) with Pippenger's algorithm * **Gas discount:** Increases with batch size (sublinear cost scaling) * **Break-even point:** \~4 pairs more efficient than separate operations * **Maximum efficiency:** Large batches (64+ pairs) get best discount ## Gas Cost Comparison Comparing MSM vs individual operations: ```typescript theme={null} // Individual: 3 muls + 2 adds // Cost: 3*12000 + 2*500 = 37000 gas // MSM with 3 pairs (discount 820) // Cost: (12000 * 3 * 820) / 1000 = 29520 gas // Savings: 7480 gas (20% reduction) // With 32 pairs: // Individual: 32*12000 + 31*500 = 399500 gas // MSM: (12000 * 32 * 250) / 1000 = 96000 gas // Savings: 303500 gas (76% reduction!) ``` ## Algorithm: Pippenger's Method Pippenger's algorithm efficiently computes MSM by: 1. **Bucketing:** Group scalars by bit windows 2. **Bucket sums:** Compute point sums for each bucket 3. **Window reduction:** Combine buckets with doubling 4. **Final sum:** Aggregate window results This reduces operations from O(k \* 256) to O(k \* log(256)), where k is number of pairs. ## Discount Rationale EIP-2537 discount table reflects: * **Algorithmic efficiency:** Pippenger's sublinear scaling * **Amortization:** Fixed costs spread over more operations * **Hardware optimization:** Better cache utilization with batches * **Incentive:** Encourage batch operations for network efficiency ## Security Considerations * All points validated individually before processing * Scalar range checked (any 256-bit value accepted) * Constant-time operations prevent timing attacks * Point at infinity handled correctly in accumulation * Uses audited blst library for security-critical operations ## Comparison with G1 Mul | Operation | Single (Mul) | Batch (MSM) | | ---------- | -------------- | -------------- | | Pairs (k) | 1 | 1-128+ | | Base gas | 12000 | 12000 | | Discount | None | 174-1000 | | Algorithm | Double-and-add | Pippenger | | Efficiency | O(log k) | O(k log log k) | ## Related * [Precompile: BLS12-381 G1 Add](/evm/precompiles/bls12-g1-add) * [Precompile: BLS12-381 G1 Mul](/evm/precompiles/bls12-g1-mul) * [Precompile: BLS12-381 G2 MSM](/evm/precompiles/bls12-g2-msm) * [Precompile: BLS12-381 Pairing](/evm/precompiles/bls12-pairing) * [EIP-2537: Precompiled Contracts for BLS12-381 Curve Operations](https://eips.ethereum.org/EIPS/eip-2537) * [Pippenger's Algorithm](https://link.springer.com/chapter/10.1007/3-540-46766-1_9) * [BLS12-381 Specification](https://hackmd.io/@benjaminion/bls12-381)