eth_pairings_cpp 0.1.1

EIP1962 reference implementation in C++
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167

#ifndef H_FROBENIUS
#define H_FROBENIUS

#include "../common.h"
#include "../element.h"
#include "../fp.h"
#include "../field.h"

template <usize M>
Repr<M + 1> calc_frobenius_factor_2(Repr<M> const &base, usize div, std::string const &err)
{
    // NON_RESIDUE**(((base) - 1) / div)
    auto const q_power = base;
    constexpr Repr<M> one = {1};
    auto power = q_power - one;
    Repr<M> const rdiv = {div};
    if (!cbn::is_zero(power % rdiv))
    {
        unknown_parameter_err("Failed to calculate Frobenius coeffs for " + err);
    }
    power = power / rdiv;
    return power;
}

template <usize N, usize M>
Fp<N> calc_frobenius_factor(Fp<N> const &non_residue, Repr<M> const &base, usize div, std::string const &err)
{
    auto const f = non_residue.pow(calc_frobenius_factor_2(base, div, err));
    return f;
}

template <class F>
std::vector<F> calculate_window_table(F base, usize window)
{
    std::vector<F> table;
    table.reserve(1 << (window - 1));

    auto acc = base;
    table.push_back(acc);
    auto square = acc;
    square.square();

    // pushed 1*G, 3*G, 5*G, etc (notation abuse, it's actually exp)
    for (auto i = 1; i < (1 << (window - 1)); i++)
    {
        acc.mul(square);
        table.push_back(acc);
    }

    return table;
}

template <class E>
class WindowExpBase
{
    u32 window_size;
    E one;
    std::vector<E> bases;

public:
    WindowExpBase(E base, E one, usize window) : window_size(window), one(one)
    {
        bases = calculate_window_table(base, window);
    }

    template <usize N>
    E exponentiate(Repr<N> scalar) const
    {
        auto const wnaf = windows(scalar);

        auto res = one;
        auto found_nonzero = false;

        for (auto it = wnaf.crbegin(); it != wnaf.crend(); it++)
        {
            auto const w = *it;
            if (w == 0 && found_nonzero)
            {
                res.square();
            }
            else if (w != 0)
            {
                found_nonzero = true;
                for (usize i = 0; i < window_size; i++)
                {
                    res.square();
                }
                usize const idx = w >> 1;
                res.mul(bases[idx]);
            }
        }

        return res;
    }

    template <usize N>
    std::vector<u64> windows(Repr<N> scalar) const
    {
        std::vector<u64> result;
        auto found_begining = false;
        u64 w = 0;
        u64 bit_count = 0;
        for (auto it = BitIterator(scalar); it.ok(); ++it)
        {
            auto const b = *it;
            if (b)
            {
                if (found_begining)
                {
                    w |= u64(1) << bit_count;
                    bit_count += 1;
                }
                else
                {
                    found_begining = true;
                    w |= u64(1) << bit_count;
                    bit_count += 1;
                }
            }
            else
            {
                if (found_begining)
                {
                    bit_count += 1;
                }
                else
                {
                    result.push_back(0);
                    continue;
                }
            }
            if (found_begining && bit_count == window_size)
            {
                result.push_back(w);
                w = 0;
                found_begining = false;
                bit_count = 0;
            }
        }

        if (w != 0)
        {
            // this is a last chunk if bit length is not divisible by window size
            result.push_back(w);
        }

        auto const n = result.size();
        for (usize i = 0; i < n; i++)
        {
            if (result.size() > 0)
            {
                if (result.back() == 0)
                {
                    result.pop_back();
                }
                else
                {
                    break;
                }
            }
        }

        return result;
    }
};

#endif