We introduce the Byzantine Approximate Agreement Cross-chain Task in the smart contract model, a recently proposed framework for capturing computation in blockchain-based systems. In this model, a set of m parties, of which up to a minority may be Byzantine, interact via n trusted smart contracts deployed on multiple independent ledgers (blockchains). We present two protocols that solve the Byzantine Approximate Agreement Cross-chain Task and prove their correctness. Both protocols are optimal with respect to Byzantine resilience - tolerating a minority of Byzantine parties - and time complexity, completing in two rounds in synchronous executions. We further analyze their bit complexity within the smart contract model. The first protocol requires \(\mathcal {O}(k)\) bits of local memory per party, where k denotes the number of bits needed to encode the proposed values, and achieves a total message bit complexity of \(\mathcal {O}(n\cdot m\cdot k)\) . The second protocol reduces the local memory usage at each party to \(\mathcal {O}(1)\) bits, at the cost of increasing the total message bit complexity to \(\mathcal {O}(n^2\cdot m\cdot k)\) .

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Byzantine Approximate Agreement Cross-chain Task

  • Maurice Herlihy,
  • Bo Pan,
  • Maria Potop-Butucaru,
  • Liuba Shrira

摘要

We introduce the Byzantine Approximate Agreement Cross-chain Task in the smart contract model, a recently proposed framework for capturing computation in blockchain-based systems. In this model, a set of m parties, of which up to a minority may be Byzantine, interact via n trusted smart contracts deployed on multiple independent ledgers (blockchains). We present two protocols that solve the Byzantine Approximate Agreement Cross-chain Task and prove their correctness. Both protocols are optimal with respect to Byzantine resilience - tolerating a minority of Byzantine parties - and time complexity, completing in two rounds in synchronous executions. We further analyze their bit complexity within the smart contract model. The first protocol requires \(\mathcal {O}(k)\) bits of local memory per party, where k denotes the number of bits needed to encode the proposed values, and achieves a total message bit complexity of \(\mathcal {O}(n\cdot m\cdot k)\) . The second protocol reduces the local memory usage at each party to \(\mathcal {O}(1)\) bits, at the cost of increasing the total message bit complexity to \(\mathcal {O}(n^2\cdot m\cdot k)\) .