Line data Source code
1 : #include "fd_vm_syscall.h"
2 :
3 : #if FD_HAS_S2NBIGNUM
4 :
5 : #include "../../../ballet/bigint/fd_big_mod_exp.h"
6 :
7 : /* sol_big_mod_exp (SIMD-0529): result = (base ^ exponent) mod modulus.
8 :
9 : All operands and the result are little-endian unsigned integers; the
10 : modulus must be odd and > 1. The computation lives in ballet
11 : (fd_big_mod_exp, wrapping s2n-bignum); this file handles the syscall
12 : ABI: reading params, validating, the compute-unit cost model, and
13 : writing the result.
14 :
15 : The syscall is gated behind the enable_big_mod_exp_syscall feature
16 : (registration in fd_vm_syscall.c); if it runs, the feature is active. */
17 :
18 : /* SIMD-0529 cost-model constants. */
19 : #define FD_BIG_MOD_EXP_BASE_CU (50UL)
20 0 : #define FD_BIG_MOD_EXP_MULT_COMPLEXITY_CONSTANT (22UL)
21 0 : #define FD_BIG_MOD_EXP_SETUP_MULTIPLICATIONS (12UL)
22 0 : #define FD_BIG_MOD_EXP_MULTIPLICATIONS_PER_EXPONENT_WORD (80UL)
23 0 : #define FD_BIG_MOD_EXP_CU_DIVISOR ( 4UL)
24 0 : #define FD_BIG_MOD_EXP_MOD_REDUCTION_CU_DIVISOR (15UL)
25 :
26 : /* BigModExpParams as laid out in VM memory (repr(C), 48 bytes, 8-byte
27 : aligned). Pointers are VM virtual addresses. */
28 : struct fd_vm_big_mod_exp_params {
29 : ulong base; /* vaddr */
30 : ulong base_len;
31 : ulong exponent; /* vaddr */
32 : ulong exponent_len;
33 : ulong modulus; /* vaddr */
34 : ulong modulus_len;
35 : };
36 : typedef struct fd_vm_big_mod_exp_params fd_vm_big_mod_exp_params_t;
37 :
38 : /* mult_complexity per SIMD-0529 */
39 : static inline ulong
40 0 : fd_big_mod_exp_mult_complexity( ulong operand_words ) {
41 0 : return operand_words*operand_words + FD_BIG_MOD_EXP_MULT_COMPLEXITY_CONSTANT;
42 0 : }
43 :
44 : /* adjusted_exponent_length per SIMD-0529 (EIP-198 form), over the
45 : little-endian exponent exp[0,exp_len). */
46 : static ulong
47 : fd_big_mod_exp_adjusted_exponent_length( uchar const * exp,
48 0 : ulong exp_len ) {
49 0 : if( exp_len<=32UL ) {
50 : /* highest set bit index (0-based) over the whole value; 0 if zero */
51 0 : for( ulong i=exp_len; i-->0UL; ) {
52 0 : if( exp[i] ) return i*8UL + (ulong)fd_ulong_find_msb( (ulong)exp[i] );
53 0 : }
54 0 : return 0UL;
55 0 : }
56 : /* exp_len>32 */
57 0 : ulong base_term = 8UL*( exp_len-32UL );
58 0 : ulong lo = exp_len-32UL;
59 0 : for( ulong i=exp_len; i-->lo; ) {
60 0 : if( exp[i] ) return base_term + (i-lo)*8UL + (ulong)fd_ulong_find_msb( (ulong)exp[i] );
61 0 : }
62 0 : return base_term;
63 0 : }
64 :
65 : /* decoded exponent == 1 (little-endian) */
66 : static inline int
67 : fd_big_mod_exp_exponent_is_one( uchar const * exp,
68 0 : ulong exp_len ) {
69 0 : if( FD_UNLIKELY( exp_len==0UL ) ) return 0;
70 0 : if( exp[0]!=1U ) return 0;
71 0 : for( ulong i=1UL; i<exp_len; i++ ) if( exp[i] ) return 0;
72 0 : return 1;
73 0 : }
74 :
75 : /* SIMD-0529 operation cost, i.e. what is charged on top of the flat
76 : FD_BIG_MOD_EXP_BASE_CU. */
77 : static ulong
78 : fd_big_mod_exp_operation_cost( uchar const * exp,
79 : ulong exp_len,
80 : ulong base_len,
81 0 : ulong mod_len ) {
82 0 : ulong operand_words = ( fd_ulong_max( base_len, mod_len ) + 7UL ) / 8UL;
83 0 : ulong mult_complexity = fd_big_mod_exp_mult_complexity( operand_words );
84 0 : if( fd_big_mod_exp_exponent_is_one( exp, exp_len ) ) {
85 : /* a single modular reduction of the base */
86 0 : return (mult_complexity + FD_BIG_MOD_EXP_MOD_REDUCTION_CU_DIVISOR - 1UL)
87 0 : / FD_BIG_MOD_EXP_MOD_REDUCTION_CU_DIVISOR;
88 0 : }
89 0 : ulong exponent_words = fd_big_mod_exp_adjusted_exponent_length( exp, exp_len ) / 64UL + 1UL;
90 0 : ulong multiplications = FD_BIG_MOD_EXP_SETUP_MULTIPLICATIONS
91 0 : + FD_BIG_MOD_EXP_MULTIPLICATIONS_PER_EXPONENT_WORD*exponent_words;
92 : /* operand_words<=64 and exponent_words<=64, so the product is below 2^25 */
93 0 : return (mult_complexity*multiplications + FD_BIG_MOD_EXP_CU_DIVISOR - 1UL)
94 0 : / FD_BIG_MOD_EXP_CU_DIVISOR;
95 0 : }
96 :
97 : int
98 : fd_vm_syscall_sol_big_mod_exp( /**/ void * _vm,
99 : /**/ ulong params_vaddr,
100 : /**/ ulong result_vaddr,
101 : FD_PARAM_UNUSED ulong r3,
102 : FD_PARAM_UNUSED ulong r4,
103 0 : FD_PARAM_UNUSED ulong r5 ) {
104 0 : fd_vm_t * vm = (fd_vm_t *)_vm;
105 :
106 : /* Charge the flat base cost up front, before any translation that could
107 : fail without being paid for. */
108 0 : FD_VM_CU_UPDATE( vm, FD_BIG_MOD_EXP_BASE_CU );
109 :
110 : /* Read the params record (48B, 8-byte aligned). */
111 0 : fd_vm_big_mod_exp_params_t const * params =
112 0 : (fd_vm_big_mod_exp_params_t const *)FD_VM_MEM_HADDR_LD(
113 0 : vm, params_vaddr, FD_VM_ALIGN_RUST_U64, sizeof(fd_vm_big_mod_exp_params_t) );
114 :
115 0 : ulong base_len = params->base_len;
116 0 : ulong exp_len = params->exponent_len;
117 0 : ulong mod_len = params->modulus_len;
118 :
119 : /* Length validation rejects only operands over the maximum; mod_len==0 is
120 : deliberately allowed through. */
121 0 : if( FD_UNLIKELY( base_len>FD_BIG_MOD_EXP_MAX_BYTES ||
122 0 : exp_len >FD_BIG_MOD_EXP_MAX_BYTES ||
123 0 : mod_len >FD_BIG_MOD_EXP_MAX_BYTES ) ) {
124 0 : FD_VM_ERR_FOR_LOG_SYSCALL( vm, FD_VM_SYSCALL_ERR_INVALID_LENGTH );
125 0 : return FD_VM_SYSCALL_ERR_INVALID_LENGTH;
126 0 : }
127 :
128 : /* Translate the exponent and charge before translating the base and modulus. */
129 0 : uchar const * exp = exp_len ? FD_VM_MEM_HADDR_LD( vm, params->exponent, FD_VM_ALIGN_RUST_U8, exp_len ) : (uchar const *)"";
130 :
131 0 : FD_VM_CU_UPDATE( vm, fd_big_mod_exp_operation_cost( exp, exp_len, base_len, mod_len ) );
132 :
133 0 : uchar const * base = base_len ? FD_VM_MEM_HADDR_LD( vm, params->base, FD_VM_ALIGN_RUST_U8, base_len ) : (uchar const *)"";
134 0 : uchar const * mod = mod_len ? FD_VM_MEM_HADDR_LD( vm, params->modulus, FD_VM_ALIGN_RUST_U8, mod_len ) : (uchar const *)"";
135 :
136 : /* An empty, zero, one or even modulus fails here, having been charged. */
137 0 : if( FD_UNLIKELY( !fd_big_mod_exp_modulus_is_valid( mod, mod_len ) ) ) {
138 0 : FD_VM_ERR_FOR_LOG_SYSCALL( vm, FD_VM_SYSCALL_ERR_INVALID_ATTRIBUTE );
139 0 : return FD_VM_SYSCALL_ERR_INVALID_ATTRIBUTE;
140 0 : }
141 :
142 0 : uchar * out = FD_VM_MEM_HADDR_ST( vm, result_vaddr, FD_VM_ALIGN_RUST_U8, mod_len );
143 :
144 0 : int err = fd_big_mod_exp( out, base, base_len, exp, exp_len, mod, mod_len );
145 0 : if( FD_UNLIKELY( err!=FD_BIG_MOD_EXP_SUCCESS ) ) {
146 0 : FD_VM_ERR_FOR_LOG_SYSCALL( vm, FD_VM_SYSCALL_ERR_INVALID_ATTRIBUTE );
147 0 : return FD_VM_SYSCALL_ERR_INVALID_ATTRIBUTE;
148 0 : }
149 :
150 0 : vm->reg[0] = 0UL;
151 0 : return FD_VM_SUCCESS;
152 0 : }
153 :
154 : #endif /* FD_HAS_S2NBIGNUM */
|
