2014年論文《One-out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin》中有提及One out of N commitments containing 0的證明，具體的代碼實作可見：https://github.com/3for/libsigma
2015年論文《Short Accountable Ring Signatures Based on DDH》的具體代碼實作仍然見：https://github.com/3for/libsigma
1. Commitment to m ∈ { 0 , 1 } m\in\{0,1\} m∈{0,1}
- 2014年論文《One-out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin》中的實作算法為：
Sigma protocol用于one-out-of-many證明 - 2015年論文《Short Accountable Ring Signatures Based on DDH》中的實作算法為：【該論文中除了證明了任意的 b j , i ∈ { 0 , 1 } b_{j,i}\in \{0,1\} bj,i∈{0,1}，還額外證明了每行僅有一個元素為1，每行的總和為】 Prover proof具體的代碼實作見：
Sigma protocol用于one-out-of-many證明 https://github.com/3for/libsigma/blob/master/src/r1_proof_generator.hpp
namespace sigma {
template<class Exponent, class GroupElement>
R1ProofGenerator<Exponent,GroupElement>::R1ProofGenerator(
const GroupElement& g,
const std::vector<GroupElement>& h_gens,
const std::vector<Exponent>& b,
const Exponent& r,
int n ,
int m)
: g_(g)
, h_(h_gens)
, b_(b)
, r(r)
, n_(n)
, m_(m)
{
SigmaPrimitives<Exponent, GroupElement>::commit(g_, h_, b_, r, B_Commit);
}
template<class Exponent, class GroupElement>
const GroupElement& R1ProofGenerator<Exponent,GroupElement>::get_B() const {
return B_Commit;
}
template<class Exponent, class GroupElement>
void R1ProofGenerator<Exponent,GroupElement>::proof(
R1Proof<Exponent, GroupElement>& proof_out, bool skip_final_response) {
std::vector<Exponent> a;
proof(a, proof_out, skip_final_response);
}
template<class Exponent, class GroupElement>
void R1ProofGenerator<Exponent,GroupElement>::proof(
std::vector<Exponent>& a_out,
R1Proof<Exponent, GroupElement>& proof_out,
bool skip_final_response) {
a_out.resize(n_ * m_);
for(int j = 0; j < m_; ++j) {
for(int i = 1; i < n_; ++i) {
a_out[j * n_ + i].randomize();
a_out[j * n_] -= a_out[j * n_ + i];
}
}
// proof_out.B_ = B_Commit;
//compute A
GroupElement A;
while(!A.isMember() || A.isInfinity()) {
rA_.randomize();
SigmaPrimitives<Exponent, GroupElement>::commit(g_, h_, a_out, rA_, A);
}
proof_out.A_ = A;
//compute C
std::vector<Exponent> c;
c.resize(n_ * m_);
for(int i = 0; i < n_ * m_; ++i) {
c[i] = (a_out[i] * (Exponent(uint64_t(1)) - (Exponent(uint64_t(2)) * b_[i])));
}
GroupElement C;
while(!C.isMember() || C.isInfinity()) {
rC_.randomize();
SigmaPrimitives<Exponent, GroupElement>::commit(g_, h_, c, rC_, C);
}
proof_out.C_ = C;
//compute D
std::vector<Exponent> d;
d.resize(n_ * m_);
for(int i = 0; i < n_ * m_; i++) {
d[i] = ((a_out[i].square()).negate());
}
GroupElement D;
while(!D.isMember() || D.isInfinity()) {
rD_.randomize();
SigmaPrimitives<Exponent, GroupElement>::commit(g_, h_, d, rD_, D);
}
proof_out.D_ = D;
if (!skip_final_response) {
Exponent x;
std::vector<GroupElement> group_elements = {A, B_Commit, C, D};
SigmaPrimitives<Exponent, GroupElement>::generate_challenge(group_elements, x);
generate_final_response(a_out, x, proof_out);
}
}
template<class Exponent, class GroupElement>
void R1ProofGenerator<Exponent,GroupElement>::generate_final_response(
const std::vector<Exponent>& a,
const Exponent& challenge_x,
R1Proof<Exponent, GroupElement>& proof_out) {
//f
proof_out.f_.clear();
proof_out.f_.reserve(m_ * (n_ - 1));
for(int j = 0; j < m_; j++) {
for(int i = 1; i < n_; i++)
proof_out.f_.emplace_back(b_[(j * n_) + i] * challenge_x + a[(j * n_) + i]);
}
//zA
proof_out.ZA_ = r * challenge_x + rA_;
proof_out.ZC_ = rC_ * challenge_x + rD_;
}
} //namespace sigma
2. One out of N commitments containing 0
2014年論文《One-out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin》中有：
其中的 C o m c k ( 0 ; ρ k ) Com_{ck}(0; \rho_k) Comck(0;ρk)是對0的commit，隻是增加了random noise值 ρ k \rho_k ρk。
convert_to_sigma
函數會将 n u m num num轉化為mxn bit矩陣，該矩陣内所有元素均 ∈ { 0 , 1 } \in\{0,1\} ∈{0,1}，且每行僅有一個元素為1。
template<class Exponent, class GroupElement>
void SigmaPrimitives<Exponent, GroupElement>::convert_to_sigma(
uint64_t num,
uint64_t n,
uint64_t m,
std::vector<Exponent>& out) {
uint64_t rem;
uint64_t j = 0;
for (j = 0; j < m; ++j)
{
rem = num % n;
num /= n;
for (uint64_t i = 0; i < n; ++i) {
if(i == rem)
out.push_back(Exponent(unsigned(1)));
else
out.push_back(Exponent(unsigned(0)));
}
}
}
3. One out of N commitments containing 1
2015年論文《Short Accountable Ring Signatures Based on DDH》中有：
上圖算法需要修訂如下錯誤：
- Prover端有： G k = ∏ i = 0 N − 1 c i p i , k ⋅ E n c c k ( 0 ; ρ k ) G_k=\prod_{i=0}^{N-1}c_i^{p_{i,k}}\cdot Enc_{ck}(0;\rho_k) Gk=∏i=0N−1cipi,k⋅Encck(0;ρk)
- Verifier端有： ∏ i = 0 N − 1 c i ∏ j = 0 m − 1 f j , i j ⋅ ∏ k = 0 m − 1 G k − x k = E n c c k ( x m ; z ) \prod_{i=0}^{N-1}c_i^{\prod_{j=0}^{m-1}f_{j,i_j}}\cdot \prod_{k=0}^{m-1}G_k^{-x^k}=Enc_{ck}(x^m;z) ∏i=0N−1ci∏j=0m−1fj,ij⋅∏k=0m−1Gk−xk=Encck(xm;z)
在
https://github.com/3for/libsigma/blob/master/tests/protocol_tests.cpp
中的
one_out_of_n_one
測試用例中做了相應實作。
另外，實際代碼實作時，為保證所送出的commitment list為n^m個，不足的會按最後一個commitment補齊，此即為
one_out_of_n_padding
測試用例的用意。
參考資料：
[1] 2014年論文《One-out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin》
[2] 2015年論文《Short Accountable Ring Signatures Based on DDH》